Optimization Online


A MIP Approach for some Practical Packing Problems: Balancing Constraints and Tetris-like Items

giorgio fasano (giorgio.fasano***at***thalesaleniaspace.com)

Abstract: This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach is proposed. The three-dimensional single bin packing problem is considered. It consists of orthogonally placing, with possibility of rotation, the maximum number of parallelepipeds into a given parallelepiped. A MIP formulation of the problem is reported together with a MIP-based heuristic approach. Balancing conditions are furthermore examined, as well as the orthogonal placement (with rotation) of tetris-like items into a rectangular domain.

Keywords: packing, balancing conditions, tetris-like items, mixed integer programming, MIP-based heuristic approach

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: 4OR Quarterly Journal of Operations Research Volume 2, Number 2, 2004

Download: [PDF]

Entry Submitted: 06/13/2007
Entry Accepted: 06/13/2007
Entry Last Modified: 06/14/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