Scippy

SCIP

Solving Constraint Integer Programs

ProbDataTSP.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 ProbDataTSP.cpp
17  * @brief C++ problem data for TSP
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "objscip/objscip.h"
24 #include "ProbDataTSP.h"
25 #include "GomoryHuTree.h"
26 
27 using namespace tsp;
28 using namespace scip;
29 
30 /** copies given graph */
31 static
33  GRAPH** graph, /**< pointer to store the copied graph */
34  GRAPH* sourcegraph /**< graph to be copied */
35  )
36 {
37  assert( graph != NULL );
38  assert( sourcegraph != NULL );
39 
40  // copy graph the way it is created in the file reader
41  int n = sourcegraph->nnodes;
42  int m = sourcegraph->nedges;
43 
44  // create_graphs allocates memory for 2 anti-parallel arcs for each edge
45  if(!create_graph(n, 2*m, graph))
46  return SCIP_NOMEMORY;
47 
48  // copy nodes
49  for(int i = 0; i < n; ++i)
50  {
51  GRAPHNODE * node = &((*graph)->nodes[i]);
52  GRAPHNODE * sourcenode = &(sourcegraph->nodes[i]);
53 
54  assert(sourcenode->id == i);
55 
56  node->x = sourcenode->x;
57  node->y = sourcenode->y;
58  node->id = sourcenode->id;
59  node->first_edge = NULL;
60  }
61 
62  // copy edges
63  int e = 0;
64  for(int i = 0; i < n - 1; ++i)
65  {
66  GRAPHNODE * nodestart = &((*graph)->nodes[i]);
67  for(int j = i + 1; j < n; ++j)
68  {
69  GRAPHNODE * nodeend = &((*graph)->nodes[j]);
70 
71  GRAPHEDGE * edgeforw = &((*graph)->edges[e]);
72  GRAPHEDGE * edgebackw = &((*graph)->edges[e + m]);
73 
74  // construct two 'parallel' halfedges
75  edgeforw->adjac = nodeend;
76  edgebackw->adjac = nodestart;
77  edgeforw->back = edgebackw;
78  edgebackw->back = edgeforw;
79 
80  // copy length
81  edgeforw->length = sourcegraph->edges[e].length;
82  edgebackw->length = edgeforw->length;
83 
84  // insert one of the halfedges into the edge list of the node
85  if (nodestart->first_edge == NULL)
86  {
87  nodestart->first_edge = edgeforw;
88  nodestart->first_edge->next = NULL;
89  }
90  else
91  {
92  edgeforw->next = nodestart->first_edge;
93  nodestart->first_edge = edgeforw;
94  }
95 
96  // dito
97  if (nodeend->first_edge == NULL)
98  {
99  nodeend->first_edge = edgebackw;
100  nodeend->first_edge->next = NULL;
101  }
102  else
103  {
104  edgebackw->next = nodeend->first_edge;
105  nodeend->first_edge = edgebackw;
106  }
107 
108  ++e;
109  } // for j
110  } // for i
111 
112  return SCIP_OKAY;
113 }
114 
115 /** copies user data if you want to copy it to a subscip */
117  SCIP* scip, /**< SCIP data structure */
118  SCIP* sourcescip, /**< source SCIP main data structure */
119  SCIP_HASHMAP* varmap, /**< a hashmap which stores the mapping of source variables to
120  * corresponding target variables */
121  SCIP_HASHMAP* consmap, /**< a hashmap which stores the mapping of source contraints to
122  * corresponding target constraints */
123  ObjProbData** objprobdata, /**< pointer to store the copied problem data object */
124  SCIP_Bool global, /**< create a global or a local copy? */
125  SCIP_RESULT* result /**< pointer to store the result of the call */
126  )
127 {
128  // get source prob data and its graph
129  ProbDataTSP * sourceprobdatatsp;
130  sourceprobdatatsp = dynamic_cast<ProbDataTSP *>(SCIPgetObjProbData(sourcescip));
131  assert( sourceprobdatatsp != NULL );
132  GRAPH * sourcegraph = sourceprobdatatsp->graph_;
133  assert( sourcegraph != NULL );
134 
135  // copy graph
136  GRAPH * graph = NULL;
137  SCIP_CALL( copy_graph(&graph, sourcegraph) );
138 
139  // copy and link variables
140  int m = graph->nedges;
141  for(int e = 0; e < m; ++e)
142  {
143  SCIP_Bool success;
144  GRAPHEDGE * edgeforw = &(graph->edges[e]);
145  GRAPHEDGE * edgebackw = &(graph->edges[e + m]);
146 
147  assert( sourcegraph->edges[e].var != NULL );
148  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcegraph->edges[e].var, &(edgeforw->var), varmap, consmap, global, &success) );
149  SCIP_CALL( SCIPcaptureVar(scip, edgeforw->var) );
150  assert(success);
151  assert(edgeforw->var != NULL);
152 
153  // anti-parallel arcs share variable
154  edgebackw->var = edgeforw->var;
155  SCIP_CALL( SCIPcaptureVar(scip, edgebackw->var) );
156  }
157 
158  // allocate memory for target prob data
159  ProbDataTSP * probdatatsp = new ProbDataTSP(graph);
160  assert( probdatatsp != NULL );
161 
162  // save data pointer
163  assert( objprobdata != NULL );
164  *objprobdata = probdatatsp;
165 
166  // graph is captured by ProbDataTSP(graph)
167  release_graph(&graph);
168 
169  *result = SCIP_SUCCESS;
170  return SCIP_OKAY;
171 }
172 
173 /** destructor of user problem data to free original user data (called when original problem is freed)
174  *
175  * If the "deleteobject" flag in the SCIPcreateObjProb() method was set to TRUE, this method is not needed,
176  * because all the work to delete the user problem data can be done in the destructor of the user problem
177  * data object. If the "deleteobject" flag was set to FALSE, and the user problem data object stays alive
178  * after the SCIP problem is freed, this method should delete all the problem specific data that is no
179  * longer needed.
180  */
182  SCIP* scip /**< SCIP data structure */
183  )
184 {
185  for( int i = 0; i < graph_->nedges; i++ )
186  {
187  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].back->var) );
188  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].var) );
189  }
190  release_graph(&graph_);
191 
192  return SCIP_OKAY;
193 }
194 
195 /** destructor of user problem data to free original user data (called when original problem is freed)
196  *
197  * If the "deleteobject" flag in the SCIPcreateObjProb() method was set to TRUE, this method is not needed,
198  * because all the work to delete the user problem data can be done in the destructor of the user problem
199  * data object. If the "deleteobject" flag was set to FALSE, and the user problem data object stays alive
200  * after the SCIP problem is freed, this method should delete all the problem specific data that is no
201  * longer needed.
202  */
204  SCIP* scip /**< SCIP data structure */
205  )
206 {
207  for( int i = 0; i < graph_->nedges; i++ )
208  {
209  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].back->var) );
210  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].var) );
211  }
212  release_graph(&graph_);
213 
214  return SCIP_OKAY;
215 }
216 
217 /** creates user data of transformed problem by transforming the original user problem data
218  * (called after problem was transformed)
219  *
220  * The user has two possibilities to implement this method:
221  * 1. Return the pointer to the original problem data object (this) as pointer to the transformed problem data
222  * object. The user may modify some internal attributes, but he has to make sure, that these modifications are
223  * reversed in the scip_deltrans() method, such that the original problem data is restored. In this case,
224  * he should set *deleteobject to FALSE, because the problem data must not be destructed by SCIP after the
225  * solving process is terminated.
226  * 2. Call the copy constructor of the problem data object and return the created copy as transformed problem
227  * data object. In this case, he probably wants to set *deleteobject to TRUE, thus letting SCIP call the
228  * destructor of the object if the transformed problem data is no longer needed.
229  */
231  SCIP* scip, /**< SCIP data structure */
232  ObjProbData** objprobdata, /**< pointer to store the transformed problem data object */
233  SCIP_Bool* deleteobject /**< pointer to store whether SCIP should delete the object after solving */
234  )
235 { /*lint --e{715}*/
236  assert( objprobdata != NULL );
237  assert( deleteobject != NULL );
238 
239  assert( graph_ != NULL );
240 
241  // copy graph
242  GRAPH * transgraph = NULL;
243  SCIP_CALL( copy_graph(&transgraph, graph_) );
244 
245  // copy and link variables
246  int m = transgraph->nedges;
247  for(int e = 0; e < m; ++e)
248  {
249  GRAPHEDGE * edgeforw = &(transgraph->edges[e]);
250  GRAPHEDGE * edgebackw = &(transgraph->edges[e + m]);
251 
252  assert( graph_->edges[e].var != NULL );
253  SCIP_CALL( SCIPgetTransformedVar(scip, graph_->edges[e].var, &(edgeforw->var)) );
254  SCIP_CALL( SCIPcaptureVar(scip, edgeforw->var) );
255  edgebackw->var = edgeforw->var; // anti-parallel arcs share variable
256  assert( edgebackw->var != NULL );
257  SCIP_CALL( SCIPcaptureVar(scip, edgebackw->var) );
258  }
259 
260  // allocate memory for target prob data
261  ProbDataTSP * transprobdatatsp = new ProbDataTSP(transgraph);
262  assert( transprobdatatsp != NULL );
263 
264  // save data pointer
265  assert( objprobdata != NULL );
266  *objprobdata = transprobdatatsp;
267 
268  // graph is captured by ProbDataTSP(graph)
269  release_graph(&transgraph);
270 
271  *deleteobject = TRUE;
272 
273  return SCIP_OKAY;
274 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
struct GraphEdge * next
Definition: GomoryHuTree.h:58
#define NULL
Definition: def.h:253
double length
Definition: GomoryHuTree.h:56
Definition: grph.h:57
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1217
virtual SCIP_RETCODE scip_copy(SCIP *scip, SCIP *sourcescip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, ObjProbData **objprobdata, SCIP_Bool global, SCIP_RESULT *result)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
generator for global cuts in undirected graphs
virtual SCIP_RETCODE scip_delorig(SCIP *scip)
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:672
C++ wrapper for user problem data.
Definition: objprobdata.h:43
SCIP_VAR * var
Definition: GomoryHuTree.h:63
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1442
GRAPHNODE * adjac
Definition: GomoryHuTree.h:61
struct GraphEdge * back
Definition: GomoryHuTree.h:59
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:43
C++ wrapper classes for SCIP.
#define SCIP_CALL(x)
Definition: def.h:365
C++ problem data for TSP.
virtual SCIP_RETCODE scip_trans(SCIP *scip, ObjProbData **objprobdata, SCIP_Bool *deleteobject)
#define SCIP_Bool
Definition: def.h:70
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
static SCIP_RETCODE copy_graph(GRAPH **graph, GRAPH *sourcegraph)
Definition: ProbDataTSP.cpp:32
double x
Definition: GomoryHuTree.h:35
virtual SCIP_RETCODE scip_deltrans(SCIP *scip)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
double y
Definition: GomoryHuTree.h:36
int edges
Definition: grph.h:92
void release_graph(GRAPH **gr)