The Complexity of Generic Primal Algorithms for Solving General Integer Programs

DOI10.1287/MOOR.27.4.681.305MaRDI QIDQ5704103zbMATH OpenOpenAlexFDO

Authors Andreas S. Schulz, Robert Weismantel

Publication date 11 November 2005

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.27.4.681.305

zbMATH Keywords

augmentation problemcombinatorial optimizationcomputational complexityinteger programmingprimal algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Primal integer programming
• The design of exponential neighborhoods -- a primal approach to integer programming.
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• A primal all-integer algorithm based on irreducible solutions
• Primal-dual approach for directed vertex connectivity augmentation and generalizations

Cited in

(16)

• Solving MIPs via scaling-based augmentation
• On the relative complexity of 15 problems related to~0/1-integer programming
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• Primal integer programming
• scientific article; zbMATH DE number 7064051 (Why is no real title available?)
• The design of exponential neighborhoods -- a primal approach to integer programming.
• A generalized simplex method for integer problems given by verification oracles
• Pivot rules for circuit-augmentation algorithms in linear optimization
• 0/1-Integer programming: Optimization and Augmentation are equivalent
• The complexity of geometric scaling
• Augmentation search for integer programming over a polyhedron
• Practical proximal primal-dual algorithms for structured saddle point problems
• Exploring the geometric buchberger algorithm in integer programming
• Integer programming with binary and bounded variables via Gröbner bases with applications to multiobjective integer programming
• Influence of the normalization constraint on the integral simplex using decomposition
• \(N\)-fold integer programming

This page was built for publication: The Complexity of Generic Primal Algorithms for Solving General Integer Programs

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