# SCIP

Solving Constraint Integer Programs

circlepacking.c File Reference

## Detailed Description

Packing circles in a rectangle of minimal size.

This example shows how to setup quadratic constraints in SCIP when using SCIP as callable library. The example implements a model for the computation of a smallest rectangle that contains a number of given circles in the plane or the computation of the maximal number of circles that can be placed into a given rectangle.

Suppose that n circles with radii $$r_i$$ are given. The task is to find coordinates $$(x_i, y_i)$$ for the circle midpoints and a rectangle of width $$W \geq 0$$ and height $$H \geq 0$$, such that

• every circle is placed within the rectangle ( $$r_i \leq x_i \leq W-r_i$$, $$r_i \leq y_i \leq H-r_i$$),
• circles are not overlapping $$\left((x_i-x_j)^2 + (y_i-y_j)^2 \geq (r_i + r_j)^2\right)$$, and
• the area of the rectangle is minimal.

Alternatively, one may fix the size of the rectangle and maximize the number of circles that can be fit into the rectangle without being overlapping.

Definition in file circlepacking.c.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

## Functions

static void visualizeSolutionMatplotlib (SCIP *scip, SCIP_SOL *sol)

static void visualizeSolutionGnuplot (SCIP *scip, SCIP_SOL *sol)

static SCIP_RETCODE visualizeSolutionAscii (SCIP *scip, SCIP_SOL *sol)

static SCIP_DECL_EVENTINIT (eventInitDispsol)

static SCIP_DECL_EVENTEXIT (eventExitDispsol)

static SCIP_DECL_EVENTEXEC (eventExecDispsol)

static SCIP_RETCODE includeEventHdlrDispsol (SCIP *scip)

static SCIP_RETCODE setupProblem (SCIP *scip, SCIP_Real fixwidth, SCIP_Real fixheight)

static SCIP_RETCODE runPacking (SCIP_Real fixwidth, SCIP_Real fixheight, SCIP_Bool dognuplot, SCIP_Bool domatplotlib)

int main (int argc, char **argv)

## Variables

int ncircles = 0

SCIP_Realr = NULL

int rsize = 0

SCIP_VAR ** x

SCIP_VAR ** y

SCIP_VAR ** b

SCIP_VARa

SCIP_VARw

SCIP_VARh

SCIP_Bool minarea

## ◆ visualizeSolutionMatplotlib()

 static void visualizeSolutionMatplotlib ( SCIP * scip, SCIP_SOL * sol )
static

plots solution by use of Python/Matplotlib

Parameters
 scip SCIP data structure sol solution to plot

Definition at line 74 of file circlepacking.c.

Referenced by runPacking().

## ◆ visualizeSolutionGnuplot()

 static void visualizeSolutionGnuplot ( SCIP * scip, SCIP_SOL * sol )
static

plots solution by use of gnuplot

Parameters
 scip SCIP data structure sol solution to plot

Definition at line 136 of file circlepacking.c.

Referenced by runPacking().

## ◆ visualizeSolutionAscii()

 static SCIP_RETCODE visualizeSolutionAscii ( SCIP * scip, SCIP_SOL * sol )
static

plots solution by use of ascii graphics

Parameters
 scip SCIP data structure sol solution to plot

Definition at line 194 of file circlepacking.c.

Referenced by SCIP_DECL_EVENTEXEC().

## ◆ SCIP_DECL_EVENTINIT()

 static SCIP_DECL_EVENTINIT ( eventInitDispsol )
static

initialization method of event handler (called after problem was transformed)

Definition at line 286 of file circlepacking.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, and SCIPcatchEvent().

## ◆ SCIP_DECL_EVENTEXIT()

 static SCIP_DECL_EVENTEXIT ( eventExitDispsol )
static

deinitialization method of event handler (called before transformed problem is freed)

Definition at line 295 of file circlepacking.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, and SCIPdropEvent().

## ◆ SCIP_DECL_EVENTEXEC()

 static SCIP_DECL_EVENTEXEC ( eventExecDispsol )
static

execution method of event handler

Definition at line 304 of file circlepacking.c.

## ◆ includeEventHdlrDispsol()

 static SCIP_RETCODE includeEventHdlrDispsol ( SCIP * scip )
static

creates event handler for dispsol event

Parameters
 scip SCIP data structure

Definition at line 320 of file circlepacking.c.

Referenced by runPacking().

## ◆ setupProblem()

 static SCIP_RETCODE setupProblem ( SCIP * scip, SCIP_Real fixwidth, SCIP_Real fixheight )
static

create problem in given SCIP and add all variables and constraints to model the circle packing problem

Parameters
 scip SCIP data structure fixwidth a given fixed width for the rectangle, or SCIP_INVALID if not fixed fixheight a given fixed height for the rectangle, or SCIP_INVALID if not fixed

Definition at line 339 of file circlepacking.c.

Referenced by runPacking().

## ◆ runPacking()

 static SCIP_RETCODE runPacking ( SCIP_Real fixwidth, SCIP_Real fixheight, SCIP_Bool dognuplot, SCIP_Bool domatplotlib )
static

run circle packing example

Sets up SCIP and the SCIP problem, solves the problem, and shows the solution.

Parameters
 fixwidth a given fixed width for the rectangle, or SCIP_INVALID if not fixed fixheight a given fixed height for the rectangle, or SCIP_INVALID if not fixed dognuplot whether to draw best solution with gnuplot domatplotlib whether to draw best solution with python/matplotlib

Definition at line 554 of file circlepacking.c.

Referenced by main().

## ◆ main()

 int main ( int argc, char ** argv )

main method starting SCIP

Parameters
 argc number of arguments from the shell argv array of shell arguments

Definition at line 629 of file circlepacking.c.

## ◆ ncircles

 int ncircles = 0

Number of possible circles

Definition at line 56 of file circlepacking.c.

## ◆ rsize

 int rsize = 0

Definition at line 60 of file circlepacking.c.

Referenced by main().

## ◆ minarea

 SCIP_Bool minarea

whether we minimize the area (TRUE) or maximize the number of circles in the rectangle (FALSE)

Definition at line 69 of file circlepacking.c.