SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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.

Referenced by main().

◆ Y_END

#define Y_END   0.0

Definition at line 71 of file brachistochrone.c.

Referenced by main().

◆ X_START

#define X_START   0.0

Definition at line 72 of file brachistochrone.c.

Referenced by main().

◆ X_END

#define X_END   10.0

Definition at line 73 of file brachistochrone.c.

Referenced by main().

Function Documentation

◆ setupProblem()

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

◆ 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 i, NULL, SCIPerrorMessage, SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPinfoMessage(), sol, 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 assert(), FALSE, i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, 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.