Scippy

SCIP

Solving Constraint Integer Programs

Macros | Functions
brachistochrone.c File Reference

Detailed Description

Computing a minimum-time trajectory for a particle to move from point A to B under gravity only.

Author
Anass Meskini
Stefan Vigerske

This is an example that uses expressions to setup 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 70 of file brachistochrone.c.

◆ Y_END

#define Y_END   0.0

Definition at line 71 of file brachistochrone.c.

◆ X_START

#define X_START   0.0

Definition at line 72 of file brachistochrone.c.

◆ X_END

#define X_END   10.0

Definition at line 73 of file brachistochrone.c.

Function Documentation

◆ setupProblem()

static SCIP_RETCODE setupProblem ( SCIP *  scip,
unsigned int  n,
SCIP_Real *  coord,
SCIP_VAR ***  xvars,
SCIP_VAR ***  yvars 
)
static

sets up problem

Parameters
scipSCIP data structure
nnumber of points for discretization
coordarray containing [y(0), y(N), x(0), x(N)]
xvarsbuffer to store pointer to x variables array
yvarsbuffer to store pointer to y variables array

Definition at line 77 of file brachistochrone.c.

References FALSE, MAX, MIN, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcreateConsBasicLinear(), SCIPcreateConsBasicNonlinear(), SCIPcreateConsQuadraticNonlinear(), SCIPcreateExprPow(), SCIPcreateExprProduct(), SCIPcreateExprSum(), SCIPcreateExprVar(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPfreeBufferArray, SCIPinfinity(), SCIPreleaseCons(), SCIPreleaseExpr(), SCIPreleaseVar(), SCIPsnprintf(), SQR, TRUE, x, and y.

Referenced by runBrachistochrone().

◆ visualizeSolutionGnuplot()

static void visualizeSolutionGnuplot ( SCIP *  scip,
SCIP_SOL *  sol,
unsigned int  n,
SCIP_VAR **  x,
SCIP_VAR **  y 
)
static

plots solution by use of gnuplot

Parameters
scipSCIP data structure
solsolution to plot
nnumber of points for discretization
xx coordinates
yy coordinates

Definition at line 310 of file brachistochrone.c.

References NULL, SCIPerrorMessage, SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPinfoMessage(), x, and y.

Referenced by runBrachistochrone().

◆ runBrachistochrone()

static SCIP_RETCODE runBrachistochrone ( unsigned int  n,
SCIP_Real *  coord 
)
static

runs the brachistochrone example

Parameters
nnumber of points for discretization
coordarray containing [y(0), y(N), x(0), x(N)]

Definition at line 345 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
argcnumber of arguments from the shell
argvarguments: number of points and end coordinates y(N), x(N)

Definition at line 403 of file brachistochrone.c.

References NULL, runBrachistochrone(), SCIP_OKAY, SCIP_Real, SCIPprintError(), X_END, X_START, Y_END, and Y_START.