hypercolgraph_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 
38 #ifndef GCG_HYPERCOLGRAPH_DEF_H_
39 #define GCG_HYPERCOLGRAPH_DEF_H_
40 
41 #include "hypercolgraph.h"
42 #include "class_seeed.h"
43 #include "class_seeedpool.h"
44 #include <set>
45 #include <algorithm>
46 #include <vector>
47 #include <iostream>
48 
49 namespace gcg
50 {
51 template <class T>
53  SCIP* scip,
54  Weights w
55 ): MatrixGraph<T>(scip, w), graph(scip)
56 {
57  this->graphiface = &graph;
58  this->name = std::string("hypercol");
59 }
60 
61 template <class T>
63 {
64  // TODO Auto-generated destructor stub
65 }
66 
67 
71 template <class T>
73  int fd,
74  SCIP_Bool edgeweights
75  )
76 {
77  function f(this->nvars);
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.getHyperedgeWeight(i));
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  if( !fclose(file) )
100  return SCIP_OKAY;
101  else
102  return SCIP_WRITEERROR;
103 }
104 
105 template <class T>
107 {
108  return this->nvars;
109 }
110 
111 template <class T>
113 {
114  return this->nconss;
115 }
116 
117 
118 template <class T>
120  int i
121 )
122 {
123  assert(i >= 0);
124  assert(i < getNEdges());
125 
126  std::vector<int> neighbors = graph.getHyperedgeNodes(i);
127  return neighbors;
128 }
129 
130 
131 template <class T>
133  SCIP_CONS** conss,
134  SCIP_VAR** vars,
135  int nconss_,
136  int nvars_
137  )
138 {
139  int i;
140  int k;
141  SCIP_Bool success;
142  std::vector< std::vector<int> > hyperedges;
143 
144  assert(conss != NULL);
145  assert(vars != NULL);
146  assert(nvars_ > 0);
147  assert(nconss_ > 0);
148 
149  this->nvars = nvars_;
150  this->nconss = nconss_;
151 
152  /* go through all constraints */
153  for( i = 0; i < this->nconss; ++i )
154  {
155  TCLIQUE_WEIGHT weight;
156 
157  /* calculate weight of node */
158  weight = this->weights.calculate(conss[i]);
159 
160  this->graph.addNode(i, weight);
161  }
162 
163  hyperedges.resize(this->nvars);
164 
165  /* go through all constraints */
166  for( i = 0; i < this->nconss; ++i )
167  {
168  SCIP_VAR **curvars1;
169 
170  int ncurvars1;
171  SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars1, &success) );
172  assert(success);
173  if( ncurvars1 == 0 )
174  continue;
175 
176  /*
177  * may work as is, as we are copying the constraint later regardless
178  * if there are variables in it or not
179  */
180  SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars1, ncurvars1) );
181  SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars1, ncurvars1, &success) );
182  assert(success);
183 
187  for( k = 0; k < ncurvars1; ++k )
188  {
189  SCIP_VAR* var1;
190  int varIndex1;
191 
192  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
193  var1 = SCIPvarGetProbvar(curvars1[k]);
194  else
195  var1 = curvars1[k];
196 
197  if( !GCGisVarRelevant(var1) )
198  continue;
199 
200  assert(var1 != NULL);
201  varIndex1 = SCIPvarGetProbindex(var1);
202  assert(varIndex1 >= 0);
203  assert(varIndex1 < this->nvars);
204 
205  hyperedges[varIndex1].insert(hyperedges[varIndex1].end(), i);
206  }
207  SCIPfreeBufferArray(this->scip_, &curvars1);
208  }
209 
210  /* go through all variables */
211  for( i = 0; i < this->nvars; ++i )
212  {
213  TCLIQUE_WEIGHT weight;
214 
215  /* calculate weight of node */
216  weight = this->weights.calculate(vars[i]);
217 
218  this->graph.addHyperedge(hyperedges[i], weight);
219  }
220  this->graph.flush();
221 
222  return SCIP_OKAY;
223 }
224 
225 template <class T>
227  Seeedpool* seeedpool,
228  Seeed* seeed
229  )
230 {
231  int i;
232  int j;
233  TCLIQUE_WEIGHT weight;
234  std::vector< std::vector<int> > hyperedges;
235  unordered_map<int, int> oldToNewConsIndex;
236  vector<bool> varsBool(seeed->getNVars(), false);
237  vector<bool> conssBool(seeed->getNConss(), false);
238  vector<int> conssForGraph;
239  vector<int> varsForGraph;
241  //fillout conssForGraph and varsForGraph
242  for(int c = 0; c < seeed->getNOpenconss(); ++c)
243  {
244  int cons = seeed->getOpenconss()[c];
245  for(int v = 0; v < seeed->getNOpenvars(); ++v)
246  {
247  int var = seeed->getOpenvars()[v];
248  for(i = 0; i < seeedpool->getNVarsForCons(cons); ++i)
249  {
250  if(var == seeedpool->getVarsForCons(cons)[i])
251  {
252  varsBool[var] = true;
253  conssBool[cons] = true;
254  }
255  }
256  }
257  }
258 
259  for(int v = 0; v < seeed->getNOpenvars(); ++v)
260  {
261  int var = seeed->getOpenvars()[v];
262  if(varsBool[var])
263  varsForGraph.push_back(var);
264  }
265  for(int c = 0; c < seeed->getNOpenconss(); ++c)
266  {
267  int cons = seeed->getOpenconss()[c];
268  if(conssBool[cons])
269  conssForGraph.push_back(cons);
270  }
271 
272  this->nconss = (int)conssForGraph.size();
273  this->nvars = (int)varsForGraph.size();
274 
275  /* go through all open constraints */
276  for( i = 0; i < this->nconss; ++i )
277  {
278  int oldConsId = conssForGraph[i];
279 
280  /* calculate weight of node */
281  weight = this->weights.calculate(seeedpool->getConsForIndex(oldConsId));
282 
283  oldToNewConsIndex.insert({oldConsId,i});
284 
285  this->graph.addNode(i, weight);
286  }
287 
288 
289 
290  /* go through all open variables */
291  for( i = 0; i < this->nvars; ++i )
292  {
293  std::vector<int> hyperedge;
294  int oldVarId = varsForGraph[i];
295 
296  for( j = 0; j < seeedpool->getNConssForVar(oldVarId); ++j )
297  {
298  int oldConsId = seeedpool->getConssForVar(oldVarId)[j];
299  if(!conssBool[oldConsId])
300  continue;
301  hyperedge.insert(hyperedge.end(), oldToNewConsIndex[oldConsId]);
302  }
303  /* calculate weight of hyperedge */
304  weight = this->weights.calculate(seeedpool->getVarForIndex(oldVarId));
305  this->graph.addHyperedge(hyperedge, weight);
306  }
307 
308 
309  this->graph.flush();
310 
311  return SCIP_OKAY;
312 }
313 
314 
315 template <class T>
317  DEC_DECOMP** decomp
318  )
319 {
320  SCIP_HASHMAP* constoblock;
321  SCIP_CONS** conss;
322  int nblocks;
323 
324  assert(decomp != NULL);
325  std::vector<int> partition = this->getPartition();
326  conss = SCIPgetConss(this->scip_);
327 
328  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
329 
330  assert((size_t)SCIPgetNConss(this->scip_) == partition.size());
331  nblocks = 1+*std::max_element(partition.begin(), partition.end() );
332 
333  for( int c = 0; c < this->nconss; ++c )
334  {
335  int consblock = partition[c]+1;
336 
337  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[c], (void*) (size_t) consblock) );
338  }
339 
340  SCIP_CALL( DECdecompCreate(this->scip_, decomp) );
341  SCIP_CALL( DECfilloutDecompFromConstoblock(this->scip_, *decomp, constoblock, nblocks, FALSE) );
342 
343  return SCIP_OKAY;
344 }
345 
346 template <class T>
348  Seeed** firstSeeed,
349  Seeed** secondSeeed,
350  Seeedpool* seeedpool
351  )
352 {
353  SCIP_HASHMAP* constoblock;
354  SCIP_CONS** conss;
355  int nblocks;
356 
357  std::vector<int> partition = this->getPartition();
358  conss = SCIPgetConss(this->scip_);
359  std::vector<bool> isEmptyBlock;
360  std::vector<int> nEmptyBlocksBefore;
361 
362  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
363 
364  assert((size_t)SCIPgetNConss(this->scip_) == partition.size());
365  nblocks = 1+*std::max_element(partition.begin(), partition.end() );
366 
369  isEmptyBlock = std::vector<bool>(nblocks, true);
370  nEmptyBlocksBefore = std::vector<int>(nblocks, 0);
371 
372  for( int c = 0; c < this->nconss; ++c )
373  {
374  int consblock = partition[c]+1;
375  isEmptyBlock[consblock-1] = false;
376  }
377 
378  for(int b1 = 0; b1 < nblocks; ++b1)
379  {
380  if (isEmptyBlock[b1] )
381  {
382  std::cout << "block " << b1 << " is an empty block " << std::endl;
383  for(int b2 = b1+1; b2 < nblocks; ++b2)
384  nEmptyBlocksBefore[b2]++;
385  }
386  }
387 
388 
389  for( int c = 0; c < this->nconss; ++c )
390  {
391  int consblock = partition[c]+1;
392  consblock -= nEmptyBlocksBefore[partition[c] ];
393  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) seeedpool->getIndexForCons(conss[c]), (void*) (size_t) consblock) );
394  }
395 
396  (*firstSeeed) = new Seeed(this->scip_, seeedpool->getNewIdForSeeed(), seeedpool);
397  SCIP_CALL((*firstSeeed)->filloutSeeedFromConstoblock(constoblock, nblocks));
398  (*secondSeeed) = new Seeed(this->scip_, seeedpool->getNewIdForSeeed(), seeedpool);
399  SCIP_CALL((*secondSeeed)->filloutBorderFromConstoblock(constoblock, nblocks));
400  SCIPhashmapFree(&constoblock);
401 
402  return SCIP_OKAY;
403 }
404 
405 template <class T>
407  Seeed* oldSeeed,
408  Seeed** firstSeeed,
409  Seeed** secondSeeed,
410  Seeedpool* seeedpool
411  )
412 {
413  SCIP_HASHMAP* constoblock;
414  int nblocks;
415  std::vector<bool> isEmptyBlock;
416  std::vector<int> nEmptyBlocksBefore;
417  int nEmptyBlocks = 0;
418 
419  if(this->nconss == 0)
420  {
421  (*firstSeeed) = NULL;
422  (*secondSeeed) = NULL;
423  return SCIP_OKAY;
424  }
425 
426  std::vector<int> partition = this->getPartition();
427 
428  //fillout conssForGraph
429  vector<int> conssForGraph;
430  vector<bool> conssBool(oldSeeed->getNConss(), false);
431  bool found;
432 
433  for(int c = 0; c < oldSeeed->getNOpenconss(); ++c)
434  {
435  int cons = oldSeeed->getOpenconss()[c];
436  found = false;
437  for(int v = 0; v < oldSeeed->getNOpenvars() && !found; ++v)
438  {
439  int var = oldSeeed->getOpenvars()[v];
440  for(int i = 0; i < seeedpool->getNVarsForCons(cons) && !found; ++i)
441  {
442  if(var == seeedpool->getVarsForCons(cons)[i])
443  {
444  conssBool[cons] = true;
445  found = true;
446  }
447  }
448  }
449  }
450 
451  for(int c = 0; c < oldSeeed->getNOpenconss(); ++c)
452  {
453  int cons = oldSeeed->getOpenconss()[c];
454  if(conssBool[cons])
455  conssForGraph.push_back(cons);
456  }
457 
458  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
459  nblocks = 1+*std::max_element(partition.begin(), partition.end() );
462  isEmptyBlock = std::vector<bool>(nblocks, true);
463  nEmptyBlocksBefore = std::vector<int>(nblocks, 0);
464 
465  for( int c = 0; c < this->nconss; ++c )
466  {
467  int consblock = partition[c]+1;
468  isEmptyBlock[consblock-1] = false;
469  }
470 
471  for(int b1 = 0; b1 < nblocks; ++b1)
472  {
473  if (isEmptyBlock[b1] )
474  {
475  nEmptyBlocks++;
476  for(int b2 = b1+1; b2 < nblocks; ++b2)
477  nEmptyBlocksBefore[b2]++;
478  }
479  }
480 
481  for( int c = 0; c < this->nconss; ++c )
482  {
483  int consblock = partition[c]+1;
484  consblock -= nEmptyBlocksBefore[partition[c] ];
485  SCIP_CALL( SCIPhashmapInsert(constoblock, (void*) (size_t) conssForGraph[c], (void*) (size_t) consblock) );
486  }
487 
488  nblocks -= nEmptyBlocks;
489 
490  (*firstSeeed) = new Seeed(oldSeeed);
491  SCIP_CALL((*firstSeeed)->assignSeeedFromConstoblock(constoblock, nblocks));
492  (*secondSeeed) = new Seeed(oldSeeed);
493  SCIP_CALL((*secondSeeed)->assignBorderFromConstoblock(constoblock, nblocks ));
494  SCIPhashmapFree(&constoblock);
495 
496  return SCIP_OKAY;
497 }
498 
499 
500 } /* namespace gcg */
501 
502 #endif
std::string name
Definition: matrixgraph.h:56
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
virtual SCIP_RETCODE createSeeedFromPartition(Seeed **firstSeeed, Seeed **secondSeeed, Seeedpool *seeedpool)
const int * getOpenconss()
returns array containing constraints not assigned yet
int getNVars()
returns number of vars
GraphInterface * graphiface
Definition: matrixgraph.h:63
int getNewIdForSeeed()
returns a new unique id for a new seeed
virtual SCIP_RETCODE createFromPartialMatrix(Seeedpool *seeedpool, Seeed *seeed)
int getNConss()
returns the number of constraints
virtual std::vector< int > getPartition()
Definition: matrixgraph.h:133
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
int getNConssForVar(int varIndex)
int getNOpenvars()
returns size of vector containing variables not assigned yet
virtual std::vector< int > getHyperedgeNodes(int i)
SCIP_VAR * getVarForIndex(int varIndex)
returns SCIP variable related to a variable index
virtual int getNEdges()
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
const int * getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
Column hypergraph.
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:467
virtual int getNNodes()
int getIndexForCons(SCIP_CONS *cons)
returns the constraint index related to a SCIP constraint
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:41
SCIP_RETCODE writeToFile(int fd, SCIP_Bool edgeweights)
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
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...
SCIP_CONS * getConsForIndex(int consIndex)
returns the SCIP constraint related to a constraint index
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
HypercolGraph(SCIP *scip, Weights w)