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