Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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-2021 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 
28 /**@file hyperrowgraph_def.h
29  * @brief Column hypergraph
30  * @author Martin Bergner
31  * @author Annika Thome
32  *
33  * Hypergraph with a node for every variable and a hyperedge for every constraint
34  */
35 
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_partialdecomp.h"
45 #include "class_detprobdata.h"
46 #include <set>
47 #include <algorithm>
48 #include <iostream>
49 
50 namespace gcg
51 {
52 template <class T>
54  SCIP* scip, /**< SCIP data structure */
55  Weights w /**< weights for the given graph */
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 
69 /** writes the graph to the given file.
70  * The format is graph dependent
71  */
72 template <class T>
74  int fd, /**< filename where the graph should be written to */
75  SCIP_Bool edgeweights /**< whether to write 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 /**< decomposition structure to generate */
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  PARTIALDECOMP** firstpartialdec,
212  PARTIALDECOMP** secondpartialdec,
213  DETPROBDATA* detprobdata
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)detprobdata->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)detprobdata->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  bool original = detprobdata->isAssignedToOrigProb();
268  if( firstpartialdec != NULL )
269  {
270  (*firstpartialdec) = new PARTIALDECOMP(this->scip_, original);
271  SCIP_CALL((*firstpartialdec)->filloutPartialdecFromConstoblock(constoblock, nblocks));
272  }
273  if( secondpartialdec != NULL )
274  {
275  (*secondpartialdec) = new PARTIALDECOMP(this->scip_, original);
276  SCIP_CALL((*secondpartialdec)->filloutBorderFromConstoblock(constoblock, nblocks));
277  }
278  SCIPhashmapFree(&constoblock);
279  }
280  else {
281  SCIPhashmapFree(&constoblock);
282  if( firstpartialdec != NULL )
283  {
284  *firstpartialdec = NULL;
285  }
286  if( secondpartialdec != NULL )
287  {
288  *secondpartialdec = NULL;
289  }
290  }
291 
292  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
293  return SCIP_OKAY;
294 }
295 
296 template <class T>
298  PARTIALDECOMP* oldpartialdec,
299  PARTIALDECOMP** firstpartialdec,
300  PARTIALDECOMP** secondpartialdec,
301  DETPROBDATA* detprobdata
302  )
303 {
304  int nblocks;
305  SCIP_HASHMAP* constoblock;
306 
307  int *nsubscipconss;
308  int i;
309  SCIP_Bool emptyblocks = FALSE;
310 
311  if(this->nconss == 0)
312  {
313  (*firstpartialdec) = NULL;
314  (*secondpartialdec) = NULL;
315  return SCIP_OKAY;
316  }
317 
318  std::vector<int> partition = graph.getPartition();
319  nblocks = *(std::max_element(partition.begin(), partition.end()))+1;
320 
321  SCIP_CALL( SCIPallocBufferArray(this->scip_, &nsubscipconss, nblocks) );
322  BMSclearMemoryArray(nsubscipconss, nblocks);
323 
324  for(int b = 0; b < nblocks; ++b)
325  {
326  nsubscipconss[b] = 0;
327  }
328 
329  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
330 
331  //fillout conssForGraph
332  vector<int> conssForGraph; /** stores the conss included by the graph */
333  vector<bool> conssBool(oldpartialdec->getNConss(), false); /**< true, if the cons will be part of the graph */
334  bool found;
335 
336  for(int c = 0; c < oldpartialdec->getNOpenconss(); ++c)
337  {
338  int cons = oldpartialdec->getOpenconss()[c];
339  found = false;
340  for(int v = 0; v < oldpartialdec->getNOpenvars() && !found; ++v)
341  {
342  int var = oldpartialdec->getOpenvars()[v];
343  for(i = 0; i < detprobdata->getNVarsForCons(cons) && !found; ++i)
344  {
345  if(var == detprobdata->getVarsForCons(cons)[i])
346  {
347  conssBool[cons] = true;
348  found = true;
349  }
350  }
351  }
352  }
353 
354  for(int c = 0; c < oldpartialdec->getNOpenconss(); ++c)
355  {
356  int cons = oldpartialdec->getOpenconss()[c];
357  if(conssBool[cons])
358  conssForGraph.push_back(cons);
359  }
360 
361  /* assign constraints to partition */
362  for( i = 0; i < this->nconss; i++ )
363  {
364 
365  std::set<int> blocks;
366  std::vector<int> neighbors = getHyperedgeNodes(i);
367  for( size_t k = 0; k < neighbors.size(); ++k )
368  {
369  if( partition[neighbors[k]] >= 0 )
370  blocks.insert(partition[neighbors[k]]);
371  }
372  if( blocks.size() > 1 )
373  {
374  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) conssForGraph[i], (void*) (size_t) (nblocks+1)) );
375  }
376  else
377  {
378  int block = *(blocks.begin());
379  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) conssForGraph[i], (void*) (size_t) (block +1)) );
380  ++(nsubscipconss[block]);
381  }
382  }
383 
384  /* first, make sure that there are constraints in every block, otherwise the hole thing is useless */
385  for( i = 0; i < nblocks; ++i )
386  {
387  if( nsubscipconss[i] == 0 )
388  {
389  SCIPdebugMessage("Block %d does not have any constraints!\n", i);
390  emptyblocks = TRUE;
391  }
392  }
393 
394  if( !emptyblocks )
395  {
396  (*firstpartialdec) = new PARTIALDECOMP(oldpartialdec);
397  SCIP_CALL( (*firstpartialdec)->assignPartialdecFromConstoblock(constoblock, nblocks) );
398  (*secondpartialdec) = new PARTIALDECOMP(oldpartialdec);
399  SCIP_CALL( (*secondpartialdec)->assignBorderFromConstoblock(constoblock, nblocks) );
400  SCIPhashmapFree(&constoblock);
401  }
402  else {
403  SCIPhashmapFree(&constoblock);
404  *firstpartialdec = NULL;
405  *secondpartialdec = NULL;
406  }
407 
408  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
409  return SCIP_OKAY;
410 }
411 
412 template <class T>
414  SCIP_CONS** conss, /**< constraints for which graph should be created */
415  SCIP_VAR** vars, /**< variables for which graph should be created */
416  int nconss_, /**< number of constraints */
417  int nvars_ /**< number of variables */
418  )
419 {
420  int i;
421  int j;
422  SCIP_Bool success;
423 
424  assert(conss != NULL);
425  assert(vars != NULL);
426  assert(nvars_ > 0);
427  assert(nconss_ > 0);
428 
429  this->nvars = nvars_;
430  this->nconss = nconss_;
431 
432  /* go through all variables */
433  for( i = 0; i < this->nvars; ++i )
434  {
435  TCLIQUE_WEIGHT weight;
436 
437  /* calculate weight of node */
438  weight = this->weights.calculate(vars[i]);
439 
440  this->graph.addNode(i, weight);
441  }
442 
443  /* go through all constraints */
444  for( i = 0; i < this->nconss; ++i )
445  {
446  SCIP_VAR **curvars;
447  std::vector<int> hyperedge;
448  TCLIQUE_WEIGHT weight;
449 
450  int ncurvars;
451  SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars, &success) );
452  assert(success);
453  if( ncurvars == 0 )
454  continue;
455 
456  /*
457  * may work as is, as we are copying the constraint later regardless
458  * if there are variables in it or not
459  */
460  SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars, ncurvars) );
461  SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars, ncurvars, &success) );
462  assert(success);
463 
464  /** @todo skip all variables that have a zero coeffient or where all coefficients add to zero */
465  /** @todo Do more then one entry per variable actually work? */
466 
467  for( j = 0; j < ncurvars; ++j )
468  {
469  SCIP_VAR* var1;
470  int varIndex1;
471 
472  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
473  var1 = SCIPvarGetProbvar(curvars[j]);
474  else
475  var1 = curvars[j];
476 
477  if( !GCGisVarRelevant(var1) )
478  continue;
479 
480  assert(var1 != NULL);
481  varIndex1 = SCIPvarGetProbindex(var1);
482  assert(varIndex1 >= 0);
483  assert(varIndex1 < this->nvars);
484 
485  hyperedge.insert(hyperedge.end(), varIndex1);
486  }
487  /* calculate weight of hyperedge */
488  weight = this->weights.calculate(conss[i]);
489 
490  this->graph.addHyperedge(hyperedge, weight);
491 
492  SCIPfreeBufferArray(this->scip_, &curvars);
493  }
494 
495 
496 
497  this->graph.flush();
498  return SCIP_OKAY;
499 }
500 
501 
502 
503 template <class T>
505  DETPROBDATA* detprobdata,
506  PARTIALDECOMP* partialdec
507  ){
508  int i;
509  int j;
510  unordered_map<int, int> oldToNewVarIndex;
511  TCLIQUE_WEIGHT weight;
512 
513  vector<bool> varsBool(partialdec->getNVars(), false); /**< true, if the var will be part of the graph */
514  vector<bool> conssBool(partialdec->getNConss(), false); /**< true, if the cons will be part of the graph */
515  vector<int> conssForGraph; /** stores the conss included by the graph */
516  vector<int> varsForGraph; /** stores the vars included by the graph */
517 
518  //fillout conssForGraph and varsForGraph
519  for(int c = 0; c < partialdec->getNOpenconss(); ++c)
520  {
521  int cons = partialdec->getOpenconss()[c];
522  for(int v = 0; v < partialdec->getNOpenvars(); ++v)
523  {
524  int var = partialdec->getOpenvars()[v];
525  for(i = 0; i < detprobdata->getNVarsForCons(cons); ++i)
526  {
527  if(var == detprobdata->getVarsForCons(cons)[i])
528  {
529  varsBool[var] = true;
530  conssBool[cons] = true;
531  }
532  }
533  }
534  }
535 
536  for(int v = 0; v < partialdec->getNOpenvars(); ++v)
537  {
538  int var = partialdec->getOpenvars()[v];
539  if(varsBool[var])
540  varsForGraph.push_back(var);
541  }
542  for(int c = 0; c < partialdec->getNOpenconss(); ++c)
543  {
544  int cons = partialdec->getOpenconss()[c];
545  if(conssBool[cons])
546  conssForGraph.push_back(cons);
547  }
548 
549  this->nconss = (int)conssForGraph.size();
550  this->nvars = (int)varsForGraph.size();
551 
552  /* go through all variables */
553  for( i = 0; i < this->nvars; ++i )
554  {
555  int oldVarId = varsForGraph[i];
556  assert(varsBool[oldVarId]);
557 
558  /* calculate weight of node */
559  weight = this->weights.calculate(detprobdata->getVar(oldVarId));
560 
561  oldToNewVarIndex.insert({oldVarId,i});
562  this->graph.addNode(i, weight);
563  }
564 
565  /* go through all open constraints */
566  for( i = 0; i < this->nconss; ++i )
567  {
568  std::vector<int> hyperedge;
569  int oldConsId = conssForGraph[i];
570 
571  assert(conssBool[oldConsId]);
572 
573  for( j = 0; j < detprobdata->getNVarsForCons(oldConsId); ++j )
574  {
575  int oldVarId = detprobdata->getVarsForCons(oldConsId)[j];
576  if(!varsBool[oldVarId])
577  continue;
578  hyperedge.insert(hyperedge.end(), oldToNewVarIndex[oldVarId]);
579  }
580  /* calculate weight of hyperedge */
581  weight = this->weights.calculate(detprobdata->getCons(oldConsId));
582  this->graph.addHyperedge(hyperedge, weight);
583  }
584 
585 
586  this->graph.flush();
587  return SCIP_OKAY;
588 }
589 
590 
591 } /* namespace gcg */
592 
593 #endif
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
SCIP_Bool isAssignedToOrigProb()
returns true if the matrix structure corresponds to the presolved problem
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
virtual int getNNeighbors(int i)
virtual int getNEdges()
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:41
various SCIP helper methods
HyperrowGraph(SCIP *scip, Weights w)
GraphInterface * graphiface
Definition: matrixgraph.h:63
virtual int getNNodes()
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)
SCIP_CONS * getCons(int consIndex)
returns the SCIP constraint related to a constraint index
SCIP_RETCODE writeToFile(int fd, SCIP_Bool edgeweights)
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec)
int getIndexForCons(SCIP_CONS *cons)
returns the constraint index related to a SCIP constraint
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1455
const int * getOpenconss()
Gets array containing constraints not assigned yet.
int getNConss()
Gets the number of constraints.
std::string name
Definition: matrixgraph.h:56
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
Column hypergraph.
class to manage partial decompositions
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
int getNOpenconss()
Gets size of vector containing constraints not assigned yet.
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:471
class storing (potentially incomplete) decompositions
virtual std::vector< int > getHyperedgeNodes(int i)
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
const int * getOpenvars()
Gets array containing variables not assigned yet.
SCIP_VAR * getVar(int varIndex)
returns SCIP variable related to a variable index
class storing partialdecs and the problem matrix
int getNVars()
Gets number of vars.