Post-optimality analysis of the optimal solution of a degenerate linear program using a pivoting algorithm

This paper gives a theory and method that specifies how the optimal solution of a linear program changes when the right-hand side of the original problem is changed and when the original optimal solution exhibits primal degeneracy. The method determines an optimal change vector as the resource availabilities change, and it calculates a range for which this vector is valid. Resource availabilities are allowed to change simultaneously in any arbitrary proportion, and the concept of an “efficient resource bundle” is introduced. The geometry of the optimal change vector is presented from which the desired results are derived. The connection between the geometrical results and their algebraic calculation in tableau-form is shown. Our method uses a pivoting algorithm and the relationship with post-optimality results from interior-point methods will be established.     

The positive edge criterion within COIN-OR׳s CLP

This paper presents the first direct implementation of the positive edge criterion using COIN-OR׳s CLP, where it has been combined with the Devex pivot rule. Positive edge is designed to take advantage of degeneracy in linear programming. The original implementation, while yielding strong computational results, suffers from significant overhead caused by CPLEX not allowing modification of its standard pivot rules. We test the method over the same set of highly degenerate problems used by the original authors of positive edge. To test its robustness, we solve a set of linear problems from Mittelmann׳s library which contains instances with a wide range of degeneracy levels. These computational results show that below a degeneracy level of 25%, the positive edge criterion is on average neutral while above this threshold, it reaches an average run time speedup of 2.3, with a maximum at 4.2 on an instance with a 75% degeneracy level.     

The positive edge pricing rule for the dual simplex

In this paper, we develop the two-dimensional positive edge criterion for the dual simplex. This work extends a similar pricing rule implemented by Towhidi et al. (2014) [24] to reduce the negative effects of degeneracy in the primal simplex. In the dual simplex, degeneracy occurs when nonbasic variables have a zero reduced cost, and it may lead to pivots that do not improve the objective value. We analyze dual degeneracy to characterize a particular set of dual compatible variables such that if any of them is selected to leave the basis the pivot will be nondegenerate. The dual positive edge rule can be used to modify any pivot selection rule so as to prioritize compatible variables. The expected effect is to reduce the number of pivots during the solution of degenerate problems with the dual simplex. For the experiments, we implement the positive edge rule within the dual simplex of the COIN-OR LP solver, and combine it with both the dual Dantzig and the dual steepest edge criteria. We test our implementation on 62 instances from four well-known benchmarks for linear programming. The results show that the dual positive edge rule significantly improves on the classical pricing rules.     

求解整数线性规划问题的定界阻止算法的改进*

在现有求解整数线性规划问题的定界阻止算法的基础上提出了一种改进。该算法通过目标函数超平面截线性规划松弛问题的有效约束锥而形成一个单纯形;然后,引入一串平行片来切割该单纯形产生更低维的凸多面体;最后,在片上的这些凸多面体上执行阻止搜寻程序。由于单纯形和片上凸多面体的极顶点可以直接通过公式计算,且变量在片上凸多面体上的取值区间更窄,改进的定界阻止算法既方便又高效,这得到了一些经典算例和随机产生的算例的验证。     

Systematic construction of examples for cycling in the simplex method

We present systematic procedures to construct examples of linear programs that cycle when the simplex method is applied. Cycling examples are constructed for diverse variants of pivot selection strategies: most negative reduced-cost and steepest-edge rule for the entering variable, and smallest ratio rule for the leaving variable (where ties are broken according to the least-index or the largest coefficient criterion, respectively). The results are of theoretical interest since only a limited number of cycling examples have been presented in the literature up to date. Constructed cycling examples may also serve as test problems to evaluate the practical performance of anticycling procedures or new variants of simplex type methods.     

Performance evaluation of a family of criss–cross algorithms for linear programming

In this article we evaluate a family of criss–cross algorithms for linear programming problems, comparing the results obtained by these algorithms over a set of test problems with those obtained by the simplex algorithms implemented in the XPRESS commercial package. We describe the known criss–cross variants existing in the literature and introduce new versions obtained with a slight modification based on the original criss–cross algorithm. Moreover, we consider some computational details of our implementation and describe the set of test problems used.     

