Abstract
This paper is the continuation of a previous work (Fasano in 4OR 2: 161–174, 2004), dedicated to a MIP formulation for non-standard 3D-packing issues, with additional conditions. The Single Bin Packing problem (Basic Problem) is considered and its MIP formulation shortly surveyed, together with some possible extensions, including balancing, tetris-like items and non-standard domains. A MIP-based heuristic is proposed to solve efficiently the Basic Problem or any possible extension of it, susceptible to a MIP formulation. The heuristic is a recursive procedure based on a non-blind local search philosophy. The concept of abstract configuration, concerning the relative positions between items, is introduced: the relative positions of items, determined by any abstract configuration, give rise to a feasible solution in an unbounded domain. The heuristic generates a sequence of good abstract configurations and solves, step by step, a reduced MIP model by fixing the relative positions of items, corresponding to the current abstract configuration.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Addis B, Locatelli M, Schoen F (2006) Efficiently packing unequal disks in a circle: a computational approach which exploits the continuous and combinatorial structure of the problem. Optimization Online (http://www.optimization-online.org) 1343
Blazewicz J, Hawryluk P, Walkowiak R (1993) Using a tabu search approach for solving the two-dimensional irregular cutting problem. AOR 41:313–327
Castillo I, Kampas FJ, Pintér JD (2006) Solving circle packing by global optimization: numerical results and industrial application. (Submitted)
Coffman E, Garey JM, Johnson D (1997) Approximation algorithms for bin packing: a survey. PWS Publishing Company, Boston
Chen CS, Lee SM, Shen QS (1995) An analytical model for the container loading problem. Eur J Oper Res 80:68–76
Daughtrey RS et al (1991) A simulated annealing approach to 3D packing with multiple constraints, Cosmic Program MFS28700, Boeing Huntsville AI Center Huntsville (Alabama)
Dyckhoff H, Scheithauer G, Terno J (1997) Cutting and packing. In: Dell’Amico M et al. (eds). Annotated bibliographies in combinatorial optimization. Wiley, Chichester
Egeblad J, Nielsen BK, Odgaard A (2006) Fast neighborhood search for two- and three-dimensional nesting problems. Euro J Oper Res (in press)
Fasano G (1989) Satellite optimal layout IBM Europe Institute 1989, application of mathematical and optimization techniques, Garmisch PK (Ge)
Fasano G (1999) Cargo analytical integration in space engineering: a three-dimensional packing model. In: Ciriani T, Gliozzi S, Johnson EL (eds) Operations research in industry, Macmillan, pp 232–246
Fasano G (2003) MIP Models for solving three-dimensional packing problems arising in space engineering. In: Ciriani T, Fasano G, Gliozzi S, Tadei R (eds). Operations research in space and air. Kluwer, Boston, pp 43–56
Fasano G (2004) A MIP approach for some practical packing problems: balancing constraints and tetris-like items. 4OR 2:161–174
Fasano G et al (2003) A Cargo accommodation problem for a space vehicle: the CAST project. In: Ciriani T, Fasano G, Gliozzi S, Tadei R (eds). Operations research in space and air. Kluwer, Dordrecht, pp. 13–26
Fekete S, Schepers J (2004) A combinatorial characterization of higher-dimensional orthogonal packing. Math Oper Res 29:353–368
Fekete S, Schepers J (2006) An exact algorithm for higher-dimensional orthogonal packing. Oper Res (in press)
Fischetti M, Luzzi I (2003) Exact and heuristic MIP models for nesting problems. EURO XIX Conference, Istanbul, Turkey
Gones AM, Oliveira JF (2002) A 2-exchange heuristics for nesting problems. Eur J Oper Res 141:359–570
Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper Res 48:256–267
Martello S, Pisinger D, Vigo D, Edgar den Boef Korst J (2006) Algorithms for general and robot-packable variants of the three- dimensional bin packing problem. ACM Trans Math Software (in press)
Mathur K (1998) An integer programming-based heuristic for the balanced loading problem. Oper Res Lett 22:19–25
Oliveira JF, Ferreira JS (1993) Algorithms for nesting problems. In: René Vidal VV (ed) Applied simulated annealing. Lecture Notes in Economics andMathematical Systems, Springer, Heidelberg, pp 255–273
Onodera H, Taniguchi Y, Tmaru K (1991) Branch-and-bound placement for building block layout. 28th ACM/IEEE design automation conference, pp 433–439
Padberg M (1999) Packing small boxes into a big box. New York University, Office of Naval Research, N00014-327
Pintér JD, Kampas FJ (2004) Generalized circle packings: model formulations and numerical results. In: Proceedings of the 6th international mathematica symposium, Banff, AB, Canada
Pintér JD, Kampas FJ (2005) Nonlinear optimization in mathematica with mathoptimizer professional. Math Educ Res 10(2)
Pisinger D (1998) A tree search heuristic for the container loading problem. Ric Oper 28:31–48
Pisinger D, Sigurd MM (2005) The two-dimensional bin packing problem with variable bin sizes and costs. Disctrete Optim 2:154–167
Pisinger D, Sigurd MM (2006) Using decomposition techniques and constraints programming for solving the two-dimensional bin packing problem. INFORMS J Comput (in press)
Stoyan Y et al (2004) Φ-functions for complex 2D-objects, 4OR 2:69–84
Tadei R et al (2003) A heuristic procedure for the space cargo rack configuration problem. In: Ciriani T, Fasano G, Gliozzi S, Tadei R (eds). Operations research in space and air. Kluwer, Dordrecht, pp. 27–42
Takadama K et al (2004) Capabilities of a multiagent-based cargo layout system for H-II transfer vehicle, 16th IFAC symposium on automatic control in aerospace
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fasano, G. MIP-based heuristic for non-standard 3D-packing problems. 4OR 6, 291–310 (2008). https://doi.org/10.1007/s10288-007-0049-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-007-0049-1
Keywords
- Non-standard 3D-packing
- Balancing conditions
- Additional conditions
- MIP-based heuristics
- Abstract configuration