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

scip	SCIP data structure
randnumgen	random 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()

static SCIP_RETCODE runCircle ( void  )

static

runs circle enclosing example

Definition at line 102 of file circle.c.

References FALSE, NULL, randseed, SCIP_CALL, SCIP_OKAY, SCIPcreate(), SCIPcreateRandom(), SCIPfree(), SCIPfreeRandom(), SCIPgetBestSol(), SCIPgetNSols(), SCIPincludeDefaultPlugins(), SCIPinfoMessage(), SCIPprintOrigProblem(), SCIPprintSol(), SCIPsolve(), setupProblem(), and TRUE.

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 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().