Scippy

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-2019 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 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 and expression trees to set up 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://scip.zib.de/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  /* child expressions:
178  * yplusexpr: expression for y[i+1]
179  * yexpr: expression for y[i]
180  * texpr, texpr2: expression for t[i]
181  */
182  SCIP_EXPR* yplusexpr;
183  SCIP_EXPR* yexpr;
184  SCIP_EXPR* texpr;
185  SCIP_EXPR* texpr2;
186 
187  /* intermediary expressions */
188  SCIP_EXPR* expr1;
189  SCIP_EXPR* expr2;
190  SCIP_EXPR* expr3;
191  SCIP_EXPR* expr4;
192  SCIP_EXPR* expr5;
193  SCIP_EXPR* expr6;
194 
195  /* trees to hold the non-linear parts of the constraint */
196  SCIP_EXPRTREE* exprtree[2];
197 
198  SCIP_Real minusone = -1.0;
199 
200  /* at each iteration create an expression for the non-linear part of the i-th constraint and add it the problem */
201  for( i = 0; i < n; ++i )
202  {
203  /* vars to be added to the exprtree in this step of the loop */
204  SCIP_VAR* varstoadd[3] = { y[i+1], y[i], t[i] };
205 
206  /* create expressions meant to be child expressions in the tree. give different indexes to the expressions to
207  * assign the correct variables to them later
208  */
209  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &yplusexpr, SCIP_EXPR_VARIDX, 0) );
210  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &yexpr, SCIP_EXPR_VARIDX, 1) );
211  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &texpr, SCIP_EXPR_VARIDX, 2) );
212  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &texpr2, SCIP_EXPR_VARIDX, 2) );
213 
214  /* set up the i-th constraint
215  * expr1: 1 - y[i+1]
216  * expr2: 1 - y[i]
217  * expr3: sqrt(1 - y[i+1])
218  * expr4: sqrt(1 - y[i])
219  * expr5: t[i] * sqrt(1 - y[i+1])
220  * expr6: t[i] * sqrt(1 - y[i])
221  */
222  SCIP_CALL( SCIPexprCreateLinear(SCIPblkmem(scip), &expr1, 1, &yplusexpr, &minusone, 1.0) );
223  SCIP_CALL( SCIPexprCreateLinear(SCIPblkmem(scip), &expr2, 1, &yexpr, &minusone, 1.0) );
224  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr3, SCIP_EXPR_SQRT, expr1) );
225  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr4, SCIP_EXPR_SQRT, expr2) );
226  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr5, SCIP_EXPR_MUL, expr3, texpr) );
227  SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr6, SCIP_EXPR_MUL, expr4, texpr2) );
228 
229  /* create the expression trees with expr5 and expr6 as root */
230  SCIP_CALL( SCIPexprtreeCreate(SCIPblkmem(scip), &exprtree[0], expr5, 3, 0, NULL) );
231  SCIP_CALL( SCIPexprtreeCreate(SCIPblkmem(scip), &exprtree[1], expr6, 3, 0, NULL) );
232  SCIP_CALL( SCIPexprtreeSetVars(exprtree[0], 3, varstoadd) );
233  SCIP_CALL( SCIPexprtreeSetVars(exprtree[1], 3, varstoadd) );
234 
235  /* use the tree and a linear term to add the constraint exprtree0 + exprtree1 - v_i >= 0 */
236  SCIPsnprintf(consname, SCIP_MAXSTRLEN, "timestep(%d)", i);
237  SCIP_CALL( SCIPcreateConsBasicNonlinear(scip, &cons, consname, 1, &v[i],
238  &minusone, 2, exprtree, NULL, 0.0, SCIPinfinity(scip)) );
239 
240  /* add the constraint to the problem, release the constraint and free the trees */
241  SCIP_CALL( SCIPaddCons(scip, cons) );
242  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
243  SCIP_CALL( SCIPexprtreeFree(&exprtree[0]) );
244  SCIP_CALL( SCIPexprtreeFree(&exprtree[1]) );
245 
246  /* add 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)
247  * SCIP should recognize that this can be formulated as SOC and do this reformulation
248  */
249  SCIPsnprintf(consname, SCIP_MAXSTRLEN, "steplength(%d)", i);
250  SCIP_CALL( SCIPcreateConsBasicQuadratic(scip, &cons, consname, 0, NULL, NULL, 0, NULL, NULL, NULL, -SCIPinfinity(scip), 0.0) );
251  SCIP_CALL( SCIPaddSquareCoefQuadratic(scip, cons, y[i], 1.0) );
252  SCIP_CALL( SCIPaddSquareCoefQuadratic(scip, cons, y[i+1], 1.0) );
253  SCIP_CALL( SCIPaddSquareCoefQuadratic(scip, cons, x[i], 1.0) );
254  SCIP_CALL( SCIPaddSquareCoefQuadratic(scip, cons, x[i+1], 1.0) );
255  SCIP_CALL( SCIPaddBilinTermQuadratic(scip, cons, y[i], y[i+1], -2.0) );
256  SCIP_CALL( SCIPaddBilinTermQuadratic(scip, cons, x[i], x[i+1], -2.0) );
257  SCIP_CALL( SCIPaddSquareCoefQuadratic(scip, cons, v[i], -1.0) );
258 
259  /* add the constraint to the problem and forget it */
260  SCIP_CALL( SCIPaddCons(scip, cons) );
261  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
262 
263  /* add constraint x[i] <= x[i+1], if x[0] < x[N], otherwise add x[i+1] <= x[i] */
264  SCIPsnprintf(consname, SCIP_MAXSTRLEN, "xorder(%d)", i);
265  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(scip), 0.0) );
266  SCIP_CALL( SCIPaddCoefLinear(scip, cons, x[i], coord[2] < coord[3] ? 1.0 : -1.0) );
267  SCIP_CALL( SCIPaddCoefLinear(scip, cons, x[i+1], coord[2] < coord[3] ? -1.0 : 1.0) );
268 
269  SCIP_CALL( SCIPaddCons(scip, cons) );
270  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
271  }
272  }
273 
274  /* release intermediate variables */
275  for( i = 0; i < n; ++i )
276  {
277  SCIP_CALL( SCIPreleaseVar(scip, &t[i]) );
278  SCIP_CALL( SCIPreleaseVar(scip, &v[i]) );
279  }
280 
281  /* free arrays allocated */
282  SCIPfreeBufferArray(scip, &t);
283  SCIPfreeBufferArray(scip, &v);
284 
285  return SCIP_OKAY;
286 }
287 
288 /** plots solution by use of gnuplot */
289 static
291  SCIP* scip, /**< SCIP data structure */
292  SCIP_SOL* sol, /**< solution to plot */
293  unsigned int n, /**< number of points for discretization */
294  SCIP_VAR** x, /**< x coordinates */
295  SCIP_VAR** y /**< y coordinates */
296  )
297 {
298 #if _POSIX_C_SOURCE < 2
299  SCIPinfoMessage(scip, NULL, "No POSIX version 2. Try http://distrowatch.com/.");
300 #else
301  FILE* stream;
302  unsigned int i;
303 
304  /* -p (persist) to keep the plot open after gnuplot terminates (if terminal is not dumb) */
305  stream = popen("gnuplot -p", "w");
306  if( stream == NULL )
307  {
308  SCIPerrorMessage("Could not open pipe to gnuplot.\n");
309  return;
310  }
311  /* take out this line to get a non-ascii plot */
312  fputs("set terminal dumb\n", stream);
313 
314  fprintf(stream, "plot '-' smooth csplines title \"Time = %.4fs\"\n", SCIPgetSolOrigObj(scip, sol));
315  for( i = 0; i < n+1; ++i )
316  fprintf(stream, "%g %g\n", SCIPgetSolVal(scip, sol, x[i]), SCIPgetSolVal(scip, sol, y[i]));
317  fputs("e\n", stream);
318 
319  pclose(stream);
320 #endif
321 }
322 
323 /** runs the brachistochrone example*/
324 static
326  unsigned int n, /**< number of points for discretization */
327  SCIP_Real* coord /**< array containing [y(0), y(N), x(0), x(N)] */
328  )
329 {
330  SCIP* scip;
331  SCIP_VAR** y;
332  SCIP_VAR** x;
333  unsigned int i;
334 
335  assert(n >= 2);
336 
337  SCIP_CALL( SCIPcreate(&scip) );
339 
340  SCIPinfoMessage(scip, NULL, "\n");
341  SCIPinfoMessage(scip, NULL, "**********************************************\n");
342  SCIPinfoMessage(scip, NULL, "* Running Brachistochrone Problem *\n");
343  SCIPinfoMessage(scip, NULL, "* between A=(%g,%g) and B=(%g,%g) with %d points *\n", coord[2], coord[0], coord[3], coord[1], n);
344  SCIPinfoMessage(scip, NULL, "**********************************************\n");
345  SCIPinfoMessage(scip, NULL, "\n");
346 
347  /* set gap at which SCIP will stop */
348  SCIP_CALL( SCIPsetRealParam(scip, "limits/gap", 0.05) );
349 
350  SCIP_CALL( setupProblem(scip, n, coord, &x, &y) );
351 
352  SCIPinfoMessage(scip, NULL, "Original problem:\n");
353  SCIP_CALL( SCIPprintOrigProblem(scip, NULL, "cip", FALSE) );
354 
355  SCIPinfoMessage(scip, NULL, "\nSolving...\n");
356  SCIP_CALL( SCIPsolve(scip) );
357 
358  if( SCIPgetNSols(scip) > 0 )
359  {
360  SCIPinfoMessage(scip, NULL, "\nSolution:\n");
361  SCIP_CALL( SCIPprintSol(scip, SCIPgetBestSol(scip), NULL, FALSE) );
362 
363  visualizeSolutionGnuplot(scip, SCIPgetBestSol(scip), n, x, y);
364  }
365 
366  /* release problem variables */
367  for( i = 0; i < n+1; ++i )
368  {
369  SCIP_CALL( SCIPreleaseVar(scip, &y[i]) );
370  SCIP_CALL( SCIPreleaseVar(scip, &x[i]) );
371  }
372 
373  /* free arrays allocated */
374  SCIPfreeMemoryArray(scip, &x);
375  SCIPfreeMemoryArray(scip, &y);
376 
377  SCIP_CALL( SCIPfree(&scip) );
378 
379  return SCIP_OKAY;
380 }
381 
382 /** main method starting SCIP */
383 int main(
384  int argc, /**< number of arguments from the shell */
385  char** argv /**< arguments: number of points and end coordinates y(N), x(N)*/
386  )
387 {
388  SCIP_RETCODE retcode;
389 
390  /* setting up default problem parameters */
391  unsigned int n = 3;
392  SCIP_Real coord[4] = { Y_START, Y_END, X_START, X_END };
393 
394  /* change some parameters if given as arguments */
395  if( argc == 4 || argc == 2 )
396  {
397  char *end1 = NULL;
398  char *end2 = NULL;
399  char *end3 = NULL;
400 
401  n = strtol(argv[1], &end1, 10);
402  if( argc == 4 )
403  {
404  coord[1] = strtof(argv[2], &end2);
405  coord[3] = strtof(argv[3], &end3);
406  }
407 
408  if( end1 == argv[1] || ( argc == 4 && ( end2 == argv[2] || end3 == argv[3] ) ) )
409  {
410  fprintf(stderr, "Error: expected real values as arguments.\n");
411  return EXIT_FAILURE;
412  }
413  }
414  else if( argc != 1 )
415  {
416  fprintf(stderr, "Usage: %s [<N> [<y(N)> <x(N)>]]\n", argv[0]);
417  return EXIT_FAILURE;
418  }
419 
420  /* check that y(0) > y(N) */
421  if( coord[0] <= coord[1] )
422  {
423  fprintf(stderr, "Error: expected y(N) < 1.0\n");
424  return EXIT_FAILURE;
425  }
426 
427  retcode = runBrachistochrone(n, coord);
428 
429  /* evaluate return code of the SCIP process */
430  if( retcode != SCIP_OKAY )
431  {
432  /* write error back trace */
433  SCIPprintError(retcode);
434  return EXIT_FAILURE;
435  }
436 
437  return EXIT_SUCCESS;
438 }
#define NULL
Definition: def.h:246
#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)
SCIP_RETCODE SCIPaddSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:88
#define SCIP_MAXSTRLEN
Definition: def.h:267
#define SQR(x)
Definition: def.h:198
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:72
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
#define FALSE
Definition: def.h:72
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
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 SCIPexprtreeSetVars(SCIP_EXPRTREE *tree, int nvars, SCIP_VAR **vars)
Definition: nlp.c:112
SCIP_RETCODE SCIPexprtreeCreate(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **tree, SCIP_EXPR *root, int nvars, int nparams, SCIP_Real *params)
Definition: expr.c:8771
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:338
SCIP_RETCODE SCIPcreateConsBasicQuadratic(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_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:694
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:279
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:223
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2577
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIPInterval sqrt(const SCIPInterval &x)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
SCIP_RETCODE SCIPprintOrigProblem(SCIP *scip, FILE *file, const char *extension, SCIP_Bool genericnames)
#define SCIP_CALL(x)
Definition: def.h:358
static SCIP_RETCODE setupProblem(SCIP *scip, unsigned int n, SCIP_Real *coord, SCIP_VAR ***xvars, SCIP_VAR ***yvars)
SCIP_RETCODE SCIPaddBilinTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
public data structures and miscellaneous methods
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
#define MIN(x, y)
Definition: def.h:216
SCIP_RETCODE SCIPexprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op,...)
Definition: expr.c:5973
SCIP_RETCODE SCIPexprtreeFree(SCIP_EXPRTREE **tree)
Definition: expr.c:8852
#define X_START
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2263
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1493
static SCIP_RETCODE runBrachistochrone(unsigned int n, SCIP_Real *coord)
#define MAX(x, y)
Definition: def.h:215
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2362
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
#define SCIP_Real
Definition: def.h:157
int main(int argc, char **argv)
SCIP_VAR ** y
Definition: circlepacking.c:55
void SCIPprintError(SCIP_RETCODE retcode)
Definition: scip_general.c:266
SCIP_RETCODE SCIPexprCreateLinear(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefs, SCIP_Real constant)
Definition: expr.c:6502
#define Y_START
SCIP_RETCODE SCIPcreateConsBasicNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *nonlincoefs, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
default SCIP plugins
SCIP callable library.
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:370
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:1824