N-fold integer programming

N-fold integer programming

0.00 Avg rating0 Votes
Article ID: iaor20091384
Country: Netherlands
Volume: 5
Issue: 2
Start Page Number: 231
End Page Number: 241
Publication Date: May 2008
Journal: Discrete Optimization
Authors: , , ,
Abstract:

In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed n-fold integer programming problems are polynomial time solvable. Our proof involves two heavy ingredients discovered recently: the equivalence of linear optimization and the 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 d-dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting-stock problem.

Reviews

Required fields are marked *. Your email address will not be published.