SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-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_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 */