columngraph_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 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #ifndef GCG_COLUMNGRAPH_DEF_H_
37 #define GCG_COLUMNGRAPH_DEF_H_
38 
39 #include "columngraph.h"
40 #include <algorithm>
41 #include <utility>
42 #include <vector>
43 
44 namespace gcg {
45 
46 template <class T>
48  SCIP* scip,
49  Weights w
50  ) : MatrixGraph<T>(scip, w), graph(scip)
51 {
52  this->graphiface = &graph;
53  this->name = std::string("columngraph");
54 }
55 
56 template <class T>
58 {
59  // TODO Auto-generated destructor stub
60 }
61 
62 
65 //template <class T>
66 //SCIP_RETCODE ColumnGraph<T>::writeToFile(
67 // const char* filename, /**< filename where the graph should be written to */
68 // SCIP_Bool writeweights /**< whether to write weights */
69 // )
70 /*{
71  int nedges;
72  int* nrealneighbors;
73  int** realneighbors;
74 
75  SCIP_Bool* handled;
76  FILE* file;
77  assert(filename != NULL);
78  file = fopen(filename, "w");
79  if( file == NULL )
80  return SCIP_FILECREATEERROR;
81 
82  nrealneighbors = 0;
83  nedges = 0;
84 
85  SCIP_CALL( SCIPallocMemoryArray(this->scip_, &handled, this->nvars) );
86  SCIP_CALL( SCIPallocMemoryArray(this->scip_, &realneighbors, this->nvars) );
87  SCIP_CALL( SCIPallocMemoryArray(this->scip_, &nrealneighbors, this->nvars) );
88 
89  for( int i = 0; i < this->nvars; ++i )
90  {
91  BMSclearMemoryArray(handled, this->nvars);
92  handled[i] = TRUE;
93  nrealneighbors[i] = 0;
94 
95  SCIP_CALL( SCIPallocMemoryArray(this->scip_, &realneighbors[i], this->nvars) );
96  int nneighbors = graph.getNNeighbors(i);
97 
98  SCIPdebugMessage("%d has %d neighbors\n", i, nneighbors);
99 
100  std::vector<int> neighbors = graph.getNeighbors(i);
101  for( int j = 0; j < nneighbors; ++j )
102  {
103  int neighbor = neighbors[j];
104  int nneighborneighbors = graph.getNNeighbors(neighbor);
105  std::vector<int> neighborneighbors = graph.getNeighbors(neighbor);
106  SCIPdebugMessage("\tneighbor %d has %d neighbors\n", neighbor, nneighborneighbors);
107  for( int k = 0; k < nneighborneighbors; ++k )
108  {
109  int neighborneighbor = neighborneighbors[k];
110 
111  SCIPdebugMessage("\t\t%d->%d->%d (", i, neighbor, neighborneighbor);
112  if( !handled[neighborneighbor] )
113  {
114  SCIPdebugPrintf("x)\n");
115  realneighbors[i][nrealneighbors[i]] = neighborneighbor;
116  ++(nrealneighbors[i]);
117 
118  handled[neighborneighbor] = TRUE;
119  ++nedges;
120  }
121  else
122  {
123  SCIPdebugPrintf("-)\n");
124  }
125  }
126  }
127  }
128 
129  SCIPinfoMessage(this->scip_, file, "%d %d\n", this->nvars, nedges);
130 
131  for( int i = 0; i < this->nvars; ++i)
132  {
133  for( int j = 0; j < nrealneighbors[i]; ++j )
134  {
135  SCIPinfoMessage(this->scip_, file, "%d ", realneighbors[i][j]+1);
136  }
137  SCIPinfoMessage(this->scip_, file, "\n");
138  SCIPfreeMemoryArray(this->scip_, &realneighbors[i]);
139  }
140 
141  for( int i = 0; i < this->dummynodes; ++i )
142  {
143  SCIPinfoMessage(this->scip_, file, "\n");
144  }
145 
146  SCIPfreeMemoryArray(this->scip_, &handled);
147  SCIPfreeMemoryArray(this->scip_, &realneighbors);
148  SCIPfreeMemoryArray(this->scip_, &nrealneighbors);
149 
150  return SCIP_OKAY;
151 }
152 */
153 
154 template <class T>
156  DEC_DECOMP** decomp
157 )
158 {
159  int nblocks;
160  SCIP_HASHMAP* constoblock;
161 
162  int *nsubscipconss;
163  int i;
164  SCIP_CONS **conss;
165  SCIP_Bool emptyblocks = FALSE;
166  std::vector<int> partition = graph.getPartition();
167  conss = SCIPgetConss(this->scip_);
168  nblocks = *(std::max_element(partition.begin(), partition.end()))+1;
169 
170  SCIP_CALL( SCIPallocBufferArray(this->scip_, &nsubscipconss, nblocks) );
171  BMSclearMemoryArray(nsubscipconss, nblocks);
172 
173  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(this->scip_), this->nconss) );
174 
175  /* assign constraints to partition */
176  for( i = 0; i < this->nconss; i++ )
177  {
178  int block = partition[i];
179  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[i], (void*) (size_t) (block +1)) );
180  ++(nsubscipconss[block]);
181  }
182 
183  /* first, make sure that there are constraints in every block, otherwise the hole thing is useless */
184  for( i = 0; i < nblocks; ++i )
185  {
186  if( nsubscipconss[i] == 0 )
187  {
188  SCIPdebugMessage("Block %d does not have any constraints!\n", i);
189  emptyblocks = TRUE;
190  }
191  }
192 
193  if( !emptyblocks )
194  {
195  SCIP_CALL( DECdecompCreate(this->scip_, decomp) );
196  SCIP_CALL( DECfilloutDecompFromConstoblock(this->scip_, *decomp, constoblock, nblocks, FALSE) );
197  }
198  else {
199  SCIPhashmapFree(&constoblock);
200  *decomp = NULL;
201  }
202 
203  SCIPfreeBufferArray(this->scip_, &nsubscipconss);
204  return SCIP_OKAY;
205 }
206 
207 
208 template <class T>
210  SCIP_CONS** conss,
211  SCIP_VAR** vars,
212  int nconss_,
213  int nvars_
214  )
215 {
216  int i;
217  int j;
218  int k;
219  SCIP_Bool success;
220  std::pair< int, int> edge;
221  std::vector< std::pair< int, int> > edges;
222 
223  assert(conss != NULL);
224  assert(vars != NULL);
225  assert(nvars_ > 0);
226  assert(nconss_ > 0);
227 
228  this->nvars = nvars_;
229  this->nconss = nconss_;
230 
231  /* go through all variables */
232  for( i = 0; i < this->nvars; ++i )
233  {
234  TCLIQUE_WEIGHT weight;
235 
236  /* calculate weight of node */
237  weight = this->weights.calculate(vars[i]);
238 
239  this->graph.addNode(i, weight);
240  }
241 
242  /* go through all constraints */
243  for( i = 0; i < this->nconss; ++i )
244  {
245  SCIP_VAR **curvars;
246 
247  int ncurvars;
248  SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars, &success) );
249  assert(success);
250  if( ncurvars == 0 )
251  continue;
252 
253  /*
254  * may work as is, as we are copying the constraint later regardless
255  * if there are variables in it or not
256  */
257  SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars, ncurvars) );
258  SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars, ncurvars, &success) );
259  assert(success);
260 
264  for( j = 0; j < ncurvars; ++j )
265  {
266  SCIP_VAR* var1;
267  int varIndex1;
268 
269  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
270  var1 = SCIPvarGetProbvar(curvars[j]);
271  else
272  var1 = curvars[j];
273 
274  if( !GCGisVarRelevant(var1) )
275  continue;
276 
277  assert(var1 != NULL);
278  varIndex1 = SCIPvarGetProbindex(var1);
279  assert(varIndex1 >= 0);
280  assert(varIndex1 < this->nvars);
281 
282  for( k = 0; k < j; ++k )
283  {
284  SCIP_VAR* var2;
285  int varIndex2;
286 
287  if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
288  var2 = SCIPvarGetProbvar(curvars[k]);
289  else
290  var2 = curvars[k];
291 
292  if( !GCGisVarRelevant(var2) )
293  continue;
294 
295  assert(var2 != NULL);
296  varIndex2 = SCIPvarGetProbindex(var2);
297  assert(varIndex2 >= 0);
298  assert(varIndex2 < this->nvars);
299 
300  edge = std::make_pair(MIN(varIndex1, varIndex2), MAX(varIndex1, varIndex2) );
301 
302  /* check if edge was not already added to graph */
303  if(edges.end() == std::find(edges.begin(), edges.end(), edge) )
304  {
305 
306  SCIP_CALL( this->graph.addEdge(varIndex1, varIndex2) );
307  edges.push_back(edge);
308  std::sort(edges.begin(), edges.end());
309  }
310  }
311  }
312  SCIPfreeBufferArray(this->scip_, &curvars);
313  }
314 
315  this->graph.flush();
316  return SCIP_OKAY;
317 }
318 
319 } /* namespace gcg */
320 
321 #endif
std::string name
Definition: matrixgraph.h:56
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
virtual ~ColumnGraph()
GraphInterface * graphiface
Definition: matrixgraph.h:63
A row graph where each column is a node and columns are adjacent if they appear in a row...
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:467
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)
ColumnGraph(SCIP *scip, Weights w)
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1454
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43