LP-based Volume Bounds in Orthogonal Packing

G. Belov; H. Rohling; G. Scheithauer

Computer Science and Information Technologies, Computer Science and Information Technologies 2009

G. Belov, H. Rohling, G. Scheithauer

Last modified: 2021-01-29

Abstract

The d-Dimensional Orthogonal Packing Problem(OPP-d , d ⩾ 2) asks whether all given boxes canbe orthogonally packed into a given containerwithout rotations. The simplest bound for OPP isthe volume bound: if the total volume of the itemsexceeds that of the container then the instance isinfeasible. Conservative scales (CS) are modifieditem sizes such that if OPP is feasible, it is alsofeasible with the modified sizes. Thus, the volumebound for the modified instance is valid for theoriginal instance. Up to now, CS have beenconstructed either (i) completely independently ineach dimension using dual-feasible functions or (ii)by an exact method in the 2D case. Between (i) and(ii), there are possible heuristic algorithms whichconstruct d conservative scales (in d dimensions)simultaneously. Our first efforts in this directionhave shown that a simple LP iteration producesresults nearly identical with the exact method insmaller time. 3D results are presented as well.

Keywords

Volume Bounds; Orthogonal Packing; LP-based Volume

References

1. Alvarez-Valdes R, Parresno F, Tamarit JM. “Abranchand bound algorithm for the strip packingproblem”. OR Spectrum, 2009; 31(2): 431-459.

2. Baldacci R, Boschetti M.A. “A cutting-planeapproach for the two-dimensional orthogonal non-guillotine cutting problem”. European Journal ofOperational Research, 2007; 183(3): 1136-1149.

3. Belov G, Kartak V, Rohling H, Scheithauer G.“Onedimensional relaxations and LP bounds fororthogonal packing”. Preprint MATH-NM-03-2009,accepted for publication in InternationalTransactions on Operational Research, 2009.

4. Caprara A, Monaci M. “Bidimensional packing bybilinear programming”. Mathematical Programming,2009; 118(1): 75-108.

5. Carlier J, Clautiaux F, Moukrim A. “New reductionprocedures and lower bounds for the two-dimensionalbin packing problem with fixed orientation”.Computers & Operations Research, 2007; 34(8):2223-2250.

6. Clautiaux F, Alves C, de Carvalho J. V. “A survey ofdual-feasible functions for bin-packing problems”.Annals of Operations Research, 2008; to appear.

7. Clautiaux F, Jouglet A, Carlier J, Moukrim A. “Anew constraint programming approach for theorthogonal packing problem”. Computers &Operations Research, 2008; 35(3): 944-959.

8. Dowsland K.A. “The three—dimensional pallet chart:An analysis of the factors affecting the set of feasiblelayouts for a class of two-dimensional packingproblems”. Journal of the Operational ResearchSociety, 1984; 35(10): 895-905.

9. Fekete S.P, Schepers J. “A combinatorialcharacterization of higher-dimensional orthogonalpacking”. Mathematics of Operations Research,2004; 29(2): 353-368.

10. Fekete S.P, Schepers J. “A general framework forbounds for higher-dimensional orthogonal packingproblems”. Mathematical Methods of OperationsResearch, 2004; 60(2): 311-329.

Full Text: PDF