Discretization based solution approaches for the circle packing problem

Official URL: https://risc01.sabanciuniv.edu/record=b2579570_(Table of contents)

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.