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-2020 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 scipopt.org. */
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  GRAPHEDGE* edgeforw = &((*graph)->edges[e]);
71  GRAPHEDGE* edgebackw = &((*graph)->edges[e + m]);
72 
73  // construct two 'parallel' halfedges
74  edgeforw->adjac = nodeend;
75  edgebackw->adjac = nodestart;
76  edgeforw->back = edgebackw;
77  edgebackw->back = edgeforw;
78 
79  // copy length
80  edgeforw->length = sourcegraph->edges[e].length;
81  edgebackw->length = edgeforw->length;
82 
83  // insert one of the halfedges into the edge list of the node
84  if (nodestart->first_edge == NULL)
85  {
86  nodestart->first_edge = edgeforw;
87  nodestart->first_edge->next = NULL;
88  }
89  else
90  {
91  edgeforw->next = nodestart->first_edge;
92  nodestart->first_edge = edgeforw;
93  }
94 
95  // ditto
96  if (nodeend->first_edge == NULL)
97  {
98  nodeend->first_edge = edgebackw;
99  nodeend->first_edge->next = NULL;
100  }
101  else
102  {
103  edgebackw->next = nodeend->first_edge;
104  nodeend->first_edge = edgebackw;
105  }
106 
107  ++e;
108  } // for j
109  } // for i
110 
111  return SCIP_OKAY;
112 }
113 
114 /** copies user data if you want to copy it to a subscip */
116  SCIP* scip, /**< SCIP data structure */
117  SCIP* sourcescip, /**< source SCIP main data structure */
118  SCIP_HASHMAP* varmap, /**< a hashmap which stores the mapping of source variables to
119  * corresponding target variables */
120  SCIP_HASHMAP* consmap, /**< a hashmap which stores the mapping of source contraints to
121  * corresponding target constraints */
122  ObjProbData** objprobdata, /**< pointer to store the copied problem data object */
123  SCIP_Bool global, /**< create a global or a local copy? */
124  SCIP_RESULT* result /**< pointer to store the result of the call */
125  )
126 {
127  // get source prob data and its graph
128  ProbDataTSP* sourceprobdatatsp;
129  sourceprobdatatsp = dynamic_cast<ProbDataTSP*>(SCIPgetObjProbData(sourcescip));
130  assert( sourceprobdatatsp != NULL );
131 
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  assert( sourcegraph->edges[e].var != NULL );
147 
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 
171  return SCIP_OKAY;
172 }
173 
174 /** destructor of user problem data to free original user data (called when original problem is freed) */
176  SCIP* scip /**< SCIP data structure */
177  )
178 {
179  for( int i = 0; i < graph_->nedges; i++ )
180  {
181  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].back->var) );
182  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].var) );
183  }
184  release_graph(&graph_);
185 
186  return SCIP_OKAY;
187 }
188 
189 /** destructor of user problem data to free original user data (called when original problem is freed) */
191  SCIP* scip /**< SCIP data structure */
192  )
193 {
194  for( int i = 0; i < graph_->nedges; i++ )
195  {
196  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].back->var) );
197  SCIP_CALL( SCIPreleaseVar(scip, &graph_->edges[i].var) );
198  }
199  release_graph(&graph_);
200 
201  return SCIP_OKAY;
202 }
203 
204 /** creates user data of transformed problem by transforming the original user problem data
205  * (called after problem was transformed) */
207  SCIP* scip, /**< SCIP data structure */
208  ObjProbData** objprobdata, /**< pointer to store the transformed problem data object */
209  SCIP_Bool* deleteobject /**< pointer to store whether SCIP should delete the object after solving */
210  )
211 { /*lint --e{715}*/
212  assert( objprobdata != NULL );
213  assert( deleteobject != NULL );
214 
215  assert( graph_ != NULL );
216 
217  // copy graph
218  GRAPH* transgraph = NULL;
219  SCIP_CALL( copy_graph(&transgraph, graph_) );
220 
221  // copy and link variables
222  int m = transgraph->nedges;
223  for(int e = 0; e < m; ++e)
224  {
225  GRAPHEDGE* edgeforw = &(transgraph->edges[e]);
226  GRAPHEDGE* edgebackw = &(transgraph->edges[e + m]);
227  assert( graph_->edges[e].var != NULL );
228 
229  SCIP_CALL( SCIPgetTransformedVar(scip, graph_->edges[e].var, &(edgeforw->var)) );
230  SCIP_CALL( SCIPcaptureVar(scip, edgeforw->var) );
231 
232  edgebackw->var = edgeforw->var; // anti-parallel arcs share variable
233  assert( edgebackw->var != NULL );
234 
235  SCIP_CALL( SCIPcaptureVar(scip, edgebackw->var) );
236  }
237 
238  // allocate memory for target prob data
239  ProbDataTSP* transprobdatatsp = new ProbDataTSP(transgraph);
240  assert( transprobdatatsp != NULL );
241 
242  // save data pointer
243  assert( objprobdata != NULL );
244  *objprobdata = transprobdatatsp;
245 
246  // graph is captured by ProbDataTSP(graph)
247  release_graph(&transgraph);
248 
249  *deleteobject = TRUE;
250 
251  return SCIP_OKAY;
252 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
struct GraphEdge * next
Definition: GomoryHuTree.h:60
double length
Definition: GomoryHuTree.h:58
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:1218
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:54
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:697
C++ wrapper for user problem data.
Definition: objprobdata.h:43
SCIP_VAR * var
Definition: GomoryHuTree.h:65
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1443
GRAPHNODE * adjac
Definition: GomoryHuTree.h:63
struct GraphEdge * back
Definition: GomoryHuTree.h:61
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:44
#define NULL
Definition: lpi_spx1.cpp:155
C++ wrapper classes for SCIP.
#define SCIP_CALL(x)
Definition: def.h:364
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:36
virtual SCIP_RETCODE scip_deltrans(SCIP *scip)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1252
double y
Definition: GomoryHuTree.h:37
int edges
Definition: grph.h:92
void release_graph(GRAPH **gr)