The cutting stock problem and integer rounding |
| |
Authors: | Odile Marcotte |
| |
Affiliation: | (1) Départment de mathématiques et d'informatique, Université de Sherbrooke, Sherbrooke, Canada |
| |
Abstract: | An integer programming problem is said to have the integer round-up property if its optimal value is given by the least integer greater than or equal to the optimal value of its linear programming relaxation. In this paper we prove that certain classes of cutting stock problems have the integer round-up property. The proof of these results relies upon the decomposition properties of certain knapsack polyhedra.This research was partially supported by National Science Foundation grants ECS-8005350 and 81-13534 to Cornell University. |
| |
Keywords: | Cutting Stock Problem Knapsack Polyhedron Integer Rounding |
本文献已被 SpringerLink 等数据库收录! |