Scippy

SCIP

Solving Constraint Integer Programs

cppmain.cpp
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-2019 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 visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file examples/TSP/src/cppmain.cpp
17  * @brief main file for C++ TSP example using SCIP as a callable library
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  *
21  * This is an example of using SCIP to solve the TSP problem on undirected graphs.
22  * Here is the CIP model that we use:
23  *
24  * Given: a graph G=(V,E) with edge weights c_e
25  * Task: find hamiltonian cycle T subseteq E in G with minimal length c(T)
26  *
27  * Variables: x_e in {0,1} for all e in E, x_e = 1 <=> e in T
28  * Constraints:
29  * 1. sum_{e in delta(v)} x_e == 2 for all v in V
30  * 2. subtour(G,x)
31  *
32  * Semantics of constraints:
33  * 1. usual linear constraints
34  * 2. subtour(G,x) <=> T defined by x does not contain any cycle of length < |V|
35  *
36  * A few remarks to the model and the implementation (references to code lines might
37  * not be up to date):
38  *
39  * As one can see, the TSP-Model consists of |V| linear constraints (the
40  * degree constraints) and one "subtour" constraint. The latter is a
41  * complex, non-linear constraint for which one has to implement an own
42  * constraint handler.
43  * The variables are created in the TSP file reader ReaderTsp.cpp at line
44  * 311. A pointer to each variable is stored in the data structure of the
45  * corresponding edge (i.e., in edge->var and edge->back->var, since the
46  * formally undirected graph is represented as a directed graph with
47  * antiparallel arcs).
48  * The degree constraints are created at line 330. The data for the
49  * linear degree constraints are the coefficients (for each e in
50  * delta(v) the variable x_e has coefficient 1.0) which are generated at
51  * line 337, and the left and right hand sides of the inequality, which
52  * are both set to 2.0 at line 330, such that the linear constraint
53  * becomes an equation.
54  * The subtour constraint is created at line 349. The data for this
55  * constraint is the graph and the variables (see above), but we only have
56  * to store a pointer to the graph because the edges already have links to
57  * their respective variables.
58  *
59  * Now the problem instance is defined, and the "only" thing left is to
60  * implement the semantics of the "subtour" constraint. This is of
61  * course done in the subtour constraint handler ConshdlrSubtour.cpp. The
62  * main task of a constraint handler is to decide whether a given
63  * solution is feasible for all constraints of the constraint handler's
64  * type (i.e., for example, for all linear constraint in the instance,
65  * for all knapsack constraints in the instance, for all subtour
66  * constraints in the instance, ...). This is performed in the
67  * scip_enfolp(), scip_enfops(), and scip_check() methods. To implement
68  * these three methods and the scip_lock() method (called the
69  * "fundamental callback methods" in the SCIP documentation) is already
70  * enough to obtain a correct algorithm, which means that the solver will
71  * find (after waiting long enough) the optimal solution. The remaining
72  * methods are only needed to speed up the solving process (for example,
73  * cutting plane separation and domain propagation).
74  *
75  * As there is only one subtour constraint in a TSP instance, all the
76  * loops "for( int i = 0; i < nconss; ++i )" in ConshdlrSubtour.cpp are a
77  * bit ridiculous, since nconss will always be equal to one. However,
78  * nothing prevents a user from using the subtour constraint handler in a
79  * different application where you have more than one graph and a
80  * solution must not contain any subtour in each of the graphs.
81  */
82 
83 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
84 
85 #include <iostream>
86 
87 /* include SCIP components */
88 #include "objscip/objscip.h"
90 
91 /* include TSP specific components */
92 #include "ReaderTSP.h"
93 #include "ConshdlrSubtour.h"
94 #include "HeurFarthestInsert.h"
95 #include "Heur2opt.h"
96 #include "HeurFrats.h"
97 #include "EventhdlrNewSol.h"
98 
99 using namespace scip;
100 using namespace tsp;
101 using namespace std;
102 
103 /** creates and runs a SCIP instance with default and TSP plugins */
104 static
106  int argc, /**< number of arguments from the shell */
107  char** argv /**< array of shell arguments */
108  )
109 {
110  SCIP* scip = NULL;
111 
112 
113  /*********
114  * Setup *
115  *********/
116 
117  /* initialize SCIP */
118  SCIP_CALL( SCIPcreate(&scip) );
119 
120  /* we explicitly enable the use of a debug solution for this main SCIP instance */
121  SCIPenableDebugSol(scip);
122 
123  /* include TSP specific plugins */
124  SCIP_CALL( SCIPincludeObjReader(scip, new ReaderTSP(scip), TRUE) );
128  SCIP_CALL( SCIPincludeObjHeur(scip, new Heur2opt(scip), TRUE) );
129  SCIP_CALL( SCIPincludeObjHeur(scip, new HeurFrats(scip), TRUE) );
130 
131  /* include default SCIP plugins */
133 
134 
135  /**********************************
136  * Process command line arguments *
137  **********************************/
138 
139  SCIP_CALL( SCIPprocessShellArguments(scip, argc, argv, "sciptsp.set") );
140 
141 
142  /********************
143  * Deinitialization *
144  ********************/
145 
146  SCIP_CALL( SCIPfree(&scip) );
147 
149 
150  return SCIP_OKAY;
151 }
152 
153 /** main method starting TSP code */
154 int main(
155  int argc, /**< number of arguments from the shell */
156  char** argv /**< array of shell arguments */
157  )
158 {
159  SCIP_RETCODE retcode;
160 
161  retcode = runSCIP(argc, argv);
162  if( retcode != SCIP_OKAY )
163  {
164  SCIPprintError(retcode);
165  return -1;
166  }
167 
168  return 0;
169 }
#define NULL
Definition: def.h:246
#define BMScheckEmptyMemory()
Definition: memory.h:144
SCIP_RETCODE SCIPincludeObjEventhdlr(SCIP *scip, scip::ObjEventhdlr *objeventhdlr, SCIP_Bool deleteobject)
2-Optimum - combinatorial improvement heuristic for TSP
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:338
farthest insert - combinatorial heuristic for TSP
SCIP_RETCODE SCIPincludeObjHeur(SCIP *scip, scip::ObjHeur *objheur, SCIP_Bool deleteobject)
Definition: objheur.cpp:195
C++ wrapper for default SCIP plugins.
SCIP_RETCODE SCIPincludeObjConshdlr(SCIP *scip, scip::ObjConshdlr *objconshdlr, SCIP_Bool deleteobject)
Definition: pqueue.h:28
C++ wrapper classes for SCIP.
#define SCIP_CALL(x)
Definition: def.h:358
event handler for new solutions in TSP
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
C++ constraint handler for TSP subtour elimination constraints.
SCIP_RETCODE SCIPincludeObjReader(SCIP *scip, scip::ObjReader *objreader, SCIP_Bool deleteobject)
Definition: objreader.cpp:146
SCIP_RETCODE SCIPprocessShellArguments(SCIP *scip, int argc, char **argv, const char *defaultsetname)
Definition: scipshell.c:147
fractional travelling salesman heuristic - Rounding heuristic for TSP
C++ file reader for TSP data files.
int main(int argc, char **argv)
Definition: cppmain.cpp:29
void SCIPprintError(SCIP_RETCODE retcode)
Definition: scip_general.c:266
static SCIP_RETCODE runSCIP(int argc, char **argv)
Definition: cppmain.cpp:105
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:370
void SCIPenableDebugSol(SCIP *scip)
Definition: scip_debug.c:132