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-2024 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
*/
examples
TSP
doc
xternal_tsp.c
© 2002-2024 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.11.0