hyperrowgraph_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 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 //#define SCIP_DEBUG
38 
39 #ifndef GCG_HYPERROWGRAPH_DEF_H_
40 #define GCG_HYPERROWGRAPH_DEF_H_
41 
42 #include "hyperrowgraph.h"
43 #include "scip_misc.h"
44 #include "class_seeed.h"
45 #include "class_seeedpool.h"
46 #include <set>
47 #include <algorithm>
48 #include <iostream>
49 
50 namespace gcg
51 {
52 template <class T>
54  SCIP* scip,
55  Weights w
56 ): MatrixGraph<T>(scip, w), graph(scip)
57 {
58  this->graphiface = &graph;
59  this->name = std::string("hyperrow");
60 }
61 
62 template <class T>
64 {
65  // TODO Auto-generated destructor stub
66 }
67 
68 
72 template <class T>
74  int fd,
75  SCIP_Bool edgeweights
76  )
77 {
78  FILE* file;
79  file = fdopen(fd, "w");
80  if( file == NULL )
81  return SCIP_FILECREATEERROR;
82 
83  SCIPinfoMessage(this->scip_, file, "%d %d %d\n", getNEdges(), getNNodes()+this->dummynodes, edgeweights ? 1 :0);
84 
85  for( int i = 0; i < getNEdges(); ++i )
86  {
87  std::vector<int> neighbors = getHyperedgeNodes(i);
88 
89  if( edgeweights )
90  {
91  SCIPinfoMessage(this->scip_, file, "%d ", graph.getWeight(i+this->nvars));
92  }
93  for( size_t j = 0; j < neighbors.size(); ++j )
94  {
95  SCIPinfoMessage(this->scip_, file, "%d ",neighbors[j]+1);
96  }
97  SCIPinfoMessage(this->scip_, file, "\n");
98  }
99 
100  if( !fclose(file) )
101  return SCIP_OKAY;
102  else
103  return SCIP_WRITEERROR;
104 }
105 
106 template <class T>
108 {
109  return this->nconss;
110 }
111 
112 template <class T>
114 {
115  return this->nvars;
116 }
117 
118 template <class T>
120  int i
121 )
122 {
123  assert(i >= 0);
124  assert(i < getNNodes());
125 
126  return graph.getNNeighbors(i);
127 }
128 
129 template <class T>
131  int i
132 )
133 {
134  assert(i >= 0);
135  assert(i < getNEdges());
136 
137  std::vector<int> neighbors = graph.getHyperedgeNodes(i);
138  return neighbors;
139 }
140 
141 template <class T>
143  DEC_DECOMP** decomp
144 )
145 {
146  int nblocks;
147  SCIP_HASHMAP* constoblock;
148 
149  int *nsubscipconss;
150  int i;
151  SCIP_CONS **conss;
152  SCIP_Bool emptyblocks = FALSE;
153  std::vector<int> partition = graph.getPartition();
154  conss = SCIPgetConss(this->scip_);
155  nblocks = *(std::max_element(partition.begin(), partition.end()))+1;
156 
157  SCIP_CALL( SCIPallocBufferArray(this->scip_, &nsubscipconss, nblocks) );
158  BMSclearMemoryArray(nsubscipconss, nblocks);
159 
160  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
161 
162  /* assign constraints to partition */
163  for( i = 0; i < this->nconss; i++ )
164  {
165 
166  std::set<int> blocks;
167  std::vector<int> neighbors = getHyperedgeNodes(i);
168  for( size_t k = 0; k < neighbors.size(); ++k )
169  {
170  if( partition[neighbors[k]] >= 0 )
171  blocks.insert(partition[neighbors[k]]);
172  }
173  if( blocks.size() > 1 )
174  {
175  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[i], (void*) (size_t) (nblocks+1)) );
176  }
177  else
178  {
179  int block = *(blocks.begin());
180  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[i], (void*) (size_t) (block +1)) );
181  ++(nsubscipconss[block]);
182  }
183  }
184 
185  /* first, make sure that there are constraints in every block, otherwise the hole thing is useless */
186  for( i = 0; i < nblocks; ++i )
187  {
188  if( nsubscipconss[i] == 0 )
189  {
190  SCIPdebugMessage("Block %d does not have any constraints!\n", i);
191  emptyblocks = TRUE;
192  }
193  }
194 
195  if( !emptyblocks )
196  {
197  SCIP_CALL( DECdecompCreate(this->scip_, decomp) );
198  SCIP_CALL( DECfilloutDecompFromConstoblock(this->scip_, *decomp, constoblock, nblocks, FALSE) );
199  }
200  else {
201  SCIPhashmapFree(&constoblock);
202  *decomp = NULL;
203  }
204 
205  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
206  return SCIP_OKAY;
207 }
208 
209 template <class T>
211  Seeed** firstSeeed,
212  Seeed** secondSeeed,
213  Seeedpool* seeedpool
214  )
215 {
216  int nblocks;
217  SCIP_HASHMAP* constoblock;
218 
219  int *nsubscipconss;
220  int i;
221  SCIP_CONS **conss;
222  SCIP_Bool emptyblocks = FALSE;
223  std::vector<int> partition = graph.getPartition();
224  conss = SCIPgetConss(this->scip_);
225  nblocks = *(std::max_element(partition.begin(), partition.end()))+1;
226 
227  SCIP_CALL( SCIPallocBufferArray(this->scip_, &nsubscipconss, nblocks) );
228  BMSclearMemoryArray(nsubscipconss, nblocks);
229 
230  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
231 
232  /* assign constraints to partition */
233  for( i = 0; i < this->nconss; i++ )
234  {
235 
236  std::set<int> blocks;
237  std::vector<int> neighbors = getHyperedgeNodes(i);
238  for( size_t k = 0; k < neighbors.size(); ++k )
239  {
240  if( partition[neighbors[k]] >= 0 )
241  blocks.insert(partition[neighbors[k]]);
242  }
243  if( blocks.size() > 1 )
244  {
245  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t)seeedpool->getIndexForCons(conss[i]), (void*) (size_t) (nblocks+1)) );
246  }
247  else
248  {
249  int block = *(blocks.begin());
250  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t)seeedpool->getIndexForCons(conss[i]), (void*) (size_t) (block +1)) );
251  ++(nsubscipconss[block]);
252  }
253  }
254 
255  /* first, make sure that there are constraints in every block, otherwise the hole thing is useless */
256  for( i = 0; i < nblocks; ++i )
257  {
258  if( nsubscipconss[i] == 0 )
259  {
260  SCIPdebugMessage("Block %d does not have any constraints!\n", i);
261  emptyblocks = TRUE;
262  }
263  }
264 
265  if( !emptyblocks )
266  {
267  (*firstSeeed) = new Seeed(this->scip_, seeedpool->getNewIdForSeeed(), seeedpool);
268  SCIP_CALL( (*firstSeeed)->filloutSeeedFromConstoblock(constoblock, nblocks) );
269  (*secondSeeed) = new Seeed(this->scip_, seeedpool->getNewIdForSeeed(), seeedpool);
270  SCIP_CALL( (*secondSeeed)->filloutBorderFromConstoblock(constoblock, nblocks) );
271  SCIPhashmapFree(&constoblock);
272  }
273  else {
274  SCIPhashmapFree(&constoblock);
275  *firstSeeed = NULL;
276  *secondSeeed = NULL;
277  }
278 
279  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
280  return SCIP_OKAY;
281 }
282 
283 template <class T>
285  Seeed* oldSeeed,
286  Seeed** firstSeeed,
287  Seeed** secondSeeed,
288  Seeedpool* seeedpool
289  )
290 {
291  int nblocks;
292  SCIP_HASHMAP* constoblock;
293 
294  int *nsubscipconss;
295  int i;
296  SCIP_Bool emptyblocks = FALSE;
297 
298  if(this->nconss == 0)
299  {
300  (*firstSeeed) = NULL;
301  (*secondSeeed) = NULL;
302  return SCIP_OKAY;
303  }
304 
305  std::vector<int> partition = graph.getPartition();
306  nblocks = *(std::max_element(partition.begin(), partition.end()))+1;
307 
308  SCIP_CALL( SCIPallocBufferArray(this->scip_, &nsubscipconss, nblocks) );
309  BMSclearMemoryArray(nsubscipconss, nblocks);
310 
311  for(int b = 0; b < nblocks; ++b)
312  {
313  nsubscipconss[b] = 0;
314  }
315 
316  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
317 
318  //fillout conssForGraph
319  vector<int> conssForGraph;
320  vector<bool> conssBool(oldSeeed->getNConss(), false);
321  bool found;
322 
323  for(int c = 0; c < oldSeeed->getNOpenconss(); ++c)
324  {
325  int cons = oldSeeed->getOpenconss()[c];
326  found = false;
327  for(int v = 0; v < oldSeeed->getNOpenvars() && !found; ++v)
328  {
329  int var = oldSeeed->getOpenvars()[v];
330  for(i = 0; i < seeedpool->getNVarsForCons(cons) && !found; ++i)
331  {
332  if(var == seeedpool->getVarsForCons(cons)[i])
333  {
334  conssBool[cons] = true;
335  found = true;
336  }
337  }
338  }
339  }
340 
341  for(int c = 0; c < oldSeeed->getNOpenconss(); ++c)
342  {
343  int cons = oldSeeed->getOpenconss()[c];
344  if(conssBool[cons])
345  conssForGraph.push_back(cons);
346  }
347 
348  /* assign constraints to partition */
349  for( i = 0; i < this->nconss; i++ )
350  {
351 
352  std::set<int> blocks;
353  std::vector<int> neighbors = getHyperedgeNodes(i);
354  for( size_t k = 0; k < neighbors.size(); ++k )
355  {
356  if( partition[neighbors[k]] >= 0 )
357  blocks.insert(partition[neighbors[k]]);
358  }
359  if( blocks.size() > 1 )
360  {
361  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) conssForGraph[i], (void*) (size_t) (nblocks+1)) );
362  }
363  else
364  {
365  int block = *(blocks.begin());
366  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) conssForGraph[i], (void*) (size_t) (block +1)) );
367  ++(nsubscipconss[block]);
368  }
369  }
370 
371  /* first, make sure that there are constraints in every block, otherwise the hole thing is useless */
372  for( i = 0; i < nblocks; ++i )
373  {
374  if( nsubscipconss[i] == 0 )
375  {
376  SCIPdebugMessage("Block %d does not have any constraints!\n", i);
377  emptyblocks = TRUE;
378  }
379  }
380 
381  if( !emptyblocks )
382  {
383  (*firstSeeed) = new Seeed(oldSeeed);
384  SCIP_CALL( (*firstSeeed)->assignSeeedFromConstoblock(constoblock, nblocks) );
385  (*secondSeeed) = new Seeed(oldSeeed);
386  SCIP_CALL( (*secondSeeed)->assignBorderFromConstoblock(constoblock, nblocks) );
387  SCIPhashmapFree(&constoblock);
388  }
389  else {
390  SCIPhashmapFree(&constoblock);
391  *firstSeeed = NULL;
392  *secondSeeed = NULL;
393  }
394 
395  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
396  return SCIP_OKAY;
397 }
398 
399 template <class T>
401  SCIP_CONS** conss,
402  SCIP_VAR** vars,
403  int nconss_,
404  int nvars_
405  )
406 {
407  int i;
408  int j;
409  SCIP_Bool success;
410 
411  assert(conss != NULL);
412  assert(vars != NULL);
413  assert(nvars_ > 0);
414  assert(nconss_ > 0);
415 
416  this->nvars = nvars_;
417  this->nconss = nconss_;
418 
419  /* go through all variables */
420  for( i = 0; i < this->nvars; ++i )
421  {
422  TCLIQUE_WEIGHT weight;
423 
424  /* calculate weight of node */
425  weight = this->weights.calculate(vars[i]);
426 
427  this->graph.addNode(i, weight);
428  }
429 
430  /* go through all constraints */
431  for( i = 0; i < this->nconss; ++i )
432  {
433  SCIP_VAR **curvars;
434  std::vector<int> hyperedge;
435  TCLIQUE_WEIGHT weight;
436 
437  int ncurvars;
438  SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars, &success) );
439  assert(success);
440  if( ncurvars == 0 )
441  continue;
442 
443  /*
444  * may work as is, as we are copying the constraint later regardless
445  * if there are variables in it or not
446  */
447  SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars, ncurvars) );
448  SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars, ncurvars, &success) );
449  assert(success);
450 
454  for( j = 0; j < ncurvars; ++j )
455  {
456  SCIP_VAR* var1;
457  int varIndex1;
458 
459  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
460  var1 = SCIPvarGetProbvar(curvars[j]);
461  else
462  var1 = curvars[j];
463 
464  if( !GCGisVarRelevant(var1) )
465  continue;
466 
467  assert(var1 != NULL);
468  varIndex1 = SCIPvarGetProbindex(var1);
469  assert(varIndex1 >= 0);
470  assert(varIndex1 < this->nvars);
471 
472  hyperedge.insert(hyperedge.end(), varIndex1);
473  }
474  /* calculate weight of hyperedge */
475  weight = this->weights.calculate(conss[i]);
476 
477  this->graph.addHyperedge(hyperedge, weight);
478 
479  SCIPfreeBufferArray(this->scip_, &curvars);
480  }
481 
482 
483 
484  this->graph.flush();
485  return SCIP_OKAY;
486 }
487 
488 
489 
490 template <class T>
492  Seeedpool* seeedpool,
493  Seeed* seeed
494  ){
495  int i;
496  int j;
497  unordered_map<int, int> oldToNewVarIndex;
498  TCLIQUE_WEIGHT weight;
499 
500  vector<bool> varsBool(seeed->getNVars(), false);
501  vector<bool> conssBool(seeed->getNConss(), false);
502  vector<int> conssForGraph;
503  vector<int> varsForGraph;
505  //fillout conssForGraph and varsForGraph
506  for(int c = 0; c < seeed->getNOpenconss(); ++c)
507  {
508  int cons = seeed->getOpenconss()[c];
509  for(int v = 0; v < seeed->getNOpenvars(); ++v)
510  {
511  int var = seeed->getOpenvars()[v];
512  for(i = 0; i < seeedpool->getNVarsForCons(cons); ++i)
513  {
514  if(var == seeedpool->getVarsForCons(cons)[i])
515  {
516  varsBool[var] = true;
517  conssBool[cons] = true;
518  }
519  }
520  }
521  }
522 
523  for(int v = 0; v < seeed->getNOpenvars(); ++v)
524  {
525  int var = seeed->getOpenvars()[v];
526  if(varsBool[var])
527  varsForGraph.push_back(var);
528  }
529  for(int c = 0; c < seeed->getNOpenconss(); ++c)
530  {
531  int cons = seeed->getOpenconss()[c];
532  if(conssBool[cons])
533  conssForGraph.push_back(cons);
534  }
535 
536  this->nconss = (int)conssForGraph.size();
537  this->nvars = (int)varsForGraph.size();
538 
539  /* go through all variables */
540  for( i = 0; i < this->nvars; ++i )
541  {
542  int oldVarId = varsForGraph[i];
543  assert(varsBool[oldVarId]);
544 
545  /* calculate weight of node */
546  weight = this->weights.calculate(seeedpool->getVarForIndex(oldVarId));
547 
548  oldToNewVarIndex.insert({oldVarId,i});
549  this->graph.addNode(i, weight);
550  }
551 
552  /* go through all open constraints */
553  for( i = 0; i < this->nconss; ++i )
554  {
555  std::vector<int> hyperedge;
556  int oldConsId = conssForGraph[i];
557 
558  assert(conssBool[oldConsId]);
559 
560  for( j = 0; j < seeedpool->getNVarsForCons(oldConsId); ++j )
561  {
562  int oldVarId = seeedpool->getVarsForCons(oldConsId)[j];
563  if(!varsBool[oldVarId])
564  continue;
565  hyperedge.insert(hyperedge.end(), oldToNewVarIndex[oldVarId]);
566  }
567  /* calculate weight of hyperedge */
568  weight = this->weights.calculate(seeedpool->getConsForIndex(oldConsId));
569  this->graph.addHyperedge(hyperedge, weight);
570  }
571 
572 
573  this->graph.flush();
574  return SCIP_OKAY;
575 }
576 
577 
578 } /* namespace gcg */
579 
580 #endif
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_)
const int * getOpenconss()
returns array containing constraints not assigned yet
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
int getNVars()
returns number of vars
GraphInterface * graphiface
Definition: matrixgraph.h:63
int getNewIdForSeeed()
returns a new unique id for a new seeed
int getNConss()
returns the number of constraints
HyperrowGraph(SCIP *scip, Weights w)
int getNOpenvars()
returns size of vector containing variables not assigned yet
SCIP_VAR * getVarForIndex(int varIndex)
returns SCIP variable related to a variable index
virtual std::vector< int > getHyperedgeNodes(int i)
virtual int getNNodes()
various SCIP helper methods
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
virtual SCIP_RETCODE createSeeedFromPartition(Seeed *oldSeeed, Seeed **firstSeeed, Seeed **secondSeeed, Seeedpool *seeedpool)
virtual int getNNeighbors(int i)
int getIndexForCons(SCIP_CONS *cons)
returns the constraint index related to a SCIP constraint
SCIP_RETCODE writeToFile(int fd, SCIP_Bool edgeweights)
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
virtual int getNEdges()
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1454
int getNOpenconss()
returns size of vector containing constraints not assigned yet
class with functions for seeed pool where a seeed is a (potentially incomplete) description of a deco...
Column hypergraph.
SCIP_CONS * getConsForIndex(int consIndex)
returns the SCIP constraint related to a constraint index
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
virtual SCIP_RETCODE createFromPartialMatrix(Seeedpool *seeedpool, Seeed *seeed)
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint