bliss.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 "bliss/graph.hh"
40 #include "pub_bliss.h"
41 #include "pub_gcgvar.h"
42 #include "scip_misc.h"
43 #include <cstring>
44 
45 static
46 int getSign(
47  SCIP* scip,
48  SCIP_Real val
49  )
50 {
51  if( SCIPisNegative(scip, val) )
52  return -1;
53  if( SCIPisPositive(scip, val) )
54  return 1;
55  else
56  return 0;
57 }
58 
60 static
61 int comp(
62  SCIP* scip,
63  SCIP_Real val1,
64  SCIP_Real val2,
65  SCIP_Bool onlysign
66  )
67 {
68  SCIP_Real compval1;
69  SCIP_Real compval2;
70 
71  if( onlysign )
72  {
73  compval1 = getSign(scip, val1);
74  compval2 = getSign(scip, val2);
75  }
76  else
77  {
78  compval1 = val1;
79  compval2 = val2;
80  }
81 
82 
83  if( SCIPisLT(scip, compval1, compval2) )
84  return -1;
85  if( SCIPisGT(scip, compval1, compval2) )
86  return 1;
87  else
88  return 0;
89 }
90 
92 static
93 int comp(
94  SCIP* scip,
95  AUT_CONS* cons1,
96  AUT_CONS* cons2,
97  SCIP_Bool onlysign
98  )
99 {
100  if( comp(scip, GCGconsGetRhs(scip, cons1->getCons()), GCGconsGetRhs(scip, cons2->getCons()), onlysign) != 0 )
101  return comp(scip, GCGconsGetRhs(scip, cons1->getCons()), GCGconsGetRhs(scip, cons2->getCons()), onlysign);
102  assert(SCIPisEQ(scip, GCGconsGetRhs(scip, cons1->getCons()), GCGconsGetRhs(scip, cons2->getCons())) || onlysign);
103 
104  if( comp(scip, GCGconsGetLhs(scip, cons1->getCons()), GCGconsGetLhs(scip, cons2->getCons()), onlysign) != 0 )
105  return comp(scip, GCGconsGetLhs(scip, cons1->getCons()), GCGconsGetLhs(scip, cons2->getCons()), onlysign);
106  assert(SCIPisEQ(scip, GCGconsGetLhs(scip, cons1->getCons()), GCGconsGetLhs(scip, cons2->getCons())) || onlysign);
107 
108  if( comp(scip, GCGconsGetNVars(scip, cons1->getCons()), GCGconsGetNVars(scip, cons2->getCons()), FALSE) != 0 )
109  return comp(scip, GCGconsGetNVars(scip, cons1->getCons()), GCGconsGetNVars(scip, cons2->getCons()), FALSE);
110  assert(SCIPisEQ(scip, GCGconsGetNVars(scip, cons1->getCons()), GCGconsGetNVars(scip, cons2->getCons())));
111 
112  return strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons1->getCons())), SCIPconshdlrGetName(SCIPconsGetHdlr(cons2->getCons())));
113 }
114 
115 
117 static
118 int comp(
119  SCIP* scip,
120  AUT_VAR* var1,
121  AUT_VAR* var2,
122  SCIP_Bool onlysign
123  )
124 {
125  SCIP_VAR* origvar1;
126  SCIP_VAR* origvar2;
127 
128  if( GCGvarIsPricing(var1->getVar()) )
129  origvar1 = GCGpricingVarGetOriginalVar(var1->getVar());
130  else
131  origvar1 = var1->getVar();
132 
133  if( GCGvarIsPricing(var2->getVar()) )
134  origvar2 = GCGpricingVarGetOriginalVar(var2->getVar());
135  else
136  origvar2 = var2->getVar();
137 
138  if( comp(scip, SCIPvarGetUbGlobal(origvar1), SCIPvarGetUbGlobal(origvar2), onlysign) != 0 )
139  return comp(scip, SCIPvarGetUbGlobal(origvar1), SCIPvarGetUbGlobal(origvar2), onlysign);
140  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(origvar1), SCIPvarGetUbGlobal(origvar2)) || onlysign);
141 
142  if( comp(scip, SCIPvarGetLbGlobal(origvar1), SCIPvarGetLbGlobal(origvar2), onlysign) != 0 )
143  return comp(scip, SCIPvarGetLbGlobal(origvar1), SCIPvarGetLbGlobal(origvar2), onlysign);
144  assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(origvar1), SCIPvarGetLbGlobal(origvar2)) || onlysign);
145 
146  if( comp(scip, SCIPvarGetObj((origvar1)), SCIPvarGetObj(origvar2), onlysign) != 0 )
147  return comp(scip, SCIPvarGetObj(origvar1), SCIPvarGetObj(origvar2), onlysign);
148  assert(SCIPisEQ(scip, SCIPvarGetObj(origvar1), SCIPvarGetObj(origvar2)) || onlysign);
149 
150  if( SCIPvarGetType(origvar1) < SCIPvarGetType(origvar2) )
151  return -1;
152  if( SCIPvarGetType(origvar1) > SCIPvarGetType(origvar2) )
153  return 1;
154  return 0;
155 }
156 
158 static
160 {
161  AUT_CONS* aut1 = (AUT_CONS*) elem1;
162  AUT_CONS* aut2 = (AUT_CONS*) elem2;
163  return comp(aut1->getScip(), aut1, aut2, FALSE);
164 }
165 
167 static
168 SCIP_DECL_SORTPTRCOMP(sortptrconssign)
169 {
170  AUT_CONS* aut1 = (AUT_CONS*) elem1;
171  AUT_CONS* aut2 = (AUT_CONS*) elem2;
172  return comp(aut1->getScip(), aut1, aut2, TRUE);
173 }
174 
176 static
178 {
179  AUT_VAR* aut1 = (AUT_VAR*) elem1;
180  AUT_VAR* aut2 = (AUT_VAR*) elem2;
181  return comp(aut1->getScip(), aut1, aut2, FALSE);
182 }
183 
185 static
186 SCIP_DECL_SORTPTRCOMP(sortptrvarsign)
187 {
188  AUT_VAR* aut1 = (AUT_VAR*) elem1;
189  AUT_VAR* aut2 = (AUT_VAR*) elem2;
190  return comp(aut1->getScip(), aut1, aut2, TRUE);
191 }
192 
194 static
196 {
197  AUT_COEF* aut1 = (AUT_COEF*) elem1;
198  AUT_COEF* aut2 = (AUT_COEF*) elem2;
199  return comp(aut1->getScip(), aut1->getVal(), aut2->getVal(), FALSE); /*lint !e864*/
200 }
201 
203 static
204 SCIP_DECL_SORTPTRCOMP(sortptrvalsign)
205 {
206  AUT_COEF* aut1 = (AUT_COEF*) elem1;
207  AUT_COEF* aut2 = (AUT_COEF*) elem2;
208  return comp(aut1->getScip(), aut1->getVal(), aut2->getVal(), TRUE); /*lint !e864*/
209 }
210 
211 
213 struct_colorinformation::struct_colorinformation()
214  : color(0), lenconssarray(0), lenvarsarray(0), lencoefsarray(0), alloccoefsarray(0),
215 ptrarraycoefs(NULL), ptrarrayvars(NULL), ptrarrayconss(NULL), onlysign(FALSE)
216 {
217 
218 }
219 
221 SCIP_RETCODE struct_colorinformation::insert(
222  AUT_VAR* svar,
223  SCIP_Bool* added
224  )
225 {
226  int pos;
227 
228  if( !onlysign )
229  {
230  if( !SCIPsortedvecFindPtr(ptrarrayvars, sortptrvar, svar, lenvarsarray, &pos) )
231  {
232  SCIPsortedvecInsertPtr(ptrarrayvars, sortptrvar, svar, &lenvarsarray, NULL);
233  *added = TRUE;
234  color++;
235  }
236  else
237  *added = FALSE;
238  }
239  else
240  {
241  if( !SCIPsortedvecFindPtr(ptrarrayvars, sortptrvarsign, svar, lenvarsarray, &pos) )
242  {
243  SCIPsortedvecInsertPtr(ptrarrayvars, sortptrvarsign, svar, &lenvarsarray, NULL);
244  *added = TRUE;
245  color++;
246  }
247  else
248  *added = FALSE;
249  }
250 
251 
252  return SCIP_OKAY;
253 }
254 
256 SCIP_RETCODE struct_colorinformation::insert(
257  AUT_CONS* scons,
258  SCIP_Bool* added
259  )
260 {
261  int pos;
262 
263  if( !onlysign )
264  {
265  if( !SCIPsortedvecFindPtr(ptrarrayconss, sortptrcons, scons,
266  lenconssarray, &pos) )
267  {
268  SCIPsortedvecInsertPtr(ptrarrayconss, sortptrcons, scons,
269  &lenconssarray, NULL);
270  *added = TRUE;
271  color++;
272  }
273  else
274  *added = FALSE;
275  }
276  else
277  {
278  if( !SCIPsortedvecFindPtr(ptrarrayconss, sortptrconssign, scons,
279  lenconssarray, &pos) )
280  {
281  SCIPsortedvecInsertPtr(ptrarrayconss, sortptrconssign, scons,
282  &lenconssarray, NULL);
283  *added = TRUE;
284  color++;
285  }
286  else
287  *added = FALSE;
288  }
289 
290  return SCIP_OKAY;
291 }
292 
294 SCIP_RETCODE struct_colorinformation::insert(
295  AUT_COEF* scoef,
296  SCIP_Bool* added
297  )
298 {
299  int pos;
300 
301  if( !onlysign )
302  {
303  if( !SCIPsortedvecFindPtr(ptrarraycoefs, sortptrval, scoef, lencoefsarray, &pos) )
304  {
305  int size = SCIPcalcMemGrowSize(scoef->getScip(), alloccoefsarray+1);
306  if( alloccoefsarray == 0 || lencoefsarray % alloccoefsarray == 0)
307  {
308  SCIP_CALL( SCIPreallocMemoryArray(scip, &ptrarraycoefs, size) );
309  alloccoefsarray = size;
310  }
311 
312  SCIPsortedvecInsertPtr(ptrarraycoefs, sortptrval, scoef, &lencoefsarray, NULL);
313  *added = TRUE;
314  color++;
315  }
316  else
317  *added = FALSE;
318  }
319  else
320  {
321  if( !SCIPsortedvecFindPtr(ptrarraycoefs, sortptrvalsign, scoef, lencoefsarray, &pos) )
322  {
323  int size = SCIPcalcMemGrowSize(scoef->getScip(), alloccoefsarray+1);
324  if( alloccoefsarray == 0 || lencoefsarray % alloccoefsarray == 0)
325  {
326  SCIP_CALL( SCIPreallocMemoryArray(scip, &ptrarraycoefs, size) );
327  alloccoefsarray = size;
328  }
329 
330  SCIPsortedvecInsertPtr(ptrarraycoefs, sortptrvalsign, scoef, &lencoefsarray, NULL);
331  *added = TRUE;
332  color++;
333  }
334  else
335  *added = FALSE;
336  }
337 
338  return SCIP_OKAY;
339 }
340 
341 int struct_colorinformation::get(
342  AUT_VAR svar
343  )
344 {
345  int pos;
346  SCIP_Bool found;
347  if( !onlysign )
348  found = SCIPsortedvecFindPtr(ptrarrayvars, sortptrvar, &svar, lenvarsarray, &pos);
349  else
350  found = SCIPsortedvecFindPtr(ptrarrayvars, sortptrvarsign, &svar, lenvarsarray, &pos);
351  return found ? pos : -1;
352 }
353 
354 int struct_colorinformation::get(
355  AUT_CONS scons
356  )
357 {
358  int pos;
359  SCIP_Bool found;
360  if( !onlysign )
361  found = SCIPsortedvecFindPtr(ptrarrayconss, sortptrcons, &scons, lenconssarray, &pos);
362  else
363  found = SCIPsortedvecFindPtr(ptrarrayconss, sortptrconssign, &scons, lenconssarray, &pos);
364  return found ? pos : -1;
365 }
366 
367 int struct_colorinformation::get(
368  AUT_COEF scoef
369  )
370 {
371  int pos;
372  SCIP_Bool found;
373  if( !onlysign )
374  found = SCIPsortedvecFindPtr(ptrarraycoefs, sortptrval, &scoef, lencoefsarray, &pos);
375  else
376  found = SCIPsortedvecFindPtr(ptrarraycoefs, sortptrvalsign, &scoef, lencoefsarray, &pos);
377  return found ? pos : -1;
378 }
379 
380 SCIP_RETCODE struct_colorinformation::setOnlySign(
381  SCIP_Bool onlysign_
382  )
383 {
384  onlysign = onlysign_;
385 
386  return SCIP_OKAY;
387 }
388 
389 
390 SCIP_Bool struct_colorinformation::getOnlySign()
391 {
392  return onlysign;
393 }
394 
395 
396 int struct_colorinformation::getLenVar()
397 {
398  return lenvarsarray;
399 }
400 
401 int struct_colorinformation::getLenCons()
402 {
403  return lenconssarray;
404 }
405 
406 SCIP_CONS* struct_cons::getCons()
407 {
408  return cons;
409 }
410 
411 SCIP* struct_cons::getScip()
412 {
413  return scip;
414 }
415 
416 SCIP_VAR* struct_var::getVar ()
417 {
418  return var;
419 }
420 
421 SCIP* struct_var::getScip()
422 {
423  return scip;
424 }
425 
426 SCIP* struct_coef::getScip()
427 {
428  return scip;
429 }
430 
431 SCIP_Real struct_coef::getVal()
432 {
433  return val;
434 }
435 
437 struct_var::struct_var(
438  SCIP* scip_,
439  SCIP_VAR* svar
440  )
441 {
442  scip = scip_;
443  var = svar;
444 }
445 
447 struct_cons::struct_cons(
448  SCIP* scip_,
449  SCIP_CONS* scons
450  )
451 {
452  scip = scip_;
453  cons = scons;
454 }
455 
457 struct_coef::struct_coef(
458  SCIP* scip_,
459  SCIP_Real val_
460  )
461 {
462  scip = scip_;
463  val = val_;
464 }
465 
466 
468 extern "C"
469 const char* GCGgetBlissVersion(void)
470 {
471  return bliss::version;
472 }
static SCIP_DECL_SORTPTRCOMP(sortptrcons)
Definition: bliss.cpp:159
struct struct_var AUT_VAR
Definition: pub_bliss.h:49
struct struct_cons AUT_CONS
Definition: pub_bliss.h:48
helper functions for automorphism detection
struct struct_coef AUT_COEF
Definition: pub_bliss.h:50
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
various SCIP helper methods
const char * GCGgetBlissVersion(void)
Definition: bliss.cpp:469
static int getSign(SCIP *scip, SCIP_Real val)
Definition: bliss.cpp:46
SCIP_VAR * GCGpricingVarGetOriginalVar(SCIP_VAR *var)
Definition: gcgvar.c:489
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:133
public methods for GCG variables
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:107
SCIP_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:205
static int comp(SCIP *scip, SCIP_Real val1, SCIP_Real val2, SCIP_Bool onlysign)
Definition: bliss.cpp:61