On the Complexity of a Cutting Plane Algorithm for Solving Combinatorial Linear Programs

DOI10.1137/S089548019325900XMaRDI QIDQ4895628zbMATHOpenAlexFDO

Authors E. Andrew Boyd

Publication date 14 October 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s089548019325900x

zbMATH Keywords

cutting plane algorithmseparation oraclecombinatorial linear programs

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Mixed integer programming (90C11)

Recommendations

• A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball
• scientific article; zbMATH DE number 780782
• A long-step, cutting plane algorithm for linear and convex programming
• Solving combinatorial optimization problems using Karmarkar's algorithm
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs

Cited in

(14)

• scientific article; zbMATH DE number 3982913 (Why is no real title available?)
• A long-step, cutting plane algorithm for linear and convex programming
• scientific article; zbMATH DE number 6829289 (Why is no real title available?)
• scientific article; zbMATH DE number 780782 (Why is no real title available?)
• Branch and cut methods for network optimization
• On cutting planes for cardinality-constrained linear programs
• scientific article; zbMATH DE number 1778406 (Why is no real title available?)
• A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball
• A parallel cutting plane algorithm for two-level linear programming problems
• On the redundancy of cutting planes for linear complementarity problems
• scientific article; zbMATH DE number 4133833 (Why is no real title available?)
• Combinatorial complexity of a certain 1-dimensional cutting stock problem
• Solving combinatorial optimization problems using Karmarkar's algorithm
• Complexity estimates of some cutting plane methods based on the analytic barrier

Describes a project that uses

Uses Software

• MINTO

This page was built for publication: On the Complexity of a Cutting Plane Algorithm for Solving Combinatorial Linear Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4895628)