N-fold integer programming
From MaRDI portal
\(N\)-fold integer programming
Abstract: In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed {em n-fold integer programming problems} are polynomial time solvable. Our proof involves two heavy ingredients discovered recently: the equivalence of linear optimization and so-called directed augmentation, and the stabilization of certain Graver bases. We discuss several applications of our algorithm to multiway transportation problems and to packing problems. One important consequence of our results is a polynomial time algorithm for the -dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting stock problem.
Recommendations
Cites work
- scientific article; zbMATH DE number 3828715 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 2087727 (Why is no real title available?)
- scientific article; zbMATH DE number 3294139 (Why is no real title available?)
- A Linear Programming Approach to the Cutting-Stock Problem
- A finiteness theorem for Markov bases of hierarchical models
- All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
- Approximation algorithms for multi-index transportation problems with decomposable costs
- Conditions for the existence of solutions of the three-dimensional planar transportation problem
- Convex combinatorial optimization
- Higher Lawrence configurations.
- Integer Programming and Combinatorial Optimization
- Integer Programming with a Fixed Number of Variables
- Markov bases of three-way tables are arbitrarily complicated
- Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
- On properties of multi-dimensional statistical tables
- On the foundations of linear and integer linear programming I
- On the positive sums property and the computation of Graver test sets
- Signature classes of transportation polytopes
- The Complexity of Generic Primal Algorithms for Solving General Integer Programs
- The Complexity of Three-Way Statistical Tables
- Three-dimensional Statistical Data Security Problems
Cited in
(44)- Combinatorial \(n\)-fold integer programming and applications
- Huge multiway table problems
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- Lower bounds on the graver complexity of M-fold matrices
- Markov Bases: A 25 Year Update
- Theory and Applications of n-Fold Integer Programming
- A polynomial oracle-time algorithm for convex integer minimization
- The Graver complexity of integer programming
- Computational complexity of three-dimensional discrete tomography with missing data
- Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes
- Compact representation of near-optimal integer programming solutions
- A heuristic method for solving integer-valued decompositional multiindex problems
- High-multiplicity \(N\)-fold IP via configuration LP
- Efficient solutions for weight-balanced partitioning problems
- A Polyhedral Frobenius Theorem with Applications to Integer Optimization
- Near-linear time algorithm for \(n\)-fold ILPs via color coding
- The double exponential runtime is tight for 2-stage stochastic ILPs
- scientific article; zbMATH DE number 3982918 (Why is no real title available?)
- Robust integer programming
- Portfolio-optimization models for small investors
- Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
- FPT algorithms for a special block-structured integer program with applications in scheduling
- The algebra of reversible Markov chains
- \(N\)-fold integer programming and nonlinear multi-transshipment
- Subset selection in sparse matrices
- The double exponential runtime is tight for 2-stage stochastic ILPs
- A polynomial-time algorithm for optimizing over \(N\)-fold 4-block decomposable integer programs
- Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
- The quadratic Graver cone, quadratic integer minimization, and extensions
- scientific article; zbMATH DE number 7561568 (Why is no real title available?)
- Convex integer optimization by constantly many linear counterparts
- The complexity of vector partition
- When is rounding allowed in integer nonlinear optimization?
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- scientific article; zbMATH DE number 7651172 (Why is no real title available?)
- Huge unimodular \(n\)-fold programs
- Block-structured integer programming: can we parameterize without the largest coefficient?
- \(n\)-fold integer programming in cubic time
- Unboundedness of Markov complexity of monomial curves in \(\mathbb{A}^n\) for \(n \geq 4\)
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Convex integer maximization via Graver bases
- Faster Algorithms for Integer Programs with Block Structure
- A colorful Steinitz lemma with application to block-structured integer programs
- Combinatorial \(n\)-fold integer programming and applications
This page was built for publication: \(N\)-fold integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q951095)
