{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,3]],"date-time":"2023-04-03T08:26:49Z","timestamp":1680510409876},"reference-count":31,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2013,4]]},"abstract":" We consider the feasibility problem OPP (orthogonal packing problem) in higher-dimensional orthogonal packing: given a set of d-dimensional (d \u2265 2) rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. The one-dimensional (1D) \u201cbar\u201d LP relaxation of OPP reduces the latter to a 1D cutting-stock problem where the packing of each stock bar represents a possible 1D stitch through an OPP layout. The dual multipliers of the LP provide us with another kind of powerful bounding information (conservative scales). We investigate how the set of possible 1D packings can be tightened using the overlapping information of item projections on the axes, with the goal to tighten the relaxation. We integrate the bar relaxation into an interval-graph algorithm for OPP, which operates on such overlapping relations. Numerical results on 2D and 3D instances demonstrate the efficiency of tightening leading to a speedup and stabilization of the algorithm. <\/jats:p>","DOI":"10.1287\/opre.1120.1150","type":"journal-article","created":{"date-parts":[[2013,4,16]],"date-time":"2013-04-16T16:22:24Z","timestamp":1366129344000},"page":"483-497","source":"Crossref","is-referenced-by-count":12,"title":["LP Bounds in an Interval-Graph Algorithm for Orthogonal-Packing Feasibility"],"prefix":"10.1287","volume":"61","author":[{"given":"Gleb","family":"Belov","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Duisburg-Essen, 47057 Duisburg, Germany"}]},{"given":"Heide","family":"Rohling","sequence":"additional","affiliation":[{"name":"OncoRay\u2014National Center of Radiation Research in Oncology, Dresden University of Technology, 01307 Dresden, Germany"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/s00291-008-0128-5"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.11.060"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1985.10"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0731-0"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00713.x"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/s00291-011-0277-9"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0833"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1093\/imaman\/13.2.95"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0184-7"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_4"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.05.012"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0079"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/s001860400376"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0369"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-8349-9777-7_2"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.6.849"},{"key":"B18","volume-title":"Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics","volume":"57","author":"Golumbic MC","year":"2004","edition":"2"},{"key":"B19","unstructured":"Hopper E. Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods. (2000) . Ph.D. thesis, Cardiff University, Cardiff, UK"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00357-4"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.08.020"},{"key":"B22","first-page":"142","volume-title":"Proc. Fourteenth Internat. Conf. Automated Planning and Scheduling (ICAPS 2004)","author":"Korf RE","year":"2004"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.08.005"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.310.16082"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45586-8_1"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.12.010"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s001860000066"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1060.0181"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00361-4"},{"key":"B30","unstructured":"Rohling H. LP bounds in exact algorithms for two-dimensional orthogonal packing. (2008) . Diploma thesis, Dresden University of Technology, Dresden, Germany"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.1999.tb00151.x"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85958-1_4"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.1120.1150","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T13:34:08Z","timestamp":1680442448000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.1120.1150"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1287\/opre.1120.1150"],"URL":"https:\/\/doi.org\/10.1287\/opre.1120.1150","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4]]}}}