Optimization Online


MIP-based heuristic for non-standard 3D-packing problems

Giorgio Fasano (giorgio.fasano***at***thalesaleniaspace.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society