# SCIP

Solving Constraint Integer Programs

brachistochrone.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-2022 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file brachistochrone.c
17  * @brief Computing a minimum-time trajectory for a particle to move from point A to B under gravity only
18  * @author Anass Meskini
19  * @author Stefan Vigerske
20  *
21  * This is an example that uses expressions to setup non-linear constraints in SCIP when used as
22  * a callable library. This example implements a discretized model to obtain the trajectory associated with the shortest
23  * time to go from point A to B for a particle under gravity only.
24  *
25  * The model:
26  *
27  * Given \f$N\f$ number of points for the discretisation of the trajectory, we can approximate the time to go from
28  * \f$(x_0,y_0)\f$ to \f$(x_N,y_N)\f$ for a given trajectory by \f[T = \sqrt{\frac{2}{g}}
29  * \sum_{0}^{N-1} \frac{\sqrt{(y_{i+1} - y_i)^2 + (x_{i+1} - x_i)^2}}{\sqrt{1-y_{i+1}} + \sqrt{1 - y_i}}.\f]
30  * We seek to minimize \f$T\f$.
31  * A more detailed description of the model can be found in the brachistochrone directory of http://scipopt.org/workshop2018/pyscipopt-exercises.tgz
32  *
33  * Passing this equation as it is to SCIP does not lead to satisfying results, though, so we reformulate a bit.
34  * Let \f$t_i \geq \frac{\sqrt{(y_{i+1} - y_i)^2 + (x_{i+1} - x_i)^2}}{\sqrt{1-y_{i+1}} + \sqrt{1 - y_i}}\f$.
35  * To avoid a potential division by zero, we rewrite this as
36  * \f$t_i (\sqrt{1-y_{i+1}} + \sqrt{1 - y_i}) \geq \sqrt{(y_{i+1} - y_i)^2 + (x_{i+1} - x_i)^2}, t_i\geq 0\f$.
37  * Further, introduce \f$v_i \geq 0\f$ such that \f$v_i \geq \sqrt{(y_{i+1} - y_i)^2 + (x_{i+1} - x_i)^2}\f$.
38  * Then we can state the optimization problem as
39  * \f{align}{ \min \;& \sqrt{\frac{2}{g}} \sum_{i=0}^{N-1} t_i \\
40  * \text{s.t.} \; & t_i (\sqrt{1-y_{i+1}} + \sqrt{1 - y_i}) \geq v_i \\
41  * & v_i^2 \geq (y_{i+1} - y_i)^2 + (x_{i+1} - x_i)^2 \\
42  * & t_i \geq 0,\; v_i \geq 0 \\
43  * & i = 0, \ldots, N-1
44  * \f}
45  *
46  * Further, we can require that the particle moves only in direction horizontally, that is
47  * \f$x_i \leq x_{i+1}\f$ if \f$x_0 \leq x_N\f$, and \f$x_{i+1} \leq x_{i}\f$, otherwise,
48  * and that it will not move higher than the start-coordinate.
49  */
50
51 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
52
53 #include <stdio.h>
54 #include <stdlib.h>
55
56 #include "scip/pub_misc.h"
57 #include "scip/scip.h"
58 #include "scip/scipdefplugins.h"
59
60 /* default start and end points */
61 #define Y_START 1.0
62 #define Y_END 0.0
63 #define X_START 0.0
64 #define X_END 10.0
65
66 /** sets up problem */
67 static
69  SCIP* scip, /**< SCIP data structure */
70  unsigned int n, /**< number of points for discretization */
71  SCIP_Real* coord, /**< array containing [y(0), y(N), x(0), x(N)] */
72  SCIP_VAR*** xvars, /**< buffer to store pointer to x variables array */
73  SCIP_VAR*** yvars /**< buffer to store pointer to y variables array */
74  )
75 {
76  /* variables:
77  * t[i] i=0..N-1, such that: value function=sum t[i]
78  * v[i] i=0..N-1, such that: v_i = ||(x_{i+1},y_{i+1})-(x_i,y_i)||_2
79  * y[i] i=0..N, projection of trajectory on y-axis
80  * x[i] i=0..N, projection of trajectory on x-axis
81  */
82  SCIP_VAR** t;
83  SCIP_VAR** v;
84  SCIP_VAR** x;
85  SCIP_VAR** y;
86
87  char namet[SCIP_MAXSTRLEN];
88  char namev[SCIP_MAXSTRLEN];
89  char namey[SCIP_MAXSTRLEN];
90  char namex[SCIP_MAXSTRLEN];
91
92  SCIP_Real ylb;
93  SCIP_Real yub;
94  SCIP_Real xlb;
95  SCIP_Real xub;
96
97  /* an upper bound for v */
98  SCIP_Real maxdistance = 10.0 * sqrt(SQR(coord[1]-coord[0]) + SQR(coord[3]-coord[2]));
99  unsigned int i;
100
101  /* create empty problem */
102  SCIP_CALL( SCIPcreateProbBasic(scip, "brachistochrone") );
103
104  /* allocate arrays of SCIP_VAR* */
105  SCIP_CALL( SCIPallocBufferArray(scip, &t, (size_t) n ) );
106  SCIP_CALL( SCIPallocBufferArray(scip, &v, (size_t) n ) );
107  SCIP_CALL( SCIPallocMemoryArray(scip, &y, (size_t) n + 1) );
108  SCIP_CALL( SCIPallocMemoryArray(scip, &x, (size_t) n + 1) );
109  *xvars = x;
110  *yvars = y;
111
112  /* create and add variables to the problem and set the initial and final point constraints through upper and lower
113  * bounds
114  */
115  for( i = 0; i < n+1; ++i )
116  {
117  /* setting up the names of the variables */
118  if( i < n )
119  {
120  SCIPsnprintf(namet, SCIP_MAXSTRLEN, "t(%d)", i);
121  SCIPsnprintf(namev, SCIP_MAXSTRLEN, "v(%d)", i);
122  }
123  SCIPsnprintf(namey, SCIP_MAXSTRLEN, "y(%d)", i);
124  SCIPsnprintf(namex, SCIP_MAXSTRLEN, "x(%d)", i);
125
126  /* fixing y(0), y(N), x(0), x(N) through lower and upper bounds */
127  if( i == 0 )
128  {
129  ylb = coord[0];
130  yub = coord[0];
131  xlb = coord[2];
132  xub = coord[2];
133  }
134  else if( i == n )
135  {
136  ylb = coord[1];
137  yub = coord[1];
138  xlb = coord[3];
139  xub = coord[3];
140  }
141  else
142  {
143  /* constraint the other variables to speed up solving */
144  ylb = -SCIPinfinity(scip);
145  yub = coord[0];
146  xlb = MIN(coord[2], coord[3]);
147  xub = MAX(coord[2], coord[3]);
148  }
149
150  if( i < n )
151  {
152  SCIP_CALL( SCIPcreateVarBasic(scip, &t[i], namet, 0.0, SCIPinfinity(scip), sqrt(2.0/9.80665), SCIP_VARTYPE_CONTINUOUS) );
153  SCIP_CALL( SCIPcreateVarBasic(scip, &v[i], namev, 0.0, maxdistance, 0.0, SCIP_VARTYPE_CONTINUOUS) );
154  }
155  SCIP_CALL( SCIPcreateVarBasic(scip, &y[i], namey, ylb, yub, 0.0, SCIP_VARTYPE_CONTINUOUS) );
156  SCIP_CALL( SCIPcreateVarBasic(scip, &x[i], namex, xlb, xub, 0.0, SCIP_VARTYPE_CONTINUOUS) );
157
158  if( i < n )
159  {
160  SCIP_CALL( SCIPaddVar(scip, t[i]) );
161  SCIP_CALL( SCIPaddVar(scip, v[i]) );
162  }
163  SCIP_CALL( SCIPaddVar(scip, y[i]) );
164  SCIP_CALL( SCIPaddVar(scip, x[i]) );
165  }
166
167  /* add constraints
168  *
169  * t(i) * sqrt(1 - y(i+1)) + t(i) * sqrt(1 - y(i)) >= v(i)
170  * v(i)^2 >= (y(i+1) - y(i))^2 + (x(i+1) - x(i))^2
171  * in the loop, create the i-th constraint
172  */
173  {
174  SCIP_CONS* cons;
175  char consname[SCIP_MAXSTRLEN];
176
177  /* variable expressions:
178  * yplusexpr: expression for y[i+1]
179  * yexpr: expression for y[i]
180  * texpr: expression for t[i]
181  * vexpr: expression for v[i]
182  */
183  SCIP_EXPR* yplusexpr;
184  SCIP_EXPR* yexpr;
185  SCIP_EXPR* texpr;
186  SCIP_EXPR* vexpr;
187
188  /* intermediary expressions */
189  SCIP_EXPR* expr1;
190  SCIP_EXPR* expr2;
191  SCIP_EXPR* expr3;
192  SCIP_EXPR* expr4;
193  SCIP_EXPR* expr5;
194  SCIP_EXPR* expr6;
195  SCIP_EXPR* expr7;
196
197  SCIP_Real minusone = -1.0;
198
199  for( i = 0; i < n; ++i )
200  {
201  SCIP_EXPR* exprs[3];
202  SCIP_Real coefs[3];
203  SCIP_VAR* quadvars1[7];
204  SCIP_VAR* quadvars2[7];
205  SCIP_Real quadcoefs[7];
206
207  /* create expressions for variables that are used in nonlinear constraint */
208  SCIP_CALL( SCIPcreateExprVar(scip, &yplusexpr, y[i+1], NULL, NULL) );
209  SCIP_CALL( SCIPcreateExprVar(scip, &yexpr, y[i], NULL, NULL) );
210  SCIP_CALL( SCIPcreateExprVar(scip, &texpr, t[i], NULL, NULL) );
211  SCIP_CALL( SCIPcreateExprVar(scip, &vexpr, v[i], NULL, NULL) );
212
213  /* set up the i-th constraint
214  * expr1: 1 - y[i+1]
215  * expr2: 1 - y[i]
216  * expr3: sqrt(1 - y[i+1])
217  * expr4: sqrt(1 - y[i])
218  * expr5: t[i] * sqrt(1 - y[i+1])
219  * expr6: t[i] * sqrt(1 - y[i])
220  * expr7: t[i] * sqrt(1 - y[i+1]) + t[i] * sqrt(1 - y[i]) - v[i]
221  */
222  SCIP_CALL( SCIPcreateExprSum(scip, &expr1, 1, &yplusexpr, &minusone, 1.0, NULL, NULL) );
223  SCIP_CALL( SCIPcreateExprSum(scip, &expr2, 1, &yexpr, &minusone, 1.0, NULL, NULL) );
224  SCIP_CALL( SCIPcreateExprPow(scip, &expr3, expr1, 0.5, NULL, NULL) );
225  SCIP_CALL( SCIPcreateExprPow(scip, &expr4, expr2, 0.5, NULL, NULL) );
226  exprs[0] = expr3;
227  exprs[1] = texpr;
228  SCIP_CALL( SCIPcreateExprProduct(scip, &expr5, 2, exprs, 1.0, NULL, NULL) );
229  exprs[0] = expr4;
230  SCIP_CALL( SCIPcreateExprProduct(scip, &expr6, 2, exprs, 1.0, NULL, NULL) );
231  exprs[0] = expr5; coefs[0] = 1.0;
232  exprs[1] = expr6; coefs[1] = 1.0;
233  exprs[2] = vexpr; coefs[2] = -1.0;
234  SCIP_CALL( SCIPcreateExprSum(scip, &expr7, 3, exprs, coefs, 0.0, NULL, NULL) );
235
236  /* create the constraint expr7 >= 0, add to the problem, and release it */
237  SCIPsnprintf(consname, SCIP_MAXSTRLEN, "timestep(%d)", i);
238  SCIP_CALL( SCIPcreateConsBasicNonlinear(scip, &cons, consname, expr7, 0.0, SCIPinfinity(scip)) );
239  SCIP_CALL( SCIPaddCons(scip, cons) );
240  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
241
242  /* release exprs */
243  SCIP_CALL( SCIPreleaseExpr(scip, &expr7) );
244  SCIP_CALL( SCIPreleaseExpr(scip, &expr6) );
245  SCIP_CALL( SCIPreleaseExpr(scip, &expr5) );
246  SCIP_CALL( SCIPreleaseExpr(scip, &expr4) );
247  SCIP_CALL( SCIPreleaseExpr(scip, &expr3) );
248  SCIP_CALL( SCIPreleaseExpr(scip, &expr2) );
249  SCIP_CALL( SCIPreleaseExpr(scip, &expr1) );
250
251  SCIP_CALL( SCIPreleaseExpr(scip, &vexpr) );
252  SCIP_CALL( SCIPreleaseExpr(scip, &texpr) );
253  SCIP_CALL( SCIPreleaseExpr(scip, &yexpr) );
254  SCIP_CALL( SCIPreleaseExpr(scip, &yplusexpr) );
255
256  /* create constraint v_i^2 >= (y_{i+1}^2 - 2*y_{i+1}y_i + y_i^2) + (x_{i+1}^2 - 2*x_{i+1}x_i + x_i^2)
257  * SCIP should recognize that this can be formulated as SOC
258  */
259  quadvars1[0] = y[i]; quadvars2[0] = y[i]; quadcoefs[0] = 1.0;
260  quadvars1[1] = y[i+1]; quadvars2[1] = y[i+1]; quadcoefs[1] = 1.0;
261  quadvars1[2] = x[i]; quadvars2[2] = x[i]; quadcoefs[2] = 1.0;
262  quadvars1[3] = x[i+1]; quadvars2[3] = x[i+1]; quadcoefs[3] = 1.0;
263  quadvars1[4] = y[i]; quadvars2[4] = y[i+1]; quadcoefs[4] = -2.0;
264  quadvars1[5] = x[i]; quadvars2[5] = x[i+1]; quadcoefs[5] = -2.0;
265  quadvars1[6] = v[i]; quadvars2[6] = v[i]; quadcoefs[6] = -1.0;
266
267  SCIPsnprintf(consname, SCIP_MAXSTRLEN, "steplength(%d)", i);
268  SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, &cons, consname, 0, NULL, NULL, 7, quadvars1, quadvars2, quadcoefs, -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
269
270  /* add the constraint to the problem and forget it */
271  SCIP_CALL( SCIPaddCons(scip, cons) );
272  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
273
274  /* add constraint x[i] <= x[i+1], if x[0] < x[N], otherwise add x[i+1] <= x[i] */
275  SCIPsnprintf(consname, SCIP_MAXSTRLEN, "xorder(%d)", i);
276  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(scip), 0.0) );
277  SCIP_CALL( SCIPaddCoefLinear(scip, cons, x[i], coord[2] < coord[3] ? 1.0 : -1.0) );
278  SCIP_CALL( SCIPaddCoefLinear(scip, cons, x[i+1], coord[2] < coord[3] ? -1.0 : 1.0) );
279
280  SCIP_CALL( SCIPaddCons(scip, cons) );
281  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
282  }
283  }
284
285  /* release intermediate variables */
286  for( i = 0; i < n; ++i )
287  {
288  SCIP_CALL( SCIPreleaseVar(scip, &t[i]) );
289  SCIP_CALL( SCIPreleaseVar(scip, &v[i]) );
290  }
291
292  /* free arrays allocated */
293  SCIPfreeBufferArray(scip, &t);
294  SCIPfreeBufferArray(scip, &v);
295
296  return SCIP_OKAY;
297 }
298
299 /** plots solution by use of gnuplot */
300 static
302  SCIP* scip, /**< SCIP data structure */
303  SCIP_SOL* sol, /**< solution to plot */
304  unsigned int n, /**< number of points for discretization */
305  SCIP_VAR** x, /**< x coordinates */
306  SCIP_VAR** y /**< y coordinates */
307  )
308 {
309 #if _POSIX_C_SOURCE < 2
310  SCIPinfoMessage(scip, NULL, "No POSIX version 2. Try http://distrowatch.com/.");
311 #else
312  FILE* stream;
313  unsigned int i;
314
315  /* -p (persist) to keep the plot open after gnuplot terminates (if terminal is not dumb) */
316  stream = popen("gnuplot -p", "w");
317  if( stream == NULL )
318  {
319  SCIPerrorMessage("Could not open pipe to gnuplot.\n");
320  return;
321  }
322  /* take out this line to get a non-ascii plot */
323  fputs("set terminal dumb\n", stream);
324
325  fprintf(stream, "plot '-' smooth csplines title \"Time = %.4fs\"\n", SCIPgetSolOrigObj(scip, sol));
326  for( i = 0; i < n+1; ++i )
327  fprintf(stream, "%g %g\n", SCIPgetSolVal(scip, sol, x[i]), SCIPgetSolVal(scip, sol, y[i]));
328  fputs("e\n", stream);
329
330  pclose(stream);
331 #endif
332 }
333
334 /** runs the brachistochrone example*/
335 static
337  unsigned int n, /**< number of points for discretization */
338  SCIP_Real* coord /**< array containing [y(0), y(N), x(0), x(N)] */
339  )
340 {
341  SCIP* scip;
342  SCIP_VAR** y;
343  SCIP_VAR** x;
344  unsigned int i;
345
346  assert(n >= 2);
347
348  SCIP_CALL( SCIPcreate(&scip) );
350
351  SCIPinfoMessage(scip, NULL, "\n");
352  SCIPinfoMessage(scip, NULL, "**********************************************\n");
353  SCIPinfoMessage(scip, NULL, "* Running Brachistochrone Problem *\n");
354  SCIPinfoMessage(scip, NULL, "* between A=(%g,%g) and B=(%g,%g) with %d points *\n", coord[2], coord[0], coord[3], coord[1], n);
355  SCIPinfoMessage(scip, NULL, "**********************************************\n");
356  SCIPinfoMessage(scip, NULL, "\n");
357
358  /* set gap at which SCIP will stop */
359  SCIP_CALL( SCIPsetRealParam(scip, "limits/gap", 0.05) );
360
361  SCIP_CALL( setupProblem(scip, n, coord, &x, &y) );
362
363  SCIPinfoMessage(scip, NULL, "Original problem:\n");
364  SCIP_CALL( SCIPprintOrigProblem(scip, NULL, "cip", FALSE) );
365
366  SCIPinfoMessage(scip, NULL, "\nSolving...\n");
367  SCIP_CALL( SCIPsolve(scip) );
368
369  if( SCIPgetNSols(scip) > 0 )
370  {
371  SCIPinfoMessage(scip, NULL, "\nSolution:\n");
372  SCIP_CALL( SCIPprintSol(scip, SCIPgetBestSol(scip), NULL, FALSE) );
373
374  visualizeSolutionGnuplot(scip, SCIPgetBestSol(scip), n, x, y);
375  }
376
377  /* release problem variables */
378  for( i = 0; i < n+1; ++i )
379  {
380  SCIP_CALL( SCIPreleaseVar(scip, &y[i]) );
381  SCIP_CALL( SCIPreleaseVar(scip, &x[i]) );
382  }
383
384  /* free arrays allocated */
385  SCIPfreeMemoryArray(scip, &x);
386  SCIPfreeMemoryArray(scip, &y);
387
388  SCIP_CALL( SCIPfree(&scip) );
389
390  return SCIP_OKAY;
391 }
392
393 /** main method starting SCIP */
394 int main(
395  int argc, /**< number of arguments from the shell */
396  char** argv /**< arguments: number of points and end coordinates y(N), x(N)*/
397  )
398 {
399  SCIP_RETCODE retcode;
400
401  /* setting up default problem parameters */
402  unsigned int n = 3;
403  SCIP_Real coord[4] = { Y_START, Y_END, X_START, X_END };
404
405  /* change some parameters if given as arguments */
406  if( argc == 4 || argc == 2 )
407  {
408  char *end1 = NULL;
409  char *end2 = NULL;
410  char *end3 = NULL;
411
412  n = strtol(argv[1], &end1, 10);
413  if( argc == 4 )
414  {
415  coord[1] = strtof(argv[2], &end2);
416  coord[3] = strtof(argv[3], &end3);
417  }
418
419  if( end1 == argv[1] || ( argc == 4 && ( end2 == argv[2] || end3 == argv[3] ) ) )
420  {
421  fprintf(stderr, "Error: expected real values as arguments.\n");
422  return EXIT_FAILURE;
423  }
424  }
425  else if( argc != 1 )
426  {
427  fprintf(stderr, "Usage: %s [<N> [<y(N)> <x(N)>]]\n", argv[0]);
428  return EXIT_FAILURE;
429  }
430
431  /* check that y(0) > y(N) */
432  if( coord[0] <= coord[1] )
433  {
434  fprintf(stderr, "Error: expected y(N) < 1.0\n");
435  return EXIT_FAILURE;
436  }
437
438  retcode = runBrachistochrone(n, coord);
439
440  /* evaluate return code of the SCIP process */
441  if( retcode != SCIP_OKAY )
442  {
443  /* write error back trace */
444  SCIPprintError(retcode);
445  return EXIT_FAILURE;
446  }
447
448  return EXIT_SUCCESS;
449 }
SCIP_RETCODE SCIPcreateExprPow(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_pow.c:3166
#define Y_END
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
#define SCIP_MAXSTRLEN
Definition: def.h:293
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
#define FALSE
Definition: def.h:87
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
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:185
SCIP_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_var.c:381
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
SCIP_RETCODE SCIPcreateExprSum(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefficients, SCIP_Real constant, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_sum.c:1070
SCIP_VAR ** x
Definition: circlepacking.c:54
#define X_END
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:171
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
SCIP_RETCODE SCIPcreateConsBasicNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPcreateConsQuadraticNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
SCIP_RETCODE SCIPprintOrigProblem(SCIP *scip, FILE *file, const char *extension, SCIP_Bool genericnames)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPcreateExprProduct(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real coefficient, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_RETCODE setupProblem(SCIP *scip, unsigned int n, SCIP_Real *coord, SCIP_VAR ***xvars, SCIP_VAR ***yvars)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
#define MAX(x, y)
Definition: tclique_def.h:83
#define X_START
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
static SCIP_RETCODE runBrachistochrone(unsigned int n, SCIP_Real *coord)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
#define SCIP_Real
Definition: def.h:177
int main(int argc, char **argv)
SCIP_VAR ** y
Definition: circlepacking.c:55
void SCIPprintError(SCIP_RETCODE retcode)
Definition: scip_general.c:211
#define Y_START
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
SCIP callable library.
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
static void visualizeSolutionGnuplot(SCIP *scip, SCIP_SOL *sol, unsigned int n, SCIP_VAR **x, SCIP_VAR **y)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766