Scippy

    SCIP

    Solving Constraint Integer Programs

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