Optimization Online


A Global Optimization point of view for non-standard packing problems

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

Abstract: This work originates from research carried out in support to the cargo accommodation of space vehicles/modules. The goal of this activity is to maximize the loaded cargo, taking into account the given accommodation requirements. Items can often be modelled as parallelepipeds, but it is even more frequent that real world issues make this approximation no longer acceptable. These aspects and the presence of additional overall conditions, such as balancing, give rise to very challenging non-standard packing problems, not only in the frame of space engineering, but also in different application areas. This article considers first the orthogonal packing of tetris-like items, within a convex domain with additional conditions and subsequently the packing of polygons with (continuous) rotations in a convex domain with additional conditions. The proposed approach is based on mixed integer linear/non-linear programming (MIP, MINLP), from a global optimization (GO) point of view. The tetris-like formulation is exploited to provide the MINLP solution process with an approximated starting solution.

Keywords: Tetris-like items packing, non-rectangular domains, balancing/additional conditions, polygons packing, MIP/MINLP

Category 1: Applications -- Science and Engineering

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

Category 3: Global Optimization (Applications )

Citation: Thales Alenia Space Italia S.p.A., Str. Ant. di Collegno 10146, Turin, Italy

Download: [PDF]

Entry Submitted: 07/21/2010
Entry Accepted: 07/21/2010
Entry Last Modified: 07/30/2010

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