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

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 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

scip	SCIP data structure
sol	solution to plot
n	number of points for discretization
x	x coordinates
y	y 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

n	number of points for discretization
coord	array 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

argc	number of arguments from the shell
argv	arguments: 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.