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-2025 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 */