Row-reduced column generation for degenerate master problems

Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to often suffer from degeneracy in the master problem. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation method that may take advantage of degenerate solutions. The idea is to reduce the number of constraints to the number of strictly positive basic variables in the current master problem solution. The advantage of this row-reduction is a smaller working basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem, itself eventually solved by column generation, that needs to generate weighted subsets of variables that are said compatible with the row-reduction, if possible. Such a subset of variables gives rise to a strict improvement in the objective function value if the weighted combination of the reduced costs is negative. We thus state, as a by-product, a necessary and sufficient optimality condition for linear programming.     

Parallel arc-allocation algorithms for optimizing generalized networks

Two parallel shared-memory algorithms are presented for the optimization of generalized networks. These algorithms are based on the allocation of arc-related operations in the (generalized) network simplex method. One method takes advantage of the multi-tree structure of basic solutions and performs pivot operations in parallel, utilizing locking to ensure correctness. The other algorithm utilizes only one processor for sequential pivoting, but parallelizes the pricing operation and overlaps this task with pivoting in a speculative manner (i.e. since pivoting and pricing involve data dependencies, a candidate for flow change generated by the pricing processors is not guaranteed to be acceptable, but in practice generally has this property). The relative performance of these two methods (on the Sequent Symmetry S81 multiprocessor) is compared and contrasted with that of a fast sequential algorithm on a set of large-scale test problems of up to 1,000,000 arcs.This research was supported in part by NSF grant CCR-8709952 and AFOSR grant AFOSR-86-0194.     

Eliminating columns in the simplex method for linear programming

We propose a column-eliminating technique for the simplex method of linear programming. A pricing criterion is developed for checking whether a dual hyperplane corresponding to a column intersects a simplex containing all of the optimal dual feasible solutions. If the dual hyperplane has no intersection with this simplex, we can eliminate the corresponding column from further computation during the course of the simplex method.The author is grateful for many discussions with Professor G. B. Dantzig, Stanford University, and for his valuable suggestions about this work. The author also gratefully acknowledges the editor and two referees for their very helpful comments, corrections, and remarks.     

A General Pricing Scheme for the Simplex Method

In the simplex method for linear programming the algorithmic step of checking the reduced costs of nonbasic variables is called the “pricing” step. If these reduced costs are all of the “right sign” the current basis (and solution) is optimal, if not, this procedure selects a candidate vector that looks profitable for inclusion in the basis. While theoretically the choice of any profitable vector will lead to a finite termination (provided degeneracy is handled properly) but the number of iterations until termination depends very heavily on the actual choice (which is defined by the selection rule applied). Pricing has long been an area of heuristics to help make better selection. As a result, many different and sophisticated pricing strategies have been developed, implemented and tested. So far none of them is known to be dominating all others in all cases. Therefore, advanced simplex solvers need to be equipped with many strategies so that the most suitable one can be activated for each individual problem instance. In this paper we present a general pricing scheme. It creates a large flexibility in pricing. It is controlled by three parameters. With different settings of the parameters many of the known strategies can be reproduced as special cases. At the same time, the framework makes it possible to define new strategies or variants of them. The scheme is equally applicable to general and network simplex algorithms.     

A degeneracy exploiting LU factorization for the simplex method

For general sparse linear programs two of the most efficient implementations of the LU factorization with Bartels—Golub updating are due to Reid and Saunders. This paper presents an alternative approach which achieves fast execution times for degenerate simplex method iterations, especially when used with multiple pricing. The method should have wide applicability since the simplex method performs a high proportion of degenerate iterations on most practical problems. A key feature of Saunders' method is combined with the updating strategy of Reid so as to make the scheme suitable for implementation out of core. Its efficiency is confirmed by experimental results.     

关于单形一个对偶式的商榷与两个新的对偶式

讨论了n维欧氏空间E^n中n维单形不等式的对偶式．利用距离几何理论与解析方法，建立了n维单形两个不等式的对偶式，指出了最近所建立的单形Finsler-Hadwiger不等式的A维对偶式是错误的．     

Implementing the simplex method as a cutting-plane method, with a view to regularization

We show that the simplex method can be interpreted as a cutting-plane method, assuming that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We focus on the special linear programming problem of finding the largest ball that fits into a given polyhedron. In a computational study we demonstrate that ball-fitting problems have such special characteristics which indicate their utility in regularization schemes.     

Two direct methods in linear programming

In this paper, we introduce two direct methods for solving some classes of linear programming problems. The first method produces the extreme vertex or a neighboring vertex with respect to the extreme point. The second method is based on the game theory. Both these methods can be used in the preparation of the starting point for the simplex method. The efficiency of the improved simplex method, whose starting point is constructed by these introduced methods, is compared with the original simplex method and the interior point methods, and illustrated by examples. Also, we investigate the elimination of excessive constraints.     

转让定价视角下的我国企业对外投资战略博弈

我国企业通过对外投资可以拥有在分处国内外的两个实体间开展转让定价的机会,以此来对抗跨国公司在华通过转让定价谋求战略竞争优势,获取公平竞争机会.以单市场双寡头古诺竞争下的转让定价决策模型为基础,构建了我国企业对外投资后在国内和国外两个市场与跨国公司进行战略性转让定价博弈模型,发现无论我国企业与跨国公司相比是否具有成本优势,都应该通过对外投资获取开展战略性转让定价机会,与跨国公司进行公平竞争.     

Ranking fuzzy quantities based on the angle of the reference functions

