Scippy

SCIP

Solving Constraint Integer Programs

cons_orbitope.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_orbitope.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group
19  * @author Timo Berthold
20  * @author Marc Pfetsch
21  * @author Christopher Hojny
22  *
23  * The type of constraints of this constraint handler is described in cons_orbitope.h.
24  *
25  * The details of the method implemented here are described in the following papers.
26  *
27  * Packing and Partitioning Orbitopes@n
28  * Volker Kaibel and Marc E. Pfetsch,@n
29  * Math. Program. 114, No. 1, 1-36 (2008)
30  *
31  * Among other things, this paper describes so-called shifted column inequalities of the following
32  * form \f$x(S) \leq x(B)\f$, where \f$S\f$ is a so-called shifted column and \f$B\f$ is a so-called
33  * bar. These inequalities can be used to handle symmetry and they are separated in this constraint
34  * handler. We use the linear time separation algorithm of the paper.@par
35  *
36  * Orbitopal Fixing@n
37  * Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,@n
38  * Discrete Optimization 8, No. 4, 595-610 (2011)
39  * (A preliminary version appears in Proc. IPCO 2007.)
40  *
41  * In this paper a linear time propagation algorithm is described, a variant of which is implemented
42  * here. The implemented variant does not run in linear time, but is very fast in practice.
43  *
44  * <table>
45  * <caption>translation table</caption>
46  * <tr><td>here</td><td>paper</td></tr>
47  * <tr><td></td><td></td></tr>
48  * <tr><td>nspcons </td><td>p </td></tr>
49  * <tr><td>nblocks </td><td>q </td></tr>
50  * <tr><td>vars </td><td>x </td></tr>
51  * <tr><td>vals </td><td>A^\\star</td></tr>
52  * <tr><td>weights </td><td>\\omega </td></tr>
53  * <tr><td>cases </td><td>\\tau </td></tr>
54  * <tr><td>fixtriangle </td><td>-- </td></tr>
55  * <tr><td>resolveprop </td><td>-- </td></tr>
56  * <tr><td>firstnonzeros</td><td>\\mu </td></tr>
57  * <tr><td>lastones </td><td>\\alpha </td></tr>
58  * <tr><td>frontiersteps</td><td>\\Gamma </td></tr>
59  * </table>
60  *
61  * Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem@n
62  * Pascale Bendotti, Pierre Fouilhoux, and Cecile Rottner,@n
63  * Optimization Online: http://www.optimization-online.org/DB_HTML/2017/10/6301.html
64  *
65  * Two linear time propagation algorithms for full orbitopes are described in this paper, a static
66  * version and a dynamic one. While the static version uses a fixed variable order, the dynamic
67  * version determines the variable order during the solving process via branching descisions.
68  * We implemented the static version as well as a modified version of the dynamic one. The reason
69  * for the latter is to simplify the compatibility with full orbitope cutting planes.
70  *
71  * Note, however, that the dynamic version may lead to conflicts if orbitopes are copied to subSCIPs.
72  * Since the dynamic version is based on branching decisions, which may be different in main SCIP
73  * and subSCIPs, orbitopes using the dynamic algorithm are not allowed to be copied. However, as a
74  * user might use orbitopes to enforce a certain variable ordering in a solution, we distinguish
75  * whether an orbitope is a model constraint or not. If it is a model constraint, we assume that
76  * a variable order has already been fixed and disable the dynamic algorithm. In this case, orbitope
77  * constraints are copied to subSCIPs. If it is not a model constraint, the orbitope was added to
78  * handle symmetries but not to enforce a solution to have a certain structure. In this case, the
79  * dynamic algorithm can be used and we do not copy orbitope constraints to subSCIPs.
80  *
81  * Polytopes associated with symmetry handling@n
82  * Christopher Hojny and Marc E. Pfetsch,@n
83  * Math. Program. (2018)
84  *
85  * In this paper, a linear time separation algorithm for orbisacks (full orbitopes with two columnes)
86  * is described. We use this algorithm for every pair of adjacent columns within the orbitope as well
87  * as a version that is adapted to the reordering based on the dynamic full orbitope propagation
88  * algorithm to ensure validity of binary points via cutting planes.
89  */
90 
91 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
92 
93 #include "blockmemshell/memory.h"
94 #include "scip/cons_orbisack.h"
95 #include "scip/cons_orbitope.h"
96 #include "scip/cons_setppc.h"
97 #include "scip/pub_cons.h"
98 #include "scip/pub_message.h"
99 #include "scip/pub_var.h"
100 #include "scip/scip.h"
101 #include "scip/scip_branch.h"
102 #include "scip/scip_conflict.h"
103 #include "scip/scip_cons.h"
104 #include "scip/scip_copy.h"
105 #include "scip/scip_cut.h"
106 #include "scip/scip_general.h"
107 #include "scip/scip_lp.h"
108 #include "scip/scip_mem.h"
109 #include "scip/scip_message.h"
110 #include "scip/scip_numerics.h"
111 #include "scip/scip_param.h"
112 #include "scip/scip_prob.h"
113 #include "scip/scip_probing.h"
114 #include "scip/scip_sol.h"
115 #include "scip/scip_var.h"
116 #include "scip/symmetry.h"
117 #include <ctype.h>
118 #include <string.h>
119 #include <symmetry/type_symmetry.h>
120 
121 /* constraint handler properties */
122 #define CONSHDLR_NAME "orbitope"
123 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes"
124 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
125 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
126 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
127 #define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */
128 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
129 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
130  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
131 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
132 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
133 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
134 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
136 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
137 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
139 #define DEFAULT_PPORBITOPE TRUE /**< whether we check if full orbitopes can be strengthened to packing/partitioning orbitopes */
140 #define DEFAULT_SEPAFULLORBITOPE FALSE /**< whether we separate inequalities for full orbitopes */
141 #define DEFAULT_FORCECONSCOPY FALSE /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
143 /*
144  * Data structures
145  */
146 
147 /** constraint handler data */
148 struct SCIP_ConshdlrData
149 {
150  SCIP_Bool checkpporbitope; /**< whether we allow upgrading to packing/partitioning orbitopes */
151  SCIP_Bool sepafullorbitope; /**< whether we separate inequalities for full orbitopes orbitopes */
152  SCIP_Bool forceconscopy; /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
153 };
154 
155 /** constraint data for orbitope constraints */
156 struct SCIP_ConsData
157 {
158  SCIP_VAR*** vars; /**< matrix of variables on which the symmetry acts */
159  SCIP_VAR** tmpvars; /**< temporary storage for variables */
160  SCIP_HASHMAP* rowindexmap; /**< map of variables to row index in orbitope matrix */
161  SCIP_Real** vals; /**< LP-solution for those variables */
162  SCIP_Real* tmpvals; /**< temporary storage for values */
163  SCIP_Real** weights; /**< SC weight table */
164  int** cases; /**< indicator of the SC cases */
165  int nspcons; /**< number of set partitioning/packing constraints <=> p */
166  int nblocks; /**< number of symmetric variable blocks <=> q */
167  SCIP_ORBITOPETYPE orbitopetype; /**< type of orbitope constraint */
168  SCIP_Bool resolveprop; /**< should propagation be resolved? */
169  SCIP_Bool istrianglefixed; /**< has the upper right triangle already globally been fixed to zero? */
170  int* roworder; /**< order of orbitope rows if dynamic propagation for full orbitopes
171  * is used. */
172  SCIP_Bool* rowused; /**< whether a row has been considered in roworder */
173  int nrowsused; /**< number of rows that have already been considered in roworder */
174  SCIP_Bool ismodelcons; /**< whether the orbitope is a model constraint */
175  SCIP_Bool mayinteract; /**< whether symmetries corresponding to orbitope might interact
176  * with symmetries handled by other routines */
177  SCIP_Bool usedynamicprop; /**< whether we use a dynamic version of the propagation routine */
178 };
179 
180 
181 /*
182  * Local methods
183  */
184 
185 /** frees an orbitope constraint data */
186 static
188  SCIP* scip, /**< SCIP data structure */
189  SCIP_CONSDATA** consdata /**< pointer to orbitope constraint data */
190  )
191 {
192  int i;
193  int p;
194  int q;
195 
196  assert( consdata != NULL );
197  assert( *consdata != NULL );
198 
199  if ( (*consdata)->usedynamicprop && (*consdata)->rowindexmap != NULL )
200  {
201  SCIPhashmapFree(&((*consdata)->rowindexmap));
202  }
203 
204  p = (*consdata)->nspcons;
205  q = (*consdata)->nblocks;
206  for (i = 0; i < p; ++i)
207  {
208  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases[i]), q); /*lint !e866*/
209  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars[i]), q); /*lint !e866*/
210  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights[i]), q); /*lint !e866*/
211  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals[i]), q); /*lint !e866*/
212  }
213 
214  if ( (*consdata)->usedynamicprop )
215  {
216  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->rowused), p);
217  }
218  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->roworder), p);
219  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases), p);
220  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), p);
221  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights), p);
222  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals), p);
223 
224  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvals), p + q);
225  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvars), p + q);
226 
227  SCIPfreeBlockMemory(scip, consdata);
228 
229  return SCIP_OKAY;
230 }
231 
232 
233 /** creates orbitope constraint data */
234 static
236  SCIP* scip, /**< SCIP data structure */
237  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
238  SCIP_VAR*** vars, /**< variables array, must have size nspcons x nblocks */
239  int nspcons, /**< number of set partitioning (packing) constraints <=> p */
240  int nblocks, /**< number of symmetric variable blocks <=> q */
241  SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
242  SCIP_Bool resolveprop, /**< should propagation be resolved? */
243  SCIP_Bool usedynamicprop, /**< whether we use a dynamic version of the propagation routine */
244  SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
245  SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact
246  * with symmetries handled by other routines */
247  )
248 {
249  int i;
250  int j;
251 
252  assert(consdata != NULL);
253 #ifndef NDEBUG
254  if ( usedynamicprop )
255  {
256  assert( ! mayinteract );
257  }
258 #endif
259 
260  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
261 
262  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals, nspcons) );
263  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights, nspcons) );
264  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vars, nspcons) );
265  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases, nspcons) );
266  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->roworder, nspcons) );
267 
268  /* if orbitope might interact with other symmetries, we cannot adapt the row order of orbitopes dynamically */
269  if ( usedynamicprop )
270  {
271  SCIP_CALL( SCIPhashmapCreate(&(*consdata)->rowindexmap, SCIPblkmem(scip), nspcons) );
272  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->rowused, nspcons) );
273  }
274 
275  for (i = 0; i < nspcons; ++i)
276  {
277  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals[i], nblocks) ); /*lint !e866*/
278  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights[i], nblocks) ); /*lint !e866*/
279  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars[i], vars[i], nblocks) ); /*lint !e866*/
280  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases[i], nblocks) ); /*lint !e866*/
281  (*consdata)->roworder[i] = i;
282 
283  if ( usedynamicprop )
284  {
285  (*consdata)->rowused[i] = FALSE;
286  }
287  }
288  (*consdata)->nrowsused = 0;
289 
290  (*consdata)->tmpvals = NULL;
291  (*consdata)->tmpvars = NULL;
292  (*consdata)->nspcons = nspcons;
293  (*consdata)->nblocks = nblocks;
294  (*consdata)->orbitopetype = orbitopetype;
295  (*consdata)->resolveprop = resolveprop;
296  (*consdata)->istrianglefixed = FALSE;
297  (*consdata)->ismodelcons = ismodelcons;
298  (*consdata)->mayinteract = mayinteract;
299  (*consdata)->usedynamicprop = usedynamicprop;
300 
301  /* get transformed variables, if we are in the transformed problem */
302  if ( SCIPisTransformed(scip) )
303  {
304  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvals, nspcons + nblocks) );
305  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvars, nspcons + nblocks) );
306 
307  for (i = 0; i < nspcons; ++i)
308  {
309  /* make sure that no variable gets multiaggregated (cannot be handled by cons_orbitope, since one cannot easily
310  * eliminate single variables from an orbitope constraint).
311  */
312  for (j = 0; j < nblocks; ++j)
313  {
314  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i][j], &(*consdata)->vars[i][j]) );
315  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i][j]) );
316  if ( usedynamicprop )
317  {
318  SCIP_CALL( SCIPhashmapInsert((*consdata)->rowindexmap, (*consdata)->vars[i][j], (void*) (size_t) i) );
319  }
320  }
321  }
322  }
323 
324  return SCIP_OKAY;
325 }
326 
327 
328 /** strengthen full orbitopes to packing/partitioning orbitopes if possible */
329 static
331  SCIP* scip, /**< SCIP data structure */
332  SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */
333  int* nrows, /**< pointer to number of rows of variable matrix */
334  int ncols, /**< number of columns of variable matrix */
335  SCIP_ORBITOPETYPE* type, /**< pointer to store type of orbitope constraint after strengthening */
336  SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact
337  * with symmetries handled by other routines */
338  )
339 {
340  SCIP_Bool* pprows = NULL;
341  int npprows;
342  int nrowsorig;
343 
344  assert( scip != NULL );
345  assert( vars != NULL );
346  assert( vars != NULL );
347  assert( *nrows > 0 );
348  assert( ncols > 0 );
349  assert( type != NULL );
350 
351  nrowsorig = *nrows;
352  SCIP_CALL( SCIPisPackingPartitioningOrbitope(scip, vars, *nrows, ncols, &pprows, &npprows, type) );
353 
354  /* If only some rows are contained in set packing/partitioning constraints, it may still be worth it
355  * to exploit the packing/partitioning structure on these rows, because packing/partitioning orbitopes
356  * or more restrictive than full orbitopes. If at least three rows have this property, we discard
357  * all rows not contained in set packing/partitioning constraints and add the smaller sub packing orbitope.
358  * This is only possible if the orbitope's symmetries do not interact with other symmetry handling
359  * methods (otherwise, dropping rows might change the variable order).
360  */
361  if ( npprows >= 3 && ! mayinteract )
362  {
363  int r = *nrows - 1;
364  int i;
365 
366  assert( pprows != NULL );
367 
368  while ( r >= 0 )
369  {
370  if ( ! pprows[r] )
371  {
372  for (i = r; i < *nrows - 1; ++i)
373  {
374  SCIP_VAR** row;
375  row = vars[i];
376  vars[i] = vars[i+1];
377  vars[i+1] = row;
378  }
379  *nrows -= 1;
380  }
381  --r;
382  }
384  }
385 
386  /* pprows might not have been initialized if there are no setppc conss */
387  if ( pprows != NULL )
388  {
389  SCIPfreeBlockMemoryArray(scip, &pprows, nrowsorig);
390  }
391 
392  return SCIP_OKAY;
393 }
394 
395 #ifdef PRINT_MATRIX
396 /** debug method, prints variable matrix */
397 static
398 void printMatrix(
399  SCIP* scip, /**< SCIP data structure */
400  SCIP_CONSDATA* consdata /**< the constraint data */
401  )
402 {
403  int i;
404  int j;
405 
406  assert( consdata != NULL );
407  assert( consdata->nspcons > 0 );
408  assert( consdata->nblocks > 0 );
409  assert( consdata->vars != NULL );
410 
411  for (j = 0; j < consdata->nblocks; ++j)
412  SCIPinfoMessage(scip, NULL, "-");
413 
414  SCIPinfoMessage(scip, NULL, "\n");
415  for (i = 0; i < consdata->nspcons; ++i)
416  {
417  for (j = 0; j < consdata->nblocks; ++j)
418  {
419  if ( SCIPvarGetUbLocal(consdata->vars[i][j]) - SCIPvarGetLbLocal(consdata->vars[i][j]) < 0.5 )
420  SCIPinfoMessage(scip, NULL, "%1.0f", REALABS(SCIPvarGetUbLocal(consdata->vars[i][j])));
421  else
422  SCIPinfoMessage(scip, NULL, " ");
423  }
424  SCIPinfoMessage(scip, NULL, "|\n");
425  }
426  for (j = 0; j < consdata->nblocks; ++j)
427  SCIPinfoMessage(scip, NULL, "-");
428  SCIPinfoMessage(scip, NULL, "\n");
429 }
430 #endif
431 
432 
433 #ifdef SHOW_SCI
434 /** Print SCI in nice form for debugging */
435 static
436 SCIP_RETCODE printSCI(
437  SCIP* scip, /**< SCIP pointer */
438  int p, /**< number of rows */
439  int q, /**< number of columns */
440  int** cases, /**< SCI dynamic programming table */
441  int i, /**< row position of bar */
442  int j /**< column position of bar */
443  )
444 {
445  int k;
446  int l;
447  int** M;
448  int p1;
449  int p2;
450 
451  SCIP_CALL( SCIPallocBufferArray(scip, &M, p) );
452  for (k = 0; k < p; ++k)
453  {
454  SCIP_CALL( SCIPallocBufferArray(scip, &M[k], q) ); /*lint !e866*/
455  for (l = 0; l < q; ++l)
456  M[k][l] = 0;
457  }
458 
459  /* first add bar */
460  for (l = j; l < q; ++l)
461  {
462  assert( M[i][l] == 0 );
463  M[i][l] = 1;
464  }
465 
466  /* then add shifted column */
467  p1 = i-1;
468  p2 = j-1;
469  do
470  {
471  assert( cases[p1][p2] != -1 );
472  assert( p1 >= 0 && p1 < i );
473  assert( p2 >= 0 && p2 < j );
474 
475  /* if case 1 */
476  if ( cases[p1][p2] == 1 )
477  --p2; /* decrease column */
478  else
479  {
480  /* case 2 or 3: */
481  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
482  assert( M[p1][p2] == 0 );
483  M[p1][p2] = -1;
484  if ( cases[p1][p2] == 3 )
485  break;
486  }
487  --p1; /* decrease row */
488  }
489  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
490  assert( cases[p1][p2] == 3 );
491 
492  /* now output matrix M */
493  for (l = 0; l < q; ++l)
494  SCIPinfoMessage(scip, NULL, "-");
495  SCIPinfoMessage(scip, NULL, "\n");
496 
497  for (k = 0; k < p; ++k)
498  {
499  for (l = 0; l < q; ++l)
500  {
501  if ( l > k )
502  SCIPinfoMessage(scip, NULL, "*");
503  else
504  {
505  switch (M[k][l])
506  {
507  case 1:
508  SCIPinfoMessage(scip, NULL, "+");
509  break;
510  case -1:
511  SCIPinfoMessage(scip, NULL, "-");
512  break;
513  case 0:
514  SCIPinfoMessage(scip, NULL, "#");
515  break;
516  default:
517  SCIPerrorMessage("unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]);
518  SCIPABORT();
519  }
520  }
521  }
522  SCIPinfoMessage(scip, NULL, "\n");
523  }
524 
525  for (l = 0; l < q; ++l)
526  SCIPinfoMessage(scip, NULL, "-");
527  SCIPinfoMessage(scip, NULL, "\n");
528 
529  for (k = 0; k < p; ++k)
530  SCIPfreeBufferArray(scip, &M[k]);
531  SCIPfreeBufferArray(scip, &M);
532 
533  return SCIP_OKAY;
534 }
535 #endif
536 
537 
538 /** copies the variables values from the solution to the constraint data structure */
539 static
540 void copyValues(
541  SCIP* scip, /**< the SCIP data structure */
542  SCIP_CONSDATA* consdata, /**< the constraint data */
543  SCIP_SOL* sol /**< a primal solution or NULL for the current LP optimum */
544  )
545 {
546  int i;
547  int j;
548 
549  assert( scip != NULL );
550  assert( consdata != NULL );
551  assert( consdata->nspcons > 0 );
552  assert( consdata->nblocks > 0 );
553  assert( consdata->vars != NULL );
554  assert( consdata->vals != NULL );
555 
556  for (i = 0; i < consdata->nspcons; ++i)
557  {
558  for (j = 0; j < consdata->nblocks; ++j)
559  consdata->vals[i][j] = SCIPgetSolVal(scip, sol, consdata->vars[i][j]);
560  }
561 }
562 
563 
564 /** compute the dynamic programming table for SC
565  *
566  * Build up dynamic programming table in order to find SCs with minimum weight.
567  *
568  * The values of the minimal SCIs are stored in @a weights.
569  * The array @a cases[i][j] stores which of the cases were applied to get @a weights[i][j].
570  * Here, 3 means that we have reached the upper limit.
571  *
572  * We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a
573  * bit more efficient.
574  */
575 static
576 void computeSCTable(
577  SCIP* scip, /**< SCIP pointer */
578  int nspcons, /**< number of set partitioning (packing) constraints <=> p */
579  int nblocks, /**< number of symmetric variable blocks <=> q */
580  SCIP_Real** weights, /**< SC weight table */
581  int** cases, /**< indicator of the SC cases */
582  SCIP_Real** vals /**< current solution */
583  )
584 {
585  SCIP_Real minvalue;
586  int diagsize;
587  int i;
588  int j;
589 
590  assert( weights != NULL );
591  assert( cases != NULL );
592  assert( vals != NULL );
593 
594 #ifndef NDEBUG
595  /* for debugging */
596  for (i = 0; i < nspcons; ++i)
597  {
598  for (j = 0; j < nblocks; ++j)
599  {
600  if ( i >= j )
601  {
602  weights[i][j] = -1.0;
603  cases[i][j] = -1;
604  }
605  }
606  }
607 #endif
608 
609  /* initialize diagonal */
610  minvalue = vals[0][0];
611  weights[0][0] = minvalue;
612  cases[0][0] = 3;
613 
614  /* get last row of triangle */
615  diagsize = nblocks;
616  if ( nspcons < nblocks )
617  diagsize = nspcons;
618 
619  for (j = 1; j < diagsize; ++j)
620  {
621  /* use LT to move entry as far to the left as possible */
622  if ( SCIPisLT(scip, vals[j][j], minvalue) )
623  {
624  minvalue = vals[j][j];
625  cases[j][j] = 3;
626  }
627  else
628  cases[j][j] = 1;
629  weights[j][j] = minvalue;
630  }
631 
632  /* initialize first column */
633  for (i = 1; i < nspcons; ++i)
634  {
635  weights[i][0] = weights[i-1][0] + vals[i][0];
636  cases[i][0] = 2; /* second case */
637  }
638 
639  /* build the table */
640  for (i = 2; i < nspcons; ++i)
641  {
642  for (j = 1; j < nblocks && j < i; ++j)
643  {
644  SCIP_Real weightleft;
645  SCIP_Real weightright;
646 
647  assert( cases[i-1][j] != -1 );
648  assert( cases[i-1][j-1] != -1 );
649 
650  weightleft = weights[i-1][j-1];
651  weightright = vals[i][j] + weights[i-1][j];
652 
653  /* For first column: cannot take left possibility */
654  if ( SCIPisLT(scip, weightleft, weightright) )
655  {
656  weights[i][j] = weightleft;
657  cases[i][j] = 1;
658  }
659  else
660  {
661  weights[i][j] = weightright;
662  cases[i][j] = 2;
663  }
664  }
665  }
666 }
667 
668 
669 /** fix upper right triangle if necessary */
670 static
672  SCIP* scip, /**< SCIP data structure */
673  SCIP_CONS* cons, /**< constraint to be processed */
674  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
675  int* nfixedvars /**< pointer to add up the number of found domain reductions */
676  )
677 {
678  SCIP_CONSDATA* consdata;
679  SCIP_VAR*** vars;
680  SCIP_Bool fixedglobal;
681  SCIP_Bool fixed;
682  int diagsize;
683  int nspcons;
684  int nblocks;
685  int i;
686  int j;
687 
688  assert( scip != NULL );
689  assert( cons != NULL );
690  assert( infeasible != NULL );
691  assert( nfixedvars != NULL );
692 
693  consdata = SCIPconsGetData(cons);
694  assert( consdata != NULL );
695  assert( consdata->nspcons > 0 );
696  assert( consdata->nblocks > 0 );
697  assert( consdata->vars != NULL );
698 
699  *infeasible = FALSE;
700  *nfixedvars = 0;
701 
702  if ( consdata->istrianglefixed )
703  return SCIP_OKAY;
704 
705  nspcons = consdata->nspcons;
706  nblocks = consdata->nblocks;
707  vars = consdata->vars;
708  fixedglobal = TRUE;
709 
710  /* get last row of triangle */
711  diagsize = nblocks;
712  if ( nspcons < nblocks )
713  diagsize = nspcons;
714 
715  /* fix variables to 0 */
716  for (i = 0; i < diagsize; ++i)
717  {
718  for (j = i+1; j < nblocks; ++j)
719  {
720  /* fix variable, if not in the root the fixation is local */
721  SCIP_CALL( SCIPfixVar(scip, vars[i][j], 0.0, infeasible, &fixed) );
722 
723  if ( *infeasible )
724  {
725  SCIPdebugMsg(scip, "The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n");
726  return SCIP_OKAY;
727  }
728 
729  if ( fixed )
730  ++(*nfixedvars);
731 
732  if ( SCIPvarGetUbGlobal(vars[i][j]) > 0.5 )
733  fixedglobal = FALSE;
734  }
735  }
736  if ( *nfixedvars > 0 )
737  {
738  SCIPdebugMsg(scip, "<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n", SCIPconsGetName(cons), fixedglobal ? "globally" : "locally", *nfixedvars);
739  }
740  else
741  {
742  SCIPdebugMsg(scip, "<%s>: Upper right triangle already fixed to 0.\n", SCIPconsGetName(cons));
743  }
744 
745  if ( fixedglobal )
746  consdata->istrianglefixed = TRUE;
747 
748  return SCIP_OKAY;
749 }
750 
751 
752 /** separates shifted column inequalities according to the solution stored in consdata->vals */
753 static
755  SCIP* scip, /**< the SCIP data structure */
756  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
757  SCIP_CONS* cons, /**< constraint */
758  SCIP_CONSDATA* consdata, /**< the constraint data */
759  SCIP_Bool* infeasible, /**< whether we detected infeasibility */
760  int* nfixedvars, /**< pointer to store the number of variables fixed */
761  int* ncuts /**< pointer to store number of separated SCIs */
762  )
763 {
764  SCIP_Real** vals;
765  SCIP_Real** weights;
766  SCIP_Real* tmpvals;
767  SCIP_VAR*** vars;
768  SCIP_VAR** tmpvars;
769  int** cases;
770  int nspcons;
771  int nblocks;
772  int i;
773  int j;
774  int l;
775 
776  assert( scip != NULL );
777  assert( conshdlr != NULL );
778  assert( cons != NULL );
779  assert( infeasible != NULL);
780  assert( nfixedvars != NULL );
781  assert( ncuts != NULL );
782 
783  assert( consdata != NULL );
784  assert( consdata->nspcons > 0 );
785  assert( consdata->nblocks > 0 );
786  assert( consdata->vars != NULL );
787  assert( consdata->vals != NULL );
788  assert( consdata->tmpvars != NULL );
789  assert( consdata->tmpvals != NULL );
790  assert( consdata->weights != NULL );
791  assert( consdata->cases != NULL );
792 
793  *infeasible = FALSE;
794  *nfixedvars = 0;
795  *ncuts = 0;
796 
797  nspcons = consdata->nspcons;
798  nblocks = consdata->nblocks;
799  vars = consdata->vars;
800  vals = consdata->vals;
801  tmpvars = consdata->tmpvars;
802  tmpvals = consdata->tmpvals;
803  weights = consdata->weights;
804  cases = consdata->cases;
805 
806  /* check for upper right triangle */
807  if ( ! consdata->istrianglefixed )
808  {
809  SCIP_CALL( fixTriangle(scip, cons, infeasible, nfixedvars) );
810  if ( *infeasible )
811  return SCIP_OKAY;
812  if ( *nfixedvars > 0 )
813  return SCIP_OKAY;
814  }
815 
816  /* compute table if necessary (i.e., not computed before) */
817  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
818 
819  /* loop through rows */
820  for (i = 1; i < nspcons && ! (*infeasible); ++i)
821  {
822  SCIP_Real bar; /* value of bar: */
823  int lastcolumn; /* last column considered as part of the bar */
824 
825  bar = 0.0;
826  lastcolumn = nblocks - 1;
827  if ( lastcolumn > i )
828  lastcolumn = i;
829 
830  /* traverse row from right to left: */
831  /* j >= 1, since for j = 0, i.e., the bar is a complete row, there does not exist an SCI */
832  for (j = lastcolumn; j > 0; --j)
833  {
834  bar += vals[i][j];
835 
836  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
837  if ( SCIPisEfficacious(scip, bar - weights[i-1][j-1]) )
838  {
839  SCIP_Real weight;
840  SCIP_ROW* row;
841 #ifdef SCIP_DEBUG
842  char name[SCIP_MAXSTRLEN];
843 #endif
844  int nvars;
845  int p1;
846  int p2;
847 
848  nvars = 0;
849  p1 = i-1;
850  p2 = j-1;
851  weight = 0.0;
852 
853  /* first add bar */
854  for (l = j; l <= lastcolumn; ++l)
855  {
856  tmpvars[nvars] = vars[i][l];
857  tmpvals[nvars] = 1.0;
858  nvars++;
859  }
860 
861  /* then add shifted column */
862  do
863  {
864  assert( cases[p1][p2] != -1 );
865  assert( p1 >= 0 && p1 < i );
866  assert( p2 >= 0 && p2 < j );
867 
868  /* if case 1 */
869  if (cases[p1][p2] == 1)
870  p2--; /* decrease column */
871  else
872  {
873  /* case 2 or 3: */
874  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
875  tmpvars[nvars] = vars[p1][p2];
876  tmpvals[nvars] = -1.0;
877  nvars++;
878  weight += vals[p1][p2];
879  if ( cases[p1][p2] == 3 )
880  break;
881  }
882  p1--; /* decrease row */
883  }
884  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
885  assert( cases[p1][p2] == 3 );
886 
887  /* generate cut */
888 #ifdef SCIP_DEBUG
889  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sci_%d_%d", i, j);
890  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
891 #else
892  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
893 #endif
894  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvars, tmpvars, tmpvals) );
895  /*SCIP_CALL( SCIPprintRow(scip, row, NULL) ); */
896  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
897  SCIP_CALL( SCIPreleaseRow(scip, &row) );
898  ++(*ncuts);
899 
900 #ifdef SHOW_SCI
901  SCIP_CALL( printSCI(scip, nspcons, nblocks, cases, i, j) );
902 #endif
903 
904  assert( SCIPisSumEQ(scip, weights[i-1][j-1], weight) );
905  }
906  }
907  }
908  return SCIP_OKAY;
909 }
910 
911 
912 /** propagation method for a single packing or partitioning orbitope constraint */
913 static
915  SCIP* scip, /**< SCIP data structure */
916  SCIP_CONS* cons, /**< constraint to be processed */
917  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
918  int* nfixedvars /**< pointer to add up the number of found domain reductions */
919  )
920 {
921  SCIP_CONSDATA* consdata;
922  SCIP_VAR*** vars;
923  SCIP_ORBITOPETYPE orbitopetype;
924  int* firstnonzeros;
925  int* lastones;
926  int* frontiersteps;
927  int lastoneprevrow;
928  int nspcons;
929  int nblocks;
930  int nsteps;
931  int i;
932  int j;
933 
934  assert( scip != NULL );
935  assert( cons != NULL );
936  assert( infeasible != NULL );
937  assert( nfixedvars != NULL );
938 
939  *nfixedvars = 0;
940 
941  if( !SCIPallowStrongDualReds(scip) )
942  return SCIP_OKAY;
943 
944  consdata = SCIPconsGetData(cons);
945  assert( consdata != NULL );
946  assert( consdata->nspcons > 0 );
947  assert( consdata->nblocks > 0 );
948  assert( consdata->vars != NULL );
949 
950  nspcons = consdata->nspcons;
951  nblocks = consdata->nblocks;
952  vars = consdata->vars;
953  orbitopetype = consdata->orbitopetype;
954 
955  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
956 
957  /* fix upper right triangle if still necessary */
958  if ( ! consdata->istrianglefixed )
959  {
960  int nfixed = 0;
961  SCIP_CALL( fixTriangle(scip, cons, infeasible, &nfixed) );
962  *nfixedvars += nfixed;
963  }
964 
965  /* prepare further propagation */
966  SCIP_CALL( SCIPallocBufferArray(scip, &firstnonzeros, nspcons) );
967  SCIP_CALL( SCIPallocBufferArray(scip, &lastones, nspcons) );
968  SCIP_CALL( SCIPallocBufferArray(scip, &frontiersteps, nblocks) );
969 
970 #ifdef PRINT_MATRIX
971  SCIPdebugMsg(scip, "Matrix:\n");
972  printMatrix(scip, consdata);
973 #endif
974 
975  /* propagate */
976  lastoneprevrow = 0;
977  lastones[0] = 0;
978 
979  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING )
980  {
981  /* packing case: if entry (0,0) is fixed to 0 */
982  if ( SCIPvarGetUbLocal(vars[0][0]) < 0.5 )
983  {
984  lastoneprevrow = -1;
985  lastones[0] = -1;
986  }
987  }
988  nsteps = 0;
989 
990  for (i = 1; i < nspcons; ++i)
991  {
992  int lastcolumn;
993  int firstnonzeroinrow;
994  int lastoneinrow;
995  SCIP_Bool infrontier;
996 
997  /* last column considered as part of the bar: */
998  lastcolumn = nblocks - 1;
999  if ( lastcolumn > i )
1000  lastcolumn = i;
1001 
1002  /* find first position not fixed to 0 (partitioning) or fixed to 1 (packing) */
1003  firstnonzeroinrow = -1;
1004  for (j = 0; j <= lastcolumn; ++j)
1005  {
1006  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1007  {
1008  /* partitioning case: if variable is not fixed to 0 */
1009  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1010  {
1011  firstnonzeroinrow = j;
1012  break;
1013  }
1014  }
1015  else
1016  {
1017  /* packing case: if variable is fixed to 1 */
1018  if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
1019  {
1020  firstnonzeroinrow = j;
1021  break;
1022  }
1023  }
1024  }
1025  /* if all variables are fixed to 0 in the partitioning case - should not happen */
1026  if ( firstnonzeroinrow == -1 && orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1027  {
1028  SCIPdebugMsg(scip, " -> Infeasible node: all variables in row %d are fixed to 0.\n", i);
1029  *infeasible = TRUE;
1030  /* conflict should be analyzed by setppc constraint handler */
1031  goto TERMINATE;
1032  }
1033  firstnonzeros[i] = firstnonzeroinrow;
1034  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || firstnonzeroinrow >= 0 );
1035  assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn );
1036 
1037  /* compute rightmost possible position for a 1 */
1038  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneprevrow );
1039  assert( lastoneprevrow <= lastcolumn );
1040 
1041  /* if we are at right border or if entry in column lastoneprevrow+1 is fixed to 0 */
1042  infrontier = FALSE;
1043  assert( lastoneprevrow + 1 >= 0 );
1044  if ( lastoneprevrow == nblocks-1 || SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 ) /*lint !e679*/
1045  lastoneinrow = lastoneprevrow;
1046  else
1047  {
1048  lastoneinrow = lastoneprevrow + 1;
1049  frontiersteps[nsteps++] = i;
1050  infrontier = TRUE;
1051  }
1052 
1053  /* store lastoneinrow */
1054  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneinrow );
1055  assert( lastoneinrow <= lastcolumn );
1056  lastones[i] = lastoneinrow;
1057 
1058  /* check whether we are infeasible */
1059  if ( firstnonzeroinrow > lastoneinrow )
1060  {
1061  int k;
1062 
1063 #ifdef SCIP_DEBUG
1064  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1065  {
1066  SCIPdebugMsg(scip, " -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n",
1067  i, firstnonzeroinrow, lastoneinrow);
1068  }
1069  else
1070  {
1071  SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n",
1072  i, firstnonzeroinrow, lastoneinrow);
1073  }
1074 #endif
1075  /* check if conflict analysis is applicable */
1077  {
1078  /* conflict analysis only applicable in SOLVING stage */
1079  assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) );
1080 
1081  /* perform conflict analysis */
1083 
1084  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1085  {
1086  /* add bounds (variables fixed to 0) that result in the first nonzero entry */
1087  for (j = 0; j <= lastcolumn; ++j)
1088  {
1089  /* add varaibles in row up to the first variable fixed to 0 */
1090  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1091  break;
1092 
1093  assert( SCIPvarGetUbLocal(vars[i][j]) < 0.5 );
1094  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1095  }
1096  }
1097  else
1098  {
1099  /* add bounds that result in the last one - check top left entry for packing case */
1100  if ( lastones[0] == -1 )
1101  {
1102  assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1103  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1104  }
1105 
1106  /* mark variable fixed to 1 */
1107  assert( SCIPvarGetLbLocal(vars[i][firstnonzeroinrow]) > 0.5 );
1108  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][firstnonzeroinrow]) );
1109  }
1110 
1111  /* add bounds that result in the last one - pass through rows */
1112  for (k = 1; k < i; ++k)
1113  {
1114  int l;
1115  l = lastones[k] + 1;
1116 
1117  /* if the frontier has not moved and we are not beyond the matrix boundaries */
1118  if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1119  {
1120  assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1121  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1122  }
1123  }
1124  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1125  }
1126 
1127  *infeasible = TRUE;
1128  goto TERMINATE;
1129  }
1130 
1131  /* fix entries beyond the last possible position for a 1 in the row to 0 (see Lemma 1 in the paper) */
1132  for (j = lastoneinrow+1; j <= lastcolumn; ++j)
1133  {
1134  /* if the entry is not yet fixed to 0 */
1135  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1136  {
1137  SCIP_Bool tightened;
1138  int inferInfo;
1139 
1140  SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 0.\n", i, j);
1141 
1142  tightened = FALSE;
1143 
1144  /* fix variable to 0 and store position of (i,lastoneinrow+1) for conflict resolution */
1145  inferInfo = i * nblocks + lastoneinrow + 1;
1146  /* correction according to Lemma 1 in the paper (second part): store (i,lastoneinrow+2) */
1147  if ( !infrontier )
1148  ++inferInfo;
1149  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i][j], FALSE, cons, inferInfo, infeasible, &tightened) );
1150 
1151  /* if entry is fixed to one -> infeasible node */
1152  if ( *infeasible )
1153  {
1154  SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow);
1155  /* check if conflict analysis is applicable */
1157  {
1158  int k;
1159 
1160  /* conflict analysis only applicable in SOLVING stage */
1161  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip));
1162 
1163  /* perform conflict analysis */
1165 
1166  /* add current bound */
1167  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1168 
1169  /* add bounds that result in the last one - check top left entry for packing case */
1170  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING && lastones[0] == -1 )
1171  {
1172  assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1173  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1174  }
1175 
1176  /* add bounds that result in the last one - pass through rows */
1177  for (k = 1; k < i; ++k)
1178  {
1179  int l;
1180  l = lastones[k] + 1;
1181 
1182  /* if the frontier has not moved and we are not beyond the matrix boundaries */
1183  if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1184  {
1185  assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1186  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1187  }
1188  }
1189  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1190  }
1191 
1192  goto TERMINATE;
1193  }
1194  if ( tightened )
1195  ++(*nfixedvars);
1196  }
1197  }
1198 
1199  lastoneprevrow = lastoneinrow;
1200  }
1201 
1202  /* check whether fixing any entry to 0 results in a contradiction -> loop through rows in frontiersteps (a.k.a. gamma) */
1203  for (j = 0; j < nsteps; ++j)
1204  {
1205  int s;
1206  int lastoneinrow;
1207 
1208  s = frontiersteps[j];
1209  lastoneinrow = lastones[s];
1210  /* note for packing case: if we are in a frontier step then lastoneinrow >= 0 */
1211  assert( 0 <= lastoneinrow && lastoneinrow < nblocks );
1212 
1213  /* if entry is not fixed */
1214  if ( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 && SCIPvarGetUbLocal(vars[s][lastoneinrow]) > 0.5 )
1215  {
1216  int betaprev;
1217  betaprev = lastoneinrow - 1;
1218 
1219  /* loop through rows below s */
1220  for (i = s+1; i < nspcons; ++i)
1221  {
1222  int beta;
1223 
1224  assert( betaprev + 1 >= 0 );
1225  if ( betaprev == nblocks-1 || SCIPvarGetUbLocal(vars[i][betaprev+1]) < 0.5 ) /*lint !e679*/
1226  beta = betaprev;
1227  else
1228  beta = betaprev + 1;
1229  assert( -1 <= beta && beta < nblocks );
1230 
1231  if ( firstnonzeros[i] > beta )
1232  {
1233  SCIP_Bool tightened;
1234  int inferInfo;
1235 
1236  /* can fix (s,lastoneinrow) (a.k.a (s,alpha)) to 1
1237  * (do not need to fix other entries to 0, since they will be
1238  * automatically fixed by SCIPtightenVarLb.)
1239  */
1240  assert( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 );
1241  SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow);
1242 
1243  tightened = FALSE;
1244 
1245  /* store position (i,firstnonzeros[i]) */
1246  inferInfo = nblocks * nspcons + i * nblocks + firstnonzeros[i];
1247  SCIP_CALL( SCIPinferBinvarCons(scip, vars[s][lastoneinrow], TRUE, cons, inferInfo, infeasible, &tightened) );
1248 
1249  assert( !(*infeasible) );
1250  if ( tightened )
1251  ++(*nfixedvars);
1252  break;
1253  }
1254  betaprev = beta;
1255  }
1256  }
1257  }
1258 
1259  TERMINATE:
1260  SCIPfreeBufferArray(scip, &frontiersteps);
1261  SCIPfreeBufferArray(scip, &lastones);
1262  SCIPfreeBufferArray(scip, &firstnonzeros);
1263 
1264  return SCIP_OKAY;
1265 }
1266 
1267 
1268 /* Compute dynamic order of rows based on the branching decisions, i.e., the row of the first branching variable
1269  * determines the first row in the new ordering, the row of the second branching variable determines the second
1270  * row in the new ordering if it differs from the row of the first branching variable, and so on.
1271  *
1272  * The roworder array stores this reordering, where acutally only the first maxrowlabel entries encode the
1273  * reordering.
1274  */
1275 static
1277  SCIP* scip, /**< SCIP pointer */
1278  SCIP_HASHMAP* rowindexmap, /**< map of variables to indices in orbitope vars matrix */
1279  SCIP_Bool* rowused, /**< bitset marking whether a row has been considered in the new order */
1280  int* roworder, /**< reordering of the rows w.r.t. branching decisions */
1281  int nrows, /**< number of rows in orbitope */
1282  int ncols, /**< number of columns in orbitope */
1283  int* maxrowlabel /**< maximum row label in ordering */
1284  )
1285 {
1286  int i;
1287  SCIP_NODE* node;
1288  int* branchdecisions;
1289  int nbranchdecision;
1290 
1291  assert( scip != NULL );
1292  assert( rowindexmap != NULL );
1293  assert( roworder != NULL );
1294  assert( nrows > 0 );
1295  assert( maxrowlabel != NULL );
1296 
1297  SCIP_CALL( SCIPallocBufferArray(scip, &branchdecisions, nrows * ncols) );
1298  nbranchdecision = 0;
1299 
1300  /* get current node */
1301  node = SCIPgetCurrentNode(scip);
1302 
1303  /* follow path to the root (in the root no domains were changed due to branching) */
1304  while ( SCIPnodeGetDepth(node) != 0 )
1305  {
1306  SCIP_BOUNDCHG* boundchg;
1307  SCIP_DOMCHG* domchg;
1308  SCIP_VAR* branchvar;
1309  int nboundchgs;
1310 
1311  /* get domain changes of current node */
1312  domchg = SCIPnodeGetDomchg(node);
1313  assert( domchg != NULL );
1314 
1315  /* loop through all bound changes */
1316  nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
1317  for (i = 0; i < nboundchgs; ++i)
1318  {
1319  /* get bound change info */
1320  boundchg = SCIPdomchgGetBoundchg(domchg, i);
1321  assert( boundchg != NULL );
1322 
1323  /* branching decisions have to be in the beginning of the bound change array */
1325  break;
1326 
1327  /* get corresponding branching variable */
1328  branchvar = SCIPboundchgGetVar(boundchg);
1329 
1330  /* we only consider binary variables */
1331  if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY )
1332  {
1333  int rowidx;
1334 
1335  /* make sure that branching variable is present in the orbitope */
1336  if ( ! SCIPhashmapExists(rowindexmap, (void*) branchvar) )
1337  continue;
1338 
1339  rowidx = (int) (size_t) SCIPhashmapGetImage(rowindexmap, (void*) branchvar);
1340  branchdecisions[nbranchdecision++] = rowidx;
1341  }
1342  }
1343 
1344  node = SCIPnodeGetParent(node);
1345  }
1346 
1347  /* Insert branching decisions of current path into global row order.
1348  * Iterate in reverse order over branching decisions to get the path
1349  * from the root to the current node.
1350  */
1351  for (i = nbranchdecision - 1; i >= 0; --i)
1352  {
1353  if ( ! rowused[branchdecisions[i]] )
1354  {
1355  roworder[*maxrowlabel] = branchdecisions[i];
1356  rowused[branchdecisions[i]] = TRUE;
1357  *maxrowlabel += 1;
1358  }
1359  }
1360 
1361  SCIPfreeBufferArray(scip, &branchdecisions);
1362 
1363  return SCIP_OKAY;
1364 }
1365 
1366 
1367 /* Compute lexicographically minimal face of the hypercube w.r.t. some coordinate fixing */
1368 static
1370  SCIP_VAR*** vars, /**< variable matrix */
1371  int** lexminfixes, /**< fixings characterzing lex-min face */
1372  int* minfixedrowlexmin, /**< index of minimum fixed row for each column or
1373  * NULL (if in prop) */
1374  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility has been
1375  * detected or NULL (if in resprop) */
1376  int m, /**< number of rows in vars */
1377  int n, /**< number of columns in vars */
1378  int nrowsused, /**< number of rows considered in propagation */
1379  SCIP_Bool resprop /**< whether we are in resprop (TRUE) or prop (FALSE) */
1380  )
1381 {
1382  int i;
1383  int j;
1384  *infeasible = FALSE;
1385 
1386  assert( vars != NULL );
1387  assert( lexminfixes != NULL );
1388  assert( !resprop || minfixedrowlexmin != NULL );
1389  assert( m > 0 );
1390  assert( n > 0 );
1391  assert( nrowsused > 0 );
1392  assert( nrowsused <= m );
1393  assert( infeasible != NULL );
1394 
1395  /* iterate over columns in reverse order and find the lexicographically minimal face
1396  * of the hypercube containing lexminfixes
1397  */
1398  for (j = n - 2; j >= 0; --j)
1399  {
1400  int maxdiscriminating = m;
1401  int minfixed = -1;
1402 
1403  /* fix free entries in column j to the corresponding value in column j + 1 and collect some information */
1404  for (i = 0; i < nrowsused; ++i)
1405  {
1406  /* is row i j-discriminating? */
1407  if ( minfixed == -1 && lexminfixes[i][j] != 0 && lexminfixes[i][j + 1] != 1 )
1408  {
1409  assert( lexminfixes[i][j + 1] == 0 );
1410 
1411  maxdiscriminating = i;
1412  }
1413 
1414  /* is row i j-fixed? */
1415  if ( minfixed == -1 && lexminfixes[i][j] != lexminfixes[i][j + 1] && lexminfixes[i][j] != 2 )
1416  {
1417  assert( lexminfixes[i][j + 1] != 2 );
1418 
1419  minfixed = i;
1420 
1421  /* detect infeasibility */
1422  if ( maxdiscriminating > minfixed )
1423  {
1424  *infeasible = TRUE;
1425 
1426  return SCIP_OKAY;
1427  }
1428  }
1429  }
1430 
1431  /* ensure that column j is lexicographically not smaller than column j + 1 */
1432  for (i = 0; i < nrowsused; ++i)
1433  {
1434  if ( lexminfixes[i][j] == 2 )
1435  {
1436  if ( i < maxdiscriminating || minfixed == -1 )
1437  lexminfixes[i][j] = lexminfixes[i][j + 1];
1438  else if ( i == maxdiscriminating )
1439  lexminfixes[i][j] = 1;
1440  else
1441  lexminfixes[i][j] = 0;
1442  }
1443  }
1444 
1445  if ( resprop )
1446  {
1447  assert( minfixedrowlexmin != NULL );
1448 
1449  /* store minimum fixed row */
1450  if ( minfixed == -1 )
1451  minfixedrowlexmin[j] = nrowsused - 1;
1452  else
1453  minfixedrowlexmin[j] = minfixed;
1454 
1455  /* columns 1, ..., n-2 are contained in two columns (take the minimum) and
1456  * the minimum fixed row of column n-1 is determined by column n-2 */
1457  if ( minfixedrowlexmin[j + 1] < minfixedrowlexmin[j] )
1458  minfixedrowlexmin[j + 1] = minfixedrowlexmin[j];
1459  }
1460  }
1461 
1462  return SCIP_OKAY;
1463 }
1464 
1465 
1466 /* Compute lexicographically maximal face of the hypercube w.r.t. some coordinate fixing */
1467 static
1469  SCIP_VAR*** vars, /**< variable matrix */
1470  int** lexmaxfixes, /**< fixings characterzing lex-max face */
1471  int* minfixedrowlexmax, /**< index of minimum fixed row for each column or
1472  * NULL (if in prop) */
1473  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility has been
1474  * detected or NULL (if in resprop) */
1475  int m, /**< number of rows in vars */
1476  int n, /**< number of columns in vars */
1477  int nrowsused, /**< number of rows considered in propagation */
1478  SCIP_Bool resprop /**< whether we are in resprop (TRUE) or prop (FALSE) */
1479  )
1480 {
1481  int i;
1482  int j;
1483  *infeasible = FALSE;
1484 
1485  assert( vars != NULL );
1486  assert( lexmaxfixes != NULL );
1487  assert( !resprop || minfixedrowlexmax != NULL );
1488  assert( m > 0 );
1489  assert( n > 0 );
1490  assert( nrowsused > 0 );
1491  assert( nrowsused <= m );
1492  assert( infeasible != NULL );
1493 
1494  for (j = 1; j < n; ++j)
1495  {
1496  int maxdiscriminating = m;
1497  int minfixed = -1;
1498 
1499  /* fix free entries in column j to the corresponding value in column j - 1 and collect some information */
1500  for (i = 0; i < nrowsused; ++i)
1501  {
1502  /* is row i j-discriminating? */
1503  if ( minfixed == -1 && lexmaxfixes[i][j - 1] != 0 && lexmaxfixes[i][j] != 1 )
1504  {
1505  assert( lexmaxfixes[i][j - 1] == 1 );
1506 
1507  maxdiscriminating = i;
1508  }
1509 
1510  /* is row i j-fixed? */
1511  if ( minfixed == -1 && lexmaxfixes[i][j - 1] != lexmaxfixes[i][j] && lexmaxfixes[i][j] != 2 )
1512  {
1513  assert( lexmaxfixes[i][j - 1] != 2 );
1514 
1515  minfixed = i;
1516 
1517  /* detect infeasibility */
1518  if ( maxdiscriminating > minfixed )
1519  {
1520  *infeasible = TRUE;
1521 
1522  return SCIP_OKAY;
1523  }
1524  }
1525  }
1526 
1527  /* ensure that column j is lexicographically not greater than column j - 1 */
1528  for (i = 0; i < nrowsused; ++i)
1529  {
1530  if ( lexmaxfixes[i][j] == 2 )
1531  {
1532  if ( i < maxdiscriminating || minfixed == -1 )
1533  lexmaxfixes[i][j] = lexmaxfixes[i][j - 1];
1534  else if ( i == maxdiscriminating )
1535  lexmaxfixes[i][j] = 0;
1536  else
1537  lexmaxfixes[i][j] = 1;
1538  }
1539  }
1540 
1541  if ( resprop )
1542  {
1543  assert( minfixedrowlexmax != NULL );
1544 
1545  /* store minimum fixed row */
1546  if ( minfixed == -1 )
1547  minfixedrowlexmax[j] = nrowsused - 1;
1548  else
1549  minfixedrowlexmax[j] = minfixed;
1550 
1551  /* columns 1, ..., n-2 are contained in two columns (take the minimum) and
1552  * the minimum fixed row of column 0 is determined by column 1 */
1553  if ( minfixedrowlexmax[j - 1] < minfixedrowlexmax[j] )
1554  minfixedrowlexmax[j - 1] = minfixedrowlexmax[j];
1555  }
1556  }
1557 
1558  return SCIP_OKAY;
1559 }
1560 
1561 
1562 /** propagation method for a single packing or partitioning orbitope constraint */
1563 static
1565  SCIP* scip, /**< SCIP data structure */
1566  SCIP_CONS* cons, /**< constraint to be processed */
1567  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
1568  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1569  SCIP_Bool dynamic /**< whether we use a dynamic propagation routine */
1570  )
1571 {
1572  SCIP_CONSDATA* consdata;
1573  SCIP_VAR*** vars;
1574  int** lexminfixes;
1575  int** lexmaxfixes;
1576  int* roworder;
1577  int nrowsused;
1578  int i;
1579  int j;
1580  int m;
1581  int n;
1582 
1583  assert( scip != NULL );
1584  assert( cons != NULL );
1585  assert( infeasible != NULL );
1586  assert( nfixedvars != NULL );
1587 
1588  *nfixedvars = 0;
1589  *infeasible = FALSE;
1590 
1591  /* @todo Can the following be removed? */
1592  if ( ! SCIPallowStrongDualReds(scip) )
1593  return SCIP_OKAY;
1594 
1595  /* do nothing if we use dynamic propagation and if we are in a probing node */
1596  if ( dynamic && SCIPinProbing(scip) )
1597  return SCIP_OKAY;
1598 
1599  consdata = SCIPconsGetData(cons);
1600  assert( consdata != NULL );
1601  assert( consdata->nspcons > 0 );
1602  assert( consdata->nblocks > 0 );
1603  assert( consdata->vars != NULL );
1604  assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL );
1605 
1606  m = consdata->nspcons;
1607  n = consdata->nblocks;
1608  vars = consdata->vars;
1609 
1610  /* determine order of orbitope rows dynamically by branching decisions */
1611  if ( dynamic )
1612  {
1613  SCIP_CALL( computeDynamicRowOrder(scip, consdata->rowindexmap, consdata->rowused,
1614  consdata->roworder, m, n, &(consdata->nrowsused)) );
1615 
1616  /* if no branching variable is contained in the full orbitope */
1617  if ( consdata->nrowsused == 0 )
1618  return SCIP_OKAY;
1619 
1620  nrowsused = consdata->nrowsused;
1621  }
1622  else
1623  nrowsused = m;
1624  roworder = consdata->roworder;
1625 
1626  /* Initialize lexicographically minimal matrix by fixed entries at the current node.
1627  * Free entries in the last column are set to 0.
1628  */
1629  SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) );
1630  for (i = 0; i < nrowsused; ++i)
1631  {
1632  SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/
1633  }
1634 
1635  for (i = 0; i < nrowsused; ++i)
1636  {
1637  int origrow;
1638 
1639  origrow = roworder[i];
1640 
1641  for (j = 0; j < n; ++j)
1642  {
1643  if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 )
1644  lexminfixes[i][j] = 1;
1645  else if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 || j == n - 1 )
1646  lexminfixes[i][j] = 0;
1647  else
1648  lexminfixes[i][j] = 2;
1649  }
1650  }
1651 
1652  /* find lexicographically minimal face of hypercube containing lexmin fixes */
1653  SCIP_CALL( findLexMinFace(vars, lexminfixes, NULL, infeasible, m, n, nrowsused, FALSE) );
1654 
1655  if ( *infeasible == TRUE )
1656  goto FREELEXMIN;
1657 
1658  /* Initialize lexicographically maximal matrix by fixed entries at the current node.
1659  * Free entries in the first column are set to 1.
1660  */
1661  SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) );
1662  for (i = 0; i < nrowsused; ++i)
1663  {
1664  SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/
1665  }
1666 
1667  for (i = 0; i < nrowsused; ++i)
1668  {
1669  int origrow;
1670 
1671  origrow = roworder[i];
1672 
1673  for (j = 0; j < n; ++j)
1674  {
1675  if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 )
1676  lexmaxfixes[i][j] = 0;
1677  else if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 || j == 0 )
1678  lexmaxfixes[i][j] = 1;
1679  else
1680  lexmaxfixes[i][j] = 2;
1681  }
1682  }
1683 
1684  /* find lexicographically maximal face of hypercube containing lexmax fixes */
1685  SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, NULL, infeasible, m, n, nrowsused, FALSE) );
1686 
1687  if ( *infeasible )
1688  goto FREELEXMAX;
1689 
1690  /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this
1691  * row to the corresponding value in lexminfixes (or lexmaxfixes).
1692  */
1693  for (j = 0; j < n; ++j)
1694  {
1695  for (i = 0; i < nrowsused; ++i)
1696  {
1697  int origrow;
1698 
1699  origrow = roworder[i];
1700 
1701  if ( lexminfixes[i][j] != lexmaxfixes[i][j] )
1702  break;
1703 
1704  if ( SCIPvarGetLbLocal(vars[origrow][j]) < 0.5 && SCIPvarGetUbLocal(vars[origrow][j]) > 0.5 )
1705  {
1706  SCIP_Bool success;
1707 
1708  SCIP_CALL( SCIPinferBinvarCons(scip, vars[origrow][j], (SCIP_Bool) lexminfixes[i][j],
1709  cons, 0, infeasible, &success) );
1710 
1711  if ( success )
1712  *nfixedvars += 1;
1713  }
1714  }
1715  }
1716 
1717  FREELEXMAX:
1718  for (i = 0; i < nrowsused; ++i)
1719  SCIPfreeBufferArray(scip, &lexmaxfixes[i]);
1720  SCIPfreeBufferArray(scip, &lexmaxfixes);
1721 
1722  FREELEXMIN:
1723  for (i = 0; i < nrowsused; ++i)
1724  SCIPfreeBufferArray(scip, &lexminfixes[i]);
1725  SCIPfreeBufferArray(scip, &lexminfixes);
1726 
1727  return SCIP_OKAY;
1728 }
1729 
1730 
1731 /** propagation method for a single orbitope constraint */
1732 static
1734  SCIP* scip, /**< SCIP data structure */
1735  SCIP_CONS* cons, /**< constraint to be processed */
1736  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
1737  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1738  )
1739 {
1740  SCIP_CONSDATA* consdata;
1741  SCIP_ORBITOPETYPE orbitopetype;
1742 
1743  assert( scip != NULL );
1744  assert( cons != NULL );
1745  assert( infeasible != NULL );
1746  assert( nfixedvars != NULL );
1747 
1748  consdata = SCIPconsGetData(cons);
1749  assert( consdata != NULL );
1750 
1751  orbitopetype = consdata->orbitopetype;
1752 
1753  if ( orbitopetype == SCIP_ORBITOPETYPE_FULL )
1754  {
1755  SCIP_CALL( propagateFullOrbitopeCons(scip, cons, infeasible, nfixedvars,
1756  consdata->usedynamicprop && !consdata->ismodelcons) );
1757  }
1758  else
1759  {
1760  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
1761  SCIP_CALL( propagatePackingPartitioningCons(scip, cons, infeasible, nfixedvars) );
1762  }
1763 
1764  return SCIP_OKAY;
1765 }
1766 
1767 
1768 /** Propagation conflict resolving method of propagator
1769  *
1770  * In this function we use that all variable reductions that can be found by the propagation algorithm
1771  * are only due to the fixed variables that are in or above the minimum fixed row of each pair of adjacent
1772  * columns of the lexmin and lexmax matrices.
1773  *
1774  * Since the storage of an integer is not enough to store the complete information about the fixing,
1775  * we have to use the linear time algorithm for finding the lexmin and lexmax
1776  * matrices and determine from this the minimum fixed rows.
1777  */
1778 static
1780  SCIP* scip, /**< SCIP data structure */
1781  SCIP_CONSHDLR* conshdlr, /**< constraint handler of the corresponding constraint */
1782  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1783  int inferinfo, /**< inference information */
1784  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1785  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1786  )
1787 { /*lint --e{715}*/
1788  SCIP_CONSDATA* consdata;
1789  SCIP_VAR*** vars;
1790  int** lexminfixes;
1791  int** lexmaxfixes;
1792  int* roworder;
1793  int* minfixedrowlexmin;
1794  int* minfixedrowlexmax;
1795  int i;
1796  int j;
1797  int m;
1798  int n;
1799  int nrowsused;
1800  SCIP_Bool dynamic;
1801  SCIP_Bool terminate;
1802 
1803  *result = SCIP_DIDNOTFIND;
1804 
1805  assert( scip != NULL );
1806  assert( conshdlr != NULL );
1807  assert( cons != NULL );
1808  assert( result != NULL );
1809 
1810  consdata = SCIPconsGetData(cons);
1811  assert( consdata != NULL );
1812  assert( consdata->nspcons > 0 );
1813  assert( consdata->nblocks > 0 );
1814  assert( consdata->vars != NULL );
1815  assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL );
1816 
1817  dynamic = consdata->usedynamicprop && !consdata->ismodelcons;
1818  m = consdata->nspcons;
1819  n = consdata->nblocks;
1820  vars = consdata->vars;
1821 
1822  if ( dynamic )
1823  {
1824  assert( consdata->roworder != NULL );
1825  assert( consdata->nrowsused > 0 );
1826 
1827  nrowsused = consdata->nrowsused;
1828  }
1829  else
1830  nrowsused = m;
1831  roworder = consdata->roworder;
1832 
1833  assert( inferinfo <= consdata->nspcons );
1834 
1835  /* Initialize lexicographically minimal matrix by fixed entries at the current node.
1836  * Free entries in the last column are set to 0.
1837  */
1838  SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) );
1839  for (i = 0; i < nrowsused; ++i)
1840  {
1841  SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/
1842  }
1843 
1844  /* store minimum fixed row for each column */
1845  SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmin, n) );
1846  minfixedrowlexmin[n - 1] = -1;
1847 
1848  for (i = 0; i < nrowsused; ++i)
1849  {
1850  int origrow;
1851 
1852  origrow = roworder[i];
1853 
1854  for (j = 0; j < n; ++j)
1855  {
1856  if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 )
1857  lexminfixes[i][j] = 1;
1858  else if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 || j == n - 1 )
1859  lexminfixes[i][j] = 0;
1860  else
1861  lexminfixes[i][j] = 2;
1862  }
1863  }
1864 
1865  /* find lexicographically minimal face of hypercube containing lexmin fixes */
1866  SCIP_CALL( findLexMinFace(vars, lexminfixes, minfixedrowlexmin, &terminate, m, n, nrowsused, TRUE) );
1867 
1868  if ( terminate )
1869  goto FREELEXMIN;
1870 
1871  /* Initialize lexicographically maximal matrix by fixed entries at the current node.
1872  * Free entries in the first column are set to 1.
1873  */
1874  SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) );
1875  for (i = 0; i < nrowsused; ++i)
1876  {
1877  SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/
1878  }
1879 
1880  /* store minimum fixed row for each column */
1881  SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmax, n) );
1882  minfixedrowlexmax[0] = -1;
1883 
1884  for (i = 0; i < nrowsused; ++i)
1885  {
1886  int origrow;
1887 
1888  origrow = roworder[i];
1889 
1890  for (j = 0; j < n; ++j)
1891  {
1892  if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 )
1893  lexmaxfixes[i][j] = 0;
1894  else if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 || j == 0 )
1895  lexmaxfixes[i][j] = 1;
1896  else
1897  lexmaxfixes[i][j] = 2;
1898  }
1899  }
1900 
1901  /* find lexicographically maximal face of hypercube containing lexmax fixes */
1902  SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, minfixedrowlexmax, &terminate, m, n, nrowsused, TRUE) );
1903 
1904  if ( terminate )
1905  goto FREELEXMAX;
1906 
1907  /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this
1908  * row to the corresponding value in lexminfixes (or lexmaxfixes).
1909  */
1910  for (j = 0; j < n; ++j)
1911  {
1912  int ub = MAX(minfixedrowlexmin[j], minfixedrowlexmax[j]);
1913 
1914  for (i = 0; i <= ub; ++i)
1915  {
1916  int origrow;
1917 
1918  origrow = roworder[i];
1919 
1920  if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 ||
1921  SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 )
1922  {
1923  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[origrow][j]) );
1924  *result = SCIP_SUCCESS;
1925  }
1926  }
1927  }
1928 
1929  FREELEXMAX:
1930  SCIPfreeBufferArray(scip, &minfixedrowlexmax);
1931  for (i = 0; i < nrowsused; ++i)
1932  SCIPfreeBufferArray(scip, &lexmaxfixes[i]);
1933  SCIPfreeBufferArray(scip, &lexmaxfixes);
1934 
1935  FREELEXMIN:
1936  SCIPfreeBufferArray(scip, &minfixedrowlexmin);
1937  for (i = 0; i < nrowsused; ++i)
1938  SCIPfreeBufferArray(scip, &lexminfixes[i]);
1939  SCIPfreeBufferArray(scip, &lexminfixes);
1940 
1941  return SCIP_OKAY;
1942 }
1943 
1944 
1945 /** Propagation conflict resolving method of propagator
1946  *
1947  * In this function we use that the propagation method above implicitly propagates SCIs, i.e., every
1948  * fixing can also be gotten via an SCI-fixing.
1949  *
1950  * Since the storage of an integer is not enough to store the complete information about the fixing
1951  * nor a complete shifted column, we have to use the linear time algorithm for SCIs.
1952  *
1953  * The inferinfo integer is set as follows:
1954  *
1955  * - If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1
1956  * then we fix these entries to 0 and inferinfo is i * nblocks + j, where (i,j) is the leader of the
1957  * bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments
1958  * above).
1959  *
1960  * - If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to
1961  * 1 and inferinfo is (nspcons*nblocks) + i * nblocks + j, where (i,j) is the leader of the bar; see
1962  * Proposition 1 (2c).
1963  */
1964 static
1966  SCIP* scip, /**< SCIP data structure */
1967  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1968  int inferinfo, /**< inference information */
1969  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1970  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1971  )
1972 { /*lint --e{715}*/
1973  SCIP_CONSDATA* consdata;
1974  SCIP_Real** vals;
1975  SCIP_Real** weights;
1976  SCIP_VAR*** vars;
1977  SCIP_ORBITOPETYPE orbitopetype;
1978  int** cases;
1979 
1980  int i;
1981  int j;
1982  int nspcons;
1983  int nblocks;
1984 
1985  assert( scip != NULL );
1986  assert( cons != NULL );
1987  assert( result != NULL );
1988 
1989  consdata = SCIPconsGetData(cons);
1990  assert( consdata != NULL );
1991  assert( consdata->nspcons > 0 );
1992  assert( consdata->nblocks > 0 );
1993  assert( consdata->vars != NULL );
1994  assert( consdata->vals != NULL );
1995  assert( consdata->weights != NULL );
1996  assert( consdata->cases != NULL );
1997  assert( consdata->istrianglefixed );
1998 
1999  *result = SCIP_DIDNOTFIND;
2000  if ( ! consdata->resolveprop )
2001  return SCIP_OKAY;
2002 
2003  nspcons = consdata->nspcons;
2004  nblocks = consdata->nblocks;
2005  vars = consdata->vars;
2006  vals = consdata->vals;
2007  weights = consdata->weights;
2008  orbitopetype = consdata->orbitopetype;
2009  cases = consdata->cases;
2010 
2011  SCIPdebugMsg(scip, "Propagation resolution method of orbitope constraint using orbitopal fixing\n");
2012 
2013  /* fill table */
2014  for (i = 0; i < nspcons; ++i)
2015  {
2016  int lastcolumn;
2017 
2018  /* last column considered as part of the bar: */
2019  lastcolumn = nblocks - 1;
2020  if ( lastcolumn > i )
2021  lastcolumn = i;
2022  for (j = 0; j <= lastcolumn; ++j)
2023  {
2024  /* if the variable was fixed to zero at conflict time */
2025  if ( SCIPgetVarUbAtIndex(scip, vars[i][j], bdchgidx, FALSE) < 0.5 )
2026  vals[i][j] = 0.0;
2027  else
2028  {
2029  /* if the variable was fixed to one at conflict time */
2030  if ( SCIPgetVarLbAtIndex(scip, vars[i][j], bdchgidx, FALSE) > 0.5 )
2031  vals[i][j] = 2.0;
2032  else
2033  vals[i][j] = 1.0;
2034  }
2035  }
2036  }
2037 
2038 #ifdef PRINT_MATRIX
2039  SCIPdebugMsg(scip, "Matrix:\n");
2040  printMatrix(scip, consdata);
2041 #endif
2042 
2043  /* computation of table: this now minimizes the value of the shifted column */
2044  assert( consdata->istrianglefixed );
2045  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2046 
2047  /* if we fixed variables in the bar to zero */
2048  assert( inferinfo >= 0 && inferinfo < 2 * nspcons * nblocks );
2049  if ( inferinfo < nspcons * nblocks )
2050  {
2051  int p1;
2052  int p2;
2053 #ifdef SCIP_DEBUG
2054  char str[SCIP_MAXSTRLEN];
2055  char tmpstr[SCIP_MAXSTRLEN];
2056 #endif
2057 
2058  i = (int) (inferinfo / nblocks);
2059  j = inferinfo % nblocks;
2060  assert( 0 <= i && i < nspcons );
2061  assert( 0 <= j && j < nblocks );
2062 
2063  /* find SCI with value 0 */
2064  assert( weights[i-1][j-1] < 0.5 );
2065 
2066  SCIPdebugMsg(scip, " -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i, MIN(i,nblocks));
2067 #ifdef SCIP_DEBUG
2068  str[0] = '\0';
2069 #endif
2070 
2071  p1 = i-1;
2072  p2 = j-1;
2073  do
2074  {
2075  assert( cases[p1][p2] != -1 );
2076  assert( p1 >= 0 && p1 < i );
2077  assert( p2 >= 0 && p2 < j );
2078 
2079  /* if case 1 */
2080  if ( cases[p1][p2] == 1 )
2081  --p2; /* decrease column */
2082  else
2083  {
2084  /* case 2 or 3: */
2085  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2086  assert( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
2087  SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
2088  *result = SCIP_SUCCESS;
2089 
2090 #ifdef SCIP_DEBUG
2091  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
2092  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
2093 #endif
2094 
2095  if ( cases[p1][p2] == 3 )
2096  break;
2097  }
2098  --p1; /* decrease row */
2099  }
2100  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
2101  assert( cases[p1][p2] == 3 );
2102 
2103 #ifdef SCIP_DEBUG
2104  SCIPdebugMsg(scip, "%s\n", str);
2105 #endif
2106  }
2107  else
2108  {
2109  int k;
2110  int p1;
2111  int p2;
2112 #ifndef NDEBUG
2113  int pos1;
2114  int pos2;
2115 #endif
2116 #ifdef SCIP_DEBUG
2117  char str[SCIP_MAXSTRLEN];
2118  char tmpstr[SCIP_MAXSTRLEN];
2119 #endif
2120 
2121  /* if we fixed a variable in the SC to 1 */
2122  inferinfo -= nspcons * nblocks;
2123  i = (int) inferinfo / nblocks;
2124  j = inferinfo % nblocks;
2125  assert( 0 <= i && i < nspcons );
2126  assert( 0 <= j && j < nblocks );
2127 
2128  /* In rare cases it might happen that we fixed a variable to 1, but the node later becomes infeasible by globally
2129  * fixing variables to 0. In this case, it might happen that we find a SC with value 0 instead of 1. We then
2130  * cannot use this SC to repropagate (and do not know how to reconstruct the original reasoning). */
2131  if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 )
2132  {
2133  SCIPdebugMsg(scip, " -> reason for x[%d][%d] = 1 was the following SC:\n", i, j);
2134 #ifdef SCIP_DEBUG
2135  (void) SCIPsnprintf(str, SCIP_MAXSTRLEN, "SC:");
2136 #endif
2137 
2138  p1 = i-1;
2139  p2 = j-1;
2140 #ifndef NDEBUG
2141  pos1 = -1;
2142  pos2 = -1;
2143 #endif
2144  do
2145  {
2146  assert( cases[p1][p2] != -1 );
2147  assert( p1 >= 0 && p1 < i );
2148  assert( p2 >= 0 && p2 < j );
2149 
2150  /* if case 1 */
2151  if ( cases[p1][p2] == 1 )
2152  --p2; /* decrease column */
2153  else
2154  {
2155  /* case 2 or 3: reason are formed by variables in SC fixed to 0 */
2156  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2157  if ( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 )
2158  {
2159  SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
2160  *result = SCIP_SUCCESS;
2161 
2162 #ifdef SCIP_DEBUG
2163  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
2164  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
2165 #endif
2166  }
2167 #ifndef NDEBUG
2168  else
2169  {
2170  assert( SCIPgetVarLbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
2171  assert( pos1 == -1 && pos2 == -1 );
2172  pos1 = p1;
2173  pos2 = p2;
2174  }
2175 #endif
2176  if ( cases[p1][p2] == 3 )
2177  break;
2178  }
2179  --p1; /* decrease row */
2180  }
2181  while ( p1 >= 0 ); /* should always be true, i.e., the break should end the loop */
2182  assert( cases[p1][p2] == 3 );
2183  assert( pos1 >= 0 && pos2 >= 0 );
2184 
2185  /* distinguish partitioning/packing */
2186  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2187  {
2188  /* partitioning case */
2189 #ifdef SCIP_DEBUG
2190  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " before bar: ");
2191  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
2192 #endif
2193  /* add variables before the bar in the partitioning case */
2194  for (k = 0; k < j; ++k)
2195  {
2196  assert( SCIPgetVarUbAtIndex(scip, vars[i][k], bdchgidx, FALSE) < 0.5 );
2197  SCIP_CALL( SCIPaddConflictUb(scip, vars[i][k], bdchgidx) );
2198  *result = SCIP_SUCCESS;
2199 #ifdef SCIP_DEBUG
2200  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", i, k);
2201  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
2202 #endif
2203  }
2204 
2205 #ifdef SCIP_DEBUG
2206  SCIPdebugMsg(scip, "%s\n", str);
2207 #endif
2208  }
2209  else
2210  {
2211  /* packing case */
2212  int lastcolumn;
2213 
2214  /* last column considered as part of the bar: */
2215  lastcolumn = nblocks - 1;
2216  if ( lastcolumn > i )
2217  lastcolumn = i;
2218 
2219  /* search for variable in the bar that is fixed to 1 in the packing case */
2220  for (k = j; k <= lastcolumn; ++k)
2221  {
2222  if ( SCIPgetVarLbAtIndex(scip, vars[i][k], bdchgidx, FALSE) > 0.5 )
2223  {
2224  SCIP_CALL( SCIPaddConflictLb(scip, vars[i][k], bdchgidx) );
2225  *result = SCIP_SUCCESS;
2226  SCIPdebugMsg(scip, " and variable x[%d][%d] fixed to 1.\n", i, k);
2227  break;
2228  }
2229  }
2230  }
2231  }
2232  }
2233 
2234  return SCIP_OKAY;
2235 }
2236 
2237 
2238 /** check packing/partitioning orbitope solution for feasibility */
2239 static
2241  SCIP* scip, /**< SCIP data structure */
2242  SCIP_CONS* cons, /**< pointer to orbitope constraint */
2243  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
2244  )
2245 {
2246  SCIP_CONSDATA* consdata;
2247  SCIP_Real** weights;
2248  SCIP_Real** vals;
2249  int** cases;
2250  int nspcons;
2251  int nblocks;
2252  int i;
2253  int j;
2254 
2255  assert( cons != NULL );
2256 
2257  consdata = SCIPconsGetData(cons);
2258 
2259  assert( scip != NULL );
2260  assert( consdata != NULL );
2261  assert( consdata->nspcons > 0 );
2262  assert( consdata->nblocks > 0 );
2263  assert( consdata->vals != NULL );
2264  assert( consdata->weights != NULL );
2265  assert( consdata->cases != NULL );
2266 
2267  /* check for upper right triangle */
2268  if ( ! consdata->istrianglefixed )
2269  {
2270  SCIP_Bool infeasible = FALSE;
2271  int nfixedvars = 0;
2272 
2273  SCIP_CALL( fixTriangle(scip, cons, &infeasible, &nfixedvars) );
2274  if ( infeasible )
2275  {
2276  *result = SCIP_CUTOFF;
2277  return SCIP_OKAY;
2278  }
2279  if ( nfixedvars > 0 )
2280  {
2281  *result = SCIP_REDUCEDDOM;
2282  return SCIP_OKAY;
2283  }
2284  }
2285 
2286  nspcons = consdata->nspcons;
2287  nblocks = consdata->nblocks;
2288  vals = consdata->vals;
2289  weights = consdata->weights;
2290  cases = consdata->cases;
2291 
2292  /* get solution */
2293  copyValues(scip, consdata, NULL);
2294  SCIPdebugMsg(scip, "Enforcing (pseudo solutions) for orbitope constraint <%s>\n", SCIPconsGetName(cons));
2295 
2296  /* compute table */
2297  assert( consdata->istrianglefixed );
2298  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2299 
2300  /* loop through rows */
2301  for (i = 1; i < nspcons; ++i)
2302  {
2303  SCIP_Real bar = 0.0;
2304  int lastcolumn;
2305 
2306  lastcolumn = nblocks - 1;
2307 
2308  /* last column considered as part of the bar: */
2309  if ( lastcolumn > i )
2310  lastcolumn = i;
2311 
2312  /* traverse row from right to left */
2313  for (j = lastcolumn; j > 0; --j)
2314  {
2315  bar += vals[i][j];
2316  assert( SCIPisIntegral(scip, vals[i][j]) );
2317 
2318  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2319  if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2320  {
2321  SCIPdebugMsg(scip, "Solution is infeasible.\n");
2322  *result = SCIP_INFEASIBLE;
2323  return SCIP_OKAY;
2324  }
2325  }
2326  }
2327 
2328  return SCIP_OKAY;
2329 }
2330 
2331 
2332 /** check packing/partitioning orbitope solution for feasibility */
2333 static
2335  SCIP* scip, /**< SCIP data structure */
2336  SCIP_CONS* cons, /**< pointer to orbitope constraint */
2337  SCIP_SOL* sol, /**< solution to be checked */
2338  SCIP_RESULT* result, /**< pointer to store the result of the enforcing call */
2339  SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
2340  )
2341 {
2342  SCIP_CONSDATA* consdata;
2343  SCIP_VAR*** vars;
2344  SCIP_Real** vals;
2345  SCIP_Real** weights;
2346  int** cases;
2347  int nspcons;
2348  int nblocks;
2349  int i;
2350  int j;
2351 
2352  /* get data of constraint */
2353  assert( cons != 0 );
2354  consdata = SCIPconsGetData(cons);
2355 
2356  assert( consdata != NULL );
2357  assert( consdata->nspcons > 0 );
2358  assert( consdata->nblocks > 0 );
2359  assert( consdata->vars != NULL );
2360  assert( consdata->vals != NULL );
2361  assert( consdata->weights != NULL );
2362  assert( consdata->cases != NULL );
2363 
2364  nspcons = consdata->nspcons;
2365  nblocks = consdata->nblocks;
2366  vars = consdata->vars;
2367  vals = consdata->vals;
2368  weights = consdata->weights;
2369  cases = consdata->cases;
2370 
2371  /* get solution */
2372  copyValues(scip, consdata, sol);
2373  SCIPdebugMsg(scip, "Checking orbitope constraint <%s> ...\n", SCIPconsGetName(cons));
2374 
2375  /* check upper right triangle (if not yet fixed to zero or in debug mode */
2376 #ifdef NDEBUG
2377  if ( ! consdata->istrianglefixed )
2378 #endif
2379  {
2380  int diagsize;
2381 
2382  /* get last row of triangle */
2383  diagsize = nblocks;
2384  if ( nspcons < nblocks )
2385  diagsize = nspcons;
2386 
2387  /* check variables */
2388  for (i = 0; i < diagsize; ++i)
2389  {
2390  for (j = i+1; j < nblocks; ++j)
2391  {
2392  if ( ! SCIPisFeasZero(scip, vals[i][j]) )
2393  {
2394  if ( printreason )
2395  SCIPinfoMessage(scip, NULL, "variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]);
2396  *result = SCIP_INFEASIBLE;
2397  }
2398  }
2399  }
2400  }
2401 
2402  /* compute table */
2403  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2404 
2405  /* loop through rows */
2406  for (i = 1; i < nspcons; ++i)
2407  {
2408  SCIP_Real bar;
2409  int lastcolumn;
2410 
2411  lastcolumn = nblocks - 1;
2412  bar = 0.0;
2413  /* last column considered as part of the bar: */
2414  if ( lastcolumn > i )
2415  lastcolumn = i;
2416 
2417  /* traverse row from right to left */
2418  for (j = lastcolumn; j > 0; --j)
2419  {
2420  bar += vals[i][j];
2421  assert( SCIPisFeasIntegral(scip, vals[i][j]) );
2422 
2423  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2424  if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2425  {
2426  SCIPdebugMsg(scip, "Solution is infeasible.\n");
2427  *result = SCIP_INFEASIBLE;
2428 
2429  if ( printreason )
2430  {
2431  int l;
2432  int p1;
2433  int p2;
2434 
2435  SCIPinfoMessage(scip, NULL, "violated SCI: bar(");
2436 
2437  /* first output bar */
2438  for (l = j; l < nblocks; ++l)
2439  SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[i][l]), consdata->vals[i][l]);
2440 
2441  SCIPinfoMessage(scip, NULL, ") SC(");
2442 
2443  /* output shifted column */
2444  p1 = i-1;
2445  p2 = j-1;
2446  do
2447  {
2448  assert( cases[p1][p2] != -1 );
2449  assert( p1 >= 0 && p1 < i );
2450  assert( p2 >= 0 && p2 < j );
2451 
2452  /* if case 1 */
2453  if (cases[p1][p2] == 1)
2454  --p2; /* decrease column */
2455  else
2456  {
2457  /* case 2 or 3: */
2458  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2459  SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[p1][p2]), consdata->vals[p1][p2]);
2460  if ( cases[p1][p2] == 3 )
2461  break;
2462  }
2463  --p1; /* decrease row */
2464  }
2465  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
2466  assert( cases[p1][p2] == 3 );
2467 
2468  SCIPinfoMessage(scip, NULL, ")");
2469  }
2470  }
2471  }
2472  }
2473 
2474  return SCIP_OKAY;
2475 }
2476 
2477 
2478 /** check full orbitope solution for feasibility */
2479 static
2481  SCIP* scip, /**< SCIP data structure */
2482  SCIP_CONS* cons, /**< constraint to process */
2483  SCIP_SOL* sol, /**< solution to be checked */
2484  SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */
2485  SCIP_Bool* feasible /**< memory address to store whether solution is feasible */
2486  )
2487 {
2488  SCIP_CONSDATA* consdata;
2489  SCIP_VAR*** vars;
2490  SCIP_VAR** vars1;
2491  SCIP_VAR** vars2;
2492  int nrows;
2493  int ncols;
2494  int j;
2495  int i;
2496 
2497  assert( scip != NULL );
2498  assert( cons != NULL );
2499  assert( feasible != NULL );
2500 
2501  consdata = SCIPconsGetData(cons);
2502 
2503  assert( consdata != NULL );
2504  assert( consdata->vars != NULL );
2505  assert( consdata->nspcons > 0 );
2506  assert( consdata->nblocks > 0 );
2507  assert( ! consdata->ismodelcons ); /* non-model constraints are never checked */
2508 
2509  vars = consdata->vars;
2510  nrows = consdata->nspcons;
2511  ncols = consdata->nblocks;
2512 
2513  SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) );
2514  SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) );
2515 
2516  /* iterate over adjacent columns of orbitope and check whether the first column in this
2517  * column pair is lexicographically not smaller than the second column in the pair */
2518  *feasible = TRUE;
2519  for (j = 1; j < ncols && *feasible; ++j)
2520  {
2521  for (i = 0; i < nrows; ++i)
2522  {
2523  vars1[i] = vars[i][j - 1];
2524  vars2[i] = vars[i][j];
2525  }
2526 
2527  SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, vars1, vars2, nrows, printreason, feasible) );
2528  }
2529 
2530  SCIPfreeBufferArray(scip, &vars2);
2531  SCIPfreeBufferArray(scip, &vars1);
2532 
2533  return SCIP_OKAY;
2534 }
2535 
2536 
2537 /** separate orbisack cover inequalities */
2538 static
2540  SCIP* scip, /**< SCIP data structure */
2541  SCIP_CONS* cons, /**< constraint to process */
2542  SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */
2543  SCIP_Bool dynamic, /**< whether we use a dynamic row order */
2544  int* ngen, /**< pointer to store number of generated cuts */
2545  SCIP_Bool* infeasible /**< pointer to store whether infeasibility has been detected */
2546  )
2547 {
2548  SCIP_CONSDATA* consdata;
2549  SCIP_VAR*** vars;
2550  int* roworder;
2551  int nrowsused;
2552  int nrows;
2553  int ncols;
2554  int i;
2555  int j;
2556  int origrow;
2557  SCIP_Real rhs;
2558  SCIP_Real lhs;
2559  SCIP_Real* coeffs1;
2560  SCIP_Real* coeffs2;
2561 
2562  assert( scip != NULL );
2563  assert( cons != NULL );
2564  assert( ngen != NULL );
2565  assert( infeasible != NULL );
2566 
2567  *ngen = 0;
2568  *infeasible = FALSE;
2569 
2570  /* get basic data */
2571  consdata = SCIPconsGetData(cons);
2572  assert( consdata != NULL );
2573 
2574  vars = consdata->vars;
2575  nrows = consdata->nspcons;
2576  ncols = consdata->nblocks;
2577  nrowsused = dynamic ? consdata->nrowsused : nrows;
2578  roworder = consdata->roworder;
2579 
2580  /* allocate memory for cover inequalities */
2581  SCIP_CALL( SCIPallocBufferArray(scip, &coeffs1, nrowsused) );
2582  SCIP_CALL( SCIPallocBufferArray(scip, &coeffs2, nrowsused) );
2583 
2584  lhs = 0.0;
2585  rhs = 0.0;
2586 
2587  /* separate orbisack cover inequalities for adjacent columns */
2588  for (j = 0; j < ncols - 1 && ! *infeasible; ++j)
2589  {
2590  SCIP_Real rowval;
2591 
2592  for (i = 0; i < nrowsused; ++i)
2593  {
2594  origrow = roworder[i];
2595 
2596  assert( origrow >= 0 );
2597  assert( origrow < nrows );
2598 
2599  rowval = SCIPgetSolVal(scip, sol, vars[origrow][j + 1]) - SCIPgetSolVal(scip, sol, vars[origrow][j]);
2600 
2601  /* check whether cover inequality is violated */
2602  if ( SCIPisEfficacious(scip, rowval + lhs - rhs) )
2603  {
2604  SCIP_ROW* row;
2605  int k;
2606 
2607  /* set coefficients for current inequality */
2608  coeffs1[i] = -1.0;
2609  coeffs2[i] = 1.0;
2610 
2611  /* add violated orbisack cover inequality */
2612  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
2613  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
2614 
2615  for (k = 0; k <= i; ++k)
2616  {
2617  int origrow2;
2618 
2619  origrow2 = roworder[k];
2620 
2621  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j], coeffs1[k]) );
2622  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j + 1], coeffs2[k]) );
2623  }
2624  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
2625 
2626  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
2627 #ifdef SCIP_DEBUG
2628  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
2629 #endif
2630  SCIP_CALL( SCIPreleaseRow(scip, &row) );
2631 
2632  *ngen += 1;
2633  if ( *infeasible )
2634  break;
2635 
2636  /* reset coefficients for next inequality */
2637  coeffs1[i] = 0.0;
2638  coeffs2[i] = 0.0;
2639  }
2640 
2641  /* add argmax( 1 - vals[i][0], vals[i][1] ) as coefficient and ensure that both vars1[0] and vars2[0] are
2642  * contained in the LIFTED cover inequality */
2643  rowval = SCIPgetSolVal(scip, sol, vars[origrow][j]) + SCIPgetSolVal(scip, sol, vars[origrow][j + 1]);
2644  if ( SCIPisEfficacious(scip, 1.0 - rowval) )
2645  {
2646  coeffs1[i] = -1.0;
2647  coeffs2[i] = 0.0;
2648  lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]);
2649 
2650  /* apply lifting? */
2651  if ( i == 0 )
2652  {
2653  coeffs2[i] = 1.0;
2654  lhs += SCIPgetSolVal(scip, sol, vars[origrow][j + 1]);
2655  }
2656  }
2657  else
2658  {
2659  coeffs1[i] = 0.0;
2660  coeffs2[i] = 1.0;
2661  lhs += SCIPgetSolVal(scip, sol, vars[origrow][j]);
2662  rhs += 1.0;
2663 
2664  /* apply lifting? */
2665  if ( i == 0 )
2666  {
2667  coeffs1[i] = -1.0;
2668  lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]);
2669  rhs -= 1.0;
2670  }
2671  }
2672  }
2673  }
2674 
2675  SCIPfreeBufferArray(scip, &coeffs1);
2676  SCIPfreeBufferArray(scip, &coeffs2);
2677 
2678  return SCIP_OKAY;
2679 }
2680 
2681 
2682 /** separate or enforce constraints */
2683 static
2685  SCIP* scip, /**< SCIP data structure */
2686  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2687  SCIP_CONS** conss, /**< constraints to process */
2688  int nconss, /**< number of constraints */
2689  int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
2690  SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */
2691  SCIP_RESULT* result, /**< pointer to store the result (should be initialized) */
2692  SCIP_Bool enforce /**< whether we enforce orbitope constraints */
2693  )
2694 {
2695  SCIP_Bool infeasible = FALSE;
2696  int nfixedvars = 0;
2697  int ncuts = 0;
2698  int c;
2699 
2700  assert( scip != NULL );
2701  assert( conshdlr != NULL );
2702  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2703  assert( result != NULL );
2704 
2705  /* loop through constraints */
2706  for (c = 0; c < nconss && ! infeasible; c++)
2707  {
2708  SCIP_CONSHDLRDATA* conshdlrdata;
2709  SCIP_CONSDATA* consdata;
2710  int nconsfixedvars = 0;
2711  int nconscuts = 0;
2712  SCIP_ORBITOPETYPE orbitopetype;
2713 
2714  assert( conss[c] != NULL );
2715 
2716  /* get data of constraint */
2717  consdata = SCIPconsGetData(conss[c]);
2718  assert( consdata != NULL );
2719 
2720  /* do not enforce non-model constraints */
2721  if ( enforce && !consdata->ismodelcons )
2722  continue;
2723 
2724  /* get solution */
2725  copyValues(scip, consdata, sol);
2726 
2727  /* separate */
2728  orbitopetype = consdata->orbitopetype;
2729 
2730  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2731  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2732  {
2733  SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
2734  nfixedvars += nconsfixedvars;
2735  }
2736  else if ( conshdlrdata->sepafullorbitope )
2737  {
2738  SCIP_CALL( separateCoversOrbisack(scip, conss[c], sol, consdata->usedynamicprop && !consdata->ismodelcons, &nconscuts, &infeasible) );
2739  }
2740  ncuts += nconscuts;
2741 
2742  /* stop after the useful constraints if we found cuts of fixed variables */
2743  if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
2744  break;
2745  }
2746 
2747  if ( infeasible )
2748  {
2749  SCIPdebugMsg(scip, "Infeasible node.\n");
2750  *result = SCIP_CUTOFF;
2751  }
2752  else if ( nfixedvars > 0 )
2753  {
2754  SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars);
2755  *result = SCIP_REDUCEDDOM;
2756  }
2757  else if ( ncuts > 0 )
2758  {
2759  SCIPdebugMsg(scip, "Separated %dinequalities.\n", ncuts);
2760  *result = SCIP_SEPARATED;
2761  }
2762  else
2763  {
2764  SCIPdebugMsg(scip, "No violated inequality found during separation.\n");
2765  }
2766 
2767  return SCIP_OKAY;
2768 }
2769 
2770 
2771 /** check whether all variables in an orbitope constraint are fixed */
2772 static
2774  SCIP* scip, /**< SCIP data structure */
2775  SCIP_CONS* cons, /**< constraint to be processed */
2776  SCIP_Bool* redundant /**< pointer to store whether constraint is redundant (contains no active vars) */
2777  )
2778 {
2779  SCIP_CONSDATA* consdata;
2780  SCIP_VAR*** vars;
2781  int i;
2782  int j;
2783  int nrows;
2784  int ncols;
2785 
2786  assert( scip != NULL );
2787  assert( cons != NULL );
2788  assert( redundant != NULL );
2789 
2790  *redundant = FALSE;
2791 
2792  consdata = SCIPconsGetData(cons);
2793  assert( consdata != NULL );
2794  assert( consdata->vars != NULL );
2795  assert( consdata->nspcons > 0 );
2796  assert( consdata->nblocks > 0 );
2797 
2798  vars = consdata->vars;
2799  nrows = consdata->nspcons;
2800  ncols = consdata->nblocks;
2801 
2802  /* check whether there exists an active variable in the orbitope */
2803  for (i = 0; i < nrows; ++i)
2804  {
2805  for (j = 0; j < ncols; ++j)
2806  {
2807  if ( SCIPvarIsActive(vars[i][j]) )
2808  return SCIP_OKAY;
2809  }
2810  }
2811 
2812  *redundant = TRUE;
2813 
2814  return SCIP_OKAY;
2815 }
2816 
2817 
2818 /*
2819  * Callback methods of constraint handler
2820  */
2821 
2822 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2823 static
2824 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
2825 { /*lint --e{715}*/
2826  assert(scip != NULL);
2827  assert(conshdlr != NULL);
2828  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2829 
2830  /* call inclusion method of constraint handler */
2832 
2833  *valid = TRUE;
2834 
2835  return SCIP_OKAY;
2836 }
2837 
2838 /** frees constraint handler */
2839 static
2840 SCIP_DECL_CONSFREE(consFreeOrbitope)
2841 { /*lint --e{715}*/
2842  SCIP_CONSHDLRDATA* conshdlrdata;
2843 
2844  assert( scip != 0 );
2845  assert( conshdlr != 0 );
2846  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2847 
2848  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2849  assert( conshdlrdata != NULL );
2850 
2851  SCIPfreeBlockMemory(scip, &conshdlrdata);
2852 
2853  return SCIP_OKAY;
2854 }
2855 
2856 /** frees specific constraint data */
2857 static
2858 SCIP_DECL_CONSDELETE(consDeleteOrbitope)
2859 { /*lint --e{715}*/
2860  assert(conshdlr != NULL);
2861  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2862 
2863  SCIP_CALL( consdataFree(scip, consdata) );
2864 
2865  return SCIP_OKAY;
2866 }
2867 
2868 /** transforms constraint data into data belonging to the transformed problem */
2869 static
2870 SCIP_DECL_CONSTRANS(consTransOrbitope)
2871 { /*lint --e{715}*/
2872  SCIP_CONSDATA* sourcedata;
2873  SCIP_CONSDATA* targetdata;
2874 
2875  assert(conshdlr != NULL);
2876  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2877  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
2878  assert(sourcecons != NULL);
2879  assert(targetcons != NULL);
2880 
2881  sourcedata = SCIPconsGetData(sourcecons);
2882  assert(sourcedata != NULL);
2883 
2884  /* create linear constraint data for target constraint */
2885  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nspcons, sourcedata->nblocks,
2886  sourcedata->orbitopetype, sourcedata->resolveprop, sourcedata->usedynamicprop, sourcedata->ismodelcons,
2887  sourcedata->mayinteract) );
2888 
2889  /* create target constraint */
2890  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2891  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2892  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2893  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2894  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2895 
2896  return SCIP_OKAY;
2897 }
2898 
2899 /** separation method of constraint handler for LP solutions */
2900 static
2901 SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
2902 { /*lint --e{715}*/
2903  assert( scip != NULL );
2904  assert( result != NULL );
2905 
2906  SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2907 
2908  *result = SCIP_DIDNOTRUN;
2909 
2910  /* if solution is integer, skip separation */
2911  if ( SCIPgetNLPBranchCands(scip) <= 0 )
2912  return SCIP_OKAY;
2913 
2914  *result = SCIP_DIDNOTFIND;
2915 
2916  /* separate constraints */
2917  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, FALSE) );
2918 
2919  return SCIP_OKAY;
2920 }
2921 
2922 /** separation method of constraint handler for arbitrary primal solutions */
2923 static
2924 SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
2925 { /*lint --e{715}*/
2926  assert( scip != NULL );
2927  assert( result != NULL );
2928 
2929  SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for primal solution.\n", SCIPconshdlrGetName(conshdlr));
2930 
2931  *result = SCIP_DIDNOTFIND;
2932 
2933  /* separate constraints */
2934  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, FALSE) );
2935 
2936  return SCIP_OKAY;
2937 }
2938 
2939 
2940 /** constraint enforcing method of constraint handler for LP solutions */
2941 static
2942 SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
2943 { /*lint --e{715}*/
2944  assert( scip != NULL );
2945  assert( result != NULL );
2946 
2947  /* we have a negative priority, so we should come after the integrality conshdlr */
2948  assert( SCIPgetNLPBranchCands(scip) == 0 );
2949 
2950  SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2951 
2952  *result = SCIP_FEASIBLE;
2953 
2954  /* separate constraints */
2955  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, TRUE) );
2956 
2957  return SCIP_OKAY;
2958 }
2959 
2960 
2961 /** constraint enforcing method of constraint handler for relaxation solutions */
2962 static
2963 SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
2964 { /*lint --e{715}*/
2965  assert( result != NULL );
2966  assert( scip != NULL );
2967 
2968  SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for relaxation solution.\n", SCIPconshdlrGetName(conshdlr));
2969 
2970  *result = SCIP_FEASIBLE;
2971 
2972  /* separate constraints */
2973  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, TRUE) );
2974 
2975  return SCIP_OKAY;
2976 }
2977 
2978 
2979 /** constraint enforcing method of constraint handler for pseudo solutions */
2980 static
2981 SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
2982 { /*lint --e{715}*/
2983  int c;
2984 
2985  assert( scip != NULL );
2986  assert( conshdlr != NULL );
2987  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2988  assert( result != NULL );
2989 
2990  *result = SCIP_FEASIBLE;
2991  if ( objinfeasible || solinfeasible )
2992  return SCIP_OKAY;
2993 
2994  /* loop through constraints */
2995  for (c = 0; c < nconss; ++c)
2996  {
2997  SCIP_CONS* cons;
2998  SCIP_CONSDATA* consdata;
2999  SCIP_ORBITOPETYPE orbitopetype;
3000  SCIP_Bool feasible;
3001 
3002  /* get data of constraint */
3003  cons = conss[c];
3004  assert( cons != 0 );
3005  consdata = SCIPconsGetData(cons);
3006 
3007  assert( consdata != NULL );
3008 
3009  /* do not enforce non-model constraints */
3010  if ( !consdata->ismodelcons )
3011  continue;
3012 
3013  orbitopetype = consdata->orbitopetype;
3014 
3015  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3016  {
3018  }
3019  else
3020  {
3021  SCIP_CALL( checkFullOrbitopeSolution(scip, cons, NULL, FALSE, &feasible) );
3022 
3023  if ( ! feasible )
3024  *result = SCIP_INFEASIBLE;
3025  }
3026 
3027  if ( *result == SCIP_INFEASIBLE )
3028  break;
3029  }
3030 
3031  return SCIP_OKAY;
3032 }
3033 
3034 
3035 /** feasibility check method of constraint handler for integral solutions */
3036 static
3037 SCIP_DECL_CONSCHECK(consCheckOrbitope)
3038 { /*lint --e{715}*/
3039  int c;
3040  SCIP_CONSDATA* consdata;
3041  SCIP_ORBITOPETYPE orbitopetype;
3042  SCIP_Bool feasible;
3043 
3044  assert( scip != NULL );
3045  assert( conshdlr != NULL );
3046  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3047  assert( result != NULL );
3048 
3049  *result = SCIP_FEASIBLE;
3050 
3051  /* loop through constraints */
3052  for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
3053  {
3054  assert( conss[c] != 0 );
3055  consdata = SCIPconsGetData(conss[c]);
3056 
3057  assert( consdata != NULL );
3058 
3059  /* do not check non-model constraints */
3060  if ( !consdata->ismodelcons )
3061  continue;
3062 
3063  orbitopetype = consdata->orbitopetype;
3064 
3065  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3066  {
3067  SCIP_CALL( checkPackingPartitioningOrbitopeSolution(scip, conss[c], sol, result, printreason) );
3068  }
3069  else
3070  {
3071  SCIP_CALL( checkFullOrbitopeSolution(scip, conss[c], sol, printreason, &feasible) );
3072 
3073  if ( ! feasible )
3074  *result = SCIP_INFEASIBLE;
3075  }
3076  }
3077  SCIPdebugMsg(scip, "Solution is feasible.\n");
3078 
3079  return SCIP_OKAY;
3080 }
3081 
3082 
3083 /** domain propagation method of constraint handler */
3084 static
3085 SCIP_DECL_CONSPROP(consPropOrbitope)
3086 { /*lint --e{715}*/
3087  SCIP_Bool infeasible = FALSE;
3088  int nfixedvars = 0;
3089  int c;
3090 
3091  assert( scip != NULL );
3092  assert( conshdlr != NULL );
3093  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3094  assert( result != NULL );
3095 
3096  *result = SCIP_DIDNOTRUN;
3097 
3098  /* propagate all useful constraints */
3099  for (c = 0; c < nusefulconss && !infeasible; ++c)
3100  {
3101  assert( conss[c] != 0 );
3102 
3103  SCIPdebugMsg(scip, "Propagation of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
3104 
3105  SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixedvars) );
3106  }
3107 
3108  /* return the correct result */
3109  if ( infeasible )
3110  {
3111  *result = SCIP_CUTOFF;
3112  SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n");
3113  }
3114  else if ( nfixedvars > 0 )
3115  {
3116  *result = SCIP_REDUCEDDOM;
3117  SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars);
3118  }
3119  else if ( nusefulconss > 0 )
3120  {
3121  *result = SCIP_DIDNOTFIND;
3122  SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n");
3123  }
3124 
3125  return SCIP_OKAY;
3126 }
3127 
3128 
3129 /** presolving method of constraint handler */
3130 static
3131 SCIP_DECL_CONSPRESOL(consPresolOrbitope)
3132 { /*lint --e{715}*/
3133  SCIP_Bool infeasible = FALSE;
3134  int noldfixedvars;
3135  int c;
3136  SCIP_Bool redundant;
3137 
3138  assert( scip != NULL );
3139  assert( conshdlr != NULL );
3140  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3141  assert( result != NULL );
3142 
3143  *result = SCIP_DIDNOTRUN;
3144  noldfixedvars = *nfixedvars;
3145 
3146  /* propagate all useful constraints
3147  *
3148  * @todo use an event handler to only propagate if a variable in the orbitope has been fixed
3149  */
3150  for (c = 0; c < nconss && !infeasible; ++c)
3151  {
3152  int nfixed = 0;
3153 
3154  assert( conss[c] != 0 );
3155 
3156  SCIPdebugMsg(scip, "Presolving of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
3157 
3158  /* first propagate */
3159  SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
3160  *nfixedvars += nfixed;
3161 
3162  if ( ! infeasible )
3163  {
3164  SCIP_CALL( checkRedundantCons(scip, conss[c], &redundant) );
3165 
3166  if ( redundant )
3167  {
3168  SCIPdebugMsg(scip, "Orbitope constraint <%s> is redundant: it does not contain active variables\n",
3169  SCIPconsGetName(conss[c]));
3170  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
3171  assert( ! SCIPconsIsActive(conss[c]) );
3172  (*ndelconss)++;
3173  continue;
3174  }
3175  }
3176  }
3177 
3178  if ( infeasible )
3179  {
3180  *result = SCIP_CUTOFF;
3181  SCIPdebugMsg(scip, "Presolving detected infeasibility.\n");
3182  }
3183  else if ( *nfixedvars > noldfixedvars )
3184  {
3185  *result = SCIP_SUCCESS;
3186  }
3187  else if ( nconss > 0 )
3188  {
3189  *result = SCIP_DIDNOTFIND;
3190  SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n");
3191  }
3192 
3193  return SCIP_OKAY;
3194 }
3195 
3196 
3197 /** propagation conflict resolving method of constraint handler */
3198 static
3199 SCIP_DECL_CONSRESPROP(consRespropOrbitope)
3200 { /*lint --e{715}*/
3201  SCIP_CONSDATA* consdata;
3202  SCIP_ORBITOPETYPE orbitopetype;
3203 
3204  assert( scip != NULL );
3205  assert( cons != NULL );
3206  assert( infervar != NULL );
3207  assert( bdchgidx != NULL );
3208  assert( result != NULL );
3209 
3210  consdata = SCIPconsGetData(cons);
3211  assert( consdata != NULL );
3212 
3213  orbitopetype = consdata->orbitopetype;
3214 
3215  /* resolution for full orbitopes not availabe yet */
3216  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3217  {
3218  SCIP_CALL( resolvePropagation(scip, cons, inferinfo, bdchgidx, result) );
3219  }
3220  else
3221  {
3222  SCIP_CALL( resolvePropagationFullOrbitope(scip, conshdlr, cons, inferinfo, bdchgidx, result) );
3223  }
3224 
3225  return SCIP_OKAY;
3226 }
3227 
3228 
3229 /** variable rounding lock method of constraint handler */
3230 static
3231 SCIP_DECL_CONSLOCK(consLockOrbitope)
3232 { /*lint --e{715}*/
3233  SCIP_CONSDATA* consdata;
3234  SCIP_VAR*** vars;
3235  int i;
3236  int j;
3237  int nspcons;
3238  int nblocks;
3239 
3240  assert( scip != NULL );
3241  assert( conshdlr != NULL );
3242  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3243  assert( cons != NULL );
3244  assert( locktype == SCIP_LOCKTYPE_MODEL );
3245 
3246  consdata = SCIPconsGetData(cons);
3247  assert( consdata != NULL );
3248  assert( consdata->nspcons > 0 );
3249  assert( consdata->nblocks > 0 );
3250  assert( consdata->vars != NULL );
3251 
3252  SCIPdebugMsg(scip, "Locking method for orbitope constraint handler\n");
3253 
3254  nspcons = consdata->nspcons;
3255  nblocks = consdata->nblocks;
3256  vars = consdata->vars;
3257 
3258  /* add up locks and down locks on each variable */
3259  for (i = 0; i < nspcons; ++i)
3260  {
3261  for (j = 0; j < nblocks; ++j)
3262  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3263  }
3264 
3265  return SCIP_OKAY;
3266 }
3267 
3268 
3269 /** constraint display method of constraint handler */
3270 static
3271 SCIP_DECL_CONSPRINT(consPrintOrbitope)
3273  SCIP_CONSDATA* consdata;
3274  SCIP_VAR*** vars;
3275  int i;
3276  int j;
3277  int nspcons;
3278  int nblocks;
3279  SCIP_ORBITOPETYPE orbitopetype;
3280 
3281  assert( scip != NULL );
3282  assert( conshdlr != NULL );
3283  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3284  assert( cons != NULL );
3285 
3286  consdata = SCIPconsGetData(cons);
3287  assert( consdata != NULL );
3288  assert( consdata->nspcons > 0 );
3289  assert( consdata->nblocks > 0 );
3290  assert( consdata->vars != NULL );
3291 
3292  nspcons = consdata->nspcons;
3293  nblocks = consdata->nblocks;
3294  vars = consdata->vars;
3295  orbitopetype = consdata->orbitopetype;
3296 
3297  SCIPdebugMsg(scip, "Printing method for orbitope constraint handler\n");
3298 
3299  switch ( orbitopetype )
3300  {
3302  SCIPinfoMessage(scip, file, "partOrbitope(");
3303  break;
3305  SCIPinfoMessage(scip, file, "packOrbitope(");
3306  break;
3308  SCIPinfoMessage(scip, file, "fullOrbitope(");
3309  break;
3310  default:
3311  SCIPABORT();
3312  }
3313 
3314  for (i = 0; i < nspcons; ++i)
3315  {
3316  for (j = 0; j < nblocks; ++j)
3317  {
3318  if ( j > 0 )
3319  SCIPinfoMessage(scip, file, ",");
3320  SCIP_CALL( SCIPwriteVarName(scip, file, vars[i][j], TRUE) );
3321  }
3322  if ( i < nspcons-1 )
3323  SCIPinfoMessage(scip, file, ".");
3324  }
3325  SCIPinfoMessage(scip, file, ")");
3326 
3327  return SCIP_OKAY;
3328 }
3329 
3330 
3331 /** constraint copying method of constraint handler */
3332 static
3333 SCIP_DECL_CONSCOPY(consCopyOrbitope)
3335  SCIP_CONSHDLRDATA* conshdlrdata;
3336  SCIP_CONSDATA* sourcedata;
3337  SCIP_VAR*** sourcevars;
3338  SCIP_VAR*** vars;
3339  int nspcons;
3340  int nblocks;
3341  int i;
3342  int k;
3343  int j;
3344 
3345  assert( scip != NULL );
3346  assert( cons != NULL );
3347  assert( sourcescip != NULL );
3348  assert( sourceconshdlr != NULL );
3349  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
3350  assert( sourcecons != NULL );
3351  assert( varmap != NULL );
3352  assert( valid != NULL );
3353 
3354  *valid = TRUE;
3355 
3356  SCIPdebugMsg(scip, "Copying method for orbitope constraint handler.\n");
3357 
3358  sourcedata = SCIPconsGetData(sourcecons);
3359  assert( sourcedata != NULL );
3360  assert( sourcedata->nspcons > 0 );
3361  assert( sourcedata->nblocks > 0 );
3362  assert( sourcedata->vars != NULL );
3363 
3364  conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
3365  assert( conshdlrdata != NULL );
3366 
3367  /* do not copy non-model constraints */
3368  if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
3369  {
3370  *valid = FALSE;
3371 
3372  return SCIP_OKAY;
3373  }
3374 
3375  nspcons = sourcedata->nspcons;
3376  nblocks = sourcedata->nblocks;
3377  sourcevars = sourcedata->vars;
3378 
3379  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nspcons) );
3380  for (i = 0; i < nspcons && *valid; ++i)
3381  {
3382  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), nblocks) ); /*lint !e866*/
3383 
3384  for (j = 0; j < nblocks && *valid; ++j)
3385  {
3386  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
3387  assert( !(*valid) || vars[i][j] != NULL );
3388  }
3389  }
3390 
3391  /* only create the target constraint, if all variables could be copied */
3392  if ( *valid )
3393  {
3394  /* create copied constraint */
3395  if ( name == NULL )
3396  name = SCIPconsGetName(sourcecons);
3397 
3398  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name,
3399  vars, sourcedata->orbitopetype, nspcons, nblocks, sourcedata->usedynamicprop,
3400  sourcedata->resolveprop, sourcedata->ismodelcons, sourcedata->mayinteract,
3401  initial, separate, enforce, check, propagate,
3402  local, modifiable, dynamic, removable, stickingatnode) );
3403  }
3404 
3405  /* free space; only up to row i if copying failed */
3406  assert( 0 <= i && i <= nspcons );
3407  for (k = i - 1; k >= 0; --k)
3408  SCIPfreeBufferArray(scip, &vars[k]);
3409  SCIPfreeBufferArray(scip, &vars);
3410 
3411  return SCIP_OKAY;
3412 }
3413 
3414 
3415 /** constraint parsing method of constraint handler */
3416 static
3417 SCIP_DECL_CONSPARSE(consParseOrbitope)
3418 { /*lint --e{715}*/
3419  const char* s;
3420  char* endptr;
3421  SCIP_ORBITOPETYPE orbitopetype;
3422  SCIP_VAR*** vars;
3423  SCIP_VAR* var;
3424  int nspcons;
3425  int maxnspcons;
3426  int nblocks;
3427  int maxnblocks;
3428  int k;
3429  int j;
3430 
3431  assert( success != NULL );
3432 
3433  *success = TRUE;
3434  s = str;
3435 
3436  /* skip white space */
3437  while ( *s != '\0' && isspace((unsigned char)*s) )
3438  ++s;
3439 
3440  if ( strncmp(s, "partOrbitope(", 13) == 0 )
3441  orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
3442  else if ( strncmp(s, "packOrbitope(", 13) == 0 )
3443  orbitopetype = SCIP_ORBITOPETYPE_PACKING;
3444  else
3445  {
3446  if ( strncmp(s, "fullOrbitope(", 13) != 0 )
3447  {
3448  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error - expected \"fullOrbitope(\", \"partOrbitope\" or \"packOrbitope\": %s\n", s);
3449  *success = FALSE;
3450  return SCIP_OKAY;
3451  }
3452  orbitopetype = SCIP_ORBITOPETYPE_FULL;
3453  }
3454  s += 13;
3455 
3456  /* loop through string */
3457  nspcons = 0;
3458  nblocks = 0;
3459  maxnspcons = 10;
3460  maxnblocks = 10;
3461 
3462  SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnspcons) );
3463  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[0]), maxnblocks) );
3464 
3465  j = 0;
3466  do
3467  {
3468  /* skip whitespace */
3469  while ( isspace((int)*s) )
3470  ++s;
3471 
3472  /* parse variable name */
3473  SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
3474  if ( var == NULL )
3475  {
3476  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "unknown variable name at '%s'\n", str);
3477  *success = FALSE;
3478  return SCIP_OKAY;
3479  }
3480  vars[nspcons][j++] = var;
3481  s = endptr;
3482 
3483  if ( j > nblocks )
3484  {
3485  if ( nspcons > 0 )
3486  {
3487  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variables per row do not match.\n");
3488  *success = FALSE;
3489  return SCIP_OKAY;
3490  }
3491  nblocks = j;
3492 
3493  if ( nblocks > maxnblocks )
3494  {
3495  int newsize;
3496 
3497  newsize = SCIPcalcMemGrowSize(scip, nblocks);
3498  SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons]), newsize) ); /*lint !e866*/
3499  maxnblocks = newsize;
3500  }
3501  }
3502  assert( nblocks <= maxnblocks );
3503 
3504  /* skip white space and ',' */
3505  while ( *s != '\0' && ( isspace((unsigned char)*s) || *s == ',' ) )
3506  ++s;
3507 
3508  /* begin new row if required */
3509  if ( *s == '.' )
3510  {
3511  ++nspcons;
3512  ++s;
3513 
3514  if ( nspcons >= maxnspcons )
3515  {
3516  int newsize;
3517 
3518  newsize = SCIPcalcMemGrowSize(scip, nspcons+1);
3519  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, newsize) );
3520  maxnspcons = newsize;
3521  }
3522  assert(nspcons < maxnspcons);
3523 
3524  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nspcons]), nblocks) ); /*lint !e866*/
3525  j = 0;
3526  }
3527  }
3528  while ( *s != ')' );
3529  ++nspcons;
3530 
3531  /* to ensure consistency, we disable dynamic propagation and tell SCIP that the orbitope could potentially
3532  * interact with other symmetry handling constraints
3533  */
3534  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, FALSE, TRUE, TRUE, TRUE,
3535  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3536 
3537  for (k = nspcons - 1; k >= 0; --k)
3538  SCIPfreeBufferArray(scip, &vars[k]);
3539  SCIPfreeBufferArray(scip, &vars);
3540 
3541  return SCIP_OKAY;
3542 }
3543 
3544 
3545 /** constraint method of constraint handler which returns the variables (if possible) */
3546 static
3547 SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
3548 { /*lint --e{715}*/
3549  SCIP_CONSDATA* consdata;
3550 
3551  assert( cons != NULL );
3552  assert( success != NULL );
3553  assert( vars != NULL );
3554 
3555  consdata = SCIPconsGetData(cons);
3556  assert( consdata != NULL );
3557 
3558  if ( varssize < consdata->nblocks * consdata->nspcons )
3559  (*success) = FALSE;
3560  else
3561  {
3562  int cnt = 0;
3563  int i;
3564  int j;
3565 
3566  for (i = 0; i < consdata->nspcons; ++i)
3567  {
3568  for (j = 0; j < consdata->nblocks; ++j)
3569  vars[cnt++] = consdata->vars[i][j];
3570  }
3571  (*success) = TRUE;
3572  }
3573 
3574  return SCIP_OKAY;
3575 }
3576 
3577 
3578 /** constraint method of constraint handler which returns the number of variables (if possible) */
3579 static
3580 SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
3581 { /*lint --e{715}*/
3582  SCIP_CONSDATA* consdata;
3583 
3584  assert( cons != NULL );
3585 
3586  consdata = SCIPconsGetData(cons);
3587  assert( consdata != NULL );
3588 
3589  (*nvars) = consdata->nblocks * consdata->nspcons;
3590  (*success) = TRUE;
3591 
3592  return SCIP_OKAY;
3593 }
3594 
3595 
3596 /*
3597  * constraint specific interface methods
3598  */
3599 
3600 /** creates the handler for orbitope constraints and includes it in SCIP */
3602  SCIP* scip /**< SCIP data structure */
3603  )
3604 {
3605  SCIP_CONSHDLRDATA* conshdlrdata;
3606  SCIP_CONSHDLR* conshdlr;
3607 
3608  /* create orbitope constraint handler data */
3609  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3610 
3611  /* include constraint handler */
3615  consEnfolpOrbitope, consEnfopsOrbitope, consCheckOrbitope, consLockOrbitope,
3616  conshdlrdata) );
3617  assert(conshdlr != NULL);
3618 
3619  /* set non-fundamental callbacks via specific setter functions */
3620  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitope, consCopyOrbitope) );
3621  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbitope) );
3622  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitope) );
3623  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitope) );
3624  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitope) );
3625  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitope) );
3626  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbitope, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3627  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitope) );
3628  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbitope, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3630  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitope) );
3631  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitope, consSepasolOrbitope, CONSHDLR_SEPAFREQ,
3633  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitope) );
3634  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitope) );
3635 
3636  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbitope",
3637  "Strengthen orbitope constraints to packing/partioning orbitopes?",
3638  &conshdlrdata->checkpporbitope, TRUE, DEFAULT_PPORBITOPE, NULL, NULL) );
3639 
3640  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/sepafullorbitope",
3641  "Whether we separate inequalities for full orbitopes?",
3642  &conshdlrdata->sepafullorbitope, TRUE, DEFAULT_SEPAFULLORBITOPE, NULL, NULL) );
3643 
3644  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
3645  "Whether orbitope constraints should be forced to be copied to sub SCIPs.",
3646  &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
3647 
3648  return SCIP_OKAY;
3649 }
3650 
3651 
3652 /** creates and captures a orbitope constraint
3653  *
3654  * @pre If packing/partitioning orbitopes are used, this constraint handler assumes that constraints which enforce
3655  * the packing/partitioning constraints are contained in the problem. It does not implement, e.g., separation and
3656  * propagation of set packing/partitioning constraints, since this would just copy large parts of the code of the
3657  * setppc constraint handler.
3658  *
3659  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3660  */
3662  SCIP* scip, /**< SCIP data structure */
3663  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3664  const char* name, /**< name of constraint */
3665  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
3666  SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
3667  int nspcons, /**< number of set partitioning/packing constraints <=> p */
3668  int nblocks, /**< number of symmetric variable blocks <=> q */
3669  SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */
3670  SCIP_Bool mayinteract, /**< whether symmetries corresponding to orbitope might interact
3671  * with symmetries handled by other routines */
3672  SCIP_Bool resolveprop, /**< should propagation be resolved? */
3673  SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
3674  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3675  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3676  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3677  * Usually set to TRUE. */
3678  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3679  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3680  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3681  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3682  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3683  * Usually set to TRUE. */
3684  SCIP_Bool local, /**< is constraint only valid locally?
3685  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3686  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3687  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3688  * adds coefficients to this constraint. */
3689  SCIP_Bool dynamic, /**< is constraint subject to aging?
3690  * Usually set to FALSE. Set to TRUE for own cuts which
3691  * are separated as constraints. */
3692  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3693  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3694  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3695  * if it may be moved to a more global node?
3696  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3697  )
3698 {
3699  SCIP_CONSHDLRDATA* conshdlrdata;
3700  SCIP_CONSHDLR* conshdlr;
3701  SCIP_CONSDATA* consdata;
3702 
3703  /* find the orbitope constraint handler */
3704  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3705  if ( conshdlr == NULL )
3706  {
3707  SCIPerrorMessage("orbitope constraint handler not found\n");
3708  return SCIP_PLUGINNOTFOUND;
3709  }
3710 
3711  /* check for consistency */
3712  if ( usedynamicprop && mayinteract )
3713  {
3714  SCIPwarningMessage(scip, "Dynamic propagation is only possible if orbitope does not interact with \
3715  other symmetry handling constraints. Ignore value of <usedynamicprop>.\n");
3716  }
3717 
3718  assert( nspcons > 0 );
3719  assert( nblocks > 0 );
3720 
3721  /* run some checks */
3722 #ifndef NDEBUG
3723  {
3724  SCIP_Real obj;
3725  int i;
3726  int j;
3727  for (i = 0; i < nspcons; ++i)
3728  {
3729  /* initialize obj to infinity */
3730  obj = SCIPinfinity(scip);
3731  for (j = 0; j < nblocks; ++j)
3732  {
3733  SCIP_Bool fixedZero;
3734  SCIP_VAR* var;
3735 
3736  var = vars[i][j];
3737  assert(var != NULL);
3738 
3739  if ( SCIPvarIsNegated(var) )
3740  var = SCIPvarGetNegatedVar(var);
3741 
3742  /* all variables need to be binary */
3743  assert( SCIPvarIsBinary(var) );
3744 
3745  /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no
3746  problem (but we cannot always check it, e.g., when in the original problem
3747  variables were fixed and this problem was copied.) */
3748  fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) );
3749 
3750  /* @todo adapt correctness of the following check for sub-scips */
3751  if ( SCIPgetSubscipDepth(scip) == 0 )
3752  {
3753  /* check whether all variables in a row have the same objective */
3754  if ( ! fixedZero && SCIPisInfinity(scip, obj) )
3755  obj = SCIPvarGetObj(var);
3756  else
3757  {
3758  assert( fixedZero || ! SCIPvarIsActive(var) || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) );
3759  }
3760  }
3761  }
3762  }
3763  }
3764 #endif
3765 
3766  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3767  if ( conshdlrdata->checkpporbitope && orbitopetype != SCIP_ORBITOPETYPE_PARTITIONING
3768  && orbitopetype != SCIP_ORBITOPETYPE_PACKING )
3769  {
3770  SCIP_CALL( strengthenOrbitopeConstraint(scip, vars, &nspcons, nblocks, &orbitopetype, mayinteract) );
3771  }
3772 
3773  /* create constraint data */
3774  SCIP_CALL( consdataCreate(scip, &consdata, vars, nspcons, nblocks, orbitopetype,
3775  resolveprop, usedynamicprop && ! mayinteract, ismodelcons, mayinteract) );
3776 
3777  /* create constraint */
3778  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3779  local, modifiable, dynamic, removable, stickingatnode) );
3780 
3781  return SCIP_OKAY;
3782 }
3783 
3784 /** creates and captures an orbitope constraint
3785  * in its most basic variant, i. e., with all constraint flags set to their default values
3786  *
3787  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3788  */
3790  SCIP* scip, /**< SCIP data structure */
3791  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3792  const char* name, /**< name of constraint */
3793  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
3794  SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
3795  int nspcons, /**< number of set partitioning/packing constraints <=> p */
3796  int nblocks, /**< number of symmetric variable blocks <=> q */
3797  SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */
3798  SCIP_Bool resolveprop, /**< should propagation be resolved? */
3799  SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
3800  SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact
3801  * with symmetries handled by other routines */
3802  )
3803 {
3804  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, usedynamicprop,
3805  resolveprop, ismodelcons, mayinteract, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3806 
3807  return SCIP_OKAY;
3808 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1413
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
static SCIP_DECL_CONSPARSE(consParseOrbitope)
static SCIP_RETCODE strengthenOrbitopeConstraint(SCIP *scip, SCIP_VAR ***vars, int *nrows, int ncols, SCIP_ORBITOPETYPE *type, SCIP_Bool mayinteract)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2125
public methods for SCIP parameter handling
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
static SCIP_RETCODE computeDynamicRowOrder(SCIP *scip, SCIP_HASHMAP *rowindexmap, SCIP_Bool *rowused, int *roworder, int nrows, int ncols, int *maxrowlabel)
static SCIP_RETCODE fixTriangle(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
#define CONSHDLR_SEPAFREQ
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE checkPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
SCIP_RETCODE SCIPcreateConsBasicOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool usedynamicprop, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool mayinteract)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1989
public methods for memory management
static SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:816
#define SCIP_MAXSTRLEN
Definition: def.h:293
static void copyValues(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol)
public methods for conflict handler plugins and conflict analysis
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2841
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7712
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1436
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:524
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
static SCIP_RETCODE findLexMinFace(SCIP_VAR ***vars, int **lexminfixes, int *minfixedrowlexmin, SCIP_Bool *infeasible, int m, int n, int nrowsused, SCIP_Bool resprop)
#define CONSHDLR_SEPAPRIORITY
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
static SCIP_DECL_CONSPRESOL(consPresolOrbitope)
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2591
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
constraint handler for orbisack constraints
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
static SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8364
#define CONSHDLR_DESC
public methods for problem variables
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:220
#define CONSHDLR_NAME
static SCIP_DECL_CONSFREE(consFreeOrbitope)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7442
#define CONSHDLR_PROPFREQ
#define CONSHDLR_PROP_TIMING
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:566
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
public methods for SCIP variables
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
static SCIP_DECL_CONSPRINT(consPrintOrbitope)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:793
SCIP_RETCODE SCIPincludeConshdlrOrbitope(SCIP *scip)
#define CONSHDLR_ENFOPRIORITY
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8146
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
static SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:934
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
static void computeSCTable(SCIP *scip, int nspcons, int nblocks, SCIP_Real **weights, int **cases, SCIP_Real **vals)
public methods for numerical tolerances
#define CONSHDLR_CHECKPRIORITY
static SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17726
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
public methods for managing constraints
#define DEFAULT_PPORBITOPE
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
static SCIP_RETCODE separateConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool enforce)
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_NEEDSCONS
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:126
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16661
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition: symmetry.c:1152
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8712
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
static SCIP_RETCODE resolvePropagationFullOrbitope(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int inferinfo, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
static SCIP_RETCODE checkRedundantCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *redundant)
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7527
#define NULL
Definition: lpi_spx1.cpp:155
static SCIP_RETCODE separateSCIs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *infeasible, int *nfixedvars, int *ncuts)
static SCIP_RETCODE propagateFullOrbitopeCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars, SCIP_Bool dynamic)
static SCIP_DECL_CONSCOPY(consCopyOrbitope)
#define REALABS(x)
Definition: def.h:201
public methods for problem copies
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_DECL_CONSPROP(consPropOrbitope)
static SCIP_RETCODE separateCoversOrbisack(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool dynamic, int *ngen, SCIP_Bool *infeasible)
static SCIP_RETCODE findLexMaxFace(SCIP_VAR ***vars, int **lexmaxfixes, int *minfixedrowlexmax, SCIP_Bool *infeasible, int m, int n, int nrowsused, SCIP_Bool resprop)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8324
static SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:632
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
static SCIP_RETCODE propagatePackingPartitioningCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
public methods for constraint handler plugins and constraints
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17168
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16542
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, int inferinfo, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
static SCIP_DECL_CONSDELETE(consDeleteOrbitope)
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17158
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:17206
public methods for cuts and aggregation rows
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
#define CONSHDLR_PRESOLTIMING
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:770
static SCIP_DECL_CONSLOCK(consLockOrbitope)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define DEFAULT_SEPAFULLORBITOPE
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for the LP relaxation, rows and columns
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_DECL_CONSTRANS(consTransOrbitope)
SCIP_Real * r
Definition: circlepacking.c:50
static SCIP_DECL_CONSCHECK(consCheckOrbitope)
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
general public methods
type definitions for symmetry computations
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
public methods for solutions
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:702
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
methods for handling symmetries
int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
Definition: var.c:17198
public methods for the probing mode
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR ***vars, int nspcons, int nblocks, SCIP_ORBITOPETYPE orbitopetype, SCIP_Bool resolveprop, SCIP_Bool usedynamicprop, SCIP_Bool ismodelcons, SCIP_Bool mayinteract)
#define CONSHDLR_MAXPREROUNDS
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:525
public methods for message output
static SCIP_RETCODE checkFullOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool *feasible)
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1712
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:839
public methods for message handling
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
#define DEFAULT_FORCECONSCOPY
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
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)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
static SCIP_DECL_CONSRESPROP(consRespropOrbitope)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
static SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3096
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1382
#define SCIPABORT()
Definition: def.h:356
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:221
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
#define CONSHDLR_EAGERFREQ
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8626
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5720
SCIP_RETCODE SCIPcheckSolutionOrbisack(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool printreason, SCIP_Bool *feasible)
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define CONSHDLR_DELAYSEPA
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
static SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17406
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266
memory allocation routines