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