# SCIP

Solving Constraint Integer Programs

brachistochrone.c File Reference

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

## ◆ 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().

## ◆ 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.

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(), and SCIPinfoMessage().

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.

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.