RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Ufimsk. Mat. Zh.: Year: Volume: Issue: Page: Find

 Ufimsk. Mat. Zh., 2011, Volume 3, Issue 4, Pages 57–63 (Mi ufa118)

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

Abstract: 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.

Keywords: Cutting Stock Problem, Branch and Bound Method, integer programming, combinatorial complexity.

Full text: PDF file (464 kB)
References: PDF file   HTML file

Bibliographic databases:

Document Type: Article
UDC: 519.1+519.8

Citation: 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
\Bibitem{KarKar11} \by V.~M.~Kartak, V.~V.~Kartak \paper Combinatorial complexity of a~certain 1-dimensional Cutting Stock Problem \jour Ufimsk. Mat. Zh. \yr 2011 \vol 3 \issue 4 \pages 57--63 \mathnet{http://mi.mathnet.ru/ufa118} \zmath{https://zbmath.org/?q=an:1249.05049}