Lexicography and degeneracy: Can a pure cutting plane algorithm work?

DOI10.1007/S10107-009-0335-0MaRDI QIDQ647393zbMATH OpenOpenAlexFDO

Authors Arrigo Zanette, Matteo Fischetti, E. Balas

Publication date 23 November 2011

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

Full work available at URL https://doi.org/10.1007/s10107-009-0335-0

zbMATH Keywords

computational analysiscutting plane methodsdegeneracy in linear programmingGomory cutslexicographic dual simplex

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Extreme-point and pivoting methods (90C49)

Recommendations

• Can Pure Cutting Plane Algorithms Work?
• A hard integer program made easy by lexicography
• On the enumerative nature of Gomory's dual cutting plane method
• Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective
• Gomory cuts revisited

Cites work

• A review of goal programming and its applications
• Can Pure Cutting Plane Algorithms Work?
• Duality Theory of Linear Programs: A Constructive Approach with Applications
• Elementary closures for integer programs.
• Gomory cuts revisited
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1175944 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• Integer Programming and Pricing
• Modern multidimensional scaling. Theory and applications.
• Numerically safe Gomory mixed-integer cuts
• Optimizing over the first Chvátal closure
• Optimizing over the split closure
• Outline of an algorithm for integer solutions to linear programs
• PAGP, A Partitioning Algorithm for (Linear) Goal Programming Problems
• Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
• Testing cut generators for mixed-integer linear programming

Cited in

(16)

• Theoretical challenges towards cutting-plane selection
• A relax-and-cut framework for Gomory mixed-integer cuts
• On the exact separation of cover inequalities of maximum-depth
• Partial hyperplane activation for generalized intersection cuts
• A lexicographic pricer for the fractional bin packing problem
• Local cuts for mixed-integer programming
• Coordinated cutting plane generation via multi-objective separation
• Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs
• Can Pure Cutting Plane Algorithms Work?
• A computational study of the cutting plane tree algorithm for general mixed-integer linear programs
• Exploring the numerics of branch-and-cut for mixed integer linear optimization
• Using symmetry to optimize over the Sherali-Adams relaxation
• On the enumerative nature of Gomory's dual cutting plane method
• \(\mathcal{V}\)-polyhedral disjunctive cuts
• A hard integer program made easy by lexicography
• The strength of root cuts in an extended abstract branch-and-cut model

Describes a project that uses

Uses Software

• PAGP
• MIPLIB2003
• MIPLIB

This page was built for publication: Lexicography and degeneracy: Can a pure cutting plane algorithm work?

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