Scippy

SCIP

Solving Constraint Integer Programs

cons_orbisack.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_orbisack.c
17  * @brief constraint handler for orbisack constraints
18  * @author Christopher Hojny
19  *
20  *
21  * The type of constraints of this constraint handler is described in cons_orbisack.h.
22  *
23  * The details of the method implemented here are described in the following papers:
24  *
25  * Describing Orbitopes by Linear Inequalities and Projection Based Tools@n
26  * Andreas Loos,@n
27  * PhD thesis, Otto-von-Guericke-Universitaet Magdeburg (2010).
28  *
29  * This thesis provides a complete linear description of orbisacks and a separation
30  * routine for its inequalities.
31  *
32  * Polytopes Associated with Symmetry Handling@n
33  * Christopher Hojny and Marc E. Pfetsch,@n
34  * (2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/01/5835.html
35  *
36  * This paper describes a linear time separation routine for so-called cover inequalities of
37  * orbisacks.
38  */
39 
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41 
42 #include <assert.h>
43 #include <string.h>
44 #include <ctype.h>
45 
46 #include "scip/cons_orbisack.h"
47 #include "scip/cons_orbitope.h"
48 #include "scip/cons_setppc.h"
49 
50 /* constraint handler properties */
51 #define CONSHDLR_NAME "orbisack"
52 #define CONSHDLR_DESC "symmetry breaking constraint handler for orbisacks"
53 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
54 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
55 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
56 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
57 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */
58 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
59  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
60 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
61 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
62 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
63 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
64 
65 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
66 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
67 
68 /* default parameters for separation routines: */
69 #define DEFAULT_ORBISEPARATION FALSE /**< whether orbisack inequalities should be separated */
70 #define DEFAULT_COVERSEPARATION TRUE /**< whether cover inequalities should be separated */
71 
72 /* default parameters for constraints */
73 #define DEFAULT_COEFFBOUND 1000000.0 /**< maximum size of coefficients in orbisack inequalities */
74 
75 #define DEFAULT_PPORBISACK TRUE /**< whether we allow upgrading to packing/partitioning orbisacks */
76 #define DEFAULT_CHECKALWAYSFEAS TRUE /**< whether check routine returns always SCIP_FEASIBLE */
77 
78 
79 /*
80  * Data structures
81  */
82 
83 /** constraint handler data */
84 struct SCIP_ConshdlrData
85 {
86  SCIP_Bool coverseparation; /**< whether only cover inequalities should be separated */
87  SCIP_Bool orbiseparation; /**< whether orbisack as well as cover inequalities should be separated */
88  SCIP_Real coeffbound; /**< maximum size of coefficients in orbisack inequalities */
89  SCIP_Bool checkpporbisack; /**< whether we allow upgrading to packing/partitioning orbisacks */
90  SCIP_Bool checkalwaysfeas; /**< whether check routine returns always SCIP_FEASIBLE */
91 };
92 
93 /** constraint data for orbisack constraints */
94 struct SCIP_ConsData
95 {
96  SCIP_VAR** vars1; /**< first column of variable matrix */
97  SCIP_VAR** vars2; /**< second column of variable matrix */
98  int nrows; /**< number of rows of variable matrix */
99 };
100 
101 
102 /*
103  * Local methods
104  */
105 
106 /** frees orbisack constraint data */
107 static
109  SCIP* scip, /**< SCIP data structure */
110  SCIP_CONSDATA** consdata /**< pointer to orbisack constraint data */
111  )
112 {
113  int nrows;
114 
115  assert( consdata != NULL );
116  assert( *consdata != NULL );
117 
118  nrows = (*consdata)->nrows;
119  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars2), nrows);
120  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars1), nrows);
121 
122  SCIPfreeBlockMemory(scip, consdata);
123 
124  return SCIP_OKAY;
125 }
126 
127 
128 /** creates orbisack constraint data */
129 static
131  SCIP* scip, /**< SCIP data structure */
132  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
133  SCIP_VAR*const* vars1, /**< first column of variable matrix */
134  SCIP_VAR*const* vars2, /**< second column of variable matrix */
135  int nrows /**< number of rows in variable matrix */
136  )
137 {
138  int i;
139 
140  assert( consdata != NULL );
141 
142  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
143 
144  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars1, vars1, nrows) );
145  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars2, vars2, nrows) );
146 
147 #ifndef NDEBUG
148  {
149  for (i = 0; i < nrows; ++i)
150  {
151  assert( SCIPvarIsBinary(vars1[i]) );
152  assert( SCIPvarIsBinary(vars2[i]) );
153  }
154  }
155 #endif
156 
157  (*consdata)->nrows = nrows;
158 
159  /* get transformed variables, if we are in the transformed problem */
160  if ( SCIPisTransformed(scip) )
161  {
162  /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_orbisack, since one cannot
163  * easily eliminate single variables from an orbisack constraint. */
164  for (i = 0; i < nrows; ++i)
165  {
166  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars1[i], &(*consdata)->vars1[i]) );
167  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars1[i]) );
168 
169  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars2[i], &(*consdata)->vars2[i]) );
170  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars2[i]) );
171  }
172  }
173 
174  return SCIP_OKAY;
175 }
176 
177 
178 /** check wether an orbisack is even a packing/partitioning orbisack */
179 static
181  SCIP* scip, /**< SCIP pointer */
182  SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
183  SCIP_VAR*const* vars2, /**< variables of second column */
184  int nrows, /**< number of rows of orbisack */
185  SCIP_Bool* success, /**< memory address to store whether constraint can be upgraded */
186  SCIP_Bool* isparttype /**< memory address to store whether upgraded orbisack is partitioning orbisack */
187  )
188 {
189  SCIP_CONSHDLR* setppcconshdlr;
190  SCIP_CONS** setppcconss;
191  SCIP_Bool* rowcovered;
192  int nsetppcconss;
193  int i;
194  int c;
195 
196  assert( scip != NULL );
197  assert( vars1 != NULL );
198  assert( vars2 != NULL );
199  assert( success != NULL );
200  assert( isparttype != NULL );
201 
202  *success = FALSE;
203 
204  /* get data of setppc conshdlr */
205  setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
206  if ( setppcconshdlr == NULL )
207  {
208  SCIPwarningMessage(scip, "Check for upgrading orbisacks to packing/partitioning orbisacks not possible - setppc constraint handler not found.\n");
209  return SCIP_OKAY;
210  }
211  setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
212  nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
213 
214  /* upgrade cannot be successful */
215  if ( nsetppcconss == 0 )
216  return SCIP_OKAY;
217  assert( setppcconss != NULL );
218 
219  SCIP_CALL( SCIPallocClearBufferArray(scip, &rowcovered, nrows) );
220 
221  /* iterate over orbisack rows and check whether rows are contained in partitioning constraints */
222  *success = TRUE;
223  for (i = 0; i < nrows; ++i)
224  {
225  /* iterate over constraints */
226  for (c = 0; c < nsetppcconss; ++c)
227  {
228  int nsetppcvars;
229  SCIP_VAR** setppcvars;
230  SCIP_VAR* var;
231  int varidx1;
232  int varidx2;
233 
234  /* check type */
235  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING ||
236  SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING )
237  continue;
238  assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING );
239 
240  /* get set packing/partitioning variables */
241  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
242  assert( nsetppcvars > 0 );
243 
244  /* partitioning constraint contains too much variables */
245  if ( nsetppcvars != 2 )
246  continue;
247  assert( nsetppcvars == 2 );
248 
249  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
250  assert( setppcvars != NULL );
251 
252  /* check whether i-th row is contained in partitioning constraint */
253  var = setppcvars[0];
254  if ( SCIPvarIsNegated(var) )
255  continue;
256 
257  varidx1 = SCIPvarGetProbindex(var);
258 
259  var = setppcvars[1];
260  if ( SCIPvarIsNegated(var) )
261  continue;
262 
263  varidx2 = SCIPvarGetProbindex(var);
264 
265  if ( (varidx1 == SCIPvarGetProbindex(vars1[i]) && varidx2 == SCIPvarGetProbindex(vars2[i])) ||
266  (varidx2 == SCIPvarGetProbindex(vars1[i]) && varidx1 == SCIPvarGetProbindex(vars2[i])))
267  {
268  rowcovered[i] = TRUE;
269  break;
270  }
271  }
272 
273  /* no partitioning constraint corresponds to row i */
274  if ( c >= nsetppcconss )
275  *success = FALSE;
276  }
277 
278  if ( *success )
279  {
280  *isparttype = TRUE;
281  SCIPfreeBufferArray(scip, &rowcovered);
282 
283  return SCIP_OKAY;
284  }
285 
286  /* Iterate over orbisack rows and check whether rows are contained in packing constraints.
287  * In particular, it is possible that variables in row i form a subset of variables in the
288  * a packing/partitioning constraint. */
289  *success = TRUE;
290  for (i = 0; i < nrows; ++i)
291  {
292  /* skip already covered rows */
293  if ( rowcovered[i] )
294  continue;
295 
296  /* iterate over constraints */
297  for (c = 0; c < nsetppcconss; ++c)
298  {
299  SCIP_VAR** setppcvars;
300  SCIP_VAR* var;
301  int nsetppcvars;
302  int varidx;
303  int nfound = 0;
304  int j;
305 
306  /* check type */
307  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
308  continue;
309  assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING ||
310  SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING );
311 
312  /* get set packing/partitioning variables */
313  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
314  assert( nsetppcvars > 0 );
315 
316  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
317  assert( setppcvars != NULL );
318 
319  /* check whether all variables of the cycle are contained in setppc constraint */
320  for (j = 0; j < nsetppcvars && nfound < 2; ++j)
321  {
322  var = setppcvars[j];
323 
324  if ( SCIPvarIsNegated(var) )
325  continue;
326 
327  varidx = SCIPvarGetProbindex(var);
328 
329  if ( varidx == SCIPvarGetProbindex(vars1[i]) || varidx == SCIPvarGetProbindex(vars2[i]) )
330  ++nfound;
331  }
332 
333  if ( nfound == 2 )
334  break;
335  }
336 
337  /* row i is not contained in an setppc constraint */
338  if ( c >= nsetppcconss )
339  *success = FALSE;
340  }
341 
342  /* we have found a packing orbisack */
343  if ( *success )
344  *isparttype = FALSE;
345 
346  SCIPfreeBufferArray(scip, &rowcovered);
347 
348  return SCIP_OKAY;
349 }
350 
351 
352 /** generate initial LP cut
353  *
354  * We generate the inequality of the orbisack on the elements of the first row, i.e.,
355  * the inequality \f$-x_{1,1} + x_{1,2} \leq 0\f$.
356  */
357 static
359  SCIP* scip, /**< SCIP pointer */
360  SCIP_CONS* cons, /**< constraint */
361  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
362  )
363 {
364  SCIP_CONSDATA* consdata;
365  SCIP_VAR** vars1;
366  SCIP_VAR** vars2;
367  SCIP_VAR* tmpvars[2];
368  SCIP_ROW* row;
369 
370  assert( scip != NULL );
371  assert( cons != NULL );
372  assert( infeasible != NULL );
373 
374  *infeasible = FALSE;
375 
376  consdata = SCIPconsGetData(cons);
377  assert( consdata != 0 );
378  assert( consdata->nrows > 0 );
379  assert( consdata->vars1 != NULL );
380  assert( consdata->vars2 != NULL );
381 
382  vars1 = consdata->vars1;
383  vars2 = consdata->vars2;
384 
385  tmpvars[0] = vars1[0];
386  tmpvars[1] = vars2[0];
387 
388  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), "orbisack0#0", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
389  SCIP_CALL( SCIPaddVarToRow(scip, row, tmpvars[0], -1.0) );
390  SCIP_CALL( SCIPaddVarToRow(scip, row, tmpvars[1], 1.0) );
391 
392  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
393 #ifdef SCIP_DEBUG
394  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
395 #endif
396  SCIP_CALL( SCIPreleaseRow(scip, &row) );
397 
398  return SCIP_OKAY;
399 }
400 
401 
402 /** add orbisack cover inequality */
403 static
405  SCIP* scip, /**< SCIP pointer */
406  SCIP_CONS* cons, /**< constraint */
407  int nrows, /**< number of rows of orbisack */
408  SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
409  SCIP_VAR*const* vars2, /**< variables of second column */
410  SCIP_Real* coeffs1, /**< coefficients of the variables of the first column of the inequality to be added */
411  SCIP_Real* coeffs2, /**< coefficients of the variables of the second column of the inequality to be added */
412  SCIP_Real rhs, /**< right-hand side of inequality to be added */
413  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
414  )
415 {
416  SCIP_ROW* row;
417  int i;
418 
419  assert( scip != NULL );
420  assert( cons != NULL );
421  assert( vars1 != NULL );
422  assert( vars2 != NULL );
423  assert( coeffs1 != NULL );
424  assert( coeffs2 != NULL );
425  assert( infeasible != NULL );
426 
427  *infeasible = FALSE;
428 
429  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
430  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
431  for (i = 0; i < nrows; ++i)
432  {
433  SCIP_CALL( SCIPaddVarToRow(scip, row, vars1[i], coeffs1[i]) );
434  SCIP_CALL( SCIPaddVarToRow(scip, row, vars2[i], coeffs2[i]) );
435  }
436  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
437 
438  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
439 #ifdef SCIP_DEBUG
440  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
441 #endif
442  SCIP_CALL( SCIPreleaseRow(scip, &row) );
443 
444  return SCIP_OKAY;
445 }
446 
447 
448 /** Separate lifted orbisack cover inequalities
449  *
450  * We currently do NOT enter cuts into the pool.
451  *
452  * We iterate over the nrows-many cover inequalities which are potentially
453  * maximal w.r.t. their violation.
454  */
455 static
457  SCIP* scip, /**< SCIP pointer */
458  SCIP_CONS* cons, /**< constraint */
459  int nrows, /**< number of rows of orbisack */
460  SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
461  SCIP_VAR*const* vars2, /**< variables of second column */
462  SCIP_Real* vals1, /**< LP-solution for those variables in first column */
463  SCIP_Real* vals2, /**< LP-solution for those variables in second column */
464  int* ngen, /**< number of separated covers */
465  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
466  )
467 {
468  SCIP_Real rhs = 0.0;
469  SCIP_Real lhs = 0.0;
470  SCIP_Real* coeff1;
471  SCIP_Real* coeff2;
472  int i;
473 
474  assert( scip != NULL );
475  assert( cons != NULL );
476  assert( nrows > 0 );
477  assert( vars1 != NULL );
478  assert( vars2 != NULL );
479  assert( infeasible != NULL );
480  assert( ngen != NULL );
481 
482  *infeasible = FALSE;
483  *ngen = 0;
484 
485  /* allocate memory for inequality coefficients */
486  SCIP_CALL( SCIPallocBufferArray(scip, &coeff1, nrows) );
487  SCIP_CALL( SCIPallocBufferArray(scip, &coeff2, nrows) );
488 
489  /* initialize coefficient matrix */
490  for (i = 0; i < nrows; ++i)
491  {
492  coeff1[i] = 0.0;
493  coeff2[i] = 0.0;
494  }
495 
496  /* detect violated covers */
497  for (i = 0; i < nrows; ++i)
498  {
499  /* cover inequality is violated */
500  if ( SCIPisEfficacious(scip, -vals1[i] + vals2[i] + lhs - rhs) )
501  {
502  /* set coefficients for inequality */
503  coeff1[i] = -1.0;
504  coeff2[i] = 1.0;
505 
506  SCIP_CALL( addOrbisackCover(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) );
507  ++(*ngen);
508  if ( *infeasible )
509  break;
510 
511  /* reset coefficients for next inequality */
512  coeff1[i] = 0.0;
513  coeff2[i] = 0.0;
514  }
515 
516  /* add argmax( 1 - vals[i][0], vals[i][1] ) as coefficient and ensure that both vars1[0] and vars2[0] are
517  * contained in the LIFTED cover inequality */
518  if ( SCIPisEfficacious(scip, 1.0 - vals1[i] - vals2[i]) )
519  {
520  coeff1[i] = -1.0;
521  lhs = lhs - vals1[i];
522 
523  /* lifting */
524  if ( i == 0 )
525  {
526  coeff2[0] = 1.0;
527  lhs += vals2[i];
528  }
529  }
530  else
531  {
532  coeff2[i] = 1.0;
533  rhs += 1.0;
534  lhs = lhs + vals2[i];
535 
536  /* lifting */
537  if ( i == 0 )
538  {
539  coeff1[0] = -1.0;
540  lhs -= vals1[i];
541  rhs -= 1.0;
542  }
543  }
544  }
545 
546  /* free coefficient matrix */
547  SCIPfreeBufferArray(scip, &coeff2);
548  SCIPfreeBufferArray(scip, &coeff1);
549 
550  return SCIP_OKAY;
551 }
552 
553 
554 /** add orbisack inequality */
555 static
557  SCIP* scip, /**< SCIP pointer */
558  SCIP_CONS* cons, /**< constraint */
559  int nrows, /**< number of rows of orbisack */
560  SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
561  SCIP_VAR*const* vars2, /**< variables of second column */
562  SCIP_Real* coeffs1, /**< first column of coefficient matrix of inequality to be added */
563  SCIP_Real* coeffs2, /**< second column of coefficient matrix of inequality to be added */
564  SCIP_Real rhs, /**< right-hand side of inequality to be added */
565  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
566  )
567 {
568  SCIP_ROW* row;
569  int i;
570 
571  assert( scip != NULL );
572  assert( cons != NULL );
573  assert( vars1 != NULL );
574  assert( vars2 != NULL );
575  assert( coeffs1 != NULL );
576  assert( coeffs2 != NULL );
577  assert( infeasible != NULL );
578 
579  *infeasible = FALSE;
580 
581  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), "orbisack", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
582  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
583 
584  for (i = 0; i < nrows; ++i)
585  {
586  SCIP_CALL( SCIPaddVarToRow(scip, row, vars1[i], coeffs1[i]) );
587  SCIP_CALL( SCIPaddVarToRow(scip, row, vars2[i], coeffs2[i]) );
588  }
589  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
590 
591  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
592 #ifdef SCIP_DEBUG
593  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
594 #endif
595  SCIP_CALL( SCIPreleaseRow(scip, &row) );
596 
597  return SCIP_OKAY;
598 }
599 
600 
601 /** separate orbisack inequalities
602  *
603  * We currently do NOT enter cuts into the pool.
604  *
605  * We stop if we checked for each possible basement row, whether a cut could be added. If the coefficients grow too
606  * large, we start separating cover inequalities.
607  *
608  * We implement the separation algorithm for orbisacks described in@n
609  * A. Loos. Describing Orbitopes by Linear Inequalities and Projection Based Tools.
610  * PhD thesis, Otto-von-Guericke-Universitaet Magdeburg, 2010.
611  */
612 static
614  SCIP* scip, /**< SCIP pointer */
615  SCIP_CONS* cons, /**< constraint */
616  int nrows, /**< number of rows of orbisack */
617  SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
618  SCIP_VAR*const* vars2, /**< variables of second column */
619  SCIP_Real* vals1, /**< LP-solution for those variables in first column */
620  SCIP_Real* vals2, /**< LP-solution for those variables in second column */
621  SCIP_Bool coverseparation, /**< whether we separate cover inequalities */
622  SCIP_Real coeffbound, /**< maximum size of coefficients in orbisack inequalities */
623  int* ngen, /**< pointer to store the number of generated cuts */
624  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
625  )
626 {
627  SCIP_Real* coeff1;
628  SCIP_Real* coeff2;
629  SCIP_Real rhs;
630  SCIP_Real lhs;
631  SCIP_Real valueA;
632  SCIP_Real valueB;
633  SCIP_Real valueC;
634  int basement;
635  int i;
636 
637  assert( scip != NULL );
638  assert( cons != NULL );
639  assert( nrows > 0 );
640  assert( vars1 != NULL );
641  assert( vars2 != NULL );
642  assert( coeffbound >= 0.0 );
643  assert( ngen != NULL );
644  assert( infeasible != NULL );
645 
646  *infeasible = FALSE;
647  *ngen = 0;
648 
649  /* if there is only one row, all cuts are added by initLP */
650  if ( nrows < 2 )
651  return SCIP_OKAY;
652 
653  /* allocate memory for inequality coefficients */
654  SCIP_CALL( SCIPallocBufferArray(scip, &coeff1, nrows) );
655  SCIP_CALL( SCIPallocBufferArray(scip, &coeff2, nrows) );
656 
657  /* initialize coefficient matrix row 0 */
658  coeff1[0] = -1.0;
659  coeff2[0] = 1.0;
660  for (i = 2; i < nrows; ++i)
661  {
662  coeff1[i] = 0.0;
663  coeff2[i] = 0.0;
664  }
665 
666  /* initialize right-hand side and left-hand side (lhs for row 0) */
667  rhs = 0.0;
668  lhs = - vals1[0] + vals2[0];
669 
670  /* basement row of orbisack */
671  basement = 1;
672 
673  /* update value of left-hand side and coefficients for basement row = 1 */
674  lhs += - vals1[1] + vals2[1];
675  coeff1[1] = -1.0;
676  coeff2[1] = 1.0;
677 
678  /* check whether cut for basement row = 1 is violated */
679  if ( SCIPisEfficacious(scip, lhs - rhs) )
680  {
681  SCIP_CALL( addOrbisackInequality(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) );
682  ++(*ngen);
683  }
684 
685  /* check whether there exists a cut with basement rows > 1 that is violated */
686  while ( basement < nrows - 1 && ! *infeasible )
687  {
688  valueA = lhs + vals1[basement] - vals1[basement + 1] + vals2[basement + 1] - rhs - 1.0; /*lint !e679, !e834*/
689  valueB = lhs - vals2[basement] - vals1[basement + 1] + vals2[basement + 1] - rhs; /*lint !e679, !e834*/
690  valueC = 2.0 * lhs + vals1[basement] - vals2[basement] - vals1[basement + 1] + vals2[basement + 1] - 2.0 * rhs; /*lint !e679, !e834*/
691 
692  /* update inequality */
693  if ( valueA >= valueB && valueA >= valueC )
694  {
695  ++rhs;
696  coeff1[basement] = 0.0;
697  lhs += vals1[basement++];
698  coeff1[basement] = -1.0;
699  coeff2[basement] = 1.0;
700  lhs += - vals1[basement] + vals2[basement];
701  }
702  else if ( valueB >= valueA && valueB >= valueC )
703  {
704  coeff2[basement] = 0.0;
705  lhs -= vals2[basement++];
706  coeff1[basement] = -1.0;
707  coeff2[basement] = 1.0;
708  lhs += - vals1[basement] + vals2[basement];
709  }
710  else
711  {
712  rhs *= 2.0;
713  lhs = 0.0;
714  for (i = 0; i < basement; ++i)
715  {
716  coeff1[i] = 2.0 * coeff1[i];
717  coeff2[i] = 2.0 * coeff2[i];
718  lhs += coeff1[i] * vals1[i] + coeff2[i] * vals2[i];
719  }
720  coeff1[basement] = -1.0;
721  coeff2[basement] = 1.0;
722  lhs -= vals1[basement];
723  lhs += vals2[basement++];
724  coeff1[basement] = -1.0;
725  coeff2[basement] = 1.0;
726  lhs -= vals1[basement];
727  lhs += vals2[basement];
728  }
729 
730  /* to avoid numerical troubles, we bound the size of coefficients and rhs */
731  if ( rhs > coeffbound || -coeff1[0] > coeffbound || coeff2[0] > coeffbound )
732  {
733  /* avoid separating cover inequalities twice */
734  if ( ! coverseparation )
735  {
736  int ncuts;
737  SCIP_CALL( separateOrbisackCovers(scip, cons, nrows, vars1, vars2, vals1, vals2, &ncuts, infeasible) );
738  *ngen += ncuts;
739  }
740  break;
741  }
742 
743  /* if current inequality is violated */
744  if ( SCIPisEfficacious(scip, lhs - rhs) )
745  {
746  SCIP_CALL( addOrbisackInequality(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) );
747  ++(*ngen);
748  }
749  }
750 
751  /* free allocated memory */
752  SCIPfreeBufferArray(scip, &coeff2);
753  SCIPfreeBufferArray(scip, &coeff1);
754 
755  return SCIP_OKAY;
756 }
757 
758 
759 /** propagation */
760 static
762  SCIP* scip, /**< SCIP pointer */
763  SCIP_CONS* cons, /**< constraint to be propagated */
764  SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */
765  SCIP_Bool* found, /**< pointer to store whether a new propagation could be found */
766  int* ngen /**< pointer to store the number of generated bound strengthenings */
767  )
768 {
769  SCIP_CONSDATA* consdata;
770  SCIP_VAR** vars1;
771  SCIP_VAR** vars2;
772  SCIP_Bool tightened = FALSE;
773  SCIP_VAR* var;
774  SCIP_Real ub;
775  SCIP_Real lb;
776  SCIP_VAR* var1;
777  SCIP_VAR* var2;
778  int* solu1;
779  int* solu2;
780  int nrows;
781  int i;
782  int r;
783 
784  assert( scip != NULL );
785  assert( cons != NULL );
786  assert( infeasible != NULL );
787  assert( ngen != NULL );
788  assert( found != NULL );
789 
790  SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons));
791 
792  *ngen = 0;
793  *infeasible = FALSE;
794  *found = FALSE;
795 
796  /* get data of constraint */
797  consdata = SCIPconsGetData(cons);
798  assert( consdata != NULL );
799  assert( consdata->vars1 != NULL );
800  assert( consdata->vars2 != NULL );
801  assert( consdata->nrows > 0 );
802 
803  nrows = consdata->nrows;
804  vars1 = consdata->vars1;
805  vars2 = consdata->vars2;
806 
807  /* determine current solution */
808  SCIP_CALL( SCIPallocBufferArray(scip, &solu1, nrows) );
809  SCIP_CALL( SCIPallocBufferArray(scip, &solu2, nrows) );
810 
811  for (i = 0; i < nrows; ++i)
812  {
813  /* determine value in first column */
814  var = vars1[i];
815  assert( SCIPvarIsBinary(var) );
816 
817  /* get local upper and lower bound on variable */
818  ub = SCIPvarGetUbLocal(var);
819  lb = SCIPvarGetLbLocal(var);
820 
821  /* if variable is fixed to 1 -> solu[i][j] = 1,
822  * if it is fixed to 0 -> solu[i][j] = 0,
823  * else, -> solu[i][j] = 2 */
824  if ( lb > 0.5 )
825  solu1[i] = 1;
826  else if (ub < 0.5)
827  solu1[i] = 0;
828  else
829  solu1[i] = 2;
830 
831  /* determine value in second column */
832  var = vars2[i];
833  assert( SCIPvarIsBinary(var) );
834 
835  /* get local upper and lower bound on variable */
836  ub = SCIPvarGetUbLocal(var);
837  lb = SCIPvarGetLbLocal(var);
838 
839  /* if variable is fixed to 1 -> solu[i][j] = 1,
840  * if it is fixed to 0 -> solu[i][j] = 0,
841  * else, -> solu[i][j] = 2 */
842  if ( lb > 0.5 )
843  solu2[i] = 1;
844  else if (ub < 0.5)
845  solu2[i] = 0;
846  else
847  solu2[i] = 2;
848  }
849 
850  /* loop through all variables */
851  for (i = 0; i < nrows; ++i)
852  {
853  /* get variables of first and second column */
854  var1 = vars1[i];
855  var2 = vars2[i];
856  assert( var1 != NULL );
857  assert( var2 != NULL );
858 
859  /* if variable in first column is fixed to 0 and variable in second column is fixed to 1 */
860  if ( SCIPvarGetUbLocal(var1) < 0.5 && SCIPvarGetLbLocal(var2) > 0.5 )
861  {
862  SCIP_Bool nocritical = TRUE;
863 
864  SCIPdebugMsg(scip, "Check variable pair (%d,0) and (%d,1).\n", i, i);
865 
866  /* check whether there is a critical row above row i, otherwise the solution is infeasible
867  * if there is a row without fixing (2) above the current row, we cannot obtain a result */
868  for (r = 0; r < i; ++r)
869  {
870  if ( (solu1[r] == 1 && solu2[r] == 0) || solu1[r] == 2 || solu2[r] == 2 )
871  {
872  nocritical = FALSE;
873  break;
874  }
875  }
876 
877  if ( nocritical )
878  {
879  SCIPdebugMsg(scip, " -> node infeasible (row was fixed to 0,1 but there was no critical row above).\n");
880 
881  /* perform conflict analysis */
883  {
885 
886  for (r = 0; r <= i; ++r)
887  {
888  SCIP_CALL( SCIPaddConflictBinvar(scip, vars1[r]) );
889  SCIP_CALL( SCIPaddConflictBinvar(scip, vars2[r]) );
890  }
891 
892  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
893 
894  *infeasible = TRUE;
895 
896  /* free current solution */
897  SCIPfreeBufferArray(scip, &solu2);
898  SCIPfreeBufferArray(scip, &solu1);
899 
900  return SCIP_OKAY;
901  }
902  }
903  }
904  /* if variable in the first column is fixed to 0 and the variable in the second column is free */
905  else if ( SCIPvarGetUbLocal(var1) < 0.5 && SCIPvarGetUbLocal(var2) > 0.5 )
906  {
907  SCIP_Bool allconstant = TRUE;
908 
909  SCIPdebugMsg(scip, "Check variable pair (%d,0) and (%d,1).\n", i, i);
910 
911  /* Check whether all rows above row i are constant. In this case, the variable in the second */
912  /* column can be fixed to 0. If an entry above row i is unfixed or a row is not constant, we cannot */
913  /* fix the second entry in row i. */
914  for (r = 0; r < i; ++r)
915  {
916  if ( solu1[r] == 2 || solu2[r] == 2 || solu1[r] != solu2[r] )
917  {
918  allconstant = FALSE;
919  break;
920  }
921  }
922 
923  /* fix variable in the second column to 0 */
924  if ( allconstant )
925  {
926  assert( SCIPvarGetLbLocal(var2) < 0.5 );
927  SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
928  assert( ! *infeasible );
929 
930  *found = *found || tightened;
931  if ( tightened )
932  ++(*ngen);
933  }
934  }
935  }
936 
937  /* free current solution */
938  SCIPfreeBufferArray(scip, &solu2);
939  SCIPfreeBufferArray(scip, &solu1);
940 
941  return SCIP_OKAY;
942 }
943 
944 
945 /** separate orbisack and cover inequalities */
946 static
948  SCIP* scip, /**< pointer to scip */
949  SCIP_RESULT* result, /**< pointer to store the result of separation */
950  SCIP_CONS* cons, /**< constraint */
951  int nrows, /**< number of rows of orbisack */
952  SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
953  SCIP_VAR*const* vars2, /**< variables of second column */
954  SCIP_Real* vals1, /**< LP-solution for those variables in first column */
955  SCIP_Real* vals2 /**< LP-solution for those variables in second column */
956  )
957 {
958  SCIP_CONSHDLRDATA* conshdlrdata;
959  SCIP_Bool infeasible = FALSE;
960  int ngen1 = 0;
961  int ngen2 = 0;
962 
963  assert( scip != NULL );
964  assert( result != NULL );
965  assert( cons != NULL );
966  assert( vars1 != NULL );
967  assert( vars2 != NULL );
968  assert( vals1 != NULL );
969  assert( vals2 != NULL );
970 
971  conshdlrdata = SCIPconshdlrGetData(SCIPconsGetHdlr(cons));
972  assert( conshdlrdata != NULL );
973 
974  if ( conshdlrdata->orbiseparation )
975  {
976  SCIP_CALL( separateOrbisack(scip, cons, nrows, vars1, vars2, vals1, vals2, FALSE, conshdlrdata->coeffbound, &ngen1, &infeasible) );
977  }
978 
979  if ( ! infeasible && conshdlrdata->coverseparation )
980  {
981  SCIP_CALL( separateOrbisackCovers(scip, cons, nrows, vars1, vars2, vals1, vals2, &ngen2, &infeasible) );
982  }
983 
984  if ( infeasible )
985  {
986  *result = SCIP_CUTOFF;
987  return SCIP_OKAY;
988  }
989 
990  if ( ngen1 + ngen2 > 0 )
991  *result = SCIP_SEPARATED;
992 
993  return SCIP_OKAY;
994 }
995 
996 
997 /*--------------------------------------------------------------------------------------------
998  *--------------------------------- SCIP functions -------------------------------------------
999  *--------------------------------------------------------------------------------------------*/
1000 
1001 /** frees specific constraint data */
1002 static
1003 SCIP_DECL_CONSDELETE(consDeleteOrbisack)
1004 { /*lint --e{715}*/
1005  assert( scip != 0 );
1006  assert( conshdlr != 0 );
1007  assert( consdata != 0 );
1008  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1009 
1010  SCIP_CALL( consdataFree(scip, consdata) );
1011 
1012  return SCIP_OKAY;
1013 }
1014 
1015 
1016 /** frees constraint handler */
1017 static
1018 SCIP_DECL_CONSFREE(consFreeOrbisack)
1019 { /*lint --e{715}*/
1020  SCIP_CONSHDLRDATA* conshdlrdata;
1021 
1022  assert( scip != 0 );
1023  assert( conshdlr != 0 );
1024  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1025 
1026  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1027  assert( conshdlrdata != NULL );
1028 
1029  SCIPfreeBlockMemory(scip, &conshdlrdata);
1030 
1031  return SCIP_OKAY;
1032 }
1033 
1034 
1035 /** transforms constraint data into data belonging to the transformed problem */
1036 static
1037 SCIP_DECL_CONSTRANS(consTransOrbisack)
1039  SCIP_CONSDATA* sourcedata;
1040  SCIP_CONSDATA* consdata = NULL;
1041  int nrows;
1042 
1043  assert( scip != NULL );
1044  assert( conshdlr != NULL );
1045  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1046  assert( sourcecons != NULL );
1047  assert( targetcons != NULL );
1048 
1049  SCIPdebugMsg(scip, "Transforming constraint.\n");
1050 
1051  /* get data of original constraint */
1052  sourcedata = SCIPconsGetData(sourcecons);
1053  assert( sourcedata != NULL );
1054  assert( sourcedata->nrows > 0 );
1055  assert( sourcedata->vars1 != NULL );
1056  assert( sourcedata->vars2 != NULL );
1057 
1058  /* create transformed constraint data (copy data where necessary) */
1059  nrows = sourcedata->nrows;
1060 
1061  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1062 
1063  consdata->nrows = nrows;
1064 
1065  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars1, nrows) );
1066  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars2, nrows) );
1067 
1068  SCIP_CALL( SCIPgetTransformedVars(scip, nrows, sourcedata->vars1, consdata->vars1) );
1069  SCIP_CALL( SCIPgetTransformedVars(scip, nrows, sourcedata->vars2, consdata->vars2) );
1070 
1071  /* create transformed constraint */
1072  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1073  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1074  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1075  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1076  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1077  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1078 
1079  return SCIP_OKAY;
1080 }
1081 
1082 
1083 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1084 static
1085 SCIP_DECL_CONSINITLP(consInitlpOrbisack)
1087  int c;
1088 
1089  assert( infeasible != NULL );
1090  *infeasible = FALSE;
1091 
1092  assert( scip != 0 );
1093  assert( conshdlr != 0 );
1094  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1095 
1096  /* loop through constraints */
1097  for (c = 0; c < nconss; ++c)
1098  {
1099  /* get data of constraint */
1100  assert( conss[c] != 0 );
1101 
1102  SCIPdebugMsg(scip, "Generating initial orbisack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1103 
1104  SCIP_CALL( initLP(scip, conss[c], infeasible) );
1105  if ( *infeasible )
1106  break;
1107 
1108  SCIPdebugMsg(scip, "Generated initial orbisack cut.\n");
1109  }
1110 
1111  return SCIP_OKAY;
1112 }
1113 
1114 
1115 /** separation method of constraint handler for LP solution */
1116 static
1117 SCIP_DECL_CONSSEPALP(consSepalpOrbisack)
1118 { /*lint --e{715}*/
1119  SCIP_CONSDATA* consdata;
1120  SCIP_Real* vals1;
1121  SCIP_Real* vals2;
1122  int c;
1123 
1124  assert( scip != NULL );
1125  assert( conshdlr != NULL );
1126  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1127  assert( result != NULL );
1128 
1129  SCIPdebugMsg(scip, "Separation method for orbisack constraints.\n");
1130 
1131  *result = SCIP_DIDNOTRUN;
1132 
1133  /* if solution is not integer */
1134  if ( SCIPgetNLPBranchCands(scip) > 0 )
1135  {
1136  *result = SCIP_DIDNOTFIND;
1137 
1138  /* loop through constraints */
1139  for (c = 0; c < nconss; ++c)
1140  {
1141  /* get data of constraint */
1142  assert( conss[c] != NULL );
1143  consdata = SCIPconsGetData(conss[c]);
1144 
1145  /* get solution */
1146  SCIP_CALL( SCIPallocBufferArray(scip, &vals1, consdata->nrows) );
1147  SCIP_CALL( SCIPallocBufferArray(scip, &vals2, consdata->nrows) );
1148 
1149  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) );
1150  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) );
1151 
1152  SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1153 
1154  SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) );
1155 
1156  SCIPfreeBufferArray(scip, &vals2);
1157  SCIPfreeBufferArray(scip, &vals1);
1158 
1159  if ( *result == SCIP_CUTOFF )
1160  break;
1161  }
1162  }
1163 
1164  return SCIP_OKAY;
1165 }
1166 
1167 
1168 /** separation method of constraint handler for arbitrary primal solution */
1169 static
1170 SCIP_DECL_CONSSEPASOL(consSepasolOrbisack)
1171 { /*lint --e{715}*/
1172  SCIP_CONSDATA* consdata;
1173  SCIP_Real* vals1;
1174  SCIP_Real* vals2;
1175  int c;
1176 
1177  assert( scip != NULL );
1178  assert( conshdlr != NULL );
1179  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1180  assert( result != NULL );
1181 
1182  SCIPdebugMsg(scip, "Separation method for orbisack constraints\n");
1183 
1184  *result = SCIP_DIDNOTFIND;
1185 
1186  if ( nconss > 0 )
1187  {
1188  int nvals;
1189 
1190  nvals = SCIPgetNVars(scip)/2;
1191  SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1192  SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1193 
1194  /* loop through constraints */
1195  for (c = 0; c < nconss; ++c)
1196  {
1197  /* get data of constraint */
1198  assert( conss[c] != NULL );
1199  consdata = SCIPconsGetData(conss[c]);
1200 
1201  /* get solution */
1202  assert( consdata->nrows <= nvals );
1203  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) );
1204  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) );
1205 
1206  SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1207 
1208  SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) );
1209  if ( *result == SCIP_CUTOFF )
1210  break;
1211  }
1212 
1213  SCIPfreeBufferArray(scip, &vals2);
1214  SCIPfreeBufferArray(scip, &vals1);
1215  }
1216 
1217  return SCIP_OKAY;
1218 }
1219 
1220 
1221 /** constraint enforcing method of constraint handler for LP solutions
1222  *
1223  * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
1224  */
1225 static
1226 SCIP_DECL_CONSENFOLP(consEnfolpOrbisack)
1227 { /*lint --e{715}*/
1228  SCIP_CONSDATA* consdata;
1229  SCIP_Bool infeasible = FALSE;
1230  SCIP_Real* vals1;
1231  SCIP_Real* vals2;
1232  int ngen = 0;
1233  int c;
1234 
1235  assert( scip != 0 );
1236  assert( conshdlr != 0 );
1237  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1238  assert( result != 0 );
1239 
1240  SCIPdebugMsg(scip, "Enfolp method for orbisack constraints\n");
1241 
1242  /* we have a negative priority, so we should come after the integrality conshdlr. */
1243  assert( SCIPgetNLPBranchCands(scip) == 0 );
1244 
1245  *result = SCIP_FEASIBLE;
1246 
1247  if ( nconss > 0 )
1248  {
1249  int nvals;
1250 
1251  nvals = SCIPgetNVars(scip)/2;
1252  SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1253  SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1254 
1255  /* loop through constraints */
1256  for (c = 0; c < nconss; ++c)
1257  {
1258  /* get data of constraint */
1259  assert( conss[c] != 0 );
1260  consdata = SCIPconsGetData(conss[c]);
1261 
1262  /* get solution */
1263  assert( consdata->nrows <= nvals );
1264  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) );
1265  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) );
1266 
1267  SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1268 
1269  /* Separate only cover inequalities to ensure that enforcing works correctly. */
1270  /* Otherwise, it may happen that infeasible solutions cannot be detected, since */
1271  /* we bound the size of the coefficients for the orbisack inequalities. */
1272  SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) );
1273 
1274  if ( infeasible )
1275  {
1276  *result = SCIP_CUTOFF;
1277  break;
1278  }
1279 
1280  SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen);
1281 
1282  if ( ngen > 0 )
1283  *result = SCIP_SEPARATED;
1284  }
1285 
1286  SCIPfreeBufferArray(scip, &vals2);
1287  SCIPfreeBufferArray(scip, &vals1);
1288  }
1289 
1290  return SCIP_OKAY;
1291 }
1292 
1293 
1294 /** constraint enforcing method of constraint handler for pseudo solutions */
1295 static
1296 SCIP_DECL_CONSENFOPS(consEnfopsOrbisack)
1297 { /*lint --e{715}*/
1298  SCIP_Bool feasible = TRUE;
1299  SCIP_CONSDATA* consdata;
1300  int c;
1301 
1302  assert( scip != NULL );
1303  assert( conshdlr != NULL );
1304  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1305  assert( result != NULL );
1306 
1307  SCIPdebugMsg(scip, "Enforcing method for orbisack constraints (pseudo solutions) ...\n");
1308 
1309  *result = SCIP_FEASIBLE;
1310 
1311  if ( objinfeasible || solinfeasible )
1312  return SCIP_OKAY;
1313 
1314  /* loop through constraints */
1315  for (c = 0; c < nconss; ++c)
1316  {
1317  /* get data of constraint */
1318  assert( conss[c] != NULL );
1319  consdata = SCIPconsGetData(conss[c]);
1320  assert( consdata != NULL);
1321  assert( consdata->nrows > 0 );
1322  assert( consdata->vars1 != NULL );
1323  assert( consdata->vars2 != NULL );
1324 
1325  SCIP_CALL( SCIPcheckSolutionOrbisack(scip, NULL, consdata->vars1, consdata->vars2, consdata->nrows, FALSE, &feasible) );
1326 
1327  if ( ! feasible )
1328  {
1329  *result = SCIP_INFEASIBLE;
1330  break;
1331  }
1332  }
1333 
1334  return SCIP_OKAY;
1335 }
1336 
1337 
1338 /** constraint enforcing method of constraint handler for relaxation solutions */
1339 static
1340 SCIP_DECL_CONSENFORELAX(consEnforelaxOrbisack)
1341 { /*lint --e{715}*/
1342  SCIP_CONSDATA* consdata;
1343  SCIP_Bool infeasible = FALSE;
1344  SCIP_Real* vals1;
1345  SCIP_Real* vals2;
1346  int ngen = 0;
1347  int c;
1348 
1349  assert( scip != 0 );
1350  assert( conshdlr != 0 );
1351  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1352  assert( result != 0 );
1353 
1354  SCIPdebugMsg(scip, "Enforelax method for orbisack constraints.\n");
1355 
1356  /* we have a negative priority, so we should come after the integrality conshdlr. */
1357  assert( SCIPgetNLPBranchCands(scip) == 0 );
1358 
1359  *result = SCIP_FEASIBLE;
1360 
1361  if ( nconss > 0 )
1362  {
1363  int nvals;
1364 
1365  nvals = SCIPgetNVars(scip)/2;
1366  SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1367  SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1368 
1369  /* loop through constraints */
1370  for (c = 0; c < nconss; ++c)
1371  {
1372  /* get data of constraint */
1373  assert( conss[c] != 0 );
1374  consdata = SCIPconsGetData(conss[c]);
1375 
1376  /* get solution */
1377  assert( consdata->nrows <= nvals );
1378  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) );
1379  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) );
1380 
1381  SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1382 
1383  /* Separate only cover inequalities to ensure that enforcing works correctly. */
1384  /* Otherwise, it may happen that infeasible solutions cannot be detected, since */
1385  /* we bound the size of the coefficients for the orbisack inequalities. */
1386  SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) );
1387 
1388  if ( infeasible )
1389  {
1390  *result = SCIP_CUTOFF;
1391  break;
1392  }
1393 
1394  SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen);
1395 
1396  if ( ngen > 0 )
1397  *result = SCIP_SEPARATED;
1398  }
1399 
1400  SCIPfreeBufferArray(scip, &vals2);
1401  SCIPfreeBufferArray(scip, &vals1);
1402  }
1403 
1404  return SCIP_OKAY;
1405 }
1406 
1407 
1408 /** feasibility check method of constraint handler for integral solutions */
1409 static
1410 SCIP_DECL_CONSCHECK(consCheckOrbisack)
1411 { /*lint --e{715}*/
1412  SCIP_Bool feasible = TRUE;
1413  SCIP_CONSHDLRDATA* conshdlrdata;
1414  SCIP_CONSDATA* consdata;
1415  int c;
1416 
1417  assert( scip != NULL );
1418  assert( conshdlr != NULL );
1419  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1420  assert( result != NULL );
1421 
1422  *result = SCIP_FEASIBLE;
1423 
1424  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1425  assert( conshdlrdata != NULL );
1426 
1427  if ( conshdlrdata->checkalwaysfeas )
1428  return SCIP_OKAY;
1429 
1430  /* loop through constraints */
1431  for (c = 0; c < nconss; ++c)
1432  {
1433  /* get data of constraint */
1434  assert( conss[c] != NULL );
1435  consdata = SCIPconsGetData(conss[c]);
1436  assert( consdata != NULL);
1437  assert( consdata->nrows > 0 );
1438  assert( consdata->vars1 != NULL );
1439  assert( consdata->vars2 != NULL );
1440 
1441  SCIPdebugMsg(scip, "Check method for orbisack constraint <%s> (%d rows) ...\n", SCIPconsGetName(conss[c]), consdata->nrows);
1442 
1443  SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, consdata->vars1, consdata->vars2, consdata->nrows, printreason, &feasible) );
1444 
1445  if ( ! feasible )
1446  {
1447  *result = SCIP_INFEASIBLE;
1448  SCIPdebugMsg(scip, "Solution is feasible.\n");
1449  break;
1450  }
1451  }
1452 
1453  if ( feasible )
1454  SCIPdebugMsg(scip, "Solution is feasible.\n");
1455 
1456  return SCIP_OKAY;
1457 }
1458 
1459 
1460 /** domain propagation method of constraint handler */
1461 static
1462 SCIP_DECL_CONSPROP(consPropOrbisack)
1463 { /*lint --e{715}*/
1464  int c;
1465 
1466  assert( scip != NULL );
1467  assert( conshdlr != NULL );
1468  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1469  assert( result != NULL );
1470 
1471  *result = SCIP_DIDNOTRUN;
1472 
1473  SCIPdebugMsg(scip, "Propagation method of orbisack constraint handler.\n");
1474 
1475  /* loop through constraints */
1476  for (c = 0; c < nconss; ++c)
1477  {
1478  SCIP_Bool infeasible = FALSE;
1479  SCIP_Bool found = FALSE;
1480  int ngen = 0;
1481 
1482  assert( conss[c] != NULL );
1483 
1484  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &ngen) );
1485 
1486  if ( infeasible )
1487  {
1488  *result = SCIP_CUTOFF;
1489  return SCIP_OKAY;
1490  }
1491 
1492  if ( found )
1493  *result = SCIP_REDUCEDDOM;
1494  }
1495 
1496  return SCIP_OKAY;
1497 }
1498 
1499 
1500 /** presolving method of constraint handler */
1501 static
1502 SCIP_DECL_CONSPRESOL(consPresolOrbisack)
1503 { /*lint --e{715}*/
1504  int c;
1505  int ngen = 0;
1506 
1507  assert( scip != NULL );
1508  assert( conshdlr != NULL );
1509  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1510  assert( result != NULL );
1511 
1512  SCIPdebugMsg(scip, "Presolving method of orbisack constraint handler. Propagating orbisack inequalities.\n");
1513 
1514  *result = SCIP_DIDNOTFIND;
1515 
1516  /* loop through constraints */
1517  for (c = 0; c < nconss; ++c)
1518  {
1519  SCIP_Bool infeasible = FALSE;
1520  SCIP_Bool found = FALSE;
1521  int curngen = 0;
1522 
1523  assert( conss[c] != NULL );
1524  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &curngen) );
1525 
1526  if ( infeasible )
1527  {
1528  *result = SCIP_CUTOFF;
1529  break;
1530  }
1531 
1532  ngen += curngen;
1533  }
1534 
1535  if ( ngen > 0 )
1536  {
1537  *nfixedvars += ngen;
1538  *result = SCIP_SUCCESS;
1539  }
1540 
1541  return SCIP_OKAY;
1542 }
1543 
1544 
1545 /** Propagation resolution for conflict analysis */
1546 static
1547 SCIP_DECL_CONSRESPROP(consRespropOrbisack)
1548 { /*lint --e{715}*/
1549  SCIP_CONSDATA* consdata;
1550  SCIP_VAR** vars1;
1551  SCIP_VAR** vars2;
1552  int i;
1553 
1554  assert( scip != NULL );
1555  assert( conshdlr != NULL );
1556  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1557  assert( cons != NULL );
1558  assert( infervar != NULL );
1559  assert( bdchgidx != NULL );
1560  assert( result != NULL );
1561 
1562  SCIPdebugMsg(scip, "Propagation resolution method of orbisack constraint handler.\n");
1563 
1564  *result = SCIP_DIDNOTFIND;
1565 
1566  consdata = SCIPconsGetData(cons);
1567  assert( consdata != NULL);
1568  assert( consdata->nrows > 0 );
1569  assert( consdata->vars1 != NULL );
1570  assert( consdata->vars2 != NULL );
1571 
1572  vars1 = consdata->vars1;
1573  vars2 = consdata->vars2;
1574 
1575  assert( 0 <= inferinfo && inferinfo < consdata->nrows );
1576 
1577  assert( vars2[inferinfo] == infervar );
1578  assert( SCIPvarGetUbAtIndex(vars2[inferinfo], bdchgidx, FALSE) > 0.5 && SCIPvarGetUbAtIndex(vars2[inferinfo], bdchgidx, TRUE) < 0.5 );
1579 
1580  if ( SCIPvarGetUbAtIndex(vars2[inferinfo], bdchgidx, FALSE) > 0.5 && SCIPvarGetUbAtIndex(vars2[inferinfo], bdchgidx, TRUE) < 0.5 )
1581  {
1582  SCIPdebugMsg(scip, " -> reason for setting x[%d][1] = 0 was fixing x[%d][0] to 0 and each row above is fixed to the same value.\n",
1583  inferinfo, inferinfo);
1584 
1585  for (i = 0; i < inferinfo; ++i)
1586  {
1587  SCIP_CALL( SCIPaddConflictUb(scip, vars1[i], bdchgidx) );
1588  SCIP_CALL( SCIPaddConflictLb(scip, vars1[i], bdchgidx) );
1589  SCIP_CALL( SCIPaddConflictUb(scip, vars2[i], bdchgidx) );
1590  SCIP_CALL( SCIPaddConflictLb(scip, vars2[i], bdchgidx) );
1591  }
1592  SCIP_CALL( SCIPaddConflictUb(scip, vars1[inferinfo], bdchgidx) );
1593 
1594  *result = SCIP_SUCCESS;
1595  }
1596 
1597  return SCIP_OKAY;
1598 }
1599 
1600 
1601 /** Lock variables
1602  *
1603  * We assume we have only one global (void) constraint and lock all variables.
1604  *
1605  * - Orbisack constraints may get violated if the variables of the first column
1606  * are rounded down, we therefor call SCIPaddVarLocks(..., nlockspos, nlocksneg).
1607  * - Orbisack constraints may get violated if the variables of the second column
1608  * are rounded up , we therefor call SCIPaddVarLocks(..., nlocksneg, nlockspo ).
1609  */
1610 static
1611 SCIP_DECL_CONSLOCK(consLockOrbisack)
1612 { /*lint --e{715}*/
1613  SCIP_CONSDATA* consdata;
1614  SCIP_VAR** vars1;
1615  SCIP_VAR** vars2;
1616  int nrows;
1617  int i;
1618 
1619  assert( scip != NULL );
1620  assert( conshdlr != NULL );
1621  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1622  assert( cons != NULL );
1623 
1624  SCIPdebugMsg(scip, "Locking method for orbisack constraint handler.\n");
1625 
1626  /* get data of original constraint */
1627  consdata = SCIPconsGetData(cons);
1628  assert( consdata != NULL);
1629  assert( consdata->nrows > 0 );
1630  assert( consdata->vars1 != NULL );
1631  assert( consdata->vars2 != NULL );
1632 
1633  nrows = consdata->nrows;
1634  vars1 = consdata->vars1;
1635  vars2 = consdata->vars2;
1636 
1637  for (i = 0; i < nrows; ++i)
1638  {
1639  SCIP_CALL( SCIPaddVarLocks(scip, vars1[i], nlockspos, nlocksneg) );
1640  SCIP_CALL( SCIPaddVarLocks(scip, vars2[i], nlocksneg, nlockspos) );
1641  }
1642 
1643  return SCIP_OKAY;
1644 }
1645 
1646 
1647 /** constraint display method of constraint handler
1648  *
1649  * The constraint handler should output a representation of the constraint into the given text file.
1650  */
1651 static
1652 SCIP_DECL_CONSPRINT(consPrintOrbisack)
1653 { /*lint --e{715}*/
1654  SCIP_CONSDATA* consdata;
1655  SCIP_VAR** vars1;
1656  SCIP_VAR** vars2;
1657  int nrows;
1658  int i;
1659 
1660  assert( scip != NULL );
1661  assert( conshdlr != NULL );
1662  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1663  assert( cons != NULL );
1664 
1665  consdata = SCIPconsGetData(cons);
1666  assert( consdata != NULL );
1667  assert( consdata->vars1 != NULL );
1668  assert( consdata->vars2 != NULL );
1669  assert( consdata->nrows > 0 );
1670 
1671  vars1 = consdata->vars1;
1672  vars2 = consdata->vars2;
1673  nrows = consdata->nrows;
1674 
1675  SCIPdebugMsg(scip, "Printing method for orbisack constraint handler\n");
1676 
1677  SCIPinfoMessage(scip, file, "orbisack(");
1678 
1679  for (i = 0; i < nrows; ++i)
1680  {
1681  SCIPinfoMessage(scip, file, "%s,%s", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
1682  if ( i < nrows-1 )
1683  SCIPinfoMessage(scip, file, ".");
1684  }
1685 
1686  return SCIP_OKAY;
1687 }
1688 
1689 
1690 /** checks given solution for feasibility */
1692  SCIP* scip, /**< SCIP data structure */
1693  SCIP_SOL* sol, /**< solution to check for feasibility */
1694  SCIP_VAR** vars1, /**< variables of first column */
1695  SCIP_VAR** vars2, /**< variables of second column */
1696  int nrows, /**< number of rows */
1697  SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */
1698  SCIP_Bool* feasible /**< memory address to store whether sol is feasible */
1699  )
1700 {
1701  int i;
1702  int val1;
1703  int val2;
1704 
1705  assert( scip != NULL );
1706  assert( vars1 != NULL );
1707  assert( vars2 != NULL );
1708  assert( nrows > 0 );
1709  assert( feasible != NULL );
1710 
1711  *feasible = TRUE;
1712 
1713  /* find first non-constant row and check for feasibility */
1714  for (i = 0; i < nrows; ++i)
1715  {
1716  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars1[i])) );
1717  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars2[i])) );
1718 
1719  /* get values of i-th row */
1720  val1 = SCIPgetSolVal(scip, sol, vars1[i]) > 0.5 ? 1 : 0;
1721  val2 = SCIPgetSolVal(scip, sol, vars2[i]) > 0.5 ? 1 : 0;
1722 
1723  /* if row i is constrant */
1724  if ( val1 == val2 )
1725  continue;
1726  /* row i has type (1,0) -> feasible */
1727  else if ( val1 == 1 )
1728  {
1729  assert( val2 == 0 );
1730  break;
1731  }
1732  else /* infeasible */
1733  {
1734  if ( printreason )
1735  SCIPinfoMessage(scip, NULL, "First non-constant row %d is fixed to (0,1).\n", i);
1736  *feasible = FALSE;
1737  break;
1738  }
1739  }
1740 
1741  return SCIP_OKAY;
1742 }
1743 
1744 
1745 /** separate orbisack cover inequalities for a given solution */
1747  SCIP* scip, /**< pointer to scip */
1748  SCIP_CONS* cons, /**< pointer to constraint for which cover inequality should be added */
1749  SCIP_SOL* sol, /**< solution to be separated */
1750  SCIP_VAR** vars1, /**< variables of first columns */
1751  SCIP_VAR** vars2, /**< variables of second columns */
1752  int nrows, /**< number of rows */
1753  SCIP_Bool* infeasible, /**< memory address to store whether we detected infeasibility */
1754  int* ngen /**< memory address to store number of generated cuts */
1755  )
1756 {
1757  SCIP_ROW* row;
1758  SCIP_Real rhs = 0.0;
1759  SCIP_Real lhs = 0.0;
1760  SCIP_Real* solvals1;
1761  SCIP_Real* solvals2;
1762  SCIP_Real* coeff1;
1763  SCIP_Real* coeff2;
1764  int i;
1765  int j;
1766 
1767  assert( scip != NULL );
1768  assert( vars1 != NULL );
1769  assert( vars2 != NULL );
1770  assert( nrows > 0 );
1771  assert( infeasible != NULL );
1772  assert( ngen != NULL );
1773 
1774  *infeasible = FALSE;
1775  *ngen = 0;
1776 
1777  /* allocate memory for inequality coefficients */
1778  SCIP_CALL( SCIPallocBufferArray(scip, &coeff1, nrows) );
1779  SCIP_CALL( SCIPallocBufferArray(scip, &coeff2, nrows) );
1780  SCIP_CALL( SCIPallocBufferArray(scip, &solvals1, nrows) );
1781  SCIP_CALL( SCIPallocBufferArray(scip, &solvals2, nrows) );
1782 
1783  /* initialize coefficient matrix and solution values */
1784  for (i = 0; i < nrows; ++i)
1785  {
1786  coeff1[i] = 0.0;
1787  coeff2[i] = 0.0;
1788  }
1789  SCIP_CALL( SCIPgetSolVals(scip, sol, nrows, vars1, solvals1) );
1790  SCIP_CALL( SCIPgetSolVals(scip, sol, nrows, vars2, solvals2) );
1791 
1792  /* detect violated covers */
1793  for (i = 0; i < nrows; ++i)
1794  {
1795  /* cover inequality is violated */
1796  if ( SCIPisEfficacious(scip, -solvals1[i] + solvals2[i] + lhs - rhs) )
1797  {
1798  /* set coefficients for inequality */
1799  coeff1[i] = -1.0;
1800  coeff2[i] = 1.0;
1801 
1802  /* add inequality */
1803  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
1804  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
1805  for (j = 0; j < nrows; ++j)
1806  {
1807  SCIP_CALL( SCIPaddVarToRow(scip, row, vars1[j], coeff1[j]) );
1808  SCIP_CALL( SCIPaddVarToRow(scip, row, vars2[j], coeff2[j]) );
1809  }
1810  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
1811 
1812  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
1813 #ifdef SCIP_DEBUG
1814  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
1815 #endif
1816  SCIP_CALL( SCIPreleaseRow(scip, &row) );
1817 
1818  ++(*ngen);
1819  if ( *infeasible )
1820  break;
1821 
1822  /* reset coefficients for next inequality */
1823  coeff1[i] = 0.0;
1824  coeff2[i] = 0.0;
1825  }
1826 
1827  /* add argmax( 1 - solvals[i][0], solvals[i][1] ) as coefficient */
1828  if ( SCIPisEfficacious(scip, 1.0 - solvals1[i] - solvals2[i]) )
1829  {
1830  coeff1[i] = -1.0;
1831  lhs = lhs - solvals1[i];
1832  }
1833  else
1834  {
1835  coeff2[i] = 1.0;
1836  rhs += 1.0;
1837  lhs = lhs + solvals2[i];
1838  }
1839  }
1840 
1841  /* free coefficient matrix */
1842  SCIPfreeBufferArray(scip, &solvals2);
1843  SCIPfreeBufferArray(scip, &solvals1);
1844  SCIPfreeBufferArray(scip, &coeff2);
1845  SCIPfreeBufferArray(scip, &coeff1);
1846 
1847  return SCIP_OKAY;
1848 
1849 }
1850 
1851 
1852 /** constraint method of constraint handler which returns the variables (if possible) */
1853 static
1854 SCIP_DECL_CONSGETVARS(consGetVarsOrbisack)
1855 { /*lint --e{715}*/
1856  SCIP_CONSDATA* consdata;
1857 
1858  assert( cons != NULL );
1859  assert( success != NULL );
1860  assert( vars != NULL );
1861 
1862  consdata = SCIPconsGetData(cons);
1863  assert( consdata != NULL );
1864 
1865  if ( varssize < 2 * consdata->nrows )
1866  (*success) = FALSE;
1867  else
1868  {
1869  int cnt = 0;
1870  int i;
1871 
1872  for (i = 0; i < consdata->nrows; ++i)
1873  {
1874  vars[cnt++] = consdata->vars1[i];
1875  vars[cnt++] = consdata->vars2[i];
1876  }
1877  (*success) = TRUE;
1878  }
1879 
1880  return SCIP_OKAY;
1881 }
1882 
1883 
1884 /** constraint method of constraint handler which returns the number of variables (if possible) */
1885 static
1886 SCIP_DECL_CONSGETNVARS(consGetNVarsOrbisack)
1887 { /*lint --e{715}*/
1888  SCIP_CONSDATA* consdata;
1889 
1890  assert( cons != NULL );
1891 
1892  consdata = SCIPconsGetData(cons);
1893  assert( consdata != NULL );
1894 
1895  (*nvars) = 2 * consdata->nrows;
1896  (*success) = TRUE;
1897 
1898  return SCIP_OKAY;
1899 }
1900 
1901 
1902 /** creates the handler for orbisack constraints and includes it in SCIP */
1904  SCIP* scip /**< SCIP data structure */
1905  )
1906 {
1907  SCIP_CONSHDLRDATA* conshdlrdata = NULL;
1908  SCIP_CONSHDLR* conshdlr;
1909 
1910  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
1911 
1912  /* include constraint handler */
1916  consEnfolpOrbisack, consEnfopsOrbisack, consCheckOrbisack, consLockOrbisack,
1917  conshdlrdata) );
1918  assert( conshdlr != NULL );
1919 
1920  /* set non-fundamental callbacks via specific setter functions */
1921  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbisack) );
1922  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbisack) );
1923  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbisack) );
1924  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbisack) );
1925  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbisack) );
1926  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbisack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
1927  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbisack) );
1929  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbisack) );
1930  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbisack, consSepasolOrbisack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
1931  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbisack) );
1932  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOrbisack) );
1933 
1934  /* separation methods */
1935  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/orbisack/coverseparation",
1936  "Separate cover inequalities for orbisacks?",
1937  &conshdlrdata->coverseparation, TRUE, DEFAULT_COVERSEPARATION, NULL, NULL) );
1938 
1939  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/orbiSeparation",
1940  "Separate orbisack inequalities?",
1941  &conshdlrdata->orbiseparation, TRUE, DEFAULT_ORBISEPARATION, NULL, NULL) );
1942 
1943  SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/coeffbound",
1944  "Maximum size of coefficients for orbisack inequalities",
1945  &conshdlrdata->coeffbound, TRUE, DEFAULT_COEFFBOUND, 0.0, DBL_MAX, NULL, NULL) );
1946 
1947  /* whether we allow upgrading to packing/partioning orbisack constraints*/
1948  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbisack",
1949  "Upgrade orbisack constraints to packing/partioning orbisacks?",
1950  &conshdlrdata->checkpporbisack, TRUE, DEFAULT_PPORBISACK, NULL, NULL) );
1951 
1952  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkalwaysfeas",
1953  "Whether check routine returns always SCIP_FEASIBLE.",
1954  &conshdlrdata->checkalwaysfeas, TRUE, DEFAULT_CHECKALWAYSFEAS, NULL, NULL) );
1955 
1956  return SCIP_OKAY;
1957 }
1958 
1959 
1960 /*
1961  * constraint specific interface methods
1962  */
1963 
1964 /** creates and captures a orbisack constraint
1965  *
1966  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
1967  */
1969  SCIP* scip, /**< SCIP data structure */
1970  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1971  const char* name, /**< name of constraint */
1972  SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
1973  SCIP_VAR*const* vars2, /**< second column of matrix of variables on which the symmetry acts */
1974  int nrows, /**< number of rows in variable matrix */
1975  SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */
1976  SCIP_Bool isparttype, /**< whether the orbisack is a partitioning orbisack */
1977  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1978  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1979  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1980  * Usually set to TRUE. */
1981  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1982  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1983  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1984  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1985  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1986  * Usually set to TRUE. */
1987  SCIP_Bool local, /**< is constraint only valid locally?
1988  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1989  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1990  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1991  * adds coefficients to this constraint. */
1992  SCIP_Bool dynamic, /**< is constraint subject to aging?
1993  * Usually set to FALSE. Set to TRUE for own cuts which
1994  * are separated as constraints. */
1995  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1996  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1997  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1998  * if it may be moved to a more global node?
1999  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2000  )
2001 {
2002  SCIP_CONSHDLR* conshdlr;
2003  SCIP_CONSHDLRDATA* conshdlrdata;
2004  SCIP_CONSDATA* consdata;
2005  SCIP_VAR*** vars;
2006  SCIP_Bool success;
2007  SCIP_ORBITOPETYPE orbitopetype;
2008  int i;
2009 
2010  /* find the orbisack constraint handler */
2011  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2012  if ( conshdlr == NULL )
2013  {
2014  SCIPerrorMessage("orbisack constraint handler not found\n");
2015  return SCIP_PLUGINNOTFOUND;
2016  }
2017 
2018  assert( nrows > 0 );
2019 
2020  /* check for upgrade to packing/partitioning orbisacks*/
2021  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2022  if ( ! ispporbisack && conshdlrdata->checkpporbisack )
2023  {
2024  SCIP_CALL( packingUpgrade(scip, vars1, vars2, nrows, &success, &isparttype) );
2025 
2026  if ( success )
2027  ispporbisack = TRUE;
2028  }
2029 
2030  /* create constraint, if it is a packing/partitioning orbisack, add orbitope constraint
2031  * instead of orbitsack constraint */
2032  if ( ispporbisack )
2033  {
2034  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) );
2035  for (i = 0; i < nrows; ++i)
2036  {
2037  SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], 2) ); /*lint !e866*/
2038  vars[i][0] = vars1[i];
2039  vars[i][1] = vars2[i];
2040  }
2041 
2042  if ( isparttype )
2043  orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
2044  else
2045  orbitopetype = SCIP_ORBITOPETYPE_PACKING;
2046 
2047  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, "pporbisack", vars, orbitopetype, nrows, 2, TRUE, initial, separate, enforce, check, propagate,
2048  local, modifiable, dynamic, removable, stickingatnode) );
2049 
2050  for (i = 0; i < nrows; ++i)
2051  SCIPfreeBufferArray(scip, &vars[i]);
2052  SCIPfreeBufferArray(scip, &vars);
2053  }
2054  else
2055  {
2056  /* create constraint data */
2057  SCIP_CALL( consdataCreate(scip, &consdata, vars1, vars2, nrows) );
2058 
2059  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2060  local, modifiable, dynamic, removable, stickingatnode) );
2061  }
2062 
2063  return SCIP_OKAY;
2064 }
2065 
2066 
2067 /** creates and captures an orbisack constraint in its most basic variant
2068  *
2069  * All constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h.
2070  *
2071  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2072  */
2074  SCIP* scip, /**< SCIP data structure */
2075  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2076  const char* name, /**< name of constraint */
2077  SCIP_VAR** vars1, /**< first column of matrix of variables on which the symmetry acts */
2078  SCIP_VAR** vars2, /**< second column of matrix of variables on which the symmetry acts */
2079  int nrows, /**< number of rows in constraint matrix */
2080  SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */
2081  SCIP_Bool isparttype /**< whether the orbisack is a partitioning orbisack */
2082  )
2083 {
2084  SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, ispporbisack, isparttype,
2086 
2087  return SCIP_OKAY;
2088 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool resolveprop, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip.c:6291
static SCIP_DECL_CONSENFOPS(consEnfopsOrbisack)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30607
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8245
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip.c:6314
static SCIP_RETCODE packingUpgrade(SCIP *scip, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool *success, SCIP_Bool *isparttype)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30630
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9230
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:22622
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip.c:6544
static SCIP_DECL_CONSRESPROP(consRespropOrbisack)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip.c:6036
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30662
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:27382
SCIP_RETCODE SCIPincludeConshdlrOrbisack(SCIP *scip)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip.c:18951
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
#define DEFAULT_COEFFBOUND
Definition: cons_orbisack.c:74
static SCIP_DECL_CONSGETVARS(consGetVarsOrbisack)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4485
#define FALSE
Definition: def.h:64
static SCIP_DECL_CONSSEPALP(consSepalpOrbisack)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip.c:5894
constraint handler for orbisack constraints
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
static SCIP_RETCODE addOrbisackCover(SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *coeffs1, SCIP_Real *coeffs2, SCIP_Real rhs, SCIP_Bool *infeasible)
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:27245
#define CONSHDLR_NEEDSCONS
Definition: cons_orbisack.c:64
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
Definition: scip.c:21654
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8265
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip.c:27149
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip.c:5948
static SCIP_RETCODE separateOrbisack(SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *vals1, SCIP_Real *vals2, SCIP_Bool coverseparation, SCIP_Real coeffbound, int *ngen, SCIP_Bool *infeasible)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:1017
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:37028
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8255
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip.c:6337
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define SCIPdebugMsg
Definition: scip.h:455
#define DEFAULT_ORBISEPARATION
Definition: cons_orbisack.c:70
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip.c:18992
SCIP_RETCODE SCIPseparateCoversOrbisack(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool *infeasible, int *ngen)
static SCIP_RETCODE initLP(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1343
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip.c:27578
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:27178
static SCIP_DECL_CONSTRANS(consTransOrbisack)
SCIP_RETCODE SCIPcreateConsOrbisack(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_RETCODE addOrbisackInequality(SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *coeffs1, SCIP_Real *coeffs2, SCIP_Real rhs, SCIP_Bool *infeasible)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:27127
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:22599
#define CONSHDLR_DELAYPROP
Definition: cons_orbisack.c:63
static SCIP_DECL_CONSPRINT(consPrintOrbisack)
static SCIP_DECL_CONSCHECK(consCheckOrbisack)
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
#define CONSHDLR_DESC
Definition: cons_orbisack.c:52
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38942
#define CONSHDLR_SEPAFREQ
Definition: cons_orbisack.c:56
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip.c:34540
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16071
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7986
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:25926
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8205
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip.c:6085
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4133
#define CONSHDLR_PROP_TIMING
Definition: cons_orbisack.c:66
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
Definition: cons_orbitope.h:78
static SCIP_DECL_CONSPROP(consPropOrbisack)
#define CONSHDLR_CHECKPRIORITY
Definition: cons_orbisack.c:55
#define SCIP_CALL(x)
Definition: def.h:350
#define DEFAULT_CHECKALWAYSFEAS
Definition: cons_orbisack.c:77
#define DEFAULT_PPORBISACK
Definition: cons_orbisack.c:76
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip.c:27529
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8225
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:34655
static SCIP_RETCODE propVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, SCIP_Bool *found, int *ngen)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip.c:6360
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:50
#define CONSHDLR_SEPAPRIORITY
Definition: cons_orbisack.c:53
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4515
static SCIP_DECL_CONSGETNVARS(consGetNVarsOrbisack)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:30396
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9272
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8006
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8185
#define CONSHDLR_ENFOPRIORITY
Definition: cons_orbisack.c:54
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8155
#define CONSHDLR_NAME
Definition: cons_orbisack.c:51
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip.c:6498
static SCIP_DECL_CONSDELETE(consDeleteOrbisack)
static SCIP_RETCODE separateInequalities(SCIP *scip, SCIP_RESULT *result, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *vals1, SCIP_Real *vals2)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9251
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
static SCIP_RETCODE separateOrbisackCovers(SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *vals1, SCIP_Real *vals2, int *ngen, SCIP_Bool *infeasible)
static SCIP_DECL_CONSENFOLP(consEnfolpOrbisack)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30534
static SCIP_DECL_CONSSEPASOL(consSepasolOrbisack)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8016
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22926
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:6253
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8235
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip.c:6567
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8175
#define CONSHDLR_MAXPREROUNDS
Definition: cons_orbisack.c:61
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8165
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:31154
#define CONSHDLR_PRESOLTIMING
Definition: cons_orbisack.c:67
static SCIP_DECL_CONSPRESOL(consPresolOrbisack)
static SCIP_DECL_CONSLOCK(consLockOrbisack)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:49
static SCIP_DECL_CONSFREE(consFreeOrbisack)
#define CONSHDLR_DELAYSEPA
Definition: cons_orbisack.c:62
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47393
SCIP_RETCODE SCIPcreateConsBasicOrbisack(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype)
#define CONSHDLR_PROPFREQ
Definition: cons_orbisack.c:57
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
static SCIP_DECL_CONSENFORELAX(consEnforelaxOrbisack)
#define CONSHDLR_EAGERFREQ
Definition: cons_orbisack.c:58
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321
SCIP_RETCODE SCIPcheckSolutionOrbisack(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool printreason, SCIP_Bool *feasible)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239
#define DEFAULT_COVERSEPARATION
Definition: cons_orbisack.c:71
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16817
static SCIP_DECL_CONSINITLP(consInitlpOrbisack)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5994