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