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