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

DOI10.1007/s10107-009-0335-0zbMath1229.90101OpenAlexW2061059731MaRDI QIDQ647393

Arrigo Zanette, Egon Balas, Matteo Fischetti

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

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

Related Items

Theoretical challenges towards cutting-plane selection, Local cuts for mixed-integer programming, Partial hyperplane activation for generalized intersection cuts, On the enumerative nature of Gomory's dual cutting plane method, A computational study of the cutting plane tree algorithm for general mixed-integer linear programs, Coordinated cutting plane generation via multi-objective separation, Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs, Using symmetry to optimize over the Sherali-Adams relaxation, A relax-and-cut framework for Gomory mixed-integer cuts, A hard integer program made easy by lexicography, Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization, A lexicographic pricer for the fractional bin packing problem, On the exact separation of cover inequalities of maximum-depth

Uses Software

• PAGP
• MIPLIB
• MIPLIB2003

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing cut generators for mixed-integer linear programming
• Optimizing over the first Chvátal closure
• Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
• A review of goal programming and its applications
• Optimizing over the split closure
• Gomory cuts revisited
• Modern multidimensional scaling. Theory and applications.
• Numerically Safe Gomory Mixed-Integer Cuts
• Outline of an algorithm for integer solutions to linear programs
• Integer Programming and Pricing
• Can Pure Cutting Plane Algorithms Work?
• PAGP, A Partitioning Algorithm for (Linear) Goal Programming Problems
• Duality Theory of Linear Programs: A Constructive Approach with Applications
• Elementary closures for integer programs.