Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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-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 bipartitegraph_def.h
29  * @brief A bipartite graph
30  * @author Martin Bergner
31  */
32 
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, /**< SCIP data structure */
46  Weights w /**< weights for the given graph */
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 
60 /**
61  * Builds a bipartite graph structure out of the matrix.
62  *
63  * The function will create an node for every constraint and every variable.
64  * A constraint and a variable are adjacent if the variable appears in the constraint variable array.
65  *
66  * @todo The nonzeroness is not checked, all variables in the variable array are considered
67  */
68 template <class T>
70  SCIP_CONS** conss, /**< constraints for which graph should be created */
71  SCIP_VAR** vars, /**< variables for which graph should be created */
72  int nconss_, /**< number of constraints */
73  int nvars_ /**< number of variables */
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 
119  /** @todo skip all variables that have a zero coeffient or where all coefficients add to zero */
120  /** @todo Do more then one entry per variable actually work? */
121 
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  DETPROBDATA* detprobdata,
153  PARTIALDECOMP* partialdec
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(partialdec->getNVars(), false); /* true, if the var will be part of the graph */
161  std::vector<bool> conssBool(partialdec->getNConss(), false); /* true, if the cons will be part of the graph */
162  std::vector<int> conssForGraph; /* stores the conss included by the graph */
163  std::vector<int> varsForGraph; /* stores the vars included by the graph */
164 
165  //fillout conssForGraph and varsForGraph
166  for(int c = 0; c < partialdec->getNOpenconss(); ++c)
167  {
168  int cons = partialdec->getOpenconss()[c];
169  for(int v = 0; v < partialdec->getNOpenvars(); ++v)
170  {
171  int var = partialdec->getOpenvars()[v];
172  for(i = 0; i < detprobdata->getNVarsForCons(cons); ++i)
173  {
174  if(var == detprobdata->getVarsForCons(cons)[i])
175  {
176  varsBool[var] = true;
177  conssBool[cons] = true;
178  }
179  }
180  }
181  }
182 
183  for(int v = 0; v < partialdec->getNOpenvars(); ++v)
184  {
185  int var = partialdec->getOpenvars()[v];
186  if(varsBool[var])
187  varsForGraph.push_back(var);
188  }
189  for(int c = 0; c < partialdec->getNOpenconss(); ++c)
190  {
191  int cons = partialdec->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 
200  /* add node for every var */
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(detprobdata->getVar(var));
208  oldToNewVarIndex.insert({var,i});
209  this->graph.addNode(i, weight);
210  }
211 
212 
213  /* add node for every cons */
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(detprobdata->getCons(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 < detprobdata->getNVarsForCons(oldConsId); ++j )
231  {
232  int oldVarId = detprobdata->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
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec)
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:41
various SCIP helper methods
GraphInterface * graphiface
Definition: matrixgraph.h:63
BipartiteGraph(SCIP *scip, Weights w)
SCIP_CONS * getCons(int consIndex)
returns the SCIP constraint related to a constraint index
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 createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
class to manage partial decompositions
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
int getNOpenconss()
Gets size of vector containing constraints not assigned yet.
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
int getNVars()
Gets number of vars.