Scippy

SCIP

Solving Constraint Integer Programs

cons_symresack.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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_symresack.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief constraint handler for symresack constraints
19  * @author Christopher Hojny
20  * @author Jasper van Doornmalen
21  *
22  * The type of constraints of this constraint handler is described in cons_symresack.h.
23  *
24  * The details of the method implemented here are described in the following papers:
25  *
26  * Fundamental Domains for Integer Programs with Symmetries@n
27  * Eric J. Friedman,@n
28  * Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007)
29  *
30  * This paper describes an inequality to handle symmetries of a single permutation. This
31  * so-called FD-inequality is the basic for the propagation routine of our implementation.
32  *
33  * Polytopes Associated with Symmetry Handling@n
34  * Christopher Hojny and Marc E. Pfetsch,@n
35  * Mathematical Programming 175, No. 1, 197-240, 2019
36  *
37  * This paper describes an almost linear time separation routine for so-called cover
38  * inequalities of symresacks. A slight modification of this algorithm allows for a linear
39  * running time, which is used in this implementation.
40  *
41  * Packing, Partitioning, and Covering Symresacks@n
42  * Christopher Hojny,@n
43  * (2020), available at https://doi.org/10.1016/j.dam.2020.03.002
44  * Discrete Applied Mathematics, volume 283, 689-717 (2020)
45  *
46  * This paper introduces linearly many inequalities with ternary coefficients that suffice to
47  * characterize the binary points contained in a packing and partitioning symresack completely.
48  */
49 
50 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
51 
52 #include "blockmemshell/memory.h"
53 #include "scip/cons_orbisack.h"
54 #include "scip/cons_setppc.h"
55 #include "scip/cons_symresack.h"
56 #include "scip/pub_cons.h"
57 #include "scip/pub_message.h"
58 #include "scip/pub_misc.h"
59 #include "scip/pub_var.h"
60 #include "scip/scip.h"
61 #include "scip/scip_branch.h"
62 #include "scip/scip_conflict.h"
63 #include "scip/scip_cons.h"
64 #include "scip/scip_cut.h"
65 #include "scip/scip_general.h"
66 #include "scip/scip_lp.h"
67 #include "scip/scip_mem.h"
68 #include "scip/scip_message.h"
69 #include "scip/scip_numerics.h"
70 #include "scip/scip_param.h"
71 #include "scip/scip_prob.h"
72 #include "scip/scip_sol.h"
73 #include "scip/scip_var.h"
74 #include <ctype.h>
75 #include <string.h>
76 
77 /* constraint handler properties */
78 #define CONSHDLR_NAME "symresack"
79 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks"
80 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
81 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
82 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
83 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
84 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */
85 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
86  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
87 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
88 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
89 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
90 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
91 
92 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
93 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
94 
95 #define DEFAULT_PPSYMRESACK TRUE /**< whether we allow upgrading to packing/partitioning symresacks */
96 #define DEFAULT_CHECKMONOTONICITY TRUE /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
97 #define DEFAULT_FORCECONSCOPY FALSE /**< whether symresack constraints should be forced to be copied to sub SCIPs */
98 
99 /* Constants to store fixings */
100 #define FIXED0 1 /* When a variable is fixed to 0. */
101 #define FIXED1 2 /* When a variable is fixed to 1. */
102 #define UNFIXED 3 /* When a variable is neither fixed to 0 or to 1. */
103 #define NOINIT 0 /* A dummy entry for non-initialized variables.
104  * Must have value 0 because of SCIPallocCleanBufferArray. */
105 /* A macro for checking if a variable was fixed during a bound change */
106 #define ISFIXED(x, bdchgidx) (SCIPvarGetUbAtIndex(x, bdchgidx, FALSE) - SCIPvarGetLbAtIndex(x, bdchgidx, FALSE) < 0.5)
108 
109 
110 /*
111  * Data structures
112  */
113 
114 /** constraint handler data */
115 struct SCIP_ConshdlrData
116 {
117  SCIP_Bool checkppsymresack; /**< whether we allow upgrading to packing/partitioning symresacks */
118  SCIP_Bool checkmonotonicity; /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
119  int maxnvars; /**< maximal number of variables in a symresack constraint */
120  SCIP_Bool forceconscopy; /**< whether symresack constraints should be forced to be copied to sub SCIPs */
121 };
122 
123 
124 /** constraint data for symresack constraints */
125 struct SCIP_ConsData
126 {
127  SCIP_VAR** vars; /**< variables */
128  int nvars; /**< number of variables */
129  int* perm; /**< permutation associated to the symresack */
130  int* invperm; /**< inverse permutation */
131  SCIP_Bool ppupgrade; /**< whether constraint is upgraded to packing/partitioning symresack */
132  SCIP_Bool ismodelcons; /**< whether the symresack is a model constraint */
133 #ifdef SCIP_DEBUG
134  int debugcnt; /**< counter to store number of added cover inequalities */
135 #endif
136 
137  /* data for upgraded symresack constraints */
138  int ncycles; /**< number of cycles in permutation */
139  int** cycledecomposition; /**< cycle decomposition */
140  int ndescentpoints; /**< number of descent points in perm (only used if perm is not monotone) */
141  int* descentpoints; /**< descent points in perm (only used if perm is not monotone) */
142 };
143 
144 
145 /*
146  * Local methods
147  */
148 
149 /** frees a symresack constraint data */
150 static
152  SCIP* scip, /**< SCIP data structure */
153  SCIP_CONSDATA** consdata /**< pointer to symresack constraint data */
154  )
155 {
156  int nvars;
157  int i;
158 
159  assert( consdata != NULL );
160  assert( *consdata != NULL );
161 
162  nvars = (*consdata)->nvars;
163 
164  if ( nvars == 0 )
165  {
166  assert( (*consdata)->vars == NULL );
167  assert( (*consdata)->perm == NULL );
168  assert( (*consdata)->invperm == NULL );
169  assert( (*consdata)->ncycles == 0 );
170  assert( (*consdata)->cycledecomposition == NULL );
171 
172  SCIPfreeBlockMemory(scip, consdata);
173 
174  return SCIP_OKAY;
175  }
176 
177  if ( (*consdata)->ndescentpoints > 0 )
178  {
179  assert( (*consdata)->descentpoints != NULL );
180 
181  SCIPfreeBlockMemoryArray(scip, &((*consdata)->descentpoints), (*consdata)->ndescentpoints);
182  }
183 
184  if ( (*consdata)->ppupgrade )
185  {
186  for (i = 0; i < (*consdata)->ncycles; ++i)
187  {
188  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition[i]), nvars + 1);
189  }
190  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition), (*consdata)->ncycles);
191  }
192 
193  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->invperm), nvars);
194  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->perm), nvars);
195 
196  for (i = 0; i < nvars; ++i)
197  {
198  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i]) );
199  }
200  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), nvars);
201 
202  SCIPfreeBlockMemory(scip, consdata);
203 
204  return SCIP_OKAY;
205 }
206 
207 
208 /** check whether constraint can be upgraded to packing/partitioning symresack */
209 static
211  SCIP* scip, /**< SCIP data structure */
212  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
213  int* perm, /**< permutation */
214  SCIP_VAR** vars, /**< variables affected by permutation */
215  int nvars, /**< length of permutation */
216  SCIP_Bool checkmonotonicity, /**< check whether permutation is monotone */
217  SCIP_Bool* upgrade /**< pointer to store whether upgrade was successful */
218  )
219 {
220  SCIP_Bool* covered;
221  SCIP_Bool descent;
222  SCIP_CONSHDLR* setppcconshdlr;
223  SCIP_CONS** setppcconss;
224  SCIP_VAR* var;
225  SCIP_Bool terminated = FALSE;
226  int** cycledecomposition;
227  int* indicesincycle;
228  int nsetppcconss;
229  int curcycle;
230  int maxcyclelength;
231  int ncycles = 0;
232  int c;
233  int i;
234  int j;
235  int ndescentpoints = 0;
236  int* descentpoints;
237 
238  assert( scip != NULL );
239  assert( perm != NULL );
240  assert( vars != NULL );
241  assert( nvars > 0 );
242  assert( upgrade != NULL );
243 
244  *upgrade = FALSE;
245 
246  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
247 
248  for (i = 0; i < nvars; ++i)
249  covered[i] = FALSE;
250 
251  /* get number of cycles in permutation */
252  for (i = 0; i < nvars; ++i)
253  {
254  /* skip checked indices */
255  if ( covered[i] )
256  continue;
257 
258  ++ncycles;
259  j = i;
260  descent = FALSE;
261 
262  do
263  {
264  covered[j] = TRUE;
265 
266  if ( perm[j] < j )
267  {
268  ++ndescentpoints;
269 
270  if ( ! descent )
271  descent = TRUE;
272  else if ( checkmonotonicity )
273  break;
274  }
275 
276  j = perm[j];
277  }
278  while ( j != i );
279 
280  /* if cycle is not monotone and we require the cycle to be monotone */
281  if ( j != i )
282  {
283  assert( checkmonotonicity );
284  SCIPfreeBufferArray(scip, &covered);
285 
286  return SCIP_OKAY;
287  }
288  }
289  assert( ncycles <= nvars / 2 );
290 
291  /* check for packing/partitioning type */
292  for (i = 0; i < nvars; ++i)
293  covered[i] = FALSE;
294 
295  /* compute cycle decomposition: row i stores in entry 0 the length of the cycle,
296  * the remaining entries are the coordinates in the cycle;
297  * store descent points as well if permutation is not monotone */
298  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition, ncycles) );
299  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &descentpoints, ndescentpoints) );
300  for (i = 0; i < ncycles; ++i)
301  {
302  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1) );
303  }
304 
305  curcycle = 0;
306  maxcyclelength = 0;
307  c = 0;
308  for (i = 0; i < nvars; ++i)
309  {
310  int cyclelength = 0;
311 
312  /* skip checked indices */
313  if ( covered[i] )
314  continue;
315 
316  j = i;
317  do
318  {
319  if ( perm[j] < j )
320  descentpoints[c++] = j;
321 
322  covered[j] = TRUE;
323  cycledecomposition[curcycle][++cyclelength] = j;
324  j = perm[j];
325  }
326  while ( j != i );
327 
328  cycledecomposition[curcycle][0] = cyclelength;
329  ++curcycle;
330 
331  if ( maxcyclelength < cyclelength )
332  maxcyclelength = cyclelength;
333  }
334  assert( c == ndescentpoints );
335 
336  /* permutation can be upgraded -> check whether the symresack is of packing/partitioning type */
337  setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
338  if ( setppcconshdlr == NULL )
339  {
340  SCIPerrorMessage("Setppc constraint handler not found.\n");
341  return SCIP_PLUGINNOTFOUND;
342  }
343  setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
344  nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
345 
346  /* Check whether each cycle of the symresack is contained in a set packing/partitioning constraint.
347  * To this end, we have to guarantee that all affected variables are not negated since permutations
348  * are given w.r.t. original variables. */
349  *upgrade = TRUE;
350 
351  SCIP_CALL( SCIPallocBufferArray(scip, &indicesincycle, maxcyclelength) );
352 
353  for (i = 0; i < ncycles && *upgrade && ! terminated; ++i)
354  {
355  int cyclelength;
356 
357  /* get indices of variables in current cycle */
358  for (j = 0; j < cycledecomposition[i][0]; ++ j)
359  {
360  var = vars[cycledecomposition[i][j + 1]];
361 
362  if ( SCIPvarIsNegated(var) )
363  {
364  terminated = TRUE;
365  break;
366  }
367 
368  indicesincycle[j] = SCIPvarGetProbindex(var);
369  }
370 
371  cyclelength = cycledecomposition[i][0];
372 
373  /* iterate over constraints
374  *
375  * @todo Improve the check by sorting the constraints in the setppcconss array
376  * by type and number of contained variables. */
377  for (c = 0; c < nsetppcconss; ++c)
378  {
379  int nsetppcvars;
380  SCIP_VAR** setppcvars;
381  int varidx;
382  int nfound = 0;
383  int k;
384 
385  /* check type */
386  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
387  continue;
388  assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING || SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING );
389 
390  /* get set packing/partitioning variables */
391  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
392 
393  /* skip empty constraints (might not have been removed by presolving yet) */
394  if ( nsetppcvars == 0 )
395  continue;
396  assert( nsetppcvars > 0 );
397 
398  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
399  assert( setppcvars != NULL );
400 
401  /* check whether all variables of the cycle are contained in setppc constraint */
402  for (j = 0; j < nsetppcvars && nfound < cyclelength; ++j)
403  {
404  var = setppcvars[j];
405 
406  if ( SCIPvarIsNegated(var) )
407  continue;
408 
409  varidx = SCIPvarGetProbindex(var);
410 
411  for (k = 0; k < cyclelength; ++k)
412  {
413  if ( varidx == indicesincycle[k] )
414  {
415  ++nfound;
416  break;
417  }
418  }
419  }
420  assert( nfound <= cyclelength );
421 
422  if ( nfound == cyclelength )
423  break;
424  }
425 
426  /* row is not contained in a set packing/partitioning constraint */
427  if ( c >= nsetppcconss )
428  *upgrade = FALSE;
429  }
430 
431  if ( *upgrade )
432  {
433  (*consdata)->ncycles = ncycles;
434  (*consdata)->cycledecomposition = cycledecomposition;
435  (*consdata)->ndescentpoints = ndescentpoints;
436  (*consdata)->descentpoints = descentpoints;
437  SCIPdebugMsg(scip, "added monotone PP symresack.\n");
438 
439  SCIPfreeBufferArray(scip, &indicesincycle);
440  SCIPfreeBufferArray(scip, &covered);
441  }
442  else
443  {
444  SCIPfreeBlockMemoryArray(scip, &descentpoints, ndescentpoints);
445  SCIPfreeBufferArray(scip, &indicesincycle);
446  SCIPfreeBufferArray(scip, &covered);
447  for (i = 0; i < ncycles; ++i)
448  {
449  SCIPfreeBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1);
450  }
451  SCIPfreeBlockMemoryArray(scip, &cycledecomposition, ncycles);
452  }
453 
454  return SCIP_OKAY;
455 }
456 
457 
458 /** creates symresack constraint data
459  *
460  * If the input data contains non-binary variables or fixed
461  * points, we delete these variables in a preprocessing step.
462  */
463 static
465  SCIP* scip, /**< SCIP data structure */
466  SCIP_CONSHDLR* conshdlr, /**< symresack constraint handler */
467  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
468  SCIP_VAR*const* inputvars, /**< input variables of the constraint handler */
469  int inputnvars, /**< input number of variables of the constraint handler*/
470  int* inputperm, /**< input permutation of the constraint handler */
471  SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
472  )
473 {
474  SCIP_CONSHDLRDATA* conshdlrdata;
475  SCIP_VAR** vars;
476  SCIP_Bool upgrade;
477  int* indexcorrection;
478  int* invperm;
479  int* perm;
480  int naffectedvariables;
481  int i;
482  int j = 0;
483 
484  assert( consdata != NULL );
485  assert( conshdlr != NULL );
486  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
487 
488  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
489 
490 #ifdef SCIP_DEBUG
491  (*consdata)->debugcnt = 0;
492 #endif
493 
494  (*consdata)->ndescentpoints = 0;
495  (*consdata)->descentpoints = NULL;
496  (*consdata)->ismodelcons = ismodelcons;
497 
498  /* count the number of binary variables which are affected by the permutation */
499  SCIP_CALL( SCIPallocBufferArray(scip, &indexcorrection, inputnvars) );
500  indexcorrection[0] = -1;
501  for (i = 0; i < inputnvars; ++i)
502  {
503  if ( inputperm[i] != i && SCIPvarIsBinary(inputvars[i]) )
504  {
505  if ( i == 0 )
506  indexcorrection[i] = 0;
507  else
508  indexcorrection[i] = indexcorrection[i - 1] + 1;
509  }
510  else
511  {
512  if ( i > 0 )
513  indexcorrection[i] = indexcorrection[i - 1];
514  }
515  }
516  naffectedvariables = indexcorrection[inputnvars - 1] + 1;
517 
518  (*consdata)->nvars = naffectedvariables;
519 
520  /* Stop if we detect that the permutation fixes each binary point. */
521  if ( naffectedvariables == 0 )
522  {
523  SCIPfreeBufferArrayNull(scip, &indexcorrection);
524 
525  (*consdata)->vars = NULL;
526  (*consdata)->perm = NULL;
527  (*consdata)->invperm = NULL;
528  (*consdata)->ppupgrade = FALSE;
529  (*consdata)->ncycles = 0;
530  (*consdata)->cycledecomposition = NULL;
531  return SCIP_OKAY;
532  }
533 
534  /* remove fixed points from permutation representation */
535  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, naffectedvariables) );
536  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &perm, naffectedvariables) );
537  for (i = 0; i < inputnvars; ++i)
538  {
539  if ( i == 0 )
540  {
541  if ( indexcorrection[i] > -1 )
542  {
543  vars[j] = inputvars[i];
544  perm[j++] = indexcorrection[inputperm[i]];
545  }
546  }
547  else
548  {
549  if ( indexcorrection[i] > indexcorrection[i - 1] )
550  {
551  vars[j] = inputvars[i];
552  perm[j++] = indexcorrection[inputperm[i]];
553  }
554  }
555  }
556  SCIPfreeBufferArrayNull(scip, &indexcorrection);
557 
558  (*consdata)->vars = vars;
559  (*consdata)->perm = perm;
560 
561  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &invperm, naffectedvariables) );
562  for (i = 0; i < naffectedvariables; ++i)
563  {
564  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i]) );
565  invperm[perm[i]] = i;
566  }
567  (*consdata)->invperm = invperm;
568 
569  /* check for upgrade to packing/partitioning symresacks*/
570  conshdlrdata = SCIPconshdlrGetData(conshdlr);
571  upgrade = FALSE;
572  if ( conshdlrdata->checkppsymresack )
573  {
574  SCIP_CALL( packingUpgrade(scip, consdata, perm, vars, naffectedvariables, conshdlrdata->checkmonotonicity, &upgrade) );
575  }
576 
577  (*consdata)->ppupgrade = upgrade;
578 
579  /* get transformed variables, if we are in the transformed problem */
580  if ( SCIPisTransformed(scip) )
581  {
582  /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_symresack, since one cannot
583  * easily eliminate single variables from a symresack constraint. */
584  for (i = 0; i < naffectedvariables; ++i)
585  {
586  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i], &(*consdata)->vars[i]) );
587  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i]) );
588  }
589  }
590 
591  return SCIP_OKAY;
592 }
593 
594 
595 /** generate initial LP cut
596  *
597  * We generate the ordering inequality for the pair \f$(1, \gamma^{-1}(1))\f$, i.e.,
598  * the inequality \f$-x_{1} + x_{\gamma^{-1}(1)} \leq 0\f$. This inequality is valid,
599  * because we guaranteed in a preprocessing step that all variables are binary.
600  *
601  * Furthermore, we add facet inequalities of packing/partitioning symresacks if
602  * we deal with packing/partitioning symresacks.
603  */
604 static
606  SCIP* scip, /**< SCIP pointer */
607  SCIP_CONS* cons, /**< constraint */
608  SCIP_Bool checkmonotonicity, /**< has it been checked whether permutation is monotone for packing/partitioning symresacks? */
609  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
610  )
611 {
612  SCIP_CONSDATA* consdata;
613  SCIP_VAR** vars;
614  SCIP_ROW* row;
615  int nvars;
616 #ifdef SCIP_DEBUG
617  char name[SCIP_MAXSTRLEN];
618 #endif
619  int i;
620  int j;
621  int k;
622 
623  assert( scip != NULL );
624  assert( cons != NULL );
625  assert( infeasible != NULL );
626 
627  *infeasible = FALSE;
628 
629  consdata = SCIPconsGetData(cons);
630  assert( consdata != NULL );
631 
632  nvars = consdata->nvars;
633 
634  /* avoid stupid problems */
635  if ( nvars <= 1 )
636  return SCIP_OKAY;
637 
638  assert( consdata->vars != NULL );
639  vars = consdata->vars;
640 
641  /* there are no fixed points */
642  assert( consdata->invperm[0] != 0 );
643 
644  /* add ordering inequality */
645 #ifdef SCIP_DEBUG
646  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_init_%s", SCIPconsGetName(cons));
647  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
648 #else
649  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
650 #endif
651  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[0], -1.0) );
652  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[consdata->invperm[0]], 1.0) );
653 
654  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
655 
656  SCIP_CALL( SCIPreleaseRow(scip, &row) );
657 
658  /* check whether we have a packing/partioning symresack */
659  if ( consdata->ppupgrade && ! *infeasible )
660  {
661  if ( checkmonotonicity )
662  {
663  SCIP_VAR** varsincons;
664  SCIP_Real* coeffs;
665  int** cycledecomposition;
666  int ncycles;
667  int nvarsincons;
668  int nvarsincycle;
669  int firstelemincycle;
670 
671  ncycles = consdata->ncycles;
672  cycledecomposition = consdata->cycledecomposition;
673 
674  SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
675  SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nvars) );
676 
677  coeffs[0] = 1.0;
678 
679  /* add packing/partitioning symresack constraints */
680  for (i = 0; i < ncycles; ++i)
681  {
682  assert( cycledecomposition[i][0] > 0 );
683 
684  nvarsincycle = cycledecomposition[i][0];
685  varsincons[0] = vars[cycledecomposition[i][nvarsincycle]];
686  firstelemincycle = cycledecomposition[i][1];
687 
688  assert( firstelemincycle == consdata->perm[cycledecomposition[i][nvarsincycle]] );
689 
690  nvarsincons = 1;
691 
692  /* add variables of other cycles to the constraint */
693  for (j = 0; j < i; ++j)
694  {
695  nvarsincycle = cycledecomposition[j][0];
696  for (k = 1; k <= nvarsincycle; ++k)
697  {
698  if ( cycledecomposition[j][k] < firstelemincycle )
699  {
700  varsincons[nvarsincons] = vars[cycledecomposition[j][k]];
701  coeffs[nvarsincons++] = -1.0;
702  }
703  else
704  continue;
705  }
706  }
707 
708 #ifdef SCIP_DEBUG
709  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", i, SCIPconsGetName(cons));
710  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
711 #else
712  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
713 #endif
714  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
715 
716  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
717  SCIP_CALL( SCIPreleaseRow(scip, &row) );
718 
719  if ( *infeasible )
720  break;
721  }
722 
723  SCIPfreeBufferArray(scip, &coeffs);
724  SCIPfreeBufferArray(scip, &varsincons);
725  }
726  else
727  {
728  SCIP_Real* coeffs;
729  SCIP_VAR** varsincons;
730  int* imgdescentpoints;
731  int* descentpoints;
732  int* perm;
733  int ndescentpoints;
734  int lastascent = 0;
735  int newlastascent = 0;
736  int nvarsincons = 1;
737 
738  descentpoints = consdata->descentpoints;
739  ndescentpoints = consdata->ndescentpoints;
740  perm = consdata->perm;
741 
742  assert( descentpoints != NULL );
743  assert( ndescentpoints > 0 );
744  assert( perm != NULL );
745  assert( vars != NULL );
746  assert( nvars > 0 );
747 
748  SCIP_CALL( SCIPallocBufferArray(scip, &imgdescentpoints, ndescentpoints) );
749 
750  /* get images of descentpoints */
751  for (j = 0; j < ndescentpoints; ++j)
752  imgdescentpoints[j] = perm[descentpoints[j]];
753 
754  /* sort descent points increasingly w.r.t. the corresponding image */
755  SCIPsortIntInt(imgdescentpoints, descentpoints, ndescentpoints);
756 
757  /* iteratively generate coefficient vector: the first entry is the descent point j and the remaining entries
758  * are the corresponding ascent points less than perm[j]
759  */
760  SCIP_CALL( SCIPallocClearBufferArray(scip, &coeffs, nvars) );
761  SCIP_CALL( SCIPallocClearBufferArray(scip, &varsincons, nvars) );
762  coeffs[0] = 1.0;
763  for (j = 0; j < ndescentpoints; ++j)
764  {
765  varsincons[0] = vars[descentpoints[j]];
766  for (i = lastascent; i < imgdescentpoints[j]; ++i)
767  {
768  if ( perm[i] > i )
769  {
770  coeffs[nvarsincons] = -1.0;
771  varsincons[nvarsincons++] = vars[i];
772  newlastascent = i;
773  }
774  }
775  lastascent = newlastascent;
776 
777 #ifdef SCIP_DEBUG
778  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", j, SCIPconsGetName(cons));
779  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
780 #else
781  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
782 #endif
783  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
784 
785  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
786  SCIP_CALL( SCIPreleaseRow(scip, &row) );
787 
788  if ( *infeasible )
789  break;
790  }
791 
792  SCIPfreeBufferArray(scip, &varsincons);
793  SCIPfreeBufferArray(scip, &coeffs);
794  SCIPfreeBufferArray(scip, &imgdescentpoints);
795  }
796  }
797 
798  return SCIP_OKAY;
799 }
800 
801 
802 /** Determines if a vector with additional fixings could exist that is lexicographically larger than its image.
803  *
804  * Given a vector of variables, a permutation, and a set of additional (virtual) fixings.
805  * If a vector adhering to the local variable bounds (local fixings) and to the virtual fixings exists,
806  * then infeasible is FALSE, otherwise TRUE.
807  */
808 static
810  SCIP* scip, /**< SCIP pointer */
811  SCIP_VAR** vars, /**< array of variables affected by permutation */
812  int* invperm, /**< inverse of permutation */
813  int nvars, /**< number of variables */
814  int start, /**< at which position to start (assuming previous positions are equal) */
815  int* tempfixings, /**< array with at entry i the virtual fixing of variable vars[i] */
816  int* tempfixentries, /**< the entries i that are virtually fixed until numfixentriesinit */
817  int numfixentriesinit, /**< the number of virtually fixed entries */
818  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected in these fixings */
819  int* infeasibleentry /**< pointer to store at which entry a (0, 1) pattern is found */
820 )
821 {
822  SCIP_VAR* var1;
823  SCIP_VAR* var2;
824  int var1fix;
825  int var2fix;
826 
827  int i;
828  int numfixentries;
829 
830  /* avoid trivial problems */
831  if ( nvars < 2 )
832  return SCIP_OKAY;
833 
834  assert( scip != NULL );
835  assert( vars != NULL );
836  assert( invperm != NULL );
837  assert( tempfixings != NULL );
838  assert( tempfixentries != NULL );
839  assert( infeasible != NULL );
840 
841  /* A counter for how many virtual fixings we have. */
842  numfixentries = numfixentriesinit;
843 
844  *infeasible = FALSE;
845 
846  for (i = start; i < nvars; ++i)
847  {
848  /* there are no fixed points */
849  assert( invperm[i] != i );
850 
851  /* get variables of first and second column */
852  var1 = vars[i];
853  var2 = vars[invperm[i]];
854 
855  assert( var1 != NULL );
856  assert( var2 != NULL );
857 
858  /* Get virtual fixing of variable in left column */
859  var1fix = tempfixings[i];
860  if ( var1fix == NOINIT )
861  {
862  if ( SCIPvarGetUbLocal(var1) < 0.5 )
863  {
864  var1fix = FIXED0;
865  assert( SCIPvarGetLbLocal(var1) <= 0.5 );
866  }
867  else if ( SCIPvarGetLbLocal(var1) > 0.5 )
868  var1fix = FIXED1;
869  else
870  var1fix = UNFIXED;
871  }
872  assert( var1fix != NOINIT );
873 
874  /* Get virtual fixing of variable in right column */
875  var2fix = tempfixings[invperm[i]];
876  if ( var2fix == NOINIT )
877  {
878  if ( SCIPvarGetUbLocal(var2) < 0.5 )
879  {
880  var2fix = FIXED0;
881  assert( SCIPvarGetLbLocal(var2) <= 0.5 );
882  }
883  else if ( SCIPvarGetLbLocal(var2) > 0.5 )
884  var2fix = FIXED1;
885  else
886  var2fix = UNFIXED;
887  }
888  assert( var2fix != NOINIT );
889 
890  /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). In all cases (1, 0) can be constructed. Thus feasible. */
891  if ( var1fix != FIXED0 && var2fix != FIXED1 )
892  break;
893  /* Encounter (0, 1). Infeasible. */
894  else if ( var1fix == FIXED0 && var2fix == FIXED1 )
895  {
896  *infeasible = TRUE;
897  *infeasibleentry = i;
898  break;
899  }
900  /* Encounter (0, _). Virtually fix var2 to 0. */
901  else if ( var1fix == FIXED0 && var2fix == UNFIXED )
902  {
903  tempfixings[invperm[i]] = FIXED0;
904  /* Mark that we have fixed invperm[i]. */
905  tempfixentries[numfixentries++] = invperm[i];
906  }
907  /* Encounter (_, 1). Virtually fix var1 to 1. */
908  else if(var1fix == UNFIXED && var2fix == FIXED1 )
909  {
910  tempfixings[i] = FIXED0;
911  /* Mark that we have fixed invperm[i]. */
912  tempfixentries[numfixentries++] = i;
913  }
914  /* Remaining cases are (0, 0) and (1, 1). In both cases: continue. */
915  }
916 
917  /* Undo virtual fixings made in this function */
918  for (i = numfixentriesinit; i < numfixentries; ++i)
919  {
920  tempfixings[tempfixentries[i]] = NOINIT;
921  tempfixentries[i] = 0;
922  }
923 
924  return SCIP_OKAY;
925 }
926 
927 
928 /** perform propagation of symresack constraint */
929 static
931  SCIP* scip, /**< SCIP pointer */
932  SCIP_CONS* cons, /**< constraint to be propagated */
933  SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */
934  int* ngen /**< pointer to store number of generated bound strengthenings */
935  )
936 {
937  SCIP_CONSDATA* consdata;
938  SCIP_VAR** vars;
939  int* invperm;
940  int nvars;
941  int i;
942  int r;
943  SCIP_VAR* var1;
944  SCIP_VAR* var2;
945  int var1fix;
946  int var2fix;
947  SCIP_Bool tightened;
948  SCIP_Bool peekinfeasible;
949  int peekinfeasibleentry;
950  int* tempfixings;
951  int* tempfixentries;
952 
953  assert( scip != NULL );
954  assert( cons != NULL );
955  assert( infeasible != NULL );
956  assert( ngen != NULL );
957 
958  SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons));
959 
960  *ngen = 0;
961  *infeasible = FALSE;
962 
963  /* get data of constraint */
964  consdata = SCIPconsGetData(cons);
965  assert( consdata != NULL );
966  nvars = consdata->nvars;
967 
968  /* avoid trivial problems */
969  if ( nvars < 2 )
970  return SCIP_OKAY;
971 
972  assert( consdata->vars != NULL );
973  assert( consdata->invperm != NULL );
974  vars = consdata->vars;
975  invperm = consdata->invperm;
976 
977  /* loop through all variables */
978  for (i = 0; i < nvars; ++i)
979  {
980  /* there are no fixed points */
981  assert( invperm[i] != i );
982 
983  /* get variables of first and second column */
984  var1 = vars[i];
985  var2 = vars[invperm[i]];
986  assert( var1 != NULL );
987  assert( var2 != NULL );
988 
989  /* Get the fixing status of the left column variable var1 */
990  if ( SCIPvarGetUbLocal(var1) < 0.5 )
991  {
992  var1fix = FIXED0;
993  assert( SCIPvarGetLbLocal(var1) <= 0.5 );
994  }
995  else if ( SCIPvarGetLbLocal(var1) > 0.5 )
996  var1fix = FIXED1;
997  else
998  var1fix = UNFIXED;
999 
1000  /* Get the fixing status of the right column variable var2 */
1001  if ( SCIPvarGetUbLocal(var2) < 0.5 )
1002  {
1003  var2fix = FIXED0;
1004  assert( SCIPvarGetLbLocal(var2) <= 0.5 );
1005  }
1006  else if ( SCIPvarGetLbLocal(var2) > 0.5 )
1007  var2fix = FIXED1;
1008  else
1009  var2fix = UNFIXED;
1010 
1011  /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). Check if (1, 1) or (0, 0) are possible, otherwise fix. */
1012  if ( var1fix != FIXED0 && var2fix != FIXED1 )
1013  {
1014  assert( SCIPvarGetUbLocal(var1) > 0.5 );
1015  assert( SCIPvarGetLbLocal(var2) < 0.5 );
1016 
1017  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1018  SCIPdebugMsg(scip, " -> node is feasible (could set pair to (1,0) and every earlier pair is constant).\n");
1019 
1020  if ( var1fix == UNFIXED || var2fix == UNFIXED )
1021  {
1022  /* Create arrays tempfixings and tempfixentries to store virtual fixings. */
1023  SCIP_CALL( SCIPallocCleanBufferArray(scip, &tempfixings, nvars) );
1024  SCIP_CALL( SCIPallocCleanBufferArray(scip, &tempfixentries, nvars) );
1025 
1026  if ( var1fix == UNFIXED )
1027  {
1028  assert( SCIPvarGetLbLocal(var1) < 0.5 );
1029 
1030  /* Peek whether a lexicographical larger-or-equal vector can be created with var1 fixed to 0 */
1031  SCIPdebugMsg(scip, " -> First entry is not fixed. Check if 0 is feasible.\n");
1032  tempfixings[i] = FIXED0;
1033  tempfixentries[0] = i;
1034  SCIP_CALL( checkFeasible(scip, vars, invperm, nvars, i, tempfixings, tempfixentries, 1,
1035  &peekinfeasible, &peekinfeasibleentry) );
1036 
1037  if ( peekinfeasible )
1038  {
1039  /* No feasible vector exists with var1 set to 0, so it must be a 1-fixing. */
1040  SCIPdebugMsg(scip, " -> First entry is not fixed. 0 is not feasible. Fixing to 1.\n");
1041  SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i + nvars * peekinfeasibleentry,
1042  FALSE, infeasible, &tightened) ); /*lint !e713*/
1043  assert( ! *infeasible );
1044 
1045  if ( tightened )
1046  ++(*ngen);
1047  }
1048 
1049  tempfixings[i] = NOINIT;
1050  tempfixentries[0] = 0;
1051  }
1052 
1053  if ( var2fix == UNFIXED )
1054  {
1055  assert( SCIPvarGetUbLocal(var2) > 0.5 );
1056 
1057  /* Peek whether a lexicographical larger-or-equal vector can be created with var2 fixed to 1 */
1058  SCIPdebugMsg(scip, " -> Second entry is not fixed. Check if 1 is feasible.\n");
1059  tempfixings[invperm[i]] = FIXED1;
1060  tempfixentries[0] = invperm[i];
1061  SCIP_CALL( checkFeasible(scip, vars, invperm, nvars, i, tempfixings, tempfixentries, 1,
1062  &peekinfeasible, &peekinfeasibleentry) );
1063 
1064  if ( peekinfeasible )
1065  {
1066  /* No feasible vector exists with var2 set to 1, so it must be a 1-fixing. */
1067  SCIPdebugMsg(scip, " -> Second entry is not fixed. 1 is not feasible. Fixing to 0.\n");
1068  SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i + nvars * peekinfeasibleentry,
1069  FALSE, infeasible, &tightened) ); /*lint !e713*/
1070  assert( ! *infeasible );
1071 
1072  if ( tightened )
1073  ++(*ngen);
1074  }
1075 
1076  tempfixings[invperm[i]] = NOINIT;
1077  tempfixentries[0] = 0;
1078  }
1079 
1080  SCIPfreeCleanBufferArray(scip, &tempfixentries);
1081  SCIPfreeCleanBufferArray(scip, &tempfixings);
1082  }
1083 
1084  /* Can stop here, because this row can become (1, 0). Therefore all next rows can take arbitrary values. */
1085  break;
1086  }
1087  /* Encounter (0, 1): If first part of variable pair fixed to 0 and second part is fixed to 1 */
1088  else if ( var1fix == FIXED0 && var2fix == FIXED1 )
1089  {
1090  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1091 
1092  SCIPdebugMsg(scip, " -> node infeasible (pair was fixed to (0,1) but there was no pair of type (1,0) before) ---> lexicographical order violated, infeasible.\n");
1093 
1094  /* perform conflict analysis */
1096  {
1098 
1099  for (r = 0; r <= i; ++r)
1100  {
1101  /* there are no fixed points */
1102  assert( invperm[r] != r );
1103 
1104  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[r]) );
1105  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[invperm[r]]) );
1106  }
1107 
1108  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1109  }
1110 
1111  *infeasible = TRUE;
1112  break;
1113  }
1114  /* Encounter (0, _): Fix second part to 0 */
1115  else if ( var1fix == FIXED0 && var2fix != FIXED0 )
1116  {
1117  assert( SCIPvarGetUbLocal(var1) < 0.5 );
1118  assert( SCIPvarGetLbLocal(var2) < 0.5 );
1119  assert( SCIPvarGetUbLocal(var2) > 0.5 );
1120 
1121  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1122 
1123  assert( SCIPvarGetLbLocal(var2) < 0.5 );
1124  SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
1125  assert( ! *infeasible );
1126 
1127  if ( tightened )
1128  ++(*ngen);
1129  }
1130  /* Encounter (_, 1): fix first part to 1 */
1131  else if ( var1fix != FIXED1 && var2fix == FIXED1 )
1132  {
1133  assert( SCIPvarGetLbLocal(var1) < 0.5 );
1134  assert( SCIPvarGetUbLocal(var1) > 0.5 );
1135  assert( SCIPvarGetLbLocal(var2) > 0.5 );
1136 
1137  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1138 
1139  assert( SCIPvarGetUbLocal(var1) > 0.5 );
1140  SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
1141  assert( ! *infeasible );
1142 
1143  if ( tightened )
1144  ++(*ngen);
1145  }
1146  /* Remaining cases are (0, 0) and (1, 1). In these cases we can continue! */
1147  }
1148 
1149  return SCIP_OKAY;
1150 }
1151 
1152 
1153 /** add symresack cover inequality */
1154 static
1156  SCIP* scip, /**< SCIP pointer */
1157  SCIP_CONS* cons, /**< constraint */
1158  int nvars, /**< number of variables */
1159  SCIP_VAR** vars, /**< variables */
1160  int* coeffs, /**< coefficient vector of inequality to be added */
1161  SCIP_Real rhs, /**< right-hand side of inequality to be added */
1162  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
1163  )
1164 {
1165  SCIP_ROW* row;
1166  int i;
1167 #ifdef SCIP_DEBUG
1168  SCIP_CONSDATA* consdata;
1169  char name[SCIP_MAXSTRLEN];
1170 #endif
1171 
1172  assert( scip != NULL );
1173  assert( cons != NULL );
1174  assert( nvars > 0 );
1175  assert( vars != NULL );
1176  assert( coeffs != NULL );
1177  assert( infeasible != NULL );
1178 
1179  *infeasible = FALSE;
1180 
1181 #ifdef SCIP_DEBUG
1182  consdata = SCIPconsGetData(cons);
1183  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_cover_%s_%d", SCIPconsGetName(cons), consdata->debugcnt);
1184  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
1185  ++consdata->debugcnt;
1186 #else
1187  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
1188 #endif
1189  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
1190 
1191  for (i = 0; i < nvars; ++i)
1192  {
1193  if ( coeffs[i] == 1 || coeffs[i] == -1 )
1194  {
1195  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], (SCIP_Real) coeffs[i]) );
1196  }
1197  }
1198  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
1199  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
1200  SCIP_CALL( SCIPreleaseRow(scip, &row) );
1201 
1202  return SCIP_OKAY;
1203 }
1204 
1205 
1206 /** Maximize a linear function on a "strict" symresack,
1207  * that is a symresack where we do not allow the solution x = gamma(x).
1208  */
1209 static
1211  SCIP* scip, /**< SCIP pointer */
1212  int nvars, /**< number of variables in symresack */
1213  SCIP_Real* objective, /**< the objective vector */
1214  int* perm, /**< the permutation (without fixed points) as an array */
1215  int* invperm, /**< the inverse permutation as an array */
1216  int* maxcrit, /**< pointer to the critical entry where optimality is found at */
1217  SCIP_Real* maxsoluval /**< pointer to store the optimal objective value */
1218  )
1219 {
1220  /* The maximal objective in every iteration. */
1221  SCIP_Real tmpobj;
1222  /* The new value of componentobj when combining two components. */
1223  SCIP_Real tmpnewcompobj;
1224  /* helperobj is the sum of all positive objective-sums for all components. */
1225  SCIP_Real helperobj = 0.0;
1226 
1227  int crit;
1228  int critinv;
1229  int i;
1230 
1231  /* For every vertex of degree < 2 we maintain componentends and componentobj. */
1232  int* componentends;
1233  SCIP_Real* componentobj;
1234 
1235  assert( scip != NULL );
1236  assert( nvars > 0 );
1237  assert( objective != NULL );
1238  assert( perm != NULL );
1239  assert( invperm != NULL );
1240  assert( maxcrit != NULL );
1241  assert( maxsoluval != NULL );
1242 
1243  /* The current best known critical entry and objective */
1244  *maxcrit = -1;
1245  *maxsoluval = -SCIP_DEFAULT_INFINITY;
1246 
1247  SCIP_CALL( SCIPallocBufferArray(scip, &componentends, nvars) );
1248  SCIP_CALL( SCIPallocBufferArray(scip, &componentobj, nvars) );
1249 
1250  /* Initialization: Every entry is a component in the graph,
1251  * having the corresponding objective
1252  */
1253  for (i = 0; i < nvars; ++i)
1254  {
1255  componentends[i] = i;
1256  componentobj[i] = objective[i];
1257  if ( SCIPisGT(scip, objective[i], 0.0) )
1258  helperobj += objective[i];
1259  }
1260 
1261  /* Iterate over all critical rows, and of the graph maintain the components on the vertices of degree < 2. */
1262  for (crit = 0; crit < nvars; ++crit)
1263  {
1264  critinv = invperm[crit];
1265 
1266  /* Do not allow fixed points. */
1267  assert( crit != critinv );
1268 
1269  /* If the other end of the component of crit is critinv, then crit cannot be a critical entry. */
1270  if ( componentends[crit] == critinv )
1271  continue;
1272 
1273  /* Compute objective for crit as critical entry. Update if it is better than the best found objective */
1274  tmpobj = helperobj;
1275  if ( SCIPisLT(scip, componentobj[crit], 0.0) )
1276  tmpobj += componentobj[crit];
1277  if ( SCIPisGT(scip, componentobj[critinv], 0.0) )
1278  tmpobj -= componentobj[critinv];
1279  if ( SCIPisGT(scip, tmpobj, *maxsoluval) )
1280  {
1281  *maxsoluval = tmpobj;
1282  *maxcrit = crit;
1283  }
1284 
1285  /* Update helperobj */
1286  tmpnewcompobj = componentobj[crit] + componentobj[critinv];
1287  if ( SCIPisGT(scip, componentobj[crit], 0.0) )
1288  helperobj -= componentobj[crit];
1289  if ( SCIPisGT(scip, componentobj[critinv], 0.0) )
1290  helperobj -= componentobj[critinv];
1291  if ( SCIPisGT(scip, tmpnewcompobj, 0.0) )
1292  helperobj += tmpnewcompobj;
1293 
1294  /* Update the objective of a component */
1295  componentobj[componentends[crit]] = tmpnewcompobj;
1296  componentobj[componentends[critinv]] = tmpnewcompobj;
1297 
1298  /* Connect the endpoints of the newly created path */
1299  if ( componentends[crit] == crit )
1300  {
1301  componentends[crit] = componentends[critinv];
1302  componentends[componentends[critinv]] = crit;
1303  }
1304  else
1305  {
1306  componentends[componentends[crit]] = componentends[critinv];
1307  componentends[componentends[critinv]] = componentends[crit];
1308  }
1309 
1310  /* Early termination criterion. helperobj is upper bound to tmpobj for every next iteration,
1311  * so if helperobj <= maxsoluval then we can terminate earlier.
1312  */
1313  if ( SCIPisGE(scip, *maxsoluval, helperobj) )
1314  break;
1315  }
1316 
1317  /* It is always possible to make the first entry critical. */
1318  assert( *maxcrit >= 0 );
1319 
1320  SCIPfreeBufferArray(scip, &componentobj);
1321  SCIPfreeBufferArray(scip, &componentends);
1322 
1323  return SCIP_OKAY;
1324 }
1325 
1326 
1327 /** For a symresack, determine a maximizer for optimizing linear function
1328  * over a symresack, where the critical entry is fixed.
1329  */
1330 static
1332  SCIP* scip, /**< SCIP pointer */
1333  int nvars, /**< number of variables in symresack */
1334  SCIP_Real* objective, /**< the objective vector */
1335  int* perm, /**< the permutation (without fixed points) as an array */
1336  int* invperm, /**< the inverse permutation as an array */
1337  int crit, /**< critical entry where optimality is found at */
1338  int* maxsolu /**< pointer to the optimal objective array */
1339  )
1340 {
1341  /* Compute to which components all entries belong. */
1342  int* entrycomponent;
1343  SCIP_Real* componentobjective;
1344 
1345  int i;
1346  int c;
1347 
1348  assert( scip != NULL );
1349  assert( nvars > 0 );
1350  assert( objective != NULL );
1351  assert( perm != NULL );
1352  assert( invperm != NULL );
1353  assert( maxsolu != NULL );
1354  assert( crit >= 0 );
1355  assert( crit <= nvars );
1356 
1357  SCIP_CALL( SCIPallocBufferArray(scip, &entrycomponent, nvars) );
1358  SCIP_CALL( SCIPallocBufferArray(scip, &componentobjective, nvars) );
1359 
1360  /* Initially: Everything forms its own component */
1361  for (i = 0; i < nvars; ++i)
1362  {
1363  entrycomponent[i] = i;
1364  componentobjective[i] = objective[i];
1365  }
1366  for (i = 0; i < crit; ++i)
1367  {
1368  /* The graph with arcs {i, invperm[i]} if i < c is a collection of paths, cycles and singletons.
1369  * Label the vertices to the lowest entry in the component, and store the value of that in this component.
1370  * Every inner while-loop labels one new vertex per iteration, and a vertex is relabeled exactly once.
1371  */
1372  if ( entrycomponent[i] < i )
1373  {
1374  /* This entry is already included in a component. */
1375  continue;
1376  }
1377 
1378  /* Follow the path forward: Take edges {c, invperm[c]} until c >= crit, or a cycle is found. */
1379  c = i;
1380  while( c < crit )
1381  {
1382  /* c < crit, so edge {c, invperm[c]} exists. Label invperm[c] as part of component of i */
1383  c = invperm[c];
1384 
1385  /* Stop if we find a cycle. */
1386  if ( entrycomponent[c] != c )
1387  break;
1388 
1389  entrycomponent[c] = i;
1390  componentobjective[i] += objective[c];
1391  }
1392 
1393  /* Follow the path backward: Take edges {c, perm[c]} until perm[c] >= crit, or a cycle is found. */
1394  c = perm[i];
1395  while( c < crit )
1396  {
1397  /* c < crit, so edge {c, invperm[c]} exists. Label c as part of component of i */
1398 
1399  /* Stop if we find a cycle. */
1400  if ( entrycomponent[c] != c )
1401  break;
1402 
1403  entrycomponent[c] = i;
1404  componentobjective[i] += objective[c];
1405  /* For next iteration: We do another step back */
1406  c = perm[c];
1407  }
1408  }
1409 
1410  /* Now fill the objective vector.
1411  * For the component containing crit, set the value to 1.
1412  * For the component contraining invperm[crit], set the value to 0.
1413  * For the other components, set the value to 1 if the objective sum is positive.
1414  * Otherwise to 0.
1415  */
1416  for (i = 0; i < nvars; ++i)
1417  {
1418  if ( entrycomponent[i] == entrycomponent[crit] )
1419  maxsolu[i] = 1;
1420  else if ( entrycomponent[i] == entrycomponent[invperm[crit]] )
1421  maxsolu[i] = 0;
1422  else if ( SCIPisGT(scip, componentobjective[entrycomponent[i]], 0.0) )
1423  maxsolu[i] = 1;
1424  else
1425  maxsolu[i] = 0;
1426  }
1427 
1428  SCIPfreeBufferArray(scip, &componentobjective);
1429  SCIPfreeBufferArray(scip, &entrycomponent);
1430 
1431  return SCIP_OKAY;
1432 }
1433 
1434 
1435 /** separate symresack cover inequalities
1436  *
1437  * We currently do NOT enter cuts into the pool.
1438  */
1439 static
1441  SCIP* scip, /**< SCIP pointer */
1442  SCIP_CONS* cons, /**< constraint */
1443  const SCIP_CONSDATA* consdata, /**< constraint data */
1444  SCIP_Real* vals, /**< solution values of variables */
1445  int* ngen, /**< pointer to store the number of separated covers */
1446  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
1447  )
1448 {
1449  SCIP_Real constobjective;
1450  SCIP_Real* sepaobjective;
1451  SCIP_Real maxsoluobj = 0.0;
1452  int* maxsolu;
1453  int* invperm;
1454  int* perm;
1455  int nvars;
1456  int maxcrit;
1457  int i;
1458 
1459  *infeasible = FALSE;
1460  *ngen = 0;
1461 
1462  assert( scip != NULL );
1463  assert( consdata != NULL );
1464 
1465  /* we do not have to take care of trivial constraints */
1466  if ( consdata->nvars < 2 )
1467  return SCIP_OKAY;
1468 
1469  assert( consdata->vars != NULL );
1470  assert( consdata->perm != NULL );
1471  assert( consdata->invperm != NULL );
1472  assert( infeasible != NULL );
1473  assert( ngen != NULL );
1474 
1475  nvars = consdata->nvars;
1476  perm = consdata->perm;
1477  invperm = consdata->invperm;
1478 
1479  /* initialize objective */
1480  SCIP_CALL( SCIPallocBufferArray(scip, &sepaobjective, nvars) );
1481 
1482  constobjective = 1.0; /* constant part of separation objective */
1483  for (i = 0; i < nvars; ++i)
1484  {
1485  if ( i < perm[i] )
1486  sepaobjective[i] = - vals[i];
1487  else
1488  {
1489  sepaobjective[i] = 1.0 - vals[i];
1490  constobjective += vals[i] - 1.0;
1491  }
1492  }
1493 
1494  /* allocate memory for temporary and global solution */
1495  SCIP_CALL( SCIPallocBufferArray(scip, &maxsolu, nvars) );
1496 
1497  /* Find critical row of a maximally violated cover */
1498  SCIP_CALL( maximizeObjectiveSymresackStrict(scip, nvars, sepaobjective, perm, invperm, &maxcrit, &maxsoluobj) );
1499  assert( maxcrit >= 0 );
1500  SCIPdebugMsg(scip, "Critical row %d found; Computing maximally violated cover.\n", maxcrit);
1501  SCIP_CALL( maximizeObjectiveSymresackCriticalEntry(scip, nvars, sepaobjective, perm, invperm, maxcrit, maxsolu) );
1502 
1503  /* Add constant to maxsoluobj to get the real objective */
1504  maxsoluobj += constobjective;
1505 
1506  /* Check whether the separation objective is positive, i.e., a violated cover was found. */
1507  if ( SCIPisEfficacious(scip, maxsoluobj) )
1508  {
1509  /* Now add the cut. Reuse array maxsolu as coefficient vector for the constraint. */
1510  SCIP_Real rhs = -1.0;
1511  for (i = 0; i < nvars; ++i)
1512  {
1513  if ( i < perm[i] )
1514  maxsolu[i] = -maxsolu[i];
1515  else
1516  {
1517  if ( maxsolu[i] == 0 )
1518  rhs += 1.0;
1519  maxsolu[i] = 1 - maxsolu[i];
1520  }
1521  }
1522 
1523  /* add cover inequality */
1524  SCIP_CALL( addSymresackInequality(scip, cons, nvars, consdata->vars, maxsolu, rhs, infeasible) );
1525 
1526  if ( ! *infeasible )
1527  ++(*ngen);
1528  }
1529 
1530  SCIPfreeBufferArrayNull(scip, &maxsolu);
1531  SCIPfreeBufferArrayNull(scip, &sepaobjective);
1532 
1533  return SCIP_OKAY;
1534 }
1535 
1536 
1537 /** check whether solution is feasible for symresacks */
1538 static
1540  SCIP* scip, /**< SCIP pointer */
1541  SCIP_CONS* cons, /**< constrained for which we check the solution */
1542  SCIP_SOL* sol, /**< solution to be checked */
1543  SCIP_RESULT* result, /**< pointer to store whether we detected infeasibility */
1544  SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
1545  )
1546 {
1547  SCIP_CONSDATA* consdata;
1548  SCIP_VAR** vars;
1549  int* invperm;
1550  int nvars;
1551  int i;
1552 
1553  assert( cons != NULL );
1554  consdata = SCIPconsGetData(cons);
1555  assert( consdata != NULL);
1556 
1557  /* we do not have to take care of trivial constraints */
1558  if ( consdata->nvars < 2 )
1559  return SCIP_OKAY;
1560 
1561  assert( consdata->vars != NULL );
1562  assert( consdata->invperm != NULL );
1563 
1564  SCIPdebugMsg(scip, "Check method for symresack constraint <%s> (%d rows) ...\n", SCIPconsGetName(cons), consdata->nvars);
1565 
1566  nvars = consdata->nvars;
1567  vars = consdata->vars;
1568  invperm = consdata->invperm;
1569 
1570  /* detect first non-constant pair of variables */
1571  for (i = 0; i < nvars; ++i)
1572  {
1573  SCIP_Real solval;
1574  int val1;
1575  int val2;
1576 
1577  /* there are no fixed points */
1578  assert( invperm[i] != i );
1579 
1580  /* get value of variable i and its inverse */
1581  solval = SCIPgetSolVal(scip, sol, vars[i]);
1582  assert( SCIPisFeasIntegral(scip, solval) );
1583  if ( solval > 0.5 )
1584  val1 = 1;
1585  else
1586  val1 = 0;
1587 
1588  solval = SCIPgetSolVal(scip, sol, vars[invperm[i]]);
1589  assert( SCIPisFeasIntegral(scip, solval) );
1590  if ( solval > 0.5 )
1591  val2 = 1;
1592  else
1593  val2 = 0;
1594 
1595  /* if we detected a constant pair */
1596  if ( val1 == val2 )
1597  continue;
1598  /* pair is (1,0) --> lexicographically maximal */
1599  else if ( val1 > val2 )
1600  break;
1601 
1602  /* pair is (0,1) --> solution is infeasible */
1603  assert( val2 > val1 );
1604  SCIPdebugMsg(scip, "Solution is infeasible.\n");
1605  *result = SCIP_INFEASIBLE;
1606 
1607  if ( printreason )
1608  SCIPinfoMessage(scip, NULL, "First non-constant pair (%d, %d) of variables has pattern (0,1).\n", i, invperm[i]);
1609 
1610  break;
1611  }
1612 
1613  return SCIP_OKAY;
1614 }
1615 
1616 
1617 /** Upgrade symresack constraints to orbisacks */
1618 static
1620  SCIP* scip, /**< SCIP pointer */
1621  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1622  const char* name, /**< name of constraint */
1623  int* perm, /**< permutation */
1624  SCIP_VAR** inputvars, /**< permuted variables array */
1625  int nvars, /**< size of perm array */
1626  SCIP_Bool* upgrade, /**< whether constraint was upgraded */
1627  SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
1628  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1629  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1630  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1631  * Usually set to TRUE. */
1632  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1633  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1634  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1635  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1636  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1637  * Usually set to TRUE. */
1638  SCIP_Bool local, /**< is constraint only valid locally?
1639  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1640  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1641  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1642  * adds coefficients to this constraint. */
1643  SCIP_Bool dynamic, /**< is constraint subject to aging?
1644  * Usually set to FALSE. Set to TRUE for own cuts which
1645  * are separated as constraints. */
1646  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1647  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1648  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1649  * if it may be moved to a more global node?
1650  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1651  )
1652 {
1653  SCIP_CONSHDLR* conshdlr;
1654  SCIP_VAR** vars1;
1655  SCIP_VAR** vars2;
1656  int nrows = 0;
1657  int i;
1658 
1659  assert( scip != NULL );
1660  assert( perm != NULL );
1661  assert( nvars > 0 );
1662  assert( inputvars != NULL );
1663  assert( upgrade != NULL );
1664 
1665  *upgrade = TRUE;
1666 
1667  /* check whether orbisack conshdlr is available */
1668  conshdlr = SCIPfindConshdlr(scip, "orbisack");
1669  if ( conshdlr == NULL )
1670  {
1671  *upgrade = FALSE;
1672  SCIPdebugMsg(scip, "Cannot check whether symresack constraint can be upgraded to orbisack constraint. ");
1673  SCIPdebugMsg(scip, "---> Orbisack constraint handler not found.\n");
1674 
1675  return SCIP_OKAY;
1676  }
1677 
1678  SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nvars) );
1679  SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nvars) );
1680 
1681  /* check whether permutation is a composition of 2-cycles */
1682  for (i = 0; i < nvars; ++i)
1683  {
1684  /* ignore non-binary variables */
1685  if ( ! SCIPvarIsBinary(inputvars[i]) )
1686  continue;
1687 
1688  if ( perm[perm[i]] != i )
1689  {
1690  *upgrade = FALSE;
1691  break;
1692  }
1693 
1694  if ( perm[i] > i )
1695  {
1696  vars1[nrows] = inputvars[i];
1697  vars2[nrows++] = inputvars[perm[i]];
1698 
1699  assert( nrows <= nvars );
1700  }
1701  }
1702 
1703  /* if permutation can be upgraded to an orbisack */
1704  if ( nrows == 0 )
1705  *upgrade = FALSE;
1706  else if ( *upgrade )
1707  {
1708  SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, ismodelcons,
1709  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1710  }
1711 
1712  SCIPfreeBufferArray(scip, &vars2);
1713  SCIPfreeBufferArray(scip, &vars1);
1714 
1715  return SCIP_OKAY;
1716 }
1717 
1718 
1719 /** creates a symmetry breaking constraint
1720  *
1721  * Depending on the given permutation, either an orbisack or symresack constraint
1722  * is created.
1723  */
1725  SCIP* scip, /**< SCIP data structure */
1726  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1727  const char* name, /**< name of constraint */
1728  int* perm, /**< permutation */
1729  SCIP_VAR** vars, /**< variables */
1730  int nvars, /**< number of variables in vars array */
1731  SCIP_Bool ismodelcons, /**< whether the added constraint is a model constraint */
1732  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1733  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1734  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1735  * Usually set to TRUE. */
1736  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1737  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1738  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1739  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1740  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1741  * Usually set to TRUE. */
1742  SCIP_Bool local, /**< is constraint only valid locally?
1743  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1744  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1745  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1746  * adds coefficients to this constraint. */
1747  SCIP_Bool dynamic, /**< is constraint subject to aging?
1748  * Usually set to FALSE. Set to TRUE for own cuts which
1749  * are separated as constraints. */
1750  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1751  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1752  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1753  * if it may be moved to a more global node?
1754  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1755  )
1756 {
1757  SCIP_Bool upgrade = FALSE;
1758 
1759  assert( scip != NULL );
1760  assert( cons != NULL );
1761  assert( perm != NULL );
1762  assert( vars != NULL );
1763  assert( nvars > 0 );
1764 
1765  SCIP_CALL( orbisackUpgrade(scip, cons, name, perm, vars, nvars, &upgrade, ismodelcons,
1766  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1767 
1768  if ( ! upgrade )
1769  {
1770  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
1771  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1772  }
1773 
1774  return SCIP_OKAY;
1775 }
1776 
1777 
1778 /*--------------------------------------------------------------------------------------------
1779  *--------------------------------- SCIP functions -------------------------------------------
1780  *--------------------------------------------------------------------------------------------*/
1781 
1782 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1783 static
1784 SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
1785 { /*lint --e{715}*/
1786  assert(scip != NULL);
1787  assert(conshdlr != NULL);
1788  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1789 
1790  /* call inclusion method of constraint handler */
1792 
1793  *valid = TRUE;
1794 
1795  return SCIP_OKAY;
1796 }
1797 
1798 
1799 /** frees specific constraint data */
1800 static
1801 SCIP_DECL_CONSDELETE(consDeleteSymresack)
1802 { /*lint --e{715}*/
1803  assert( scip != NULL );
1804  assert( conshdlr != NULL );
1805  assert( consdata != NULL );
1806  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1807 
1808  SCIP_CALL( consdataFree(scip, consdata) );
1809 
1810  return SCIP_OKAY;
1811 }
1812 
1813 
1814 /** frees constraint handler */
1815 static
1816 SCIP_DECL_CONSFREE(consFreeSymresack)
1817 { /*lint --e{715}*/
1818  SCIP_CONSHDLRDATA* conshdlrdata;
1819 
1820  assert( scip != NULL );
1821  assert( conshdlr != NULL );
1822  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1823 
1824  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1825  assert( conshdlrdata != NULL );
1826 
1827  SCIPfreeBlockMemory(scip, &conshdlrdata);
1828 
1829  return SCIP_OKAY;
1830 }
1831 
1832 
1833 /** transforms constraint data into data belonging to the transformed problem */
1834 static
1835 SCIP_DECL_CONSTRANS(consTransSymresack)
1837  SCIP_CONSDATA* sourcedata;
1838  SCIP_CONSDATA* consdata = NULL;
1839  int nvars;
1840  int i;
1841 
1842  assert( scip != NULL );
1843  assert( conshdlr != NULL );
1844  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1845  assert( sourcecons != NULL );
1846  assert( targetcons != NULL );
1847 
1848  SCIPdebugMsg(scip, "Transforming constraint.\n");
1849 
1850  /* get data of original constraint */
1851  sourcedata = SCIPconsGetData(sourcecons);
1852  assert( sourcedata != NULL);
1853 
1854  /* constraint might be empty and not deleted if no presolving took place */
1855  assert( sourcedata->nvars == 0 || sourcedata->vars != NULL );
1856  assert( sourcedata->nvars == 0 || sourcedata->perm != NULL );
1857  assert( sourcedata->nvars == 0 || sourcedata->invperm != NULL );
1858 #ifndef NDEBUG
1859  if ( sourcedata->ppupgrade )
1860  {
1861  assert( sourcedata->nvars > 0 );
1862  assert( sourcedata->ncycles != 0 );
1863  assert( sourcedata->cycledecomposition != NULL );
1864  for (i = 0; i < sourcedata->ncycles; ++i)
1865  {
1866  assert( sourcedata->cycledecomposition[i] != NULL );
1867  assert( sourcedata->cycledecomposition[i][0] != 0 );
1868  }
1869  }
1870 #endif
1871 
1872  /* create transformed constraint data
1873  *
1874  * do NOT call consdataCreate() again to avoid doing the packing-upgrade check twice
1875  */
1876  nvars = sourcedata->nvars;
1877 
1878  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1879 
1880  consdata->vars = NULL;
1881  consdata->nvars = nvars;
1882  consdata->perm = NULL;
1883  consdata->invperm = NULL;
1884  consdata->ppupgrade = sourcedata->ppupgrade;
1885  consdata->ismodelcons = sourcedata->ismodelcons;
1886 #ifdef SCIP_DEBUG
1887  consdata->debugcnt = 0;
1888 #endif
1889  consdata->ncycles = 0;
1890  consdata->cycledecomposition = NULL;
1891  consdata->ndescentpoints = 0;
1892  consdata->descentpoints = NULL;
1893 
1894  if ( nvars > 0 )
1895  {
1896  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) );
1897  SCIP_CALL( SCIPgetTransformedVars(scip, nvars, sourcedata->vars, consdata->vars) );
1898  for (i = 0; i < nvars; ++i)
1899  {
1900  SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
1901  }
1902 
1903  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->perm, sourcedata->perm, nvars) );
1904  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->invperm, sourcedata->invperm, nvars) );
1905 
1906  if ( sourcedata->ppupgrade )
1907  {
1908  consdata->ncycles = sourcedata->ncycles;
1909  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition, sourcedata->cycledecomposition, sourcedata->ncycles) );
1910  for (i = 0; i < sourcedata->ncycles; ++i)
1911  {
1912  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition[i], sourcedata->cycledecomposition[i], nvars + 1) ); /*lint !e866*/
1913  }
1914 
1915  consdata->ndescentpoints = sourcedata->ndescentpoints;
1916  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->descentpoints, sourcedata->descentpoints, sourcedata->ndescentpoints) );
1917  }
1918 
1919  /* Make sure that all variables cannot be multiaggregated (this cannot be handled by cons_symresack, since one cannot
1920  * easily eliminate single variables from a symresack constraint).
1921  *
1922  * We need to call this again to ensure that multiaggregation is forbidden also if the constraint was part
1923  * of the original problem.
1924  */
1925  for (i = 0; i < sourcedata->nvars; ++i)
1926  {
1927  SCIP_CALL( SCIPgetTransformedVar(scip, consdata->vars[i], &consdata->vars[i]) );
1928  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, consdata->vars[i]) );
1929  }
1930  }
1931 
1932  /* create transformed constraint */
1933  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1934  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1935  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1936  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1937  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1938  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1939 
1940  return SCIP_OKAY;
1941 }
1942 
1943 
1944 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1945 static
1946 SCIP_DECL_CONSINITLP(consInitlpSymresack)
1948  int c;
1949  SCIP_CONSHDLRDATA* conshdlrdata;
1950 
1951  assert( infeasible != NULL );
1952  *infeasible = FALSE;
1953 
1954  assert( scip != NULL );
1955  assert( conshdlr != NULL );
1956  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1957 
1958  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1959  assert( conshdlrdata != NULL );
1960 
1961  /* loop through constraints */
1962  for (c = 0; c < nconss; ++c)
1963  {
1964  assert( conss[c] != NULL );
1965 
1966  SCIPdebugMsg(scip, "Generating initial symresack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1967 
1968  SCIP_CALL( initLP(scip, conss[c], conshdlrdata->checkmonotonicity, infeasible) );
1969  if ( *infeasible )
1970  break;
1971  }
1972  SCIPdebugMsg(scip, "Generated initial symresack cuts.\n");
1973 
1974  return SCIP_OKAY;
1975 }
1976 
1977 
1978 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1979 static
1980 SCIP_DECL_CONSINITSOL(consInitsolSymresack)
1982  SCIP_CONSHDLRDATA* conshdlrdata;
1983  int c;
1984 
1985  assert( scip != NULL );
1986  assert( conshdlr != NULL );
1987  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1988 
1989  /* determine maximum number of vars in a symresack constraint */
1990  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1991  assert( conshdlrdata != NULL );
1992 
1993  conshdlrdata->maxnvars = 0;
1994 
1995  /* loop through constraints */
1996  for (c = 0; c < nconss; ++c)
1997  {
1998  SCIP_CONSDATA* consdata;
1999 
2000  assert( conss[c] != NULL );
2001 
2002  consdata = SCIPconsGetData(conss[c]);
2003  assert( consdata != NULL );
2004 
2005  /* update conshdlrdata if necessary */
2006  if ( consdata->nvars > conshdlrdata->maxnvars )
2007  conshdlrdata->maxnvars = consdata->nvars;
2008  }
2009 
2010  return SCIP_OKAY;
2011 }
2012 
2013 
2014 /** separation method of constraint handler for LP solution */
2015 static
2016 SCIP_DECL_CONSSEPALP(consSepalpSymresack)
2017 { /*lint --e{715}*/
2018  SCIP_CONSHDLRDATA* conshdlrdata;
2019  SCIP_CONSDATA* consdata;
2020  SCIP_Real* vals;
2021  int maxnvars;
2022  int c;
2023 
2024  assert( scip != NULL );
2025  assert( conshdlr != NULL );
2026  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2027  assert( result != NULL );
2028 
2029  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
2030 
2031  *result = SCIP_DIDNOTRUN;
2032 
2033  /* if solution is not integer */
2034  if ( SCIPgetNLPBranchCands(scip) == 0 )
2035  return SCIP_OKAY;
2036 
2037  if ( nconss == 0 )
2038  return SCIP_OKAY;
2039 
2040  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2041  assert( conshdlrdata != NULL );
2042 
2043  maxnvars = conshdlrdata->maxnvars;
2044  assert( maxnvars > 0 );
2045 
2046  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2047 
2048  /* loop through constraints */
2049  for (c = 0; c < nconss; ++c)
2050  {
2051  SCIP_Bool infeasible = FALSE;
2052  int ngen = 0;
2053 
2054  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2055 
2056  /* get data of constraint */
2057  assert( conss[c] != NULL );
2058  consdata = SCIPconsGetData(conss[c]);
2059 
2060  if ( consdata->nvars == 0 )
2061  continue;
2062 
2063  /* get solution */
2064  assert( consdata->nvars <= maxnvars );
2065  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
2066  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2067 
2068  if ( infeasible )
2069  {
2070  *result = SCIP_CUTOFF;
2071  SCIPfreeBufferArray(scip, &vals);
2072 
2073  return SCIP_OKAY;
2074  }
2075 
2076  if ( ngen > 0 )
2077  *result = SCIP_SEPARATED;
2078 
2079  if ( *result == SCIP_DIDNOTRUN )
2080  *result = SCIP_DIDNOTFIND;
2081  }
2082  SCIPfreeBufferArray(scip, &vals);
2083 
2084  return SCIP_OKAY;
2085 }
2086 
2087 
2088 /** separation method of constraint handler for arbitrary primal solution */
2089 static
2090 SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
2091 { /*lint --e{715}*/
2092  SCIP_CONSHDLRDATA* conshdlrdata;
2093  SCIP_CONSDATA* consdata;
2094  SCIP_Real* vals;
2095  int maxnvars;
2096  int c;
2097 
2098  assert( scip != NULL );
2099  assert( conshdlr != NULL );
2100  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2101  assert( result != NULL );
2102 
2103  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
2104 
2105  *result = SCIP_DIDNOTRUN;
2106 
2107  if ( nconss == 0 )
2108  return SCIP_OKAY;
2109 
2110  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2111  assert( conshdlrdata != NULL );
2112 
2113  maxnvars = conshdlrdata->maxnvars;
2114  assert( maxnvars > 0 );
2115 
2116  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2117 
2118  /* loop through constraints */
2119  for (c = 0; c < nconss; ++c)
2120  {
2121  SCIP_Bool infeasible = FALSE;
2122  int ngen = 0;
2123 
2124  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2125 
2126  /* get data of constraint */
2127  assert( conss[c] != NULL );
2128  consdata = SCIPconsGetData(conss[c]);
2129 
2130  if ( consdata->nvars == 0 )
2131  continue;
2132 
2133  /* get solution */
2134  assert( consdata->nvars <= maxnvars );
2135  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
2136  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2137 
2138  if ( infeasible )
2139  {
2140  *result = SCIP_CUTOFF;
2141  SCIPfreeBufferArray(scip, &vals);
2142 
2143  return SCIP_OKAY;
2144  }
2145 
2146  if ( ngen > 0 )
2147  *result = SCIP_SEPARATED;
2148 
2149  if ( *result == SCIP_DIDNOTRUN )
2150  *result = SCIP_DIDNOTFIND;
2151  }
2152  SCIPfreeBufferArray(scip, &vals);
2153 
2154  return SCIP_OKAY;
2155 }
2156 
2157 
2158 /** constraint enforcing method of constraint handler for LP solutions.
2159  *
2160  * To check feasibility, we separate cover inequalities.
2161  *
2162  * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
2163  */
2164 static
2165 SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
2166 { /*lint --e{715}*/
2167  SCIP_CONSDATA* consdata;
2168  int c;
2169 
2170  assert( scip != NULL );
2171  assert( conshdlr != NULL );
2172  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2173  assert( result != NULL );
2174 
2175  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (lp solutions) ...\n");
2176 
2177  /* we have a negative priority, so we should come after the integrality conshdlr. */
2178  assert( SCIPgetNLPBranchCands(scip) == 0 );
2179 
2180  *result = SCIP_FEASIBLE;
2181 
2182  if ( nconss > 0 )
2183  {
2184  SCIP_CONSHDLRDATA* conshdlrdata;
2185  SCIP_Real* vals;
2186  int maxnvars;
2187 
2188  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2189  assert( conshdlrdata != NULL );
2190 
2191  maxnvars = conshdlrdata->maxnvars;
2192  assert( maxnvars > 0 );
2193 
2194  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2195 
2196  /* loop through constraints */
2197  for (c = 0; c < nconss; ++c)
2198  {
2199  SCIP_Bool infeasible = FALSE;
2200  int ngen = 0;
2201 
2202  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2203 
2204  /* get data of constraint */
2205  assert( conss[c] != NULL );
2206  consdata = SCIPconsGetData(conss[c]);
2207  assert( consdata != NULL );
2208 
2209  /* do not enforce non-model constraints */
2210  if ( !consdata->ismodelcons )
2211  continue;
2212 
2213  if ( consdata->nvars == 0 )
2214  continue;
2215 
2216  /* get solution */
2217  assert( consdata->nvars <= maxnvars );
2218  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
2219  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2220 
2221  if ( infeasible )
2222  {
2223  *result = SCIP_CUTOFF;
2224  SCIPfreeBufferArray(scip, &vals);
2225 
2226  return SCIP_OKAY;
2227  }
2228 
2229  /* SCIPdebugMsg(scip, "Generated symresack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); */
2230 
2231  if ( ngen > 0 )
2232  *result = SCIP_SEPARATED;
2233  }
2234  SCIPfreeBufferArray(scip, &vals);
2235  }
2236 
2237  return SCIP_OKAY;
2238 }
2239 
2240 
2241 /** constraint enforcing method of constraint handler for pseudo solutions */
2242 static
2243 SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
2244 { /*lint --e{715}*/
2245  SCIP_CONSDATA* consdata;
2246  int c;
2247 
2248  assert( scip != NULL );
2249  assert( conshdlr != NULL );
2250  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2251  assert( result != NULL );
2252 
2253  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (pseudo solutions) ...\n");
2254 
2255  *result = SCIP_FEASIBLE;
2256 
2257  if ( objinfeasible || solinfeasible )
2258  return SCIP_OKAY;
2259 
2260  /* loop through constraints */
2261  for (c = 0; c < nconss; ++c)
2262  {
2263  consdata = SCIPconsGetData(conss[c]);
2264  assert( consdata != NULL );
2265 
2266  /* do not enforce non-model constraints */
2267  if ( !consdata->ismodelcons )
2268  continue;
2269 
2270  SCIP_CALL( checkSymresackSolution(scip, conss[c], NULL, result, FALSE) );
2271 
2272  if ( *result == SCIP_INFEASIBLE )
2273  break;
2274  }
2275 
2276  return SCIP_OKAY;
2277 }
2278 
2279 
2280 /** constraint enforcing method of constraint handler for relaxation solutions
2281  *
2282  * To check feasibility, we separate cover inequalities.
2283  *
2284  */
2285 static
2286 SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
2287 { /*lint --e{715}*/
2288  SCIP_CONSDATA* consdata;
2289  int c;
2290 
2291  assert( scip != NULL );
2292  assert( conshdlr != NULL );
2293  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2294  assert( result != NULL );
2295 
2296  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (relaxation solutions) ...\n");
2297 
2298  /* we have a negative priority, so we should come after the integrality conshdlr. */
2299  assert( SCIPgetNLPBranchCands(scip) == 0 );
2300 
2301  *result = SCIP_FEASIBLE;
2302 
2303  if ( nconss > 0 )
2304  {
2305  SCIP_CONSHDLRDATA* conshdlrdata;
2306  SCIP_Real* vals;
2307  int maxnvars;
2308 
2309  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2310  assert( conshdlrdata != NULL );
2311 
2312  maxnvars = conshdlrdata->maxnvars;
2313  assert( maxnvars > 0 );
2314 
2315  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2316 
2317  /* loop through constraints */
2318  for (c = 0; c < nconss; ++c)
2319  {
2320  SCIP_Bool infeasible = FALSE;
2321  int ngen = 0;
2322 
2323  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2324 
2325  /* get data of constraint */
2326  assert( conss[c] != NULL );
2327  consdata = SCIPconsGetData(conss[c]);
2328  assert( consdata != NULL );
2329 
2330  /* do not enforce non-model constraints */
2331  if ( !consdata->ismodelcons )
2332  continue;
2333 
2334  if ( consdata->nvars == 0 )
2335  continue;
2336 
2337  /* get solution */
2338  assert( consdata->nvars <= maxnvars );
2339  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
2340  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2341 
2342  if ( infeasible )
2343  {
2344  *result = SCIP_CUTOFF;
2345  SCIPfreeBufferArray(scip, &vals);
2346 
2347  return SCIP_OKAY;
2348  }
2349 
2350  if ( ngen > 0 )
2351  *result = SCIP_SEPARATED;
2352  }
2353  SCIPfreeBufferArray(scip, &vals);
2354  }
2355 
2356  return SCIP_OKAY;
2357 }
2358 
2359 
2360 /** feasibility check method of constraint handler for integral solutions */
2361 static
2362 SCIP_DECL_CONSCHECK(consCheckSymresack)
2363 { /*lint --e{715}*/
2364  SCIP_CONSDATA* consdata;
2365  int c;
2366 
2367  assert( scip != NULL );
2368  assert( conshdlr != NULL );
2369  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2370  assert( result != NULL );
2371 
2372  *result = SCIP_FEASIBLE;
2373 
2374  /* loop through constraints */
2375  for (c = 0; c < nconss; ++c)
2376  {
2377  consdata = SCIPconsGetData(conss[c]);
2378  assert( consdata != NULL );
2379 
2380  /* do not check non-model constraints */
2381  if ( !consdata->ismodelcons )
2382  continue;
2383 
2384  SCIP_CALL( checkSymresackSolution(scip, conss[c], sol, result, printreason) );
2385 
2386  if ( *result == SCIP_INFEASIBLE )
2387  break;
2388  }
2389 
2390  if ( *result == SCIP_FEASIBLE )
2391  SCIPdebugMsg(scip, "Solution is feasible.\n");
2392 
2393  return SCIP_OKAY;
2394 }
2395 
2396 
2397 /** domain propagation method of constraint handler */
2398 static
2399 SCIP_DECL_CONSPROP(consPropSymresack)
2400 { /*lint --e{715}*/
2401  int c;
2402  SCIP_Bool success = FALSE;
2403 
2404  assert( scip != NULL );
2405  assert( conshdlr != NULL );
2406  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2407  assert( result != NULL );
2408 
2409  *result = SCIP_DIDNOTRUN;
2410 
2411  SCIPdebugMsg(scip, "Propagation method of symresack constraint handler.\n");
2412 
2413  /* loop through constraints */
2414  for (c = 0; c < nconss; ++c)
2415  {
2416  SCIP_Bool infeasible = FALSE;
2417  int ngen = 0;
2418 
2419  assert( conss[c] != NULL );
2420 
2421  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2422 
2423  if ( infeasible )
2424  {
2425  *result = SCIP_CUTOFF;
2426  return SCIP_OKAY;
2427  }
2428 
2429  success = success || ( ngen > 0 );
2430 
2431  *result = SCIP_DIDNOTFIND;
2432  }
2433 
2434  if ( success )
2435  {
2436  *result = SCIP_REDUCEDDOM;
2437  return SCIP_OKAY;
2438  }
2439 
2440  return SCIP_OKAY;
2441 }
2442 
2443 
2444 /** presolving method of constraint handler */
2445 static
2446 SCIP_DECL_CONSPRESOL(consPresolSymresack)
2447 { /*lint --e{715}*/
2448  int c;
2449  SCIP_Bool success = FALSE;
2450  int oldndelconss;
2451 
2452  assert( scip != NULL );
2453  assert( conshdlr != NULL );
2454  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2455  assert( result != NULL );
2456 
2457  oldndelconss = *ndelconss;
2458 
2459  SCIPdebugMsg(scip, "Presolving method of symresack constraint handler. Propagating symresack inequalities.\n");
2460  *result = SCIP_DIDNOTRUN;
2461 
2462  /* loop through constraints */
2463  for (c = 0; c < nconss; ++c)
2464  {
2465  SCIP_Bool infeasible = FALSE;
2466  SCIP_CONSDATA* consdata;
2467  int ngen = 0;
2468 
2469  assert( conss[c] != NULL );
2470 
2471  consdata = SCIPconsGetData(conss[c]);
2472  assert( consdata != NULL );
2473 
2474  /* avoid trivial problems */
2475  if ( consdata->nvars == 0 )
2476  {
2477  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2478  (*ndelconss)++;
2479  }
2480  else
2481  {
2482  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2483  }
2484 
2485  if ( infeasible )
2486  {
2487  *result = SCIP_CUTOFF;
2488  break;
2489  }
2490 
2491  if ( ngen > 0 )
2492  {
2493  *nfixedvars += ngen;
2494  success = TRUE;
2495  }
2496 
2497  *result = SCIP_DIDNOTFIND;
2498  }
2499 
2500  if ( *ndelconss > oldndelconss || success )
2501  *result = SCIP_SUCCESS;
2502 
2503  return SCIP_OKAY;
2504 }
2505 
2506 
2507 /** Propagation resolution for conflict analysis */
2508 static
2509 SCIP_DECL_CONSRESPROP(consRespropSymresack)
2510 { /*lint --e{715}*/
2511  SCIP_CONSDATA* consdata;
2512  SCIP_VAR** vars;
2513  int* perm;
2514  int* invperm;
2515  int nvars;
2516  int i;
2517  int varrow;
2518  int infrow;
2519 
2520  assert( scip != NULL );
2521  assert( conshdlr != NULL );
2522  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2523  assert( cons != NULL );
2524  assert( infervar != NULL );
2525  assert( bdchgidx != NULL );
2526  assert( result != NULL );
2527 
2528  SCIPdebugMsg(scip, "Propagation resolution method of symresack constraint handler.\n");
2529 
2530  *result = SCIP_DIDNOTFIND;
2531 
2532  consdata = SCIPconsGetData(cons);
2533  assert( consdata != NULL );
2534 
2535  /* we do not have to take care of trivial constraints */
2536  if ( consdata->nvars < 2 )
2537  return SCIP_OKAY;
2538 
2539  assert( consdata->vars != NULL );
2540  assert( consdata->invperm != NULL );
2541 
2542  vars = consdata->vars;
2543  nvars = consdata->nvars;
2544  perm = consdata->perm;
2545  invperm = consdata->invperm;
2546 
2547  /* inferinfo == varrow + infrow * nvars.
2548  * infrow is 0 if the fixing is not caused by a lookahead.
2549  */
2550  varrow = inferinfo % nvars;
2551  infrow = inferinfo / nvars;
2552 
2553  assert( varrow >= 0 );
2554  assert( varrow < nvars );
2555  assert( infrow >= 0 );
2556  assert( infrow < nvars );
2557  assert( vars[varrow] == infervar || vars[invperm[varrow]] == infervar );
2558 
2559  /* Up to entry varrow the vectors x and perm[x] are equal. */
2560  for (i = 0; i < varrow; ++i)
2561  {
2562  /* Conflict caused by bounds of x[i] and perm(x)[i] = x[invperm[i]]. */
2563 
2564  /* No fixed points in the permutation. */
2565  assert( i != invperm[i] );
2566 
2567  /* Up to entry varrow the vectors x and perm[x] are fixed to the same value. */
2568  assert( ISFIXED(vars[i], bdchgidx) );
2569  assert( ISFIXED(vars[invperm[i]], bdchgidx) );
2570  assert( REALABS(SCIPvarGetUbAtIndex(vars[i], bdchgidx, FALSE) -
2571  SCIPvarGetUbAtIndex(vars[invperm[i]], bdchgidx, FALSE)) < 0.5 );
2572  assert( REALABS(SCIPvarGetLbAtIndex(vars[i], bdchgidx, FALSE) -
2573  SCIPvarGetLbAtIndex(vars[invperm[i]], bdchgidx, FALSE)) < 0.5 );
2574 
2575  /* At iteration i the vars x[i] and x[invperm[i]] are fixed.
2576  * So only new information is received if i < perm[i] (i.e. there is no j < i with j = invperm[i])
2577  * Or if invperm[i] > i.
2578  */
2579  if ( i < perm[i] )
2580  {
2581  assert( vars[i] != infervar );
2582  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2583  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2584  }
2585  if ( invperm[i] > i )
2586  {
2587  assert( vars[invperm[i]] != infervar );
2588  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2589  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2590  }
2591  }
2592 
2593  /* Case distinction: Fixing due to propagation or due to lookahead */
2594  if ( infrow > 0 )
2595  {
2596  /* The fixing of infervar is caused by a lookahead (checkFeasible)
2597  * Up to row "varrow" the entries x[i] and perm(x)[i] are forced to be equal
2598  * If x[varrow] = perm(x)[varrow] is assumed, then until infrow we find x[i] = perm(x)[i] ( = x[invperm[i]] )
2599  * and (x[infrow], perm(x)[infrow]) = (0, 1).
2600  */
2601 
2602  /* Everything after varrow to infrow is forced to a constant, and row infrow is (0, 1) */
2603  for (i = varrow + 1; i <= infrow; ++i)
2604  {
2605  /* Conflict caused by bounds of x[i] and perm(x)[i] = x[invperm[i]]. */
2606 
2607  /* No fixed points in the permutation. */
2608  assert( i != invperm[i] );
2609 
2610  /* The fixing are applied 'virtually', i.e. if varrow is considered constant, then fixings will follow.
2611  * Thus, between entries varrow and infrow of vectorx x and gamma(x) the entries do not have to be fixed.
2612  * For conflict analysis, only the fixed entries matter.
2613  */
2614  if ( ( i < perm[i] || i == invperm[varrow] ) && ISFIXED(vars[i], bdchgidx) )
2615  {
2616  assert( vars[i] != infervar );
2617  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2618  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2619  }
2620  if ( ( invperm[i] > i || invperm[i] == varrow ) && ISFIXED(vars[invperm[i]], bdchgidx) )
2621  {
2622  assert( vars[invperm[i]] != infervar );
2623  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2624  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2625  }
2626  }
2627  }
2628  else
2629  {
2630  /* This is not a fixing caused by lookahead (checkFeasible),
2631  * so row "varrow" was (0, _) or (_, 1) and for i < varrow x[i] = perm(x)[i].
2632  */
2633  if ( boundtype == SCIP_BOUNDTYPE_LOWER )
2634  {
2635  /* Changed the lower bound of infervar to 1. That means that this fixing is due to (_, 1) */
2636  assert( infervar == vars[varrow] );
2637  assert( ISFIXED(vars[invperm[varrow]], bdchgidx) );
2638 
2639  if ( invperm[varrow] > varrow )
2640  {
2641  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[varrow]], bdchgidx) );
2642  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[varrow]], bdchgidx) );
2643  }
2644  }
2645  else
2646  {
2647  /* Changed the lower bound of infervar to 0. That means that this fixing is due to (0, _) */
2648  assert( infervar == vars[invperm[varrow]] );
2649  assert( ISFIXED(vars[varrow], bdchgidx) );
2650 
2651  if ( varrow < perm[varrow] )
2652  {
2653  SCIP_CALL( SCIPaddConflictUb(scip, vars[varrow], bdchgidx) );
2654  SCIP_CALL( SCIPaddConflictLb(scip, vars[varrow], bdchgidx) );
2655  }
2656  }
2657  }
2658 
2659  *result = SCIP_SUCCESS;
2660 
2661  return SCIP_OKAY;
2662 }
2663 
2664 
2665 /** lock variables
2666  *
2667  * We assume we have only one global (void) constraint and lock all binary variables
2668  * which do not correspond to fixed points of the permutation.
2669  *
2670  * - Symresack constraints may get violated if the variables with a negative coefficient
2671  * in the FD inequality are rounded down, we therefor call
2672  * SCIPaddVarLocksType(..., nlockspos, nlocksneg).
2673  * - Symresack constraints may get violated if the variables with a positive coefficient
2674  * in the FD inequality are rounded up, we therefor call
2675  * SCIPaddVarLocksType(..., nlocksneg, nlockspo ).
2676  */
2677 static
2678 SCIP_DECL_CONSLOCK(consLockSymresack)
2679 { /*lint --e{715}*/
2680  SCIP_CONSDATA* consdata;
2681  SCIP_VAR** vars;
2682  int* perm;
2683  int nvars;
2684  int i;
2685 
2686  assert( scip != NULL );
2687  assert( conshdlr != NULL );
2688  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2689  assert( cons != NULL );
2690 
2691  SCIPdebugMsg(scip, "Locking method for symresack constraint handler.\n");
2692 
2693  /* get data of original constraint */
2694  consdata = SCIPconsGetData(cons);
2695  assert( consdata != NULL );
2696 
2697  /* we do not have to take care of trivial constraints */
2698  if ( consdata->nvars < 2 )
2699  return SCIP_OKAY;
2700 
2701  assert( consdata->vars != NULL );
2702  assert( consdata->perm != NULL );
2703 
2704  nvars = consdata->nvars;
2705  vars = consdata->vars;
2706  perm = consdata->perm;
2707 
2708  for (i = 0; i < nvars; ++i)
2709  {
2710  /* due to clean-up in consdataCreate, there are no fixed points */
2711  assert( perm[i] != i );
2712 
2713  if ( perm[i] > i )
2714  {
2715  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlockspos, nlocksneg) );
2716  }
2717  else
2718  {
2719  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlocksneg, nlockspos) );
2720  }
2721  }
2722 
2723  return SCIP_OKAY;
2724 }
2725 
2726 
2727 /** constraint copying method of constraint handler */
2728 static
2729 SCIP_DECL_CONSCOPY(consCopySymresack)
2731  SCIP_CONSHDLRDATA* conshdlrdata;
2732  SCIP_CONSDATA* sourcedata;
2733  SCIP_VAR** sourcevars;
2734  SCIP_VAR** vars;
2735  int nvars;
2736  int i;
2737 
2738  assert( scip != NULL );
2739  assert( cons != NULL );
2740  assert( sourcescip != NULL );
2741  assert( sourceconshdlr != NULL );
2742  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
2743  assert( sourcecons != NULL );
2744  assert( varmap != NULL );
2745  assert( valid != NULL );
2746 
2747  *valid = TRUE;
2748 
2749  SCIPdebugMsg(scip, "Copying method for symresack constraint handler.\n");
2750 
2751  sourcedata = SCIPconsGetData(sourcecons);
2752  assert( sourcedata != NULL );
2753  assert( sourcedata->vars != NULL );
2754  assert( sourcedata->perm != NULL );
2755  assert( sourcedata->nvars > 0 );
2756 
2757  conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
2758  assert( conshdlrdata != NULL );
2759 
2760  /* do not copy non-model constraints */
2761  if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
2762  {
2763  *valid = FALSE;
2764 
2765  return SCIP_OKAY;
2766  }
2767 
2768  sourcevars = sourcedata->vars;
2769  nvars = sourcedata->nvars;
2770 
2771  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2772 
2773  for (i = 0; i < nvars && *valid; ++i)
2774  {
2775  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i], &(vars[i]), varmap, consmap, global, valid) );
2776  assert( !(*valid) || vars[i] != NULL );
2777  }
2778 
2779  /* only create the target constraint, if all variables could be copied */
2780  if ( *valid )
2781  {
2782  /* create copied constraint */
2783  if ( name == NULL )
2784  name = SCIPconsGetName(sourcecons);
2785 
2786  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, sourcedata->perm, vars, nvars, sourcedata->ismodelcons,
2787  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2788  }
2789 
2790  SCIPfreeBufferArray(scip, &vars);
2791 
2792  return SCIP_OKAY;
2793 }
2794 
2795 
2796 /** constraint parsing method of constraint handler */
2797 static
2798 SCIP_DECL_CONSPARSE(consParseSymresack)
2799 { /*lint --e{715}*/
2800  const char* s;
2801  char* endptr;
2802  SCIP_VAR** vars;
2803  SCIP_VAR* var;
2804  int* perm;
2805  int val;
2806  int nvars = 0;
2807  int cnt = 0;
2808  int nfoundpermidx = 0;
2809  int maxnvars = 128;
2810 
2811  assert( success != NULL );
2812 
2813  *success = TRUE;
2814  s = str;
2815 
2816  /* skip white space */
2817  while ( *s != '\0' && isspace((unsigned char)*s) )
2818  ++s;
2819 
2820  if ( strncmp(s, "symresack(", 10) != 0 )
2821  {
2822  SCIPerrorMessage("Syntax error - expected \"symresack(\", but got '%s'", s);
2823  *success = FALSE;
2824  return SCIP_OKAY;
2825  }
2826  s += 10;
2827 
2828  /* loop through string */
2829  SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnvars) );
2830  SCIP_CALL( SCIPallocBufferArray(scip, &perm, maxnvars) );
2831 
2832  do
2833  {
2834  if ( cnt > 1 )
2835  {
2836  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "expected two arrays, but got more\n");
2837  *success = FALSE;
2838 
2839  SCIPfreeBufferArray(scip, &perm);
2840  SCIPfreeBufferArray(scip, &vars);
2841  }
2842 
2843  /* skip whitespace and ',' */
2844  while ( *s != '\0' && ( isspace((unsigned char)*s) || *s == ',' ) )
2845  ++s;
2846 
2847  /* if we could not find starting indicator of array */
2848  if ( *s != '[' )
2849  {
2850  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "expected '[' to start new array\n");
2851  *success = FALSE;
2852 
2853  SCIPfreeBufferArray(scip, &perm);
2854  SCIPfreeBufferArray(scip, &vars);
2855  }
2856  ++s;
2857 
2858  /* read array, cnt = 0: variables; cnt = 1: permutation*/
2859  if ( cnt == 0 )
2860  {
2861  do
2862  {
2863  /* skip whitespace and ',' */
2864  while ( *s != '\0' && ( isspace((unsigned char)*s) || *s == ',' ) )
2865  ++s;
2866 
2867  /* parse variable name */
2868  SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
2869  if ( var == NULL )
2870  {
2871  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "unknown variable name at '%s'\n", str);
2872  *success = FALSE;
2873  SCIPfreeBufferArray(scip, &vars);
2874  return SCIP_OKAY;
2875  }
2876  s = endptr;
2877  assert( s != NULL );
2878 
2879  vars[nvars++] = var;
2880 
2881  if ( nvars >= maxnvars )
2882  {
2883  int newsize;
2884 
2885  newsize = SCIPcalcMemGrowSize(scip, nvars + 1);
2886  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, newsize) );
2887  SCIP_CALL( SCIPreallocBufferArray(scip, &perm, newsize) );
2888  maxnvars = newsize;
2889  }
2890  }
2891  while ( *s != ']' );
2892  }
2893  else
2894  {
2895  do
2896  {
2897  /* skip whitespace and ',' */
2898  while ( *s != '\0' && ( isspace((unsigned char)*s) || *s == ',' ) )
2899  ++s;
2900 
2901  /* parse integer value */
2902  if ( ! SCIPstrToIntValue(s, &val, &endptr) )
2903  {
2904  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "could not extract int from string '%s'\n", str);
2905  *success = FALSE;
2906  SCIPfreeBufferArray(scip, &perm);
2907  SCIPfreeBufferArray(scip, &vars);
2908  return SCIP_OKAY;
2909  }
2910  s = endptr;
2911  assert( s != NULL );
2912 
2913  perm[nfoundpermidx++] = val;
2914 
2915  if ( nfoundpermidx > nvars )
2916  {
2917  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "permutation is longer than vars array\n");
2918  *success = FALSE;
2919  SCIPfreeBufferArray(scip, &perm);
2920  SCIPfreeBufferArray(scip, &vars);
2921  return SCIP_OKAY;
2922  }
2923  }
2924  while ( *s != ']' );
2925  }
2926  ++s;
2927  ++cnt;
2928  }
2929  while ( *s != ')' );
2930 
2931  if ( nfoundpermidx == nvars )
2932  {
2933  SCIP_CALL( SCIPcreateConsBasicSymresack(scip, cons, name, perm, vars, nvars, TRUE) );
2934  }
2935  else
2936  {
2938  "Length of permutation is not equal to number of given variables.\n");
2939  *success = FALSE;
2940  }
2941 
2942  SCIPfreeBufferArray(scip, &perm);
2943  SCIPfreeBufferArray(scip, &vars);
2944 
2945  return SCIP_OKAY;
2946 }
2947 
2948 
2949 /** constraint display method of constraint handler
2950  *
2951  * The constraint handler should output a representation of the constraint into the given text file.
2952  */
2953 static
2954 SCIP_DECL_CONSPRINT(consPrintSymresack)
2955 { /*lint --e{715}*/
2956  SCIP_CONSDATA* consdata;
2957  SCIP_VAR** vars;
2958  int* perm;
2959  int nvars;
2960  int i;
2961 
2962  assert( scip != NULL );
2963  assert( conshdlr != NULL );
2964  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2965  assert( cons != NULL );
2966 
2967  consdata = SCIPconsGetData(cons);
2968  assert( consdata != NULL );
2969 
2970  SCIPdebugMsg(scip, "Printing method for symresack constraint handler\n");
2971 
2972  /* we do not have to take care of trivial constraints */
2973  if ( consdata->nvars < 2 )
2974  return SCIP_OKAY;
2975 
2976  assert( consdata->vars != NULL );
2977  assert( consdata->perm != NULL );
2978 
2979  vars = consdata->vars;
2980  nvars = consdata->nvars;
2981  perm = consdata->perm;
2982 
2983  SCIPinfoMessage(scip, file, "symresack([");
2984  SCIP_CALL( SCIPwriteVarName(scip, file, vars[0], TRUE) );
2985 
2986  for (i = 1; i < nvars; ++i)
2987  {
2988  SCIPinfoMessage(scip, file, ",");
2989  SCIP_CALL( SCIPwriteVarName(scip, file, vars[i], TRUE) );
2990  }
2991  SCIPinfoMessage(scip, file, "],[%d", perm[0]);
2992  for (i = 1; i < nvars; ++i)
2993  SCIPinfoMessage(scip, file, ",%d", perm[i]);
2994  SCIPinfoMessage(scip, file, "])");
2995 
2996  return SCIP_OKAY;
2997 }
2998 
2999 
3000 /** constraint method of constraint handler which returns the variables (if possible) */
3001 static
3002 SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
3003 { /*lint --e{715}*/
3004  SCIP_CONSDATA* consdata;
3005 
3006  assert( cons != NULL );
3007  assert( success != NULL );
3008  assert( vars != NULL );
3009 
3010  consdata = SCIPconsGetData(cons);
3011  assert( consdata != NULL );
3012 
3013  if ( varssize < consdata->nvars )
3014  (*success) = FALSE;
3015  else
3016  {
3017  int cnt = 0;
3018  int i;
3019 
3020  for (i = 0; i < consdata->nvars; ++i)
3021  vars[cnt++] = consdata->vars[i];
3022  (*success) = TRUE;
3023  }
3024 
3025  return SCIP_OKAY;
3026 }
3027 
3028 
3029 /** constraint method of constraint handler which returns the number of variables (if possible) */
3030 static
3031 SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
3032 { /*lint --e{715}*/
3033  SCIP_CONSDATA* consdata;
3034 
3035  assert( cons != NULL );
3036  assert( success != NULL );
3037  assert( nvars != NULL );
3038 
3039  consdata = SCIPconsGetData(cons);
3040  assert( consdata != NULL );
3041 
3042  (*nvars) = consdata->nvars;
3043  (*success) = TRUE;
3044 
3045  return SCIP_OKAY;
3046 }
3047 
3048 
3049 /** creates the handler for symresack constraints and includes it in SCIP */
3051  SCIP* scip /**< SCIP data structure */
3052  )
3053 {
3054  SCIP_CONSHDLRDATA* conshdlrdata = NULL;
3055  SCIP_CONSHDLR* conshdlr;
3056 
3057  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3058 
3059  /* include constraint handler */
3062  consEnfolpSymresack, consEnfopsSymresack, consCheckSymresack, consLockSymresack,
3063  conshdlrdata) );
3064  assert( conshdlr != NULL );
3065 
3066  /* set non-fundamental callbacks via specific setter functions */
3067  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySymresack, consCopySymresack) );
3068  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSymresack) );
3069  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSymresack) );
3070  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSymresack) );
3071  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSymresack) );
3072  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSymresack) );
3073  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSymresack) );
3074  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSymresack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3075  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSymresack) );
3077  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSymresack) );
3078  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSymresack, consSepasolSymresack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
3079  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSymresack) );
3080  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSymresack) );
3081  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSymresack) );
3082 
3083  /* whether we allow upgrading to packing/partioning symresack constraints*/
3084  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/ppsymresack",
3085  "Upgrade symresack constraints to packing/partioning symresacks?",
3086  &conshdlrdata->checkppsymresack, TRUE, DEFAULT_PPSYMRESACK, NULL, NULL) );
3087 
3088  /* whether we check for monotonicity of perm when upgrading to packing/partioning symresacks */
3089  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkmonotonicity",
3090  "Check whether permutation is monotone when upgrading to packing/partioning symresacks?",
3091  &conshdlrdata->checkmonotonicity, TRUE, DEFAULT_CHECKMONOTONICITY, NULL, NULL) );
3092 
3093  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
3094  "Whether symresack constraints should be forced to be copied to sub SCIPs.",
3095  &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
3096 
3097  return SCIP_OKAY;
3098 }
3099 
3100 
3101 /*
3102  * constraint specific interface methods
3103  */
3104 
3105 /** creates and captures a symresack constraint
3106  *
3107  * In a presolving step, we check whether the permutation acts only on binary points. Otherwise, we eliminate
3108  * the non-binary variables from the permutation.
3109  *
3110  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
3111  */
3113  SCIP* scip, /**< SCIP data structure */
3114  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3115  const char* name, /**< name of constraint */
3116  int* perm, /**< permutation */
3117  SCIP_VAR** vars, /**< variables */
3118  int nvars, /**< number of variables in vars array */
3119  SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
3120  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3121  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3122  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3123  * Usually set to TRUE. */
3124  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3125  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3126  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3127  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3128  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3129  * Usually set to TRUE. */
3130  SCIP_Bool local, /**< is constraint only valid locally?
3131  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3132  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3133  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3134  * adds coefficients to this constraint. */
3135  SCIP_Bool dynamic, /**< is constraint subject to aging?
3136  * Usually set to FALSE. Set to TRUE for own cuts which
3137  * are separated as constraints. */
3138  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3139  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3140  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3141  * if it may be moved to a more global node?
3142  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3143  )
3144 {
3145  SCIP_CONSHDLR* conshdlr;
3146  SCIP_CONSDATA* consdata;
3147 
3148  assert( cons != NULL );
3149  assert( nvars > 0 );
3150 
3151  /* find the symresack constraint handler */
3152  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3153  if ( conshdlr == NULL )
3154  {
3155  SCIPerrorMessage("Symresack constraint handler not found.\n");
3156  return SCIP_PLUGINNOTFOUND;
3157  }
3158 
3159  /* create constraint data */
3160  SCIP_CALL( consdataCreate(scip, conshdlr, &consdata, vars, nvars, perm, ismodelcons) );
3161 
3162  /* create constraint */
3163  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate && (! consdata->ppupgrade), enforce, check, propagate,
3164  local, modifiable, dynamic, removable, stickingatnode) );
3165 
3166  return SCIP_OKAY;
3167 }
3168 
3169 
3170 /** creates and captures a symresack constraint
3171  * in its most basic variant, i.e., with all constraint flags set to their default values
3172  *
3173  * In a presolving step, we remove all fixed points and cycles that act on non-binary variables of the permutation
3174  *
3175  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
3176  */
3178  SCIP* scip, /**< SCIP data structure */
3179  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3180  const char* name, /**< name of constraint */
3181  int* perm, /**< permutation */
3182  SCIP_VAR** vars, /**< variables */
3183  int nvars, /**< number of variables in vars array */
3184  SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
3185  )
3186 {
3187  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
3189 
3190  return SCIP_OKAY;
3191 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1413
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_PRESOLTIMING
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_RETCODE SCIPcreateConsOrbisack(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_DECL_CONSPROP(consPropSymresack)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
public methods for SCIP parameter handling
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
public methods for memory management
static SCIP_DECL_CONSFREE(consFreeSymresack)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9394
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
#define CONSHDLR_NAME
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:816
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
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:308
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2841
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
static SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateConsBasicSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons)
#define ISFIXED(x, bdchgidx)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1436
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:524
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
static SCIP_DECL_CONSCOPY(consCopySymresack)
static SCIP_DECL_CONSPARSE(consParseSymresack)
static SCIP_RETCODE initLP(SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkmonotonicity, SCIP_Bool *infeasible)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
#define FALSE
Definition: def.h:87
#define CONSHDLR_PROPFREQ
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
constraint handler for orbisack constraints
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8364
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA **consdata, SCIP_VAR *const *inputvars, int inputnvars, int *inputperm, SCIP_Bool ismodelcons)
static SCIP_RETCODE checkSymresackSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17600
#define CONSHDLR_MAXPREROUNDS
public methods for problem variables
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10825
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:220
#define FIXED0
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
static SCIP_DECL_CONSPRESOL(consPresolSymresack)
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:566
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
public methods for SCIP variables
static SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:609
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1477
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:793
static SCIP_RETCODE separateSymresackCovers(SCIP *scip, SCIP_CONS *cons, const SCIP_CONSDATA *consdata, SCIP_Real *vals, int *ngen, SCIP_Bool *infeasible)
static SCIP_DECL_CONSINITLP(consInitlpSymresack)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:934
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
static SCIP_RETCODE maximizeObjectiveSymresackStrict(SCIP *scip, int nvars, SCIP_Real *objective, int *perm, int *invperm, int *maxcrit, SCIP_Real *maxsoluval)
public methods for numerical tolerances
static SCIP_DECL_CONSPRINT(consPrintSymresack)
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
constraint handler for symresack constraints
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
public methods for managing constraints
static SCIP_RETCODE addSymresackInequality(SCIP *scip, SCIP_CONS *cons, int nvars, SCIP_VAR **vars, int *coeffs, SCIP_Real rhs, SCIP_Bool *infeasible)
static SCIP_RETCODE orbisackUpgrade(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **inputvars, int nvars, SCIP_Bool *upgrade, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
static SCIP_DECL_CONSSEPALP(consSepalpSymresack)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateConsSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
static SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:126
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16661
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
static SCIP_DECL_CONSLOCK(consLockSymresack)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8712
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
static SCIP_DECL_CONSDELETE(consDeleteSymresack)
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
#define CONSHDLR_SEPAFREQ
static SCIP_RETCODE maximizeObjectiveSymresackCriticalEntry(SCIP *scip, int nvars, SCIP_Real *objective, int *perm, int *invperm, int crit, int *maxsolu)
#define SCIP_CALL(x)
Definition: def.h:384
#define FIXED1
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:216
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8324
static SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:632
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
#define UNFIXED
static SCIP_RETCODE packingUpgrade(SCIP *scip, SCIP_CONSDATA **consdata, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool checkmonotonicity, SCIP_Bool *upgrade)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4590
public methods for constraint handler plugins and constraints
#define DEFAULT_CHECKMONOTONICITY
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9440
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16542
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
static SCIP_DECL_CONSRESPROP(consRespropSymresack)
public methods for cuts and aggregation rows
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
static SCIP_DECL_CONSCHECK(consCheckSymresack)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:770
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5498
public methods for the LP relaxation, rows and columns
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9417
#define CONSHDLR_DELAYSEPA
SCIP_Real * r
Definition: circlepacking.c:50
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
general public methods
#define SCIP_DEFAULT_INFINITY
Definition: def.h:182
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_PROP_TIMING
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:702
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5612
static SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
#define DEFAULT_PPSYMRESACK
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:525
static SCIP_RETCODE checkFeasible(SCIP *scip, SCIP_VAR **vars, int *invperm, int nvars, int start, int *tempfixings, int *tempfixentries, int numfixentriesinit, SCIP_Bool *infeasible, int *infeasibleentry)
#define DEFAULT_FORCECONSCOPY
public methods for message output
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1211
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1712
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
#define CONSHDLR_CHECKPRIORITY
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:839
public methods for message handling
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
#define NOINIT
#define CONSHDLR_DESC
static SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
#define CONSHDLR_SEPAPRIORITY
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE propVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *ngen)
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:221
public methods for global and local (sub)problems
static SCIP_DECL_CONSINITSOL(consInitsolSymresack)
static SCIP_DECL_CONSTRANS(consTransSymresack)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17406
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266
memory allocation routines