线性规划最优解集的表现

文献［１］讨论了有无穷多最优解的线性规划问题，并利用最优单纯形表格的检验数给出线性规划有无穷多最优解的判别法，本文利用最优基可行解的凸组合及最优极向的非负线性组合给出线性规划最优解集的表现，从而把线性规划最优解集的几何特征阐释清楚．     

线性规划无穷多最优解的讨论

利用线性规划单纯形表对线性规划原问题存在无穷多最优解和对偶问题存在无穷多最优解的情况进行了讨论,并分析了对偶问题存在无穷多最优解情况下的影子价格的方向性。最后以实例说明了各种情况。对初学者加深理解及决策者决策参考有一定帮助     

线性规划的对偶基线算法

In this paper,we studied the dual form of the basic line algorthm for linear programs.It can be easily implemented in tableau that similar to the primal/dual simplex method.Different from primal simplex method or dual simplex method,the dual basic line algorithm can keep primal feasibility and dual feasibility at the same time in a tableau,which makes it more efficient than the former ones.Principles and convergence of dual basic line algorthm were discussed.Some examplex and computational experience were given to illustrate the efficiency of our method.     

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.     

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.     

互补基解性质的应用研究

对线性规划互补基解性质进行了研究,得到了由线性规划问题最优基对应的单纯形表直接获得对偶线性规划问题最优基对应的单纯形表的一个有效方法,给出了应用实例.     

Adding activities to the dual instead of cuts to the primal problem

When solving a problem by appending cuts the dimension of the corresponding simplex tableau and the basic inverse oscillates, which makes it difficult to implement a cutting plane algorithm based on a standard LP code. Moreover, it is complicated to express a cut in the original variables. In this paper we show that by formulating the dual to the problem and adding activities, these adverse effects can be circumvented. It is shown that the set of activities which can be added is the same as the set of cuts which can be appended and that it is easy to exhibit an activity in the original primal variables. As a consequence of this a new formulation of a cut in the original primal variables is given.     

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants

Lift-and-project cuts for mixed integer programs (MIP), derived from a disjunction on an integer-constrained fractional variable, were originally (Balas et al. in Math program 58:295–324, 1993) generated by solving a higher-dimensional cut generating linear program (CGLP). Later, a correspondence established (Balas and Perregaard in Math program 94:221–245, 2003) between basic feasible solutions to the CGLP and basic (not necessarily feasible) solutions to the linear programming relaxation LP of the MIP, has made it possible to mimic the process of solving the CGLP through certain pivots in the LP tableau guaranteed to improve the CGLP objective function. This has also led to an alternative interpretation of lift-and-project (L&P) cuts, as mixed integer Gomory cuts from various (in general neither primal nor dual feasible) LP tableaus, guaranteed to be stronger than the one from the optimal tableau. In this paper we analyze the relationship between a pivot in the LP tableau and the (unique) corresponding block pivot (sequence of pivots) in the CGLP tableau. Namely, we show how a single pivot in the LP defines a sequence (potentially as long as the number of variables) of pivots in the CGLP, and we identify this sequence. Also, we give a new procedure for finding in a given LP tableau a pivot that produces the maximum improvement in the CGLP objective (which measures the amount of violation of the resulting cut by the current LP solution). Further, we introduce a procedure called iterative disjunctive modularization. In the standard procedure, pivoting in the LP tableau optimizes the multipliers with which the inequalities on each side of the disjunction are weighted in the resulting cut. Once this solution has been obtained, a strengthening step is applied that uses the integrality constraints (if any) on the variables on each side of the disjunction to improve the cut coefficients by choosing optimal values for the elements of a certain monoid. Iterative disjunctive modularization is a procedure for approximating the simultaneous optimization of both the continuous multipliers and the integer elements of the monoid. All this is discussed in the context of a CGLP with a more general normalization constraint than the standard one used in (Balas and Perregaard in Math program 94:221–245, 2003), and the expressions that describe the above mentioned correspondence are accordingly generalized. Finally, we summarize our extensive computational experience with the above procedures.     

On Analyses of the Solution to a Linear Programming Problem

Many complex problem situations in various contexts have been represented in recent years by the linear programming model. The simplex method can then be used to give the optimal values of the variables corresponding to a given set of values of the parameters. However, in many situations it is useful to have the solution to many other related problems which differ from the original problem only in the values of some of the parameters. This paper presents procedures by which the solutions to the changed problems can be derived from the simplex solution tableau corresponding to the original problem. The method will be illustrated by means of an example problem, and it will be shown how quantitative information obtained from such analyses can aid management in decision making.     

