MIP-based heuristic for non-standard 3D-packing problems
Giorgio Fasano (giorgio.fasanothalesaleniaspace.com)
Abstract: This paper is the continuation of a previous work (Fasano 2004), dedicated to a MIP formulation for non-standard three-dimensional 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.
Keywords: non-standard three-dimensional packing, balancing conditions,additional conditions, MIP-based heuristics, abstract configuration
Category 1: Applications -- OR and Management Sciences
Category 2: Integer Programming ((Mixed) Integer Linear Programming )
Citation: Accepted for pubblication in '4OR A Quarterly Journal of Operations Research'
Entry Submitted: 06/14/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|