Scippy

    SCIP

    Solving Constraint Integer Programs

    xternal_tsp.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_tsp.c
    26 * @brief main document page
    27 * @author Timo Berthold
    28 */
    29
    30/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    31
    32/**@page TSP_MAIN Traveling Salesman Problem
    33 * @version 0.9
    34 * @author Timo Berthold
    35
    36 * This is an example of using SCIP to solve the TSP problem on undirected graphs.
    37 * Here is the CIP model that we use:
    38 *
    39 * Given: a graph \f$ G=(V,E) \f$ with edge weights \f$ c_e \f$
    40 * Task: find hamiltonian cycle \f$ T \f$ in \f$ G \f$ with minimal length \f$ c(T) \f$
    41 *
    42 * Variables: \f$ x_e \in \{0,1\} \, \forall e \in E, x_e = 1 \Leftrightarrow e \in T \f$
    43 *
    44 * Constraints:
    45 * -# \f$\sum_{e \in \delta(v)} x_e = 2 \, \forall v \in V \qquad \qquad \f$
    46 * -# subtour\f$(G,x) \f$
    47 *
    48 * Semantics of constraints:
    49 * -# usual linear constraints
    50 * -# subtour\f$(G,x)\Leftrightarrow\f$ \f$ T \f$ defined by \f$ x \f$ does not contain
    51 * any cycle of length \f$ < |V| \f$.
    52 *
    53 * A few remarks to the model and the implementation (references to code lines might
    54 * not be up to date):
    55 *
    56 * As one can see, the TSP-Model consists of \f$ |V| \f$ linear constraints (the
    57 * degree constraints) and one "subtour" constraint. The latter is a
    58 * complex, non-linear constraint for which one has to implement an own
    59 * constraint handler.
    60 * The variables are created in the TSP file reader ReaderTSP.cpp:
    61 *
    62 * @refsnippet{examples/TSP/src/ReaderTSP.cpp,SnippetTSPVariableCreation}
    63 *
    64 * A pointer to each variable is stored in the data structure of the
    65 * corresponding edge (i.e., in <code>edge->var</code> and <code>edge->back->var</code>,
    66 * since the formally undirected graph is represented as a directed graph with
    67 * antiparallel arcs).
    68 * After that, the degree constraints are created:
    69 *
    70 * @refsnippet{examples/TSP/src/ReaderTSP.cpp,SnippetTSPDegreeConstraintCreation}
    71 *
    72 * The data for the
    73 * linear degree constraints are the coefficients (for each \f$e \in
    74 * \delta(v)\f$ the variable \f$ x_e \f$ has coefficient 1.0) which are generated at
    75 * line 437, and the left and right hand sides of the inequality, which
    76 * are both set to 2.0 at line 430, such that the linear constraint
    77 * becomes an equation.
    78 * The subtour constraint is created at line 449. The data for this
    79 * constraint is the graph and the variables (see above), but we only have
    80 * to store a pointer to the graph because the edges already have links to
    81 * their respective variables.
    82 *
    83 * Now the problem instance is defined, and the "only" thing left is to
    84 * implement the semantics of the "subtour" constraint. This is of
    85 * course done in the subtour constraint handler ConshdlrSubtour.cpp. The
    86 * main task of a constraint handler is to decide whether a given
    87 * solution is feasible for all constraints of the constraint handler's
    88 * type (i.e., for example, for all linear constraint in the instance,
    89 * for all knapsack constraints in the instance, for all subtour
    90 * constraints in the instance, ...). This is performed in the
    91 * scip_enfolp(), scip_enfops(), and scip_check() methods. To implement
    92 * these three methods and the scip_lock() method (called the
    93 * "fundamental callback methods" in the SCIP documentation) is already
    94 * enough to obtain a correct algorithm, which means that the solver will
    95 * find (after waiting long enough) the optimal solution. The remaining
    96 * methods are only needed to speed up the solving process (for example,
    97 * cutting plane separation and domain propagation).
    98 *
    99 * @refsnippet{examples/TSP/src/ReaderTSP.cpp,SnippetTSPNosubtourConstraintCreation}
    100 *
    101 * As there is only one subtour constraint in a TSP instance, all the
    102 * loops
    103 * \code
    104 * for( int i = 0; i < nconss; ++i )
    105 * ...
    106 * \endcode in ConshdlrSubtour.cpp are a
    107 * bit ridiculous, since <code>nconss</code> will always be equal to one. However,
    108 * nothing prevents a user from using the subtour constraint handler in a
    109 * different application where you have more than one graph and a
    110 * solution must not contain any subtour in each of the graphs.
    111 *
    112 * Additionally, this example contains two well known combinatorial heuristics for the TSP,
    113 * namely a \ref HeurFarthestInsert.cpp "farthest insert heuristic" and a \ref Heur2opt.cpp "2-opt heuristic",
    114 * and a \ref HeurFrats.cpp "rounding heuristic" for TSPs.
    115 * The idea of the latter one is to take an LP solution and construct a hamiltonian cycle in the following way:
    116 * If \f$ x_e \f$ is equal to one, add edge \f$ e \f$ to the cycle.
    117 * Iterate over the remaining variables in nonincreasing order of their LP value \f$ x_e \f$ and add
    118 * the corresponding edge \f$ e \f$ ,
    119 * if it does not close a subtour.
    120 *
    121 * Installation
    122 * ------------
    123 *
    124 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
    125 */