Optimization Online


A Customized Branch-and-Bound Approach for Irregular Shape Nesting

Akang Wang (akangw***at***andrew.cmu.edu)
Christopher L. Hanselman (chanselm***at***andrew.cmu.edu)
Chrysanthos E. Gounaris (gounaris***at***cmu.edu)

Abstract: We study the Nesting Problem, which aims to determine a configuration of a set of irregular shapes within a rectangular sheet of material of fixed width, such that no overlap among the shapes exists, and such that the length of the sheet is minimized. When both translation and rotation of the shapes are allowed, the problem can be formulated as a nonconvex quadratic programming model that approximates each shape by a set of inscribed circles and enforces that circle pairs stemming from different shapes do not overlap. However, despite many recent advances in today's global optimization solvers, solving this nonconvex model to guaranteed optimality remains extremely challenging even for the state-of-the-art codes. In this paper, we propose a customized branch-and-bound approach to address the Nesting Problem to guaranteed optimality. Our approach utilizes a novel branching scheme to deal with the reverse convex quadratic constraints in the quadratic model and incorporates a number of problem-specific algorithmic tweaks. Our computational studies on a suite of 64 benchmark instances demonstrate the customized algorithm's effectiveness and competitiveness over the use of general-purpose global optimization solvers, including for the first time the ability to find global optimal nestings featuring five polygons under free rotation.

Keywords: Nesting Problem, Irregular Strip Packing, Global Optimization, Reverse Convex Quadratic Constraints

Category 1: Global Optimization (Applications )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Carnegie Mellon University, Pittsburgh, PA, August, 2017.

Download: [PDF]

Entry Submitted: 10/26/2017
Entry Accepted: 11/01/2017
Entry Last Modified: 11/01/2017

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