Scippy

SCIP

Solving Constraint Integer Programs

circle.c File Reference

Detailed Description

Solving the Circle Enclosing Points Problem.

Author
Stefan Vigerske

This example shows how to setup second-order-cone constraints in SCIP when using SCIP as callable library. The example implements a model for the computation of a smallest circle that contains a number of given points in the plane.

The model is taken from the GAMS model library: http://www.gams.com/modlib/libhtml/circle.htm

See also: http://en.wikipedia.org/wiki/Smallest_circle_problem

Given n points in the plane with coordinates \((x_i, y_i)\), the task is to find a coordinates \((a,b)\) and a minimal radius \(r \geq 0\), such that \(\sqrt{(x_i-a)^2 + (y_i-b)^2} \leq r\). The latter are second-order-cone constraints.

Definition in file circle.c.

#include <stdio.h>
#include "scip/pub_misc.h"
#include "scip/scip.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

Functions

static SCIP_RETCODE setupProblem (SCIP *scip, SCIP_RANDNUMGEN *randnumgen)
 
static SCIP_RETCODE runCircle (void)
 
int main (int argc, char **argv)
 

Variables

static const int npoints = 10
 
static const unsigned int randseed = 42
 

Function Documentation

◆ setupProblem()

static SCIP_RETCODE setupProblem ( SCIP scip,
SCIP_RANDNUMGEN randnumgen 
)
static

sets up problem

Parameters
scipSCIP data structure
randnumgenrandom number generator

Definition at line 50 of file circle.c.

References a, b, npoints, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCons(), SCIPaddVar(), SCIPcreateConsBasicSOC(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPrandomGetReal(), SCIPreleaseCons(), SCIPreleaseVar(), and SCIPsnprintf().

Referenced by runCircle().

◆ runCircle()

◆ main()

int main ( int  argc,
char **  argv 
)

main method starting SCIP

Parameters
argcnumber of arguments from the shell
argvarray of shell arguments

Definition at line 142 of file circle.c.

References runCircle(), SCIP_OKAY, and SCIPprintError().

Variable Documentation

◆ npoints

const int npoints = 10
static

number of points to enclose by a circle

Definition at line 43 of file circle.c.

Referenced by applyHeur(), clusterPointsGreedy(), filterPoints(), setupProblem(), and solveNLP().

◆ randseed

const unsigned int randseed = 42
static

seed for random number generator

Definition at line 46 of file circle.c.

Referenced by runCircle().