Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory

References

• Johnson MP, Rennick C, Zak EJ. Skiving addition to the cutting stock problem in the paper industry. SIAM Rev. 1997;39(3):472–483. doi: 10.1137/S003614459531004X
   Web of Science ®Google Scholar
• Zak EJ. The skiving stock problem as a counterpart of the cutting stock problem. Int Trans Oper Res. 2003;10:637–650. doi: 10.1111/1475-3995.00433
   Google Scholar
• Delorme M, Iori M, Martello S. Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur J Oper Res. 2016;255:1–20. doi: 10.1016/j.ejor.2016.04.030
   Web of Science ®Google Scholar
• Gilmore PC, Gomory RE. A linear programming approach to the cutting-stock problem (Part I). Oper Res. 1961;9:849–859. doi: 10.1287/opre.9.6.849
   Web of Science ®Google Scholar
• Kantorovich LV. Mathematical methods of organising and planning production. Manage Sci. (1939 Russian, 1960 English);6:366–422. doi: 10.1287/mnsc.6.4.366
   Web of Science ®Google Scholar
• Martinovic J, Scheithauer G, Valério de Carvalho JM. A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems. Eur J Oper Res. 2018;266(2):458–471. doi: 10.1016/j.ejor.2017.10.008
   Web of Science ®Google Scholar
• Scheithauer G. Introduction to cutting and packing optimization – problems, modeling approaches, solution methods. 1st ed. Cham (Switzerland): Springer; 2018. (International series in operations research & management science; 263).
   Google Scholar
• Valério de Carvalho JM. LP models for bin packing and cutting stock problems. Eur J Oper Res. 2002;141(2):253–273. doi: 10.1016/S0377-2217(02)00124-8
   Web of Science ®Google Scholar
• Labbé M, Laporte G, Martello S. An exact algorithm for the dual bin packing problem. Oper Res Lett. 1995;17:9–18. doi: 10.1016/0167-6377(94)00060-J
   Web of Science ®Google Scholar
• Peeters M, Degraeve Z. Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem. Eur J Oper Res. 2006;170(2):416–439. doi: 10.1016/j.ejor.2004.06.034
   Web of Science ®Google Scholar
• Wäscher G, Haußner H, Schumann H. An improved typology of cutting and packing problems. Eur J Oper Res. 2007;183:1109–1130. doi: 10.1016/j.ejor.2005.12.047
   Web of Science ®Google Scholar
• Alon N, Azar Y, Csirik J, et al. On-line and off-line approximation algorithms for vector covering problems. Algorithmica. 1998;21:104–118. doi: 10.1007/PL00009203
   Web of Science ®Google Scholar
• Csirik J, Frenk JBG, Galambos G, et al. Probabilistic analysis of algorithms for dual bin packing problems. J Algorithms. 1991;12:189–203. doi: 10.1016/0196-6774(91)90001-F
   Web of Science ®Google Scholar
• Bruno JL, Downey PJ. Probabilistic bounds for dual bin-packing. Acta Inform. 1985;22:333–345.
   Web of Science ®Google Scholar
• Martinovic J, Jorswieck E, Scheithauer G. On the solution of generalized spectrum allocation problems. Oper Res Proc. 2018;2016:133–138.
   Google Scholar
• Martinovic J, Jorswieck E, Scheithauer G, et al. Integer linear programming formulations for cognitive radio resource allocation. IEEE Wirel Commun Lett. 2017;6(4):494–497. doi: 10.1109/LWC.2017.2708105
   Web of Science ®Google Scholar
• Tragos EZ, Zeadally S, Fragkiadakis VA, et al. Spectrum assignment in cognitive radio networks: a comprehensive survey. IEEE Commun Surv Tutorials. 2013;15(3):1108–1135. doi: 10.1109/SURV.2012.121112.00047
   Web of Science ®Google Scholar
• Alvim ACF, Ribeiro CC, Glover F, et al. A hybrid improvement heuristic for the one-dimensional bin packing problem. J Heuristics. 2004;10(2):205–229. doi: 10.1023/B:HEUR.0000026267.44673.ed
   Web of Science ®Google Scholar
• Arbib C, Di Iorio CF, Marinelli F, et al. Cutting and reuse: an application from automobile component manufacturing. Oper Res. 2002;50(6):923–934. doi: 10.1287/opre.50.6.923.348
   Web of Science ®Google Scholar
