Cutting planes and column generation techniques with the projective algorithm

DOI10.1007/BF00939559zbMath0676.90041OpenAlexW1977531475MaRDI QIDQ1123123

Jean-Philippe Vial, Jean-Louis Goffin

Publication date: 1990

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

column generationnondifferentiable optimizationcutting plane techniquesKarmarkar's algorithmdual projective methodprimal projective method

Mathematics Subject Classification ID

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

Related Items

Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming, Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs, BoxStep methods for crew pairing problems, 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 new algorithm for minimizing convex functions over convex sets, A cutting plane algorithm for convex programming that uses analytic centers, A cutting plane method for solving KYP-SDPs, An algorithm for bounded-error identification of nonlinear systems based on DC functions, Specialized fast algorithms for IQC feasibility and optimization problems., Solving combinatorial optimization problems using Karmarkar's algorithm, Using central prices in the decomposition of linear programs, A build-up variant of the logarithmic barrier method for LP, On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm, A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, Warm start of the primal-dual method applied in the cutting-plane scheme, Solving an equilibrium model for trade of \(\text{CO}_2\) emission permits

Uses Software

• ACCPM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• A polynomial Newton method for linear programming
• An analog of Karmarkar's algorithm for inequality constrained liner programs, with a `new' class of projective transformations for centering a polytope
• Conical projection algorithms for linear programming
• Partitioning procedures for solving mixed-variables programming problems
• An implementation of Karmarkar's algorithm for linear programming
• The Decomposition Algorithm for Linear Programs
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
• A Linear Programming Approach to the Cutting Stock Problem—Part II