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
36using namespace tsp;
37using namespace scip;
38
39/** copies given graph */
40static
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 */
124SCIP_RETCODE ProbDataTSP::scip_copy(
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}
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
void release_graph(GRAPH **gr)
generator for global cuts in undirected graphs
static SCIP_RETCODE copy_graph(GRAPH **graph, GRAPH *sourcegraph)
Definition: ProbDataTSP.cpp:41
C++ problem data for TSP.
C++ wrapper for user problem data.
Definition: objprobdata.h:53
virtual SCIP_RETCODE scip_delorig(SCIP *scip)
virtual SCIP_RETCODE scip_trans(SCIP *scip, ObjProbData **objprobdata, SCIP_Bool *deleteobject)
ProbDataTSP(GRAPH *g)
Definition: ProbDataTSP.h:49
virtual SCIP_RETCODE scip_deltrans(SCIP *scip)
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define TRUE
Definition: def.h:93
#define SCIP_CALL(x)
Definition: def.h:374
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
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1439
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
C++ wrapper classes for SCIP.
struct GraphEdge * back
Definition: GomoryHuTree.h:70
GRAPHNODE * adjac
Definition: GomoryHuTree.h:72
SCIP_VAR * var
Definition: GomoryHuTree.h:74
double length
Definition: GomoryHuTree.h:67
struct GraphEdge * next
Definition: GomoryHuTree.h:69
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:53
double y
Definition: GomoryHuTree.h:46
double x
Definition: GomoryHuTree.h:45
GRAPHNODE * nodes
Definition: GomoryHuTree.h:86
int nedges
Definition: GomoryHuTree.h:83
int nnodes
Definition: GomoryHuTree.h:82
GRAPHEDGE * edges
Definition: GomoryHuTree.h:87
@ SCIP_SUCCESS
Definition: type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_NOMEMORY
Definition: type_retcode.h:44
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63