Optimization Online


A Modeling-based Approach for Non-standard Packing Problems

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

Abstract: This chapter examines the problem of packing tetris-like items, orthogonally, with the possibility of rotations, into a convex domain, in the presence of additional conditions. An MILP (Mixed Integer Linear Programming) and an MINLP (Mixed Integer Nonlinear Programming) models, previously studied by the author, are surveyed. An efficient formulation of the objective function, aimed at maximizing the loaded cargo, is pointed out for the MILP model. The MINLP one, addressed to the relevant feasibility sub-problem, has been conceived to improve approximate solutions, as an intermediate step of a heuristic process. A space-indexed model is further introduced and the problem of approximating polygons by means of tetris-like items investigated. In both cases an MILP formulation has been adopted. An overall heuristic approach is proposed to provide effective solutions in practice.

Keywords: tetris-like items ∙ Orthogonal packing ∙ Convex domain ∙ Additional/balancing conditions ∙ Mixed Integer Linerar/Non-linear Programming ∙ MILP/MINLP models ∙ Global Optimization (GO) ∙ Efficient formulation ∙ Feasibility sub-problem ∙ Space-indexed/grid-based-position paradigms ∙ Polygon approximation ∙ Heuristics

Category 1: Applications -- Science and Engineering

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

Category 3: Global Optimization

Citation: 'A Modeling-based Approach for Non-standard Packing Problems' by Giorgio Fasano. In: Giorgio Fasano and János D. Pintér, Eds. Optimized Packings and Their Applications. Springer Optimization and Its Applications, pp 67-85, 2015

Download: [PDF]

Entry Submitted: 04/25/2016
Entry Accepted: 04/25/2016
Entry Last Modified: 04/26/2016

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 Optimization Society