SCIP Doxygen Documentation
Loading...
Searching...
No Matches
xternal_vrp.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-2023 Zuse Institute Berlin (ZIB) */
7
/* */
8
/* Licensed under the Apache License, Version 2.0 (the "License"); */
9
/* you may not use this file except in compliance with the License. */
10
/* You may obtain a copy of the License at */
11
/* */
12
/* http://www.apache.org/licenses/LICENSE-2.0 */
13
/* */
14
/* Unless required by applicable law or agreed to in writing, software */
15
/* distributed under the License is distributed on an "AS IS" BASIS, */
16
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17
/* See the License for the specific language governing permissions and */
18
/* limitations under the License. */
19
/* */
20
/* You should have received a copy of the Apache-2.0 license */
21
/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22
/* */
23
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25
/**@file xternal_vrp.c
26
* @brief main document page of VRP example
27
* @author Andreas Bley
28
*/
29
30
/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32
/**@page VRP_MAIN Vehicle Routing
33
* @version 0.1
34
* @author Andreas Bley
35
*
36
*
37
* We want to solve the vehicle routing problem (VRP) on a graph \f$G = (V,E)\f$ with \f$V = J \cup {d}\f$, where
38
* \f$d\f$ is the depot and the distances are given by the length function \f$l_e: E \to R_{\ge 0}\f$.
39
*
40
* Consider the MIP formulation
41
*
42
* \f[
43
* \begin{array}[t]{rll}
44
* \min & \displaystyle \sum_{e \in E} l_e y_e \\
45
* & & \\
46
* s.t. & -y_e + \sum_{t \in T_k} a^t_e x_t \leq 0, & \forall e \in E\\
47
* & \displaystyle \sum_{t \in T_k} a^t_j x_t = 1, & \forall j \in J \\
48
* & y(\delta(j)) = 2, & \forall j \in J \\
49
* & y_e \in \{0,1,2\}, & \forall e \in E \\
50
* & x_t \in [0,1], & \forall t \in T_k
51
* \end{array}
52
* \f]
53
*
54
* where \f$T_k\f$ is the set of tours visiting at most \f$k\f$ customers with repetitions of customers allowed and
55
* \f$a^t_e (a^t_j)\f$ counts how often edge e (node j) is traversed in \f$t \in T_k\f$. The model contains two types of
56
* variables, namely \f$ x \f$ which selects tours fractionally and \f$ y \f$ which indicates which edges of the graph
57
* are in at least one selected tour. Note that it is possible to use an edge as a forward and backward edge in a tour.
58
* This is necessary to ensure that a customer \f$ j \f$ with \f$ |\delta(j)| = 1 \f$ can be served.
59
*
60
* Since the number of tours can be exponential in the size of the graph, the algorithm starts with some subset \f$
61
* \bar{T} \subseteq T_k \f$ and adds further tours during the solution process. This way it tries to improve the
62
* current LP solution.
63
*
64
* Let \f$ \lambda_e \f$ and \f$ \gamma_i \f$ be the dual multipliers for the first and seconds constraint of the
65
* MIP and we define the costs of a tour \f$ T \in T_k \f$ as:
66
* \f[
67
* C(T) := \sum_{e \in E(T)} \lambda_e - \sum_{j \in V(T)} \gamma_j
68
* \f]
69
*
70
* The resulting pricing problem \f$ \min_{T \in T_k} C(T) \f$ can be solved with dynamic programming. The algorithm is
71
* similar to Dijkstra's shortest path algorithm if we shift the the costs \f$ \gamma_j \f$ from the nodes to the edges
72
* of \f$ G \f$.
73
*
74
* Branching decisions on the variables \f$ y \f$ modify the pricing problem only slightly. The branch \f$ y_e = 0\f$
75
* forbids \f$ e \f$ to be contained in a tour which can be easily realized if we remove \f$ e \f$ from \f$ E \f$. The
76
* branch \f$ y_e \ge 1 \f$ does not have an impact on the pricing problem.
77
*
78
* Further information about the pricing routine and the dynamic program can be found in the documentation of the
79
* corresponding files.
80
*
81
* The pricer pricer_vrp.cpp shows how to perform column generation in SCIP and how to solve the above described pricing
82
* problem which uses an implementation of a priority queue implemented in pqueue.h. In main_vrp.cpp we read the
83
* instance, create all necessary data and set up SCIP.
84
*
85
* Installation
86
* ------------
87
*
88
* See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
89
*/
examples
VRP
doc
xternal_vrp.c
© 2002-2023 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.10.0