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