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