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-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 
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_seeed.h"
52 #include "class_seeedpool.h"
53 #include "scip/clock.h"
54 
55 
56 
57 /* constraint handler properties */
58 #define DEC_DETECTORNAME "staircase_lsp"
59 #define DEC_DESC "Staircase detection via shortest paths"
60 #define DEC_PRIORITY 200
61 #define DEC_FREQCALLROUND 1
62 #define DEC_MAXCALLROUND INT_MAX
63 #define DEC_MINCALLROUND 0
64 #define DEC_FREQCALLROUNDORIGINAL 1
65 #define DEC_MAXCALLROUNDORIGINAL INT_MAX
66 #define DEC_MINCALLROUNDORIGINAL 0
67 #define DEC_DECCHAR 'S'
68 #define DEC_ENABLED FALSE
69 #define DEC_ENABLEDORIGINAL FALSE
70 #define DEC_ENABLEDFINISHING FALSE
71 #define DEC_ENABLEDPOSTPROCESSING FALSE
72 #define DEC_SKIP FALSE
73 #define DEC_USEFULRECALL FALSE
74 #define DEC_LEGACYMODE FALSE
76 #define TCLIQUE_CALL(x) do \
77  { \
78  if((x) != TRUE ) \
79  { \
80  SCIPerrorMessage("Error in function call\n"); \
81  return SCIP_ERROR; \
82  } \
83  } \
84  while( FALSE )
85 
86 /*
87  * Data structures
88  */
89 
91 struct DEC_DetectorData
92 {
93  SCIP_HASHMAP* constoblock;
94  SCIP_HASHMAP* vartoblock;
95  TCLIQUE_GRAPH* graph;
96  int* components;
97  int ncomponents;
98  int nblocks;
99  std::vector<int>* oldToNew;
100  std::vector<int>* newToOld;
101 };
102 
103 
104 /*
105  * Local methods
106  */
107 
108 /* put your local methods here, and declare them static */
109 
111 {
112  if( elem1 == elem2 )
113  return 0;
114  else if( elem1 < elem2 )
115  return -1;
116  else {
117  assert(elem1 > elem2);
118  return 1;
119  }
120 }
121 
123 static
124 SCIP_RETCODE createGraph(
125  SCIP* scip,
126  TCLIQUE_GRAPH** graph
127  )
128 {
129  int i;
130  int j;
131  int v;
132  int v1;
133  int v2;
134  int nconss;
135  SCIP_CONS** conss;
136  SCIP_Bool useprobvars = FALSE;
137  bool foundEdge;
138 
139  assert(scip != NULL);
140  assert(graph != NULL);
141 
142  nconss = SCIPgetNConss(scip);
143  conss = SCIPgetConss(scip);
144 
145  TCLIQUE_CALL( tcliqueCreate(graph) );
146  assert(*graph != NULL);
147 
148  for( i = 0; i < nconss; ++i )
149  {
150  TCLIQUE_CALL( tcliqueAddNode(*graph, i, 0) );
151  }
152 
153  useprobvars = ( SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED );
154 
155  /* Be aware: the following has n*n*m*log(m) complexity but doesn't need any additional memory
156  * With additional memory, we can get it down to probably n*m + m*m*n
157  */
158  for( i = 0; i < nconss; ++i )
159  {
160  SCIP_VAR** curvars1;
161  int ncurvars1;
162 
163  ncurvars1 = GCGconsGetNVars(scip, conss[i]);
164  if( ncurvars1 == 0 )
165  continue;
166 
167  SCIP_CALL( SCIPallocMemoryArray(scip, &curvars1, ncurvars1) );
168 
169  SCIP_CALL( GCGconsGetVars(scip, conss[i], curvars1, ncurvars1) );
170 
171  if( useprobvars )
172  {
173  /* replace all variables by probvars */
174  for( v = 0; v < ncurvars1; ++v )
175  {
176  curvars1[v] = SCIPvarGetProbvar(curvars1[v]);
177  assert( SCIPvarIsActive(curvars1[v]) );
178  }
179  }
180 
181  SCIPsortPtr((void**)curvars1, cmp, ncurvars1);
182 
183  for( j = i+1; j < nconss; ++j )
184  {
185  SCIP_VAR** curvars2;
186  int ncurvars2;
187 
188  ncurvars2 = GCGconsGetNVars(scip, conss[j]);
189  if( ncurvars2 == 0 )
190  continue;
191 
192  SCIP_CALL( SCIPallocMemoryArray(scip, &curvars2, ncurvars2) );
193 
194  SCIP_CALL( GCGconsGetVars(scip, conss[j], curvars2, ncurvars2) );
195 
196  foundEdge = false;
197 
198  for( v2 = 0; v2 < ncurvars2 && !foundEdge; ++v2 )
199  {
200  if( useprobvars )
201  {
202  curvars2[v2] = SCIPvarGetProbvar(curvars2[v2]);
203  assert( SCIPvarIsActive(curvars2[v2]) );
204  }
205 
206  for( v1 = 0; v1 < ncurvars1 && !foundEdge; ++v1 )
207  {
208  if( curvars2[v2] == curvars1[v1] )
209  {
210  tcliqueAddEdge( *graph, i, j );
211  foundEdge = true;
212  }
213  }
214  }
215  SCIPfreeMemoryArray(scip, &curvars2);
216  }
217 
218  SCIPfreeMemoryArray(scip, &curvars1);
219  }
220 
221  TCLIQUE_CALL( tcliqueFlush(*graph) );
222  /*SCIPdebug(tcliquePrintGraph(*graph));*/
223 
224  return SCIP_OKAY;
225 }
226 
228 static
230  SCIP* scip,
231  TCLIQUE_GRAPH** graph,
232  gcg::Seeed* seeed,
233  gcg::Seeedpool* seeedpool,
234  DEC_DETECTORDATA* detectordata
235  )
236 {
237  int i;
238  int v;
239 
240  assert(scip != NULL);
241  assert(graph != NULL);
242 
243  TCLIQUE_CALL( tcliqueCreate(graph) );
244  assert(*graph != NULL);
245 
246  if(detectordata->newToOld != NULL)
247  delete detectordata->newToOld;
248  if(detectordata->oldToNew != NULL)
249  delete detectordata->oldToNew;
250 
251  detectordata->oldToNew = new std::vector<int>(seeedpool->getNConss(), -1) ;
252  detectordata->newToOld = new std::vector<int>(seeed->getNOpenconss(), -1) ;
253 
254  for( i = 0; i < seeed->getNOpenconss(); ++i )
255  {
256  int cons = seeed->getOpenconss()[i];
257  detectordata->oldToNew->at(cons) = i;
258  detectordata->newToOld->at(i) = cons;
259  TCLIQUE_CALL( tcliqueAddNode(*graph, i, 0) );
260  }
261 
262  /*
263  *
264  */
265 
266  std::vector<bool> alreadyConsidered(seeedpool->getNConss(), false );
267 
268 
269  for( i = 0; i < seeed->getNOpenconss(); ++i )
270  {
271  int cons = seeed->getOpenconss()[i];
272  std::vector<int> neighborNodes(0);
273  std::vector<bool> isNeighbor(seeedpool->getNConss(), false);
274 
275  alreadyConsidered[cons] = true;
276 
277  for( v = 0; v < seeedpool->getNVarsForCons(cons ) ; ++v )
278  {
279  int var = seeedpool->getVarsForCons(cons)[v];
280 
281  if(!seeed->isVarOpenvar(var) )
282  continue;
283 
284  for( int c = 0; c < seeedpool->getNConssForVar(var); ++c )
285  {
286  int otherCons = seeedpool->getConssForVar(var)[c];
287  if( isNeighbor[otherCons] || alreadyConsidered[otherCons] || !seeed->isConsOpencons(otherCons) )
288  continue;
289  isNeighbor[otherCons] = true;
290 
291  TCLIQUE_CALL( tcliqueAddEdge(*graph, detectordata->oldToNew->at(cons), detectordata->oldToNew->at(otherCons)) );
292  }
293  }
294  }
295 
296  TCLIQUE_CALL( tcliqueFlush(*graph) );
297  /*SCIPdebug(tcliquePrintGraph(*graph));*/
298 
299  return SCIP_OKAY;
300 }
301 
302 
303 
304 
306 static
307 SCIP_RETCODE findDiameter(
308  SCIP *scip,
309  DEC_DETECTORDATA* detectordata,
310  int* maxdistance,
311  int* ncomp,
312  int* vertices,
313  int* distances,
314  int component
315 )
316 {
317  TCLIQUE_GRAPH* graph;
318  int diameter = -1;
319  int* queue; /* queue, first entry is queue[squeue], last entry is queue[equeue] */
320  int squeue; /* index of first entry of the queue */
321  int equeue; /* index of last entry of the queue */
322  int nnodes; /* number of vertices the graph contains */
323  int ncompnodes = 0; /* number of vertices the component contains */
324  SCIP_Bool* marked;
325  int* eccentricity; /* upper bounds on the eccentricities */
326  int* dist; /* distances from some start vertex to all other vertices (gets updated in each BFS) */
327  int* origdegree; /* degrees of the vertices */
328  int* degree; /* degrees of the vertices sorted in decreasing order */
329  int* degreepos;
330  int i;
331  int j;
332  int k = 50; /* number of low-degree vertices that are visited before high-degree vertices are visited */
333 
334  /* This method computes the diameter of a connected component by starting BFS at each vertex and memorizing the depth of the search tree.
335  * 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
336  * tree are stored in 'vertices' and 'distances', respectively.
337  *
338  * 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
339  * maximum eccentricity, and in some cases it even prevents starting BFS at such vertices.
340  * 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.
341  * b) Whenever a BFS with root 'v' has finished, 'eccentricity[v]' contains the actual eccentricity of 'v'.
342  * 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',
343  * and therefore the BFS is stopped if dist(v, u) + eccentricity[u] <= diameter_lb, where diameter_lb is the greatest eccentricity known so far.
344  */
345 
346  assert(scip != NULL);
347  assert(detectordata != NULL);
348  assert(detectordata->graph != NULL);
349  assert(detectordata->components != NULL);
350  assert(maxdistance != NULL);
351  assert(vertices != NULL);
352  assert(distances != NULL);
353  assert(ncomp != NULL);
354 
355  graph = detectordata->graph;
356  nnodes = tcliqueGetNNodes(graph);
357 
358  SCIP_CALL( SCIPallocMemoryArray(scip, &queue, nnodes) );
359  SCIP_CALL( SCIPallocMemoryArray(scip, &marked, nnodes) );
360  SCIP_CALL( SCIPallocMemoryArray(scip, &eccentricity, nnodes) );
361  SCIP_CALL( SCIPallocMemoryArray(scip, &dist, nnodes) );
362  SCIP_CALL( SCIPallocMemoryArray(scip, &degree, nnodes) );
363  SCIP_CALL( SCIPallocMemoryArray(scip, &degreepos, nnodes) );
364 
365  /* get degrees of vertices and initialize all eccentricities of vertices to values representing upper bounds */
366  origdegree = tcliqueGetDegrees(graph);
367  for( i = 0; i < nnodes; ++i )
368  {
369  if( detectordata->components[i] != component )
370  continue;
371 
372  eccentricity[i] = 2 * nnodes; /* do not use INT_MAX because it could lead to an overflow when adding values */
373  degree[ncompnodes] = origdegree[i]; /* we copy the degree array because we are going to sort it */
374  degreepos[ncompnodes] = i;
375 
376  ++ncompnodes;
377  }
378 
379  /* sort vertices by their degrees in decreasing order */
380  SCIPsortDownIntInt(degree, degreepos, ncompnodes);
381 
382  if( ncompnodes < k )
383  k = ncompnodes;
384 
385  /* for each vertex a BFS will be performed */
386  for( j = 0; j < ncompnodes; j++ )
387  {
388  int eccent = 0; /* eccentricity of this vertex, only valid if vertex has not been pruned */
389  int startnode;
390  SCIP_Bool pruned = FALSE;
391 
392  /* change order in which BFSes are performed: first start at 'k' low-degree vertices, then start BFS at high-degree vertices */
393  if(j < k)
394  startnode = degreepos[ncompnodes - k + j];
395  else
396  startnode = degreepos[j - k];
397 
398  /* eccentricity[startnode] always represents an UPPER BOUND on the actual eccentricity! */
399  if( eccentricity[startnode] <= diameter )
400  continue;
401 
402  /* unmark all vertices */
403  BMSclearMemoryArray(marked, nnodes);
404 
405  /* add 'startnode' to the queue */
406  queue[0] = startnode;
407  equeue = 1;
408  squeue = 0;
409  marked[startnode] = TRUE;
410  dist[startnode] = 0;
411 
412  /* continue BFS until vertex gets pruned or all vertices have been visited */
413  while( !pruned && (equeue > squeue) )
414  {
415  int currentnode;
416  int currentdistance;
417  int* lastneighbour;
418  int* node;
419 
420  /* dequeue new node */
421  currentnode = queue[squeue];
422  currentdistance = dist[currentnode];
423  ++squeue;
424 
425  lastneighbour = tcliqueGetLastAdjedge(graph, currentnode);
426  /* go through all neighbours */
427  for( node = tcliqueGetFirstAdjedge(graph, currentnode); !pruned && (node <= lastneighbour); ++node )
428  {
429  const int v = *node;
430  /* visit 'v' if it has not been visited yet */
431  if( !marked[v] )
432  {
433  /* mark 'v' and add it to the queue */
434  marked[v] = TRUE;
435  queue[equeue] = v;
436  dist[v] = currentdistance + 1;
437  ++equeue;
438 
439  /* if 'v' is further away from the startnode than any other vertex, update the eccentricity */
440  if( dist[v] > eccent )
441  eccent = dist[v];
442 
443  /* prune the startnode if its eccentricity will certainly not lead to a new upper bound */
444  if( eccentricity[v] + dist[v] <= diameter )
445  {
446  pruned = TRUE;
447  eccent = eccentricity[v] + dist[v];
448  }
449 
450  /* update upper bound on eccentricity of 'v' */
451  /*if( eccentricity[currentnode] + dist[v] < eccentricity[v] )
452  eccentricity[v] = eccentricity[currentnode] + dist[v];*/
453  }
454  }
455  }
456 
457  eccentricity[startnode] = eccent;
458 
459  if( eccent > diameter )
460  {
461  SCIPdebugMessage("new incumbent in component %i: path of length %i starts at %i\n", component, eccent, startnode);
462  diameter = eccent;
463 
464  *maxdistance = diameter;
465  *ncomp = ncompnodes;
466  /*detectordata->nblocks = diameter + 1;*/
467 
468  for( i = 0; i < ncompnodes; ++i )
469  {
470  vertices[i] = queue[i];
471  distances[i] = dist[queue[i]];
472  }
473  }
474  }
475 
476  SCIPfreeMemoryArray(scip, &degreepos);
477  SCIPfreeMemoryArray(scip, &degree);
478  SCIPfreeMemoryArray(scip, &dist);
479  SCIPfreeMemoryArray(scip, &eccentricity);
480  SCIPfreeMemoryArray(scip, &marked);
481  SCIPfreeMemoryArray(scip, &queue);
482 
483  return SCIP_OKAY;
484 }
485 
487 static
489  SCIP* scip,
490  DEC_DETECTORDATA* detectordata
491  )
492 {
493  int i;
494  int nnodes;
495  int ncomps = 0;
496  int curcomp;
497  int* queue;
498  int squeue;
499  int equeue;
500  TCLIQUE_GRAPH* graph;
501  int* component;
502 
503  assert(scip != NULL);
504  assert(detectordata != NULL);
505  assert(detectordata->graph != NULL);
506  assert(tcliqueGetNNodes(detectordata->graph) >= 0);
507 
508  graph = detectordata->graph;
509  nnodes = tcliqueGetNNodes(graph);
510 
511  /* for each vertex the 'component' array contains a number from [0, ncomponents) */
512  assert(detectordata->components == NULL);
513  SCIP_CALL( SCIPallocMemoryArray(scip, &(detectordata->components), nnodes) );
514  component = detectordata->components;
515 
516  /* component[i] == -1 if and only if vertex i has not been assigned to a component yet */
517  for( i = 0; i < nnodes; ++i )
518  component[i] = -1;
519 
520  SCIP_CALL( SCIPallocMemoryArray(scip, &queue, nnodes) );
521 
522  for( i = 0; i < nnodes; ++i )
523  {
524  /* find first node that has not been visited yet and start BFS */
525  if( component[i] >= 0 )
526  continue;
527 
528  SCIPdebugMessage("found new component; starting at %i\n", i);
529  squeue = 0;
530  equeue = 1;
531  queue[0] = i;
532  curcomp = ncomps++;
533  component[i] = curcomp;
534 
535  /* dequeue a vertex as long as the queue is not empty */
536  while( equeue > squeue )
537  {
538  int curnode;
539  int* lastneighbour;
540  int* node;
541 
542  curnode = queue[squeue++];
543 
544  assert(curnode < nnodes);
545 
546  /* add unvisited neighbors of this vertex to the queue */
547  lastneighbour = tcliqueGetLastAdjedge(graph, curnode);
548  for( node = tcliqueGetFirstAdjedge(graph, curnode); node <= lastneighbour; ++node )
549  {
550  assert(*node < nnodes);
551 
552  if( component[*node] < 0 )
553  {
554  assert(equeue < nnodes);
555  component[*node] = curcomp;
556  queue[equeue++] = *node;
557  }
558  }
559  }
560  }
561 
562  detectordata->ncomponents = ncomps;
563  SCIPdebugMessage("found %i components\n", ncomps);
564 
565  SCIPfreeMemoryArray(scip, &queue);
566  return SCIP_OKAY;
567 }
568 
569 /* copy conshdldata data to decdecomp */
570 static
571 SCIP_RETCODE copyToDecdecomp(
572  SCIP* scip,
573  DEC_DETECTORDATA* detectordata,
574  DEC_DECOMP* decdecomp
575  )
576 {
577 
578  assert(scip != NULL);
579  assert(detectordata != NULL);
580  assert(decdecomp != NULL);
581 
582  SCIP_CALL( DECfilloutDecompFromConstoblock(scip, decdecomp, detectordata->constoblock, detectordata->nblocks, TRUE) );
583 
584  return SCIP_OKAY;
585 }
586 
588 static
589 DEC_DECL_FREEDETECTOR(detectorFreeStaircaseLsp)
590 { /*lint --e{715}*/
591  DEC_DETECTORDATA *detectordata;
592 
593  assert(scip != NULL);
594  assert(detector != NULL);
595 
596  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
597 
598  detectordata = DECdetectorGetData(detector);
599  assert(detectordata != NULL);
600 
601  delete detectordata->newToOld;
602  delete detectordata->oldToNew;
603 
604  SCIPfreeMemory(scip, &detectordata);
605 
606  return SCIP_OKAY;
607 }
608 
610 static
611 DEC_DECL_INITDETECTOR(detectorInitStaircaseLsp)
612 { /*lint --e{715}*/
613 
614  DEC_DETECTORDATA *detectordata;
615 
616  assert(scip != NULL);
617  assert(detector != NULL);
618 
619  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
620 
621  detectordata = DECdetectorGetData(detector);
622  assert(detectordata != NULL);
623 
624  detectordata->graph = NULL;
625  detectordata->components = NULL;
626  detectordata->ncomponents = 0;
627  detectordata->constoblock = NULL;
628  detectordata->vartoblock = NULL;
629  detectordata->nblocks = 0;
630 
631  return SCIP_OKAY;
632 }
633 
635 static
636 DEC_DECL_EXITDETECTOR(detectorExitStaircaseLsp)
637 { /*lint --e{715}*/
638  DEC_DETECTORDATA *detectordata;
639 
640  assert(scip != NULL);
641  assert(detector != NULL);
642 
643  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
644 
645  detectordata = DECdetectorGetData(detector);
646  assert(detectordata != NULL);
647 
648  if( detectordata->graph != NULL )
649  {
650  tcliqueFree(&detectordata->graph);
651  }
652 
653  if( detectordata->components != NULL )
654  {
655  SCIPfreeMemoryArray(scip, &detectordata->components);
656  }
657 
658  return SCIP_OKAY;
659 }
660 
662 static
663 DEC_DECL_DETECTSTRUCTURE(detectorDetectStaircaseLsp)
664 {
665  int i;
666  int j;
667  int* nodes;
668  int nnodes;
669  int* distances;
670  int* blocks;
671  int nblocks = 0;
672 
673  *result = SCIP_DIDNOTFIND;
674 
675  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting staircase structure:");
676 
677  SCIP_CALL( createGraph(scip, &(detectordata->graph)) );
678  SCIP_CALL( SCIPhashmapCreate(&detectordata->constoblock, SCIPblkmem(scip), SCIPgetNConss(scip)) );
679 
680  if( tcliqueGetNNodes(detectordata->graph) > 0 )
681  {
682  nnodes = tcliqueGetNNodes(detectordata->graph);
683  /* find connected components of the graph. the result will be stored in 'detectordata->components' */
684  SCIP_CALL( findConnectedComponents(scip, detectordata) );
685 
686  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes, nnodes) );
687  SCIP_CALL( SCIPallocMemoryArray(scip, &distances, nnodes) );
688  SCIP_CALL( SCIPallocMemoryArray(scip, &blocks, nnodes) );
689 
690  for( i = 0; i < nnodes; ++i)
691  blocks[i] = -1;
692 
693  /* find the diameter of each connected component */
694  for( i = 0; i < detectordata->ncomponents; ++i )
695  {
696  int diameter = 0;
697  int ncompsize = 0;
698 
699  SCIP_CALL( findDiameter(scip, detectordata, &diameter, &ncompsize, nodes, distances, i) );
700  SCIPdebugMessage("component %i has %i vertices and diameter %i\n", i, ncompsize, diameter);
701 
702  for( j = 0; j < ncompsize; j++ )
703  {
704  assert(nodes[j] >= 0);
705  assert(nodes[j] < nnodes);
706  assert(distances[j] >= 0);
707  assert(distances[j] <= diameter);
708  assert(distances[j] + nblocks < nnodes);
709 
710  blocks[nodes[j]] = nblocks + distances[j];
711  SCIPdebugMessage("\tnode %i to block %i\n", nodes[j], nblocks + distances[j]);
712  }
713 
714  nblocks += (diameter + 1);
715  }
716 
717  if( nblocks > 0 )
718  {
719  SCIP_CONS** conss = SCIPgetConss(scip);
720 
721  detectordata->nblocks = nblocks;
722 
723  for( i = 0; i < nnodes; ++i )
724  {
725  assert(blocks[i] >= 0);
726  SCIP_CALL( SCIPhashmapInsert(detectordata->constoblock, conss[i], (void*) (size_t) (blocks[i] + 1)) );
727  }
728 
729  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " found %d blocks.\n", detectordata->nblocks);
730  SCIP_CALL( SCIPallocMemoryArray(scip, decdecomps, 1) ); /*lint !e506*/
731  SCIP_CALL( DECdecompCreate(scip, &((*decdecomps)[0])) );
732  SCIP_CALL( copyToDecdecomp(scip, detectordata, (*decdecomps)[0]) );
733  *ndecdecomps = 1;
734  *result = SCIP_SUCCESS;
735  }
736 
737  SCIPfreeMemoryArray(scip, &blocks);
738  SCIPfreeMemoryArray(scip, &nodes);
739  SCIPfreeMemoryArray(scip, &distances);
740  SCIPfreeMemoryArray(scip, &(detectordata->components));
741  }
742 
743  if( *result != SCIP_SUCCESS )
744  {
745  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " not found.\n");
746  if( detectordata->constoblock != NULL )
747  SCIPhashmapFree(&detectordata->constoblock);
748  if( detectordata->vartoblock != NULL )
749  SCIPhashmapFree(&detectordata->vartoblock);
750  }
751 
752  tcliqueFree(&detectordata->graph);
753 
754  return SCIP_OKAY;
755 }
756 
758 static
759 SCIP_RETCODE detection(
760  SCIP* scip,
761  DEC_DETECTORDATA* detectordata,
762  Seeed_Propagation_Data* seeedPropagationData
763 )
764 {
765  int i;
766  int j;
767  int* nodes;
768  int nnodes;
769  int* distances;
770  int* blocks;
771  int nblocks = 0;
772 
773  char decinfo[SCIP_MAXSTRLEN];
774 
775  gcg::Seeedpool* seeedpool = seeedPropagationData->seeedpool;
776  gcg::Seeed* currseeed = new gcg::Seeed(seeedPropagationData->seeedToPropagate);
777 
778  SCIP_CLOCK* temporaryClock;
779  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
780  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
781 
782  currseeed->refineToMaster();
783 
784  currseeed->sort();
785 
786  //currseeed->showScatterPlot(seeedpool);
787 
788  //SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting staircase structure:");
789 
790  SCIP_CALL( createGraphFromPartialMatrix(scip, &(detectordata->graph), currseeed, seeedpool, detectordata) );
791  SCIP_CALL( SCIPhashmapCreate(&detectordata->constoblock, SCIPblkmem(scip), seeedpool->getNConss() ) );
792 
793  if( tcliqueGetNNodes(detectordata->graph) > 0 )
794  {
795  nnodes = tcliqueGetNNodes(detectordata->graph);
796 
797  /* find connected components of the graph. the result will be stored in 'detectordata->components' */
798  SCIP_CALL( findConnectedComponents(scip, detectordata) );
799 
800  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes, nnodes) );
801  SCIP_CALL( SCIPallocMemoryArray(scip, &distances, nnodes) );
802  SCIP_CALL( SCIPallocMemoryArray(scip, &blocks, nnodes) );
803 
804  for( i = 0; i < nnodes; ++i)
805  blocks[i] = -1;
806 
807  /* find the diameter of each connected component */
808  for( i = 0; i < detectordata->ncomponents; ++i )
809  {
810  int diameter = 0;
811  int ncompsize = 0;
812 
813  SCIP_CALL( findDiameter(scip, detectordata, &diameter, &ncompsize, nodes, distances, i) );
814  SCIPdebugMessage("component %i has %i vertices and diameter %i\n", i, ncompsize, diameter);
815 
816  for( j = 0; j < ncompsize; j++ )
817  {
818  assert(nodes[j] >= 0);
819  assert(nodes[j] < nnodes);
820  assert(distances[j] >= 0);
821  assert(distances[j] <= diameter);
822  assert(distances[j] + nblocks < nnodes);
823 
824  blocks[nodes[j]] = nblocks + distances[j];
825  SCIPdebugMessage("\tnode %i to block %i\n", nodes[j], nblocks + distances[j]);
826  }
827 
828  nblocks += (diameter + 1);
829  }
830  if( nblocks > 0 )
831  {
832  detectordata->nblocks = nblocks;
833 
834  for( i = 0; i < nnodes; ++i )
835  {
836  assert(blocks[i] >= 0);
837  SCIP_CALL( SCIPhashmapInsert(detectordata->constoblock, (void*) (size_t) detectordata->newToOld->at(i), (void*) (size_t) (blocks[i] + 1)) );
838  }
839  }
840 
841  SCIPfreeMemoryArray(scip, &blocks);
842  SCIPfreeMemoryArray(scip, &nodes);
843  SCIPfreeMemoryArray(scip, &distances);
844  SCIPfreeMemoryArray(scip, &(detectordata->components));
845  }
846 
847  SCIP_CALL( currseeed->assignSeeedFromConstoblock(detectordata->constoblock, nblocks) );
848 
849  currseeed->assignCurrentStairlinking();
850  currseeed->considerImplicits();
851  currseeed->sort();
852 
853  if( detectordata->constoblock != NULL )
854  SCIPhashmapFree(&detectordata->constoblock);
855  if( detectordata->vartoblock != NULL )
856  SCIPhashmapFree(&detectordata->vartoblock);
857 
858 
859  assert(currseeed->checkConsistency( ) );
860 
861  SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), 1) );
862  seeedPropagationData->newSeeeds[0] = currseeed;
863  seeedPropagationData->nNewSeeeds = 1;
864 
865  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "staircase\\_lsp");
866  seeedPropagationData->newSeeeds[0]->addDetectorChainInfo(decinfo);
867 
868  tcliqueFree(&detectordata->graph);
869 
870  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
871  seeedPropagationData->newSeeeds[0]->addClockTime( SCIPclockGetTime(temporaryClock ) );
872  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
873 
874 
875 
876  return SCIP_OKAY;
877 }
878 
879 
881 static
882 DEC_DECL_PROPAGATESEEED(detectorPropagateSeeedStaircaseLsp)
883 {
884 
885  DEC_DETECTORDATA* detectordata;
886  char decinfo[SCIP_MAXSTRLEN];
887  SCIP_CLOCK* temporaryClock;
888  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
889  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
890 
891 
892 
893  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
894  assert(detectordata != NULL);
895  detectordata->graph = NULL;
896  detectordata->constoblock = NULL;
897  detectordata->vartoblock = NULL;
898  detectordata->nblocks = 0;
899  detectordata->newToOld = NULL;
900  detectordata->oldToNew = NULL;
901  detectordata->components = NULL;
902  detectordata->ncomponents = 0;
903 
904  *result = SCIP_DIDNOTFIND;
905 
906  detection(scip, detectordata, seeedPropagationData);
907 
908  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "staircase-lsp");
909  seeedPropagationData->newSeeeds[0]->addDetectorChainInfo(decinfo);
910 
911  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
912  seeedPropagationData->newSeeeds[0]->addClockTime( SCIPclockGetTime(temporaryClock ) );
913  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
914 
915 
916 
917  delete detectordata->newToOld;
918  delete detectordata->oldToNew;
919 
920  SCIPfreeMemory(scip, &detectordata);
921 
922  *result = SCIP_SUCCESS;
923 
924  return SCIP_OKAY;
925 }
926 
927 static
928 DEC_DECL_FINISHSEEED(detectorFinishSeeedStaircaseLsp)
929 {
930  DEC_DETECTORDATA* detectordata;
931  char decinfo[SCIP_MAXSTRLEN];
932 
933  SCIP_CLOCK* temporaryClock;
934  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
935  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
936 
937 
938  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
939  assert(detectordata != NULL);
940  detectordata->graph = NULL;
941  detectordata->constoblock = NULL;
942  detectordata->vartoblock = NULL;
943  detectordata->nblocks = 0;
944  detectordata->newToOld = NULL;
945  detectordata->oldToNew = NULL;
946  detectordata->components = NULL;
947  detectordata->ncomponents = 0;
948 
949 
950  *result = SCIP_DIDNOTFIND;
951 
952  detection(scip, detectordata, seeedPropagationData);
953 
954 
955  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "staircase-lsp");
956  seeedPropagationData->newSeeeds[0]->addDetectorChainInfo(decinfo);
957 
958  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
959  seeedPropagationData->newSeeeds[0]->addClockTime( SCIPclockGetTime(temporaryClock ) );
960  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
961 
962 
963  delete detectordata->newToOld;
964  delete detectordata->oldToNew;
965 
966  SCIPfreeMemory(scip, &detectordata);
967 
968  *result = SCIP_SUCCESS;
969 
970  return SCIP_OKAY;
971 }
972 //#define detectorExitStaircase NULL
973 
974 #define detectorPostprocessSeeedStaircaseLsp NULL
975 
976 
977 static
978 DEC_DECL_SETPARAMFAST(setParamAggressiveStaircaseLsp)
979 {
980  char setstr[SCIP_MAXSTRLEN];
981  const char* name = DECdetectorGetName(detector);
982 
983  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
984  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
985 
986  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
987  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
988 
989  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
990  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
991 
992  return SCIP_OKAY;
993 
994 }
995 
996 static
997 DEC_DECL_SETPARAMFAST(setParamDefaultStaircaseLsp)
998 {
999  char setstr[SCIP_MAXSTRLEN];
1000  const char* name = DECdetectorGetName(detector);
1001 
1002  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
1003  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
1004 
1005  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
1006  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDORIGINAL) );
1007 
1008  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
1009  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
1010 
1011  return SCIP_OKAY;
1012 
1013 }
1014 
1015 
1016 
1017 static
1018 DEC_DECL_SETPARAMFAST(setParamFastStaircaseLsp)
1019 {
1020  char setstr[SCIP_MAXSTRLEN];
1021  const char* name = DECdetectorGetName(detector);
1022 
1023  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
1024  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
1025 
1026  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
1027  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
1028 
1029  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
1030  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
1031 
1032  return SCIP_OKAY;
1033 
1034 }
1035 
1036 
1037 /*
1038  * constraint specific interface methods
1039  */
1040 
1043  SCIP* scip
1044  )
1045 {
1046  DEC_DETECTORDATA* detectordata;
1047 
1048  /* for thread safety: create staircase constraint handler data in callback methods*/
1049  detectordata = NULL;
1050 
1051  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
1052  assert(detectordata != NULL);
1053  detectordata->graph = NULL;
1054  detectordata->constoblock = NULL;
1055  detectordata->vartoblock = NULL;
1056  detectordata->nblocks = 0;
1057  detectordata->newToOld = NULL;
1058  detectordata->oldToNew = NULL;
1059 
1060 
1063  DEC_USEFULRECALL, DEC_LEGACYMODE, detectordata, detectorDetectStaircaseLsp, detectorFreeStaircaseLsp,
1064  detectorInitStaircaseLsp, detectorExitStaircaseLsp, detectorPropagateSeeedStaircaseLsp, NULL, NULL, detectorFinishSeeedStaircaseLsp, detectorPostprocessSeeedStaircaseLsp, setParamAggressiveStaircaseLsp, setParamDefaultStaircaseLsp, setParamFastStaircaseLsp) );
1065 
1066 
1067  return SCIP_OKAY;
1068 }
SCIP_RETCODE considerImplicits()
: assigns every open cons/var in the following manner:
#define DEC_ENABLED
static SCIP_RETCODE findConnectedComponents(SCIP *scip, DEC_DETECTORDATA *detectordata)
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Seeed_Propagation_Data *seeedPropagationData)
gcg::Seeedpool * seeedpool
static DEC_DECL_INITDETECTOR(detectorInitStaircaseLsp)
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
#define DEC_FREQCALLROUNDORIGINAL
const int * getOpenconss()
returns array containing constraints not assigned yet
static DEC_DECL_PROPAGATESEEED(detectorPropagateSeeedStaircaseLsp)
TCLIQUE_GRAPH * graph
Definition: dec_staircase.c:87
void sort()
sorts the vars and conss datat structures by their indices
#define DEC_MINCALLROUND
std::vector< int > * oldToNew
#define DEC_MINCALLROUNDORIGINAL
#define DEC_FREQCALLROUND
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
#define DEC_MAXCALLROUNDORIGINAL
SCIP_HASHMAP * vartoblock
Definition: dec_staircase.c:86
#define DEC_DESC
#define DEC_DECCHAR
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
int getNConssForVar(int varIndex)
bool assignCurrentStairlinking()
assigns open vars to stairlinking if they can be found in exactly two consecutive blocks...
#define detectorPostprocessSeeedStaircaseLsp
static SCIP_DECL_SORTPTRCOMP(cmp)
SCIP_RETCODE refineToMaster()
refine seeed with focus on master: do obvious (
#define DEC_PRIORITY
static DEC_DECL_SETPARAMFAST(setParamAggressiveStaircaseLsp)
int getNConss()
returns the number of variables considered in the seeedpool
static DEC_DECL_FINISHSEEED(detectorFinishSeeedStaircaseLsp)
#define DEC_USEFULRECALL
#define TCLIQUE_CALL(x)
bool isVarOpenvar(int var)
returns true if the var is an open var
various SCIP helper methods
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
gcg::Seeed * seeedToPropagate
static DEC_DECL_EXITDETECTOR(detectorExitStaircaseLsp)
const int * getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
SCIP_RETCODE assignSeeedFromConstoblock(SCIP_HASHMAP *constoblock, int additionalNBlocks)
adds blocks and assigns open conss to such a new block or to master according to the cons assignment ...
SCIP_RETCODE SCIPincludeDetectorStaircaseLsp(SCIP *scip)
void addDetectorChainInfo(const char *decinfo)
adds a detectorchain information string to the corresponding vector (that carries information for eac...
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:467
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:489
static SCIP_RETCODE createGraphFromPartialMatrix(SCIP *scip, TCLIQUE_GRAPH **graph, gcg::Seeed *seeed, gcg::Seeedpool *seeedpool, DEC_DETECTORDATA *detectordata)
#define DEC_ENABLEDFINISHING
SCIP_HASHMAP * constoblock
static SCIP_RETCODE createGraph(SCIP *scip, TCLIQUE_GRAPH **graph)
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 enabledOriginal, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, SCIP_Bool legacymode, DEC_DETECTORDATA *detectordata, DEC_DECL_DETECTSTRUCTURE((*detectStructure)), DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATESEEED((*propagateSeeedDetector)), DEC_DECL_PROPAGATEFROMTOOLBOX((*propagateFromToolboxDetector)), DEC_DECL_FINISHFROMTOOLBOX((*finishFromToolboxDetector)), DEC_DECL_FINISHSEEED((*finishSeeedDetector)), DEC_DECL_POSTPROCESSSEEED((*postprocessSeeedDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
includes one detector
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1454
std::vector< int > * newToOld
#define DEC_LEGACYMODE
#define DEC_SKIP
static DEC_DECL_DETECTSTRUCTURE(detectorDetectStaircaseLsp)
bool isConsOpencons(int cons)
returns true if the cons is an open cons
static DEC_DECL_FREEDETECTOR(detectorFreeStaircaseLsp)
static SCIP_RETCODE findDiameter(SCIP *scip, DEC_DETECTORDATA *detectordata, int *maxdistance, int *ncomp, int *vertices, int *distances, int component)
int getNOpenconss()
returns size of vector containing constraints not assigned yet
#define DEC_DETECTORNAME
#define DEC_ENABLEDORIGINAL
class with functions for seeed pool where a seeed is a (potentially incomplete) description of a deco...
static SCIP_RETCODE copyToDecdecomp(SCIP *scip, DEC_DETECTORDATA *detectordata, DEC_DECOMP *decdecomp)
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
#define DEC_ENABLEDPOSTPROCESSING
bool checkConsistency()
returns true if the assignments in the seeed are consistent the following checks are performed: 1) ch...
SCIP_RESULT result
Definition: dec_dbscan.cpp:88
#define DEC_MAXCALLROUND
void addClockTime(SCIP_Real clocktime)
incorporates the needed time of a certain detector in the detector chain
interface data structure for the detector calling methods
constraint handler for structure detection
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
public methods for working with decomposition structures
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint