Toggle navigation
SCIP Optimization Suite
SCIP
SoPlex
ZIMPL
UG
GCG
Documentation
SCIP 9.0.0
SCIP 8.1.0
SCIP 7.0.3
SCIP 6.0.2
SCIP 5.0.1
SCIP 4.0.1
SCIP 3.2.1
SCIP
Solving Constraint Integer Programs
Main Page
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Typedefs
Pages
scip-repo
examples
VRP
doc
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