Optimization Online


On tackling reverse convex constraints for non-overlapping of unequal circles

Akang Wang (akangw***at***andrew.cmu.edu)
Chrysanthos E. Gounaris (gounaris***at***cmu.edu)

Abstract: We study the unequal circle-circle non-overlapping constraints, a form of reverse convex constraints that often arise in optimization models for cutting and packing applications. The feasible region induced by the intersection of circle-circle non-overlapping constraints is highly non-convex, and standard approaches to construct convex relaxations for spatial branch-and-bound global optimization of such models typically yield unsatisfactory loose relaxations. Consequently, solving such non-convex models to guaranteed optimality remains extremely challenging even for the state-of-the-art codes. In this paper, we apply a purpose-built branching scheme on non-overlapping constraints and utilize strengthened intersection cuts and various feasibility-based tightening techniques to further tighten the model relaxation. We embed these techniques into a branch-and-bound code and test them on two variants of circle packing problems. Our computational studies on a suite of 75 benchmark instances yielded, for the first time in the open literature, a total of 54 provably optimal solutions, and it was demonstrated to be competitive over the use of the state-of-the-art general-purpose global optimization solvers.

Keywords: non-overlapping constraints, circle packing, global optimization, branching scheme, strengthened intersection cuts, feasibility-based tightening

Category 1: Global Optimization

Category 2: Global Optimization (Applications )

Citation: Wang, A., Gounaris, C.E. On tackling reverse convex constraints for non-overlapping of unequal circles. J Glob Optim 80, 357385 (2021). https://doi.org/10.1007/s10898-020-00976-y


Entry Submitted: 12/17/2019
Entry Accepted: 12/22/2019
Entry Last Modified: 06/10/2021

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