Scippy

SCIP

Solving Constraint Integer Programs

xternal.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file xternal.c
17  * @brief main document page of VRP example
18  * @author Andreas Bley
19  */
20 
21 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 /**@mainpage Overview
24  * @version 0.1
25  * @author Andreas Bley
26  *
27  *
28  * We want to solve the vehicle routing problem (VRP) on a graph \f$G = (V,E)\f$ with
29  * \f$V = J \cup {d}\f$, where \f$d\f$ is the depot and the distances are given by the
30  * length function \f$l_e: E \to R_{\ge 0}\f$.
31  *
32  * Consider the MIP formulation
33  *
34  * \f[
35  * \begin{array}[t]{rll}
36  * \min & \displaystyle \sum_{e \in E} l_e y_e \\
37  * & & \\
38  * s.t. & -y_e + \sum_{t \in T_k} a^t_e x_t \leq 0, & \forall e \in E\\
39  * & \displaystyle \sum_{t \in T_k} a^t_j x_t = 1, & \forall j \in J \\
40  * & y(\delta(j)) = 2, & \forall j \in J \\
41  * & y_e \in \{0,1,2\}, & \forall e \in E \\
42  * & x_t \in [0,1], & \forall t \in T_k
43  * \end{array}
44  * \f]
45  *
46  * where \f$T_k\f$ is the set of tours visiting at most \f$k\f$ customers
47  * with repetitions of customers allowed and \f$a^t_e (a^t_j)\f$ counts how often
48  * edge e (node j) is traversed in \f$t \in T_k\f$.
49  */
50