Ordering fuzzy quantities and their comparison play a key tool in many applied models in the world and in particular decision-making procedures. However a huge number of researches is attracted to this filed but until now there is any unique accepted method to rank the fuzzy quantities. In fact, each proposed method may has some shortcoming. So we are going to present a novel method based on the angle of the reference functions to cover a wide range of fuzzy quantities by over coming the draw backs of some existing methods. In the mentioned firstly, the angle between the left and right membership functions (the reference functions) of every fuzzy set is called Angle of Fuzzy Set (AFS), and then in order to extend ranking of two fuzzy sets the angle of fuzzy sets and α-cuts is used. The method is illustrated by some numerical examples and in particular the results of ranking by the proposed method and some common and existing methods for ranking fuzzy sets is compared to verify the advantage of the new approach. In particular, based on the results of comparison of our method with well known methods which are exist in the literature, we will see that against of most existing ranking approaches, our proposed approach can rank fuzzy numbers that have the same mode and symmetric spreads. In fact, the proposed method in this paper can effectively rank symmetric fuzzy numbers as well as the effective methods which are appeared in the literature. Moreover, unlike of most existing ranking approaches, our proposed approach can rank non-normal fuzzy sets. Finally, we emphasize that the concept of fuzzy ordering is one of key role in establishing the numerical algorithms in operations research such as fuzzy primal simplex algorithms, fuzzy dual simplex algorithms and as well as discussed in the works of Ebrahimnejad and Nasseri and coworkers , , , , ,  and .     

A joint dynamic pricing and advertising model of perishable products

Advertising and dynamic pricing play key roles in maximizing profit of a firm. In this paper a joint dynamic pricing and advertising problem for perishable products is investigated, where the time-varying demand rate is decreasing in sales price and increasing in goodwill. A dynamic optimization model is proposed to maximize total profit by setting a joint pricing and advertising policy under the constraint of a limited advertising capacity. By solving the dynamic optimization problem on the basis of Pontryagin’s maximum principle, the analytical solutions of the optimal joint dynamic pricing and advertising policy are obtained. Additionally, to highlight the advantage of the joint dynamic strategy, the case of the optimal advertising with static pricing policy is considered. Numerical examples are presented to illustrate the validness of the theoretical results, and some managerial implications for the pricing and advertising of the perishable products are provided.     

Partial Pricing Rule Simplex Method with Deficient Basis

A new partial pricing column rule is proposed to the basis-deficiency-allowing simplex method developed by Pan.Computational results obtained with a set of small problems and a set of standard NETLIB problems show its promise of success.     

Backward stochastic differential equations with rank-based data

In this paper, we investigate Markovian backward stochastic differential equations(BSDEs) with the generator and the terminal value that depend on the solutions of stochastic differential equations with rankbased drift coefficients. We study regularity properties of the solutions of this kind of BSDEs and establish their connection with semi-linear backward parabolic partial differential equations in simplex with Neumann boundary condition. As an application, we study the European option pricing problem with capital size based stock prices.     

A Structural Model with Unobserved Default Boundary

In this paper we investigate a numerical algorithm for the pricing of swing options, relying on the so‐called optimal quantization method. The numerical procedure is described in detail and numerous simulations are provided to assert its efficiency. In particular, we carry out a comparison with the Longstaff–Schwartz algorithm.     

基于GARCH-GH模型的上证50ETF期权定价研究

上证50ETF期权是中国推出的首支股票期权.为描述上证50ETF收益率偏态、尖峰、时变波动率等特征,结合GARCH模型和广义双曲(Generalized Hyperbolic,GH)分布两方面的优势,建立GARCH-GH模型为上证50ETF期权定价.在等价鞅测度下,利用蒙特卡罗方法估计上证50ETF欧式认购期权价格.实证表明,相比较Black-Scholes模型和GARCH-Gaussian模型,GARCH-GH模型得到的结果更接近于上证50ETF期权的实际价格,其定价误差最小.     

The most-obtuse-angle row pivot rule for achieving dual feasibility: A computational study

We recently proposed several new pivot rules for achieving dual feasibility in linear programming, which are distinct from existing ones: the objective function value will no longer change necessarily monotonically in their solution process. In this paper, we report our further computational testing with one of them, the most-obtuse-angle rule. A two-phase dual simplex algorithm, in which the rule is used as a row selection rule for Phase-1, has been implemented in FORTRAN 77 modules, and was tested on a set of standard linear programming problems from NETLIB. We show that, if full pricing is applied, our code unambiguously will outperform MINOS 5.3, one of the best implementations of the simplex algorithm at present.     

双曲空间中Veljan-Korchmaros型不等式及应用

本文研究了双曲空间Hn(K)中n维高维单形的几何不等式问题.利用距离几何的理论与方法,获得了涉及n维双曲单形体积,侧面积与棱长的几个几何不等式,这些几何不等式是双曲单形几何不等式的基础.     

Pricing longevity risk with the parametric bootstrap: A maximum entropy approach

In recent years, there has been significant development in the securitization of longevity risk. Various methods for pricing longevity risk have been proposed. In this paper we present an alternative pricing method, which is based on the maximization of the Shannon entropy in physics. Specifically, we propose implementing this pricing method with the parametric bootstrap (Brouhns et al., 2005), which is highly flexible and can be performed under different model assumptions. Through this pricing method we also quantify the impact of cohort effects and parameter uncertainty on prices of mortality-linked securities. Numerical illustrations based on longevity bonds with different maturities are provided.