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