An implementation of Karmarkar's algorithm for linear programming

DOI10.1007/BF01587095zbMath0682.90061OpenAlexW1981053712WikidataQ29032067 ScholiaQ29032067MaRDI QIDQ1824551

Mauricio G. C. Resende, Geraldo Veiga, Ilan Adler, Narendra K. Karmarkar

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01587095

zbMATH Keywords

interior point methods Implementation Karmarkar's algorithm power series dual affine scaling variants

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items

Exploiting low-rank structure in semidefinite programming by approximate operator splitting, An interior-point approach for solving MC$^2$ linear programming problems, An efficient search direction for linear programming problems, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, Interior dual proximal point algorithm for linear programs, Superlinear convergence of the affine scaling algorithm, A weighted-gradient approach to multi-objective linear programming problems using the analytic hierarchy process, Interior-point algorithms for semi-infinite programming, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, Interior point method for long-term generation scheduling of large-scale hydrothermal systems, A new procedure for solving integer linear programming problems, A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming, A combined homotopy interior point method for general nonlinear programming problems, Fuzzy goal programming: complementary slackness conditions and computational schemes, Limit analysis with the dual affine scaling algorithm, 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, A QMR-based interior-point algorithm for solving linear programs, A relaxed version of Karmarkar's method, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, A combined homotopy interior point method for convex nonlinear programming, New trajectory-following polynomial-time algorithm for linear programming problems, Presolving in linear programming, Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case, Conical projection algorithms for 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, Cutting planes and column generation techniques with the projective algorithm, An interior point algorithm for semi-infinite linear programming, An adaptation of the dual-affine interior point method for the surface flatness problem, Design of face-centred orthorhombic filter banks, Trust region affine scaling algorithms for linearly constrained convex and concave programs, A primal-dual potential reduction method for problems involving matrix inequalities, An extended variant of Karmarkar's interior point algorithm, Midconvexity for finite sets, Hopfield neural networks in large-scale linear optimization problems, Cubically convergent method for locating a nearby vertex in linear programming, A ``build-down scheme for linear programming, Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis, Decomposed block Cholesky factorization in the Karmarkar algorithm. Solving a class of super large LP problems, Dual interior point algorithms, A Primal-dual affine scaling algorithm with necessary centering as a safeguard, On the generalized Wolf problem: preprocessing of nonnegative large-scale linear programming problems with group constraints, 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, An analytical approach to the inference of summary data of additive type, 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, A partial first-order affine-scaling method, Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods, Dual versus primal-dual interior-point methods for linear and conic programming, Solving combinatorial optimization problems using Karmarkar's algorithm, On affine scaling and semi-infinite programming, Bilevel time minimizing transportation problem, The $\ell_1$ solution of linear inequalities, An interior multiobjective linear programming algorithm, 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, 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 new class of preconditioners for large-scale linear systems from interior point methods for linear programming, 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-…, Loss and retention of accuracy in affine scaling methods, Symmetric indefinite systems for interior point methods, Efficient solution of two-stage stochastic linear programs using interior point methods, A weighted least squares study of robustness in interior point linear programming, Affine-scaling for linear programs with free variables, Vector processing in simplex and interior methods for linear programming, Computing Karmarkar's projections quickly by using matrix factorization, Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning, Computing Karmarkar's projections in stochastic linear programming, SICOpt: Solution approach for nonlinear integer stochastic programming problems, An affine-scaling pivot algorithm for linear programming, Piecewise linear programming via interior points, A parallel interior point algorithm for linear programming on a network of transputers, A unified view of interior point methods for linear programming, Feasibility issues in a primal-dual interior-point method for linear programming, 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, Massive memory buys little speed for complete, in-core sparse Cholesky factorizations on some scalar computers, Splitting dense columns in sparse linear systems, 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, 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, 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-point methods for linear programming: a review

Uses Software

Cites Work