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'

Download: [PDF]

Entry Submitted: 06/14/2007
Entry Accepted: 06/14/2007
Entry Last Modified: 06/15/2007

Modify/Update this entry