کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141839 | 957095 | 2008 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
NN-fold integer programming
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
Transportation polytopeMarkov basis - اساس مارکوفHilbert basis - اساس هیلبرتCutting stock - برش سهامInteger programming - برنامه ریزی عدد صحیحBin Packing - بسته بندی بنAugmentation - تقویتContingency table - جدول احتمالیTest set - مجموعه تستTransportation problem - مشکل حمل و نقلGraver basis - پایه حفاری
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: NN-fold integer programming NN-fold integer programming](/preview/png/1141839.png)
چکیده انگلیسی
In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed nn-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 dd-dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting-stock problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 5, Issue 2, May 2008, Pages 231–241
Journal: Discrete Optimization - Volume 5, Issue 2, May 2008, Pages 231–241
نویسندگان
Jesús A. De Loera, Raymond Hemmecke, Shmuel Onn, Robert Weismantel,