bipartitegraph_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 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #ifndef GCG_BIPARTITEGRAPH_DEF_H_
36 #define GCG_BIPARTITEGRAPH_DEF_H_
37 
38 #include "bipartitegraph.h"
39 #include "scip_misc.h"
40 
41 namespace gcg {
42 
43 template <class T>
45  SCIP* scip,
46  Weights w
47  ): MatrixGraph<T>(scip,w), graph(scip)
48 {
49  this->graphiface = &graph;
50  this->name = std::string("bipartite");
51 }
52 
53 template <class T>
55 {
56 
57 }
58 
59 
68 template <class T>
70  SCIP_CONS** conss,
71  SCIP_VAR** vars,
72  int nconss_,
73  int nvars_
74  )
75 {
76  int i;
77  int j;
78  SCIP_Bool success;
79 
80  assert(conss != NULL);
81  assert(vars != NULL);
82  assert(nvars_ > 0);
83  assert(nconss_ > 0);
84  this->nvars = nvars_;
85  this->nconss = nconss_;
86 
87  for( i = 0; i < this->nvars + this->nconss; ++i )
88  {
89  TCLIQUE_WEIGHT weight;
90 
91  /* note that the first nvars nodes correspond to variables */
92  if( i < this->nvars )
93  weight = this->weights.calculate(vars[i]);
94  else
95  weight = this->weights.calculate(conss[i-this->nvars]);
96 
97  this->graph.addNode(i, weight);
98  }
99 
100  /* go through all constraints */
101  for( i = 0; i < this->nconss; ++i )
102  {
103  SCIP_VAR **curvars;
104 
105  int ncurvars;
106  SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars, &success) );
107  assert(success);
108  if( ncurvars == 0 )
109  continue;
110 
111  /*
112  * may work as is, as we are copying the constraint later regardless
113  * if there are variables in it or not
114  */
115  SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars, ncurvars) );
116  SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars, ncurvars, &success) );
117  assert(success);
118 
122  for( j = 0; j < ncurvars; ++j )
123  {
124  SCIP_VAR* var;
125  int varIndex;
126 
127  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
128  var = SCIPvarGetProbvar(curvars[j]);
129  else
130  var = curvars[j];
131 
132  if( !GCGisVarRelevant(var) )
133  continue;
134 
135  assert(var != NULL);
136  varIndex = SCIPvarGetProbindex(var);
137  assert(varIndex >= 0);
138  assert(varIndex < this->nvars);
139 
140  SCIP_CALL( this->graph.addEdge(varIndex, this->nvars+i) );
141  }
142  SCIPfreeBufferArray(this->scip_, &curvars);
143  }
144 
145  this->graph.flush();
146  return SCIP_OKAY;
147 }
148 
149 
150 template <class T>
152  Seeedpool* seeedpool,
153  Seeed* seeed
154  ){
155 
156  int i;
157  int j;
158  unordered_map<int, int> oldToNewVarIndex;
159  unordered_map<int, int> oldToNewConsIndex;
160  std::vector<bool> varsBool(seeed->getNVars(), false);
161  std::vector<bool> conssBool(seeed->getNConss(), false);
162  std::vector<int> conssForGraph;
163  std::vector<int> varsForGraph;
165  //fillout conssForGraph and varsForGraph
166  for(int c = 0; c < seeed->getNOpenconss(); ++c)
167  {
168  int cons = seeed->getOpenconss()[c];
169  for(int v = 0; v < seeed->getNOpenvars(); ++v)
170  {
171  int var = seeed->getOpenvars()[v];
172  for(i = 0; i < seeedpool->getNVarsForCons(cons); ++i)
173  {
174  if(var == seeedpool->getVarsForCons(cons)[i])
175  {
176  varsBool[var] = true;
177  conssBool[cons] = true;
178  }
179  }
180  }
181  }
182 
183  for(int v = 0; v < seeed->getNOpenvars(); ++v)
184  {
185  int var = seeed->getOpenvars()[v];
186  if(varsBool[var])
187  varsForGraph.push_back(var);
188  }
189  for(int c = 0; c < seeed->getNOpenconss(); ++c)
190  {
191  int cons = seeed->getOpenconss()[c];
192  if(conssBool[cons])
193  conssForGraph.push_back(cons);
194  }
195 
196  this->nconss = (int)conssForGraph.size();
197  this->nvars = (int)varsForGraph.size();
198 
199 
201  for( i = 0 ; i < this->nvars; ++i )
202  {
203  TCLIQUE_WEIGHT weight;
204  int var = varsForGraph[i];
205 
206  /* note that the first nvars nodes correspond to variables */
207  weight = this->weights.calculate(seeedpool->getVarForIndex(var));
208  oldToNewVarIndex.insert({var,i});
209  this->graph.addNode(i, weight);
210  }
211 
212 
214  for( j = 0 ; j < this->nconss; ++j )
215  {
216  TCLIQUE_WEIGHT weight;
217  int cons = conssForGraph[j];
218 
219  /* note that the first nvars nodes correspond to variables (legacy implementation) */
220  weight = this->weights.calculate( seeedpool->getConsForIndex(cons) );
221  oldToNewConsIndex.insert({cons, j});
222  this->graph.addNode( this->nvars + j, weight);
223  }
224 
225  /* go through all open constraints */
226  for( i = 0; i < this->nconss; ++i )
227  {
228  int oldConsId = conssForGraph[i];
229 
230  for( j = 0; j < seeedpool->getNVarsForCons(oldConsId); ++j )
231  {
232  int oldVarId = seeedpool->getVarsForCons(oldConsId)[j];
233  if(!varsBool[oldVarId])
234  continue;
235  SCIP_CALL( this->graph.addEdge(oldToNewVarIndex[oldVarId], this->nvars+i) );
236  }
237  }
238 
239  this->graph.flush();
240  return SCIP_OKAY;
241  }
242 
243 
244 template <class T>
246 {
247  return this->nconss;
248 }
249 
250 template <class T>
252 {
253  return this->nvars;
254 }
255 
256 
257 } /* namespace gcg */
258 
259 #endif
std::string name
Definition: matrixgraph.h:56
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
const int * getOpenconss()
returns array containing constraints not assigned yet
int getNVars()
returns number of vars
GraphInterface * graphiface
Definition: matrixgraph.h:63
int getNConss()
returns the number of constraints
int getNOpenvars()
returns size of vector containing variables not assigned yet
SCIP_VAR * getVarForIndex(int varIndex)
returns SCIP variable related to a variable index
various SCIP helper methods
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:41
int calculate(SCIP_CONS *cons) const
Definition: weights.cpp:73
const int * getOpenvars()
returns array containing variables not assigned yet
int getNOpenconss()
returns size of vector containing constraints not assigned yet
BipartiteGraph(SCIP *scip, Weights w)
SCIP_CONS * getConsForIndex(int consIndex)
returns the SCIP constraint related to a constraint index
virtual SCIP_RETCODE createFromPartialMatrix(Seeedpool *seeedpool, Seeed *seeed)
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint