Solving MIPs via scaling-based augmentation

DOI10.1016/j.disopt.2017.08.004zbMath1506.90171arXiv1509.03206OpenAlexW2964108155MaRDI QIDQ1662107

Marc E. Pfetsch, Pierre Le Bodic, Sebastian Pokutta, Jeffrey W. Pavelka

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.03206

zbMATH Keywords

scalingprimal methodsaugmentation methodsmixed-integer programs

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Linear programming (90C05)

Related Items

Solving MIPs via scaling-based augmentation, Unnamed Item, Short simplex paths in lattice polytopes

Uses Software

• SCIP
• MIPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proximity search for 0--1 mixed-integer convex programming
• A polynomial oracle-time algorithm for convex integer minimization
• SCIP: solving constraint integer programs
• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• Nonlinear discrete optimization. An algorithmic theory
• On test sets for nonlinear integer maximization
• An application of simultaneous diophantine approximation in combinatorial optimization
• New scaling algorithms for the assignment and minimum mean cycle problems
• A combinatorial interior point method for network flow problems
• Test sets for integer programs
• Potential function methods for approximately solving linear programming problems: theory and practice.
• Local branching
• Solving MIPs via scaling-based augmentation
• The quadratic Graver cone, quadratic integer minimization, and extensions
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• Measuring the impact of primal heuristics
• Variable neighborhood search and local branching
• Lectures on Modern Convex Optimization
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• Nonlinear Integer Programming
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the foundations of linear and integer linear programming I
• Monotone Operators and the Proximal Point Algorithm
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• The Complexity of Generic Primal Algorithms for Solving General Integer Programs
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• 0/1-Integer programming: Optimization and Augmentation are equivalent