Solving combinatorial optimization problems using Karmarkar's algorithm
From MaRDI portal
Publication:1196181
DOI10.1007/BF01580902zbMath0763.90074OpenAlexW2014944169WikidataQ92159393 ScholiaQ92159393MaRDI QIDQ1196181
John E. Mitchell, Michael J. Todd
Publication date: 17 December 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01580902
Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming, A second-order cone cutting surface method: Complexity and application, A Newton's method for perturbed second-order cone programs, Solving nonlinear multicommodity flow problems by the analytic center cutting plane method, Using the primal-dual interior point algorithm within the branch-price-and-cut method, A logarithmic barrier cutting plane method for convex programming, An analytic center cutting plane method for pseudomonotone variational inequalities, Solving real-world linear ordering problems using a primal-dual interior point cutting plane method, A cutting plane method from analytic centers for stochastic programming, Using the analytic center in the feasibility pump, An interior point cutting plane heuristic for mixed integer programming, An interior-point Benders based branch-and-cut algorithm for mixed integer programs, A new warmstarting strategy for the primal-dual column generation method, A build-up variant of the logarithmic barrier method for LP, Polynomial Interior Point Cutting Plane Methods, A warm-start approach for large-scale stochastic linear programs, Self-concordant barriers for convex approximations of structured convex sets, Using selective orthonormalization to update the analytic center after addition of multiple cuts, Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts, Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method, Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A monotonic projective algorithm for fractional linear programming
- A modification of Karmarkar's linear programming algorithm
- A new polynomial-time algorithm for linear programming
- Computational experience with a primal-dual interior point method for linear programming
- On the use of optimal fractional matchings for solving the (integer) matching problem
- An extension of Karmarkar's algorithm for linear programming using dual variables
- Conical projection algorithms for linear programming
- Cutting planes and column generation techniques with the projective algorithm
- Solution of sparse linear least squares problems using Givens rotations
- The ellipsoid method and its consequences in combinatorial optimization
- A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
- A survey of search directions in interior point methods for linear programming
- An interior point algorithm to solve computationally difficult set covering problems
- An implementation of Karmarkar's algorithm for linear programming
- Solving matching problems with linear programming
- Orthogonal Reduction of Sparse Matrices to Upper Triangular Form Using Householder Transformations
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- A Variant of Karmarkar’s Linear Programming Algorithm for Problems with Some Unrestricted Variables
- The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
- The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Multi-Terminal Network Flows
- Odd Minimum Cut-Sets and b-Matchings
- Decomposition and Nondifferentiable Optimization with the Projective Algorithm
- A Potential Reduction Algorithm Allowing Column Generation
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
- Further Development of a Primal-Dual Interior Point Method
- Paths, Trees, and Flowers
- Computer Solutions of the Traveling Salesman Problem
- Maximum matching and a polyhedron with 0,1-vertices