• Arbib C, Marinelli F. Integrating process optimization and inventory planning in cutting-stock with skiving option: an optimization model and its application. Eur J Oper Res. 2005;163(3):617–630. doi: 10.1016/j.ejor.2003.12.021
   Web of Science ®Google Scholar
• Chen Y, Song X, Ouelhadj D, et al. A heuristic for the skiving and cutting stock problem in paper and plastic film industries. Int Trans Oper Res. 2017, to appear. Available from: http://dx.doi.org/10.1111/itor.12390.
   Google Scholar
• Assmann SF, Johnson DS, Kleitman DJ, et al. On a dual version of the one-dimensional bin packing problem. J Algorithms. 1984;5:502–525. doi: 10.1016/0196-6774(84)90004-X
   Web of Science ®Google Scholar
• Assmann SF. Problems in discrete applied mathematics [PhD thesis]. Cambridge (MA): Mathematics Department, Massachusetts Institute of Technology; 1983.
   Google Scholar
• Martinovic J, Scheithauer G. Integer linear programming models for the skiving stock problem. Eur J Oper Res. 2016;251(2):356–368. doi: 10.1016/j.ejor.2015.11.005
   Web of Science ®Google Scholar
• Baum S, Trotter LE. Integer rounding for polymatroid and branching optimization problems. SIAM J Algebr Discrete Methods. 1981;2:416–425. doi: 10.1137/0602044
   Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM. Column generation. New York (NY): Springer; 2005.
   Google Scholar
• Valério de Carvalho JM. Exact solution of bin-packing problems using column generation and branch-and-bound. Ann Oper Res. 1999;86:629–659. doi: 10.1023/A:1018952112615
   Web of Science ®Google Scholar
• Vance PH, Barnhart C, Johnson EL, et al. Solving binary cutting stock problems by column generation and branch-and-bound. Comput Optim Appl. 1994;3(2):111–130. doi: 10.1007/BF01300970
   Google Scholar
• Nemhauser G, Wolsey L. Integer and combinatorial optimization. New York (NY): Wiley; 1988.
   Google Scholar
• Garfinkel R, Nemhauser GL. Integer programming. New York (NY): Wiley; 1972.
   Google Scholar
• Eisenbrand F, Weismantel R. Proximity results and faster algorithms for integer programming using the Steinitz lemma. Preprint; 2017 [cited 2018 Jun 23]. Available From: https://arxiv.org/abs/1707.00481.
   Google Scholar
• Martinovic J, Scheithauer G. The proper relaxation and the proper gap of the skiving stock problem. Math Methods Oper Res. 2016;84(3):527–548. doi: 10.1007/s00186-016-0552-2
   Web of Science ®Google Scholar
• Caprara A, Dell'Amico M, Díaz-Díaz JC, et al. Friendly bin packing instances without integer round-up property. Math Program. 2015;150(1):5–17. doi: 10.1007/s10107-014-0791-z
   Web of Science ®Google Scholar
• Rietz J, Dempe S. Large gaps in one-dimensional cutting stock problems. Discrete Appl Math. 2008;156(10):1929–1935. doi: 10.1016/j.dam.2007.08.052
   Web of Science ®Google Scholar
• Rietz J, Scheithauer G, Terno J. Families of non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl Math. 2002;121:229–245. doi: 10.1016/S0166-218X(01)00361-4
   Web of Science ®Google Scholar
• Martinovic J, Scheithauer G. An upper bound of for skiving stock instances of the divisible case. Discrete Appl Math. 2017;229:161–167. doi: 10.1016/j.dam.2017.05.015
   Web of Science ®Google Scholar
• Martinovic J, Scheithauer G. Integer rounding and modified integer rounding for the skiving stock problem. Discrete Optim. 2016;21:118–130. doi: 10.1016/j.disopt.2016.06.004
   Web of Science ®Google Scholar
• Martinovic J, Scheithauer G. LP-based relaxations of the skiving stock problem – improved upper bounds for the gap. Oper Res Proc. 2017;2015:49–54.
   Google Scholar
• Kartak VM, Ripatti AV, Scheithauer G, et al. Minimal proper non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl Math. 2015;187:120–129. doi: 10.1016/j.dam.2015.02.020
   Web of Science ®Google Scholar
• Marcotte O. Topics in combinatorial packing and covering. Cornell University; 1983. (Technical Report; no. 568).
   Google Scholar
• Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. New York (NY): W. H. Freeman & Co.; 1979.
   Google Scholar
• Marcotte O. The cutting stock problem and integer rounding. Math Program. 1985;33(1):82–92. doi: 10.1007/BF01582013
   Web of Science ®Google Scholar