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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 25.06.2011

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}


Linking options:
  • http://mi.mathnet.ru/eng/ufa118
  • http://mi.mathnet.ru/eng/ufa/v3/i4/p57

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Уфимский математический журнал
    Number of views:
    This page:294
    Full text:76
    References:15
    First page:2

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019