Discretization based solution approaches for the circle packing problem

Taşpınar, Rabia (2021) Discretization based solution approaches for the circle packing problem. [Thesis]

[thumbnail of 10409817.pdf] PDF

Download (558kB)


In this thesis, we study the Circle Packing Problem (CPP), which involves packing a set of circles into the smallest surrounding container. This problem can be cast as a nonconvex quadratically constrained quadratic program with reverse convex constraints, which is difficult to solve in general. The CPP arises in different application areas such as automobile, textile, food, and chemical industries. For this problem, we propose an iterative solution approach based on a bisection-type algorithm on the radius of the surrounding container. At each iteration, the algorithm solves two different mixed-integer linear programming formulations proposed for a restricted and a relaxed version of the original problem over the discretized surrounding container. In the restricted version, the centers of the circles can only be located at the candidate points in each cell. By changing some properties of the restricted version, we also construct a relaxed version of the original problem. We also proposed an enhancement to the algorithm that exploits the special structure of CPP. We perform a computational study in order to evaluate the performance of our algorithm. We compare the results from our algorithm with those from commercial global optimization solvers BARON and Gurobi that solve the original nonlinear formulation, and also with the results of other methods from the literature. In addition, we examine a case study from a real life problem from the automobile industry, which is solved to a small optimality gap.
Item Type: Thesis
Uncontrolled Keywords: circle packing problem. -- discretization. -- global optimization. -- çember paketleme problemi. -- ayrıklastırma. -- küresel eniyileme.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 26 Oct 2021 14:28
Last Modified: 26 Apr 2022 10:39
URI: https://research.sabanciuniv.edu/id/eprint/42522

Actions (login required)

View Item
View Item