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