A distributed global optimization method for packing problems

Han-Lin Li, J. F. Tsai*, N. Z. Hu

*Corresponding author for this work

Research output: Contribution to journalArticle

16 Scopus citations

Abstract

Packing optimization problems aim to seek the best way of placing a given set of rectangular cartons within a minimum volume rectangular container. Currently, packing optimization methods either have difficulty in finding a globally optimal solution or are computationally inefficient, because models involve too many 0-1 variables and because use of just a single computer. This study proposes a distributed computation method for solving a packing problem by a set of personal computers via the Internet. First, the traditional packing optimization model is converted into an equivalent model containing many fewer 0-1 variables. Then the model is decomposed into several sub-problems by dividing the objective value into many intervals. Each of these sub-problems is a linearized logarithmic program expressed as a linear mixed 0-1 problem. The whole problem is solvable and reaches a globally optimal solution. The numerical examples demonstrate that the proposed method can obtain the global optimum of a packing problem effectively.

Original languageEnglish
Pages (from-to)419-425
Number of pages7
JournalJournal of the Operational Research Society
Volume54
Issue number4
DOIs
StatePublished - 1 Apr 2003

Keywords

  • Cutting stock problem
  • Distributed computation
  • Layout
  • Optimization

Fingerprint Dive into the research topics of 'A distributed global optimization method for packing problems'. Together they form a unique fingerprint.

  • Cite this