An implementation of Karmarkar's algorithm for linear programming

65K05: Numerical mathematical programming methods

90C05: Linear programming

Related Items

Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, A Primal-dual affine scaling algorithm with necessary centering as a safeguard, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, An interior-point approach for solving MC$^2$ linear programming problems, An efficient search direction for linear programming problems, Splitting dense columns of constraint matrix in interior point methods for large scale linear programming¹¹The results discussed in the paper have been obtained when the author was staying at LAMSADE, University of Paris Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France$ef:²²A preliminary version of the paper has been presented at the Applied Mathematical Programming and Modelling Symposium APMOD’91 in London, January 14-…, An interior multiobjective linear programming algorithm, Vector processing in simplex and interior methods for linear programming, A unified view of interior point methods for linear programming, Feasibility issues in a primal-dual interior-point method for linear programming, Massive memory buys little speed for complete, in-core sparse Cholesky factorizations on some scalar computers, Splitting dense columns in sparse linear systems, Computational experience with a primal-dual interior point method for linear programming, Optimizing over three-dimensional subspaces in an interior-point method for linear programming, An $O(n^ 3L)$ potential reduction algorithm for linear programming, Fuzzy goal programming: complementary slackness conditions and computational schemes, An adaptation of the dual-affine interior point method for the surface flatness problem, Design of face-centred orthorhombic filter banks, An extended variant of Karmarkar's interior point algorithm, Cubically convergent method for locating a nearby vertex in linear programming, A ``build-down scheme for linear programming, Decomposed block Cholesky factorization in the Karmarkar algorithm. Solving a class of super large LP problems, On the generalized Wolf problem: preprocessing of nonnegative large-scale linear programming problems with group constraints, A relaxed version of Karmarkar's method, New trajectory-following polynomial-time algorithm for linear programming problems, Conical projection algorithms for linear programming, Cutting planes and column generation techniques with the projective algorithm, An interior point algorithm for semi-infinite linear programming, On finding a vertex solution using interior point methods, An optimal-basis identification technique for interior-point linear programming algorithms, An $O(\sqrt n L)$ iteration potential reduction algorithm for linear complementarity problems, Interior point algorithms for linear programming with inequality constraints, Global convergence of the affine scaling methods for degenerate linear programming problems, Comparative analysis of affine scaling algorithms based on simplifying assumptions, A survey of search directions in interior point methods for linear programming, On the complexity of following the central path of linear programs by linear extrapolation. II, Computational results of an interior point algorithm for large scale linear programming, Solving combinatorial optimization problems using Karmarkar's algorithm, On affine scaling and semi-infinite programming, Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals, On combined phase 1-phase 2 projective methods for linear programming, A weighted least squares study of robustness in interior point linear programming, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Computing Karmarkar's projections in stochastic linear programming, A parallel interior point algorithm for linear programming on a network of transputers, Degeneracy in interior point methods for linear programming: A survey, A simplified global convergence proof of the affine scaling algorithm, Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems, On the expected optimal value of random assignment problems: Experimental results and open questions, K-K-T multiplier estimates and objective function lower bounds from projective SUMT, Solving symmetric indefinite systems in an interior-point method for linear programming, On the big ${\mathcal M}$ in the affine scaling algorithm, A primal-dual affine-scaling potential-reduction algorithm for linear programming, On the number of iterations of Karmarkar's algorithm for linear programming, Interior dual proximal point algorithm for linear programs, Interior-point algorithms for semi-infinite programming, A combined homotopy interior point method for general nonlinear programming problems, A QMR-based interior-point algorithm for solving linear programs, A combined homotopy interior point method for convex nonlinear programming, Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case, Trust region affine scaling algorithms for linearly constrained convex and concave programs, Piecewise linear programming via interior points, A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Symmetric indefinite systems for interior point methods, Efficient solution of two-stage stochastic linear programs using interior point methods, Affine-scaling for linear programs with free variables, Computing Karmarkar's projections quickly by using matrix factorization, Limit analysis with the dual affine scaling algorithm, Presolving in linear programming, A simple proof of a primal affine scaling method, An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption, The primal power affine scaling method, An interior point method for general large-scale quadratic programming problems, An $O(\sqrt {n} L)$ iteration bound primal-dual cone affine scaling algorithm for linear programming, A primal-dual potential reduction method for problems involving matrix inequalities, Superlinear convergence of the affine scaling algorithm, A weighted-gradient approach to multi-objective linear programming problems using the analytic hierarchy process, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, An analytical approach to the inference of summary data of additive type, Dual versus primal-dual interior-point methods for linear and conic programming, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods, Loss and retention of accuracy in affine scaling methods, Interior-point methods for linear programming: a review, Generating interior search directions for multiobjective linear programming using approximate gradients and efficient anchoring points, Numerical experiments with the symmetric affine scaling algorithm on degenerate linear programming problema, Implementing cholesky factorization for interior point methods of linear programming

Uses Software

Cites Work