On a decision procedure for quantified linear programs

Quantified linear programming is the problem of checking whether a polyhedron specified by a linear system of inequalities is non-empty, with respect to a specified quantifier string. Quantified linear programming subsumes traditional linear programming, since in traditional linear programming, all the program variables are existentially quantified (implicitly), whereas, in quantified linear programming, a program variable may be existentially quantified or universally quantified over a continuous range. In this paper, the term linear programming is used to describe the problem of checking whether a system of linear inequalities has a feasible solution. On account of the alternation of quantifiers in the specification of a quantified linear program (QLP), this problem is non-trivial. QLPs represent a class of declarative constraint logic programs (CLPs) that are extremely rich in their expressive power. The complexity of quantified linear programming for arbitrary constraint matrices is unknown. In this paper, we show that polynomial time decision procedures exist for the case in which the constraint matrix satisfies certain structural properties. We also provide a taxonomy of quantified linear programs, based on the structure of the quantifier string and discuss the computational complexities of the constituent classes. This research has been supported in part by the Air Force Office of Scientific Research under contract FA9550-06-1-0050.     

A new linearization method for generalized linear multiplicative programming

This paper presents a deterministic global optimization algorithm for solving generalized linear multiplicative programming (GLMP). In this algorithm, a new linearization method is proposed, which applies more information of the function of (GLMP) than some other methods. By using this new linearization technique, the initial nonconvex problem is reduced to a sequence of linear programming problems. A deleting rule is presented to improve the convergence speed of this algorithm. The convergence of this algorithm is established, and some experiments are reported to show the feasibility and efficiency of this algorithm.     

Lexicographic perturbation for multiparametric linear programming with applications to control

Optimal control problems for constrained linear systems with a linear cost can be posed as multiparametric linear programs (mpLPs) with a parameter in the cost, or equivalently the right-hand side of the constraints, and solved explicitly offline. Degeneracy occurs when the control input, or optimiser, is non-unique, which can cause chattering of the control input and overlap of the polyhedral regions of the explicit solution. This paper introduces a new and efficient approach to the computation of the solution to a degenerate mpLP with the parameter in the cost. Rather than solve the degenerate problem directly, we solve a lexicographically (symbolically) perturbed version of it that is guaranteed to be non-degenerate. We show that every optimal solution of the perturbed problem is an optimal solution to the original and that the perturbed solution is continuous, unique and defined over a set of non-overlapping polyhedral regions. Furthermore, we introduce a new method for computing the optimal solution in an adjacent region, which is very efficient in all cases and reduces to a single simplex pivot for non-degenerate regions. The proposed algorithm is particularly suited for the calculation of the explicit solution to a class of constrained optimal control problems, since it ensures that the control input is everywhere continuous and unique, thereby removing the danger of chattering in problems with linear costs. The algorithm is compared through example to existing proposals and a significant complexity improvement is demonstrated.     

基于单纯形方法的建筑钢筋配料算法

文章以单纯形方法为基础求解建筑钢筋配料问题。运用单纯形方法的一个问题是解为小数值，作者用一个简单的方法进行取整。运用单纯形方法的另一个更重要的问题是决策变量数过大。为在有限的内存空间和时间内运用单纯形法，文中提出了五个用于减少决策变量数（备选方案数）的方法，并综合运用了这五个方法，既将空间和时间复杂度减少到合适的程度，又保证了配料结果经济有效。     

A distributed simplex algorithm for degenerate linear programs and multi-agent assignments

In this paper we propose a novel distributed algorithm to solve degenerate linear programs on asynchronous peer-to-peer networks with distributed information structures. We propose a distributed version of the well-known simplex algorithm for general degenerate linear programs. A network of agents, running our algorithm, will agree on a common optimal solution, even if the optimal solution is not unique, or will determine infeasibility or unboundedness of the problem. We establish how the multi-agent assignment problem can be efficiently solved by means of our distributed simplex algorithm. We provide simulations supporting the conjecture that the completion time scales linearly with the diameter of the communication graph.     

A linear programming algorithm for invariant polyhedral sets of discrete-time linear systems

