dec_colors.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 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 #include <assert.h>
40 #include <string.h>
41 
42 #include "dec_colors.h"
43 #include "cons_decomp.h"
44 #include "scip_misc.h"
45 #include "pub_decomp.h"
46 
47 #include <set>
48 #include <vector>
49 #include <bitset>
50 #include <iostream>
51 #include <algorithm>
52 
53 /* constraint handler properties */
54 #define DEC_DETECTORNAME "colors"
55 #define DEC_DESC "Detector according to color classes"
56 #define DEC_FREQCALLROUND 1
57 #define DEC_MAXCALLROUND INT_MAX
58 #define DEC_MINCALLROUND 0
59 #define DEC_FREQCALLROUNDORIGINAL 1
60 #define DEC_MAXCALLROUNDORIGINAL INT_MAX
61 #define DEC_MINCALLROUNDORIGINAL 0
62 #define DEC_PRIORITY 0
64 #define DEC_DECCHAR 'k'
66 #define DEC_ENABLED FALSE
67 #define DEC_ENABLED_ORIGINAL FALSE
68 #define DEC_ENABLEDFINISHING FALSE
69 #define DEC_ENABLEDPOSTPROCESSING FALSE
70 #define DEC_SKIP FALSE
71 #define DEC_USEFULRECALL FALSE
72 #define DEC_LEGACYMODE FALSE
74 /*
75  * Data structures
76  */
77 
80 {
81 };
82 
83 
84 /*
85  * Local methods
86  */
87 
88 struct ConsData {
89  SCIP* scip;
90  SCIP_Real lhs;
91  SCIP_Real rhs;
92  const char* conshdlrname;
93 
94  ConsData(SCIP* scip_, SCIP_CONS* cons) {
95  scip = scip_;
96  lhs = GCGconsGetLhs(scip, cons);
97  rhs = GCGconsGetRhs(scip, cons);
98  conshdlrname = SCIPconshdlrGetName(SCIPconsGetHdlr(cons));
99  }
100 
101  void print(void)
102  {
103  SCIPdebugMessage("Data: %s, lhs %.3f, rhs %.3f\n", conshdlrname, lhs, rhs);
104  }
105 };
106 
107 typedef struct ConsData CONSDATA;
108 
109 /* put your local methods here, and declare them static */
110 #ifdef SCIP_DEBUG
111 static
112 void printSubset(
113  std::vector<bool> bit_mask
114  )
115 {
116 
117  static int cnt = 0;
118  std::cout << ++cnt << ". [ ";
119  for( std::size_t i = 0; i < bit_mask.size(); ++i )
120  if( bit_mask[i] )
121  std::cout << i << ' ';
122  std::cout << "]\n";
123 }
124 #endif
125 
126 
127 static
129 {
130  CONSDATA* dat1 = (CONSDATA*)elem1;
131  CONSDATA* dat2 = (CONSDATA*)elem2;
132 
133  int result = strncmp(dat1->conshdlrname, dat2->conshdlrname, (size_t) SCIP_MAXSTRLEN);
134  if( result == 0)
135  {
136  if( SCIPisLT(dat1->scip, dat1->lhs, dat2->lhs) )
137  result = -1;
138  else if (SCIPisGT(dat1->scip, dat1->lhs, dat2->lhs) )
139  result = 1;
140  }
141  if( result == 0)
142  {
143  if( SCIPisLT(dat1->scip, dat1->rhs, dat2->rhs) )
144  result = -1;
145  else if (SCIPisGT(dat1->scip, dat1->rhs, dat2->rhs) )
146  result = 1;
147  }
148 
149  //SCIPdebugMessage("1 %s 2\n", result == 0 ? "=": (result < 0 ? "<" : ">"));
150  return result;
151 }
152 
153 static
154 SCIP_RETCODE assignConsColors(
155  SCIP* scip,
156  SCIP_CONS** conss,
157  int nconss,
158  int* colors,
159  int* ncolors
160 )
161 { /*lint -esym(593, data)*/
162 
163  CONSDATA** colordata = NULL;
164  int pos;
165 
166  assert(scip != NULL);
167  assert(conss != NULL);
168  assert(nconss > 0);
169  assert(colors != NULL);
170  assert(ncolors != NULL);
171 
172  SCIP_CALL( SCIPallocMemoryArray(scip, &colordata, nconss) );
173  *ncolors = 0;
174  for( int i = 0; i < nconss; ++i )
175  {
176  SCIP_CONS* cons = conss[i];
177  CONSDATA* data = new CONSDATA(scip, cons);
178 
179  if( !SCIPsortedvecFindPtr((void**)colordata, sortCons, data, *ncolors, &pos) )
180  {
181  SCIPsortedvecInsertPtr( (void**) colordata, sortCons, data, ncolors, &pos );
182  }
183  else
184  delete data;
185  }
186 
187  for( int i = 0; i < *ncolors; ++i)
188  {
189  colordata[i]->print();
190  }
191 
192  for( int i = 0; i < nconss; ++i )
193  {
194  SCIP_CONS* cons = conss[i];
195  CONSDATA* data = new CONSDATA(scip, cons);
196 
197  (void) SCIPsortedvecFindPtr( (void**) colordata, sortCons, data, *ncolors, &pos);
198  colors[i] = pos;
199  SCIPdebugMessage("Conss <%s> has color %d\n", SCIPconsGetName(conss[i]), pos);
200  delete data;
201  }
202 
203  SCIPfreeMemoryArray(scip, &colordata);
204  SCIPdebugMessage("%d colors found\n", *ncolors);
205  return SCIP_OKAY;
206 }
207 
208 
210 static
212  SCIP* scip,
213  SCIP_CONS*** masterconss,
214  int* nmasterconss,
215  int* colors,
216  std::set<int> colorset,
217  SCIP_Bool* masterisempty,
218  SCIP_Bool* pricingisempty
219  )
220 {
221  int i;
222 
223  SCIP_CONS** conss;
224  int nconss;
225 
226  assert(scip != NULL);
227  assert(masterconss != NULL);
228  assert(nmasterconss != NULL);
229  assert(masterisempty != NULL);
230  assert(pricingisempty != NULL);
231  conss = SCIPgetConss(scip);
232  nconss = SCIPgetNConss(scip);
233 
234  SCIP_CALL( SCIPallocMemoryArray(scip, masterconss, nconss) );
235  *nmasterconss = 0;
236 
237  for (i = 0; i < nconss; ++i)
238  {
239  if( colorset.find(colors[i]) != colorset.end() ) /*lint !e1702 std::pair*/
240  {
241  SCIPdebugMessage("Constraint <%s> to be placed in master.\n", SCIPconsGetName(conss[i]));
242  (*masterconss)[*nmasterconss] = conss[i];
243  ++(*nmasterconss);
244  }
245  }
246 
247  if( *nmasterconss > 0 )
248  {
249  SCIP_CALL( SCIPreallocMemoryArray(scip, masterconss, *nmasterconss) );
250  }
251  else
252  {
253  SCIPfreeMemoryArray(scip, masterconss);
254  *nmasterconss = 0;
255  *masterconss = NULL;
256  }
257 
258  *pricingisempty = (*nmasterconss == nconss);
259  *masterisempty = (*nmasterconss == 0);
260 
261  return SCIP_OKAY;
262 }
263 
264 static
266  std::vector<bool>& bit_mask
267  )
268 { /*lint -esym(1793,std::_Bit_reference::operator=)*/
269  std::size_t i = 0;
270  for( ; (i < bit_mask.size()) && bit_mask[i]; ++i )
271  bit_mask[i] = false;
272 
273  if( i < bit_mask.size() )
274  {
275  bit_mask[i] = true;
276  return true;
277  } else
278  return false;
279 }
280 
281 static
282 std::set<int> getSetFromBits(
283  std::vector<bool> bits
284 )
285 {
286  std::set<int> set;
287  for( size_t i = 0; i < bits.size(); ++i )
288  {
289  if( bits[i] )
290  (void) set.insert(int(i));
291  }
292  return set;
293 }
294 
295 static
297  int n,
298  int k
299  )
300 {
301  int result = 1;
302  for( int i = 1; i <= k; i++ )
303  {
304  result *= n - (k - i);
305  result /= i;
306  }
307  return result;
308 }
309 
311 static
312 SCIP_RETCODE findColorsComponents(
313  SCIP* scip,
314  DEC_DECOMP*** decomps,
315  int* ndecomps,
316  SCIP_RESULT* result
317  )
318 {
319 
320  SCIP_Bool masterisempty;
321  SCIP_Bool pricingisempty;
322  int* colors = NULL;
323  int ncolors = 0;
324  SCIP_CONS** conss = NULL;
325  int nconss = 0;
326  assert(scip != NULL);
327  assert(decomps != NULL);
328  assert(ndecomps != NULL);
329  assert(result != NULL);
330 
331  *ndecomps = 0;
332  *decomps = 0;
333  *result = SCIP_DIDNOTFIND;
334 
335  SCIP_CALL( SCIPallocMemoryArray(scip, &colors, SCIPgetNConss(scip)) ); /*lint !e666 */
336 
337  SCIP_CALL( assignConsColors(scip, SCIPgetConss(scip), SCIPgetNConss(scip), colors, &ncolors) );
338 
339  std::vector<bool> bit_mask((size_t)ncolors);
340 
341  SCIP_CALL( SCIPallocMemoryArray(scip, decomps, 1) ); /*lint !e506*/
342 
343  int nbits = 2;
344 
345  for( int subsetsize = 2; subsetsize <= nbits; ++subsetsize )
346  {
347  int size = nChooseK(ncolors, subsetsize);
348 
349  SCIP_CALL( SCIPreallocMemoryArray(scip, decomps, (size_t)*ndecomps + size) );
350 
351  do
352  {
353  if( std::count(bit_mask.begin(), bit_mask.end(), true) != subsetsize ) /*lint !e864*/
354  continue;
355 
356  std::set<int> colorset = getSetFromBits(bit_mask);
357 #ifdef SCIP_DEBUG
358  SCIPdebugMessage("Colors:");
359  for( std::set<int>::iterator it = colorset.begin(); it != colorset.end(); ++it)
360  {
361  SCIPdebugPrintf(" %d", *it);
362  }
363  SCIPdebugPrintf("\n");
364  printSubset(bit_mask);
365 #endif
366  SCIP_CALL( createMasterconssArray(scip, &conss, &nconss, colors, colorset, &masterisempty, &pricingisempty) );
367 
368  SCIP_CALL( DECcreateDecompFromMasterconss(scip, &((*decomps)[*ndecomps]), conss, nconss) );
369  ++(*ndecomps);
370 
371  } while( nextBitmask(bit_mask) );
372  }
373  if( *ndecomps > 0 )
374  {
375  SCIP_CALL( SCIPreallocMemoryArray(scip, decomps, *ndecomps) );
376  *result = SCIP_SUCCESS;
377  }
378 
379  SCIPfreeMemoryArrayNull(scip, &colors);
380 
381  return SCIP_OKAY;
382 }
383 
384 
385 
387 static
388 DEC_DECL_FREEDETECTOR(detectorFreeColors)
389 { /*lint --e{715}*/
390  DEC_DETECTORDATA *detectordata;
391 
392  assert(scip != NULL);
393  assert(detector != NULL);
394 
395  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
396 
397  detectordata = DECdetectorGetData(detector);
398  assert(detectordata != NULL);
399 
400  SCIPfreeMemory(scip, &detectordata);
401 
402  return SCIP_OKAY;
403 }
404 
406 static
407 DEC_DECL_DETECTSTRUCTURE(detectorDetectColors)
408 { /*lint -e715*/
409  *result = SCIP_DIDNOTFIND;
410 
411  *ndecdecomps = 0;
412  *decdecomps = NULL;
413 
414  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting colored structure:");
415 
416  SCIP_CALL( findColorsComponents(scip, decdecomps, ndecdecomps, result) );
417 
418  if( *result == SCIP_SUCCESS )
419  {
420  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " found %d decompositions.\n", *ndecdecomps);
421  }
422  else
423  {
424  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " not found.\n");
425  }
426 
427  if( *ndecdecomps == 0 )
428  {
429  SCIPfreeMemoryArrayNull(scip, decdecomps);
430  }
431 
432  return SCIP_OKAY;
433 }
434 
435 #define detectorPropagateSeeedColors NULL
436 #define detectorFinishSeeedColors NULL
437 #define detectorPostprocessSeeedColors NULL
438 #define detectorExitColors NULL
439 #define detectorInitColors NULL
440 
441 #define setParamAggressiveColors NULL
442 #define setParamDefaultColors NULL
443 #define setParamFastColor NULL
444 
445 
446 
447 /*
448  * detector specific interface methods
449  */
450 
452 extern "C"
454  SCIP* scip
455  )
456 {
457  DEC_DETECTORDATA* detectordata;
458 
459  /* create colors constraint handler data */
460  detectordata = NULL;
461 
462  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
463  assert(detectordata != NULL);
464 
465 
468 
469 
470  /* add colors constraint handler parameters */
471 
472  return SCIP_OKAY;
473 }
SCIP_Real rhs
Definition: dec_colors.cpp:91
static std::set< int > getSetFromBits(std::vector< bool > bits)
Definition: dec_colors.cpp:282
#define DEC_MINCALLROUNDORIGINAL
Definition: dec_colors.cpp:61
#define setParamDefaultColors
Definition: dec_colors.cpp:442
#define detectorPropagateSeeedColors
Definition: dec_colors.cpp:435
SCIP_Real lhs
Definition: dec_colors.cpp:90
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
#define DEC_MINCALLROUND
Definition: dec_colors.cpp:58
static SCIP_DECL_SORTPTRCOMP(sortCons)
Definition: dec_colors.cpp:128
struct ConsData CONSDATA
Definition: dec_colors.cpp:107
#define detectorFinishSeeedColors
Definition: dec_colors.cpp:436
#define detectorPostprocessSeeedColors
Definition: dec_colors.cpp:437
#define DEC_PRIORITY
Definition: dec_colors.cpp:62
#define DEC_FREQCALLROUNDORIGINAL
Definition: dec_colors.cpp:59
SCIP_RETCODE DECcreateDecompFromMasterconss(SCIP *scip, DEC_DECOMP **decomp, SCIP_CONS **masterconss, int nmasterconss)
Definition: decomp.c:2688
static DEC_DECL_DETECTSTRUCTURE(detectorDetectColors)
Definition: dec_colors.cpp:407
static SCIP_RETCODE assignConsColors(SCIP *scip, SCIP_CONS **conss, int nconss, int *colors, int *ncolors)
Definition: dec_colors.cpp:154
#define setParamAggressiveColors
Definition: dec_colors.cpp:441
#define setParamFastColor
Definition: dec_colors.cpp:443
static DEC_DECL_FREEDETECTOR(detectorFreeColors)
Definition: dec_colors.cpp:388
#define DEC_ENABLED
Definition: dec_colors.cpp:66
#define DEC_DETECTORNAME
Definition: dec_colors.cpp:54
various SCIP helper methods
#define detectorExitColors
Definition: dec_colors.cpp:438
#define DEC_FREQCALLROUND
Definition: dec_colors.cpp:56
#define DEC_MAXCALLROUNDORIGINAL
Definition: dec_colors.cpp:60
static SCIP_RETCODE findColorsComponents(SCIP *scip, DEC_DECOMP ***decomps, int *ndecomps, SCIP_RESULT *result)
Definition: dec_colors.cpp:312
#define DEC_MAXCALLROUND
Definition: dec_colors.cpp:57
const char * conshdlrname
Definition: dec_colors.cpp:92
SCIP * scip
Definition: dec_colors.cpp:89
void print(void)
Definition: dec_colors.cpp:101
ConsData(SCIP *scip_, SCIP_CONS *cons)
Definition: dec_colors.cpp:94
#define DEC_SKIP
Definition: dec_colors.cpp:70
#define DEC_ENABLEDPOSTPROCESSING
Definition: dec_colors.cpp:69
static int nChooseK(int n, int k)
Definition: dec_colors.cpp:296
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:107
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_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:205
#define DEC_ENABLED_ORIGINAL
Definition: dec_colors.cpp:67
detector assigning color classes to constraints and try combinations of colors in the master ...
static SCIP_RETCODE createMasterconssArray(SCIP *scip, SCIP_CONS ***masterconss, int *nmasterconss, int *colors, std::set< int > colorset, SCIP_Bool *masterisempty, SCIP_Bool *pricingisempty)
Definition: dec_colors.cpp:211
#define DEC_USEFULRECALL
Definition: dec_colors.cpp:71
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
#define DEC_ENABLEDFINISHING
Definition: dec_colors.cpp:68
#define detectorInitColors
Definition: dec_colors.cpp:439
SCIP_RESULT result
Definition: dec_dbscan.cpp:88
#define DEC_DECCHAR
Definition: dec_colors.cpp:64
constraint handler for structure detection
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
static bool nextBitmask(std::vector< bool > &bit_mask)
Definition: dec_colors.cpp:265
public methods for working with decomposition structures
#define DEC_LEGACYMODE
Definition: dec_colors.cpp:72
SCIP_RETCODE SCIPincludeDetectorColors(SCIP *scip)
Definition: dec_colors.cpp:453
#define DEC_DESC
Definition: dec_colors.cpp:55