Scippy

GCG

Branch-and-Price & Column Generation for Everyone

dec_staircase_lsp.cpp
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 dec_staircase_lsp.cpp
29  * @ingroup DETECTORS
30  * @brief detector for staircase_lsp matrices
31  * @author Martin Bergner
32  * @author Michael Bastubbe
33  *
34  * This detector detects staircase_lsp structures in the constraint matrix by searching for the longest shortest path
35  * in the row graph of the matrix.
36  *
37  */
38 
39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40 
41 #include <assert.h>
42 #include <string.h>
43 #include <iostream>
44 
45 
46 #include "dec_staircase_lsp.h"
47 #include "cons_decomp.h"
48 #include "scip_misc.h"
49 #include "pub_decomp.h"
50 #include "tclique/tclique.h"
51 #include "class_partialdecomp.h"
52 #include "class_detprobdata.h"
53 #include "scip/clock.h"
54 
55 
56 /* constraint handler properties */
57 #define DEC_DETECTORNAME "staircase_lsp" /**< name of detector */
58 #define DEC_DESC "Staircase detection via shortest paths" /**< description of detector */
59 #define DEC_PRIORITY 200 /**< priority of the detector */
60 #define DEC_FREQCALLROUND 1 /**< frequency the detector gets called in detection loop ,ie it is called in round r if and only if minCallRound <= r <= maxCallRound AND (r - minCallRound) mod freqCallRound == 0 */
61 #define DEC_MAXCALLROUND INT_MAX /**< last round the detector gets called */
62 #define DEC_MINCALLROUND 0 /**< first round the detector gets called */
63 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
64 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /**< last round the detector gets called while detecting the original problem */
65 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
66 #define DEC_DECCHAR 'S' /**< display character of detector */
67 #define DEC_ENABLED FALSE /**< should the detection be enabled */
68 #define DEC_ENABLEDFINISHING FALSE /**< should the finishing be enabled */
69 #define DEC_ENABLEDPOSTPROCESSING FALSE /**< should the postprocessing be enabled */
70 #define DEC_SKIP FALSE /**< should detector be skipped if others found detections */
71 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
72 
73 #define TCLIQUE_CALL(x) do \
74  { \
75  if((x) != TRUE ) \
76  { \
77  SCIPerrorMessage("Error in function call\n"); \
78  return SCIP_ERROR; \
79  } \
80  } \
81  while( FALSE )
82 
83 /*
84  * Data structures
85  */
86 
87 /** constraint handler data */
88 struct DEC_DetectorData
89 {
90  SCIP_HASHMAP* constoblock;
91  SCIP_HASHMAP* vartoblock;
92  TCLIQUE_GRAPH* graph;
93  int* components;
95  int nblocks;
96  std::vector<int>* oldToNew;
97  std::vector<int>* newToOld;
98 };
99 
100 
101 /*
102  * Local methods
103  */
104 
105 /* put your local methods here, and declare them static */
106 
107 
108 /** creates the graph from the constraint matrix */
109 static
111  SCIP* scip, /**< SCIP data structure */
112  TCLIQUE_GRAPH** graph, /**< Graph data structure */
113  gcg::PARTIALDECOMP* partialdec, /**< partial decomposition to use for matrix */
114  gcg::DETPROBDATA* detprobdata, /**< detection process information and data */
115  DEC_DETECTORDATA* detectordata /**< detector data data structure */
116  )
117 {
118  int i;
119  int v;
120 
121  assert(scip != NULL);
122  assert(graph != NULL);
123 
124  TCLIQUE_CALL( tcliqueCreate(graph) );
125  assert(*graph != NULL);
126 
127  if(detectordata->newToOld != NULL)
128  delete detectordata->newToOld;
129  if(detectordata->oldToNew != NULL)
130  delete detectordata->oldToNew;
131 
132  detectordata->oldToNew = new std::vector<int>(detprobdata->getNConss(), -1) ;
133  detectordata->newToOld = new std::vector<int>(partialdec->getNOpenconss(), -1) ;
134 
135  for( i = 0; i < partialdec->getNOpenconss(); ++i )
136  {
137  int cons = partialdec->getOpenconss()[i];
138  detectordata->oldToNew->at(cons) = i;
139  detectordata->newToOld->at(i) = cons;
140  TCLIQUE_CALL( tcliqueAddNode(*graph, i, 0) );
141  }
142 
143  std::vector<bool> alreadyConsidered(detprobdata->getNConss(), false );
144 
145 
146  for( i = 0; i < partialdec->getNOpenconss(); ++i )
147  {
148  int cons = partialdec->getOpenconss()[i];
149  std::vector<int> neighborNodes(0);
150  std::vector<bool> isNeighbor(detprobdata->getNConss(), false);
151 
152  alreadyConsidered[cons] = true;
153 
154  for( v = 0; v < detprobdata->getNVarsForCons(cons ) ; ++v )
155  {
156  int var = detprobdata->getVarsForCons(cons)[v];
157 
158  if(!partialdec->isVarOpenvar(var) )
159  continue;
160 
161  for( int c = 0; c < detprobdata->getNConssForVar(var); ++c )
162  {
163  int otherCons = detprobdata->getConssForVar(var)[c];
164  if( isNeighbor[otherCons] || alreadyConsidered[otherCons] || !partialdec->isConsOpencons(otherCons) )
165  continue;
166  isNeighbor[otherCons] = true;
167 
168  TCLIQUE_CALL( tcliqueAddEdge(*graph, detectordata->oldToNew->at(cons), detectordata->oldToNew->at(otherCons)) );
169  }
170  }
171  }
172 
173  TCLIQUE_CALL( tcliqueFlush(*graph) );
174  /*SCIPdebug(tcliquePrintGraph(*graph));*/
175 
176  return SCIP_OKAY;
177 }
178 
179 
180 
181 
182 /** finds the diameter of a connected component of a graph and computes all distances from some vertex of maximum eccentricity to all other vertices */
183 static
184 SCIP_RETCODE findDiameter(
185  SCIP* scip, /**< SCIP data structure */
186  DEC_DETECTORDATA* detectordata, /**< constraint handler data structure */
187  int* maxdistance, /**< diameter of the graph */
188  int* ncomp, /**< number of vertices the component contains */
189  int* vertices, /**< vertices of the connected component (ordered by BFS) */
190  int* distances, /**< distances of vertices to some vertex of maximum eccentricity */
191  int component /**< connected component to investigate */
192 )
193 {
194  TCLIQUE_GRAPH* graph;
195  int diameter = -1;
196  int* queue; /* queue, first entry is queue[squeue], last entry is queue[equeue] */
197  int squeue; /* index of first entry of the queue */
198  int equeue; /* index of last entry of the queue */
199  int nnodes; /* number of vertices the graph contains */
200  int ncompnodes = 0; /* number of vertices the component contains */
201  SCIP_Bool* marked;
202  int* eccentricity; /* upper bounds on the eccentricities */
203  int* dist; /* distances from some start vertex to all other vertices (gets updated in each BFS) */
204  int* origdegree; /* degrees of the vertices */
205  int* degree; /* degrees of the vertices sorted in decreasing order */
206  int* degreepos;
207  int i;
208  int j;
209  int k = 50; /* number of low-degree vertices that are visited before high-degree vertices are visited */
210 
211  /* This method computes the diameter of a connected component by starting BFS at each vertex and memorizing the depth of the search tree.
212  * If a tree has greater depth than any other tree that was computed before, the vertices itself and their distances to the root of the
213  * tree are stored in 'vertices' and 'distances', respectively.
214  *
215  * As these steps require $O(nm)$ time in the worst case, we apply a simple heuristic that stops BFS from vertices that do not have
216  * maximum eccentricity, and in some cases it even prevents starting BFS at such vertices.
217  * a) For each vertex 'v' there is an upper bound 'eccentricity[v]' on the actual eccentricity of 'v'. Initially, this is set to a very large number.
218  * b) Whenever a BFS with root 'v' has finished, 'eccentricity[v]' contains the actual eccentricity of 'v'.
219  * c) If during a BFS with root 'v' a vertex 'u' is discovered, then dist(v, u) + eccentricty[u] is an upper bound on the eccentricity of 'v',
220  * and therefore the BFS is stopped if dist(v, u) + eccentricity[u] <= diameter_lb, where diameter_lb is the greatest eccentricity known so far.
221  */
222 
223  assert(scip != NULL);
224  assert(detectordata != NULL);
225  assert(detectordata->graph != NULL);
226  assert(detectordata->components != NULL);
227  assert(maxdistance != NULL);
228  assert(vertices != NULL);
229  assert(distances != NULL);
230  assert(ncomp != NULL);
231 
232  graph = detectordata->graph;
233  nnodes = tcliqueGetNNodes(graph);
234 
235  SCIP_CALL( SCIPallocMemoryArray(scip, &queue, nnodes) );
236  SCIP_CALL( SCIPallocMemoryArray(scip, &marked, nnodes) );
237  SCIP_CALL( SCIPallocMemoryArray(scip, &eccentricity, nnodes) );
238  SCIP_CALL( SCIPallocMemoryArray(scip, &dist, nnodes) );
239  SCIP_CALL( SCIPallocMemoryArray(scip, &degree, nnodes) );
240  SCIP_CALL( SCIPallocMemoryArray(scip, &degreepos, nnodes) );
241 
242  /* get degrees of vertices and initialize all eccentricities of vertices to values representing upper bounds */
243  origdegree = tcliqueGetDegrees(graph);
244  for( i = 0; i < nnodes; ++i )
245  {
246  if( detectordata->components[i] != component )
247  continue;
248 
249  eccentricity[i] = 2 * nnodes; /* do not use INT_MAX because it could lead to an overflow when adding values */
250  degree[ncompnodes] = origdegree[i]; /* we copy the degree array because we are going to sort it */
251  degreepos[ncompnodes] = i;
252 
253  ++ncompnodes;
254  }
255 
256  /* sort vertices by their degrees in decreasing order */
257  SCIPsortDownIntInt(degree, degreepos, ncompnodes);
258 
259  if( ncompnodes < k )
260  k = ncompnodes;
261 
262  /* for each vertex a BFS will be performed */
263  for( j = 0; j < ncompnodes; j++ )
264  {
265  int eccent = 0; /* eccentricity of this vertex, only valid if vertex has not been pruned */
266  int startnode;
267  SCIP_Bool pruned = FALSE;
268 
269  /* change order in which BFSes are performed: first start at 'k' low-degree vertices, then start BFS at high-degree vertices */
270  if(j < k)
271  startnode = degreepos[ncompnodes - k + j];
272  else
273  startnode = degreepos[j - k];
274 
275  /* eccentricity[startnode] always represents an UPPER BOUND on the actual eccentricity! */
276  if( eccentricity[startnode] <= diameter )
277  continue;
278 
279  /* unmark all vertices */
280  BMSclearMemoryArray(marked, nnodes);
281 
282  /* add 'startnode' to the queue */
283  queue[0] = startnode;
284  equeue = 1;
285  squeue = 0;
286  marked[startnode] = TRUE;
287  dist[startnode] = 0;
288 
289  /* continue BFS until vertex gets pruned or all vertices have been visited */
290  while( !pruned && (equeue > squeue) )
291  {
292  int currentnode;
293  int currentdistance;
294  int* lastneighbour;
295  int* node;
296 
297  /* dequeue new node */
298  currentnode = queue[squeue];
299  currentdistance = dist[currentnode];
300  ++squeue;
301 
302  lastneighbour = tcliqueGetLastAdjedge(graph, currentnode);
303  /* go through all neighbours */
304  for( node = tcliqueGetFirstAdjedge(graph, currentnode); !pruned && (node <= lastneighbour); ++node )
305  {
306  const int v = *node;
307  /* visit 'v' if it has not been visited yet */
308  if( !marked[v] )
309  {
310  /* mark 'v' and add it to the queue */
311  marked[v] = TRUE;
312  queue[equeue] = v;
313  dist[v] = currentdistance + 1;
314  ++equeue;
315 
316  /* if 'v' is further away from the startnode than any other vertex, update the eccentricity */
317  if( dist[v] > eccent )
318  eccent = dist[v];
319 
320  /* prune the startnode if its eccentricity will certainly not lead to a new upper bound */
321  if( eccentricity[v] + dist[v] <= diameter )
322  {
323  pruned = TRUE;
324  eccent = eccentricity[v] + dist[v];
325  }
326 
327  /* update upper bound on eccentricity of 'v' */
328  /*if( eccentricity[currentnode] + dist[v] < eccentricity[v] )
329  eccentricity[v] = eccentricity[currentnode] + dist[v];*/
330  }
331  }
332  }
333 
334  eccentricity[startnode] = eccent;
335 
336  if( eccent > diameter )
337  {
338  SCIPdebugMessage("new incumbent in component %i: path of length %i starts at %i\n", component, eccent, startnode);
339  diameter = eccent;
340 
341  *maxdistance = diameter;
342  *ncomp = ncompnodes;
343  /*detectordata->nblocks = diameter + 1;*/
344 
345  for( i = 0; i < ncompnodes; ++i )
346  {
347  vertices[i] = queue[i];
348  distances[i] = dist[queue[i]];
349  }
350  }
351  }
352 
353  SCIPfreeMemoryArray(scip, &degreepos);
354  SCIPfreeMemoryArray(scip, &degree);
355  SCIPfreeMemoryArray(scip, &dist);
356  SCIPfreeMemoryArray(scip, &eccentricity);
357  SCIPfreeMemoryArray(scip, &marked);
358  SCIPfreeMemoryArray(scip, &queue);
359 
360  return SCIP_OKAY;
361 }
362 
363 /** finds the connected components of the row graph. a staircase_lsp decomposition will be built for each component separately. */
364 static
366  SCIP* scip, /**< SCIP data structure */
367  DEC_DETECTORDATA* detectordata /**< constraint handler data structure */
368  )
369 {
370  int i;
371  int nnodes;
372  int ncomps = 0;
373  int curcomp;
374  int* queue;
375  int squeue;
376  int equeue;
377  TCLIQUE_GRAPH* graph;
378  int* component;
379 
380  assert(scip != NULL);
381  assert(detectordata != NULL);
382  assert(detectordata->graph != NULL);
383  assert(tcliqueGetNNodes(detectordata->graph) >= 0);
384 
385  graph = detectordata->graph;
386  nnodes = tcliqueGetNNodes(graph);
387 
388  /* for each vertex the 'component' array contains a number from [0, ncomponents) */
389  assert(detectordata->components == NULL);
390  SCIP_CALL( SCIPallocMemoryArray(scip, &(detectordata->components), nnodes) );
391  component = detectordata->components;
392 
393  /* component[i] == -1 if and only if vertex i has not been assigned to a component yet */
394  for( i = 0; i < nnodes; ++i )
395  component[i] = -1;
396 
397  SCIP_CALL( SCIPallocMemoryArray(scip, &queue, nnodes) );
398 
399  for( i = 0; i < nnodes; ++i )
400  {
401  /* find first node that has not been visited yet and start BFS */
402  if( component[i] >= 0 )
403  continue;
404 
405  SCIPdebugMessage("found new component; starting at %i\n", i);
406  squeue = 0;
407  equeue = 1;
408  queue[0] = i;
409  curcomp = ncomps++;
410  component[i] = curcomp;
411 
412  /* dequeue a vertex as long as the queue is not empty */
413  while( equeue > squeue )
414  {
415  int curnode;
416  int* lastneighbour;
417  int* node;
418 
419  curnode = queue[squeue++];
420 
421  assert(curnode < nnodes);
422 
423  /* add unvisited neighbors of this vertex to the queue */
424  lastneighbour = tcliqueGetLastAdjedge(graph, curnode);
425  for( node = tcliqueGetFirstAdjedge(graph, curnode); node <= lastneighbour; ++node )
426  {
427  assert(*node < nnodes);
428 
429  if( component[*node] < 0 )
430  {
431  assert(equeue < nnodes);
432  component[*node] = curcomp;
433  queue[equeue++] = *node;
434  }
435  }
436  }
437  }
438 
439  detectordata->ncomponents = ncomps;
440  SCIPdebugMessage("found %i components\n", ncomps);
441 
442  SCIPfreeMemoryArray(scip, &queue);
443  return SCIP_OKAY;
444 }
445 
446 
447 /** destructor of detector to free user data (called when GCG is exiting) */
448 static
449 DEC_DECL_FREEDETECTOR(detectorFreeStaircaseLsp)
450 { /*lint --e{715}*/
451  DEC_DETECTORDATA *detectordata;
452 
453  assert(scip != NULL);
454  assert(detector != NULL);
455 
456  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
457 
458  detectordata = DECdetectorGetData(detector);
459  assert(detectordata != NULL);
460 
461  delete detectordata->newToOld;
462  delete detectordata->oldToNew;
463 
464  SCIPfreeMemory(scip, &detectordata);
465 
466  return SCIP_OKAY;
467 }
468 
469 /** detector initialization method (called after the problem has been transformed) */
470 static
471 DEC_DECL_INITDETECTOR(detectorInitStaircaseLsp)
472 { /*lint --e{715}*/
473 
474  DEC_DETECTORDATA *detectordata;
475 
476  assert(scip != NULL);
477  assert(detector != NULL);
478 
479  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
480 
481  detectordata = DECdetectorGetData(detector);
482  assert(detectordata != NULL);
483 
484  detectordata->graph = NULL;
485  detectordata->components = NULL;
486  detectordata->ncomponents = 0;
487  detectordata->constoblock = NULL;
488  detectordata->vartoblock = NULL;
489  detectordata->nblocks = 0;
490 
491  return SCIP_OKAY;
492 }
493 
494 /** detector deinitialization method (called before the transformed problem is freed) */
495 static
496 DEC_DECL_EXITDETECTOR(detectorExitStaircaseLsp)
497 { /*lint --e{715}*/
498  DEC_DETECTORDATA *detectordata;
499 
500  assert(scip != NULL);
501  assert(detector != NULL);
502 
503  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
504 
505  detectordata = DECdetectorGetData(detector);
506  assert(detectordata != NULL);
507 
508  if( detectordata->graph != NULL )
509  {
510  tcliqueFree(&detectordata->graph);
511  }
512 
513  if( detectordata->components != NULL )
514  {
515  SCIPfreeMemoryArray(scip, &detectordata->components);
516  }
517 
518  return SCIP_OKAY;
519 }
520 
521 
522 /** detection function for partialdecs */
523 static
524 SCIP_RETCODE detection(
525  SCIP* scip, /**< SCIP data structure */
526  DEC_DETECTORDATA* detectordata, /**< detectordata of the detector */
527  Partialdec_Detection_Data* partialdecdetectiondata /**< partialdecdetectiondata (including the detprobdata) where to store the new Partialdecs */
528 )
529 {
530  int i;
531  int j;
532  int* nodes;
533  int nnodes;
534  int* distances;
535  int* blocks;
536  int nblocks = 0;
537 
538  char decinfo[SCIP_MAXSTRLEN];
539 
540  gcg::DETPROBDATA* detprobdata = partialdecdetectiondata->detprobdata;
541  gcg::PARTIALDECOMP* currpartialdec = new gcg::PARTIALDECOMP(partialdecdetectiondata->workonpartialdec);
542 
543  SCIP_CLOCK* temporaryClock;
544  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
545  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
546 
547  currpartialdec->refineToMaster();
548 
549  currpartialdec->sort();
550 
551  //currpartialdec->showScatterPlot(detprobdata);
552 
553  //SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting staircase structure:");
554 
555  SCIP_CALL( createGraphFromPartialMatrix(scip, &(detectordata->graph), currpartialdec, detprobdata, detectordata) );
556  SCIP_CALL( SCIPhashmapCreate(&detectordata->constoblock, SCIPblkmem(scip), detprobdata->getNConss() ) );
557 
558  if( tcliqueGetNNodes(detectordata->graph) > 0 )
559  {
560  nnodes = tcliqueGetNNodes(detectordata->graph);
561 
562  /* find connected components of the graph. the result will be stored in 'detectordata->components' */
563  SCIP_CALL( findConnectedComponents(scip, detectordata) );
564 
565  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes, nnodes) );
566  SCIP_CALL( SCIPallocMemoryArray(scip, &distances, nnodes) );
567  SCIP_CALL( SCIPallocMemoryArray(scip, &blocks, nnodes) );
568 
569  for( i = 0; i < nnodes; ++i)
570  blocks[i] = -1;
571 
572  /* find the diameter of each connected component */
573  for( i = 0; i < detectordata->ncomponents; ++i )
574  {
575  int diameter = 0;
576  int ncompsize = 0;
577 
578  SCIP_CALL( findDiameter(scip, detectordata, &diameter, &ncompsize, nodes, distances, i) );
579  SCIPdebugMessage("component %i has %i vertices and diameter %i\n", i, ncompsize, diameter);
580 
581  for( j = 0; j < ncompsize; j++ )
582  {
583  assert(nodes[j] >= 0);
584  assert(nodes[j] < nnodes);
585  assert(distances[j] >= 0);
586  assert(distances[j] <= diameter);
587  assert(distances[j] + nblocks < nnodes);
588 
589  blocks[nodes[j]] = nblocks + distances[j];
590  SCIPdebugMessage("\tnode %i to block %i\n", nodes[j], nblocks + distances[j]);
591  }
592 
593  nblocks += (diameter + 1);
594  }
595  if( nblocks > 0 )
596  {
597  detectordata->nblocks = nblocks;
598 
599  for( i = 0; i < nnodes; ++i )
600  {
601  assert(blocks[i] >= 0);
602  SCIP_CALL( SCIPhashmapInsert(detectordata->constoblock, (void*) (size_t) detectordata->newToOld->at(i), (void*) (size_t) (blocks[i] + 1)) );
603  }
604  }
605 
606  SCIPfreeMemoryArray(scip, &blocks);
607  SCIPfreeMemoryArray(scip, &nodes);
608  SCIPfreeMemoryArray(scip, &distances);
609  SCIPfreeMemoryArray(scip, &(detectordata->components));
610  }
611 
612  SCIP_CALL( currpartialdec->assignPartialdecFromConstoblock(detectordata->constoblock, nblocks) );
613 
614  currpartialdec->assignCurrentStairlinking();
615  currpartialdec->prepare();
616 
617  if( detectordata->constoblock != NULL )
618  SCIPhashmapFree(&detectordata->constoblock);
619  if( detectordata->vartoblock != NULL )
620  SCIPhashmapFree(&detectordata->vartoblock);
621 
622  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
623 
624  assert(currpartialdec->checkConsistency());
625 
626  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
627  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
628  partialdecdetectiondata->newpartialdecs[0] = currpartialdec;
629  partialdecdetectiondata->nnewpartialdecs = 1;
630  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "staircase\\_lsp");
631  partialdecdetectiondata->newpartialdecs[0]->addDetectorChainInfo(decinfo);
632  partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
633 
634  tcliqueFree(&detectordata->graph);
635  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
636 
637  return SCIP_OKAY;
638 }
639 
640 
641 /** detector structure detection method, tries to detect a structure in the problem */
642 static
643 DEC_DECL_PROPAGATEPARTIALDEC(detectorPropagatePartialdecStaircaseLsp)
644 {
645 
646  DEC_DETECTORDATA* detectordata;
647 
648  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
649  assert(detectordata != NULL);
650  detectordata->graph = NULL;
651  detectordata->constoblock = NULL;
652  detectordata->vartoblock = NULL;
653  detectordata->nblocks = 0;
654  detectordata->newToOld = NULL;
655  detectordata->oldToNew = NULL;
656  detectordata->components = NULL;
657  detectordata->ncomponents = 0;
658 
659  *result = SCIP_DIDNOTFIND;
660 
661  detection(scip, detectordata, partialdecdetectiondata);
662 
663  delete detectordata->newToOld;
664  delete detectordata->oldToNew;
665 
666  SCIPfreeMemory(scip, &detectordata);
667 
668  *result = SCIP_SUCCESS;
669 
670  return SCIP_OKAY;
671 }
672 
673 static
674 DEC_DECL_FINISHPARTIALDEC(detectorFinishPartialdecStaircaseLsp)
675 {
676  DEC_DETECTORDATA* detectordata;
677 
678  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
679  assert(detectordata != NULL);
680  detectordata->graph = NULL;
681  detectordata->constoblock = NULL;
682  detectordata->vartoblock = NULL;
683  detectordata->nblocks = 0;
684  detectordata->newToOld = NULL;
685  detectordata->oldToNew = NULL;
686  detectordata->components = NULL;
687  detectordata->ncomponents = 0;
688 
689  *result = SCIP_DIDNOTFIND;
690 
691  detection(scip, detectordata, partialdecdetectiondata);
692 
693  delete detectordata->newToOld;
694  delete detectordata->oldToNew;
695 
696  SCIPfreeMemory(scip, &detectordata);
697 
698  *result = SCIP_SUCCESS;
699 
700  return SCIP_OKAY;
701 }
702 //#define detectorExitStaircase NULL
703 
704 #define detectorPostprocessPartialdecStaircaseLsp NULL
705 
706 
707 static
708 DEC_DECL_SETPARAMFAST(setParamAggressiveStaircaseLsp)
709 {
710  char setstr[SCIP_MAXSTRLEN];
711  const char* name = DECdetectorGetName(detector);
712 
713  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
714  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
715 
716  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
717  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
718 
719  return SCIP_OKAY;
720 
721 }
722 
723 static
724 DEC_DECL_SETPARAMFAST(setParamDefaultStaircaseLsp)
725 {
726  char setstr[SCIP_MAXSTRLEN];
727  const char* name = DECdetectorGetName(detector);
728 
729  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
730  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
731 
732  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
733  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
734 
735  return SCIP_OKAY;
736 
737 }
738 
739 
740 
741 static
742 DEC_DECL_SETPARAMFAST(setParamFastStaircaseLsp)
743 {
744  char setstr[SCIP_MAXSTRLEN];
745  const char* name = DECdetectorGetName(detector);
746 
747  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
748  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
749 
750  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
751  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
752 
753  return SCIP_OKAY;
754 
755 }
756 
757 
758 /*
759  * constraint specific interface methods
760  */
761 
762 /** creates the handler for staircase constraints and includes it in SCIP */
764  SCIP* scip /**< SCIP data structure */
765  )
766 {
767  DEC_DETECTORDATA* detectordata;
768 
769  /* for thread safety: create staircase constraint handler data in callback methods*/
770  detectordata = NULL;
771 
772  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
773  assert(detectordata != NULL);
774  detectordata->graph = NULL;
775  detectordata->constoblock = NULL;
776  detectordata->vartoblock = NULL;
777  detectordata->nblocks = 0;
778  detectordata->newToOld = NULL;
779  detectordata->oldToNew = NULL;
780 
781 
784  DEC_USEFULRECALL, detectordata, detectorFreeStaircaseLsp,
785  detectorInitStaircaseLsp, detectorExitStaircaseLsp, detectorPropagatePartialdecStaircaseLsp, detectorFinishPartialdecStaircaseLsp, detectorPostprocessPartialdecStaircaseLsp, setParamAggressiveStaircaseLsp, setParamDefaultStaircaseLsp, setParamFastStaircaseLsp) );
786 
787 
788  return SCIP_OKAY;
789 }
#define DEC_FREQCALLROUND
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
int getNConss()
returns the number of variables considered in the detprobdata
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
TCLIQUE_GRAPH * graph
static SCIP_RETCODE findDiameter(SCIP *scip, DEC_DETECTORDATA *detectordata, int *maxdistance, int *ncomp, int *vertices, int *distances, int component)
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
SCIP_HASHMAP * vartoblock
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
#define DEC_DESC
static SCIP_RETCODE findConnectedComponents(SCIP *scip, DEC_DETECTORDATA *detectordata)
static DEC_DECL_SETPARAMFAST(setParamAggressiveStaircaseLsp)
#define DEC_MINCALLROUNDORIGINAL
#define DEC_USEFULRECALL
std::vector< int > & getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
static DEC_DECL_FREEDETECTOR(detectorFreeStaircaseLsp)
various SCIP helper methods
SCIP_RETCODE SCIPincludeDetectorStaircaseLsp(SCIP *scip)
static DEC_DECL_FINISHPARTIALDEC(detectorFinishPartialdecStaircaseLsp)
staircase compontent detector
static DEC_DECL_INITDETECTOR(detectorInitStaircaseLsp)
#define DEC_FREQCALLROUNDORIGINAL
std::vector< int > * newToOld
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
interface data structure for the detector calling methods
#define DEC_PRIORITY
bool assignCurrentStairlinking()
assigns open vars to stairlinking if appropriate
bool sort()
sorts the vars and conss data structures by their indices
#define DEC_ENABLEDPOSTPROCESSING
gcg::DETPROBDATA * detprobdata
const int * getOpenconss()
Gets array containing constraints not assigned yet.
#define DEC_DECCHAR
std::vector< int > * oldToNew
bool checkConsistency()
Checks whether the assignments in the partialdec are consistent.
#define detectorPostprocessPartialdecStaircaseLsp
static SCIP_RETCODE createGraphFromPartialMatrix(SCIP *scip, TCLIQUE_GRAPH **graph, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata)
class to manage partial decompositions
#define TCLIQUE_CALL(x)
#define DEC_ENABLEDFINISHING
gcg::PARTIALDECOMP ** newpartialdecs
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
SCIP_RETCODE DECincludeDetector(SCIP *scip, const char *name, const char decchar, const char *description, int freqCallRound, int maxCallRound, int minCallRound, int freqCallRoundOriginal, int maxCallRoundOriginal, int minCallRoundOriginal, int priority, SCIP_Bool enabled, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, DEC_DETECTORDATA *detectordata, DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATEPARTIALDEC((*propagatePartialdecDetector)), DEC_DECL_FINISHPARTIALDEC((*finishPartialdecDetector)), DEC_DECL_POSTPROCESSPARTIALDEC((*postprocessPartialdecDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
#define DEC_DETECTORNAME
int getNOpenconss()
Gets size of vector containing constraints not assigned yet.
SCIP_RETCODE assignPartialdecFromConstoblock(SCIP_HASHMAP *constoblock, int additionalNBlocks)
assigns conss structure according to given hashmap
bool isConsOpencons(int cons)
Gets whether the cons is an open cons.
#define DEC_MINCALLROUND
static DEC_DECL_PROPAGATEPARTIALDEC(detectorPropagatePartialdecStaircaseLsp)
class storing (potentially incomplete) decompositions
static DEC_DECL_EXITDETECTOR(detectorExitStaircaseLsp)
int getNConssForVar(int varIndex)
returns the number of constraints for a given variable where the var has a nonzero entry in
SCIP_HASHMAP * constoblock
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
void refineToMaster()
refine partialdec with focus on master
class storing partialdecs and the problem matrix
#define DEC_MAXCALLROUNDORIGINAL
#define DEC_MAXCALLROUND
gcg::PARTIALDECOMP * workonpartialdec
#define DEC_SKIP
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata)
#define DEC_ENABLED
public methods for working with decomposition structures