In this paper we formulate necessary and sufficient conditions for an arbitrary polyhedral set to be a positively invariant set of a linear discrete-time system. Polyhedral cones and linear subspaces are included in the analysis. A linear programming algorithm is presented that enables practical application of the results stated in this paper.     

A polynomial newton method for linear programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n ² m ² L) operations that there is no solution or, else, computes an exact solution in at mostO(n ³ m ² L) operations.The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n ³ m ² L) operations.     

A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

A new approach on designing l1 optimal regulator with minimum order for SISO linear systems

For a SISO linear discrete-time system with a specified input signal, a novel method to realize optimal l1 regulation control is presented. Utilizing the technique of converting a polynomial equation to its corresponding matrix equation, a linear programming problem to get an optimal l1 norm of the system output error map is developed which includes the first term and the last term of the map sequence in the objective function and the right vector of its constraint matrix equation, respectively. The adjustability for the width of the constraint matrix makes the trade-off between the order of the optimal regulator and the value of the minimum objective norm become possible, especially for achieving the optimal regulator with minimum order. By norm scaling rules for the constraint matrix equation, the optimal solution can be scaled directly or be obtained by solving a linear programming problem with l\ norm objective.     

A new approach on designing l_1 optimal regulator with minimum order for SISO linear systems

For a SISO linear discrete-time system with a specified input signal, a novel method to realize optimal l1 regulation control is presented. Utilizing the technique of converting a polynomial equation to its corresponding matrix equation, a linear programming problem to get an optimal l1 norm of the system output error map is developed which includes the first term and the last term of the map sequence in the objective function and the right vector of its constraint matrix equation, respectively. The adjustability for the width of the constraint matrix makes the trade-off between the order of the optimal regulator and the value of the minimum objective norm become possible, especially for achieving the optimal regulator with minimum order. By norm scaling rules for the constraint matrix equation, the optimal solution can be scaled directly or be obtained by solving a linear programming problem with l\ norm objective.     

单纯形法求解与Excel规划求解

利用单纯形法求解线性规划问题在产品品种问题、合理配料问题、开料问题等问题中有着极其广泛的应用,但整个计算过程非常繁杂,而且容易计算错误。对Excel规划求解的研究发现,利用Excel中的规划求解工具可以实现单纯形法求解线性规划的问题,大大提高了求解的速度和准确性。     

An experimental comparison of the new goal programming and the linear programming approaches in the two-group discriminant problems

The aim of this article is to consider a new linear programming and two goal programming models for two-group classification problems. When these approaches are applied to the data of real life or of simulation, our proposed new models perform well both in separating the groups and the group–membership predictions of new objects. In discriminant analysis some linear programming models determine the attribute weights and the cut-off value in two steps, but our models determine simultaneously all of these values in one step. Moreover, the results of simulation experiments show that our proposed models outperform significantly than existing linear programming and statistical approaches in attaining higher average hit-ratios.     

A projective method for linear programming with box-type constraints

A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.This work was done while the author was visiting New York University.     

A dynamic version for the Network Simplex Algorithm

In most practical environments, scheduling is an ongoing reactive process where the presence of real time information continually forces reconsideration and revision of pre-established schedules. The objectives of the research reported in this paper are to respond to changes in the problem, to solve the new problem faster and to use some parts of the previous solution for the next problem. In this paper, based on Network Simplex Algorithm, a dynamic algorithm, which is called Dynamic Network Simplex Algorithm (DNSA), is presented. Although the traditional network simplex algorithm is at least one hundred times faster than traditional simplex algorithm for Linear Programs (through specialization), for dynamic scheduling with large scale problems it still takes time to make a new graph model and to solve it. The overall approach of DNSA is to update the graph model dynamically and repair its spanning tree by some strategies when any changes happen. To test the algorithm and its performance, an application of this algorithm to Dynamic Scheduling of Automated Guided Vehicles in the container terminal is used. The dynamic problem arises when new jobs are arrived, the fulfilled jobs are removed and the links or junctions are blocked (which results in distances between points being changed). The results show considerable improvements, in terms of reducing the number of iterations and CPU time, to solve randomly generated problems.