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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_orbitope.c
17  * @brief constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group
18  * @author Timo Berthold
19  * @author Marc Pfetsch
20  * @author Christopher Hojny
21  *
22  * The type of constraints of this constraint handler is described in cons_orbitope.h.
23  *
24  * The details of the method implemented here are described in the following papers.
25  *
26  * Packing and Partitioning Orbitopes@n
27  * Volker Kaibel and Marc E. Pfetsch,@n
28  * Math. Program. 114, No. 1, 1-36 (2008)
29  *
30  * Among other things, this paper describes so-called shifted column inequalities of the following
31  * 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
32  * bar. These inequalities can be used to handle symmetry and they are separated in this constraint
33  * handler. We use the linear time separation algorithm of the paper.@par
34  *
35  * Orbitopal Fixing@n
36  * Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,@n
37  * Discrete Optimization 8, No. 4, 595-610 (2011)
38  * (A preliminary version appears in Proc. IPCO 2007.)
39  *
40  * In this paper a linear time propagation algorithm is described, a variant of which is implemented
41  * here. The implemented variant does not run in linear time, but is very fast in practice.
42  *
43  * <table>
44  * <caption>translation table</caption>
45  * <tr><td>here</td><td>paper</td></tr>
46  * <tr><td></td><td></td></tr>
47  * <tr><td>nspcons </td><td>p </td></tr>
48  * <tr><td>nblocks </td><td>q </td></tr>
49  * <tr><td>vars </td><td>x </td></tr>
50  * <tr><td>vals </td><td>A^\\star</td></tr>
51  * <tr><td>weights </td><td>\\omega </td></tr>
52  * <tr><td>cases </td><td>\\tau </td></tr>
53  * <tr><td>fixtriangle </td><td>-- </td></tr>
54  * <tr><td>resolveprop </td><td>-- </td></tr>
55  * <tr><td>firstnonzeros</td><td>\\mu </td></tr>
56  * <tr><td>lastones </td><td>\\alpha </td></tr>
57  * <tr><td>frontiersteps</td><td>\\Gamma </td></tr>
58  * </table>
59  */
60 
61 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 
63 #include <assert.h>
64 #include <string.h>
65 #include <ctype.h>
66 
67 #include "scip/cons_orbisack.h"
68 #include "scip/cons_orbitope.h"
69 #include "scip/cons_setppc.h"
70 
71 /* constraint handler properties */
72 #define CONSHDLR_NAME "orbitope"
73 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes"
74 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
75 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
76 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
77 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
78 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */
79 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
80  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
81 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
82 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
83 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
84 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
85 
86 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
87 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
88 
89 #define DEFAULT_PPORBITOPE TRUE /**< whether we check if full orbitopes can be strengthened to packing/partitioning orbitopes */
90 #define DEFAULT_SEPAFULLORBITOPE FALSE /**< whether we separate inequalities for full orbitopes */
91 #define DEFAULT_CHECKALWAYSFEAS TRUE /**< whether check routine returns always SCIP_FEASIBLE */
92 
93 
94 /*
95  * Data structures
96  */
97 
98 /** constraint handler data */
99 struct SCIP_ConshdlrData
100 {
101  SCIP_Bool checkpporbitope; /**< whether we allow upgrading to packing/partitioning orbitopes */
102  SCIP_Bool sepafullorbitope; /**< whether we separate inequalities for full orbitopes orbitopes */
103  SCIP_Bool checkalwaysfeas; /**< whether check routine returns always SCIP_FEASIBLE */
104 };
105 
106 /** constraint data for orbitope constraints */
107 struct SCIP_ConsData
108 {
109  SCIP_VAR*** vars; /**< matrix of variables on which the symmetry acts */
110  SCIP_VAR** tmpvars; /**< temporary storage for variables */
111  SCIP_Real** vals; /**< LP-solution for those variables */
112  SCIP_Real* tmpvals; /**< temporary storage for values */
113  SCIP_Real** weights; /**< SC weight table */
114  int** cases; /**< indicator of the SC cases */
115  int nspcons; /**< number of set partitioning/packing constraints <=> p */
116  int nblocks; /**< number of symmetric variable blocks <=> q */
117  SCIP_ORBITOPETYPE orbitopetype; /**< type of orbitope constraint */
118  SCIP_Bool resolveprop; /**< should propagation be resolved? */
119  SCIP_Bool istrianglefixed; /**< has the upper right triangle already globally been fixed to zero? */
120 };
121 
122 
123 /*
124  * Local methods
125  */
126 
127 /** frees an orbitope constraint data */
128 static
130  SCIP* scip, /**< SCIP data structure */
131  SCIP_CONSDATA** consdata /**< pointer to orbitope constraint data */
132  )
133 {
134  int i;
135  int p;
136  int q;
137 
138  assert( consdata != NULL );
139  assert( *consdata != NULL );
140 
141  p = (*consdata)->nspcons;
142  q = (*consdata)->nblocks;
143  for (i = 0; i < p; ++i)
144  {
145  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases[i]), q); /*lint !e866*/
146  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars[i]), q); /*lint !e866*/
147  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights[i]), q); /*lint !e866*/
148  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals[i]), q); /*lint !e866*/
149  }
150 
151  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases), p);
152  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), p);
153  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights), p);
154  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals), p);
155 
156  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvals), p + q);
157  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvars), p + q);
158 
159  SCIPfreeBlockMemory(scip, consdata);
160 
161  return SCIP_OKAY;
162 }
163 
164 
165 /** creates orbitope constraint data */
166 static
168  SCIP* scip, /**< SCIP data structure */
169  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
170  SCIP_VAR*** vars, /**< variables array, must have size nspcons x nblocks */
171  int nspcons, /**< number of set partitioning (packing) constraints <=> p */
172  int nblocks, /**< number of symmetric variable blocks <=> q */
173  SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
174  SCIP_Bool resolveprop /**< should propagation be resolved? */
175  )
176 {
177  int i;
178  int j;
179 
180  assert(consdata != NULL);
181 
182  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
183 
184  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals, nspcons) );
185  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights, nspcons) );
186  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vars, nspcons) );
187  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases, nspcons) );
188 
189  for (i = 0; i < nspcons; ++i)
190  {
191  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals[i], nblocks) ); /*lint !e866*/
192  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights[i], nblocks) ); /*lint !e866*/
193  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars[i], vars[i], nblocks) ); /*lint !e866*/
194  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases[i], nblocks) ); /*lint !e866*/
195  }
196 
197  (*consdata)->tmpvals = NULL;
198  (*consdata)->tmpvars = NULL;
199  (*consdata)->nspcons = nspcons;
200  (*consdata)->nblocks = nblocks;
201  (*consdata)->orbitopetype = orbitopetype;
202  (*consdata)->resolveprop = resolveprop;
203  (*consdata)->istrianglefixed = FALSE;
204 
205  /* get transformed variables, if we are in the transformed problem */
206  if ( SCIPisTransformed(scip) )
207  {
208  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvals, nspcons + nblocks) );
209  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvars, nspcons + nblocks) );
210 
211  for (i = 0; i < nspcons; ++i)
212  {
213  /* make sure that no variable gets multiaggregated (cannot be handled by cons_orbitope, since one cannot easily
214  * eliminate single variables from an orbitope constraint).
215  */
216  for (j = 0; j < nblocks; ++j)
217  {
218  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i][j], &(*consdata)->vars[i][j]) );
219  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i][j]) );
220  }
221  }
222  }
223 
224  return SCIP_OKAY;
225 }
226 
227 
228 /** strenghten full orbitopes to packing/partitioning orbitopes if possible */
229 static
231  SCIP* scip, /**< SCIP data structure */
232  SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */
233  int* nrows, /**< pointer to number of rows of variable matrix */
234  int ncols, /**< number of columns of variable matrix */
235  SCIP_ORBITOPETYPE* type /**< pointer to store type of orbitope constraint after strengthening */
236  )
237 {
238  SCIP_CONSHDLR* setppcconshdlr;
239  SCIP_CONS** setppcconss;
240  int nsetppcconss;
241  SCIP_Bool* covered;
242  int nprobvars;
243  int* rowidxvar;
244  int ncovered;
245  int i;
246  int j;
247  SCIP_Bool success = TRUE;
248 
249  assert( scip != NULL );
250  assert( vars != NULL );
251  assert( vars != NULL );
252  assert( *nrows > 0 );
253  assert( ncols > 0 );
254  assert( type != NULL );
255 
256  *type = SCIP_ORBITOPETYPE_FULL;
257 
258  setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
259  if ( setppcconshdlr == NULL )
260  return SCIP_OKAY;
261 
262  setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
263  nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
264 
265  if ( nsetppcconss == 0 )
266  return SCIP_OKAY;
267  assert( setppcconss != NULL );
268 
269  /* whether a row is contained in packing/partitioning constraint */
270  SCIP_CALL( SCIPallocClearBufferArray(scip, &covered, *nrows) );
271  ncovered = 0;
272 
273  /* array storing index of orbitope row a variable is contained in */
274  nprobvars = SCIPgetNVars(scip);
275 
276  SCIP_CALL( SCIPallocBufferArray(scip, &rowidxvar, nprobvars) );
277 
278  for (i = 0; i < nprobvars; ++i)
279  rowidxvar[i] = -1;
280 
281  for (i = 0; i < *nrows && success; ++i)
282  {
283  for (j = 0; j < ncols; ++j)
284  {
285  if ( SCIPvarIsNegated(vars[i][j]) )
286  {
287  success = FALSE;
288  break;
289  }
290 
291  rowidxvar[SCIPvarGetProbindex(vars[i][j])] = i;
292  }
293  }
294 
295  if ( ! success )
296  goto FREEUPGRADESTRUCTURES;
297 
298  /* iterate over rows of orbitope and check whether rows are contained in partitioning constraints
299  *
300  * @todo sort constraints within the setppcconss array: first by type and then by increasing number of
301  * contained variables */
302  for (i = 0; i < *nrows && success; ++i)
303  {
304  /* iterate over constraints */
305  int c;
306  for (c = 0; c < nsetppcconss && success; ++c)
307  {
308  int nsetppcvars;
309  SCIP_VAR** setppcvars;
310  SCIP_VAR* var;
311  int nfound = 0;
312 
313  /* check type */
314  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING ||
315  SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING )
316  continue;
317  assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING );
318 
319  /* get set packing/partitioning variables */
320  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
321  assert( nsetppcvars > 0 );
322 
323  /* partitioning constraint contains wrong number of variables */
324  if ( nsetppcvars != ncols )
325  continue;
326  assert( nsetppcvars == ncols );
327 
328  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
329  assert( setppcvars != NULL );
330 
331  /* check whether i-th row is contained in partitioning constraint */
332  for (j = 0; j < nsetppcvars; ++j)
333  {
334  int idx;
335 
336  var = setppcvars[j];
337  if ( SCIPvarIsNegated(var) )
338  break;
339 
340  idx = SCIPvarGetProbindex(var);
341 
342  if ( rowidxvar[idx] == i )
343  ++nfound;
344  else
345  break;
346  }
347 
348  if ( nfound == ncols )
349  {
350  assert( ! covered[i] );
351  covered[i] = TRUE;
352  ++ncovered;
353 
354  break;
355  }
356  }
357  }
358 
359  if ( ncovered == *nrows )
360  {
362  goto FREEUPGRADESTRUCTURES;
363  }
364 
365  /* iterate over rows of orbitope and check whether rows are contained in packing constraints */
366  for (i = 0; i < *nrows; ++i)
367  {
368  int c;
369 
370  if ( covered[i] )
371  continue;
372 
373  /* iterate over constraints */
374  for (c = 0; c < nsetppcconss; ++c)
375  {
376  int nsetppcvars;
377  SCIP_VAR** setppcvars;
378  SCIP_VAR* var;
379  int nfound = 0;
380 
381  /* check type */
382  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
383  continue;
384 
385  /* get set packing/partitioning variables */
386  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
387  assert( nsetppcvars > 0 );
388 
389  /* packing/partitioning constraint contains too few variables */
390  if ( nsetppcvars < ncols )
391  continue;
392  assert( nsetppcvars >= ncols );
393 
394  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
395  assert( setppcvars != NULL );
396 
397  /* check whether i-th row is contained in packing constraint */
398  for (j = 0; j < nsetppcvars && nfound < ncols; ++j)
399  {
400  int idx;
401 
402  var = setppcvars[j];
403  if ( SCIPvarIsNegated(var) )
404  continue;
405 
406  idx = SCIPvarGetProbindex(var);
407 
408  if ( rowidxvar[idx] == i )
409  ++nfound;
410  }
411 
412  if ( nfound == ncols )
413  {
414  assert( ! covered[i] );
415  covered[i] = TRUE;
416  ++ncovered;
417 
418  break;
419  }
420  }
421  }
422 
423  if ( ncovered == *nrows )
425  else if ( ncovered >= 3 )
426  {
427  int r = *nrows - 1;
428  while ( r >= 0 )
429  {
430  if ( ! covered[r] )
431  {
432  for (i = r; i < *nrows - 1; ++i)
433  {
434  SCIP_VAR** row = vars[i];
435  vars[i] = vars[i+1];
436  vars[i+1] = row;
437  }
438  *nrows -= 1;
439  }
440  --r;
441  }
443  }
444 
445  FREEUPGRADESTRUCTURES:
446  SCIPfreeBufferArray(scip, &rowidxvar);
447  SCIPfreeBufferArray(scip, &covered);
448 
449  return SCIP_OKAY;
450 }
451 
452 
453 #ifdef PRINT_MATRIX
454 /** debug method, prints variable matrix */
455 static
456 void printMatrix(
457  SCIP* scip, /**< SCIP data structure */
458  SCIP_CONSDATA* consdata /**< the constraint data */
459  )
460 {
461  int i;
462  int j;
463 
464  assert( consdata != NULL );
465  assert( consdata->nspcons > 0 );
466  assert( consdata->nblocks > 0 );
467  assert( consdata->vars != NULL );
468 
469  for (j = 0; j < consdata->nblocks; ++j)
470  SCIPinfoMessage(scip, NULL, "-");
471 
472  SCIPinfoMessage(scip, NULL, "\n");
473  for (i = 0; i < consdata->nspcons; ++i)
474  {
475  for (j = 0; j < consdata->nblocks; ++j)
476  {
477  if ( SCIPvarGetUbLocal(consdata->vars[i][j]) - SCIPvarGetLbLocal(consdata->vars[i][j]) < 0.5 )
478  SCIPinfoMessage(scip, NULL, "%1.0f", REALABS(SCIPvarGetUbLocal(consdata->vars[i][j])));
479  else
480  SCIPinfoMessage(scip, NULL, " ");
481  }
482  SCIPinfoMessage(scip, NULL, "|\n");
483  }
484  for (j = 0; j < consdata->nblocks; ++j)
485  SCIPinfoMessage(scip, NULL, "-");
486  SCIPinfoMessage(scip, NULL, "\n");
487 }
488 #endif
489 
490 
491 #ifdef SHOW_SCI
492 /** Print SCI in nice form for debugging */
493 static
494 SCIP_RETCODE printSCI(
495  SCIP* scip, /**< SCIP pointer */
496  int p, /**< number of rows */
497  int q, /**< number of columns */
498  int** cases, /**< SCI dynamic programming table */
499  int i, /**< row position of bar */
500  int j /**< column position of bar */
501  )
502 {
503  int k;
504  int l;
505  int** M;
506  int p1;
507  int p2;
508 
509  SCIP_CALL( SCIPallocBufferArray(scip, &M, p) );
510  for (k = 0; k < p; ++k)
511  {
512  SCIP_CALL( SCIPallocBufferArray(scip, &M[k], q) ); /*lint !e866*/
513  for (l = 0; l < q; ++l)
514  M[k][l] = 0;
515  }
516 
517  /* first add bar */
518  for (l = j; l < q; ++l)
519  {
520  assert( M[i][l] == 0 );
521  M[i][l] = 1;
522  }
523 
524  /* then add shifted column */
525  p1 = i-1;
526  p2 = j-1;
527  do
528  {
529  assert( cases[p1][p2] != -1 );
530  assert( p1 >= 0 && p1 < i );
531  assert( p2 >= 0 && p2 < j );
532 
533  /* if case 1 */
534  if ( cases[p1][p2] == 1 )
535  --p2; /* decrease column */
536  else
537  {
538  /* case 2 or 3: */
539  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
540  assert( M[p1][p2] == 0 );
541  M[p1][p2] = -1;
542  if ( cases[p1][p2] == 3 )
543  break;
544  }
545  --p1; /* decrease row */
546  }
547  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
548  assert( cases[p1][p2] == 3 );
549 
550  /* now output matrix M */
551  for (l = 0; l < q; ++l)
552  SCIPinfoMessage(scip, NULL, "-");
553  SCIPinfoMessage(scip, NULL, "\n");
554 
555  for (k = 0; k < p; ++k)
556  {
557  for (l = 0; l < q; ++l)
558  {
559  if ( l > k )
560  SCIPinfoMessage(scip, NULL, "*");
561  else
562  {
563  switch (M[k][l])
564  {
565  case 1:
566  SCIPinfoMessage(scip, NULL, "+");
567  break;
568  case -1:
569  SCIPinfoMessage(scip, NULL, "-");
570  break;
571  case 0:
572  SCIPinfoMessage(scip, NULL, "#");
573  break;
574  default:
575  SCIPerrorMessage("unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]);
576  SCIPABORT();
577  }
578  }
579  }
580  SCIPinfoMessage(scip, NULL, "\n");
581  }
582 
583  for (l = 0; l < q; ++l)
584  SCIPinfoMessage(scip, NULL, "-");
585  SCIPinfoMessage(scip, NULL, "\n");
586 
587  for (k = 0; k < p; ++k)
588  SCIPfreeBufferArray(scip, &M[k]);
589  SCIPfreeBufferArray(scip, &M);
590 
591  return SCIP_OKAY;
592 }
593 #endif
594 
595 
596 /** copies the variables values from the solution to the constraint data structure */
597 static
598 void copyValues(
599  SCIP* scip, /**< the SCIP data structure */
600  SCIP_CONSDATA* consdata, /**< the constraint data */
601  SCIP_SOL* sol /**< a primal solution or NULL for the current LP optimum */
602  )
603 {
604  int i;
605  int j;
606 
607  assert( scip != NULL );
608  assert( consdata != NULL );
609  assert( consdata->nspcons > 0 );
610  assert( consdata->nblocks > 0 );
611  assert( consdata->vars != NULL );
612  assert( consdata->vals != NULL );
613 
614  for (i = 0; i < consdata->nspcons; ++i)
615  {
616  for (j = 0; j < consdata->nblocks; ++j)
617  consdata->vals[i][j] = SCIPgetSolVal(scip, sol, consdata->vars[i][j]);
618  }
619 }
620 
621 
622 /** compute the dynamic programming table for SC
623  *
624  * Build up dynamic programming table in order to find SCs with minimum weight.
625  *
626  * The values of the minimal SCIs are stored in @a weights.
627  * The array @a cases[i][j] stores which of the cases were applied to get @a weights[i][j].
628  * Here, 3 means that we have reached the upper limit.
629  *
630  * We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a
631  * bit more efficient.
632  */
633 static
634 void computeSCTable(
635  SCIP* scip, /**< SCIP pointer */
636  int nspcons, /**< number of set partitioning (packing) constraints <=> p */
637  int nblocks, /**< number of symmetric variable blocks <=> q */
638  SCIP_Real** weights, /**< SC weight table */
639  int** cases, /**< indicator of the SC cases */
640  SCIP_Real** vals /**< current solution */
641  )
642 {
643  SCIP_Real minvalue;
644  int diagsize;
645  int i;
646  int j;
647 
648  assert( weights != NULL );
649  assert( cases != NULL );
650  assert( vals != NULL );
651 
652 #ifndef NDEBUG
653  /* for debugging */
654  for (i = 0; i < nspcons; ++i)
655  {
656  for (j = 0; j < nblocks; ++j)
657  {
658  if ( i >= j )
659  {
660  weights[i][j] = -1.0;
661  cases[i][j] = -1;
662  }
663  }
664  }
665 #endif
666 
667  /* initialize diagonal */
668  minvalue = vals[0][0];
669  weights[0][0] = minvalue;
670  cases[0][0] = 3;
671 
672  /* get last row of triangle */
673  diagsize = nblocks;
674  if ( nspcons < nblocks )
675  diagsize = nspcons;
676 
677  for (j = 1; j < diagsize; ++j)
678  {
679  /* use LT to move entry as far to the left as possible */
680  if ( SCIPisLT(scip, vals[j][j], minvalue) )
681  {
682  minvalue = vals[j][j];
683  cases[j][j] = 3;
684  }
685  else
686  cases[j][j] = 1;
687  weights[j][j] = minvalue;
688  }
689 
690  /* initialize first column */
691  for (i = 1; i < nspcons; ++i)
692  {
693  weights[i][0] = weights[i-1][0] + vals[i][0];
694  cases[i][0] = 2; /* second case */
695  }
696 
697  /* build the table */
698  for (i = 2; i < nspcons; ++i)
699  {
700  for (j = 1; j < nblocks && j < i; ++j)
701  {
702  SCIP_Real weightleft;
703  SCIP_Real weightright;
704 
705  assert( cases[i-1][j] != -1 );
706  assert( cases[i-1][j-1] != -1 );
707 
708  weightleft = weights[i-1][j-1];
709  weightright = vals[i][j] + weights[i-1][j];
710 
711  /* For first column: cannot take left possibility */
712  if ( SCIPisLT(scip, weightleft, weightright) )
713  {
714  weights[i][j] = weightleft;
715  cases[i][j] = 1;
716  }
717  else
718  {
719  weights[i][j] = weightright;
720  cases[i][j] = 2;
721  }
722  }
723  }
724 }
725 
726 
727 /** fix upper right triangle if necessary */
728 static
730  SCIP* scip, /**< SCIP data structure */
731  SCIP_CONS* cons, /**< constraint to be processed */
732  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
733  int* nfixedvars /**< pointer to add up the number of found domain reductions */
734  )
735 {
736  SCIP_CONSDATA* consdata;
737  SCIP_VAR*** vars;
738  SCIP_Bool fixedglobal;
739  SCIP_Bool fixed;
740  int diagsize;
741  int nspcons;
742  int nblocks;
743  int i;
744  int j;
745 
746  assert( scip != NULL );
747  assert( cons != NULL );
748  assert( infeasible != NULL );
749  assert( nfixedvars != NULL );
750 
751  consdata = SCIPconsGetData(cons);
752  assert( consdata != NULL );
753  assert( consdata->nspcons > 0 );
754  assert( consdata->nblocks > 0 );
755  assert( consdata->vars != NULL );
756 
757  *infeasible = FALSE;
758  *nfixedvars = 0;
759 
760  if ( consdata->istrianglefixed )
761  return SCIP_OKAY;
762 
763  nspcons = consdata->nspcons;
764  nblocks = consdata->nblocks;
765  vars = consdata->vars;
766  fixedglobal = TRUE;
767 
768  /* get last row of triangle */
769  diagsize = nblocks;
770  if ( nspcons < nblocks )
771  diagsize = nspcons;
772 
773  /* fix variables to 0 */
774  for (i = 0; i < diagsize; ++i)
775  {
776  for (j = i+1; j < nblocks; ++j)
777  {
778  /* fix variable, if not in the root the fixation is local */
779  SCIP_CALL( SCIPfixVar(scip, vars[i][j], 0.0, infeasible, &fixed) );
780 
781  if ( *infeasible )
782  {
783  SCIPdebugMsg(scip, "The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n");
784  return SCIP_OKAY;
785  }
786 
787  if ( fixed )
788  ++(*nfixedvars);
789 
790  if ( SCIPvarGetUbGlobal(vars[i][j]) > 0.5 )
791  fixedglobal = FALSE;
792  }
793  }
794  if ( *nfixedvars > 0 )
795  {
796  SCIPdebugMsg(scip, "<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n", SCIPconsGetName(cons), fixedglobal ? "globally" : "locally", *nfixedvars);
797  }
798  else
799  {
800  SCIPdebugMsg(scip, "<%s>: Upper right triangle already fixed to 0.\n", SCIPconsGetName(cons));
801  }
802 
803  if ( fixedglobal )
804  consdata->istrianglefixed = TRUE;
805 
806  return SCIP_OKAY;
807 }
808 
809 
810 /** separates shifted column inequalities according to the solution stored in consdata->vals */
811 static
813  SCIP* scip, /**< the SCIP data structure */
814  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
815  SCIP_CONS* cons, /**< constraint */
816  SCIP_CONSDATA* consdata, /**< the constraint data */
817  SCIP_Bool* infeasible, /**< whether we detected infeasibility */
818  int* nfixedvars, /**< pointer to store the number of variables fixed */
819  int* ncuts /**< pointer to store number of separated SCIs */
820  )
821 {
822  SCIP_Real** vals;
823  SCIP_Real** weights;
824  SCIP_Real* tmpvals;
825  SCIP_VAR*** vars;
826  SCIP_VAR** tmpvars;
827  int** cases;
828  int nspcons;
829  int nblocks;
830  int i;
831  int j;
832  int l;
833 
834  assert( scip != NULL );
835  assert( conshdlr != NULL );
836  assert( cons != NULL );
837  assert( infeasible != NULL);
838  assert( nfixedvars != NULL );
839  assert( ncuts != NULL );
840 
841  assert( consdata != NULL );
842  assert( consdata->nspcons > 0 );
843  assert( consdata->nblocks > 0 );
844  assert( consdata->vars != NULL );
845  assert( consdata->vals != NULL );
846  assert( consdata->tmpvars != NULL );
847  assert( consdata->tmpvals != NULL );
848  assert( consdata->weights != NULL );
849  assert( consdata->cases != NULL );
850 
851  *infeasible = FALSE;
852  *nfixedvars = 0;
853  *ncuts = 0;
854 
855  nspcons = consdata->nspcons;
856  nblocks = consdata->nblocks;
857  vars = consdata->vars;
858  vals = consdata->vals;
859  tmpvars = consdata->tmpvars;
860  tmpvals = consdata->tmpvals;
861  weights = consdata->weights;
862  cases = consdata->cases;
863 
864  /* check for upper right triangle */
865  if ( ! consdata->istrianglefixed )
866  {
867  SCIP_CALL( fixTriangle(scip, cons, infeasible, nfixedvars) );
868  if ( *infeasible )
869  return SCIP_OKAY;
870  if ( *nfixedvars > 0 )
871  return SCIP_OKAY;
872  }
873 
874  /* compute table if necessary (i.e., not computed before) */
875  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
876 
877  /* loop through rows */
878  for (i = 1; i < nspcons && ! (*infeasible); ++i)
879  {
880  SCIP_Real bar; /* value of bar: */
881  int lastcolumn; /* last column considered as part of the bar */
882 
883  bar = 0.0;
884  lastcolumn = nblocks - 1;
885  if ( lastcolumn > i )
886  lastcolumn = i;
887 
888  /* traverse row from right to left: */
889  /* j >= 1, since for j = 0, i.e., the bar is a complete row, there does not exist an SCI */
890  for (j = lastcolumn; j > 0; --j)
891  {
892  bar += vals[i][j];
893 
894  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
895  if ( SCIPisEfficacious(scip, bar - weights[i-1][j-1]) )
896  {
897  SCIP_Real weight;
898  SCIP_ROW* row;
899 #ifdef SCIP_DEBUG
900  char name[SCIP_MAXSTRLEN];
901 #endif
902  int nvars;
903  int p1;
904  int p2;
905 
906  nvars = 0;
907  p1 = i-1;
908  p2 = j-1;
909  weight = 0.0;
910 
911  /* first add bar */
912  for (l = j; l <= lastcolumn; ++l)
913  {
914  tmpvars[nvars] = vars[i][l];
915  tmpvals[nvars] = 1.0;
916  nvars++;
917  }
918 
919  /* then add shifted column */
920  do
921  {
922  assert( cases[p1][p2] != -1 );
923  assert( p1 >= 0 && p1 < i );
924  assert( p2 >= 0 && p2 < j );
925 
926  /* if case 1 */
927  if (cases[p1][p2] == 1)
928  p2--; /* decrease column */
929  else
930  {
931  /* case 2 or 3: */
932  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
933  tmpvars[nvars] = vars[p1][p2];
934  tmpvals[nvars] = -1.0;
935  nvars++;
936  weight += vals[p1][p2];
937  if ( cases[p1][p2] == 3 )
938  break;
939  }
940  p1--; /* decrease row */
941  }
942  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
943  assert( cases[p1][p2] == 3 );
944 
945  /* generate cut */
946 #ifdef SCIP_DEBUG
947  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sci_%d_%d", i, j);
948  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
949 #else
950  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
951 #endif
952  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvars, tmpvars, tmpvals) );
953  /*SCIP_CALL( SCIPprintRow(scip, row, NULL) ); */
954  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
955  SCIP_CALL( SCIPreleaseRow(scip, &row) );
956  ++(*ncuts);
957 
958 #ifdef SHOW_SCI
959  SCIP_CALL( printSCI(scip, nspcons, nblocks, cases, i, j) );
960 #endif
961 
962  assert( SCIPisSumEQ(scip, weights[i-1][j-1], weight) );
963  }
964  }
965  }
966  return SCIP_OKAY;
967 }
968 
969 
970 /** propagation method for a single packing or partitioning orbitope constraint */
971 static
973  SCIP* scip, /**< SCIP data structure */
974  SCIP_CONS* cons, /**< constraint to be processed */
975  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
976  int* nfixedvars /**< pointer to add up the number of found domain reductions */
977  )
978 {
979  SCIP_CONSDATA* consdata;
980  SCIP_VAR*** vars;
981  SCIP_ORBITOPETYPE orbitopetype;
982  int* firstnonzeros;
983  int* lastones;
984  int* frontiersteps;
985  int lastoneprevrow;
986  int nspcons;
987  int nblocks;
988  int nsteps;
989  int i;
990  int j;
991 
992  assert( scip != NULL );
993  assert( cons != NULL );
994  assert( infeasible != NULL );
995  assert( nfixedvars != NULL );
996 
997  *nfixedvars = 0;
998 
999  if( !SCIPallowDualReds(scip) )
1000  return SCIP_OKAY;
1001 
1002  consdata = SCIPconsGetData(cons);
1003  assert( consdata != NULL );
1004  assert( consdata->nspcons > 0 );
1005  assert( consdata->nblocks > 0 );
1006  assert( consdata->vars != NULL );
1007 
1008  nspcons = consdata->nspcons;
1009  nblocks = consdata->nblocks;
1010  vars = consdata->vars;
1011  orbitopetype = consdata->orbitopetype;
1012 
1013  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
1014 
1015  /* fix upper right triangle if still necessary */
1016  if ( ! consdata->istrianglefixed )
1017  {
1018  int nfixed = 0;
1019  SCIP_CALL( fixTriangle(scip, cons, infeasible, &nfixed) );
1020  *nfixedvars += nfixed;
1021  }
1022 
1023  /* prepare further propagation */
1024  SCIP_CALL( SCIPallocBufferArray(scip, &firstnonzeros, nspcons) );
1025  SCIP_CALL( SCIPallocBufferArray(scip, &lastones, nspcons) );
1026  SCIP_CALL( SCIPallocBufferArray(scip, &frontiersteps, nblocks) );
1027 
1028 #ifdef PRINT_MATRIX
1029  SCIPdebugMsg(scip, "Matrix:\n");
1030  printMatrix(scip, consdata);
1031 #endif
1032 
1033  /* propagate */
1034  lastoneprevrow = 0;
1035  lastones[0] = 0;
1036 
1037  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING )
1038  {
1039  /* packing case: if entry (0,0) is fixed to 0 */
1040  if ( SCIPvarGetUbLocal(vars[0][0]) < 0.5 )
1041  {
1042  lastoneprevrow = -1;
1043  lastones[0] = -1;
1044  }
1045  }
1046  nsteps = 0;
1047 
1048  for (i = 1; i < nspcons; ++i)
1049  {
1050  int lastcolumn;
1051  int firstnonzeroinrow;
1052  int lastoneinrow;
1053  SCIP_Bool infrontier;
1054 
1055  /* last column considered as part of the bar: */
1056  lastcolumn = nblocks - 1;
1057  if ( lastcolumn > i )
1058  lastcolumn = i;
1059 
1060  /* find first position not fixed to 0 (partitioning) or fixed to 1 (packing) */
1061  firstnonzeroinrow = -1;
1062  for (j = 0; j <= lastcolumn; ++j)
1063  {
1064  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1065  {
1066  /* partitioning case: if variable is not fixed to 0 */
1067  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1068  {
1069  firstnonzeroinrow = j;
1070  break;
1071  }
1072  }
1073  else
1074  {
1075  /* packing case: if variable is fixed to 1 */
1076  if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
1077  {
1078  firstnonzeroinrow = j;
1079  break;
1080  }
1081  }
1082  }
1083  /* if all variables are fixed to 0 in the partitioning case - should not happen */
1084  if ( firstnonzeroinrow == -1 && orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1085  {
1086  SCIPdebugMsg(scip, " -> Infeasible node: all variables in row %d are fixed to 0.\n", i);
1087  *infeasible = TRUE;
1088  /* conflict should be analyzed by setppc constraint handler */
1089  goto TERMINATE;
1090  }
1091  firstnonzeros[i] = firstnonzeroinrow;
1092  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || firstnonzeroinrow >= 0 );
1093  assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn );
1094 
1095  /* compute rightmost possible position for a 1 */
1096  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneprevrow );
1097  assert( lastoneprevrow <= lastcolumn );
1098 
1099  /* if we are at right border or if entry in column lastoneprevrow+1 is fixed to 0 */
1100  infrontier = FALSE;
1101  assert( lastoneprevrow + 1 >= 0 );
1102  if ( lastoneprevrow == nblocks-1 || SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 ) /*lint !e679*/
1103  lastoneinrow = lastoneprevrow;
1104  else
1105  {
1106  lastoneinrow = lastoneprevrow + 1;
1107  frontiersteps[nsteps++] = i;
1108  infrontier = TRUE;
1109  }
1110 
1111  /* store lastoneinrow */
1112  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneinrow );
1113  assert( lastoneinrow <= lastcolumn );
1114  lastones[i] = lastoneinrow;
1115 
1116  /* check whether we are infeasible */
1117  if ( firstnonzeroinrow > lastoneinrow )
1118  {
1119  int k;
1120 
1121 #ifdef SCIP_DEBUG
1122  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1123  {
1124  SCIPdebugMsg(scip, " -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n",
1125  i, firstnonzeroinrow, lastoneinrow);
1126  }
1127  else
1128  {
1129  SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n",
1130  i, firstnonzeroinrow, lastoneinrow);
1131  }
1132 #endif
1133  /* check if conflict analysis is applicable */
1135  {
1136  /* conflict analysis only applicable in SOLVING stage */
1137  assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) );
1138 
1139  /* perform conflict analysis */
1141 
1142  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1143  {
1144  /* add bounds (variables fixed to 0) that result in the first nonzero entry */
1145  for (j = 0; j <= lastcolumn; ++j)
1146  {
1147  /* add varaibles in row up to the first variable fixed to 0 */
1148  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1149  break;
1150 
1151  assert( SCIPvarGetUbLocal(vars[i][j]) < 0.5 );
1152  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1153  }
1154  }
1155  else
1156  {
1157  /* add bounds that result in the last one - check top left entry for packing case */
1158  if ( lastones[0] == -1 )
1159  {
1160  assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1161  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1162  }
1163 
1164  /* mark variable fixed to 1 */
1165  assert( SCIPvarGetLbLocal(vars[i][firstnonzeroinrow]) > 0.5 );
1166  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][firstnonzeroinrow]) );
1167  }
1168 
1169  /* add bounds that result in the last one - pass through rows */
1170  for (k = 1; k < i; ++k)
1171  {
1172  int l;
1173  l = lastones[k] + 1;
1174 
1175  /* if the frontier has not moved and we are not beyond the matrix boundaries */
1176  if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1177  {
1178  assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1179  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1180  }
1181  }
1182  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1183  }
1184 
1185  *infeasible = TRUE;
1186  goto TERMINATE;
1187  }
1188 
1189  /* fix entries beyond the last possible position for a 1 in the row to 0 (see Lemma 1 in the paper) */
1190  for (j = lastoneinrow+1; j <= lastcolumn; ++j)
1191  {
1192  /* if the entry is not yet fixed to 0 */
1193  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1194  {
1195  SCIP_Bool tightened;
1196  int inferInfo;
1197 
1198  SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 0.\n", i, j);
1199 
1200  tightened = FALSE;
1201 
1202  /* fix variable to 0 and store position of (i,lastoneinrow+1) for conflict resolution */
1203  inferInfo = i * nblocks + lastoneinrow + 1;
1204  /* correction according to Lemma 1 in the paper (second part): store (i,lastoneinrow+2) */
1205  if ( !infrontier )
1206  ++inferInfo;
1207  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i][j], FALSE, cons, inferInfo, infeasible, &tightened) );
1208 
1209  /* if entry is fixed to one -> infeasible node */
1210  if ( *infeasible )
1211  {
1212  SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow);
1213  /* check if conflict analysis is applicable */
1215  {
1216  int k;
1217 
1218  /* conflict analysis only applicable in SOLVING stage */
1219  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip));
1220 
1221  /* perform conflict analysis */
1223 
1224  /* add current bound */
1225  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1226 
1227  /* add bounds that result in the last one - check top left entry for packing case */
1228  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING && lastones[0] == -1 )
1229  {
1230  assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1231  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1232  }
1233 
1234  /* add bounds that result in the last one - pass through rows */
1235  for (k = 1; k < i; ++k)
1236  {
1237  int l;
1238  l = lastones[k] + 1;
1239 
1240  /* if the frontier has not moved and we are not beyond the matrix boundaries */
1241  if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1242  {
1243  assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1244  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1245  }
1246  }
1247  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1248  }
1249 
1250  goto TERMINATE;
1251  }
1252  if ( tightened )
1253  ++(*nfixedvars);
1254  }
1255  }
1256 
1257  lastoneprevrow = lastoneinrow;
1258  }
1259 
1260  /* check whether fixing any entry to 0 results in a contradiction -> loop through rows in frontiersteps (a.k.a. gamma) */
1261  for (j = 0; j < nsteps; ++j)
1262  {
1263  int s;
1264  int lastoneinrow;
1265 
1266  s = frontiersteps[j];
1267  lastoneinrow = lastones[s];
1268  /* note for packing case: if we are in a frontier step then lastoneinrow >= 0 */
1269  assert( 0 <= lastoneinrow && lastoneinrow < nblocks );
1270 
1271  /* if entry is not fixed */
1272  if ( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 && SCIPvarGetUbLocal(vars[s][lastoneinrow]) > 0.5 )
1273  {
1274  int betaprev;
1275  betaprev = lastoneinrow - 1;
1276 
1277  /* loop through rows below s */
1278  for (i = s+1; i < nspcons; ++i)
1279  {
1280  int beta;
1281 
1282  assert( betaprev + 1 >= 0 );
1283  if ( betaprev == nblocks-1 || SCIPvarGetUbLocal(vars[i][betaprev+1]) < 0.5 ) /*lint !e679*/
1284  beta = betaprev;
1285  else
1286  beta = betaprev + 1;
1287  assert( -1 <= beta && beta < nblocks );
1288 
1289  if ( firstnonzeros[i] > beta )
1290  {
1291  SCIP_Bool tightened;
1292  int inferInfo;
1293 
1294  /* can fix (s,lastoneinrow) (a.k.a (s,alpha)) to 1
1295  * (do not need to fix other entries to 0, since they will be
1296  * automatically fixed by SCIPtightenVarLb.)
1297  */
1298  assert( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 );
1299  SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow);
1300 
1301  tightened = FALSE;
1302 
1303  /* store position (i,firstnonzeros[i]) */
1304  inferInfo = nblocks * nspcons + i * nblocks + firstnonzeros[i];
1305  SCIP_CALL( SCIPinferBinvarCons(scip, vars[s][lastoneinrow], TRUE, cons, inferInfo, infeasible, &tightened) );
1306 
1307  assert( !(*infeasible) );
1308  if ( tightened )
1309  ++(*nfixedvars);
1310  break;
1311  }
1312  betaprev = beta;
1313  }
1314  }
1315  }
1316 
1317  TERMINATE:
1318  SCIPfreeBufferArray(scip, &frontiersteps);
1319  SCIPfreeBufferArray(scip, &lastones);
1320  SCIPfreeBufferArray(scip, &firstnonzeros);
1321 
1322  return SCIP_OKAY;
1323 }
1324 
1325 
1326 /** propagation of full orbitopes (called recursively) */
1327 static
1329  SCIP* scip, /**< the SCIP data structure */
1330  SCIP_CONS* cons, /**< constraint to be processed */
1331  SCIP_VAR*** vars, /**< variable matrix */
1332  int firstcol, /**< first column to consider */
1333  int lastcol, /**< last column to consider + 1 */
1334  int currow, /**< current row */
1335  int nrows, /**< number of rows */
1336  int ncols, /**< number of columns */
1337  int* nfixedvars, /**< pointer to store the number of variables fixed during propagation */
1338  SCIP_Bool* infeasible /**< pointer to store whether infeasibility was detected */
1339  )
1340 {
1341  int lastone;
1342  int firstzero = -1;
1343  int i;
1344  int j;
1345  int l;
1346  SCIP_Bool tightened;
1347  int inferinfo;
1348 
1349  assert( scip != NULL );
1350  assert( cons != NULL );
1351  assert( vars != NULL );
1352  assert( 0 <= firstcol && firstcol < lastcol );
1353  assert( infeasible != NULL );
1354  assert( nfixedvars != NULL );
1355  assert( nrows > 0 );
1356  assert( ncols > 0 );
1357 
1358  /* possibly stop recursion */
1359  if ( *infeasible || currow >= nrows )
1360  return SCIP_OKAY;
1361 
1362  /* init indicators of 1-entry position */
1363  lastone = firstcol - 1;
1364 
1365  /* iterate over entries of current row and perform orbitope propagation */
1366  for (j = firstcol; j < lastcol; ++j)
1367  {
1368  assert( vars[currow][j] != NULL );
1369 
1370  if ( SCIPvarGetLbLocal(vars[currow][j]) > 0.5 )
1371  {
1372  /* fix all variables smaller than j to 1 */
1373  for (l = lastone + 1; l < j; ++l)
1374  {
1375  /* check again since fixing previous entries may have modified the current entry */
1376  if ( SCIPvarGetLbLocal(vars[currow][l]) < 0.5 && SCIPvarGetUbLocal(vars[currow][l]) > 0.5 )
1377  {
1378  tightened = FALSE;
1379  inferinfo = currow * ncols + j;
1380 
1381  SCIP_CALL( SCIPinferBinvarCons(scip, vars[currow][l], TRUE, cons, inferinfo, infeasible, &tightened) );
1382  if ( tightened )
1383  ++(*nfixedvars);
1384  }
1385  else if ( SCIPvarGetUbLocal(vars[currow][l]) < 0.5 )
1386  {
1388  {
1390 
1391  for (i = 0; i <= currow; ++i)
1392  {
1393  int s;
1394  for (s = 0; s <= l; ++s)
1395  {
1396  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][s]) );
1397  }
1398  }
1399 
1400  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1401  }
1402  *infeasible = TRUE;
1403 
1404  return SCIP_OKAY;
1405  }
1406  }
1407 
1408  lastone = j;
1409  }
1410  else if ( SCIPvarGetUbLocal(vars[currow][j]) < 0.5 )
1411  {
1412  firstzero = j;
1413 
1414  /* fix all remaining entries to 0 */
1415  for (l = j + 1; l < lastcol; ++l)
1416  {
1417  if ( SCIPvarGetUbLocal(vars[currow][l]) > 0.5 && SCIPvarGetLbLocal(vars[currow][l]) < 0.5 )
1418  {
1419  tightened = FALSE;
1420  inferinfo = currow * ncols + j;
1421 
1422  SCIP_CALL( SCIPinferBinvarCons(scip, vars[currow][l], FALSE, cons, inferinfo, infeasible, &tightened) );
1423 
1424  if ( tightened )
1425  ++(*nfixedvars);
1426  }
1427  /* -> infeasible */
1428  else if ( SCIPvarGetLbLocal(vars[currow][l]) > 0.5 )
1429  {
1431  {
1433 
1434  for (i = 0; i <= currow; ++i)
1435  {
1436  int s;
1437  for (s = 0; s <= l; ++s)
1438  {
1439  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][s]) );
1440  }
1441  }
1442 
1443  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1444  }
1445  *infeasible = TRUE;
1446 
1447  return SCIP_OKAY;
1448  }
1449  }
1450 
1451  break;
1452  }
1453  }
1454 
1455  /* The orbitope can be split into the sub orbitopes w.r.t. the 1-entries (firstcol, ..., lastone) and the 0-entries
1456  * (firstzero, ..., lastcol - 1). Furthermore, avoid trivial cases, i.e., the sub-orbitopes contain only one
1457  * column. */
1458  if ( lastone > firstcol )
1459  {
1460  SCIP_CALL( propagateFullOrbitope(scip, cons, vars, firstcol, lastone + 1, currow + 1, nrows, ncols, nfixedvars, infeasible) );
1461  }
1462 
1463  if ( firstzero >= 0 && firstzero < lastcol - 1 )
1464  {
1465  SCIP_CALL( propagateFullOrbitope(scip, cons, vars, firstzero, lastcol, currow + 1, nrows, ncols, nfixedvars, infeasible) );
1466  }
1467 
1468  return SCIP_OKAY;
1469 }
1470 
1471 
1472 /** propagation method for a single packing or partitioning orbitope constraint */
1473 static
1475  SCIP* scip, /**< SCIP data structure */
1476  SCIP_CONS* cons, /**< constraint to be processed */
1477  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
1478  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1479  )
1480 {
1481  SCIP_CONSDATA* consdata;
1482 
1483  assert( scip != NULL );
1484  assert( cons != NULL );
1485  assert( infeasible != NULL );
1486  assert( nfixedvars != NULL );
1487 
1488  *nfixedvars = 0;
1489  *infeasible = FALSE;
1490 
1491  /* @todo Can the following be removed? */
1492  if ( ! SCIPallowDualReds(scip) )
1493  return SCIP_OKAY;
1494 
1495  consdata = SCIPconsGetData(cons);
1496  assert( consdata != NULL );
1497  assert( consdata->nspcons > 0 );
1498  assert( consdata->nblocks > 0 );
1499  assert( consdata->vars != NULL );
1500  assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL );
1501 
1502  SCIP_CALL( propagateFullOrbitope(scip, cons, consdata->vars, 0, consdata->nblocks, 0, consdata->nspcons, consdata->nblocks, nfixedvars, infeasible) );
1503 
1504  return SCIP_OKAY;
1505 }
1506 
1507 
1508 /** propagation method for a single orbitope constraint */
1509 static
1511  SCIP* scip, /**< SCIP data structure */
1512  SCIP_CONS* cons, /**< constraint to be processed */
1513  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
1514  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1515  )
1516 {
1517  SCIP_CONSDATA* consdata;
1518  SCIP_ORBITOPETYPE orbitopetype;
1519 
1520  assert( scip != NULL );
1521  assert( cons != NULL );
1522  assert( infeasible != NULL );
1523  assert( nfixedvars != NULL );
1524 
1525  consdata = SCIPconsGetData(cons);
1526  assert( consdata != NULL );
1527 
1528  orbitopetype = consdata->orbitopetype;
1529 
1530  if ( orbitopetype == SCIP_ORBITOPETYPE_FULL )
1531  {
1532  SCIP_CALL( propagateFullOrbitopeCons(scip, cons, infeasible, nfixedvars) );
1533  }
1534  else
1535  {
1536  assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
1537  SCIP_CALL( propagatePackingPartitioningCons(scip, cons, infeasible, nfixedvars) );
1538  }
1539 
1540  return SCIP_OKAY;
1541 }
1542 
1543 
1544 /** Propagation conflict resolving method of propagator
1545  *
1546  * In this function we use that the propagation method above implicitly propagates SCIs, i.e., every
1547  * fixing can also be gotten via an SCI-fixing.
1548  *
1549  * Since the storage of an integer is not enough to store the complete information about the fixing
1550  * nor a complete shifted column, we have to use the linear time algorithm for SCIs.
1551  *
1552  * The inferinfo integer is set as follows:
1553  *
1554  * - If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1
1555  * then we fix these entries to 0 and inferinfo is i * nblocks + j, where (i,j) is the leader of the
1556  * bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments
1557  * above).
1558  *
1559  * - If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to
1560  * 1 and inferinfo is (nspcons*nblocks) + i * nblocks + j, where (i,j) is the leader of the bar; see
1561  * Proposition 1 (2c).
1562  */
1563 static
1565  SCIP* scip, /**< SCIP data structure */
1566  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1567  SCIP_VAR* infervar, /**< variable that was deduced */
1568  int inferinfo, /**< inference information */
1569  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
1570  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1571  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1572  )
1573 { /*lint --e{715}*/
1574  SCIP_CONSDATA* consdata;
1575  SCIP_Real** vals;
1576  SCIP_Real** weights;
1577  SCIP_VAR*** vars;
1578  SCIP_ORBITOPETYPE orbitopetype;
1579  int** cases;
1580 
1581  int i;
1582  int j;
1583  int nspcons;
1584  int nblocks;
1585 
1586  assert( scip != NULL );
1587  assert( cons != NULL );
1588  assert( result != NULL );
1589 
1590  consdata = SCIPconsGetData(cons);
1591  assert( consdata != NULL );
1592  assert( consdata->nspcons > 0 );
1593  assert( consdata->nblocks > 0 );
1594  assert( consdata->vars != NULL );
1595  assert( consdata->vals != NULL );
1596  assert( consdata->weights != NULL );
1597  assert( consdata->cases != NULL );
1598  assert( consdata->istrianglefixed );
1599 
1600  *result = SCIP_DIDNOTFIND;
1601  if ( ! consdata->resolveprop )
1602  return SCIP_OKAY;
1603 
1604  nspcons = consdata->nspcons;
1605  nblocks = consdata->nblocks;
1606  vars = consdata->vars;
1607  vals = consdata->vals;
1608  weights = consdata->weights;
1609  orbitopetype = consdata->orbitopetype;
1610  cases = consdata->cases;
1611 
1612  SCIPdebugMsg(scip, "Propagation resolution method of orbitope constraint using orbitopal fixing\n");
1613 
1614  /* fill table */
1615  for (i = 0; i < nspcons; ++i)
1616  {
1617  int lastcolumn;
1618 
1619  /* last column considered as part of the bar: */
1620  lastcolumn = nblocks - 1;
1621  if ( lastcolumn > i )
1622  lastcolumn = i;
1623  for (j = 0; j <= lastcolumn; ++j)
1624  {
1625  /* if the variable was fixed to zero at conflict time */
1626  if ( SCIPgetVarUbAtIndex(scip, vars[i][j], bdchgidx, FALSE) < 0.5 )
1627  vals[i][j] = 0.0;
1628  else
1629  {
1630  /* if the variable was fixed to one at conflict time */
1631  if ( SCIPgetVarLbAtIndex(scip, vars[i][j], bdchgidx, FALSE) > 0.5 )
1632  vals[i][j] = 2.0;
1633  else
1634  vals[i][j] = 1.0;
1635  }
1636  }
1637  }
1638 
1639 #ifdef PRINT_MATRIX
1640  SCIPdebugMsg(scip, "Matrix:\n");
1641  printMatrix(scip, consdata);
1642 #endif
1643 
1644  /* computation of table: this now minimizes the value of the shifted column */
1645  assert( consdata->istrianglefixed );
1646  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
1647 
1648  /* if we fixed variables in the bar to zero */
1649  assert( inferinfo >= 0 && inferinfo < 2 * nspcons * nblocks );
1650  if ( inferinfo < nspcons * nblocks )
1651  {
1652  int p1;
1653  int p2;
1654 #ifdef SCIP_DEBUG
1655  char str[SCIP_MAXSTRLEN];
1656  char tmpstr[SCIP_MAXSTRLEN];
1657 #endif
1658 
1659  i = (int) (inferinfo / nblocks);
1660  j = inferinfo % nblocks;
1661  assert( 0 <= i && i < nspcons );
1662  assert( 0 <= j && j < nblocks );
1663 
1664  /* find SCI with value 0 */
1665  assert( weights[i-1][j-1] < 0.5 );
1666 
1667  SCIPdebugMsg(scip, " -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i, MIN(i,nblocks));
1668 #ifdef SCIP_DEBUG
1669  str[0] = '\0';
1670 #endif
1671 
1672  p1 = i-1;
1673  p2 = j-1;
1674  do
1675  {
1676  assert( cases[p1][p2] != -1 );
1677  assert( p1 >= 0 && p1 < i );
1678  assert( p2 >= 0 && p2 < j );
1679 
1680  /* if case 1 */
1681  if ( cases[p1][p2] == 1 )
1682  --p2; /* decrease column */
1683  else
1684  {
1685  /* case 2 or 3: */
1686  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1687  assert( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
1688  SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
1689  *result = SCIP_SUCCESS;
1690 
1691 #ifdef SCIP_DEBUG
1692  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
1693  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1694 #endif
1695 
1696  if ( cases[p1][p2] == 3 )
1697  break;
1698  }
1699  --p1; /* decrease row */
1700  }
1701  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
1702  assert( cases[p1][p2] == 3 );
1703 
1704 #ifdef SCIP_DEBUG
1705  SCIPdebugMsg(scip, "%s\n", str);
1706 #endif
1707  }
1708  else
1709  {
1710  int k;
1711  int p1;
1712  int p2;
1713 #ifndef NDEBUG
1714  int pos1;
1715  int pos2;
1716 #endif
1717 #ifdef SCIP_DEBUG
1718  char str[SCIP_MAXSTRLEN];
1719  char tmpstr[SCIP_MAXSTRLEN];
1720 #endif
1721 
1722  /* if we fixed a variable in the SC to 1 */
1723  inferinfo -= nspcons * nblocks;
1724  i = (int) inferinfo / nblocks;
1725  j = inferinfo % nblocks;
1726  assert( 0 <= i && i < nspcons );
1727  assert( 0 <= j && j < nblocks );
1728 
1729  /* In rare cases it might happen that we fixed a variable to 1, but the node later becomes infeasible by globally
1730  * fixing variables to 0. In this case, it might happen that we find a SC with value 0 instead of 1. We then
1731  * cannot use this SC to repropagate (and do not know how to reconstruct the original reasoning). */
1732  if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 )
1733  {
1734  SCIPdebugMsg(scip, " -> reason for x[%d][%d] = 1 was the following SC:\n", i, j);
1735 #ifdef SCIP_DEBUG
1736  (void) SCIPsnprintf(str, SCIP_MAXSTRLEN, "SC:");
1737 #endif
1738 
1739  p1 = i-1;
1740  p2 = j-1;
1741 #ifndef NDEBUG
1742  pos1 = -1;
1743  pos2 = -1;
1744 #endif
1745  do
1746  {
1747  assert( cases[p1][p2] != -1 );
1748  assert( p1 >= 0 && p1 < i );
1749  assert( p2 >= 0 && p2 < j );
1750 
1751  /* if case 1 */
1752  if ( cases[p1][p2] == 1 )
1753  --p2; /* decrease column */
1754  else
1755  {
1756  /* case 2 or 3: reason are formed by variables in SC fixed to 0 */
1757  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1758  if ( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 )
1759  {
1760  SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
1761  *result = SCIP_SUCCESS;
1762 
1763 #ifdef SCIP_DEBUG
1764  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
1765  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1766 #endif
1767  }
1768 #ifndef NDEBUG
1769  else
1770  {
1771  assert( SCIPgetVarLbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
1772  assert( pos1 == -1 && pos2 == -1 );
1773  pos1 = p1;
1774  pos2 = p2;
1775  }
1776 #endif
1777  if ( cases[p1][p2] == 3 )
1778  break;
1779  }
1780  --p1; /* decrease row */
1781  }
1782  while ( p1 >= 0 ); /* should always be true, i.e., the break should end the loop */
1783  assert( cases[p1][p2] == 3 );
1784  assert( pos1 >= 0 && pos2 >= 0 );
1785 
1786  /* distinguish partitioning/packing */
1787  if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1788  {
1789  /* partitioning case */
1790 #ifdef SCIP_DEBUG
1791  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " before bar: ");
1792  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1793 #endif
1794  /* add variables before the bar in the partitioning case */
1795  for (k = 0; k < j; ++k)
1796  {
1797  assert( SCIPgetVarUbAtIndex(scip, vars[i][k], bdchgidx, FALSE) < 0.5 );
1798  SCIP_CALL( SCIPaddConflictUb(scip, vars[i][k], bdchgidx) );
1799  *result = SCIP_SUCCESS;
1800 #ifdef SCIP_DEBUG
1801  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", i, k);
1802  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1803 #endif
1804  }
1805 
1806 #ifdef SCIP_DEBUG
1807  SCIPdebugMsg(scip, "%s\n", str);
1808 #endif
1809  }
1810  else
1811  {
1812  /* packing case */
1813  int lastcolumn;
1814 
1815  /* last column considered as part of the bar: */
1816  lastcolumn = nblocks - 1;
1817  if ( lastcolumn > i )
1818  lastcolumn = i;
1819 
1820  /* search for variable in the bar that is fixed to 1 in the packing case */
1821  for (k = j; k <= lastcolumn; ++k)
1822  {
1823  if ( SCIPgetVarLbAtIndex(scip, vars[i][k], bdchgidx, FALSE) > 0.5 )
1824  {
1825  SCIP_CALL( SCIPaddConflictLb(scip, vars[i][k], bdchgidx) );
1826  *result = SCIP_SUCCESS;
1827  SCIPdebugMsg(scip, " and variable x[%d][%d] fixed to 1.\n", i, k);
1828  break;
1829  }
1830  }
1831  }
1832  }
1833  }
1834 
1835  return SCIP_OKAY;
1836 }
1837 
1838 
1839 /** Propagation conflict resolving method of propagator for full orbitope constraints */
1840 static
1842  SCIP* scip, /**< SCIP data structure */
1843  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1844  SCIP_VAR* infervar, /**< variable that was deduced */
1845  int inferinfo, /**< inference information */
1846  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
1847  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1848  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1849  )
1850 { /*lint --e{715}*/
1851  SCIP_CONSDATA* consdata;
1852  SCIP_VAR*** vars;
1853  int ncols;
1854  int inferrow;
1855  int infercol;
1856  int i;
1857  int j;
1858  int k;
1859 
1860  assert( scip != NULL );
1861  assert( cons != NULL );
1862  assert( infervar != NULL );
1863  assert( bdchgidx != NULL );
1864  assert( result != NULL );
1865 
1866  *result = SCIP_DIDNOTFIND;
1867 
1868  consdata = SCIPconsGetData(cons);
1869  assert( consdata != NULL );
1870  assert( consdata->nspcons > 0 );
1871  assert( consdata->nblocks > 0 );
1872 
1873  vars = consdata->vars;
1874  ncols = consdata->nblocks;
1875 
1876  infercol = inferinfo % ncols;
1877  inferrow = (int) inferinfo / ncols;
1878 
1879  assert( inferrow < consdata->nspcons );
1880 
1881  /* reason for 1-fixing */
1882  if ( SCIPvarGetLbAtIndex(infervar, bdchgidx, FALSE) < 0.5 && SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE) > 0.5 )
1883  {
1884  SCIPdebugMsg(scip, " -> reason for fixing variable with index %d to 1 was the fixing of the upperleft %dx%d-matrix and x[%d][%d] = 1.\n",
1885  SCIPvarGetIndex(infervar), inferrow - 1, infercol, inferrow, infercol);
1886 
1887  for (i = 0; i < inferrow; ++i)
1888  {
1889  for (j = 0; j <= infercol; ++j)
1890  {
1891  SCIP_CALL( SCIPaddConflictLb(scip, vars[i][j], bdchgidx) );
1892  SCIP_CALL( SCIPaddConflictUb(scip, vars[i][j], bdchgidx) );
1893  }
1894  }
1895  SCIP_CALL( SCIPaddConflictLb(scip, vars[inferrow][infercol], bdchgidx) );
1896 
1897  *result = SCIP_SUCCESS;
1898 
1899  return SCIP_OKAY;
1900  }
1901  else if ( SCIPvarGetUbAtIndex(infervar, bdchgidx, FALSE) > 0.5 && SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < 0.5 )
1902  {
1903  /* find position of infervar in vars matrix (it has to be contained in inferrow behind infercol)*/
1904  for (k = infercol + 1; k < ncols; ++k)
1905  {
1906  if ( SCIPvarGetIndex(infervar) == SCIPvarGetIndex(vars[inferrow][k]) )
1907  {
1908  SCIPdebugMsg(scip, " -> reason for fixing variable with index %d to 0 was the fixing of the upper left %dx%d-matrix and x[%d][%d] = 0.\n",
1909  SCIPvarGetIndex(infervar), inferrow - 1, k, inferrow, infercol);
1910 
1911  for (i = 0; i < inferrow; ++i)
1912  {
1913  for (j = 0; j <= k; ++j)
1914  {
1915  SCIP_CALL( SCIPaddConflictLb(scip, vars[i][j], bdchgidx) );
1916  SCIP_CALL( SCIPaddConflictUb(scip, vars[i][j], bdchgidx) );
1917  }
1918  }
1919  SCIP_CALL( SCIPaddConflictUb(scip, vars[inferrow][infercol], bdchgidx) );
1920 
1921  *result = SCIP_SUCCESS;
1922 
1923  return SCIP_OKAY;
1924  }
1925  }
1926  assert( *result == SCIP_SUCCESS );
1927  }
1928 
1929  return SCIP_OKAY;
1930 }
1931 
1932 
1933 /** check packing/partitioning orbitope solution for feasibility */
1934 static
1936  SCIP* scip, /**< SCIP data structure */
1937  SCIP_CONS* cons, /**< pointer to orbitope constraint */
1938  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
1939  )
1940 {
1941  SCIP_CONSDATA* consdata;
1942  SCIP_Real** weights;
1943  SCIP_Real** vals;
1944  int** cases;
1945  int nspcons;
1946  int nblocks;
1947  int i;
1948  int j;
1949 
1950  assert( cons != NULL );
1951 
1952  consdata = SCIPconsGetData(cons);
1953 
1954  assert( scip != NULL );
1955  assert( consdata != NULL );
1956  assert( consdata->nspcons > 0 );
1957  assert( consdata->nblocks > 0 );
1958  assert( consdata->vals != NULL );
1959  assert( consdata->weights != NULL );
1960  assert( consdata->cases != NULL );
1961 
1962  /* check for upper right triangle */
1963  if ( ! consdata->istrianglefixed )
1964  {
1965  SCIP_Bool infeasible = FALSE;
1966  int nfixedvars = 0;
1967 
1968  SCIP_CALL( fixTriangle(scip, cons, &infeasible, &nfixedvars) );
1969  if ( infeasible )
1970  {
1971  *result = SCIP_CUTOFF;
1972  return SCIP_OKAY;
1973  }
1974  if ( nfixedvars > 0 )
1975  {
1976  *result = SCIP_REDUCEDDOM;
1977  return SCIP_OKAY;
1978  }
1979  }
1980 
1981  nspcons = consdata->nspcons;
1982  nblocks = consdata->nblocks;
1983  vals = consdata->vals;
1984  weights = consdata->weights;
1985  cases = consdata->cases;
1986 
1987  /* get solution */
1988  copyValues(scip, consdata, NULL);
1989  SCIPdebugMsg(scip, "Enforcing (pseudo solutions) for orbitope constraint <%s>\n", SCIPconsGetName(cons));
1990 
1991  /* compute table */
1992  assert( consdata->istrianglefixed );
1993  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
1994 
1995  /* loop through rows */
1996  for (i = 1; i < nspcons; ++i)
1997  {
1998  SCIP_Real bar = 0.0;
1999  int lastcolumn;
2000 
2001  lastcolumn = nblocks - 1;
2002 
2003  /* last column considered as part of the bar: */
2004  if ( lastcolumn > i )
2005  lastcolumn = i;
2006 
2007  /* traverse row from right to left */
2008  for (j = lastcolumn; j > 0; --j)
2009  {
2010  bar += vals[i][j];
2011  assert( SCIPisIntegral(scip, vals[i][j]) );
2012 
2013  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2014  if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2015  {
2016  SCIPdebugMsg(scip, "Solution is infeasible.\n");
2017  *result = SCIP_INFEASIBLE;
2018  return SCIP_OKAY;
2019  }
2020  }
2021  }
2022 
2023  return SCIP_OKAY;
2024 }
2025 
2026 
2027 /** check packing/partitioning orbitope solution for feasibility */
2028 static
2030  SCIP* scip, /**< SCIP data structure */
2031  SCIP_CONS* cons, /**< pointer to orbitope constraint */
2032  SCIP_SOL* sol, /**< solution to be checked */
2033  SCIP_RESULT* result, /**< pointer to store the result of the enforcing call */
2034  SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
2035  )
2036 {
2037  SCIP_CONSDATA* consdata;
2038  SCIP_VAR*** vars;
2039  SCIP_Real** vals;
2040  SCIP_Real** weights;
2041  int** cases;
2042  int nspcons;
2043  int nblocks;
2044  int i;
2045  int j;
2046 
2047  /* get data of constraint */
2048  assert( cons != 0 );
2049  consdata = SCIPconsGetData(cons);
2050 
2051  assert( consdata != NULL );
2052  assert( consdata->nspcons > 0 );
2053  assert( consdata->nblocks > 0 );
2054  assert( consdata->vars != NULL );
2055  assert( consdata->vals != NULL );
2056  assert( consdata->weights != NULL );
2057  assert( consdata->cases != NULL );
2058 
2059  nspcons = consdata->nspcons;
2060  nblocks = consdata->nblocks;
2061  vars = consdata->vars;
2062  vals = consdata->vals;
2063  weights = consdata->weights;
2064  cases = consdata->cases;
2065 
2066  /* get solution */
2067  copyValues(scip, consdata, sol);
2068  SCIPdebugMsg(scip, "Checking orbitope constraint <%s> ...\n", SCIPconsGetName(cons));
2069 
2070  /* check upper right triangle (if not yet fixed to zero or in debug mode */
2071 #ifdef NDEBUG
2072  if ( ! consdata->istrianglefixed )
2073 #endif
2074  {
2075  int diagsize;
2076 
2077  /* get last row of triangle */
2078  diagsize = nblocks;
2079  if ( nspcons < nblocks )
2080  diagsize = nspcons;
2081 
2082  /* check variables */
2083  for (i = 0; i < diagsize; ++i)
2084  {
2085  for (j = i+1; j < nblocks; ++j)
2086  {
2087  if ( ! SCIPisFeasZero(scip, vals[i][j]) )
2088  {
2089  if ( printreason )
2090  SCIPinfoMessage(scip, NULL, "variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]);
2091  *result = SCIP_INFEASIBLE;
2092  }
2093  }
2094  }
2095  }
2096 
2097  /* compute table */
2098  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2099 
2100  /* loop through rows */
2101  for (i = 1; i < nspcons; ++i)
2102  {
2103  SCIP_Real bar;
2104  int lastcolumn;
2105 
2106  lastcolumn = nblocks - 1;
2107  bar = 0.0;
2108  /* last column considered as part of the bar: */
2109  if ( lastcolumn > i )
2110  lastcolumn = i;
2111 
2112  /* traverse row from right to left */
2113  for (j = lastcolumn; j > 0; --j)
2114  {
2115  bar += vals[i][j];
2116  assert( SCIPisFeasIntegral(scip, vals[i][j]) );
2117 
2118  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2119  if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2120  {
2121  SCIPdebugMsg(scip, "Solution is infeasible.\n");
2122  *result = SCIP_INFEASIBLE;
2123 
2124  if ( printreason )
2125  {
2126  int l;
2127  int p1;
2128  int p2;
2129 
2130  SCIPinfoMessage(scip, NULL, "violated SCI: bar(");
2131 
2132  /* first output bar */
2133  for (l = j; l < nblocks; ++l)
2134  SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[i][l]), consdata->vals[i][l]);
2135 
2136  SCIPinfoMessage(scip, NULL, ") SC(");
2137 
2138  /* output shifted column */
2139  p1 = i-1;
2140  p2 = j-1;
2141  do
2142  {
2143  assert( cases[p1][p2] != -1 );
2144  assert( p1 >= 0 && p1 < i );
2145  assert( p2 >= 0 && p2 < j );
2146 
2147  /* if case 1 */
2148  if (cases[p1][p2] == 1)
2149  --p2; /* decrease column */
2150  else
2151  {
2152  /* case 2 or 3: */
2153  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2154  SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[p1][p2]), consdata->vals[p1][p2]);
2155  if ( cases[p1][p2] == 3 )
2156  break;
2157  }
2158  --p1; /* decrease row */
2159  }
2160  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
2161  assert( cases[p1][p2] == 3 );
2162 
2163  SCIPinfoMessage(scip, NULL, ")");
2164  }
2165  }
2166  }
2167  }
2168 
2169  return SCIP_OKAY;
2170 }
2171 
2172 
2173 /** check full orbitope solution for feasibility */
2174 static
2176  SCIP* scip, /**< SCIP data structure */
2177  SCIP_CONS* cons, /**< constraint to process */
2178  SCIP_SOL* sol, /**< solution to be checked */
2179  SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */
2180  SCIP_Bool* feasible /**< memory address to store whether solution is feasible */
2181  )
2182 {
2183  SCIP_CONSDATA* consdata;
2184  SCIP_VAR*** vars;
2185  SCIP_VAR** vars1;
2186  SCIP_VAR** vars2;
2187  int nrows;
2188  int ncols;
2189  int j;
2190  int i;
2191 
2192  assert( scip != NULL );
2193  assert( cons != NULL );
2194  assert( feasible != NULL );
2195 
2196  consdata = SCIPconsGetData(cons);
2197 
2198  assert( consdata != NULL );
2199  assert( consdata->vars != NULL );
2200  assert( consdata->nspcons > 0 );
2201  assert( consdata->nblocks > 0 );
2202 
2203  vars = consdata->vars;
2204  nrows = consdata->nspcons;
2205  ncols = consdata->nblocks;
2206 
2207  SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) );
2208  SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) );
2209 
2210  /* iterate over adjacent columns of orbitope and check whether the first column in this
2211  * column pair is lexicographically not smaller than the second column in the pair */
2212  *feasible = TRUE;
2213  for (j = 1; j < ncols && *feasible; ++j)
2214  {
2215  for (i = 0; i < nrows; ++i)
2216  {
2217  vars1[i] = vars[i][j - 1];
2218  vars2[i] = vars[i][j];
2219  }
2220 
2221  SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, vars1, vars2, nrows, printreason, feasible) );
2222  }
2223 
2224  SCIPfreeBufferArray(scip, &vars2);
2225  SCIPfreeBufferArray(scip, &vars1);
2226 
2227  return SCIP_OKAY;
2228 }
2229 
2230 
2231 /** separate or enforce constraints */
2232 static
2234  SCIP* scip, /**< SCIP data structure */
2235  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2236  SCIP_CONS** conss, /**< constraints to process */
2237  int nconss, /**< number of constraints */
2238  int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
2239  SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */
2240  SCIP_RESULT* result /**< pointer to store the result (should be initialized) */
2241  )
2242 {
2243  SCIP_Bool infeasible = FALSE;
2244  int nfixedvars = 0;
2245  int ncuts = 0;
2246  int c;
2247 
2248  assert( scip != NULL );
2249  assert( conshdlr != NULL );
2250  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2251  assert( result != NULL );
2252 
2253  /* loop through constraints */
2254  for (c = 0; c < nconss && ! infeasible; c++)
2255  {
2256  SCIP_CONSHDLRDATA* conshdlrdata;
2257  SCIP_CONSDATA* consdata;
2258  int nconsfixedvars = 0;
2259  int nconscuts = 0;
2260  SCIP_ORBITOPETYPE orbitopetype;
2261  SCIP_VAR*** vars;
2262  SCIP_VAR** vars1;
2263  SCIP_VAR** vars2;
2264  int nrows;
2265  int i;
2266  int j;
2267 
2268  assert( conss[c] != NULL );
2269 
2270  /* get data of constraint */
2271  consdata = SCIPconsGetData(conss[c]);
2272  assert( consdata != NULL );
2273 
2274  /* get solution */
2275  copyValues(scip, consdata, sol);
2276 
2277  /* separate */
2278  orbitopetype = consdata->orbitopetype;
2279 
2280  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2281  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2282  {
2283  SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
2284  }
2285  else if ( conshdlrdata->sepafullorbitope )
2286  {
2287  assert( consdata->nspcons > 0 );
2288  assert( consdata->vars != NULL );
2289 
2290  nrows = consdata->nspcons;
2291  vars = consdata->vars;
2292 
2293  SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) );
2294  SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) );
2295 
2296  /* iterate over adjacent columns of orbitope and separate inequalities for the corresponding orbisacks */
2297  for (j = 1; j < consdata->nblocks && ! infeasible; ++j)
2298  {
2299  for (i = 0; i < nrows; ++i)
2300  {
2301  vars1[i] = vars[i][j - 1];
2302  vars2[i] = vars[i][j];
2303  }
2304 
2305  SCIP_CALL( SCIPseparateCoversOrbisack(scip, conss[c], sol, vars1, vars2, nrows, &infeasible, &nconscuts) );
2306  }
2307 
2308  SCIPfreeBufferArray(scip, &vars2);
2309  SCIPfreeBufferArray(scip, &vars1);
2310  }
2311  nfixedvars += nconsfixedvars;
2312  ncuts += nconscuts;
2313 
2314  /* stop after the useful constraints if we found cuts of fixed variables */
2315  if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
2316  break;
2317  }
2318 
2319  if ( infeasible )
2320  {
2321  SCIPdebugMsg(scip, "Infeasible node.\n");
2322  *result = SCIP_CUTOFF;
2323  }
2324  else if ( nfixedvars > 0 )
2325  {
2326  SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars);
2327  *result = SCIP_REDUCEDDOM;
2328  }
2329  else if ( ncuts > 0 )
2330  {
2331  SCIPdebugMsg(scip, "Separated %d SCIs.\n", ncuts);
2332  *result = SCIP_SEPARATED;
2333  }
2334  else
2335  {
2336  SCIPdebugMsg(scip, "No violated inequality found during separation.\n");
2337  }
2338 
2339  return SCIP_OKAY;
2340 }
2341 
2342 /*
2343  * Callback methods of constraint handler
2344  */
2345 
2346 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2347 static
2348 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
2349 { /*lint --e{715}*/
2350  assert(scip != NULL);
2351  assert(conshdlr != NULL);
2352  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2353 
2354  /* call inclusion method of constraint handler */
2356 
2357  *valid = TRUE;
2358 
2359  return SCIP_OKAY;
2360 }
2361 
2362 /** frees constraint handler */
2363 static
2364 SCIP_DECL_CONSFREE(consFreeOrbitope)
2365 { /*lint --e{715}*/
2366  SCIP_CONSHDLRDATA* conshdlrdata;
2367 
2368  assert( scip != 0 );
2369  assert( conshdlr != 0 );
2370  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2371 
2372  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2373  assert( conshdlrdata != NULL );
2374 
2375  SCIPfreeBlockMemory(scip, &conshdlrdata);
2376 
2377  return SCIP_OKAY;
2378 }
2379 
2380 /** frees specific constraint data */
2381 static
2382 SCIP_DECL_CONSDELETE(consDeleteOrbitope)
2383 { /*lint --e{715}*/
2384  assert(conshdlr != NULL);
2385  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2386 
2387  SCIP_CALL( consdataFree(scip, consdata) );
2388 
2389  return SCIP_OKAY;
2390 }
2391 
2392 /** transforms constraint data into data belonging to the transformed problem */
2393 static
2394 SCIP_DECL_CONSTRANS(consTransOrbitope)
2395 { /*lint --e{715}*/
2396  SCIP_CONSDATA* sourcedata;
2397  SCIP_CONSDATA* targetdata;
2398 
2399  assert(conshdlr != NULL);
2400  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2401  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
2402  assert(sourcecons != NULL);
2403  assert(targetcons != NULL);
2404 
2405  sourcedata = SCIPconsGetData(sourcecons);
2406  assert(sourcedata != NULL);
2407 
2408  /* create linear constraint data for target constraint */
2409  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nspcons, sourcedata->nblocks,
2410  sourcedata->orbitopetype, sourcedata->resolveprop) );
2411 
2412  /* create target constraint */
2413  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2414  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2415  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2416  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2417  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2418 
2419  return SCIP_OKAY;
2420 }
2421 
2422 /** separation method of constraint handler for LP solutions */
2423 static
2424 SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
2425 { /*lint --e{715}*/
2426  assert( scip != NULL );
2427  assert( result != NULL );
2428 
2429  SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2430 
2431  *result = SCIP_DIDNOTRUN;
2432 
2433  /* if solution is integer, skip separation */
2434  if ( SCIPgetNLPBranchCands(scip) <= 0 )
2435  return SCIP_OKAY;
2436 
2437  *result = SCIP_DIDNOTFIND;
2438 
2439  /* separate constraints */
2440  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
2441 
2442  return SCIP_OKAY;
2443 }
2444 
2445 /** separation method of constraint handler for arbitrary primal solutions */
2446 static
2447 SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
2448 { /*lint --e{715}*/
2449  assert( scip != NULL );
2450  assert( result != NULL );
2451 
2452  SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for primal solution.\n", SCIPconshdlrGetName(conshdlr));
2453 
2454  *result = SCIP_DIDNOTFIND;
2455 
2456  /* separate constraints */
2457  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
2458 
2459  return SCIP_OKAY;
2460 }
2461 
2462 
2463 /** constraint enforcing method of constraint handler for LP solutions */
2464 static
2465 SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
2466 { /*lint --e{715}*/
2467  assert( scip != NULL );
2468  assert( result != NULL );
2469 
2470  /* we have a negative priority, so we should come after the integrality conshdlr */
2471  assert( SCIPgetNLPBranchCands(scip) == 0 );
2472 
2473  SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2474 
2475  *result = SCIP_FEASIBLE;
2476 
2477  /* separate constraints */
2478  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
2479 
2480  return SCIP_OKAY;
2481 }
2482 
2483 
2484 /** constraint enforcing method of constraint handler for relaxation solutions */
2485 static
2486 SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
2487 { /*lint --e{715}*/
2488  assert( result != NULL );
2489  assert( scip != NULL );
2490 
2491  SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for relaxation solution.\n", SCIPconshdlrGetName(conshdlr));
2492 
2493  *result = SCIP_FEASIBLE;
2494 
2495  /* separate constraints */
2496  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
2497 
2498  return SCIP_OKAY;
2499 }
2500 
2501 
2502 /** constraint enforcing method of constraint handler for pseudo solutions */
2503 static
2504 SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
2505 { /*lint --e{715}*/
2506  int c;
2507 
2508  assert( scip != NULL );
2509  assert( conshdlr != NULL );
2510  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2511  assert( result != NULL );
2512 
2513  *result = SCIP_FEASIBLE;
2514  if ( objinfeasible || solinfeasible )
2515  return SCIP_OKAY;
2516 
2517  /* loop through constraints */
2518  for (c = 0; c < nconss; ++c)
2519  {
2520  SCIP_CONS* cons;
2521  SCIP_CONSDATA* consdata;
2522  SCIP_ORBITOPETYPE orbitopetype;
2523  SCIP_Bool feasible;
2524 
2525  /* get data of constraint */
2526  cons = conss[c];
2527  assert( cons != 0 );
2528  consdata = SCIPconsGetData(cons);
2529 
2530  assert( consdata != NULL );
2531 
2532  orbitopetype = consdata->orbitopetype;
2533 
2534  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2535  {
2537  }
2538  else
2539  {
2540  SCIP_CALL( checkFullOrbitopeSolution(scip, cons, NULL, FALSE, &feasible) );
2541 
2542  if ( ! feasible )
2543  *result = SCIP_INFEASIBLE;
2544  }
2545 
2546  if ( *result == SCIP_INFEASIBLE )
2547  break;
2548  }
2549 
2550  return SCIP_OKAY;
2551 }
2552 
2553 
2554 /** feasibility check method of constraint handler for integral solutions */
2555 static
2556 SCIP_DECL_CONSCHECK(consCheckOrbitope)
2557 { /*lint --e{715}*/
2558  int c;
2559  SCIP_CONSHDLRDATA* conshdlrdata;
2560  SCIP_CONSDATA* consdata;
2561  SCIP_ORBITOPETYPE orbitopetype;
2562  SCIP_Bool feasible;
2563 
2564  assert( scip != NULL );
2565  assert( conshdlr != NULL );
2566  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2567  assert( result != NULL );
2568 
2569  *result = SCIP_FEASIBLE;
2570 
2571  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2572  assert( conshdlrdata != NULL );
2573 
2574  if ( conshdlrdata->checkalwaysfeas )
2575  return SCIP_OKAY;
2576 
2577  /* loop through constraints */
2578  for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
2579  {
2580  assert( conss[c] != 0 );
2581  consdata = SCIPconsGetData(conss[c]);
2582 
2583  assert( consdata != NULL );
2584 
2585  orbitopetype = consdata->orbitopetype;
2586 
2587  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2588  {
2589  SCIP_CALL( checkPackingPartitioningOrbitopeSolution(scip, conss[c], sol, result, printreason) );
2590  }
2591  else
2592  {
2593  SCIP_CALL( checkFullOrbitopeSolution(scip, conss[c], sol, printreason, &feasible) );
2594 
2595  if ( ! feasible )
2596  *result = SCIP_INFEASIBLE;
2597  }
2598  }
2599  SCIPdebugMsg(scip, "Solution is feasible.\n");
2600 
2601  return SCIP_OKAY;
2602 }
2603 
2604 
2605 /** domain propagation method of constraint handler */
2606 static
2607 SCIP_DECL_CONSPROP(consPropOrbitope)
2608 { /*lint --e{715}*/
2609  SCIP_Bool infeasible = FALSE;
2610  int nfixedvars = 0;
2611  int c;
2612 
2613  assert( scip != NULL );
2614  assert( conshdlr != NULL );
2615  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2616  assert( result != NULL );
2617 
2618  *result = SCIP_DIDNOTRUN;
2619 
2620  /* propagate all useful constraints */
2621  for (c = 0; c < nusefulconss && !infeasible; ++c)
2622  {
2623  assert( conss[c] != 0 );
2624 
2625  SCIPdebugMsg(scip, "Propagation of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2626 
2627  SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixedvars) );
2628  }
2629 
2630  /* return the correct result */
2631  if ( infeasible )
2632  {
2633  *result = SCIP_CUTOFF;
2634  SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n");
2635  }
2636  else if ( nfixedvars > 0 )
2637  {
2638  *result = SCIP_REDUCEDDOM;
2639  SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars);
2640  }
2641  else if ( nusefulconss > 0 )
2642  {
2643  *result = SCIP_DIDNOTFIND;
2644  SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n");
2645  }
2646 
2647  return SCIP_OKAY;
2648 }
2649 
2650 
2651 /** presolving method of constraint handler */
2652 static
2653 SCIP_DECL_CONSPRESOL(consPresolOrbitope)
2654 { /*lint --e{715}*/
2655  SCIP_Bool infeasible = FALSE;
2656  int noldfixedvars;
2657  int c;
2658 
2659  assert( scip != NULL );
2660  assert( conshdlr != NULL );
2661  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2662  assert( result != NULL );
2663 
2664  *result = SCIP_DIDNOTRUN;
2665  noldfixedvars = *nfixedvars;
2666 
2667  /* propagate all useful constraints */
2668  for (c = 0; c < nconss && !infeasible; ++c)
2669  {
2670  int nfixed = 0;
2671 
2672  assert( conss[c] != 0 );
2673 
2674  SCIPdebugMsg(scip, "Presolving of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2675 
2676  SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
2677  *nfixedvars += nfixed;
2678  }
2679 
2680  if ( infeasible )
2681  {
2682  *result = SCIP_CUTOFF;
2683  SCIPdebugMsg(scip, "Presolving detected infeasibility.\n");
2684  }
2685  else if ( *nfixedvars > noldfixedvars )
2686  {
2687  *result = SCIP_SUCCESS;
2688  }
2689  else if ( nconss > 0 )
2690  {
2691  *result = SCIP_DIDNOTFIND;
2692  SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n");
2693  }
2694 
2695  return SCIP_OKAY;
2696 }
2697 
2698 
2699 /** propagation conflict resolving method of constraint handler */
2700 static
2701 SCIP_DECL_CONSRESPROP(consRespropOrbitope)
2702 { /*lint --e{715}*/
2703  SCIP_CONSDATA* consdata;
2704  SCIP_ORBITOPETYPE orbitopetype;
2705 
2706  assert( scip != NULL );
2707  assert( cons != NULL );
2708  assert( infervar != NULL );
2709  assert( bdchgidx != NULL );
2710  assert( result != NULL );
2711 
2712  consdata = SCIPconsGetData(cons);
2713  assert( consdata != NULL );
2714 
2715  orbitopetype = consdata->orbitopetype;
2716 
2717  /* resolution for full orbitopes not availabe yet */
2718  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2719  {
2720  SCIP_CALL( resolvePropagation(scip, cons, infervar, inferinfo, boundtype, bdchgidx, result) );
2721  }
2722  else
2723  {
2724  SCIP_CALL( resolvePropagationFullOrbitopes(scip, cons, infervar, inferinfo, boundtype, bdchgidx, result) );
2725  }
2726 
2727  return SCIP_OKAY;
2728 }
2729 
2730 
2731 /** variable rounding lock method of constraint handler */
2732 static
2733 SCIP_DECL_CONSLOCK(consLockOrbitope)
2734 { /*lint --e{715}*/
2735  SCIP_CONSDATA* consdata;
2736  SCIP_VAR*** vars;
2737  int i;
2738  int j;
2739  int nspcons;
2740  int nblocks;
2741 
2742  assert( scip != NULL );
2743  assert( conshdlr != NULL );
2744  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2745  assert( cons != NULL );
2746 
2747  consdata = SCIPconsGetData(cons);
2748  assert( consdata != NULL );
2749  assert( consdata->nspcons > 0 );
2750  assert( consdata->nblocks > 0 );
2751  assert( consdata->vars != NULL );
2752 
2753  SCIPdebugMsg(scip, "Locking method for orbitope constraint handler\n");
2754 
2755  nspcons = consdata->nspcons;
2756  nblocks = consdata->nblocks;
2757  vars = consdata->vars;
2758 
2759  /* add up locks and down locks on each variable */
2760  for (i = 0; i < nspcons; ++i)
2761  {
2762  for (j = 0; j < nblocks; ++j)
2763  SCIP_CALL( SCIPaddVarLocks(scip, vars[i][j], nlockspos + nlocksneg, nlockspos + nlocksneg) );
2764  }
2765 
2766  return SCIP_OKAY;
2767 }
2768 
2769 
2770 /** constraint display method of constraint handler */
2771 static
2772 SCIP_DECL_CONSPRINT(consPrintOrbitope)
2774  SCIP_CONSDATA* consdata;
2775  SCIP_VAR*** vars;
2776  int i;
2777  int j;
2778  int nspcons;
2779  int nblocks;
2780  SCIP_ORBITOPETYPE orbitopetype;
2781 
2782  assert( scip != NULL );
2783  assert( conshdlr != NULL );
2784  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2785  assert( cons != NULL );
2786 
2787  consdata = SCIPconsGetData(cons);
2788  assert( consdata != NULL );
2789  assert( consdata->nspcons > 0 );
2790  assert( consdata->nblocks > 0 );
2791  assert( consdata->vars != NULL );
2792 
2793  nspcons = consdata->nspcons;
2794  nblocks = consdata->nblocks;
2795  vars = consdata->vars;
2796  orbitopetype = consdata->orbitopetype;
2797 
2798  SCIPdebugMsg(scip, "Printing method for orbitope constraint handler\n");
2799 
2800  switch ( orbitopetype )
2801  {
2803  SCIPinfoMessage(scip, file, "partOrbitope(");
2804  break;
2806  SCIPinfoMessage(scip, file, "packOrbitope(");
2807  break;
2809  SCIPinfoMessage(scip, file, "fullOrbitope(");
2810  break;
2811  default:
2812  SCIPABORT();
2813  }
2814 
2815  for (i = 0; i < nspcons; ++i)
2816  {
2817  for (j = 0; j < nblocks; ++j)
2818  {
2819  if ( j > 0 )
2820  SCIPinfoMessage(scip, file, ",");
2821  SCIPinfoMessage(scip, file, "%s", SCIPvarGetName(vars[i][j]));
2822  }
2823  if ( i < nspcons-1 )
2824  SCIPinfoMessage(scip, file, ".");
2825  }
2826  SCIPinfoMessage(scip, file, ")");
2827 
2828  return SCIP_OKAY;
2829 }
2830 
2831 
2832 /** constraint copying method of constraint handler */
2833 static
2834 SCIP_DECL_CONSCOPY(consCopyOrbitope)
2836  SCIP_CONSDATA* sourcedata;
2837  SCIP_VAR*** sourcevars;
2838  SCIP_VAR*** vars;
2839  int nspcons;
2840  int nblocks;
2841  int i;
2842  int k;
2843  int j;
2844 
2845  assert( scip != NULL );
2846  assert( cons != NULL );
2847  assert( sourcescip != NULL );
2848  assert( sourceconshdlr != NULL );
2849  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
2850  assert( sourcecons != NULL );
2851  assert( varmap != NULL );
2852  assert( valid != NULL );
2853 
2854  *valid = TRUE;
2855 
2856  SCIPdebugMsg(scip, "Copying method for orbitope constraint handler.\n");
2857 
2858  sourcedata = SCIPconsGetData(sourcecons);
2859  assert( sourcedata != NULL );
2860  assert( sourcedata->nspcons > 0 );
2861  assert( sourcedata->nblocks > 0 );
2862  assert( sourcedata->vars != NULL );
2863 
2864  nspcons = sourcedata->nspcons;
2865  nblocks = sourcedata->nblocks;
2866  sourcevars = sourcedata->vars;
2867 
2868  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nspcons) );
2869  for (i = 0; i < nspcons && *valid; ++i)
2870  {
2871  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), nblocks) ); /*lint !e866*/
2872 
2873  for (j = 0; j < nblocks && *valid; ++j)
2874  {
2875  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
2876  assert( !(*valid) || vars[i][j] != NULL );
2877  }
2878  }
2879 
2880  /* only create the target constraint, if all variables could be copied */
2881  if ( *valid )
2882  {
2883  /* create copied constraint */
2884  if ( name == NULL )
2885  name = SCIPconsGetName(sourcecons);
2886 
2887  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name,
2888  vars, sourcedata->orbitopetype, nspcons, nblocks, sourcedata->resolveprop,
2889  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2890  }
2891 
2892  /* free space; only up to row i if copying failed */
2893  assert( 0 <= i && i <= nspcons );
2894  for (k = 0; k < i; ++k)
2895  SCIPfreeBufferArray(scip, &vars[k]);
2896  SCIPfreeBufferArray(scip, &vars);
2897 
2898  return SCIP_OKAY;
2899 }
2900 
2901 
2902 /** constraint parsing method of constraint handler */
2903 static
2904 SCIP_DECL_CONSPARSE(consParseOrbitope)
2905 { /*lint --e{715}*/
2906  const char* s;
2907  SCIP_ORBITOPETYPE orbitopetype;
2908  char varname[SCIP_MAXSTRLEN];
2909  SCIP_VAR*** vars;
2910  SCIP_VAR* var;
2911  int nspcons;
2912  int maxnspcons;
2913  int nblocks;
2914  int maxnblocks;
2915  int k;
2916  int j;
2917 
2918  assert( success != NULL );
2919 
2920  *success = TRUE;
2921  s = str;
2922 
2923  /* skip white space */
2924  while ( *s != '\0' && isspace((unsigned char)*s) )
2925  ++s;
2926 
2927  if ( strncmp(s, "partOrbitope(", 13) == 0 )
2928  orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
2929  else if ( strncmp(s, "packOrbitope(", 13) == 0 )
2930  orbitopetype = SCIP_ORBITOPETYPE_PACKING;
2931  else
2932  {
2933  if ( strncmp(s, "fullOrbitope(", 13) != 0 )
2934  {
2935  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error - expected \"fullOrbitope(\", \"partOrbitope\" or \"packOrbitope\": %s\n", s);
2936  *success = FALSE;
2937  return SCIP_OKAY;
2938  }
2939  orbitopetype = SCIP_ORBITOPETYPE_FULL;
2940  }
2941  s += 13;
2942 
2943  /* loop through string */
2944  nspcons = 0;
2945  nblocks = 0;
2946  maxnspcons = 10;
2947  maxnblocks = 10;
2948 
2949  SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnspcons) );
2950  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[0]), maxnblocks) );
2951 
2952  j = 0;
2953  do
2954  {
2955  /* find variable name */
2956  k = 0;
2957  while ( *s != '\0' && ! isspace((unsigned char)*s) && *s != ',' && *s != '.' && *s != ')' )
2958  varname[k++] = *s++;
2959  varname[k] = '\0';
2960 
2961  /* get variable */
2962  var = SCIPfindVar(scip, varname);
2963  if ( var == NULL )
2964  {
2965  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "unknown variable <%s>\n", varname);
2966  *success = FALSE;
2967  return SCIP_OKAY;
2968  }
2969  vars[nspcons][j++] = var;
2970 
2971  if ( j > nblocks )
2972  {
2973  if ( nspcons > 0 )
2974  {
2975  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variables per row do not match.\n");
2976  *success = FALSE;
2977  return SCIP_OKAY;
2978  }
2979  nblocks = j;
2980 
2981  if ( nblocks > maxnblocks )
2982  {
2983  int newsize;
2984 
2985  newsize = SCIPcalcMemGrowSize(scip, nblocks);
2986  SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons]), newsize) ); /*lint !e866*/
2987  maxnblocks = newsize;
2988  }
2989  }
2990  assert( nblocks <= maxnblocks );
2991 
2992  /* skip white space and ',' */
2993  while ( *s != '\0' && ( isspace((unsigned char)*s) || *s == ',' ) )
2994  ++s;
2995 
2996  /* begin new row if required */
2997  if ( *s == '.' )
2998  {
2999  ++nspcons;
3000  ++s;
3001 
3002  if ( nspcons >= maxnspcons )
3003  {
3004  int newsize;
3005 
3006  newsize = SCIPcalcMemGrowSize(scip, nspcons+1);
3007  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, newsize) );
3008  maxnspcons = newsize;
3009  }
3010  assert(nspcons < maxnspcons);
3011 
3012  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nspcons]), nblocks) ); /*lint !e866*/
3013  j = 0;
3014  }
3015  }
3016  while ( *s != ')' );
3017  ++nspcons;
3018 
3019  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, TRUE,
3020  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3021 
3022  for (k = 0; k < nspcons; ++k)
3023  SCIPfreeBufferArray(scip, &vars[k]);
3024  SCIPfreeBufferArray(scip, &vars);
3025 
3026  return SCIP_OKAY;
3027 }
3028 
3029 
3030 /** constraint method of constraint handler which returns the variables (if possible) */
3031 static
3032 SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
3033 { /*lint --e{715}*/
3034  SCIP_CONSDATA* consdata;
3035 
3036  assert( cons != NULL );
3037  assert( success != NULL );
3038  assert( vars != NULL );
3039 
3040  consdata = SCIPconsGetData(cons);
3041  assert( consdata != NULL );
3042 
3043  if ( varssize < consdata->nblocks * consdata->nspcons )
3044  (*success) = FALSE;
3045  else
3046  {
3047  int cnt = 0;
3048  int i;
3049  int j;
3050 
3051  for (i = 0; i < consdata->nspcons; ++i)
3052  {
3053  for (j = 0; j < consdata->nblocks; ++j)
3054  vars[cnt++] = consdata->vars[i][j];
3055  }
3056  (*success) = TRUE;
3057  }
3058 
3059  return SCIP_OKAY;
3060 }
3061 
3062 
3063 /** constraint method of constraint handler which returns the number of variables (if possible) */
3064 static
3065 SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
3066 { /*lint --e{715}*/
3067  SCIP_CONSDATA* consdata;
3068 
3069  assert( cons != NULL );
3070 
3071  consdata = SCIPconsGetData(cons);
3072  assert( consdata != NULL );
3073 
3074  (*nvars) = consdata->nblocks * consdata->nspcons;
3075  (*success) = TRUE;
3076 
3077  return SCIP_OKAY;
3078 }
3079 
3080 
3081 /*
3082  * constraint specific interface methods
3083  */
3084 
3085 /** creates the handler for orbitope constraints and includes it in SCIP */
3087  SCIP* scip /**< SCIP data structure */
3088  )
3089 {
3090  SCIP_CONSHDLRDATA* conshdlrdata;
3091  SCIP_CONSHDLR* conshdlr;
3092 
3093  /* create orbitope constraint handler data */
3094  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3095 
3096  /* include constraint handler */
3100  consEnfolpOrbitope, consEnfopsOrbitope, consCheckOrbitope, consLockOrbitope,
3101  conshdlrdata) );
3102  assert(conshdlr != NULL);
3103 
3104  /* set non-fundamental callbacks via specific setter functions */
3105  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitope, consCopyOrbitope) );
3106  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbitope) );
3107  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitope) );
3108  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitope) );
3109  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitope) );
3110  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitope) );
3111  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbitope, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3112  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitope) );
3113  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbitope, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3115  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitope) );
3116  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitope, consSepasolOrbitope, CONSHDLR_SEPAFREQ,
3118  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitope) );
3119  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitope) );
3120 
3121  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbitope",
3122  "Strengthen orbitope constraints to packing/partioning orbitopes?",
3123  &conshdlrdata->checkpporbitope, TRUE, DEFAULT_PPORBITOPE, NULL, NULL) );
3124 
3125  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/sepafullorbitope",
3126  "Whether we separate inequalities for full orbitopes?",
3127  &conshdlrdata->sepafullorbitope, TRUE, DEFAULT_SEPAFULLORBITOPE, NULL, NULL) );
3128 
3129  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkalwaysfeas",
3130  "Whether check routine returns always SCIP_FEASIBLE.",
3131  &conshdlrdata->checkalwaysfeas, TRUE, DEFAULT_CHECKALWAYSFEAS, NULL, NULL) );
3132 
3133  return SCIP_OKAY;
3134 }
3135 
3136 
3137 /** creates and captures a orbitope constraint
3138  *
3139  * @pre If packing/partitioning orbitopes are used, this constraint handler assumes that constraints which enforce
3140  * the packing/partitioning constraints are contained in the problem. It does not implement, e.g., separation and
3141  * propagation of set packing/partitioning constraints, since this would just copy large parts of the code of the
3142  * setppc constraint handler.
3143  *
3144  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3145  */
3147  SCIP* scip, /**< SCIP data structure */
3148  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3149  const char* name, /**< name of constraint */
3150  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
3151  SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
3152  int nspcons, /**< number of set partitioning/packing constraints <=> p */
3153  int nblocks, /**< number of symmetric variable blocks <=> q */
3154  SCIP_Bool resolveprop, /**< should propagation be resolved? */
3155  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3156  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3157  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3158  * Usually set to TRUE. */
3159  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3160  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3161  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3162  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3163  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3164  * Usually set to TRUE. */
3165  SCIP_Bool local, /**< is constraint only valid locally?
3166  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3167  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3168  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3169  * adds coefficients to this constraint. */
3170  SCIP_Bool dynamic, /**< is constraint subject to aging?
3171  * Usually set to FALSE. Set to TRUE for own cuts which
3172  * are separated as constraints. */
3173  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3174  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3175  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3176  * if it may be moved to a more global node?
3177  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3178  )
3179 {
3180  SCIP_CONSHDLRDATA* conshdlrdata;
3181  SCIP_CONSHDLR* conshdlr;
3182  SCIP_CONSDATA* consdata;
3183  SCIP_ORBITOPETYPE type;
3184 
3185  /* find the orbitope constraint handler */
3186  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3187  if ( conshdlr == NULL )
3188  {
3189  SCIPerrorMessage("orbitope constraint handler not found\n");
3190  return SCIP_PLUGINNOTFOUND;
3191  }
3192 
3193  assert( nspcons > 0 );
3194  assert( nblocks > 0 );
3195 
3196  /* run some checks */
3197 #ifndef NDEBUG
3198  {
3199  SCIP_Real obj;
3200  int i;
3201  int j;
3202  for (i = 0; i < nspcons; ++i)
3203  {
3204  /* initialize obj to infinity */
3205  obj = SCIPinfinity(scip);
3206  for (j = 0; j < nblocks; ++j)
3207  {
3208  SCIP_Bool fixedZero;
3209  SCIP_VAR* var;
3210 
3211  var = vars[i][j];
3212  assert(var != NULL);
3213 
3214  if ( SCIPvarIsNegated(var) )
3215  var = SCIPvarGetNegatedVar(var);
3216 
3217  /* all variables need to be binary */
3218  assert( SCIPvarIsBinary(var) );
3219 
3220  /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no
3221  problem (but we cannot always check it, e.g., when in the original problem
3222  variables were fixed and this problem was copied.) */
3223  fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) );
3224 
3225  /* @todo adapt correctness of the following check for sub-scips */
3226  if ( SCIPgetSubscipDepth(scip) == 0 )
3227  {
3228  /* check whether all variables in a row have the same objective */
3229  if ( ! fixedZero && SCIPisInfinity(scip, obj) )
3230  obj = SCIPvarGetObj(var);
3231  else
3232  {
3233  assert( fixedZero || ! SCIPvarIsActive(var) || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) );
3234  }
3235  }
3236  }
3237  }
3238  }
3239 #endif
3240 
3241  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3242  if ( conshdlrdata->checkpporbitope && orbitopetype != SCIP_ORBITOPETYPE_PARTITIONING
3243  && orbitopetype != SCIP_ORBITOPETYPE_PACKING )
3244  {
3245  type = SCIP_ORBITOPETYPE_FULL;
3246  SCIP_CALL( strenghtenOrbitopeConstraint(scip, vars, &nspcons, nblocks, &type) );
3247  }
3248 
3249  /* create constraint data */
3250  SCIP_CALL( consdataCreate(scip, &consdata, vars, nspcons, nblocks, orbitopetype, resolveprop) );
3251 
3252  /* create constraint */
3253  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3254  local, modifiable, dynamic, removable, stickingatnode) );
3255 
3256  return SCIP_OKAY;
3257 }
3258 
3259 /** creates and captures an orbitope constraint
3260  * in its most basic variant, i. e., with all constraint flags set to their default values
3261  *
3262  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3263  */
3265  SCIP* scip, /**< SCIP data structure */
3266  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3267  const char* name, /**< name of constraint */
3268  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
3269  SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
3270  int nspcons, /**< number of set partitioning/packing constraints <=> p */
3271  int nblocks, /**< number of symmetric variable blocks <=> q */
3272  SCIP_Bool resolveprop /**< should propagation be resolved? */
3273  )
3274 {
3275  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, resolveprop,
3276  TRUE, TRUE, TRUE, TRUE, TRUE,
3277  FALSE, FALSE, FALSE, FALSE, FALSE) );
3278 
3279  return SCIP_OKAY;
3280 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
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 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)
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip.c:6291
static SCIP_DECL_CONSPARSE(consParseOrbitope)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19643
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
static SCIP_RETCODE fixTriangle(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
#define CONSHDLR_SEPAFREQ
Definition: cons_orbitope.c:77
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8245
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip.c:6314
#define CONSHDLR_DELAYPROP
Definition: cons_orbitope.c:84
static SCIP_RETCODE checkPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19503
static SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9230
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:22622
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip.c:6544
#define SCIP_MAXSTRLEN
Definition: def.h:259
static void copyValues(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip.c:6036
static SCIP_RETCODE propagateFullOrbitopeCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:46807
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:27382
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip.c:18951
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
#define CONSHDLR_SEPAPRIORITY
Definition: cons_orbitope.c:74
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4485
#define FALSE
Definition: def.h:64
static SCIP_DECL_CONSPRESOL(consPresolOrbitope)
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip.c:3542
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.c:5894
constraint handler for orbisack constraints
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
#define TRUE
Definition: def.h:63
static SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:27245
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
Definition: scip.c:21654
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8265
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
#define CONSHDLR_DESC
Definition: cons_orbitope.c:73
static SCIP_RETCODE resolvePropagationFullOrbitopes(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip.c:27149
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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.c:5948
#define CONSHDLR_NAME
Definition: cons_orbitope.c:72
#define DEFAULT_CHECKALWAYSFEAS
Definition: cons_orbitope.c:92
static SCIP_DECL_CONSFREE(consFreeOrbitope)
static SCIP_RETCODE propagateFullOrbitope(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***vars, int firstcol, int lastcol, int currow, int nrows, int ncols, int *nfixedvars, SCIP_Bool *infeasible)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define CONSHDLR_PROPFREQ
Definition: cons_orbitope.c:78
#define CONSHDLR_PROP_TIMING
Definition: cons_orbitope.c:87
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:1017
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:37028
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8255
static SCIP_DECL_CONSPRINT(consPrintOrbitope)
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPseparateCoversOrbisack(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool *infeasible, int *ngen)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip.c:6521
SCIP_RETCODE SCIPincludeConshdlrOrbitope(SCIP *scip)
#define CONSHDLR_ENFOPRIORITY
Definition: cons_orbitope.c:75
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1343
static SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip.c:27578
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:27178
static void computeSCTable(SCIP *scip, int nspcons, int nblocks, SCIP_Real **weights, int **cases, SCIP_Real **vals)
#define CONSHDLR_CHECKPRIORITY
Definition: cons_orbitope.c:76
static SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17092
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:27127
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip.c:12500
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:22599
#define DEFAULT_PPORBITOPE
Definition: cons_orbitope.c:90
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:6060
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
#define CONSHDLR_NEEDSCONS
Definition: cons_orbitope.c:85
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip.c:34540
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16071
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7986
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:25926
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8205
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip.c:6085
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4133
static SCIP_RETCODE separateSCIs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *infeasible, int *nfixedvars, int *ncuts)
static SCIP_DECL_CONSCOPY(consCopyOrbitope)
#define REALABS(x)
Definition: def.h:173
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
Definition: cons_orbitope.h:78
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47191
#define SCIP_CALL(x)
Definition: def.h:350
static SCIP_DECL_CONSPROP(consPropOrbitope)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip.c:27529
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8225
static SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:34655
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip.c:6360
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:50
static SCIP_RETCODE propagatePackingPartitioningCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4515
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
#define SCIP_Bool
Definition: def.h:61
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR ***vars, int nspcons, int nblocks, SCIP_ORBITOPETYPE orbitopetype, SCIP_Bool resolveprop)
SCIP_RETCODE SCIPcreateEmptyRowCons(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.c:30396
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9272
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:15947
static SCIP_DECL_CONSDELETE(consDeleteOrbitope)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8185
#define CONSHDLR_PRESOLTIMING
Definition: cons_orbitope.c:88
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8155
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25569
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip.c:6498
static SCIP_DECL_CONSLOCK(consLockOrbitope)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
#define DEFAULT_SEPAFULLORBITOPE
Definition: cons_orbitope.c:91
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35830
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9251
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_DECL_CONSTRANS(consTransOrbitope)
static SCIP_DECL_CONSCHECK(consCheckOrbitope)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30534
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
static SCIP_RETCODE separateConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47106
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.c:1920
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8016
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 SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25879
#define CONSHDLR_MAXPREROUNDS
Definition: cons_orbitope.c:82
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:6253
static SCIP_RETCODE strenghtenOrbitopeConstraint(SCIP *scip, SCIP_VAR ***vars, int *nrows, int ncols, SCIP_ORBITOPETYPE *type)
static SCIP_RETCODE checkFullOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool *feasible)
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8235
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:30688
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip.c:6567
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8175
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8165
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16959
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:49
static SCIP_DECL_CONSRESPROP(consRespropOrbitope)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
static SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47393
#define SCIPABORT()
Definition: def.h:322
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
#define CONSHDLR_EAGERFREQ
Definition: cons_orbitope.c:79
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23033
SCIP_RETCODE SCIPcheckSolutionOrbisack(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool printreason, SCIP_Bool *feasible)
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.c:4239
#define CONSHDLR_DELAYSEPA
Definition: cons_orbitope.c:83
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
static SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16817
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5994