An implementation of Karmarkar's algorithm for linear programming

This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.     

New trajectory-following polynomial-time algorithm for linear programming problems

A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., deepstep) version of the algorithm.The author is indebted to J. Bisschop, P. C. J. M. Geven, J. H. Van Lint, J. Ponstein, and J. P. Vial for their remarks on an earlier version of this paper.     

Finding a strict feasible solution of a linear semidefinite program

This study deals with the performance of projective interior point methods for linear semidefinite program. We propose a modification in the initialization phases of the method in order to reduce the computation time.This purpose is confirmed by numerical experiments showing the efficiency which are presented in the last section of the paper.     

On solution-containing ellipsoids in linear programming

Ellipsoids that contain all optimal dual slack solutions and those that contain all optimal primal solutions and that are independent of the algorithm used are derived. Based upon these ellipsoids, two criteria each for detecting optimal basic and nonbasic variables prior to optimality in interior-point methods are obtained. Using these results, we then derive a sufficient condition for a linear program to be feasible.This research was supported in part by NSF Grant DMS-85-12277, DMS-91-06195, CDR-84-21402 and ONR Contract N00014-87-K-0214.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

Global convergence of the affine scaling methods for degenerate linear programming problems

In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.This paper was presented at the International Symposium Interior Point Methods for Linear Programming: Theory and Practice, held on January 18–19, 1990, at the Europa Hotel, Scheveningen, the Netherlands.     

Polynomial affine algorithms for linear programming

The method of steepest descent with scaling (affine scaling) applied to the potential functionq logcx — _i=1 ⁿ logx _i solves the linear programming problem in polynomial time forq n. Ifq = n, then the algorithm terminates in no more than O(n ² L) iterations; if q n + withq = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n ⁴ L) and O(n ^3.5 L) arithmetic computions.     

Structural properties and recognition of restricted and strongly unimodular matrices

A (0, ±1) matrix A is restricted unimodular if every matrix obtained from A by setting to zero any subset of its entries is totally unimodular. Restricted unimodular matrices are also known as matrices without odd cycles. They have been studied by Commoner and recently Yannakakis has given a polynomial algorithm to recognize when a matrix belongs to this class. A matrix A is strongly unimodular if any matrix obtained from A by setting at most one of its entries to zero is totally unimodular. Crama et al. have shown that (0,1) matrix A is strongly unimodular if and only if any basis of (A, 1) is triangular, whereI is an identity matrix of suitable dimensions. In this paper we give a very simple algorithm to test whether a matrix is restricted unimodular and we show that all strongly unimodular matrices can be obtained by composing restricted unimodular matrices with a simple operation. Partially supported by a New York University Research Challenge Fund Grant.     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.     

An active-set strategy in an interior point method for linear programming

We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks—termed active constraints—will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( L) iterations with the same polynomial bound as in the full constraints case, wheren is the number of variables andL is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration may be considerably reduced by the proposed strategy.This research was partially done in June 1990 while the author was visiting the Department of Mathematics, University of Pisa.     

Neighborhood-following algorithms for linear programming

In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.     

A primal—dual affine-scaling potential-reduction algorithm for linear programming

We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

Intelligent gradient search in linear programming

The simplex algorithm is still the best known and most frequently used way to solve LP problems. Khachian has suggested a method to solve these problems in polynomial time. The average behaviour of his method, however, is still inferior to the modern simplex based LP codes. A new gradient based approach which also has polynomial worst-case behaviour has been suggested by Karmarkar. This method was modified, programmed and compared with other available LP codes. It is shown that the numerical efficiency of Karmarkar's method compares favourably with other LP codes, particularly for problems with high numbers of variables and few constraints.     

Presolving in linear programming

Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and Tomlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible.In this paper we present a comprehensive survey of presolve methods. Moreover, we discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve.Computational results on the NETLIB problems (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.This author was supported by a Danish SNF Research studentship.     

Deriving an unconstrained convex program for linear programming

Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions.     

Weak linear bilevel programming problems: existence of solutions via a penalty method

We are concerned with a class of weak linear bilevel programs with nonunique lower level solutions. For such problems, we give via an exact penalty method an existence theorem of solutions. Then, we propose an algorithm.     

Note: continuous-time linear programming problems revisited

This note is aimed to correct the strong duality theorem of previous paper regarding the continuous-time linear programming problems. The argument presented in the previous paper can only be used to prove the case of piecewise continuous functions in which the discontinuities are the left-continuities.     

Multiple centrality corrections in a primal-dual method for linear programming

A modification of the (infeasible) primal-dual interior point method is developed. The method uses multiple corrections to improve the centrality of the current iterate. The maximum number of corrections the algorithm is encouraged to make depends on the ratio of the efforts to solve and to factorize the KKT systems. For any LP problem, this ratio is determined right after preprocessing the KKT system and prior to the optimization process. The harder the factorization, the more advantageous the higher-order corrections might prove to be.The computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real-life LP models arising from applications. The use of multiple centrality corrections gives on the average a 25% to 40% reduction in the number of iterations compared with the widely used second-order predictor-corrector method. This translates into 20% to 30% savings in CPU time.Supported by the Fonds National de la Recherche Scientifique Suisse, Grant #12-34002.92.     

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

This paper presents a “standard form” variant of Karmarkar's algorithm for linear programming. The tecniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.     

On fuzzy linear programming

Fuzzy multi-objective and fuzzy Goal Programming are discussed in connection with several membership functions which are used to transform the original problem into three equivalent linear programming problems. Existence and uniqueness theorems are given. Fuzzy duality is presented, and an extension of the initial fuzzy problem arises immediately from it.