Circle Packing

Description

In this AIMMS project different circle packing problems are solved.

An object packing is a non-overlapping arrangement of a collection of objects in a container set; an optimized packing meets a specific optimality criterion. This general problem statement includes the frequently studied special cases in which identical circles (with an unknown, maximized radius) are to be packed into the unit square or the unit circle. A similar – but generally more difficult – problem is the packing of an arbitrary collection of circles in an optimized circle (with minimal radius).

To solve object packing problems numerically, we often need nonlinear optimization tools. In the case of circle packings listed above, we have to handle non-convex models, therefore the global solver LGO can be used as a suitable tool. We recommend having solver LGO installed before running this example.

In this illustrative AIMMS project, three different circle packing problems are solved:

1) Packing equal size circles in the unit square; the objective is to maximize the radius of the packed circles.

2) Packing equal size circles in the unit circle; the objective is again to maximize the radius of the packed circles.

3) Packing a set of non-uniform size circles in an optimized circle; the objective is to minimize the radius of the container circle.

These models have been developed based on, and thanks to, reference materials by János D. Pintér and Frank J. Kampas.

Keywords

Circle Packing, LGO, Network Object

Industries

Manufacturing

Model Types

Nonlinear Programming, Global Optimization

Download AIMMS Example

You can download an AIMMS example dealing with this problem via the link below, and run it after installing the AIMMS software. If you don’t have an AIMMS license yet, you can download a free license of AIMMS.

ftp://ftp.aimms.com/pub/Download/Examples/Circle Packing.aimmspack

Please make sure to save this file including the .aimmspack extension so that it can be opened by AIMMS.

This example application is a simplification of reality. Please do not hesitate to contact us to discuss how AIMMS enables you to build a complete optimization application that captures the full complexity of your problem.

Screenshot AIMMS Example

Circle Packing