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