A bound for the number of different basic solutions generated by the simplex method

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems (LP) having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the problem is primal nondegenerate, it becomes a bound for the number of iterations. The result includes strong polynomiality for Markov Decision Problem by Ye (http://www.stanford.edu/~yyye/simplexmdp1.pdf, 2010) and utilize its analysis. We also apply our result to an LP whose constraint matrix is totally unimodular and a constant vector b of constraints is integral.     

Persistency in quadratic 0–1 optimization

This paper is concerned with persistency properties which allow the evaluation of some variables at all maximizing points of a quadratic pseudo-Boolean function. Hammer, Hansen and Simeone (1984) have proposed to determine these variables using a procedure described by Balinski for computing a strongly complementary pair of optimal primal and dual solutions for arbitrary linear programs. We propose a linear time algorithm for determining these variables from a best roof off, i.e. from a lowest upper linear bound off.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

Optimal matrix-segmentation by rectangles

We study the problem of decomposing a nonnegative matrix into a nonnegative combination of 0-1-matrices whose ones form a rectangle such that the sum of the coefficients is minimal. We present for the case of two rows an easy algorithm that provides an optimal solution which is integral if the given matrix is integral. An additional integrality constraint makes the problem more difficult if the matrix has more than two rows. An algorithm that is based on the revised simplex method and uses only very few Gomory cuts yields exact integral solutions for integral matrices of reasonable size in a short time. For matrices of large dimension we propose a special greedy algorithm that provides sufficiently good results in numerical experiments.     

Complementarity and nondegeneracy in semidefinite programming

Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutionsX andZ. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest probability distributions for the ranks ofX andZ which are consistent with the nondegeneracy conditions. Supported in part by the U.S. National Science Foundation grant CCR-9625955. Supported in part by U.S. National Science Foundation grant CCR-9501941 and the U.S. Office of Naval Research grant N00014-96-1-0704. Supported in part by U.S. National Science Foundation grant CCR-9401119.     

An overview on the simplex algorithm

In this paper, the simplex algorithm and its variants are investigated. First, we define a new concept called formal tableau, which leads to derive easily the dual solution from the latest primal table; without any distinction between the original variables and the slack ones. Second, we propose a new method for initializing the simplex algorithm. Unlike the two-phase and the big-M methods, our technique does not involve artificial variables. The computational results reveal that this new method is very favorable especially when the number of artificial variables is significant. Finally, this method will be combined with the notion of formal tableau leading naturally to a second new approach.     

On the strength of Gomory mixed-integer cuts as group cuts

Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from other facets of master cyclic group polyhedra (group cuts) do not seem to be as useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.     

On the optimal value function for certain linear programs with unbounded optimal solution sets

Often, the coefficients of a linear programming problem represent estimates of true values of data or are subject to systematic variations. In such cases, it is useful to perturb the original data and to either compute, estimate, or otherwise describe the values of the functionf which gives the optimal value of the linear program for each perturbation. If the right-hand derivative off at a chosen point exists and is calculated, then the values off in a neighborhood of that point can be estimated. However, if the optimal solution set of either the primal problem or the dual problem is unbounded, then this derivative may not exist. In this note, we show that, frequently, even if the primal problem or the dual problem has an unbounded optimal solution set, the nature of the values off at points near a given point can be investigated. To illustrate the potential utility of our results, their application to two types of problems is also explained.This research was supported, in part, by the Center for Econometrics and Decision Sciences, University of Florida, Gainesville, Florida.The author would like to thank two anonymous reviewers for their most useful comments on earlier versions of this paper.     

A convergent criss-cross method

Our paper presents a new Criss-Cross method for solving linear programming problems. Starting from a neither primal nor dual feasible solution, we reach an optimal solution in finite number of steps if it exists. If there is no optimal solution, then we show that there is not primal feasible or dual feasible solution, We prove the finiteness of this procedure. Our procedure is not the same as the primal or dual simplex method if we have a primal or dual feasible solution, so we have constructed a quite new procedure for solving linear programming problems.     

On the existence of a short pivoting sequence for a linear program

We show that given a feasible primal–dual pair of linear programs in canonical form, there exists a sequence of pivots, whose length is bounded by the minimum dimension of the constraint matrix, leading from the origin to the optimum. The sequence of pivots give a sequence of square and nonsingular submatrices of the constraint matrix. Solving two linear equations involving such a submatrix give primal–dual optimal solutions to the corresponding linear program in canonical form.