rowgraph_def.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 // #define SCIP_DEBUG
36 
37 #ifndef GCG_ROWGRAPH_DEF_H_
38 #define GCG_ROWGRAPH_DEF_H_
39 
40 #include "rowgraph.h"
41 #include <algorithm>
42 
43 namespace gcg {
44 
45 template <class T>
47  SCIP* scip,
48  Weights w
49  ) : MatrixGraph<T>(scip,w), graph(scip)
50 {
51  this->graphiface = &graph;
52  this->name = std::string("rowgraph");
53 }
54 
55 template <class T>
57 {
58  // TODO Auto-generated destructor stub
59 }
60 
61 template <class T>
63  DEC_DECOMP** decomp
64 )
65 {
66  int nblocks;
67  SCIP_HASHMAP* constoblock;
68 
69  int *nsubscipconss;
70  int i;
71  SCIP_CONS **conss;
72  SCIP_Bool emptyblocks = FALSE;
73  std::vector<int> partition = graph.getPartition();
74  conss = SCIPgetConss(this->scip_);
75  nblocks = *(std::max_element(partition.begin(), partition.end()))+1;
76 
77  SCIP_CALL( SCIPallocBufferArray(this->scip_, &nsubscipconss, nblocks) );
78  BMSclearMemoryArray(nsubscipconss, nblocks);
79 
80  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
81 
82  /* assign constraints to partition */
83  for( i = 0; i < this->nconss; i++ )
84  {
85  int block = partition[i];
86 
87  if(block == -1)
88  {
89  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[i], (void*) (size_t) (nblocks +1)) );
90  }
91  else
92  { assert(block >= 0);
93  assert(block < nblocks);
94  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[i], (void*) (size_t) (block +1)) );
95  ++(nsubscipconss[block]);
96  }
97 
98  }
99 
100 
101  // TODO: remove- FOR DEBUG ONLY!!!
102  std::vector<int> nsubscipconss_dbg(nblocks);
103 
104  /* first, make sure that there are constraints in every block, otherwise the hole thing is useless */
105  for( i = 0; i < nblocks; ++i )
106  {
107  // TODO: remove- FOR DEBUG ONLY!!!
108  nsubscipconss_dbg[i] = nsubscipconss[i];
109  if( nsubscipconss[i] == 0 )
110  {
111  SCIPdebugMessage("Block %d does not have any constraints!\n", i);
112  emptyblocks = TRUE;
113  }
114  }
115 
116  if( !emptyblocks )
117  {
118  SCIP_CALL( DECdecompCreate(this->scip_, decomp) );
119  SCIP_CALL( DECfilloutDecompFromConstoblock(this->scip_, *decomp, constoblock, nblocks, FALSE) );
120  }
121  else {
122  SCIPhashmapFree(&constoblock);
123  *decomp = NULL;
124  }
125 
126  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
127  return SCIP_OKAY;
128 }
129 
130 template <class T>
132  Seeed* oldSeeed,
133  Seeed** firstSeeed,
134  Seeed** secondSeeed,
135  Seeedpool* seeedpool
136  )
137 {
138  int nblocks;
139  SCIP_HASHMAP* constoblock;
140 
141  int *nsubscipconss;
142  int i;
143  SCIP_Bool emptyblocks = FALSE;
144 
145  //fillout conssForGraph
146  std::vector<int> conssForGraph;
147  std::vector<bool> conssBool(oldSeeed->getNConss(), false);
148  bool found;
149 
150  for(int c = 0; c < oldSeeed->getNOpenconss(); ++c)
151  {
152  int cons = oldSeeed->getOpenconss()[c];
153  found = false;
154  for(int v = 0; v < oldSeeed->getNOpenvars() && !found; ++v)
155  {
156  int var = oldSeeed->getOpenvars()[v];
157  for(i = 0; i < seeedpool->getNVarsForCons(cons) && !found; ++i)
158  {
159  if(var == seeedpool->getVarsForCons(cons)[i])
160  {
161  conssBool[cons] = true;
162  found = true;
163  }
164  }
165  }
166  }
167 
168  for(int c = 0; c < oldSeeed->getNOpenconss(); ++c)
169  {
170  int cons = oldSeeed->getOpenconss()[c];
171  if(conssBool[cons])
172  conssForGraph.push_back(cons);
173  }
174 
175  std::vector<int> partition = graph.getPartition();
176  nblocks = *(std::max_element(partition.begin(), partition.end()))+1;
177 
178  SCIP_CALL( SCIPallocBufferArray(this->scip_, &nsubscipconss, nblocks) );
179  BMSclearMemoryArray(nsubscipconss, nblocks);
180 
181  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
182 
183  /* assign constraints to partition */
184  for( i = 0; i < this->nconss; i++ )
185  {
186  int block = partition[i];
187 
188  if(block == -1)
189  {
190  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) conssForGraph[i], (void*) (size_t) (nblocks +1)) );
191  }
192  else
193  { assert(block >= 0);
194  assert(block < nblocks);
195  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) conssForGraph[i], (void*) (size_t) (block +1)) );
196  ++(nsubscipconss[block]);
197  }
198 
199  }
200 
201 
202  // TODO: remove- FOR DEBUG ONLY!!!
203  std::vector<int> nsubscipconss_dbg(nblocks);
204 
205  /* first, make sure that there are constraints in every block, otherwise the hole thing is useless */
206  for( i = 0; i < nblocks; ++i )
207  {
208  // TODO: remove- FOR DEBUG ONLY!!!
209  nsubscipconss_dbg[i] = nsubscipconss[i];
210  if( nsubscipconss[i] == 0 )
211  {
212  SCIPdebugMessage("Block %d does not have any constraints!\n", i);
213  emptyblocks = TRUE;
214  }
215  }
216 
217  if( !emptyblocks )
218  {
219  (*firstSeeed) = new Seeed(oldSeeed);
220  SCIP_CALL( (*firstSeeed)->assignSeeedFromConstoblock(constoblock, nblocks) );
221  (*secondSeeed) = new Seeed(oldSeeed);
222  SCIP_CALL( (*secondSeeed)->assignBorderFromConstoblock(constoblock, nblocks) );
223  SCIPhashmapFree(&constoblock);
224  }
225  else {
226  SCIPhashmapFree(&constoblock);
227  (*firstSeeed) = NULL;
228  (*secondSeeed) = NULL;
229  }
230 
231  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
232  return SCIP_OKAY;
233 }
234 
235 template <class T>
237  SCIP_CONS** conss,
238  SCIP_VAR** vars,
239  int nconss_,
240  int nvars_
241  )
242 {
243  int i;
244  int j;
245  int k;
246  int l;
247  SCIP_Bool success;
248 
249  std::pair< int, int> edge;
250  std::vector< std::pair< int, int> > edges;
251 
252  assert(conss != NULL);
253  assert(vars != NULL);
254  assert(nvars_ > 0);
255  assert(nconss_ > 0);
256 
257  this->nvars = nvars_;
258  this->nconss = nconss_;
259 
260  /* go through all constraints */
261  for( i = 0; i < this->nconss; ++i )
262  {
263  TCLIQUE_WEIGHT weight;
264 
265  /* calculate weight of node */
266  weight = this->weights.calculate(conss[i]);
267 
268  this->graph.addNode(i, weight);
269  }
270 
271  /* go through all constraints */
272  for( i = 0; i < this->nconss; ++i )
273  {
274  SCIP_VAR **curvars1;
275 
276  int ncurvars1;
277  SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars1, &success) );
278  assert(success);
279  if( ncurvars1 == 0 )
280  continue;
281 
282  /*
283  * may work as is, as we are copying the constraint later regardless
284  * if there are variables in it or not
285  */
286  SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars1, ncurvars1) );
287  SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars1, ncurvars1, &success) );
288  assert(success);
289 
290  /* go through all constraints */
291  for( j = 0; j < i; ++j )
292  {
293  SCIP_VAR **curvars2;
294  SCIP_Bool continueloop;
295  int ncurvars2;
296  SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[j], &ncurvars2, &success) );
297  assert(success);
298  if( ncurvars2 == 0 )
299  continue;
300 
301  edge = std::make_pair(MIN(i, j), MAX(i, j) );
302 
303  /* check if edge was not already added to graph */
304  if(edges.end() != std::find(edges.begin(), edges.end(), edge) )
305  continue;
306 
307  /*if(this->graph.edge(i, j))
308  continue;
309  */
310  continueloop = FALSE;
311  /*
312  * may work as is, as we are copying the constraint later regardless
313  * if there are variables in it or not
314  */
315  SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars2, ncurvars2) );
316  SCIP_CALL( SCIPgetConsVars(this->scip_, conss[j], curvars2, ncurvars2, &success) );
317  assert(success);
318 
319 
323  for( k = 0; k < ncurvars1; ++k )
324  {
325  SCIP_VAR* var1;
326  int varIndex1;
327 
328  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
329  var1 = SCIPvarGetProbvar(curvars1[k]);
330  else
331  var1 = curvars1[k];
332 
333  if( !GCGisVarRelevant(var1) )
334  continue;
335 
336  assert(var1 != NULL);
337  varIndex1 = SCIPvarGetProbindex(var1);
338  assert(varIndex1 >= 0);
339  assert(varIndex1 < this->nvars);
340 
341  for( l = 0; l < ncurvars2; ++l )
342  {
343  SCIP_VAR* var2;
344  int varIndex2;
345 
346  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
347  var2 = SCIPvarGetProbvar(curvars2[l]);
348  else
349  var2 = curvars2[l];
350 
351  if( !GCGisVarRelevant(var2) )
352  continue;
353 
354  assert(var2 != NULL);
355  varIndex2 = SCIPvarGetProbindex(var2);
356  assert(varIndex2 >= 0);
357  assert(varIndex2 < this->nvars);
358 
359  if(varIndex1 == varIndex2)
360  {
361  SCIP_CALL( this->graph.addEdge(i, j) );
362 
363  edges.push_back(edge);
364  std::sort(edges.begin(), edges.end());
365 
366  /*
367  * this->graph.flush();
368  */
369 
370  continueloop = TRUE;
371  break;
372  }
373  }
374  if(continueloop)
375  break;
376  }
377  SCIPfreeBufferArray(this->scip_, &curvars2);
378  }
379  SCIPfreeBufferArray(this->scip_, &curvars1);
380  }
381  this->graph.flush();
382 
383  return SCIP_OKAY;
384 }
385 
386 } /* namespace gcg */
387 #endif
virtual ~RowGraph()
Definition: rowgraph_def.h:56
std::string name
Definition: matrixgraph.h:56
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
Definition: rowgraph_def.h:236
const int * getOpenconss()
returns array containing constraints not assigned yet
GraphInterface * graphiface
Definition: matrixgraph.h:63
int getNConss()
returns the number of constraints
int getNOpenvars()
returns size of vector containing variables not assigned yet
virtual SCIP_RETCODE createSeeedFromPartition(Seeed *oldSeeed, Seeed **firstSeeed, Seeed **secondSeeed, Seeedpool *seeedpool)
Definition: rowgraph_def.h:131
A row graph where each row is a node and rows are adjacent if they share a variable.
RowGraph(SCIP *scip, Weights w)
Definition: rowgraph_def.h:46
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:467
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:41
int calculate(SCIP_CONS *cons) const
Definition: weights.cpp:73
static SCIP_RETCODE partition(SCIP *scip, SCIP_VAR **J, int *Jsize, SCIP_Longint *priority, SCIP_VAR **F, int Fsize, SCIP_VAR **origvar, SCIP_Real *median)
const int * getOpenvars()
returns array containing variables not assigned yet
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1454
gcg::Graph< T > graph
Definition: rowgraph.h:48
int getNOpenconss()
returns size of vector containing constraints not assigned yet
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
Definition: rowgraph_def.h:62
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint