Scippy

SCIP

Solving Constraint Integer Programs

cons_orbitope.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_orbitope.c
17  * @brief constraint handler for (partitioning/packing) orbitope constraints w.r.t. the full symmetric group
18  * @author Timo Berthold
19  * @author Marc Pfetsch
20  *
21  * The type of constraints of this constraint handler is described in cons_orbitope.h.
22  *
23  * The details of the method implemented here are described in the following papers.
24  *
25  * Packing and Partitioning Orbitopes@n
26  * Volker Kaibel and Marc E. Pfetsch,@n
27  * Math. Program. 114, No. 1, 1-36 (2008)
28  *
29  * Among other things, this paper describes so-called shifted column inequalities of the following
30  * 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
31  * bar. These inequalities can be used to handle symmetry and they are separated in this constraint
32  * handler. We use the linear time separation algorithm of the paper.@par
33  *
34  * Orbitopal Fixing@n
35  * Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,@n
36  * Discrete Optimization 8, No. 4, 595-610 (2011)
37  * (A preliminary version appears in Proc. IPCO 2007.)
38  *
39  * In this paper a linear time propagation algorithm is described, a variant of which is implemented
40  * here. The implemented variant does not run in linear time, but is very fast in practice.
41  *
42  * <table>
43  * <caption>translation table</caption>
44  * <tr><td>here</td><td>paper</td></tr>
45  * <tr><td></td><td></td></tr>
46  * <tr><td>nspcons </td><td>p </td></tr>
47  * <tr><td>nblocks </td><td>q </td></tr>
48  * <tr><td>vars </td><td>x </td></tr>
49  * <tr><td>vals </td><td>A^\\star</td></tr>
50  * <tr><td>weights </td><td>\\omega </td></tr>
51  * <tr><td>cases </td><td>\\tau </td></tr>
52  * <tr><td>fixtriangle </td><td>-- </td></tr>
53  * <tr><td>resolveprop </td><td>-- </td></tr>
54  * <tr><td>firstnonzeros</td><td>\\mu </td></tr>
55  * <tr><td>lastones </td><td>\\alpha </td></tr>
56  * <tr><td>frontiersteps</td><td>\\Gamma </td></tr>
57  * </table>
58  */
59 
60 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
61 
62 #include <assert.h>
63 #include <string.h>
64 #include <ctype.h>
65 
66 #include "scip/cons_orbitope.h"
67 
68 /* constraint handler properties */
69 #define CONSHDLR_NAME "orbitope"
70 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes"
71 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
72 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
73 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
74 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
75 #define CONSHDLR_PROPFREQ -1 /**< frequency for propagating domains; zero means only preprocessing propagation */
76 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
77  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
78 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
79 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
80 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
81 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
82 
83 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
84 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
85 
86 
87 /*
88  * Data structures
89  */
90 
91 /** constraint data for orbitope constraints */
92 struct SCIP_ConsData
93 {
94  SCIP_VAR*** vars; /**< matrix of variables on which the symmetry acts */
95  SCIP_VAR** tmpvars; /**< temporary storage for variables */
96  SCIP_Real** vals; /**< LP-solution for those variables */
97  SCIP_Real* tmpvals; /**< temporary storage for values */
98  SCIP_Real** weights; /**< SC weight table */
99  int** cases; /**< indicator of the SC cases */
100  int nspcons; /**< number of set partitioning/packing constraints <=> p */
101  int nblocks; /**< number of symmetric variable blocks <=> q */
102  SCIP_Bool ispart; /**< whether we deal with the partitioning case (packing otherwise) */
103  SCIP_Bool resolveprop; /**< should propagation be resolved? */
104  SCIP_Bool istrianglefixed; /**< has the upper right triangle already globally been fixed to zero? */
105 };
106 
107 
108 /*
109  * Local methods
110  */
111 
112 /** frees an orbitope constraint data */
113 static
115  SCIP* scip, /**< SCIP data structure */
116  SCIP_CONSDATA** consdata /**< pointer to orbitope constraint data */
117  )
118 {
119  int i;
120  int p;
121  int q;
122 
123  assert( consdata != NULL );
124  assert( *consdata != NULL );
125 
126  p = (*consdata)->nspcons;
127  q = (*consdata)->nblocks;
128  for (i = 0; i < p; ++i)
129  {
130  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases[i]), q); /*lint !e866*/
131  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars[i]), q); /*lint !e866*/
132  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights[i]), q); /*lint !e866*/
133  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals[i]), q); /*lint !e866*/
134  }
135 
136  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases), p);
137  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), p);
138  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights), p);
139  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals), p);
140 
141  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvals), p + q);
142  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvars), p + q);
143 
144  SCIPfreeBlockMemory(scip, consdata);
145 
146  return SCIP_OKAY;
147 }
148 
149 
150 /** creates orbitope constraint data */
151 static
153  SCIP* scip, /**< SCIP data structure */
154  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
155  SCIP_VAR*** vars, /**< variables array, must have size nspcons x nblocks */
156  int nspcons, /**< number of set partitioning (packing) constraints <=> p */
157  int nblocks, /**< number of symmetric variable blocks <=> q */
158  SCIP_Bool ispart, /**< deal with the partitioning case (packing otherwise) */
159  SCIP_Bool resolveprop /**< should propagation be resolved? */
160  )
161 {
162  int i;
163  int j;
164 
165  assert(consdata != NULL);
166 
167  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
168 
169  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals, nspcons) );
170  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights, nspcons) );
171  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vars, nspcons) );
172  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases, nspcons) );
173 
174  for (i = 0; i < nspcons; ++i)
175  {
176  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals[i], nblocks) ); /*lint !e866*/
177  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights[i], nblocks) ); /*lint !e866*/
178  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars[i], vars[i], nblocks) ); /*lint !e866*/
179  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases[i], nblocks) ); /*lint !e866*/
180  }
181 
182  (*consdata)->tmpvals = NULL;
183  (*consdata)->tmpvars = NULL;
184  (*consdata)->nspcons = nspcons;
185  (*consdata)->nblocks = nblocks;
186  (*consdata)->ispart = ispart;
187  (*consdata)->resolveprop = resolveprop;
188  (*consdata)->istrianglefixed = FALSE;
189 
190  /* get transformed variables, if we are in the transformed problem */
191  if ( SCIPisTransformed(scip) )
192  {
193  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvals, nspcons + nblocks) );
194  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvars, nspcons + nblocks) );
195 
196  for (i = 0; i < nspcons; ++i)
197  {
198  /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_orbitope, sine one cannot
199  * easily eliminate single variables from an orbitope constraint. */
200  for (j = 0; j < nblocks; ++j)
201  {
202  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i][j], &(*consdata)->vars[i][j]) );
203  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i][j]) );
204  }
205  }
206  }
207 
208  return SCIP_OKAY;
209 }
210 
211 
212 #ifdef PRINT_MATRIX
213 /** debug method, prints variable matrix */
214 static
215 void printMatrix(
216  SCIP* scip, /**< SCIP data structure */
217  SCIP_CONSDATA* consdata /**< the constraint data */
218  )
219 {
220  int i;
221  int j;
222 
223  assert( consdata != NULL );
224  assert( consdata->nspcons > 0 );
225  assert( consdata->nblocks > 0 );
226  assert( consdata->vars != NULL );
227 
228  for (j = 0; j < consdata->nblocks; ++j)
229  SCIPinfoMessage(scip, NULL, "-");
230 
231  SCIPinfoMessage(scip, NULL, "\n");
232  for (i = 0; i < consdata->nspcons; ++i)
233  {
234  for (j = 0; j < consdata->nblocks; ++j)
235  {
236  if ( SCIPvarGetUbLocal(consdata->vars[i][j]) - SCIPvarGetLbLocal(consdata->vars[i][j]) < 0.5 )
237  SCIPinfoMessage(scip, NULL, "%1.0f", REALABS(SCIPvarGetUbLocal(consdata->vars[i][j])));
238  else
239  SCIPinfoMessage(scip, NULL, " ");
240  }
241  SCIPinfoMessage(scip, NULL, "|\n");
242  }
243  for (j = 0; j < consdata->nblocks; ++j)
244  SCIPinfoMessage(scip, NULL, "-");
245  SCIPinfoMessage(scip, NULL, "\n");
246 }
247 #endif
248 
249 
250 #ifdef SHOW_SCI
251 /** Print SCI in nice form for debugging */
252 static
253 SCIP_RETCODE printSCI(
254  SCIP* scip, /**< SCIP pointer */
255  int p, /**< number of rows */
256  int q, /**< number of columns */
257  int** cases, /**< SCI dynamic programming table */
258  int i, /**< row position of bar */
259  int j /**< column position of bar */
260  )
261 {
262  int k;
263  int l;
264  int** M;
265  int p1;
266  int p2;
267 
268  SCIP_CALL( SCIPallocBufferArray(scip, &M, p) );
269  for (k = 0; k < p; ++k)
270  {
271  SCIP_CALL( SCIPallocBufferArray(scip, &M[k], q) ); /*lint !e866*/
272  for (l = 0; l < q; ++l)
273  M[k][l] = 0;
274  }
275 
276  /* first add bar */
277  for (l = j; l < q; ++l)
278  {
279  assert( M[i][l] == 0 );
280  M[i][l] = 1;
281  }
282 
283  /* then add shifted column */
284  p1 = i-1;
285  p2 = j-1;
286  do
287  {
288  assert( cases[p1][p2] != -1 );
289  assert( p1 >= 0 && p1 < i );
290  assert( p2 >= 0 && p2 < j );
291 
292  /* if case 1 */
293  if ( cases[p1][p2] == 1 )
294  --p2; /* decrease column */
295  else
296  {
297  /* case 2 or 3: */
298  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
299  assert( M[p1][p2] == 0 );
300  M[p1][p2] = -1;
301  if ( cases[p1][p2] == 3 )
302  break;
303  }
304  --p1; /* decrease row */
305  }
306  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
307  assert( cases[p1][p2] == 3 );
308 
309  /* now output matrix M */
310  for (l = 0; l < q; ++l)
311  SCIPinfoMessage(scip, NULL, "-");
312  SCIPinfoMessage(scip, NULL, "\n");
313 
314  for (k = 0; k < p; ++k)
315  {
316  for (l = 0; l < q; ++l)
317  {
318  if ( l > k )
319  SCIPinfoMessage(scip, NULL, "*");
320  else
321  {
322  switch (M[k][l])
323  {
324  case 1:
325  SCIPinfoMessage(scip, NULL, "+");
326  break;
327  case -1:
328  SCIPinfoMessage(scip, NULL, "-");
329  break;
330  case 0:
331  SCIPinfoMessage(scip, NULL, "#");
332  break;
333  default:
334  SCIPerrorMessage("unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]);
335  SCIPABORT();
336  }
337  }
338  }
339  SCIPinfoMessage(scip, NULL, "\n");
340  }
341 
342  for (l = 0; l < q; ++l)
343  SCIPinfoMessage(scip, NULL, "-");
344  SCIPinfoMessage(scip, NULL, "\n");
345 
346  for (k = 0; k < p; ++k)
347  SCIPfreeBufferArray(scip, &M[k]);
348  SCIPfreeBufferArray(scip, &M);
349 
350  return SCIP_OKAY;
351 }
352 #endif
353 
354 
355 /** copies the variables values from the solution to the constraint data structure */
356 static
357 void copyValues(
358  SCIP* scip, /**< the SCIP data structure */
359  SCIP_CONSDATA* consdata, /**< the constraint data */
360  SCIP_SOL* sol /**< a primal solution or NULL for the current LP optimum */
361  )
362 {
363  int i;
364  int j;
365 
366  assert( scip != NULL );
367  assert( consdata != NULL );
368  assert( consdata->nspcons > 0 );
369  assert( consdata->nblocks > 0 );
370  assert( consdata->vars != NULL );
371  assert( consdata->vals != NULL );
372 
373  for (i = 0; i < consdata->nspcons; ++i)
374  {
375  for (j = 0; j < consdata->nblocks; ++j)
376  consdata->vals[i][j] = SCIPgetSolVal(scip, sol, consdata->vars[i][j]);
377  }
378 }
379 
380 
381 /** compute the dynamic programming table for SC
382  *
383  * Build up dynamic programming table in order to find SCs with minimum weight.
384  *
385  * The values of the minimal SCIs are stored in @a weights.
386  * The array @a cases[i][j] stores which of the cases were applied to get @a weights[i][j].
387  * Here, 3 means that we have reached the upper limit.
388  *
389  * We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a
390  * bit more efficient.
391  */
392 static
393 void computeSCTable(
394  SCIP* scip, /**< SCIP pointer */
395  int nspcons, /**< number of set partitioning (packing) constraints <=> p */
396  int nblocks, /**< number of symmetric variable blocks <=> q */
397  SCIP_Real** weights, /**< SC weight table */
398  int** cases, /**< indicator of the SC cases */
399  SCIP_Real** vals /**< current solution */
400  )
401 {
402  SCIP_Real minvalue;
403  int diagsize;
404  int i;
405  int j;
406 
407  assert( weights != NULL );
408  assert( cases != NULL );
409  assert( vals != NULL );
410 
411 #ifndef NDEBUG
412  /* for debugging */
413  for (i = 0; i < nspcons; ++i)
414  {
415  for (j = 0; j < nblocks; ++j)
416  {
417  if ( i >= j )
418  {
419  weights[i][j] = -1.0;
420  cases[i][j] = -1;
421  }
422  }
423  }
424 #endif
425 
426  /* initialize diagonal */
427  minvalue = vals[0][0];
428  weights[0][0] = minvalue;
429  cases[0][0] = 3;
430 
431  /* get last row of triangle */
432  diagsize = nblocks;
433  if ( nspcons < nblocks )
434  diagsize = nspcons;
435 
436  for (j = 1; j < diagsize; ++j)
437  {
438  /* use LT to move entry as far to the left as possible */
439  if ( SCIPisLT(scip, vals[j][j], minvalue) )
440  {
441  minvalue = vals[j][j];
442  cases[j][j] = 3;
443  }
444  else
445  cases[j][j] = 1;
446  weights[j][j] = minvalue;
447  }
448 
449  /* initialize first column */
450  for (i = 1; i < nspcons; ++i)
451  {
452  weights[i][0] = weights[i-1][0] + vals[i][0];
453  cases[i][0] = 2; /* second case */
454  }
455 
456  /* build the table */
457  for (i = 2; i < nspcons; ++i)
458  {
459  for (j = 1; j < nblocks && j < i; ++j)
460  {
461  SCIP_Real weightleft;
462  SCIP_Real weightright;
463 
464  assert( cases[i-1][j] != -1 );
465  assert( cases[i-1][j-1] != -1 );
466 
467  weightleft = weights[i-1][j-1];
468  weightright = vals[i][j] + weights[i-1][j];
469 
470  /* For first column: cannot take left possibility */
471  if ( SCIPisLT(scip, weightleft, weightright) )
472  {
473  weights[i][j] = weightleft;
474  cases[i][j] = 1;
475  }
476  else
477  {
478  weights[i][j] = weightright;
479  cases[i][j] = 2;
480  }
481  }
482  }
483 }
484 
485 
486 /** fix upper right triangle if necessary */
487 static
489  SCIP* scip, /**< SCIP data structure */
490  SCIP_CONS* cons, /**< constraint to be processed */
491  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
492  int* nfixedvars /**< pointer to add up the number of found domain reductions */
493  )
494 {
495  SCIP_CONSDATA* consdata;
496  SCIP_VAR*** vars;
497  SCIP_Bool fixedglobal;
498  SCIP_Bool fixed;
499  int diagsize;
500  int nspcons;
501  int nblocks;
502  int i;
503  int j;
504 
505  assert( scip != NULL );
506  assert( cons != NULL );
507  assert( infeasible != NULL );
508  assert( nfixedvars != NULL );
509 
510  consdata = SCIPconsGetData(cons);
511  assert( consdata != NULL );
512  assert( consdata->nspcons > 0 );
513  assert( consdata->nblocks > 0 );
514  assert( consdata->vars != NULL );
515 
516  *infeasible = FALSE;
517  *nfixedvars = 0;
518 
519  if ( consdata->istrianglefixed )
520  return SCIP_OKAY;
521 
522  nspcons = consdata->nspcons;
523  nblocks = consdata->nblocks;
524  vars = consdata->vars;
525  fixedglobal = TRUE;
526 
527  /* get last row of triangle */
528  diagsize = nblocks;
529  if ( nspcons < nblocks )
530  diagsize = nspcons;
531 
532  /* fix variables to 0 */
533  for (i = 0; i < diagsize; ++i)
534  {
535  for (j = i+1; j < nblocks; ++j)
536  {
537  /* fix variable, if not in the root the fixation is local */
538  SCIP_CALL( SCIPfixVar(scip, vars[i][j], 0.0, infeasible, &fixed) );
539 
540  if ( *infeasible )
541  {
542  SCIPdebugMsg(scip, "The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n");
543  return SCIP_OKAY;
544  }
545 
546  if ( fixed )
547  ++(*nfixedvars);
548 
549  if ( SCIPvarGetUbGlobal(vars[i][j]) > 0.5 )
550  fixedglobal = FALSE;
551  }
552  }
553  if ( *nfixedvars > 0 )
554  {
555  SCIPdebugMsg(scip, "<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n", SCIPconsGetName(cons), fixedglobal ? "globally" : "locally", *nfixedvars);
556  }
557  else
558  {
559  SCIPdebugMsg(scip, "<%s>: Upper right triangle already fixed to 0.\n", SCIPconsGetName(cons));
560  }
561 
562  if ( fixedglobal )
563  consdata->istrianglefixed = TRUE;
564 
565  return SCIP_OKAY;
566 }
567 
568 
569 /** separates shifted column inequalities according to the solution stored in consdata->vals */
570 static
572  SCIP* scip, /**< the SCIP data structure */
573  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
574  SCIP_CONS* cons, /**< constraint */
575  SCIP_CONSDATA* consdata, /**< the constraint data */
576  SCIP_Bool* infeasible, /**< whether we detected infeasibility */
577  int* nfixedvars, /**< pointer to store the number of variables fixed */
578  int* ncuts /**< pointer to store number of separated SCIs */
579  )
580 {
581  SCIP_Real** vals;
582  SCIP_Real** weights;
583  SCIP_Real* tmpvals;
584  SCIP_VAR*** vars;
585  SCIP_VAR** tmpvars;
586  int** cases;
587  int nspcons;
588  int nblocks;
589  int i;
590  int j;
591  int l;
592 
593  assert( scip != NULL );
594  assert( conshdlr != NULL );
595  assert( cons != NULL );
596  assert( infeasible != NULL);
597  assert( nfixedvars != NULL );
598  assert( ncuts != NULL );
599 
600  assert( consdata != NULL );
601  assert( consdata->nspcons > 0 );
602  assert( consdata->nblocks > 0 );
603  assert( consdata->vars != NULL );
604  assert( consdata->vals != NULL );
605  assert( consdata->tmpvars != NULL );
606  assert( consdata->tmpvals != NULL );
607  assert( consdata->weights != NULL );
608  assert( consdata->cases != NULL );
609 
610  *infeasible = FALSE;
611  *nfixedvars = 0;
612  *ncuts = 0;
613 
614  nspcons = consdata->nspcons;
615  nblocks = consdata->nblocks;
616  vars = consdata->vars;
617  vals = consdata->vals;
618  tmpvars = consdata->tmpvars;
619  tmpvals = consdata->tmpvals;
620  weights = consdata->weights;
621  cases = consdata->cases;
622 
623  /* check for upper right triangle */
624  if ( ! consdata->istrianglefixed )
625  {
626  SCIP_CALL( fixTriangle(scip, cons, infeasible, nfixedvars) );
627  if ( *infeasible )
628  return SCIP_OKAY;
629  if ( *nfixedvars > 0 )
630  return SCIP_OKAY;
631  }
632 
633  /* compute table if necessary (i.e., not computed before) */
634  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
635 
636  /* loop through rows */
637  for (i = 1; i < nspcons && ! (*infeasible); ++i)
638  {
639  SCIP_Real bar; /* value of bar: */
640  int lastcolumn; /* last column considered as part of the bar */
641 
642  bar = 0.0;
643  lastcolumn = nblocks - 1;
644  if ( lastcolumn > i )
645  lastcolumn = i;
646 
647  /* traverse row from right to left: */
648  /* j >= 2, since for j = 1 we look at column 0, which is uninteresting due to the one at position (0,0) */
649  for (j = lastcolumn; j > 1; --j)
650  {
651  bar += vals[i][j];
652 
653  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
654  if ( SCIPisEfficacious(scip, bar - weights[i-1][j-1]) )
655  {
656  SCIP_Real weight;
657  SCIP_ROW* row;
658 #ifdef SCIP_DEBUG
659  char name[SCIP_MAXSTRLEN];
660 #endif
661  int nvars;
662  int p1;
663  int p2;
664 
665  nvars = 0;
666  p1 = i-1;
667  p2 = j-1;
668  weight = 0.0;
669 
670  /* first add bar */
671  for (l = j; l <= lastcolumn; ++l)
672  {
673  tmpvars[nvars] = vars[i][l];
674  tmpvals[nvars] = 1.0;
675  nvars++;
676  }
677 
678  /* then add shifted column */
679  do
680  {
681  assert( cases[p1][p2] != -1 );
682  assert( p1 >= 0 && p1 < i );
683  assert( p2 >= 0 && p2 < j );
684 
685  /* if case 1 */
686  if (cases[p1][p2] == 1)
687  p2--; /* decrease column */
688  else
689  {
690  /* case 2 or 3: */
691  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
692  tmpvars[nvars] = vars[p1][p2];
693  tmpvals[nvars] = -1.0;
694  nvars++;
695  weight += vals[p1][p2];
696  if ( cases[p1][p2] == 3 )
697  break;
698  }
699  p1--; /* decrease row */
700  }
701  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
702  assert( cases[p1][p2] == 3 );
703 
704  /* generate cut */
705 #ifdef SCIP_DEBUG
706  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sci_%d_%d", i, j);
707  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
708 #else
709  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
710 #endif
711  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvars, tmpvars, tmpvals) );
712  /*SCIP_CALL( SCIPprintRow(scip, row, NULL) ); */
713  SCIP_CALL( SCIPaddCut(scip, NULL, row, FALSE, infeasible) );
714  SCIP_CALL( SCIPreleaseRow(scip, &row) );
715  ++(*ncuts);
716 
717 #ifdef SHOW_SCI
718  SCIP_CALL( printSCI(scip, nspcons, nblocks, cases, i, j) );
719 #endif
720 
721  assert( SCIPisSumEQ(scip, weights[i-1][j-1], weight) );
722  }
723  }
724  }
725  return SCIP_OKAY;
726 }
727 
728 
729 /** propagation method for a single orbitope constraint */
730 static
732  SCIP* scip, /**< SCIP data structure */
733  SCIP_CONS* cons, /**< constraint to be processed */
734  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
735  int* nfixedvars /**< pointer to add up the number of found domain reductions */
736  )
737 {
738  SCIP_CONSDATA* consdata;
739  SCIP_VAR*** vars;
740  SCIP_Bool ispart;
741  int* firstnonzeros;
742  int* lastones;
743  int* frontiersteps;
744  int lastoneprevrow;
745  int nspcons;
746  int nblocks;
747  int nsteps;
748  int i;
749  int j;
750 
751  assert( scip != NULL );
752  assert( cons != NULL );
753  assert( infeasible != NULL );
754  assert( nfixedvars != NULL );
755 
756  *nfixedvars = 0;
757 
758  if( !SCIPallowDualReds(scip) )
759  return SCIP_OKAY;
760 
761  consdata = SCIPconsGetData(cons);
762  assert( consdata != NULL );
763  assert( consdata->nspcons > 0 );
764  assert( consdata->nblocks > 0 );
765  assert( consdata->vars != NULL );
766 
767  nspcons = consdata->nspcons;
768  nblocks = consdata->nblocks;
769  vars = consdata->vars;
770  ispart = consdata->ispart;
771 
772  /* fix upper right triangle if still necessary */
773  if ( ! consdata->istrianglefixed )
774  {
775  int nfixed = 0;
776  SCIP_CALL( fixTriangle(scip, cons, infeasible, &nfixed) );
777  *nfixedvars += nfixed;
778  }
779 
780  /* prepare further propagation */
781  SCIP_CALL( SCIPallocBufferArray(scip, &firstnonzeros, nspcons) );
782  SCIP_CALL( SCIPallocBufferArray(scip, &lastones, nspcons) );
783  SCIP_CALL( SCIPallocBufferArray(scip, &frontiersteps, nblocks) );
784 
785 #ifdef PRINT_MATRIX
786  SCIPdebugMsg(scip, "Matrix:\n");
787  printMatrix(scip, consdata);
788 #endif
789 
790  /* propagate */
791  lastoneprevrow = 0;
792  lastones[0] = 0;
793 
794  if ( ! ispart )
795  {
796  /* packing case: if entry (0,0) is fixed to 0 */
797  if ( SCIPvarGetUbLocal(vars[0][0]) < 0.5 )
798  {
799  lastoneprevrow = -1;
800  lastones[0] = -1;
801  }
802  }
803  nsteps = 0;
804 
805  for (i = 1; i < nspcons; ++i)
806  {
807  int lastcolumn;
808  int firstnonzeroinrow;
809  int lastoneinrow;
810  SCIP_Bool infrontier;
811 
812  /* last column considered as part of the bar: */
813  lastcolumn = nblocks - 1;
814  if ( lastcolumn > i )
815  lastcolumn = i;
816 
817  /* find first position not fixed to 0 (partitioning) or fixed to 1 (packing) */
818  firstnonzeroinrow = -1;
819  for (j = 0; j <= lastcolumn; ++j)
820  {
821  if ( ispart )
822  {
823  /* partitioning case: if variable is not fixed to 0 */
824  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
825  {
826  firstnonzeroinrow = j;
827  break;
828  }
829  }
830  else
831  {
832  /* packing case: if variable is fixed to 1 */
833  if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
834  {
835  firstnonzeroinrow = j;
836  break;
837  }
838  }
839  }
840  /* if all variables are fixed to 0 in the partitioning case - should not happen */
841  if ( firstnonzeroinrow == -1 && ispart )
842  {
843  SCIPdebugMsg(scip, " -> Infeasible node: all variables in row %d are fixed to 0.\n", i);
844  *infeasible = TRUE;
845  /* conflict should be analyzed by setppc constraint handler */
846  goto TERMINATE;
847  }
848  firstnonzeros[i] = firstnonzeroinrow;
849  assert( !ispart || firstnonzeroinrow >= 0 );
850  assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn );
851 
852  /* compute rightmost possible position for a 1 */
853  assert( !ispart || 0 <= lastoneprevrow );
854  assert( lastoneprevrow <= lastcolumn );
855 
856  /* if we are at right border or if entry in column lastoneprevrow+1 is fixed to 0 */
857  infrontier = FALSE;
858  assert( lastoneprevrow + 1 >= 0 );
859  if ( lastoneprevrow == nblocks-1 || SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 ) /*lint !e679*/
860  lastoneinrow = lastoneprevrow;
861  else
862  {
863  lastoneinrow = lastoneprevrow + 1;
864  frontiersteps[nsteps++] = i;
865  infrontier = TRUE;
866  }
867 
868  /* store lastoneinrow */
869  assert( !ispart || 0 <= lastoneinrow );
870  assert( lastoneinrow <= lastcolumn );
871  lastones[i] = lastoneinrow;
872 
873  /* check whether we are infeasible */
874  if ( firstnonzeroinrow > lastoneinrow )
875  {
876  int k;
877 
878 #ifdef SCIP_DEBUG
879  if ( ispart )
880  {
881  SCIPdebugMsg(scip, " -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n",
882  i, firstnonzeroinrow, lastoneinrow);
883  }
884  else
885  {
886  SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n",
887  i, firstnonzeroinrow, lastoneinrow);
888  }
889 #endif
890  /* check if conflict analysis is applicable */
892  {
893  /* conflict analysis only applicable in SOLVING stage */
894  assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) );
895 
896  /* perform conflict analysis */
898 
899  if ( ispart )
900  {
901  /* add bounds (variables fixed to 0) that result in the first nonzero entry */
902  for (j = 0; j <= lastcolumn; ++j)
903  {
904  /* add varaibles in row up to the first variable fixed to 0 */
905  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
906  break;
907 
908  assert( SCIPvarGetUbLocal(vars[i][j]) < 0.5 );
909  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
910  }
911  }
912  else
913  {
914  /* add bounds that result in the last one - check top left entry for packing case */
915  if ( lastones[0] == -1 )
916  {
917  assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
918  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
919  }
920 
921  /* mark variable fixed to 1 */
922  assert( SCIPvarGetLbLocal(vars[i][firstnonzeroinrow]) > 0.5 );
923  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][firstnonzeroinrow]) );
924  }
925 
926  /* add bounds that result in the last one - pass through rows */
927  for (k = 1; k < i; ++k)
928  {
929  int l;
930  l = lastones[k] + 1;
931 
932  /* if the frontier has not moved and we are not beyond the matrix boundaries */
933  if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
934  {
935  assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
936  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
937  }
938  }
939  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
940  }
941 
942  *infeasible = TRUE;
943  goto TERMINATE;
944  }
945 
946  /* fix entries beyond the last possible position for a 1 in the row to 0 (see Lemma 1 in the paper) */
947  for (j = lastoneinrow+1; j <= lastcolumn; ++j)
948  {
949  /* if the entry is not yet fixed to 0 */
950  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
951  {
952  SCIP_Bool tightened;
953  int inferInfo;
954 
955  SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 0.\n", i, j);
956 
957  tightened = FALSE;
958 
959  /* fix variable to 0 and store position of (i,lastoneinrow+1) for conflict resolution */
960  inferInfo = i * nblocks + lastoneinrow + 1;
961  /* correction according to Lemma 1 in the paper (second part): store (i,lastoneinrow+2) */
962  if ( !infrontier )
963  ++inferInfo;
964  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i][j], FALSE, cons, inferInfo, infeasible, &tightened) );
965 
966  /* if entry is fixed to one -> infeasible node */
967  if ( *infeasible )
968  {
969  SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow);
970  /* check if conflict analysis is applicable */
972  {
973  int k;
974 
975  /* conflict analysis only applicable in SOLVING stage */
976  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip));
977 
978  /* perform conflict analysis */
980 
981  /* add current bound */
982  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
983 
984  /* add bounds that result in the last one - check top left entry for packing case */
985  if ( ! ispart && lastones[0] == -1 )
986  {
987  assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
988  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
989  }
990 
991  /* add bounds that result in the last one - pass through rows */
992  for (k = 1; k < i; ++k)
993  {
994  int l;
995  l = lastones[k] + 1;
996 
997  /* if the frontier has not moved and we are not beyond the matrix boundaries */
998  if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
999  {
1000  assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1001  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1002  }
1003  }
1004  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1005  }
1006 
1007  goto TERMINATE;
1008  }
1009  if ( tightened )
1010  ++(*nfixedvars);
1011  }
1012  }
1013 
1014  lastoneprevrow = lastoneinrow;
1015  }
1016 
1017  /* check whether fixing any entry to 0 results in a contradiction -> loop through rows in frontiersteps (a.k.a. gamma) */
1018  for (j = 0; j < nsteps; ++j)
1019  {
1020  int s;
1021  int lastoneinrow;
1022 
1023  s = frontiersteps[j];
1024  lastoneinrow = lastones[s];
1025  /* note for packing case: if we are in a frontier step then lastoneinrow >= 0 */
1026  assert( 0 <= lastoneinrow && lastoneinrow < nblocks );
1027 
1028  /* if entry is not fixed */
1029  if ( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 && SCIPvarGetUbLocal(vars[s][lastoneinrow]) > 0.5 )
1030  {
1031  int betaprev;
1032  betaprev = lastoneinrow - 1;
1033 
1034  /* loop through rows below s */
1035  for (i = s+1; i < nspcons; ++i)
1036  {
1037  int beta;
1038 
1039  assert( betaprev + 1 >= 0 );
1040  if ( betaprev == nblocks-1 || SCIPvarGetUbLocal(vars[i][betaprev+1]) < 0.5 ) /*lint !e679*/
1041  beta = betaprev;
1042  else
1043  beta = betaprev + 1;
1044  assert( -1 <= beta && beta < nblocks );
1045 
1046  if ( firstnonzeros[i] > beta )
1047  {
1048  SCIP_Bool tightened;
1049  int inferInfo;
1050 
1051  /* can fix (s,lastoneinrow) (a.k.a (s,alpha)) to 1
1052  * (do not need to fix other entries to 0, since they will be
1053  * automatically fixed by SCIPtightenVarLb.)
1054  */
1055  assert( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 );
1056  SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow);
1057 
1058  tightened = FALSE;
1059 
1060  /* store position (i,firstnonzeros[i]) */
1061  inferInfo = nblocks * nspcons + i * nblocks + firstnonzeros[i];
1062  SCIP_CALL( SCIPinferBinvarCons(scip, vars[s][lastoneinrow], TRUE, cons, inferInfo, infeasible, &tightened) );
1063 
1064  assert( !(*infeasible) );
1065  if ( tightened )
1066  ++(*nfixedvars);
1067  break;
1068  }
1069  betaprev = beta;
1070  }
1071  }
1072  }
1073 
1074  TERMINATE:
1075  SCIPfreeBufferArray(scip, &frontiersteps);
1076  SCIPfreeBufferArray(scip, &lastones);
1077  SCIPfreeBufferArray(scip, &firstnonzeros);
1078 
1079  return SCIP_OKAY;
1080 }
1081 
1082 
1083 /** Propagation conflict resolving method of propagator
1084  *
1085  * In this function we use that the propagation method above implicitly propagates SCIs, i.e., every
1086  * fixing can also be gotten via an SCI-fixing.
1087  *
1088  * Since the storage of an integer is not enough to store the complete information about the fixing
1089  * nor a complete shifted column, we have to use the linear time algorithm for SCIs.
1090  *
1091  * The inferinfo integer is set as follows:
1092  *
1093  * - If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1
1094  * then we fix these entries to 0 and inferinfo is i * nblocks + j, where (i,j) is the leader of the
1095  * bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments
1096  * above).
1097  *
1098  * - If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to
1099  * 1 and inferinfo is (nspcons*nblocks) + i * nblocks + j, where (i,j) is the leader of the bar; see
1100  * Proposition 1 (2c).
1101  */
1102 static
1104  SCIP* scip, /**< SCIP data structure */
1105  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1106  SCIP_VAR* infervar, /**< variable that was deduced */
1107  int inferinfo, /**< inference information */
1108  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
1109  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1110  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1111  )
1112 { /*lint --e{715}*/
1113  SCIP_CONSDATA* consdata;
1114  SCIP_Real** vals;
1115  SCIP_Real** weights;
1116  SCIP_VAR*** vars;
1117  SCIP_Bool ispart;
1118  int** cases;
1119 
1120  int i;
1121  int j;
1122  int nspcons;
1123  int nblocks;
1124 
1125  assert( scip != NULL );
1126  assert( cons != NULL );
1127  assert( result != NULL );
1128 
1129  consdata = SCIPconsGetData(cons);
1130  assert( consdata != NULL );
1131  assert( consdata->nspcons > 0 );
1132  assert( consdata->nblocks > 0 );
1133  assert( consdata->vars != NULL );
1134  assert( consdata->vals != NULL );
1135  assert( consdata->weights != NULL );
1136  assert( consdata->cases != NULL );
1137  assert( consdata->istrianglefixed );
1138 
1139  *result = SCIP_DIDNOTFIND;
1140  if ( ! consdata->resolveprop )
1141  return SCIP_OKAY;
1142 
1143  nspcons = consdata->nspcons;
1144  nblocks = consdata->nblocks;
1145  vars = consdata->vars;
1146  vals = consdata->vals;
1147  weights = consdata->weights;
1148  ispart = consdata->ispart;
1149  cases = consdata->cases;
1150 
1151  SCIPdebugMsg(scip, "Propagation resolution method of orbitope constraint using orbitopal fixing\n");
1152 
1153  /* fill table */
1154  for (i = 0; i < nspcons; ++i)
1155  {
1156  int lastcolumn;
1157 
1158  /* last column considered as part of the bar: */
1159  lastcolumn = nblocks - 1;
1160  if ( lastcolumn > i )
1161  lastcolumn = i;
1162  for (j = 0; j <= lastcolumn; ++j)
1163  {
1164  /* if the variable was fixed to zero at conflict time */
1165  if ( SCIPgetVarUbAtIndex(scip, vars[i][j], bdchgidx, FALSE) < 0.5 )
1166  vals[i][j] = 0.0;
1167  else
1168  {
1169  /* if the variable was fixed to one at conflict time */
1170  if ( SCIPgetVarLbAtIndex(scip, vars[i][j], bdchgidx, FALSE) > 0.5 )
1171  vals[i][j] = 2.0;
1172  else
1173  vals[i][j] = 1.0;
1174  }
1175  }
1176  }
1177 
1178 #ifdef PRINT_MATRIX
1179  SCIPdebugMsg(scip, "Matrix:\n");
1180  printMatrix(scip, consdata);
1181 #endif
1182 
1183  /* computation of table: this now minimizes the value of the shifted column */
1184  assert( consdata->istrianglefixed );
1185  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
1186 
1187  /* if we fixed variables in the bar to zero */
1188  assert( inferinfo >= 0 && inferinfo < 2 * nspcons * nblocks );
1189  if ( inferinfo < nspcons * nblocks )
1190  {
1191  int p1;
1192  int p2;
1193 #ifdef SCIP_DEBUG
1194  char str[SCIP_MAXSTRLEN];
1195  char tmpstr[SCIP_MAXSTRLEN];
1196 #endif
1197 
1198  i = (int) (inferinfo / nblocks);
1199  j = inferinfo % nblocks;
1200  assert( 0 <= i && i < nspcons );
1201  assert( 0 <= j && j < nblocks );
1202 
1203  /* find SCI with value 0 */
1204  assert( weights[i-1][j-1] < 0.5 );
1205 
1206  SCIPdebugMsg(scip, " -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i, MIN(i,nblocks));
1207 #ifdef SCIP_DEBUG
1208  str[0] = '\0';
1209 #endif
1210 
1211  p1 = i-1;
1212  p2 = j-1;
1213  do
1214  {
1215  assert( cases[p1][p2] != -1 );
1216  assert( p1 >= 0 && p1 < i );
1217  assert( p2 >= 0 && p2 < j );
1218 
1219  /* if case 1 */
1220  if ( cases[p1][p2] == 1 )
1221  --p2; /* decrease column */
1222  else
1223  {
1224  /* case 2 or 3: */
1225  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1226  assert( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
1227  SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
1228  *result = SCIP_SUCCESS;
1229 
1230 #ifdef SCIP_DEBUG
1231  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
1232  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1233 #endif
1234 
1235  if ( cases[p1][p2] == 3 )
1236  break;
1237  }
1238  --p1; /* decrease row */
1239  }
1240  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
1241  assert( cases[p1][p2] == 3 );
1242 
1243 #ifdef SCIP_DEBUG
1244  SCIPdebugMsg(scip, "%s\n", str);
1245 #endif
1246  }
1247  else
1248  {
1249  int k;
1250  int p1;
1251  int p2;
1252 #ifndef NDEBUG
1253  int pos1;
1254  int pos2;
1255 #endif
1256 #ifdef SCIP_DEBUG
1257  char str[SCIP_MAXSTRLEN];
1258  char tmpstr[SCIP_MAXSTRLEN];
1259 #endif
1260 
1261  /* if we fixed a variable in the SC to 1 */
1262  inferinfo -= nspcons * nblocks;
1263  i = (int) inferinfo / nblocks;
1264  j = inferinfo % nblocks;
1265  assert( 0 <= i && i < nspcons );
1266  assert( 0 <= j && j < nblocks );
1267 
1268  /* In rare cases it might happen that we fixed a variable to 1, but the node later becomes infeasible by globally
1269  * fixing variables to 0. In this case, it might happen that we find a SC with value 0 instead of 1. We then
1270  * cannot use this SC to repropagate (and do not know how to reconstruct the original reasoning). */
1271  if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 )
1272  {
1273  SCIPdebugMsg(scip, " -> reason for x[%d][%d] = 1 was the following SC:\n", i, j);
1274 #ifdef SCIP_DEBUG
1275  (void) SCIPsnprintf(str, SCIP_MAXSTRLEN, "SC:");
1276 #endif
1277 
1278  p1 = i-1;
1279  p2 = j-1;
1280 #ifndef NDEBUG
1281  pos1 = -1;
1282  pos2 = -1;
1283 #endif
1284  do
1285  {
1286  assert( cases[p1][p2] != -1 );
1287  assert( p1 >= 0 && p1 < i );
1288  assert( p2 >= 0 && p2 < j );
1289 
1290  /* if case 1 */
1291  if ( cases[p1][p2] == 1 )
1292  --p2; /* decrease column */
1293  else
1294  {
1295  /* case 2 or 3: reason are formed by variables in SC fixed to 0 */
1296  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1297  if ( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 )
1298  {
1299  SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
1300  *result = SCIP_SUCCESS;
1301 
1302 #ifdef SCIP_DEBUG
1303  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
1304  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1305 #endif
1306  }
1307 #ifndef NDEBUG
1308  else
1309  {
1310  assert( SCIPgetVarLbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
1311  assert( pos1 == -1 && pos2 == -1 );
1312  pos1 = p1;
1313  pos2 = p2;
1314  }
1315 #endif
1316  if ( cases[p1][p2] == 3 )
1317  break;
1318  }
1319  --p1; /* decrease row */
1320  }
1321  while ( p1 >= 0 ); /* should always be true, i.e., the break should end the loop */
1322  assert( cases[p1][p2] == 3 );
1323  assert( pos1 >= 0 && pos2 >= 0 );
1324 
1325  /* distinguish partitioning/packing */
1326  if ( ispart )
1327  {
1328  /* partitioning case */
1329 #ifdef SCIP_DEBUG
1330  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " before bar: ");
1331  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1332 #endif
1333  /* add variables before the bar in the partitioning case */
1334  for (k = 0; k < j; ++k)
1335  {
1336  assert( SCIPgetVarUbAtIndex(scip, vars[i][k], bdchgidx, FALSE) < 0.5 );
1337  SCIP_CALL( SCIPaddConflictUb(scip, vars[i][k], bdchgidx) );
1338  *result = SCIP_SUCCESS;
1339 #ifdef SCIP_DEBUG
1340  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", i, k);
1341  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN);
1342 #endif
1343  }
1344 
1345 #ifdef SCIP_DEBUG
1346  SCIPdebugMsg(scip, "%s\n", str);
1347 #endif
1348  }
1349  else
1350  {
1351  /* packing case */
1352  int lastcolumn;
1353 
1354  /* last column considered as part of the bar: */
1355  lastcolumn = nblocks - 1;
1356  if ( lastcolumn > i )
1357  lastcolumn = i;
1358 
1359  /* search for variable in the bar that is fixed to 1 in the packing case */
1360  for (k = j; k <= lastcolumn; ++k)
1361  {
1362  if ( SCIPgetVarLbAtIndex(scip, vars[i][k], bdchgidx, FALSE) > 0.5 )
1363  {
1364  SCIP_CALL( SCIPaddConflictLb(scip, vars[i][k], bdchgidx) );
1365  *result = SCIP_SUCCESS;
1366  SCIPdebugMsg(scip, " and variable x[%d][%d] fixed to 1.\n", i, k);
1367  break;
1368  }
1369  }
1370  }
1371  }
1372  }
1373 
1374  return SCIP_OKAY;
1375 }
1376 
1377 /** separate or enforce constraints */
1378 static
1380  SCIP* scip, /**< SCIP data structure */
1381  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1382  SCIP_CONS** conss, /**< constraints to process */
1383  int nconss, /**< number of constraints */
1384  int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
1385  SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */
1386  SCIP_RESULT* result /**< pointer to store the result (should be initialized) */
1387  )
1388 {
1389  SCIP_Bool infeasible = FALSE;
1390  int nfixedvars = 0;
1391  int ncuts = 0;
1392  int c;
1393 
1394  assert( scip != NULL );
1395  assert( conshdlr != NULL );
1396  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1397  assert( result != NULL );
1398 
1399  /* loop through constraints */
1400  for (c = 0; c < nconss && ! infeasible; c++)
1401  {
1402  SCIP_CONSDATA* consdata;
1403  int nconsfixedvars;
1404  int nconscuts;
1405 
1406  assert( conss[c] != NULL );
1407 
1408  /* get data of constraint */
1409  consdata = SCIPconsGetData(conss[c]);
1410  assert( consdata != NULL );
1411 
1412  /* get solution */
1413  copyValues(scip, consdata, sol);
1414 
1415  /* separate */
1416  SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
1417  nfixedvars += nconsfixedvars;
1418  ncuts += nconscuts;
1419 
1420  /* stop after the useful constraints if we found cuts of fixed variables */
1421  if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
1422  break;
1423  }
1424 
1425  if ( infeasible )
1426  {
1427  SCIPdebugMsg(scip, "Infeasible node.\n");
1428  *result = SCIP_CUTOFF;
1429  }
1430  else if ( nfixedvars > 0 )
1431  {
1432  SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars);
1433  *result = SCIP_REDUCEDDOM;
1434  }
1435  else if ( ncuts > 0 )
1436  {
1437  SCIPdebugMsg(scip, "Separated %d SCIs.\n", ncuts);
1438  *result = SCIP_SEPARATED;
1439  }
1440  else
1441  {
1442  SCIPdebugMsg(scip, "No violated SCI found during separation.\n");
1443  }
1444 
1445  return SCIP_OKAY;
1446 }
1447 
1448 /*
1449  * Callback methods of constraint handler
1450  */
1451 
1452 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1453 static
1454 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
1455 { /*lint --e{715}*/
1456  assert(scip != NULL);
1457  assert(conshdlr != NULL);
1458  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1459 
1460  /* call inclusion method of constraint handler */
1462 
1463  *valid = TRUE;
1464 
1465  return SCIP_OKAY;
1466 }
1467 
1468 /** frees specific constraint data */
1469 static
1470 SCIP_DECL_CONSDELETE(consDeleteOrbitope)
1471 { /*lint --e{715}*/
1472  assert(conshdlr != NULL);
1473  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1474 
1475  SCIP_CALL( consdataFree(scip, consdata) );
1476 
1477  return SCIP_OKAY;
1478 }
1479 
1480 /** transforms constraint data into data belonging to the transformed problem */
1481 static
1482 SCIP_DECL_CONSTRANS(consTransOrbitope)
1483 { /*lint --e{715}*/
1484  SCIP_CONSDATA* sourcedata;
1485  SCIP_CONSDATA* targetdata;
1486 
1487  assert(conshdlr != NULL);
1488  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1489  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
1490  assert(sourcecons != NULL);
1491  assert(targetcons != NULL);
1492 
1493  sourcedata = SCIPconsGetData(sourcecons);
1494  assert(sourcedata != NULL);
1495 
1496  /* create linear constraint data for target constraint */
1497  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nspcons, sourcedata->nblocks,
1498  sourcedata->ispart, sourcedata->resolveprop) );
1499 
1500  /* create target constraint */
1501  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1502  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1503  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
1504  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
1505  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1506 
1507  return SCIP_OKAY;
1508 }
1509 
1510 /** separation method of constraint handler for LP solutions */
1511 static
1512 SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
1513 { /*lint --e{715}*/
1514  assert( scip != NULL );
1515  assert( result != NULL );
1516 
1517  SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
1518 
1519  *result = SCIP_DIDNOTRUN;
1520 
1521  /* if solution is integer, skip separation */
1522  if ( SCIPgetNLPBranchCands(scip) <= 0 )
1523  return SCIP_OKAY;
1524 
1525  *result = SCIP_DIDNOTFIND;
1526 
1527  /* separate constraints */
1528  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
1529 
1530  return SCIP_OKAY;
1531 }
1532 
1533 /** separation method of constraint handler for arbitrary primal solutions */
1534 static
1535 SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
1536 { /*lint --e{715}*/
1537  assert( scip != NULL );
1538  assert( result != NULL );
1539 
1540  SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for primal solution.\n", SCIPconshdlrGetName(conshdlr));
1541 
1542  *result = SCIP_DIDNOTFIND;
1543 
1544  /* separate constraints */
1545  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
1546 
1547  return SCIP_OKAY;
1548 }
1549 
1550 
1551 /** constraint enforcing method of constraint handler for LP solutions */
1552 static
1553 SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
1554 { /*lint --e{715}*/
1555  assert( scip != NULL );
1556  assert( result != NULL );
1557 
1558  /* we have a negative priority, so we should come after the integrality conshdlr */
1559  assert( SCIPgetNLPBranchCands(scip) == 0 );
1560 
1561  SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
1562 
1563  *result = SCIP_FEASIBLE;
1564 
1565  /* separate constraints */
1566  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
1567 
1568  return SCIP_OKAY;
1569 }
1570 
1571 
1572 /** constraint enforcing method of constraint handler for relaxation solutions */
1573 static
1574 SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
1575 { /*lint --e{715}*/
1576  assert( result != NULL );
1577  assert( scip != NULL );
1578 
1579  SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for relaxation solution.\n", SCIPconshdlrGetName(conshdlr));
1580 
1581  *result = SCIP_FEASIBLE;
1582 
1583  /* separate constraints */
1584  SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
1585 
1586  return SCIP_OKAY;
1587 }
1588 
1589 
1590 /** constraint enforcing method of constraint handler for pseudo solutions */
1591 static
1592 SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
1593 { /*lint --e{715}*/
1594  int c;
1595 
1596  assert( scip != NULL );
1597  assert( conshdlr != NULL );
1598  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1599  assert( result != NULL );
1600 
1601  *result = SCIP_FEASIBLE;
1602  if ( objinfeasible || solinfeasible )
1603  return SCIP_OKAY;
1604 
1605  /* loop through constraints */
1606  for (c = 0; c < nconss; ++c)
1607  {
1608  SCIP_CONSDATA* consdata;
1609  SCIP_Real** weights;
1610  SCIP_Real** vals;
1611  SCIP_CONS* cons;
1612  int** cases;
1613  int nspcons;
1614  int nblocks;
1615  int i;
1616  int j;
1617 
1618  /* get data of constraint */
1619  cons = conss[c];
1620  assert( cons != 0 );
1621  consdata = SCIPconsGetData(cons);
1622 
1623  assert( consdata != NULL );
1624  assert( consdata->nspcons > 0 );
1625  assert( consdata->nblocks > 0 );
1626  assert( consdata->vals != NULL );
1627  assert( consdata->weights != NULL );
1628  assert( consdata->cases != NULL );
1629 
1630  /* check for upper right triangle */
1631  if ( ! consdata->istrianglefixed )
1632  {
1633  SCIP_Bool infeasible = FALSE;
1634  int nfixedvars = 0;
1635 
1636  SCIP_CALL( fixTriangle(scip, cons, &infeasible, &nfixedvars) );
1637  if ( infeasible )
1638  {
1639  *result = SCIP_CUTOFF;
1640  return SCIP_OKAY;
1641  }
1642  if ( nfixedvars > 0 )
1643  {
1644  *result = SCIP_REDUCEDDOM;
1645  return SCIP_OKAY;
1646  }
1647  }
1648 
1649  nspcons = consdata->nspcons;
1650  nblocks = consdata->nblocks;
1651  vals = consdata->vals;
1652  weights = consdata->weights;
1653  cases = consdata->cases;
1654 
1655  /* get solution */
1656  copyValues(scip, consdata, NULL);
1657  SCIPdebugMsg(scip, "Enforcing (pseudo solutions) for orbitope constraint <%s>\n", SCIPconsGetName(conss[c]));
1658 
1659  /* compute table */
1660  assert( consdata->istrianglefixed );
1661  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
1662 
1663  /* loop through rows */
1664  for (i = 1; i < nspcons; ++i)
1665  {
1666  SCIP_Real bar = 0.0;
1667  int lastcolumn;
1668 
1669  lastcolumn = nblocks - 1;
1670 
1671  /* last column considered as part of the bar: */
1672  if ( lastcolumn > i )
1673  lastcolumn = i;
1674 
1675  /* traverse row from right to left */
1676  for (j = lastcolumn; j > 1; --j)
1677  {
1678  bar += vals[i][j];
1679  assert( SCIPisIntegral(scip, vals[i][j]) );
1680 
1681  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
1682  if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
1683  {
1684  SCIPdebugMsg(scip, "Solution is infeasible.\n");
1685  *result = SCIP_INFEASIBLE;
1686  return SCIP_OKAY;
1687  }
1688  }
1689  }
1690  }
1691 
1692  return SCIP_OKAY;
1693 }
1694 
1695 
1696 /** feasibility check method of constraint handler for integral solutions */
1697 static
1698 SCIP_DECL_CONSCHECK(consCheckOrbitope)
1699 { /*lint --e{715}*/
1700  int c;
1701 
1702  assert( scip != NULL );
1703  assert( conshdlr != NULL );
1704  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1705  assert( result != NULL );
1706 
1707  *result = SCIP_FEASIBLE;
1708 
1709  /* loop through constraints */
1710  for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
1711  {
1712  SCIP_CONSDATA* consdata;
1713  SCIP_VAR*** vars;
1714  SCIP_Real** vals;
1715  SCIP_Real** weights;
1716  int** cases;
1717  int nspcons;
1718  int nblocks;
1719  int i;
1720  int j;
1721 
1722  /* get data of constraint */
1723  assert( conss[c] != 0 );
1724  consdata = SCIPconsGetData(conss[c]);
1725 
1726  assert( consdata != NULL );
1727  assert( consdata->nspcons > 0 );
1728  assert( consdata->nblocks > 0 );
1729  assert( consdata->vars != NULL );
1730  assert( consdata->vals != NULL );
1731  assert( consdata->weights != NULL );
1732  assert( consdata->cases != NULL );
1733 
1734  nspcons = consdata->nspcons;
1735  nblocks = consdata->nblocks;
1736  vars = consdata->vars;
1737  vals = consdata->vals;
1738  weights = consdata->weights;
1739  cases = consdata->cases;
1740 
1741  /* get solution */
1742  copyValues(scip, consdata, sol);
1743  SCIPdebugMsg(scip, "Checking orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1744 
1745  /* check upper right triangle (if not yet fixed to zero or in debug mode */
1746 #ifdef NDEBUG
1747  if ( ! consdata->istrianglefixed )
1748 #endif
1749  {
1750  int diagsize;
1751 
1752  /* get last row of triangle */
1753  diagsize = nblocks;
1754  if ( nspcons < nblocks )
1755  diagsize = nspcons;
1756 
1757  /* check variables */
1758  for (i = 0; i < diagsize; ++i)
1759  {
1760  for (j = i+1; j < nblocks; ++j)
1761  {
1762  if ( ! SCIPisFeasZero(scip, vals[i][j]) )
1763  {
1764  if ( printreason )
1765  SCIPinfoMessage(scip, NULL, "variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]);
1766  *result = SCIP_INFEASIBLE;
1767  }
1768  }
1769  }
1770  }
1771 
1772  /* compute table */
1773  computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
1774 
1775  /* loop through rows */
1776  for (i = 1; i < nspcons; ++i)
1777  {
1778  SCIP_Real bar;
1779  int lastcolumn;
1780 
1781  lastcolumn = nblocks - 1;
1782  bar = 0.0;
1783  /* last column considered as part of the bar: */
1784  if ( lastcolumn > i )
1785  lastcolumn = i;
1786 
1787  /* traverse row from right to left */
1788  for (j = lastcolumn; j > 1; --j)
1789  {
1790  bar += vals[i][j];
1791  assert( SCIPisFeasIntegral(scip, vals[i][j]) );
1792 
1793  /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
1794  if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
1795  {
1796  SCIPdebugMsg(scip, "Solution is infeasible.\n");
1797  *result = SCIP_INFEASIBLE;
1798 
1799  if ( printreason )
1800  {
1801  int l;
1802  int p1;
1803  int p2;
1804 
1805  SCIPinfoMessage(scip, NULL, "violated SCI: bar(");
1806 
1807  /* first output bar */
1808  for (l = j; l < nblocks; ++l)
1809  SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[i][l]), consdata->vals[i][l]);
1810 
1811  SCIPinfoMessage(scip, NULL, ") SC(");
1812 
1813  /* output shifted column */
1814  p1 = i-1;
1815  p2 = j-1;
1816  do
1817  {
1818  assert( cases[p1][p2] != -1 );
1819  assert( p1 >= 0 && p1 < i );
1820  assert( p2 >= 0 && p2 < j );
1821 
1822  /* if case 1 */
1823  if (cases[p1][p2] == 1)
1824  --p2; /* decrease column */
1825  else
1826  {
1827  /* case 2 or 3: */
1828  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1829  SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[p1][p2]), consdata->vals[p1][p2]);
1830  if ( cases[p1][p2] == 3 )
1831  break;
1832  }
1833  --p1; /* decrease row */
1834  }
1835  while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
1836  assert( cases[p1][p2] == 3 );
1837 
1838  SCIPinfoMessage(scip, NULL, ")");
1839  }
1840  }
1841  }
1842  }
1843  }
1844  SCIPdebugMsg(scip, "Solution is feasible.\n");
1845 
1846  return SCIP_OKAY;
1847 }
1848 
1849 
1850 /** domain propagation method of constraint handler */
1851 static
1852 SCIP_DECL_CONSPROP(consPropOrbitope)
1853 { /*lint --e{715}*/
1854  SCIP_Bool infeasible = FALSE;
1855  int nfixedvars = 0;
1856  int c;
1857 
1858  assert( scip != NULL );
1859  assert( conshdlr != NULL );
1860  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1861  assert( result != NULL );
1862 
1863  *result = SCIP_DIDNOTRUN;
1864 
1865  /* propagate all useful constraints */
1866  for (c = 0; c < nusefulconss && !infeasible; ++c)
1867  {
1868  assert( conss[c] != 0 );
1869 
1870  SCIPdebugMsg(scip, "Propagation of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1871 
1872  SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixedvars) );
1873  }
1874 
1875  /* return the correct result */
1876  if ( infeasible )
1877  {
1878  *result = SCIP_CUTOFF;
1879  SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n");
1880  }
1881  else if ( nfixedvars > 0 )
1882  {
1883  *result = SCIP_REDUCEDDOM;
1884  SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars);
1885  }
1886  else if ( nusefulconss > 0 )
1887  {
1888  *result = SCIP_DIDNOTFIND;
1889  SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n");
1890  }
1891 
1892  return SCIP_OKAY;
1893 }
1894 
1895 
1896 /** presolving method of constraint handler */
1897 static
1898 SCIP_DECL_CONSPRESOL(consPresolOrbitope)
1899 { /*lint --e{715}*/
1900  SCIP_Bool infeasible = FALSE;
1901  int noldfixedvars;
1902  int c;
1903 
1904  assert( scip != NULL );
1905  assert( conshdlr != NULL );
1906  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1907  assert( result != NULL );
1908 
1909  *result = SCIP_DIDNOTRUN;
1910  noldfixedvars = *nfixedvars;
1911 
1912  /* propagate all useful constraints */
1913  for (c = 0; c < nconss && !infeasible; ++c)
1914  {
1915  int nfixed = 0;
1916 
1917  assert( conss[c] != 0 );
1918 
1919  SCIPdebugMsg(scip, "Presolving of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1920 
1921  SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
1922  *nfixedvars += nfixed;
1923  }
1924 
1925  if ( infeasible )
1926  {
1927  *result = SCIP_CUTOFF;
1928  SCIPdebugMsg(scip, "Presolving detected infeasibility.\n");
1929  }
1930  else if ( *nfixedvars > noldfixedvars )
1931  {
1932  *result = SCIP_SUCCESS;
1933  }
1934  else if ( nconss > 0 )
1935  {
1936  *result = SCIP_DIDNOTFIND;
1937  SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n");
1938  }
1939 
1940  return SCIP_OKAY;
1941 }
1942 
1943 
1944 /** propagation conflict resolving method of constraint handler */
1945 static
1946 SCIP_DECL_CONSRESPROP(consRespropOrbitope)
1947 { /*lint --e{715}*/
1948  assert( scip != NULL );
1949  assert( cons != NULL );
1950  assert( infervar != NULL );
1951  assert( bdchgidx != NULL );
1952  assert( result != NULL );
1953 
1954  SCIP_CALL( resolvePropagation(scip, cons, infervar, inferinfo, boundtype, bdchgidx, result) );
1955 
1956  return SCIP_OKAY;
1957 }
1958 
1959 
1960 /** variable rounding lock method of constraint handler */
1961 static
1962 SCIP_DECL_CONSLOCK(consLockOrbitope)
1963 { /*lint --e{715}*/
1964  SCIP_CONSDATA* consdata;
1965  SCIP_VAR*** vars;
1966  int i;
1967  int j;
1968  int nspcons;
1969  int nblocks;
1970 
1971  assert( scip != NULL );
1972  assert( conshdlr != NULL );
1973  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1974  assert( cons != NULL );
1975 
1976  consdata = SCIPconsGetData(cons);
1977  assert( consdata != NULL );
1978  assert( consdata->nspcons > 0 );
1979  assert( consdata->nblocks > 0 );
1980  assert( consdata->vars != NULL );
1981 
1982  SCIPdebugMsg(scip, "Locking method for orbitope constraint handler\n");
1983 
1984  nspcons = consdata->nspcons;
1985  nblocks = consdata->nblocks;
1986  vars = consdata->vars;
1987 
1988  /* add up locks and down locks on each variable */
1989  for (i = 0; i < nspcons; ++i)
1990  {
1991  for (j = 0; j < nblocks; ++j)
1992  SCIP_CALL( SCIPaddVarLocks(scip, vars[i][j], nlockspos + nlocksneg, nlockspos + nlocksneg) );
1993  }
1994 
1995  return SCIP_OKAY;
1996 }
1997 
1998 
1999 /** constraint display method of constraint handler */
2000 static
2001 SCIP_DECL_CONSPRINT(consPrintOrbitope)
2003  SCIP_CONSDATA* consdata;
2004  SCIP_VAR*** vars;
2005  int i;
2006  int j;
2007  int nspcons;
2008  int nblocks;
2009 
2010  assert( scip != NULL );
2011  assert( conshdlr != NULL );
2012  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2013  assert( cons != NULL );
2014 
2015  consdata = SCIPconsGetData(cons);
2016  assert( consdata != NULL );
2017  assert( consdata->nspcons > 0 );
2018  assert( consdata->nblocks > 0 );
2019  assert( consdata->vars != NULL );
2020 
2021  nspcons = consdata->nspcons;
2022  nblocks = consdata->nblocks;
2023  vars = consdata->vars;
2024 
2025  SCIPdebugMsg(scip, "Printing method for orbitope constraint handler\n");
2026 
2027  if ( consdata->ispart )
2028  SCIPinfoMessage(scip, file, "partOrbitope(");
2029  else
2030  SCIPinfoMessage(scip, file, "packOrbitope(");
2031 
2032  for (i = 0; i < nspcons; ++i)
2033  {
2034  for (j = 0; j < nblocks; ++j)
2035  {
2036  if ( j > 0 )
2037  SCIPinfoMessage(scip, file, ",");
2038  SCIPinfoMessage(scip, file, "%s", SCIPvarGetName(vars[i][j]));
2039  }
2040  if ( i < nspcons-1 )
2041  SCIPinfoMessage(scip, file, ".");
2042  }
2043  SCIPinfoMessage(scip, file, ")");
2044 
2045  return SCIP_OKAY;
2046 }
2047 
2048 
2049 /** constraint copying method of constraint handler */
2050 static
2051 SCIP_DECL_CONSCOPY(consCopyOrbitope)
2053  SCIP_CONSDATA* sourcedata;
2054  SCIP_VAR*** sourcevars;
2055  SCIP_VAR*** vars;
2056  int nspcons;
2057  int nblocks;
2058  int i;
2059  int k;
2060  int j;
2061 
2062  assert( scip != NULL );
2063  assert( cons != NULL );
2064  assert( sourcescip != NULL );
2065  assert( sourceconshdlr != NULL );
2066  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
2067  assert( sourcecons != NULL );
2068  assert( varmap != NULL );
2069  assert( valid != NULL );
2070 
2071  *valid = TRUE;
2072 
2073  SCIPdebugMsg(scip, "Copying method for orbitope constraint handler.\n");
2074 
2075  sourcedata = SCIPconsGetData(sourcecons);
2076  assert( sourcedata != NULL );
2077  assert( sourcedata->nspcons > 0 );
2078  assert( sourcedata->nblocks > 0 );
2079  assert( sourcedata->vars != NULL );
2080 
2081  nspcons = sourcedata->nspcons;
2082  nblocks = sourcedata->nblocks;
2083  sourcevars = sourcedata->vars;
2084 
2085  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nspcons) );
2086  for (i = 0; i < nspcons && *valid; ++i)
2087  {
2088  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), nblocks) ); /*lint !e866*/
2089 
2090  for (j = 0; j < nblocks && *valid; ++j)
2091  {
2092  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
2093  assert( !(*valid) || vars[i][j] != NULL );
2094  }
2095  }
2096 
2097  /* only create the target constraint, if all variables could be copied */
2098  if ( *valid )
2099  {
2100  /* create copied constraint */
2101  if ( name == NULL )
2102  name = SCIPconsGetName(sourcecons);
2103 
2104  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name,
2105  vars, sourcedata->ispart, nspcons, nblocks, sourcedata->resolveprop,
2106  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2107  }
2108 
2109  /* free space; only up to row i if copying failed */
2110  assert( 0 <= i && i <= nspcons );
2111  for (k = 0; k < i; ++k)
2112  SCIPfreeBufferArray(scip, &vars[k]);
2113  SCIPfreeBufferArray(scip, &vars);
2114 
2115  return SCIP_OKAY;
2116 }
2117 
2118 
2119 /** constraint parsing method of constraint handler */
2120 static
2121 SCIP_DECL_CONSPARSE(consParseOrbitope)
2122 { /*lint --e{715}*/
2123  const char* s;
2124  SCIP_Bool ispart;
2125  char varname[SCIP_MAXSTRLEN];
2126  SCIP_VAR*** vars;
2127  SCIP_VAR* var;
2128  int nspcons;
2129  int maxnspcons;
2130  int nblocks;
2131  int maxnblocks;
2132  int k;
2133  int j;
2134 
2135  assert( success != NULL );
2136 
2137  *success = TRUE;
2138  s = str;
2139 
2140  /* skip white space */
2141  while ( *s != '\0' && isspace((unsigned char)*s) )
2142  ++s;
2143 
2144  ispart = FALSE;
2145  if ( strncmp(s, "partOrbitope(", 13) == 0 )
2146  ispart = TRUE;
2147  else
2148  {
2149  if ( strncmp(s, "packOrbitope(", 13) != 0 )
2150  {
2151  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error - expected \"partOrbitope\" or \"packOrbitope\": %s\n", s);
2152  *success = FALSE;
2153  return SCIP_OKAY;
2154  }
2155  }
2156  s += 13;
2157 
2158  /* loop through string */
2159  nspcons = 0;
2160  nblocks = 0;
2161  maxnspcons = 10;
2162  maxnblocks = 10;
2163 
2164  SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnspcons) );
2165  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[0]), maxnblocks) );
2166 
2167  j = 0;
2168  do
2169  {
2170  /* find variable name */
2171  k = 0;
2172  while ( *s != '\0' && ! isspace((unsigned char)*s) && *s != ',' && *s != '.' && *s != ')' )
2173  varname[k++] = *s++;
2174  varname[k] = '\0';
2175 
2176  /* get variable */
2177  var = SCIPfindVar(scip, varname);
2178  if ( var == NULL )
2179  {
2180  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "unknown variable <%s>\n", varname);
2181  *success = FALSE;
2182  return SCIP_OKAY;
2183  }
2184  vars[nspcons][j++] = var;
2185 
2186  if ( j > nblocks )
2187  {
2188  if ( nspcons > 0 )
2189  {
2190  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variables per row do not match.\n");
2191  *success = FALSE;
2192  return SCIP_OKAY;
2193  }
2194  nblocks = j;
2195 
2196  if ( nblocks > maxnblocks )
2197  {
2198  int newsize;
2199 
2200  newsize = SCIPcalcMemGrowSize(scip, nblocks);
2201  SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons]), newsize) ); /*lint !e866*/
2202  maxnblocks = newsize;
2203  }
2204  }
2205  assert( nblocks <= maxnblocks );
2206 
2207  /* skip white space and ',' */
2208  while ( *s != '\0' && ( isspace((unsigned char)*s) || *s == ',' ) )
2209  ++s;
2210 
2211  /* begin new row if required */
2212  if ( *s == '.' )
2213  {
2214  ++nspcons;
2215  ++s;
2216 
2217  if ( nspcons >= maxnspcons )
2218  {
2219  int newsize;
2220 
2221  newsize = SCIPcalcMemGrowSize(scip, nspcons+1);
2222  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, newsize) );
2223  maxnspcons = newsize;
2224  }
2225  assert(nspcons < maxnspcons);
2226 
2227  SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nspcons]), nblocks) ); /*lint !e866*/
2228  j = 0;
2229  }
2230  }
2231  while ( *s != ')' );
2232  ++nspcons;
2233 
2234  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, ispart, nspcons, nblocks, TRUE,
2235  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2236 
2237  for (k = 0; k < nspcons; ++k)
2238  SCIPfreeBufferArray(scip, &vars[k]);
2239  SCIPfreeBufferArray(scip, &vars);
2240 
2241  return SCIP_OKAY;
2242 }
2243 
2244 
2245 /** constraint method of constraint handler which returns the variables (if possible) */
2246 static
2247 SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
2248 { /*lint --e{715}*/
2249  SCIP_CONSDATA* consdata;
2250 
2251  assert( cons != NULL );
2252  assert( success != NULL );
2253  assert( vars != NULL );
2254 
2255  consdata = SCIPconsGetData(cons);
2256  assert( consdata != NULL );
2257 
2258  if ( varssize < consdata->nblocks * consdata->nspcons )
2259  (*success) = FALSE;
2260  else
2261  {
2262  int cnt = 0;
2263  int i;
2264  int j;
2265 
2266  for (i = 0; i < consdata->nspcons; ++i)
2267  {
2268  for (j = 0; j < consdata->nblocks; ++j)
2269  vars[cnt++] = consdata->vars[i][j];
2270  }
2271  (*success) = TRUE;
2272  }
2273 
2274  return SCIP_OKAY;
2275 }
2276 
2277 
2278 /** constraint method of constraint handler which returns the number of variables (if possible) */
2279 static
2280 SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
2281 { /*lint --e{715}*/
2282  SCIP_CONSDATA* consdata;
2283 
2284  assert( cons != NULL );
2285 
2286  consdata = SCIPconsGetData(cons);
2287  assert( consdata != NULL );
2288 
2289  (*nvars) = consdata->nblocks * consdata->nspcons;
2290  (*success) = TRUE;
2291 
2292  return SCIP_OKAY;
2293 }
2294 
2295 
2296 /*
2297  * constraint specific interface methods
2298  */
2299 
2300 /** creates the handler for orbitope constraints and includes it in SCIP */
2302  SCIP* scip /**< SCIP data structure */
2303  )
2304 {
2305  SCIP_CONSHDLRDATA* conshdlrdata;
2306  SCIP_CONSHDLR* conshdlr;
2307 
2308  /* create orbitope constraint handler data */
2309  conshdlrdata = NULL;
2310 
2311  /* include constraint handler */
2315  consEnfolpOrbitope, consEnfopsOrbitope, consCheckOrbitope, consLockOrbitope,
2316  conshdlrdata) );
2317  assert(conshdlr != NULL);
2318 
2319  /* set non-fundamental callbacks via specific setter functions */
2320  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitope, consCopyOrbitope) );
2321  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitope) );
2322  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitope) );
2323  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitope) );
2324  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitope) );
2325  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbitope, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2326  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitope) );
2327  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbitope, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
2329  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitope) );
2330  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitope, consSepasolOrbitope, CONSHDLR_SEPAFREQ,
2332  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitope) );
2333  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitope) );
2334 
2335  return SCIP_OKAY;
2336 }
2337 
2338 
2339 /** creates and captures a orbitope constraint
2340  *
2341  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2342  */
2344  SCIP* scip, /**< SCIP data structure */
2345  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2346  const char* name, /**< name of constraint */
2347  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
2348  SCIP_Bool ispart, /**< whether we deal with the partitioning case (packing otherwise) */
2349  int nspcons, /**< number of set partitioning/packing constraints <=> p */
2350  int nblocks, /**< number of symmetric variable blocks <=> q */
2351  SCIP_Bool resolveprop, /**< should propagation be resolved? */
2352  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2353  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2354  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2355  * Usually set to TRUE. */
2356  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2357  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2358  SCIP_Bool check, /**< should the constraint be checked for feasibility?
2359  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2360  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2361  * Usually set to TRUE. */
2362  SCIP_Bool local, /**< is constraint only valid locally?
2363  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2364  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2365  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2366  * adds coefficients to this constraint. */
2367  SCIP_Bool dynamic, /**< is constraint subject to aging?
2368  * Usually set to FALSE. Set to TRUE for own cuts which
2369  * are separated as constraints. */
2370  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2371  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2372  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2373  * if it may be moved to a more global node?
2374  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2375  )
2376 {
2377  SCIP_CONSHDLR* conshdlr;
2378  SCIP_CONSDATA* consdata;
2379 
2380  /* find the orbitope constraint handler */
2381  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2382  if ( conshdlr == NULL )
2383  {
2384  SCIPerrorMessage("orbitope constraint handler not found\n");
2385  return SCIP_PLUGINNOTFOUND;
2386  }
2387 
2388  assert( nspcons > 0 );
2389  assert( nblocks > 0 );
2390 
2391  /* run some checks */
2392 #ifndef NDEBUG
2393  {
2394  SCIP_Real obj;
2395  int i;
2396  int j;
2397  for (i = 0; i < nspcons; ++i)
2398  {
2399  /* initialize obj to infinity */
2400  obj = SCIPinfinity(scip);
2401  for (j = 0; j < nblocks; ++j)
2402  {
2403  SCIP_Bool fixedZero;
2404  SCIP_VAR* var;
2405 
2406  var = vars[i][j];
2407  assert(var != NULL);
2408 
2409  if ( SCIPvarIsNegated(var) )
2410  var = SCIPvarGetNegatedVar(var);
2411 
2412  /* all variables need to be binary */
2413  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
2414 
2415  /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no
2416  problem (but we cannot always check it, e.g., when in the original problem
2417  variables were fixed and this problem was copied.) */
2418  fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) );
2419 
2420  /* check whether all variables in a row have the same objective */
2421  if ( ! fixedZero && SCIPisInfinity(scip, obj) )
2422  obj = SCIPvarGetObj(var);
2423  else
2424  {
2425  assert( fixedZero || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) );
2426  }
2427  }
2428  }
2429  }
2430 #endif
2431 
2432  /* create constraint data */
2433  SCIP_CALL( consdataCreate(scip, &consdata, vars, nspcons, nblocks, ispart, resolveprop) );
2434 
2435  /* create constraint */
2436  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2437  local, modifiable, dynamic, removable, stickingatnode) );
2438 
2439  return SCIP_OKAY;
2440 }
2441 
2442 /** creates and captures an orbitope constraint
2443  * in its most basic variant, i. e., with all constraint flags set to their default values
2444  *
2445  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2446  */
2448  SCIP* scip, /**< SCIP data structure */
2449  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2450  const char* name, /**< name of constraint */
2451  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
2452  SCIP_Bool ispart, /**< whether we deal with the partitioning case (packing otherwise) */
2453  int nspcons, /**< number of set partitioning/packing constraints <=> p */
2454  int nblocks, /**< number of symmetric variable blocks <=> q */
2455  SCIP_Bool resolveprop /**< should propagation be resolved? */
2456  )
2457 {
2458  SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, ispart, nspcons, nblocks, resolveprop,
2459  TRUE, TRUE, TRUE, TRUE, TRUE,
2460  FALSE, FALSE, FALSE, FALSE, FALSE) );
2461 
2462  return SCIP_OKAY;
2463 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46151
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip.c:6228
static SCIP_DECL_CONSPARSE(consParseOrbitope)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19263
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
static SCIP_RETCODE fixTriangle(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
#define CONSHDLR_SEPAFREQ
Definition: cons_orbitope.c:74
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8140
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip.c:6251
#define CONSHDLR_DELAYPROP
Definition: cons_orbitope.c:81
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19123
static SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip.c:6481
#define SCIP_MAXSTRLEN
Definition: def.h:215
static void copyValues(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip.c:5973
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45601
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26950
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip.c:18575
#define CONSHDLR_SEPAPRIORITY
Definition: cons_orbitope.c:71
#define FALSE
Definition: def.h:64
static SCIP_DECL_CONSPRESOL(consPresolOrbitope)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip.c:5831
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
#define TRUE
Definition: def.h:63
static SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:26813
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
Definition: scip.c:21255
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8160
#define CONSHDLR_DESC
Definition: cons_orbitope.c:70
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip.c:26717
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip.c:5885
#define CONSHDLR_NAME
Definition: cons_orbitope.c:69
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
#define CONSHDLR_PROPFREQ
Definition: cons_orbitope.c:75
#define CONSHDLR_PROP_TIMING
Definition: cons_orbitope.c:84
SCIP_RETCODE SCIPcreateConsBasicOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_Bool ispart, int nspcons, int nblocks, SCIP_Bool resolveprop)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:1010
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:36161
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8150
static SCIP_DECL_CONSPRINT(consPrintOrbitope)
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip.c:6458
SCIP_RETCODE SCIPincludeConshdlrOrbitope(SCIP *scip)
#define CONSHDLR_ENFOPRIORITY
Definition: cons_orbitope.c:72
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1336
static SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip.c:27146
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:26746
static void computeSCTable(SCIP *scip, int nspcons, int nblocks, SCIP_Real **weights, int **cases, SCIP_Real **vals)
#define CONSHDLR_CHECKPRIORITY
Definition: cons_orbitope.c:73
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:16982
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:26695
constraint handler for (partitioning/packing) orbitope constraints w.r.t. the full symmetric group ...
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip.c:12325
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:21904
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:5997
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
#define CONSHDLR_NEEDSCONS
Definition: cons_orbitope.c:82
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip.c:33779
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7881
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:25494
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8100
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
#define NULL
Definition: lpi_spx1.cpp:137
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:159
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
#define SCIP_CALL(x)
Definition: def.h:306
static SCIP_DECL_CONSPROP(consPropOrbitope)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip.c:27097
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8120
static SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip.c:6297
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:33869
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:50
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
#define SCIP_Bool
Definition: def.h:61
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:30022
static SCIP_DECL_CONSDELETE(consDeleteOrbitope)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8080
#define CONSHDLR_PRESOLTIMING
Definition: cons_orbitope.c:85
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8050
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_Bool ispart, 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)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25141
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip.c:6435
static SCIP_DECL_CONSLOCK(consLockOrbitope)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35033
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_DECL_CONSTRANS(consTransOrbitope)
static SCIP_DECL_CONSCHECK(consCheckOrbitope)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30160
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
static SCIP_RETCODE separateConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:45900
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip.c:1911
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:7911
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25447
#define CONSHDLR_MAXPREROUNDS
Definition: cons_orbitope.c:79
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:6190
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8130
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:30314
#define MIN(x, y)
Definition: memory.c:75
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip.c:6504
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8070
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8060
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:49
static SCIP_DECL_CONSRESPROP(consRespropOrbitope)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
static SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21910
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46187
#define SCIPABORT()
Definition: def.h:278
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
#define CONSHDLR_EAGERFREQ
Definition: cons_orbitope.c:76
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22634
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR ***vars, int nspcons, int nblocks, SCIP_Bool ispart, SCIP_Bool resolveprop)
#define CONSHDLR_DELAYSEPA
Definition: cons_orbitope.c:80
static SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16707
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:21929
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5931