SCIP
Solving Constraint Integer Programs
Detailed Description
Computing a minimum-time trajectory for a particle to move from point A to B under gravity only.
This is an example that uses expressions and expression trees to set up non-linear constraints in SCIP when used as a callable library. This example implements a discretized model to obtain the trajectory associated with the shortest time to go from point A to B for a particle under gravity only.
The model:
Given \(N\) number of points for the discretisation of the trajectory, we can approximate the time to go from \((x_0,y_0)\) to \( (x_N,y_N)\) for a given trajectory by
\[T = \sqrt{\frac{2}{g}} \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}}.\]
We seek to minimize \(T\). A more detailed description of the model can be found in the brachistochrone directory of http://scipopt.org/workshop2018/pyscipopt-exercises.tgz
Passing this equation as it is to SCIP does not lead to satisfying results, though, so we reformulate a bit. Let \(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}}\). To avoid a potential division by zero, we rewrite this as \(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\). Further, introduce \(v_i \geq 0\) such that \(v_i \geq \sqrt{(y_{i+1} - y_i)^2 + (x_{i+1} - x_i)^2}\). Then we can state the optimization problem as
\begin{align} \min \;& \sqrt{\frac{2}{g}} \sum_{i=0}^{N-1} t_i \\ \text{s.t.} \; & t_i (\sqrt{1-y_{i+1}} + \sqrt{1 - y_i}) \geq v_i \\ & v_i^2 \geq (y_{i+1} - y_i)^2 + (x_{i+1} - x_i)^2 \\ & t_i \geq 0,\; v_i \geq 0 \\ & i = 0, \ldots, N-1 \end{align}
Further, we can require that the particle moves only in direction horizontally, that is \(x_i \leq x_{i+1}\) if \(x_0 \leq x_N\), and \(x_{i+1} \leq x_{i}\), otherwise, and that it will not move higher than the start-coordinate.
Definition in file brachistochrone.c.
#include <stdio.h>#include <stdlib.h>#include "scip/pub_misc.h"#include "scip/scip.h"#include "scip/scipdefplugins.h"Go to the source code of this file.
Macros | |
| #define | Y_START 1.0 |
| #define | Y_END 0.0 |
| #define | X_START 0.0 |
| #define | X_END 10.0 |
Functions | |
| static SCIP_RETCODE | setupProblem (SCIP *scip, unsigned int n, SCIP_Real *coord, SCIP_VAR ***xvars, SCIP_VAR ***yvars) |
| static void | visualizeSolutionGnuplot (SCIP *scip, SCIP_SOL *sol, unsigned int n, SCIP_VAR **x, SCIP_VAR **y) |
| static SCIP_RETCODE | runBrachistochrone (unsigned int n, SCIP_Real *coord) |
| int | main (int argc, char **argv) |
Macro Definition Documentation
◆ Y_START
| #define Y_START 1.0 |
Definition at line 61 of file brachistochrone.c.
Referenced by main().
◆ Y_END
| #define Y_END 0.0 |
Definition at line 62 of file brachistochrone.c.
Referenced by main().
◆ X_START
| #define X_START 0.0 |
Definition at line 63 of file brachistochrone.c.
Referenced by main().
◆ X_END
| #define X_END 10.0 |
Definition at line 64 of file brachistochrone.c.
Referenced by main().
Function Documentation
◆ setupProblem()
|
static |
sets up problem
- Parameters
-
scip SCIP data structure n number of points for discretization coord array containing [y(0), y(N), x(0), x(N)] xvars buffer to store pointer to x variables array yvars buffer to store pointer to y variables array
Definition at line 68 of file brachistochrone.c.
References MAX, NULL, SCIP_CALL, SCIP_EXPR_MUL, SCIP_EXPR_SQRT, SCIP_EXPR_VARIDX, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddBilinTermQuadratic(), SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddSquareCoefQuadratic(), SCIPaddVar(), SCIPallocBufferArray, SCIPallocMemoryArray, SCIPblkmem(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicNonlinear(), SCIPcreateConsBasicQuadratic(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPexprCreate(), SCIPexprCreateLinear(), SCIPexprtreeCreate(), SCIPexprtreeFree(), SCIPexprtreeSetVars(), SCIPfreeBufferArray, SCIPinfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), sqrt(), x, and y.
Referenced by runBrachistochrone().
◆ visualizeSolutionGnuplot()
|
static |
plots solution by use of gnuplot
- Parameters
-
scip SCIP data structure sol solution to plot n number of points for discretization x x coordinates y y coordinates
Definition at line 290 of file brachistochrone.c.
References NULL, SCIPerrorMessage, SCIPgetSolOrigObj(), SCIPgetSolVal(), and SCIPinfoMessage().
Referenced by runBrachistochrone().
◆ runBrachistochrone()
|
static |
runs the brachistochrone example
- Parameters
-
n number of points for discretization coord array containing [y(0), y(N), x(0), x(N)]
Definition at line 325 of file brachistochrone.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreate(), SCIPfree(), SCIPfreeMemoryArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPincludeDefaultPlugins(), SCIPinfoMessage(), SCIPprintOrigProblem(), SCIPprintSol(), SCIPreleaseVar(), SCIPsetRealParam(), SCIPsolve(), setupProblem(), visualizeSolutionGnuplot(), x, and y.
Referenced by main().
◆ main()
| int main | ( | int | argc, |
| char ** | argv | ||
| ) |
main method starting SCIP
- Parameters
-
argc number of arguments from the shell argv arguments: number of points and end coordinates y(N), x(N)
Definition at line 383 of file brachistochrone.c.
References NULL, runBrachistochrone(), SCIP_OKAY, SCIP_Real, SCIPprintError(), X_END, X_START, Y_END, and Y_START.