Guntram Scheithauer, Johannes Terno: A Cutting Plane Approach for the One-Dimensional Cutting-Stock Problem CSIT 2000 : 304
When solving the one-dimensional cutting stock problem (CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and the huge number of variables.
In the usual solution approach the continuous relaxation is solved via column generation technique followed by an appropriate rounding of the in general non-integer solution.
Obviously, in this way an optimal solution cannot be obtained for any instance.
In order to compute a proved optimal solution, techniques like branch-and-bound have to be applied.
In this paper we present another exact solution approach for the CSP which is based on the cutting plane method.
We investigate how to compute and how to use suitable cutting planes in an algorithm which is based on column generation.
Results of extensive computational experiments are reported.
Copyright © 2000 by the Institute for Contemporary Education "JurInfoR-MSU". Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the CSIT copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Institute for Contemporary Education JMSUICE. To copy otherwise, or to republish, requires a fee and/or special permission from the JMSUICE.
Heinz Schweppe and Yuri S. Kabalnov (Eds.): CSIT'2000, Proceedings of 2nd International Workshop on Computer Science and Information Technologies, September 18-23, 2000, Ufa, Russia. USATU Publishers & JurInfoR-MSU Publishing 2000, ISBN 5-86911-312-1
CSIT Proceedings: Copyright © by JurInfoR-MSU ICE,