Combinatorial complexity of a certain 1-dimensional Cutting Stock Problem
V. M. Kartaka, V. V. Kartakb
a Ufa State Aviation Technical University, Ufa, Russia
b Bashkir State University, Ufa, Russia
The classical Cutting Stock Problem (1dCSP) is considered. It is known that 1CSP is at least NP-hard. In the present paper a combinatorial algorithm for its solution based on the Branch and Bound Method is described. We estimate the complexity of this algorithm presented for a class of problems that is called compact. The most difficult examples to solve by combinatorial algorithms are identified. This result is consistent with experimental data and could be used to generate difficult test problems, as well as for predicting the time of the algorithm.
Cutting Stock Problem, Branch and Bound Method, integer programming, combinatorial complexity.
PDF file (464 kB)
V. M. Kartak, V. V. Kartak, “Combinatorial complexity of a certain 1-dimensional Cutting Stock Problem”, Ufimsk. Mat. Zh., 3:4 (2011), 57–63
Citation in format AMSBIB
\by V.~M.~Kartak, V.~V.~Kartak
\paper Combinatorial complexity of a~certain 1-dimensional Cutting Stock Problem
\jour Ufimsk. Mat. Zh.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|