Mathematics – Optimization and Control
Scientific paper
2006-05-09
Discrete Optimization, 5:231--241, 2008
Mathematics
Optimization and Control
Scientific paper
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 $d$-dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting stock problem.
de Loera Jesus A.
Hemmecke Raymond
Onn Shmuel
Weismantel Robert
No associations
LandOfFree
N-Fold Integer Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with N-Fold Integer Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and N-Fold Integer Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-705853