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