Some fundamental issues of basic line search algorithm for linear programming problems

In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration.     

A theoretical comparison between the simplex method and the basic line search algorithm

A theoretical comparison between the simplex method (SM) and the basic line search method (BLSA) is presented. The explicit formulae for the upper and lower bounds in the BLSA are provided using SM. Further, it is shown that both methods are operationally equivalent.     

关于单纯形表迭代法的一种提高计算精确度的方法

在计算机上进行分数运算时，会造成舍入误差，因此，用单纯形表迭代法解线性规划问题时，会因误差累积而改变问题解的性质。本文针对线性规划的单纯形表迭代法给出了一种提高计算精确度的方法     

Primal-Dual Simplex Method for Multiobjective Linear Programming

We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research. The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121. We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.     

最速下降规则不失为一可用规则

本从统计意义上平均迭代次数的观点出发，指出求解线性规划的最速下降规则是可取的，好用的。     

线性规划的单纯形法及其发展

本文给出了一种新的原对偶单纯形法,并通过它分析了隐藏在经典单纯形法中的对偶信息．我们重新评价经典单纯形法并详细讨论了它与现代单纯形法之间的联系．两个修改版本一并给出．新算法具有计算量小和实施简单等特点,计算效果也不错．初步数值实验表明现代单纯形法比经典方法具有明显的优越性．     

线性双层规划的改进PCP全局求解算法

本文采用K-T条件将线性双层规划模型改写为单层规划后,将参数引入上层目标函数,构造了含参线性互补问题(PLCP)并给出它的一些性质。进而通过改进Lemke算法的进基规则,在保持互补旋转算法原有优势的基础上,引入充分小正数ε,设计了改进参数互补旋转(PCP)算法求取全局最优解,最后通过两个算例说明了其有效性。     

Pivot rules for linear programming: A survey on recent theoretical developments

The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed.In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2115.     

A Dual Projective Pivot Algorithm for Linear Programming

Recently, a linear programming problem solver, called dual projective simplex method, was proposed (Pan, Computers and Mathematics with Applications, vol. 35, no. 6, pp. 119–135, 1998). This algorithm requires a crash procedure to provide an initial (normal or deficient) basis. In this paper, it is recast in a more compact form so that it can get itself started from scratch with any dual (basic or nonbasic) feasible solution. A new dual Phase-1 approach for producing such a solution is proposed. Reported are also computational results obtained with a set of standard NETLIB problems.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

线性规划联合算法的理论与应用

本在[1]的基础上．较系统的叙述了线性规划联合算法的步骤、相关理论及其应用，指出该算法具有避免人工变量、减少迭代次数、使用灵活、应用方便等特点。     

无比值检验的亏基原始Ⅰ阶段算法

首次将亏基和无比值检验列主元规则相结合,执行亏基对偶单纯形算法得到一个原始可行基,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.数值试验表明,亏基和无比值主元规则的结合,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.     

Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

Abstract

Several variations of index selection rules for simplex-type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the flexibility of these anti-cycling pivot rules is evaluated using public benchmark LP test sets. Our results also provide numerical evidence that the MBU-simplex algorithm is a viable alternative to the traditional simplex algorithm.     

Solving Bilevel Linear Programs Using Multiple Objective Linear Programming

We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound algorithm when the number of leader variables is small.     

线性规划问题的规范型算法

提出了线性规划问题的两种规范标准形式；证明了任意一个线性规划问题都可化为这两种形式之一；给出了不需引入人工变量的线性规划问题的求解算法。     

关于使用最大改进规则的对偶单纯形算法

本举例证明了[3]的定理10-1是错误的。     

关于使用最大改进规则的单纯形算法

[5]建立了定理5—3、5—4、5—5，并据此证明了采用该的最大改进规则的单纯形算法是多项式算法。本举例证明了[5]中的定理5—3、5—4、5—5是错误的。     

线性规划两阶段法的改进算法

将单纯形法与对偶单纯形法及其思想结合运用,对两阶段法引进人工变量的方式进行了改进,探索出一种最多引入一个人工变量,即可求得线性规划初始可行基的新算法,能有效地节约计算机的存储量和计算量。     

Three nearly scaling-invariant versions of an exterior point algorithm for linear programming

In this paper, we describe three versions of a primal exterior point Simplex type algorithm for solving linear programming problems. Also, these algorithms are not affected mainly by scaling techniques. We compare their practical effectiveness versus the revised primal Simplex algorithm (our implementation) and the MATLAB’s implementations of Simplex and Interior Point Method. A computational study on randomly generated sparse linear programs is presented to establish the practical value of the proposed versions. The results are very encouraging and verify the superiority of the exterior point versions over the other algorithms either using scaling techniques or not.     

线性规划全方位变化的灵敏度分析

本文对变量目标函数系数、变量约束系数向量以及约束右端项向量同时变化进行灵敏度分析。不仅对变化后可能出现的各种情况进行分析处理,尤其在对偶可行性和可行性都不满足时,利用联合算法进行处理,并通过算例加以说明。