Solving combinatorial optimization problems using Karmarkar's algorithm
From MaRDI portal
This paper presents a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem. The computational experience with this algorithm on matching problems is described.
Recommendations
- scientific article; zbMATH DE number 4197736
- On the Complexity of a Cutting Plane Algorithm for Solving Combinatorial Linear Programs
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- scientific article; zbMATH DE number 1047684
- A variable-metric variant of the Karmarkar algorithm for linear programming
Cites work
- A modification of Karmarkar's linear programming algorithm
- A monotonic projective algorithm for fractional linear programming
- A new polynomial-time algorithm for linear programming
- A Potential Reduction Algorithm Allowing Column Generation
- 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
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- A Variant of Karmarkar’s Linear Programming Algorithm for Problems with Some Unrestricted Variables
- An extension of Karmarkar's algorithm for linear programming using dual variables
- An implementation of Karmarkar's algorithm for linear programming
- An interior point algorithm to solve computationally difficult set covering problems
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Computational experience with a primal-dual interior point method for linear programming
- Computer Solutions of the Traveling Salesman Problem
- Conical projection algorithms for linear programming
- Cutting planes and column generation techniques with the projective algorithm
- Decomposition and Nondifferentiable Optimization with the Projective Algorithm
- Further Development of a Primal-Dual Interior Point Method
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- scientific article; zbMATH DE number 3069632 (Why is no real title available?)
- Maximum matching and a polyhedron with 0,1-vertices
- Multi-Terminal Network Flows
- Odd Minimum Cut-Sets and b-Matchings
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
- On the use of optimal fractional matchings for solving the (integer) matching problem
- Orthogonal Reduction of Sparse Matrices to Upper Triangular Form Using Householder Transformations
- Paths, Trees, and Flowers
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- Solution of sparse linear least squares problems using Givens rotations
- Solving matching problems with linear programming
- The ellipsoid method and its consequences in combinatorial optimization
- 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
Cited in
(27)- Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension
- A build-up variant of the logarithmic barrier method for LP
- 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
- Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming
- Solving nonlinear multicommodity flow problems by the analytic center cutting plane method
- Potential reduction algorithms for structured combinatorial optimization problems
- An analytic center cutting plane method for pseudomonotone variational inequalities
- Using selective orthonormalization to update the analytic center after addition of multiple cuts
- A logarithmic barrier cutting plane method for convex programming
- 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
- A Newton's method for perturbed second-order cone programs
- An interior-point Benders based branch-and-cut algorithm for mixed integer programs
- Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts
- Using the primal-dual interior point algorithm within the branch-price-and-cut method
- Using the analytic center in the feasibility pump
- Polynomial Interior Point Cutting Plane Methods
- On the Complexity of a Cutting Plane Algorithm for Solving Combinatorial Linear Programs
- A new warmstarting strategy for the primal-dual column generation method
- scientific article; zbMATH DE number 4197736 (Why is no real title available?)
- A warm-start approach for large-scale stochastic linear programs
- An interior point cutting plane heuristic for mixed integer programming
- Interior point methods in the year 2025
- Self-concordant barriers for convex approximations of structured convex sets
- A second-order cone cutting surface method: Complexity and application
This page was built for publication: Solving combinatorial optimization problems using Karmarkar's algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1196181)
