Scippy

SCIP

Solving Constraint Integer Programs

circle.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file circle.c
17  * @brief Solving the Circle Enclosing Points Problem
18  * @author Stefan Vigerske
19  *
20  * This example shows how to setup second-order-cone constraints in SCIP when using SCIP as callable library.
21  * The example implements a model for the computation of a smallest circle that contains a number of given points
22  * in the plane.
23  *
24  * The model is taken from the GAMS model library:
25  * http://www.gams.com/modlib/libhtml/circle.htm
26  *
27  * See also: http://en.wikipedia.org/wiki/Smallest_circle_problem
28  *
29  * Given n points in the plane with coordinates \f$(x_i, y_i)\f$, the task is to find a coordinates \f$(a,b)\f$
30  * and a minimal radius \f$r \geq 0\f$, such that \f$\sqrt{(x_i-a)^2 + (y_i-b)^2} \leq r\f$.
31  * The latter are second-order-cone constraints.
32  */
33 
34 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <stdio.h>
37 
38 #include "scip/pub_misc.h"
39 #include "scip/scip.h"
40 #include "scip/scipdefplugins.h"
41 
42 /** number of points to enclose by a circle */
43 static const int npoints = 10;
44 
45 /** seed for random number generator */
46 static const unsigned int randseed = 42;
47 
48 /** sets up problem */
49 static
51  SCIP* scip, /**< SCIP data structure */
52  SCIP_RANDNUMGEN* randnumgen /**< random number generator */
53  )
54 {
55  SCIP_VAR* a;
56  SCIP_VAR* b;
57  SCIP_VAR* r;
58 
59  char name[SCIP_MAXSTRLEN];
60  int i;
61 
62  /* create empty problem */
63  SCIP_CALL( SCIPcreateProbBasic(scip, "circle") );
64 
65  /* create variables and add to problem */
66  SCIP_CALL( SCIPcreateVarBasic(scip, &a, "a", -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
67  SCIP_CALL( SCIPcreateVarBasic(scip, &b, "b", -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
68  SCIP_CALL( SCIPcreateVarBasic(scip, &r, "r", 0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_CONTINUOUS) );
69 
70  SCIP_CALL( SCIPaddVar(scip, a) );
71  SCIP_CALL( SCIPaddVar(scip, b) );
72  SCIP_CALL( SCIPaddVar(scip, r) );
73 
74  /* create soc constraints, add to problem, and forget about them */
75  for( i = 0; i < npoints; ++i )
76  {
77  SCIP_CONS* cons;
78  SCIP_VAR* ab[2];
79  SCIP_Real xy[2];
80 
81  ab[0] = a;
82  ab[1] = b;
83  xy[0] = -SCIPrandomGetReal(randnumgen, 1.0, 10.0);
84  xy[1] = -SCIPrandomGetReal(randnumgen, 1.0, 10.0);
85 
86  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "point%d", i);
87  SCIP_CALL( SCIPcreateConsBasicSOC(scip, &cons, name, 2, ab, NULL, xy, 0.0, r, 1.0, 0.0) );
88  SCIP_CALL( SCIPaddCons(scip, cons) );
89  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
90  }
91 
92  /* release variables */
93  SCIP_CALL( SCIPreleaseVar(scip, &a) );
94  SCIP_CALL( SCIPreleaseVar(scip, &b) );
95  SCIP_CALL( SCIPreleaseVar(scip, &r) );
96 
97  return SCIP_OKAY;
98 }
99 
100 /* runs circle enclosing example */
101 static
103 {
104  SCIP* scip;
105  SCIP_RANDNUMGEN* randnumgen;
106 
107  SCIP_CALL( SCIPcreate(&scip) );
109 
110  SCIPinfoMessage(scip, NULL, "\n");
111  SCIPinfoMessage(scip, NULL, "*********************************************\n");
112  SCIPinfoMessage(scip, NULL, "* Running Smallest Enclosing Circle Problem *\n");
113  SCIPinfoMessage(scip, NULL, "*********************************************\n");
114  SCIPinfoMessage(scip, NULL, "\n");
115 
116  /* create random number generator */
117  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, randseed, TRUE) );
118 
119  SCIP_CALL( setupProblem(scip, randnumgen) );
120 
121  SCIPinfoMessage(scip, NULL, "Original problem:\n");
122  SCIP_CALL( SCIPprintOrigProblem(scip, NULL, "cip", FALSE) );
123 
124  SCIPinfoMessage(scip, NULL, "\nSolving...\n");
125  SCIP_CALL( SCIPsolve(scip) );
126 
127  if( SCIPgetNSols(scip) > 0 )
128  {
129  SCIPinfoMessage(scip, NULL, "\nSolution:\n");
130  SCIP_CALL( SCIPprintSol(scip, SCIPgetBestSol(scip), NULL, FALSE) );
131  }
132 
133  /* free random number generator */
134  SCIPfreeRandom(scip, &randnumgen);
135 
136  SCIP_CALL( SCIPfree(&scip) );
137 
138  return SCIP_OKAY;
139 }
140 
141 /** main method starting SCIP */
142 int main(
143  int argc, /**< number of arguments from the shell */
144  char** argv /**< array of shell arguments */
145  ) /*lint --e{715}*/
146 {
147  SCIP_RETCODE retcode;
148 
149  retcode = runCircle();
150 
151  /* evaluate return code of the SCIP process */
152  if( retcode != SCIP_OKAY )
153  {
154  /* write error back trace */
155  SCIPprintError(retcode);
156  return -1;
157  }
158 
159  return 0;
160 }
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define NULL
Definition: def.h:239
SCIP_RETCODE SCIPcreateConsBasicSOC(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *coefs, SCIP_Real *offsets, SCIP_Real constant, SCIP_VAR *rhsvar, SCIP_Real rhscoeff, SCIP_Real rhsoffset)
Definition: cons_soc.c:5320
#define SCIP_MAXSTRLEN
Definition: def.h:260
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
#define FALSE
Definition: def.h:65
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static const int npoints
Definition: circle.c:43
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:184
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:339
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:223
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2577
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
static SCIP_RETCODE runCircle(void)
Definition: circle.c:102
SCIP_RETCODE SCIPprintOrigProblem(SCIP *scip, FILE *file, const char *extension, SCIP_Bool genericnames)
int main(int argc, char **argv)
Definition: circle.c:142
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
public data structures and miscellaneous methods
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
static SCIP_RETCODE setupProblem(SCIP *scip, SCIP_RANDNUMGEN *randnumgen)
Definition: circle.c:50
static const unsigned int randseed
Definition: circle.c:46
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2280
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9394
SCIP_Real * r
Definition: circlepacking.c:50
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1724
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIP_Real
Definition: def.h:150
void SCIPprintError(SCIP_RETCODE retcode)
Definition: scip_general.c:267
default SCIP plugins
SCIP callable library.
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:371
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1824