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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_symresack.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief constraint handler for symresack constraints
19  * @author Christopher Hojny
20  *
21  * The type of constraints of this constraint handler is described in cons_symresack.h.
22  *
23  * The details of the method implemented here are described in the following papers:
24  *
25  * Fundamental Domains for Integer Programs with Symmetries@n
26  * Eric J. Friedman,@n
27  * Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007)
28  *
29  * This paper describes an inequality to handle symmetries of a single permutation. This
30  * so-called FD-inequality is the basic for the propagation routine of our implementation.
31  *
32  * Polytopes Associated with Symmetry Handling@n
33  * Christopher Hojny and Marc E. Pfetsch,@n
34  * Mathematical Programming 175, No. 1, 197-240, 2019
35  *
36  * This paper describes an almost linear time separation routine for so-called cover
37  * inequalities of symresacks. In our implementation, however, we use a separation routine with
38  * quadratic worst case running time.
39  *
40  * Packing, Partitioning, and Covering Symresacks@n
41  * Christopher Hojny,@n
42  * (2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/05/5990.html
43  *
44  * This paper introduces linearly many inequalities with ternary coefficients that suffice to
45  * characterize the binary points contained in a packing and partitioning symresack completely.
46  */
47 
48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49 
50 #include "blockmemshell/memory.h"
51 #include "scip/cons_orbisack.h"
52 #include "scip/cons_setppc.h"
53 #include "scip/cons_symresack.h"
54 #include "scip/pub_cons.h"
55 #include "scip/pub_message.h"
56 #include "scip/pub_misc.h"
57 #include "scip/pub_var.h"
58 #include "scip/scip.h"
59 #include "scip/scip_branch.h"
60 #include "scip/scip_conflict.h"
61 #include "scip/scip_cons.h"
62 #include "scip/scip_cut.h"
63 #include "scip/scip_general.h"
64 #include "scip/scip_lp.h"
65 #include "scip/scip_mem.h"
66 #include "scip/scip_message.h"
67 #include "scip/scip_numerics.h"
68 #include "scip/scip_param.h"
69 #include "scip/scip_prob.h"
70 #include "scip/scip_sol.h"
71 #include "scip/scip_var.h"
72 #include <string.h>
73 
74 /* constraint handler properties */
75 #define CONSHDLR_NAME "symresack"
76 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks"
77 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
78 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
79 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
80 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
81 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */
82 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
83  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
84 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
85 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
86 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
87 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
88 
89 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
90 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
91 
92 #define DEFAULT_PPSYMRESACK TRUE /**< whether we allow upgrading to packing/partitioning symresacks */
93 #define DEFAULT_CHECKMONOTONICITY TRUE /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
94 #define DEFAULT_FORCECONSCOPY FALSE /**< whether symresack constraints should be forced to be copied to sub SCIPs */
95 
96 /* macros for getting bounds of pseudo solutions in propagation */
97 #define ISFIXED0(x) (SCIPvarGetUbLocal(x) < 0.5 ? TRUE : FALSE)
98 #define ISFIXED1(x) (SCIPvarGetLbLocal(x) > 0.5 ? TRUE : FALSE)
99 
100 
101 /*
102  * Data structures
103  */
104 
105 /** constraint handler data */
106 struct SCIP_ConshdlrData
107 {
108  SCIP_Bool checkppsymresack; /**< whether we allow upgrading to packing/partitioning symresacks */
109  SCIP_Bool checkmonotonicity; /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
110  int maxnvars; /**< maximal number of variables in a symresack constraint */
111  SCIP_Bool forceconscopy; /**< whether symresack constraints should be forced to be copied to sub SCIPs */
112 };
113 
114 
115 /** constraint data for symresack constraints */
116 struct SCIP_ConsData
117 {
118  SCIP_VAR** vars; /**< variables */
119  int nvars; /**< number of variables */
120  int* perm; /**< permutation associated to the symresack */
121  int* invperm; /**< inverse permutation */
122  SCIP_Bool ppupgrade; /**< whether constraint is upgraded to packing/partitioning symresack */
123  SCIP_Bool ismodelcons; /**< whether the symresack is a model constraint */
124 #ifdef SCIP_DEBUG
125  int debugcnt; /**< counter to store number of added cover inequalities */
126 #endif
127 
128  /* data for upgraded symresack constraints */
129  int ncycles; /**< number of cycles in permutation */
130  int** cycledecomposition; /**< cycle decomposition */
131  int ndescentpoints; /**< number of descent points in perm (only used if perm is not monotone) */
132  int* descentpoints; /**< descent points in perm (only used if perm is not monotone) */
133 };
134 
135 
136 /*
137  * Local methods
138  */
139 
140 /** frees a symresack constraint data */
141 static
142 SCIP_RETCODE consdataFree(
143  SCIP* scip, /**< SCIP data structure */
144  SCIP_CONSDATA** consdata /**< pointer to symresack constraint data */
145  )
146 {
147  int nvars;
148  int i;
149 
150  assert( consdata != NULL );
151  assert( *consdata != NULL );
152 
153  nvars = (*consdata)->nvars;
154 
155  if ( nvars == 0 )
156  {
157  assert( (*consdata)->vars == NULL );
158  assert( (*consdata)->perm == NULL );
159  assert( (*consdata)->invperm == NULL );
160  assert( (*consdata)->ncycles == 0 );
161  assert( (*consdata)->cycledecomposition == NULL );
162 
163  SCIPfreeBlockMemory(scip, consdata);
164 
165  return SCIP_OKAY;
166  }
167 
168  if ( (*consdata)->ndescentpoints > 0 )
169  {
170  assert( (*consdata)->descentpoints != NULL );
171 
172  SCIPfreeBlockMemoryArray(scip, &((*consdata)->descentpoints), (*consdata)->ndescentpoints);
173  }
174 
175  if ( (*consdata)->ppupgrade )
176  {
177  for (i = 0; i < (*consdata)->ncycles; ++i)
178  {
179  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition[i]), nvars + 1);
180  }
181  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition), (*consdata)->ncycles);
182  }
183 
184  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->invperm), nvars);
185  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->perm), nvars);
186 
187  for (i = 0; i < nvars; ++i)
188  {
189  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i]) );
190  }
191  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), nvars);
192 
193  SCIPfreeBlockMemory(scip, consdata);
194 
195  return SCIP_OKAY;
196 }
197 
198 
199 /** check whether constraint can be upgraded to packing/partitioning symresack */
200 static
201 SCIP_RETCODE packingUpgrade(
202  SCIP* scip, /**< SCIP data structure */
203  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
204  int* perm, /**< permutation */
205  SCIP_VAR** vars, /**< variables affected by permutation */
206  int nvars, /**< length of permutation */
207  SCIP_Bool checkmonotonicity, /**< check whether permutation is monotone */
208  SCIP_Bool* upgrade /**< pointer to store whether upgrade was successful */
209  )
210 {
211  SCIP_Bool* covered;
212  SCIP_Bool descent;
213  SCIP_CONSHDLR* setppcconshdlr;
214  SCIP_CONS** setppcconss;
215  SCIP_VAR* var;
216  SCIP_Bool terminated = FALSE;
217  int** cycledecomposition;
218  int* indicesincycle;
219  int nsetppcconss;
220  int curcycle;
221  int maxcyclelength;
222  int ncycles = 0;
223  int c;
224  int i;
225  int j;
226  int ndescentpoints = 0;
227  int* descentpoints;
228 
229  assert( scip != NULL );
230  assert( perm != NULL );
231  assert( vars != NULL );
232  assert( nvars > 0 );
233  assert( upgrade != NULL );
234 
235  *upgrade = FALSE;
236 
237  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
238 
239  for (i = 0; i < nvars; ++i)
240  covered[i] = FALSE;
241 
242  /* get number of cycles in permutation */
243  for (i = 0; i < nvars; ++i)
244  {
245  /* skip checked indices */
246  if ( covered[i] )
247  continue;
248 
249  ++ncycles;
250  j = i;
251  descent = FALSE;
252 
253  do
254  {
255  covered[j] = TRUE;
256 
257  if ( perm[j] < j )
258  {
259  ++ndescentpoints;
260 
261  if ( ! descent )
262  descent = TRUE;
263  else if ( checkmonotonicity )
264  break;
265  }
266 
267  j = perm[j];
268  }
269  while ( j != i );
270 
271  /* if cycle is not monotone and we require the cycle to be monotone */
272  if ( j != i )
273  {
274  assert( checkmonotonicity );
275  SCIPfreeBufferArray(scip, &covered);
276 
277  return SCIP_OKAY;
278  }
279  }
280  assert( ncycles <= nvars / 2 );
281 
282  /* check for packing/partitioning type */
283  for (i = 0; i < nvars; ++i)
284  covered[i] = FALSE;
285 
286  /* compute cycle decomposition: row i stores in entry 0 the length of the cycle,
287  * the remaining entries are the coordinates in the cycle;
288  * store descent points as well if permutation is not monotone */
289  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition, ncycles) );
290  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &descentpoints, ndescentpoints) );
291  for (i = 0; i < ncycles; ++i)
292  {
293  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1) );
294  }
295 
296  curcycle = 0;
297  maxcyclelength = 0;
298  c = 0;
299  for (i = 0; i < nvars; ++i)
300  {
301  int cyclelength = 0;
302 
303  /* skip checked indices */
304  if ( covered[i] )
305  continue;
306 
307  j = i;
308  do
309  {
310  if ( perm[j] < j )
311  descentpoints[c++] = j;
312 
313  covered[j] = TRUE;
314  cycledecomposition[curcycle][++cyclelength] = j;
315  j = perm[j];
316  }
317  while ( j != i );
318 
319  cycledecomposition[curcycle][0] = cyclelength;
320  ++curcycle;
321 
322  if ( maxcyclelength < cyclelength )
323  maxcyclelength = cyclelength;
324  }
325  assert( c == ndescentpoints );
326 
327  /* permutation can be upgraded -> check whether the symresack is of packing/partitioning type */
328  setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
329  if ( setppcconshdlr == NULL )
330  {
331  SCIPerrorMessage("Setppc constraint handler not found.\n");
332  return SCIP_PLUGINNOTFOUND;
333  }
334  setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
335  nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
336 
337  /* Check whether each cycle of the symresack is contained in a set packing/partitioning constraint.
338  * To this end, we have to guarantee that all affected variables are not negated since permutations
339  * are given w.r.t. original variables. */
340  *upgrade = TRUE;
341 
342  SCIP_CALL( SCIPallocBufferArray(scip, &indicesincycle, maxcyclelength) );
343 
344  for (i = 0; i < ncycles && *upgrade && ! terminated; ++i)
345  {
346  int cyclelength;
347 
348  /* get indices of variables in current cycle */
349  for (j = 0; j < cycledecomposition[i][0]; ++ j)
350  {
351  var = vars[cycledecomposition[i][j + 1]];
352 
353  if ( SCIPvarIsNegated(var) )
354  {
355  terminated = TRUE;
356  break;
357  }
358 
359  indicesincycle[j] = SCIPvarGetProbindex(var);
360  }
361 
362  cyclelength = cycledecomposition[i][0];
363 
364  /* iterate over constraints
365  *
366  * @todo Improve the check by sorting the constraints in the setppcconss array
367  * by type and number of contained variables. */
368  for (c = 0; c < nsetppcconss; ++c)
369  {
370  int nsetppcvars;
371  SCIP_VAR** setppcvars;
372  int varidx;
373  int nfound = 0;
374  int k;
375 
376  /* check type */
377  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
378  continue;
379  assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING || SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING );
380 
381  /* get set packing/partitioning variables */
382  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
383  assert( nsetppcvars > 0 );
384 
385  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
386  assert( setppcvars != NULL );
387 
388  /* check whether all variables of the cycle are contained in setppc constraint */
389  for (j = 0; j < nsetppcvars && nfound < cyclelength; ++j)
390  {
391  var = setppcvars[j];
392 
393  if ( SCIPvarIsNegated(var) )
394  continue;
395 
396  varidx = SCIPvarGetProbindex(var);
397 
398  for (k = 0; k < cyclelength; ++k)
399  {
400  if ( varidx == indicesincycle[k] )
401  {
402  ++nfound;
403  break;
404  }
405  }
406  }
407  assert( nfound <= cyclelength );
408 
409  if ( nfound == cyclelength )
410  break;
411  }
412 
413  /* row is not contained in a set packing/partitioning constraint */
414  if ( c >= nsetppcconss )
415  *upgrade = FALSE;
416  }
417 
418  if ( *upgrade )
419  {
420  (*consdata)->ncycles = ncycles;
421  (*consdata)->cycledecomposition = cycledecomposition;
422  (*consdata)->ndescentpoints = ndescentpoints;
423  (*consdata)->descentpoints = descentpoints;
424  SCIPdebugMsg(scip, "added monotone PP symresack.\n");
425 
426  SCIPfreeBufferArray(scip, &indicesincycle);
427  SCIPfreeBufferArray(scip, &covered);
428  }
429  else
430  {
431  SCIPfreeBlockMemoryArray(scip, &descentpoints, ndescentpoints);
432  SCIPfreeBufferArray(scip, &indicesincycle);
433  SCIPfreeBufferArray(scip, &covered);
434  for (i = 0; i < ncycles; ++i)
435  {
436  SCIPfreeBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1);
437  }
438  SCIPfreeBlockMemoryArray(scip, &cycledecomposition, ncycles);
439  }
440 
441  return SCIP_OKAY;
442 }
443 
444 
445 /** creates symresack constraint data
446  *
447  * If the input data contains non-binary variables or fixed
448  * points, we delete these variables in a preprocessing step.
449  */
450 static
451 SCIP_RETCODE consdataCreate(
452  SCIP* scip, /**< SCIP data structure */
453  SCIP_CONSHDLR* conshdlr, /**< symresack constraint handler */
454  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
455  SCIP_VAR*const* inputvars, /**< input variables of the constraint handler */
456  int inputnvars, /**< input number of variables of the constraint handler*/
457  int* inputperm, /**< input permutation of the constraint handler */
458  SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
459  )
460 {
461  SCIP_CONSHDLRDATA* conshdlrdata;
462  SCIP_VAR** vars;
463  SCIP_Bool upgrade;
464  int* indexcorrection;
465  int* invperm;
466  int* perm;
467  int naffectedvariables;
468  int i;
469  int j = 0;
470 
471  assert( consdata != NULL );
472  assert( conshdlr != NULL );
473  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
474 
475  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
476 
477 #ifdef SCIP_DEBUG
478  (*consdata)->debugcnt = 0;
479 #endif
480 
481  (*consdata)->ndescentpoints = 0;
482  (*consdata)->descentpoints = NULL;
483 
484  /* count the number of binary variables which are affected by the permutation */
485  SCIP_CALL( SCIPallocBufferArray(scip, &indexcorrection, inputnvars) );
486  indexcorrection[0] = -1;
487  for (i = 0; i < inputnvars; ++i)
488  {
489  if ( inputperm[i] != i && SCIPvarIsBinary(inputvars[i]) )
490  {
491  if ( i == 0 )
492  indexcorrection[i] = 0;
493  else
494  indexcorrection[i] = indexcorrection[i - 1] + 1;
495  }
496  else
497  {
498  if ( i > 0 )
499  indexcorrection[i] = indexcorrection[i - 1];
500  }
501  }
502  naffectedvariables = indexcorrection[inputnvars - 1] + 1;
503 
504  (*consdata)->nvars = naffectedvariables;
505 
506  /* Stop if we detect that the permutation fixes each binary point. */
507  if ( naffectedvariables == 0 )
508  {
509  SCIPfreeBufferArrayNull(scip, &indexcorrection);
510 
511  (*consdata)->vars = NULL;
512  (*consdata)->perm = NULL;
513  (*consdata)->invperm = NULL;
514  (*consdata)->ppupgrade = FALSE;
515  (*consdata)->ncycles = 0;
516  (*consdata)->cycledecomposition = NULL;
517 
518  return SCIP_OKAY;
519  }
520 
521  /* remove fixed points from permutation representation */
522  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, naffectedvariables) );
523  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &perm, naffectedvariables) );
524  for (i = 0; i < inputnvars; ++i)
525  {
526  if ( i == 0 )
527  {
528  if ( indexcorrection[i] > -1 )
529  {
530  vars[j] = inputvars[i];
531  perm[j++] = indexcorrection[inputperm[i]];
532  }
533  }
534  else
535  {
536  if ( indexcorrection[i] > indexcorrection[i - 1] )
537  {
538  vars[j] = inputvars[i];
539  perm[j++] = indexcorrection[inputperm[i]];
540  }
541  }
542  }
543  SCIPfreeBufferArrayNull(scip, &indexcorrection);
544 
545  (*consdata)->vars = vars;
546  (*consdata)->perm = perm;
547  (*consdata)->ismodelcons = ismodelcons;
548 
549  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &invperm, naffectedvariables) );
550  for (i = 0; i < naffectedvariables; ++i)
551  {
552  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i]) );
553  invperm[perm[i]] = i;
554  }
555  (*consdata)->invperm = invperm;
556 
557  /* check for upgrade to packing/partitioning symresacks*/
558  conshdlrdata = SCIPconshdlrGetData(conshdlr);
559  upgrade = FALSE;
560  if ( conshdlrdata->checkppsymresack )
561  {
562  SCIP_CALL( packingUpgrade(scip, consdata, perm, vars, naffectedvariables, conshdlrdata->checkmonotonicity, &upgrade) );
563  }
564 
565  (*consdata)->ppupgrade = upgrade;
566 
567  /* get transformed variables, if we are in the transformed problem */
568  if ( SCIPisTransformed(scip) )
569  {
570  /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_symresack, since one cannot
571  * easily eliminate single variables from a symresack constraint. */
572  for (i = 0; i < naffectedvariables; ++i)
573  {
574  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i], &(*consdata)->vars[i]) );
575  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i]) );
576  }
577  }
578 
579  return SCIP_OKAY;
580 }
581 
582 
583 /** generate initial LP cut
584  *
585  * We generate the ordering inequality for the pair \f$(1, \gamma^{-1}(1))\f$, i.e.,
586  * the inequality \f$-x_{1} + x_{\gamma^{-1}(1)} \leq 0\f$. This inequality is valid,
587  * because we guaranteed in a preprocessing step that all variables are binary.
588  *
589  * Furthermore, we add facet inequalities of packing/partitioning symresacks if
590  * we deal with packing/partitioning symresacks.
591  */
592 static
593 SCIP_RETCODE initLP(
594  SCIP* scip, /**< SCIP pointer */
595  SCIP_CONS* cons, /**< constraint */
596  SCIP_Bool checkmonotonicity, /**< has it been checked whether permutation is monotone for packing/partitioning symresacks? */
597  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
598  )
599 {
600  SCIP_CONSDATA* consdata;
601  SCIP_VAR** vars;
602  SCIP_ROW* row;
603  int nvars;
604 #ifdef SCIP_DEBUG
605  char name[SCIP_MAXSTRLEN];
606 #endif
607  int i;
608  int j;
609  int k;
610 
611  assert( scip != NULL );
612  assert( cons != NULL );
613  assert( infeasible != NULL );
614 
615  *infeasible = FALSE;
616 
617  consdata = SCIPconsGetData(cons);
618  assert( consdata != NULL );
619 
620  nvars = consdata->nvars;
621 
622  /* avoid stupid problems */
623  if ( nvars <= 1 )
624  return SCIP_OKAY;
625 
626  assert( consdata->vars != NULL );
627  vars = consdata->vars;
628 
629  /* there are no fixed points */
630  assert( consdata->invperm[0] != 0 );
631 
632  /* add ordering inequality */
633 #ifdef SCIP_DEBUG
634  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_init_%s", SCIPconsGetName(cons));
635  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
636 #else
637  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
638 #endif
639  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[0], -1.0) );
640  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[consdata->invperm[0]], 1.0) );
641 
642  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
643 
644  SCIP_CALL( SCIPreleaseRow(scip, &row) );
645 
646  /* check whether we have a packing/partioning symresack */
647  if ( consdata->ppupgrade && ! *infeasible )
648  {
649  if ( checkmonotonicity )
650  {
651  SCIP_VAR** varsincons;
652  SCIP_Real* coeffs;
653  int** cycledecomposition;
654  int ncycles;
655  int nvarsincons;
656  int nvarsincycle;
657  int firstelemincycle;
658 
659  ncycles = consdata->ncycles;
660  cycledecomposition = consdata->cycledecomposition;
661 
662  SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
663  SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nvars) );
664 
665  coeffs[0] = 1.0;
666 
667  /* add packing/partitioning symresack constraints */
668  for (i = 0; i < ncycles; ++i)
669  {
670  assert( cycledecomposition[i][0] > 0 );
671 
672  nvarsincycle = cycledecomposition[i][0];
673  varsincons[0] = vars[cycledecomposition[i][nvarsincycle]];
674  firstelemincycle = cycledecomposition[i][1];
675 
676  assert( firstelemincycle == consdata->perm[cycledecomposition[i][nvarsincycle]] );
677 
678  nvarsincons = 1;
679 
680  /* add variables of other cycles to the constraint */
681  for (j = 0; j < i; ++j)
682  {
683  nvarsincycle = cycledecomposition[j][0];
684  for (k = 1; k <= nvarsincycle; ++k)
685  {
686  if ( cycledecomposition[j][k] < firstelemincycle )
687  {
688  varsincons[nvarsincons] = vars[cycledecomposition[j][k]];
689  coeffs[nvarsincons++] = -1.0;
690  }
691  else
692  continue;
693  }
694  }
695 
696 #ifdef SCIP_DEBUG
697  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", i, SCIPconsGetName(cons));
698  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
699 #else
700  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
701 #endif
702  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
703 
704  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
705  SCIP_CALL( SCIPreleaseRow(scip, &row) );
706 
707  if ( *infeasible )
708  break;
709  }
710 
711  SCIPfreeBufferArray(scip, &coeffs);
712  SCIPfreeBufferArray(scip, &varsincons);
713  }
714  else
715  {
716  SCIP_Real* coeffs;
717  SCIP_VAR** varsincons;
718  int* imgdescentpoints;
719  int* descentpoints;
720  int* perm;
721  int ndescentpoints;
722  int lastascent = 0;
723  int newlastascent = 0;
724  int nvarsincons = 1;
725 
726  descentpoints = consdata->descentpoints;
727  ndescentpoints = consdata->ndescentpoints;
728  perm = consdata->perm;
729 
730  assert( descentpoints != NULL );
731  assert( ndescentpoints > 0 );
732  assert( perm != NULL );
733  assert( vars != NULL );
734  assert( nvars > 0 );
735 
736  SCIP_CALL( SCIPallocBufferArray(scip, &imgdescentpoints, ndescentpoints) );
737 
738  /* get images of descentpoints */
739  for (j = 0; j < ndescentpoints; ++j)
740  imgdescentpoints[j] = perm[descentpoints[j]];
741 
742  /* sort descent points increasingly w.r.t. the corresponding image */
743  SCIPsortIntInt(imgdescentpoints, descentpoints, ndescentpoints);
744 
745  /* iteratively generate coefficient vector: the first entry is the descent point j and the remaining entries
746  * are the corresponding ascent points less than perm[j]
747  */
748  SCIP_CALL( SCIPallocClearBufferArray(scip, &coeffs, nvars) );
749  SCIP_CALL( SCIPallocClearBufferArray(scip, &varsincons, nvars) );
750  coeffs[0] = 1.0;
751  for (j = 0; j < ndescentpoints; ++j)
752  {
753  varsincons[0] = vars[descentpoints[j]];
754  for (i = lastascent; i < imgdescentpoints[j]; ++i)
755  {
756  if ( perm[i] > i )
757  {
758  coeffs[nvarsincons] = -1.0;
759  varsincons[nvarsincons++] = vars[i];
760  newlastascent = i;
761  }
762  }
763  lastascent = newlastascent;
764 
765 #ifdef SCIP_DEBUG
766  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", j, SCIPconsGetName(cons));
767  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
768 #else
769  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
770 #endif
771  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
772 
773  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
774  SCIP_CALL( SCIPreleaseRow(scip, &row) );
775 
776  if ( *infeasible )
777  break;
778  }
779 
780  SCIPfreeBufferArray(scip, &varsincons);
781  SCIPfreeBufferArray(scip, &coeffs);
782  SCIPfreeBufferArray(scip, &imgdescentpoints);
783  }
784  }
785 
786  return SCIP_OKAY;
787 }
788 
789 
790 /** perform propagation of symresack constraint */
791 static
792 SCIP_RETCODE propVariables(
793  SCIP* scip, /**< SCIP pointer */
794  SCIP_CONS* cons, /**< constraint to be propagated */
795  SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */
796  int* ngen /**< pointer to store number of generated bound strengthenings */
797  )
798 {
799  SCIP_CONSDATA* consdata;
800  SCIP_VAR** vars;
801  int* invperm;
802  int nvars;
803  int i;
804 
805  assert( scip != NULL );
806  assert( cons != NULL );
807  assert( infeasible != NULL );
808  assert( ngen != NULL );
809 
810  SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons));
811 
812  *ngen = 0;
813  *infeasible = FALSE;
814 
815  /* get data of constraint */
816  consdata = SCIPconsGetData(cons);
817  assert( consdata != NULL );
818  nvars = consdata->nvars;
819 
820  /* avoid trivial problems */
821  if ( nvars < 2 )
822  return SCIP_OKAY;
823 
824  assert( consdata->vars != NULL );
825  assert( consdata->invperm != NULL );
826  vars = consdata->vars;
827  invperm = consdata->invperm;
828 
829  /* loop through all variables */
830  for (i = 0; i < nvars; ++i)
831  {
832  SCIP_VAR* var2;
833  SCIP_VAR* var;
834  int r;
835  SCIP_Bool tightened;
836 
837  /* there are no fixed points */
838  assert( invperm[i] != i );
839 
840  /* get variables of first and second column */
841  var = vars[i];
842  var2 = vars[invperm[i]];
843  assert( var != NULL );
844  assert( var2 != NULL );
845 
846  /* if first part of variable pair fixed to 0 and second part is fixed to 1 */
847  if ( ISFIXED0(var) && ISFIXED1(var2) )
848  {
849  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
850 
851  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");
852 
853  /* perform conflict analysis */
854  if ( SCIPisConflictAnalysisApplicable(scip) )
855  {
856  SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
857 
858  for (r = 0; r <= i; ++r)
859  {
860  /* there are no fixed points */
861  assert( invperm[r] != r );
862 
863  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[r]) );
864  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[invperm[r]]) );
865  }
866 
867  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
868  }
869 
870  *infeasible = TRUE;
871  break;
872  }
873  /* if first part of the variable pair is fixed to 0 and the second part is free --> fix second part to 0 */
874  else if ( ISFIXED0(var) && ( ! ISFIXED0(var2) ) )
875  {
876  assert( SCIPvarGetUbLocal(var) < 0.5 );
877  assert( SCIPvarGetLbLocal(var2) < 0.5 );
878  assert( SCIPvarGetUbLocal(var2) > 0.5 );
879 
880  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
881 
882  assert( SCIPvarGetLbLocal(var2) < 0.5 );
883  SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
884  assert( ! *infeasible );
885 
886  if ( tightened )
887  ++(*ngen);
888  }
889  /* if second part of the variable pair is fixed to 1 and the first part is free --> fix first part to 1 */
890  else if ( ( ! ISFIXED1(var) ) && ISFIXED1(var2) )
891  {
892  assert( SCIPvarGetLbLocal(var) < 0.5 );
893  assert( SCIPvarGetUbLocal(var) > 0.5 );
894  assert( SCIPvarGetLbLocal(var2) > 0.5 );
895 
896  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
897 
898  assert( SCIPvarGetUbLocal(var) > 0.5 );
899  SCIP_CALL( SCIPinferVarLbCons(scip, var, 1.0, cons, i + nvars, FALSE, infeasible, &tightened) ); /*lint !e713*/
900  assert( ! *infeasible );
901 
902  if ( tightened )
903  ++(*ngen);
904  }
905  /* if solution is lexicographically maximal */
906  else if ( ISFIXED1(var) && ISFIXED0(var2) )
907  {
908  assert( SCIPvarGetLbLocal(var) > 0.5 );
909  assert( SCIPvarGetUbLocal(var2) < 0.5 );
910 
911  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
912  SCIPdebugMsg(scip, " -> node is feasible (pair was fixed to (1,0) and every earlier pair is constant).\n");
913 
914  break;
915  }
916  /* cannot apply propagation */
917  else
918  break;
919  }
920 
921  return SCIP_OKAY;
922 }
923 
924 
925 /** add symresack cover inequality */
926 static
927 SCIP_RETCODE addSymresackInequality(
928  SCIP* scip, /**< SCIP pointer */
929  SCIP_CONS* cons, /**< constraint */
930  int nvars, /**< number of variables */
931  SCIP_VAR** vars, /**< variables */
932  int* coeffs, /**< coefficient vector of inequality to be added */
933  SCIP_Real rhs, /**< right-hand side of inequality to be added */
934  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
935  )
936 {
937  SCIP_ROW* row;
938  int i;
939 #ifdef SCIP_DEBUG
940  SCIP_CONSDATA* consdata;
941  char name[SCIP_MAXSTRLEN];
942 #endif
943 
944  assert( scip != NULL );
945  assert( cons != NULL );
946  assert( nvars > 0 );
947  assert( vars != NULL );
948  assert( coeffs != NULL );
949  assert( infeasible != NULL );
950 
951  *infeasible = FALSE;
952 
953 #ifdef SCIP_DEBUG
954  consdata = SCIPconsGetData(cons);
955  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_cover_%s_%d", SCIPconsGetName(cons), consdata->debugcnt);
956  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
957  consdata->debugcnt += 1;
958 #else
959  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
960 #endif
961  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
962 
963  for (i = 0; i < nvars; ++i)
964  {
965  if ( coeffs[i] == 1 || coeffs[i] == -1 )
966  {
967  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], (SCIP_Real) coeffs[i]) );
968  }
969  }
970  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
971  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
972  SCIP_CALL( SCIPreleaseRow(scip, &row) );
973 
974  return SCIP_OKAY;
975 }
976 
977 
978 /** separate symresack cover inequalities
979  *
980  * We currently do NOT enter cuts into the pool.
981  */
982 static
983 SCIP_RETCODE separateSymresackCovers(
984  SCIP* scip, /**< SCIP pointer */
985  SCIP_CONS* cons, /**< constraint */
986  const SCIP_CONSDATA* consdata, /**< constraint data */
987  SCIP_Real* vals, /**< solution values of variables */
988  int* ngen, /**< pointer to store the number of separated covers */
989  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
990  )
991 {
992  SCIP_Real constobjective;
993  SCIP_Real* sepaobjective;
994  SCIP_Real tmpsoluobj = 0.0;
995  SCIP_Real maxsoluobj = 0.0;
996  int* tmpsolu;
997  int* maxsolu;
998  int* invperm;
999  int* perm;
1000  int nvars;
1001  int crit;
1002  int i;
1003 
1004  *infeasible = FALSE;
1005  *ngen = 0;
1006 
1007  assert( scip != NULL );
1008  assert( consdata != NULL );
1009 
1010  /* we do not have to take care of trivial constraints */
1011  if ( consdata->nvars < 2 )
1012  return SCIP_OKAY;
1013 
1014  assert( consdata->vars != NULL );
1015  assert( consdata->perm != NULL );
1016  assert( consdata->invperm != NULL );
1017  assert( infeasible != NULL );
1018  assert( ngen != NULL );
1019 
1020  nvars = consdata->nvars;
1021  perm = consdata->perm;
1022  invperm = consdata->invperm;
1023 
1024  /* initialize objective */
1025  SCIP_CALL( SCIPallocBufferArray(scip, &sepaobjective, nvars) );
1026 
1027  constobjective = 1.0; /* constant part of separation objective */
1028  for (i = 0; i < nvars; ++i)
1029  {
1030  if ( i < perm[i] )
1031  {
1032  sepaobjective[i] = vals[i];
1033  constobjective -= vals[i];
1034  }
1035  else
1036  sepaobjective[i] = vals[i] - 1.0;
1037  }
1038 
1039  /* allocate memory for temporary and global solution */
1040  SCIP_CALL( SCIPallocBufferArray(scip, &tmpsolu, nvars) );
1041  SCIP_CALL( SCIPallocBufferArray(scip, &maxsolu, nvars) );
1042 
1043  /* start separation procedure by iterating over critical rows */
1044  for (crit = 0; crit < nvars; ++crit)
1045  {
1046  /* there are no fixed points */
1047  assert( perm[crit] != crit );
1048 
1049  /* initialize temporary solution */
1050  for (i = 0; i < nvars; ++i)
1051  tmpsolu[i] = 2;
1052  tmpsoluobj = 0.0;
1053 
1054  /* perform fixings implied by the critical row */
1055  tmpsolu[crit] = 0;
1056  assert( invperm[crit] < nvars );
1057 
1058  tmpsolu[invperm[crit]] = 1;
1059  tmpsoluobj += sepaobjective[invperm[crit]];
1060 
1061  /* perform 1-fixings */
1062  i = invperm[crit];
1063  while ( i < crit )
1064  {
1065  i = invperm[i];
1066  tmpsolu[i] = 1;
1067  tmpsoluobj += sepaobjective[i];
1068  }
1069 
1070  /* row c cannot be critical */
1071  if ( i == crit )
1072  continue;
1073 
1074  assert( tmpsolu[crit] == 0 );
1075 
1076  /* perform 0-fixing */
1077  i = perm[crit];
1078  while ( i < crit )
1079  {
1080  tmpsolu[i] = 0;
1081  i = perm[i];
1082  }
1083 
1084  /* iterate over rows above the critical row */
1085  for (i = 0; i < crit; ++i)
1086  {
1087  SCIP_Real objimpact = 0.0;
1088  int j;
1089 
1090  /* skip already fixed entries */
1091  if ( tmpsolu[i] != 2 )
1092  continue;
1093 
1094  /* Check effect of fixing entry i to 1 and apply all implied fixing to other entries.
1095  *
1096  * Observe: Experiments indicate that entries are more often fixed to 1 than to 0.
1097  * For this reason, we apply the 1-fixings directly. If it turns out that the 1-fixings
1098  * have a negative impact on the objective, we undo these fixings afterwards and apply
1099  * 0-fixings instead. */
1100 
1101  /* check fixings in invperm direction */
1102  j = i;
1103  do
1104  {
1105  assert( tmpsolu[j] == 2 );
1106  tmpsolu[j] = 1;
1107  objimpact += sepaobjective[j];
1108  j = invperm[j];
1109  }
1110  while ( j < crit && j != i );
1111 
1112  /* if we do not detect a cycle */
1113  if ( j != i )
1114  {
1115  /* fix entry j since this is not done in the above do-while loop */
1116  assert( tmpsolu[j] == 2 );
1117  tmpsolu[j] = 1;
1118  objimpact += sepaobjective[j];
1119 
1120  /* check fixings in perm direction */
1121  j = perm[i];
1122  while ( j < crit )
1123  {
1124  assert( j != i );
1125  assert( tmpsolu[j] == 2 );
1126  tmpsolu[j] = 1;
1127  objimpact += sepaobjective[j];
1128  j = perm[j];
1129  }
1130 
1131  assert( j != crit );
1132  }
1133 
1134  /* if fixing entry i has a positive impact -> keep above fixings of entries to 1 */
1135  /* otherwise -> reset entries to 0 */
1136  if ( SCIPisEfficacious(scip, objimpact) )
1137  tmpsoluobj += objimpact;
1138  else
1139  {
1140  j = i;
1141  do
1142  {
1143  assert( tmpsolu[j] == 1 );
1144  tmpsolu[j] = 0;
1145  j = invperm[j];
1146  }
1147  while ( j < crit && j != i );
1148 
1149  /* if we do not detect a cycle */
1150  if ( j != i )
1151  {
1152  /* fix entry j since this is not done in the above do-while loop */
1153  assert( tmpsolu[j] == 1 );
1154  tmpsolu[j] = 0;
1155 
1156  /* check fixings in perm direction */
1157  j = perm[i];
1158  while ( j < crit )
1159  {
1160  assert( j != i );
1161  assert( tmpsolu[j] == 1 );
1162  tmpsolu[j] = 0;
1163  j = perm[j];
1164  }
1165 
1166  assert( j != crit );
1167  }
1168  }
1169  }
1170 
1171  /* iterate over unfixed entries below the critical row */
1172  for (i = crit + 1; i < nvars; ++i)
1173  {
1174  /* skip already fixed entries */
1175  if ( tmpsolu[i] != 2 )
1176  continue;
1177 
1178  if ( SCIPisEfficacious(scip, sepaobjective[i]) )
1179  {
1180  assert( tmpsolu[i] == 2 );
1181  tmpsolu[i] = 1;
1182  tmpsoluobj += sepaobjective[i];
1183  }
1184  else
1185  {
1186  assert( tmpsolu[i] == 2 );
1187  tmpsolu[i] = 0;
1188  }
1189  }
1190 
1191  /* check whether we have found a better solution which has positive separation objective*/
1192  if ( SCIPisEfficacious(scip, tmpsoluobj + constobjective - maxsoluobj) )
1193  {
1194  assert( SCIPisEfficacious(scip, tmpsoluobj + constobjective) );
1195  for (i = 0; i < nvars; ++i)
1196  maxsolu[i] = tmpsolu[i];
1197  maxsoluobj = tmpsoluobj + constobjective;
1198  }
1199  }
1200 
1201  /* Check whether the separation objective is positive, i.e., a violated cover was found. */
1202  if ( SCIPisEfficacious(scip, maxsoluobj) )
1203  {
1204  SCIP_Real rhs = -1.0;
1205  SCIP_Real lhs = 0.0;
1206 
1207  for (i = 0; i < nvars; ++i)
1208  {
1209  if ( i < perm[i] )
1210  {
1211  maxsolu[i] = maxsolu[i] - 1;
1212  lhs += vals[i] * maxsolu[i];
1213  }
1214  else
1215  {
1216  lhs += vals[i] * maxsolu[i];
1217  rhs += maxsolu[i];
1218  }
1219  }
1220 
1221  assert( SCIPisGT(scip, lhs, rhs) );
1222 
1223  /* add cover inequality */
1224  SCIP_CALL( addSymresackInequality(scip, cons, nvars, consdata->vars, maxsolu, rhs, infeasible) );
1225 
1226  if ( ! *infeasible )
1227  ++(*ngen);
1228  }
1229 
1230  SCIPfreeBufferArrayNull(scip, &maxsolu);
1231  SCIPfreeBufferArrayNull(scip, &tmpsolu);
1232  SCIPfreeBufferArrayNull(scip, &sepaobjective);
1233 
1234  return SCIP_OKAY;
1235 }
1236 
1237 
1238 /** check whether solution is feasible for symresacks */
1239 static
1240 SCIP_RETCODE checkSymresackSolution(
1241  SCIP* scip, /**< SCIP pointer */
1242  SCIP_CONS* cons, /**< constrained for which we check the solution */
1243  SCIP_SOL* sol, /**< solution to be checked */
1244  SCIP_RESULT* result, /**< pointer to store whether we detected infeasibility */
1245  SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
1246  )
1247 {
1248  SCIP_CONSDATA* consdata;
1249  SCIP_VAR** vars;
1250  int* invperm;
1251  int nvars;
1252  int i;
1253 
1254  assert( cons != NULL );
1255  consdata = SCIPconsGetData(cons);
1256  assert( consdata != NULL);
1257 
1258  /* we do not have to take care of trivial constraints */
1259  if ( consdata->nvars < 2 )
1260  return SCIP_OKAY;
1261 
1262  assert( consdata->vars != NULL );
1263  assert( consdata->invperm != NULL );
1264 
1265  SCIPdebugMsg(scip, "Check method for symresack constraint <%s> (%d rows) ...\n", SCIPconsGetName(cons), consdata->nvars);
1266 
1267  nvars = consdata->nvars;
1268  vars = consdata->vars;
1269  invperm = consdata->invperm;
1270 
1271  /* detect first non-constant pair of variables */
1272  for (i = 0; i < nvars; ++i)
1273  {
1274  SCIP_Real solval;
1275  int val1;
1276  int val2;
1277 
1278  /* there are no fixed points */
1279  assert( invperm[i] != i );
1280 
1281  /* get value of variable i and its inverse */
1282  solval = SCIPgetSolVal(scip, sol, vars[i]);
1283  assert( SCIPisFeasIntegral(scip, solval) );
1284  if ( solval > 0.5 )
1285  val1 = 1;
1286  else
1287  val1 = 0;
1288 
1289  solval = SCIPgetSolVal(scip, sol, vars[invperm[i]]);
1290  assert( SCIPisFeasIntegral(scip, solval) );
1291  if ( solval > 0.5 )
1292  val2 = 1;
1293  else
1294  val2 = 0;
1295 
1296  /* if we detected a constant pair */
1297  if ( val1 == val2 )
1298  continue;
1299  /* pair is (1,0) --> lexicographically maximal */
1300  else if ( val1 > val2 )
1301  break;
1302 
1303  /* pair is (0,1) --> solution is infeasible */
1304  assert( val2 > val1 );
1305  SCIPdebugMsg(scip, "Solution is infeasible.\n");
1306  *result = SCIP_INFEASIBLE;
1307 
1308  if ( printreason )
1309  SCIPinfoMessage(scip, NULL, "First non-constant pair (%d, %d) of variables has pattern (0,1).\n", i, invperm[i]);
1310 
1311  break;
1312  }
1313 
1314  return SCIP_OKAY;
1315 }
1316 
1317 
1318 /** Upgrade symresack constraints to orbisacks */
1319 static
1320 SCIP_RETCODE orbisackUpgrade(
1321  SCIP* scip, /**< SCIP pointer */
1322  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1323  const char* name, /**< name of constraint */
1324  int* perm, /**< permutation */
1325  SCIP_VAR** inputvars, /**< permuted variables array */
1326  int nvars, /**< size of perm array */
1327  SCIP_Bool* upgrade, /**< whether constraint was upgraded */
1328  SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
1329  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1330  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1331  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1332  * Usually set to TRUE. */
1333  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1334  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1335  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1336  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1337  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1338  * Usually set to TRUE. */
1339  SCIP_Bool local, /**< is constraint only valid locally?
1340  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1341  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1342  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1343  * adds coefficients to this constraint. */
1344  SCIP_Bool dynamic, /**< is constraint subject to aging?
1345  * Usually set to FALSE. Set to TRUE for own cuts which
1346  * are separated as constraints. */
1347  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1348  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1349  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1350  * if it may be moved to a more global node?
1351  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1352  )
1353 {
1354  SCIP_CONSHDLR* conshdlr;
1355  SCIP_VAR** vars1;
1356  SCIP_VAR** vars2;
1357  int nrows = 0;
1358  int i;
1359 
1360  assert( scip != NULL );
1361  assert( perm != NULL );
1362  assert( nvars > 0 );
1363  assert( inputvars != NULL );
1364  assert( upgrade != NULL );
1365 
1366  *upgrade = TRUE;
1367 
1368  /* check whether orbisack conshdlr is available */
1369  conshdlr = SCIPfindConshdlr(scip, "orbisack");
1370  if ( conshdlr == NULL )
1371  {
1372  *upgrade = FALSE;
1373  SCIPdebugMsg(scip, "Cannot check whether symresack constraint can be upgraded to orbisack constraint. ");
1374  SCIPdebugMsg(scip, "---> Orbisack constraint handler not found.\n");
1375 
1376  return SCIP_OKAY;
1377  }
1378 
1379  SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nvars) );
1380  SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nvars) );
1381 
1382  /* check whether permutation is a composition of 2-cycles */
1383  for (i = 0; i < nvars; ++i)
1384  {
1385  /* ignore non-binary variables */
1386  if ( ! SCIPvarIsBinary(inputvars[i]) )
1387  continue;
1388 
1389  if ( perm[perm[i]] != i )
1390  {
1391  *upgrade = FALSE;
1392  break;
1393  }
1394 
1395  if ( perm[i] > i )
1396  {
1397  vars1[nrows] = inputvars[i];
1398  vars2[nrows++] = inputvars[perm[i]];
1399 
1400  assert( nrows <= nvars );
1401  }
1402  }
1403 
1404  /* if permutation can be upgraded to an orbisack */
1405  if ( nrows == 0 )
1406  *upgrade = FALSE;
1407  else if ( *upgrade )
1408  {
1409  SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, ismodelcons,
1410  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1411  }
1412 
1413  SCIPfreeBufferArray(scip, &vars2);
1414  SCIPfreeBufferArray(scip, &vars1);
1415 
1416  return SCIP_OKAY;
1417 }
1418 
1419 
1420 /** creates a symmetry breaking constraint
1421  *
1422  * Depending on the given permutation, either an orbisack or symresack constraint
1423  * is created.
1424  */
1425 SCIP_RETCODE SCIPcreateSymbreakCons(
1426  SCIP* scip, /**< SCIP data structure */
1427  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1428  const char* name, /**< name of constraint */
1429  int* perm, /**< permutation */
1430  SCIP_VAR** vars, /**< variables */
1431  int nvars, /**< number of variables in vars array */
1432  SCIP_Bool ismodelcons, /**< whether the added constraint is a model constraint */
1433  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1434  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1435  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1436  * Usually set to TRUE. */
1437  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1438  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1439  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1440  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1441  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1442  * Usually set to TRUE. */
1443  SCIP_Bool local, /**< is constraint only valid locally?
1444  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1445  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1446  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1447  * adds coefficients to this constraint. */
1448  SCIP_Bool dynamic, /**< is constraint subject to aging?
1449  * Usually set to FALSE. Set to TRUE for own cuts which
1450  * are separated as constraints. */
1451  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1452  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1453  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1454  * if it may be moved to a more global node?
1455  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1456  )
1457 {
1458  SCIP_Bool upgrade = FALSE;
1459 
1460  assert( scip != NULL );
1461  assert( cons != NULL );
1462  assert( perm != NULL );
1463  assert( vars != NULL );
1464  assert( nvars > 0 );
1465 
1466  SCIP_CALL( orbisackUpgrade(scip, cons, name, perm, vars, nvars, &upgrade, ismodelcons,
1467  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1468 
1469  if ( ! upgrade )
1470  {
1471  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
1472  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1473  }
1474 
1475  return SCIP_OKAY;
1476 }
1477 
1478 
1479 /*--------------------------------------------------------------------------------------------
1480  *--------------------------------- SCIP functions -------------------------------------------
1481  *--------------------------------------------------------------------------------------------*/
1482 
1483 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1484 static
1485 SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
1486 { /*lint --e{715}*/
1487  assert(scip != NULL);
1488  assert(conshdlr != NULL);
1489  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1490 
1491  /* call inclusion method of constraint handler */
1492  SCIP_CALL( SCIPincludeConshdlrSymresack(scip) );
1493 
1494  *valid = TRUE;
1495 
1496  return SCIP_OKAY;
1497 }
1498 
1499 
1500 /** frees specific constraint data */
1501 static
1502 SCIP_DECL_CONSDELETE(consDeleteSymresack)
1503 { /*lint --e{715}*/
1504  assert( scip != NULL );
1505  assert( conshdlr != NULL );
1506  assert( consdata != NULL );
1507  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1508 
1509  SCIP_CALL( consdataFree(scip, consdata) );
1510 
1511  return SCIP_OKAY;
1512 }
1513 
1514 
1515 /** frees constraint handler */
1516 static
1517 SCIP_DECL_CONSFREE(consFreeSymresack)
1518 { /*lint --e{715}*/
1519  SCIP_CONSHDLRDATA* conshdlrdata;
1520 
1521  assert( scip != NULL );
1522  assert( conshdlr != NULL );
1523  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1524 
1525  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1526  assert( conshdlrdata != NULL );
1527 
1528  SCIPfreeBlockMemory(scip, &conshdlrdata);
1529 
1530  return SCIP_OKAY;
1531 }
1532 
1533 
1534 /** transforms constraint data into data belonging to the transformed problem */
1535 static
1536 SCIP_DECL_CONSTRANS(consTransSymresack)
1537 {
1538  SCIP_CONSDATA* sourcedata;
1539  SCIP_CONSDATA* consdata = NULL;
1540  int nvars;
1541  int i;
1542 
1543  assert( scip != NULL );
1544  assert( conshdlr != NULL );
1545  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1546  assert( sourcecons != NULL );
1547  assert( targetcons != NULL );
1548 
1549  SCIPdebugMsg(scip, "Transforming constraint.\n");
1550 
1551  /* get data of original constraint */
1552  sourcedata = SCIPconsGetData(sourcecons);
1553  assert( sourcedata != NULL);
1554 
1555  /* constraint might be empty and not deleted if no presolving took place */
1556  assert( sourcedata->nvars == 0 || sourcedata->vars != NULL );
1557  assert( sourcedata->nvars == 0 || sourcedata->perm != NULL );
1558  assert( sourcedata->nvars == 0 || sourcedata->invperm != NULL );
1559 #ifndef NDEBUG
1560  if ( sourcedata->ppupgrade )
1561  {
1562  assert( sourcedata->nvars > 0 );
1563  assert( sourcedata->ncycles != 0 );
1564  assert( sourcedata->cycledecomposition != NULL );
1565  for (i = 0; i < sourcedata->ncycles; ++i)
1566  {
1567  assert( sourcedata->cycledecomposition[i] != NULL );
1568  assert( sourcedata->cycledecomposition[i][0] != 0 );
1569  }
1570  }
1571 #endif
1572 
1573  /* create transformed constraint data (copy data where necessary) */
1574  nvars = sourcedata->nvars;
1575 
1576  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1577 
1578 #ifdef SCIP_DEBUG
1579  consdata->debugcnt = sourcedata->debugcnt;
1580 #endif
1581  consdata->nvars = nvars;
1582  consdata->ismodelcons = sourcedata->ismodelcons;
1583 
1584  if ( nvars > 0 )
1585  {
1586  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) );
1587  SCIP_CALL( SCIPgetTransformedVars(scip, nvars, sourcedata->vars, consdata->vars) );
1588  for (i = 0; i < nvars; ++i)
1589  {
1590  SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
1591  }
1592 
1593  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->perm, sourcedata->perm, nvars) );
1594  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->invperm, sourcedata->invperm, nvars) );
1595 
1596  consdata->ppupgrade = sourcedata->ppupgrade;
1597 
1598  if ( sourcedata->ppupgrade )
1599  {
1600  consdata->ncycles = sourcedata->ncycles;
1601  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition, sourcedata->cycledecomposition, sourcedata->ncycles) );
1602  for (i = 0; i < sourcedata->ncycles; ++i)
1603  {
1604  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition[i], sourcedata->cycledecomposition[i], nvars + 1) ); /*lint !e866*/
1605  }
1606  }
1607  }
1608  else
1609  {
1610  consdata->perm = NULL;
1611  consdata->invperm = NULL;
1612  consdata->ppupgrade = FALSE;
1613  consdata->ncycles = 0;
1614  consdata->cycledecomposition = NULL;
1615  }
1616 
1617  /* create transformed constraint */
1618  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1619  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1620  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1621  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1622  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1623  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1624 
1625  return SCIP_OKAY;
1626 }
1627 
1628 
1629 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1630 static
1631 SCIP_DECL_CONSINITLP(consInitlpSymresack)
1632 {
1633  int c;
1634  SCIP_CONSHDLRDATA* conshdlrdata;
1635 
1636  assert( infeasible != NULL );
1637  *infeasible = FALSE;
1638 
1639  assert( scip != NULL );
1640  assert( conshdlr != NULL );
1641  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1642 
1643  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1644  assert( conshdlrdata != NULL );
1645 
1646  /* loop through constraints */
1647  for (c = 0; c < nconss; ++c)
1648  {
1649  assert( conss[c] != NULL );
1650 
1651  SCIPdebugMsg(scip, "Generating initial symresack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1652 
1653  SCIP_CALL( initLP(scip, conss[c], conshdlrdata->checkmonotonicity, infeasible) );
1654  if ( *infeasible )
1655  break;
1656  }
1657  SCIPdebugMsg(scip, "Generated initial symresack cuts.\n");
1658 
1659  return SCIP_OKAY;
1660 }
1661 
1662 
1663 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1664 static
1665 SCIP_DECL_CONSINITSOL(consInitsolSymresack)
1666 {
1667  SCIP_CONSHDLRDATA* conshdlrdata;
1668  int c;
1669 
1670  assert( scip != NULL );
1671  assert( conshdlr != NULL );
1672  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1673 
1674  /* determine maximum number of vars in a symresack constraint */
1675  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1676  assert( conshdlrdata != NULL );
1677 
1678  conshdlrdata->maxnvars = 0;
1679 
1680  /* loop through constraints */
1681  for (c = 0; c < nconss; ++c)
1682  {
1683  SCIP_CONSDATA* consdata;
1684 
1685  assert( conss[c] != NULL );
1686 
1687  consdata = SCIPconsGetData(conss[c]);
1688  assert( consdata != NULL );
1689 
1690  /* update conshdlrdata if necessary */
1691  if ( consdata->nvars > conshdlrdata->maxnvars )
1692  conshdlrdata->maxnvars = consdata->nvars;
1693  }
1694 
1695  return SCIP_OKAY;
1696 }
1697 
1698 
1699 /** separation method of constraint handler for LP solution */
1700 static
1701 SCIP_DECL_CONSSEPALP(consSepalpSymresack)
1702 { /*lint --e{715}*/
1703  SCIP_CONSHDLRDATA* conshdlrdata;
1704  SCIP_CONSDATA* consdata;
1705  SCIP_Real* vals;
1706  int maxnvars;
1707  int c;
1708 
1709  assert( scip != NULL );
1710  assert( conshdlr != NULL );
1711  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1712  assert( result != NULL );
1713 
1714  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
1715 
1716  *result = SCIP_DIDNOTRUN;
1717 
1718  /* if solution is not integer */
1719  if ( SCIPgetNLPBranchCands(scip) == 0 )
1720  return SCIP_OKAY;
1721 
1722  if ( nconss == 0 )
1723  return SCIP_OKAY;
1724 
1725  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1726  assert( conshdlrdata != NULL );
1727 
1728  maxnvars = conshdlrdata->maxnvars;
1729  assert( maxnvars > 0 );
1730 
1731  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1732 
1733  /* loop through constraints */
1734  for (c = 0; c < nconss; ++c)
1735  {
1736  SCIP_Bool infeasible = FALSE;
1737  int ngen = 0;
1738 
1739  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1740 
1741  /* get data of constraint */
1742  assert( conss[c] != NULL );
1743  consdata = SCIPconsGetData(conss[c]);
1744 
1745  if ( consdata->nvars == 0 )
1746  continue;
1747 
1748  /* get solution */
1749  assert( consdata->nvars <= maxnvars );
1750  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
1751  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1752 
1753  if ( infeasible )
1754  {
1755  *result = SCIP_CUTOFF;
1756  SCIPfreeBufferArray(scip, &vals);
1757 
1758  return SCIP_OKAY;
1759  }
1760 
1761  if ( ngen > 0 )
1762  *result = SCIP_SEPARATED;
1763 
1764  if ( *result == SCIP_DIDNOTRUN )
1765  *result = SCIP_DIDNOTFIND;
1766  }
1767  SCIPfreeBufferArray(scip, &vals);
1768 
1769  return SCIP_OKAY;
1770 }
1771 
1772 
1773 /** separation method of constraint handler for arbitrary primal solution */
1774 static
1775 SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
1776 { /*lint --e{715}*/
1777  SCIP_CONSHDLRDATA* conshdlrdata;
1778  SCIP_CONSDATA* consdata;
1779  SCIP_Real* vals;
1780  int maxnvars;
1781  int c;
1782 
1783  assert( scip != NULL );
1784  assert( conshdlr != NULL );
1785  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1786  assert( result != NULL );
1787 
1788  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
1789 
1790  *result = SCIP_DIDNOTRUN;
1791 
1792  if ( nconss == 0 )
1793  return SCIP_OKAY;
1794 
1795  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1796  assert( conshdlrdata != NULL );
1797 
1798  maxnvars = conshdlrdata->maxnvars;
1799  assert( maxnvars > 0 );
1800 
1801  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1802 
1803  /* loop through constraints */
1804  for (c = 0; c < nconss; ++c)
1805  {
1806  SCIP_Bool infeasible = FALSE;
1807  int ngen = 0;
1808 
1809  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1810 
1811  /* get data of constraint */
1812  assert( conss[c] != NULL );
1813  consdata = SCIPconsGetData(conss[c]);
1814 
1815  if ( consdata->nvars == 0 )
1816  continue;
1817 
1818  /* get solution */
1819  assert( consdata->nvars <= maxnvars );
1820  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
1821  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1822 
1823  if ( infeasible )
1824  {
1825  *result = SCIP_CUTOFF;
1826  SCIPfreeBufferArray(scip, &vals);
1827 
1828  return SCIP_OKAY;
1829  }
1830 
1831  if ( ngen > 0 )
1832  *result = SCIP_SEPARATED;
1833 
1834  if ( *result == SCIP_DIDNOTRUN )
1835  *result = SCIP_DIDNOTFIND;
1836  }
1837  SCIPfreeBufferArray(scip, &vals);
1838 
1839  return SCIP_OKAY;
1840 }
1841 
1842 
1843 /** constraint enforcing method of constraint handler for LP solutions.
1844  *
1845  * To check feasibility, we separate cover inequalities.
1846  *
1847  * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
1848  */
1849 static
1850 SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
1851 { /*lint --e{715}*/
1852  SCIP_CONSDATA* consdata;
1853  int c;
1854 
1855  assert( scip != NULL );
1856  assert( conshdlr != NULL );
1857  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1858  assert( result != NULL );
1859 
1860  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (lp solutions) ...\n");
1861 
1862  /* we have a negative priority, so we should come after the integrality conshdlr. */
1863  assert( SCIPgetNLPBranchCands(scip) == 0 );
1864 
1865  *result = SCIP_FEASIBLE;
1866 
1867  if ( nconss > 0 )
1868  {
1869  SCIP_CONSHDLRDATA* conshdlrdata;
1870  SCIP_Real* vals;
1871  int maxnvars;
1872 
1873  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1874  assert( conshdlrdata != NULL );
1875 
1876  maxnvars = conshdlrdata->maxnvars;
1877  assert( maxnvars > 0 );
1878 
1879  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1880 
1881  /* loop through constraints */
1882  for (c = 0; c < nconss; ++c)
1883  {
1884  SCIP_Bool infeasible = FALSE;
1885  int ngen = 0;
1886 
1887  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1888 
1889  /* get data of constraint */
1890  assert( conss[c] != NULL );
1891  consdata = SCIPconsGetData(conss[c]);
1892  assert( consdata != NULL );
1893 
1894  /* do not enforce non-model constraints */
1895  if ( !consdata->ismodelcons )
1896  continue;
1897 
1898  if ( consdata->nvars == 0 )
1899  continue;
1900 
1901  /* get solution */
1902  assert( consdata->nvars <= maxnvars );
1903  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
1904  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1905 
1906  if ( infeasible )
1907  {
1908  *result = SCIP_CUTOFF;
1909  SCIPfreeBufferArray(scip, &vals);
1910 
1911  return SCIP_OKAY;
1912  }
1913 
1914  /* SCIPdebugMsg(scip, "Generated symresack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); */
1915 
1916  if ( ngen > 0 )
1917  *result = SCIP_SEPARATED;
1918  }
1919  SCIPfreeBufferArray(scip, &vals);
1920  }
1921 
1922  return SCIP_OKAY;
1923 }
1924 
1925 
1926 /** constraint enforcing method of constraint handler for pseudo solutions */
1927 static
1928 SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
1929 { /*lint --e{715}*/
1930  SCIP_CONSDATA* consdata;
1931  int c;
1932 
1933  assert( scip != NULL );
1934  assert( conshdlr != NULL );
1935  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1936  assert( result != NULL );
1937 
1938  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (pseudo solutions) ...\n");
1939 
1940  *result = SCIP_FEASIBLE;
1941 
1942  if ( objinfeasible || solinfeasible )
1943  return SCIP_OKAY;
1944 
1945  /* loop through constraints */
1946  for (c = 0; c < nconss; ++c)
1947  {
1948  consdata = SCIPconsGetData(conss[c]);
1949  assert( consdata != NULL );
1950 
1951  /* do not enforce non-model constraints */
1952  if ( !consdata->ismodelcons )
1953  continue;
1954 
1955  SCIP_CALL( checkSymresackSolution(scip, conss[c], NULL, result, FALSE) );
1956 
1957  if ( *result == SCIP_INFEASIBLE )
1958  break;
1959  }
1960 
1961  return SCIP_OKAY;
1962 }
1963 
1964 
1965 /** constraint enforcing method of constraint handler for relaxation solutions
1966  *
1967  * To check feasibility, we separate cover inequalities.
1968  *
1969  */
1970 static
1971 SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
1972 { /*lint --e{715}*/
1973  SCIP_CONSDATA* consdata;
1974  int c;
1975 
1976  assert( scip != NULL );
1977  assert( conshdlr != NULL );
1978  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1979  assert( result != NULL );
1980 
1981  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (relaxation solutions) ...\n");
1982 
1983  /* we have a negative priority, so we should come after the integrality conshdlr. */
1984  assert( SCIPgetNLPBranchCands(scip) == 0 );
1985 
1986  *result = SCIP_FEASIBLE;
1987 
1988  if ( nconss > 0 )
1989  {
1990  SCIP_CONSHDLRDATA* conshdlrdata;
1991  SCIP_Real* vals;
1992  int maxnvars;
1993 
1994  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1995  assert( conshdlrdata != NULL );
1996 
1997  maxnvars = conshdlrdata->maxnvars;
1998  assert( maxnvars > 0 );
1999 
2000  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2001 
2002  /* loop through constraints */
2003  for (c = 0; c < nconss; ++c)
2004  {
2005  SCIP_Bool infeasible = FALSE;
2006  int ngen = 0;
2007 
2008  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2009 
2010  /* get data of constraint */
2011  assert( conss[c] != NULL );
2012  consdata = SCIPconsGetData(conss[c]);
2013  assert( consdata != NULL );
2014 
2015  /* do not enforce non-model constraints */
2016  if ( !consdata->ismodelcons )
2017  continue;
2018 
2019  if ( consdata->nvars == 0 )
2020  continue;
2021 
2022  /* get solution */
2023  assert( consdata->nvars <= maxnvars );
2024  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
2025  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2026 
2027  if ( infeasible )
2028  {
2029  *result = SCIP_CUTOFF;
2030  SCIPfreeBufferArray(scip, &vals);
2031 
2032  return SCIP_OKAY;
2033  }
2034 
2035  if ( ngen > 0 )
2036  *result = SCIP_SEPARATED;
2037  }
2038  SCIPfreeBufferArray(scip, &vals);
2039  }
2040 
2041  return SCIP_OKAY;
2042 }
2043 
2044 
2045 /** feasibility check method of constraint handler for integral solutions */
2046 static
2047 SCIP_DECL_CONSCHECK(consCheckSymresack)
2048 { /*lint --e{715}*/
2049  SCIP_CONSDATA* consdata;
2050  int c;
2051 
2052  assert( scip != NULL );
2053  assert( conshdlr != NULL );
2054  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2055  assert( result != NULL );
2056 
2057  *result = SCIP_FEASIBLE;
2058 
2059  /* loop through constraints */
2060  for (c = 0; c < nconss; ++c)
2061  {
2062  consdata = SCIPconsGetData(conss[c]);
2063  assert( consdata != NULL );
2064 
2065  /* do not check non-model constraints */
2066  if ( !consdata->ismodelcons )
2067  continue;
2068 
2069  SCIP_CALL( checkSymresackSolution(scip, conss[c], sol, result, printreason) );
2070 
2071  if ( *result == SCIP_INFEASIBLE )
2072  break;
2073  }
2074 
2075  if ( *result == SCIP_FEASIBLE )
2076  SCIPdebugMsg(scip, "Solution is feasible.\n");
2077 
2078  return SCIP_OKAY;
2079 }
2080 
2081 
2082 /** domain propagation method of constraint handler */
2083 static
2084 SCIP_DECL_CONSPROP(consPropSymresack)
2085 { /*lint --e{715}*/
2086  int c;
2087  SCIP_Bool success = FALSE;
2088 
2089  assert( scip != NULL );
2090  assert( conshdlr != NULL );
2091  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2092  assert( result != NULL );
2093 
2094  *result = SCIP_DIDNOTRUN;
2095 
2096  SCIPdebugMsg(scip, "Propagation method of symresack constraint handler.\n");
2097 
2098  /* loop through constraints */
2099  for (c = 0; c < nconss; ++c)
2100  {
2101  SCIP_Bool infeasible = FALSE;
2102  int ngen = 0;
2103 
2104  assert( conss[c] != NULL );
2105 
2106  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2107 
2108  if ( infeasible )
2109  {
2110  *result = SCIP_CUTOFF;
2111  return SCIP_OKAY;
2112  }
2113 
2114  success = success || ( ngen > 0 );
2115 
2116  *result = SCIP_DIDNOTFIND;
2117  }
2118 
2119  if ( success )
2120  {
2121  *result = SCIP_REDUCEDDOM;
2122  return SCIP_OKAY;
2123  }
2124 
2125  return SCIP_OKAY;
2126 }
2127 
2128 
2129 /** presolving method of constraint handler */
2130 static
2131 SCIP_DECL_CONSPRESOL(consPresolSymresack)
2132 { /*lint --e{715}*/
2133  int c;
2134  SCIP_Bool success = FALSE;
2135  int oldndelconss;
2136 
2137  assert( scip != NULL );
2138  assert( conshdlr != NULL );
2139  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2140  assert( result != NULL );
2141 
2142  oldndelconss = *ndelconss;
2143 
2144  SCIPdebugMsg(scip, "Presolving method of symresack constraint handler. Propagating symresack inequalities.\n");
2145  *result = SCIP_DIDNOTRUN;
2146 
2147  /* loop through constraints */
2148  for (c = 0; c < nconss; ++c)
2149  {
2150  SCIP_Bool infeasible = FALSE;
2151  SCIP_CONSDATA* consdata;
2152  int ngen = 0;
2153 
2154  assert( conss[c] != NULL );
2155 
2156  consdata = SCIPconsGetData(conss[c]);
2157  assert( consdata != NULL );
2158 
2159  /* avoid trivial problems */
2160  if ( consdata->nvars == 0 )
2161  {
2162  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2163  (*ndelconss)++;
2164  }
2165  else
2166  {
2167  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2168  }
2169 
2170  if ( infeasible )
2171  {
2172  *result = SCIP_CUTOFF;
2173  break;
2174  }
2175 
2176  if ( ngen > 0 )
2177  {
2178  *nfixedvars += ngen;
2179  success = TRUE;
2180  }
2181 
2182  *result = SCIP_DIDNOTFIND;
2183  }
2184 
2185  if ( *ndelconss > oldndelconss || success )
2186  *result = SCIP_SUCCESS;
2187 
2188  return SCIP_OKAY;
2189 }
2190 
2191 
2192 /** Propagation resolution for conflict analysis */
2193 static
2194 SCIP_DECL_CONSRESPROP(consRespropSymresack)
2195 { /*lint --e{715}*/
2196  SCIP_CONSDATA* consdata;
2197  SCIP_VAR** vars;
2198  int* invperm;
2199  int nvars;
2200  int i;
2201 
2202  assert( scip != NULL );
2203  assert( conshdlr != NULL );
2204  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2205  assert( cons != NULL );
2206  assert( infervar != NULL );
2207  assert( bdchgidx != NULL );
2208  assert( result != NULL );
2209 
2210  SCIPdebugMsg(scip, "Propagation resolution method of symresack constraint handler.\n");
2211 
2212  *result = SCIP_DIDNOTFIND;
2213 
2214  consdata = SCIPconsGetData(cons);
2215  assert( consdata != NULL );
2216 
2217  /* we do not have to take care of trivial constraints */
2218  if ( consdata->nvars < 2 )
2219  return SCIP_OKAY;
2220 
2221  assert( consdata->vars != NULL );
2222  assert( consdata->invperm != NULL );
2223 
2224  vars = consdata->vars;
2225  nvars = consdata->nvars;
2226  invperm = consdata->invperm;
2227 
2228  assert( 0 <= inferinfo && inferinfo < (2 * nvars - 1) );
2229 
2230  /* if first part of variable pair was fixed to 0 */
2231  if ( inferinfo < nvars )
2232  {
2233  assert( vars[invperm[inferinfo]] == infervar );
2234  assert( SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, FALSE) > 0.5
2235  && SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, TRUE) < 0.5 );
2236 
2237  if ( SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, FALSE) > 0.5
2238  && SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, TRUE) < 0.5 )
2239  {
2240  SCIPdebugMsg(scip, " -> reason for setting x[%d] = 0 was fixing x[%d] to 0 ", invperm[inferinfo], inferinfo);
2241  SCIPdebugMsg(scip, "and each pair of binary variables before (%d,%d) which are not fixed points is constant.\n",
2242  inferinfo, invperm[inferinfo]);
2243 
2244  SCIP_CALL( SCIPaddConflictUb(scip, vars[inferinfo], bdchgidx) );
2245 
2246  for (i = 0; i < inferinfo; ++i)
2247  {
2248  /* there are no fixed points */
2249  assert( invperm[i] != i );
2250 
2251  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2252  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2253  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2254  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2255  }
2256  }
2257  }
2258  /* if second part of variable pair was fixed to 1 */
2259  else
2260  {
2261  int inferinfo2;
2262 
2263  inferinfo2 = inferinfo - nvars;
2264  assert( vars[inferinfo2] == infervar );
2265  assert( SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, FALSE) < 0.5
2266  && SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, TRUE) > 0.5 );
2267 
2268  if ( SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, FALSE) < 0.5
2269  && SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, TRUE) > 0.5 )
2270  {
2271  SCIPdebugMsg(scip, " -> reason for setting x[%d] = 1 was fixing x[%d] to 1 ", inferinfo2, invperm[inferinfo2]);
2272  SCIPdebugMsg(scip, "and each pair of binary variables before (%d,%d) which are not fixed points is constant.\n",
2273  inferinfo2, invperm[inferinfo2]);
2274 
2275  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[inferinfo2]], bdchgidx) );
2276 
2277  for (i = 0; i < inferinfo2; ++i)
2278  {
2279  /* there are no fixed points */
2280  assert( invperm[i] != i );
2281 
2282  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2283  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2284  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2285  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2286  }
2287  }
2288  }
2289 
2290  *result = SCIP_SUCCESS;
2291 
2292  return SCIP_OKAY;
2293 }
2294 
2295 
2296 /** lock variables
2297  *
2298  * We assume we have only one global (void) constraint and lock all binary variables
2299  * which do not correspond to fixed points of the permutation.
2300  *
2301  * - Symresack constraints may get violated if the variables with a negative coefficient
2302  * in the FD inequality are rounded down, we therefor call
2303  * SCIPaddVarLocksType(..., nlockspos, nlocksneg).
2304  * - Symresack constraints may get violated if the variables with a positive coefficient
2305  * in the FD inequality are rounded up, we therefor call
2306  * SCIPaddVarLocksType(..., nlocksneg, nlockspo ).
2307  */
2308 static
2309 SCIP_DECL_CONSLOCK(consLockSymresack)
2310 { /*lint --e{715}*/
2311  SCIP_CONSDATA* consdata;
2312  SCIP_VAR** vars;
2313  int* perm;
2314  int nvars;
2315  int i;
2316 
2317  assert( scip != NULL );
2318  assert( conshdlr != NULL );
2319  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2320  assert( cons != NULL );
2321 
2322  SCIPdebugMsg(scip, "Locking method for symresack constraint handler.\n");
2323 
2324  /* get data of original constraint */
2325  consdata = SCIPconsGetData(cons);
2326  assert( consdata != NULL );
2327 
2328  /* we do not have to take care of trivial constraints */
2329  if ( consdata->nvars < 2 )
2330  return SCIP_OKAY;
2331 
2332  assert( consdata->vars != NULL );
2333  assert( consdata->perm != NULL );
2334 
2335  nvars = consdata->nvars;
2336  vars = consdata->vars;
2337  perm = consdata->perm;
2338 
2339  for (i = 0; i < nvars; ++i)
2340  {
2341  /* due to clean-up in consdataCreate, there are no fixed points */
2342  assert( perm[i] != i );
2343 
2344  if ( perm[i] > i )
2345  {
2346  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlockspos, nlocksneg) );
2347  }
2348  else
2349  {
2350  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlocksneg, nlockspos) );
2351  }
2352  }
2353 
2354  return SCIP_OKAY;
2355 }
2356 
2357 
2358 /** constraint copying method of constraint handler */
2359 static
2360 SCIP_DECL_CONSCOPY(consCopySymresack)
2361 {
2362  SCIP_CONSHDLRDATA* conshdlrdata;
2363  SCIP_CONSDATA* sourcedata;
2364  SCIP_VAR** sourcevars;
2365  SCIP_VAR** vars;
2366  int nvars;
2367  int i;
2368 
2369  assert( scip != NULL );
2370  assert( cons != NULL );
2371  assert( sourcescip != NULL );
2372  assert( sourceconshdlr != NULL );
2373  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
2374  assert( sourcecons != NULL );
2375  assert( varmap != NULL );
2376  assert( valid != NULL );
2377 
2378  *valid = TRUE;
2379 
2380  SCIPdebugMsg(scip, "Copying method for symresack constraint handler.\n");
2381 
2382  sourcedata = SCIPconsGetData(sourcecons);
2383  assert( sourcedata != NULL );
2384  assert( sourcedata->vars != NULL );
2385  assert( sourcedata->perm != NULL );
2386  assert( sourcedata->nvars > 0 );
2387 
2388  conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
2389  assert( conshdlrdata != NULL );
2390 
2391  /* do not copy non-model constraints */
2392  if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
2393  {
2394  *valid = FALSE;
2395 
2396  return SCIP_OKAY;
2397  }
2398 
2399  sourcevars = sourcedata->vars;
2400  nvars = sourcedata->nvars;
2401 
2402  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2403 
2404  for (i = 0; i < nvars && *valid; ++i)
2405  {
2406  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i], &(vars[i]), varmap, consmap, global, valid) );
2407  assert( !(*valid) || vars[i] != NULL );
2408  }
2409 
2410  /* only create the target constraint, if all variables could be copied */
2411  if ( *valid )
2412  {
2413  /* create copied constraint */
2414  if ( name == NULL )
2415  name = SCIPconsGetName(sourcecons);
2416 
2417  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, sourcedata->perm, vars, nvars, sourcedata->ismodelcons,
2418  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2419  }
2420 
2421  SCIPfreeBufferArray(scip, &vars);
2422 
2423  return SCIP_OKAY;
2424 }
2425 
2426 
2427 /** constraint display method of constraint handler
2428  *
2429  * The constraint handler should output a representation of the constraint into the given text file.
2430  */
2431 static
2432 SCIP_DECL_CONSPRINT(consPrintSymresack)
2433 { /*lint --e{715}*/
2434  SCIP_CONSDATA* consdata;
2435  SCIP_VAR** vars;
2436  SCIP_Bool* covered;
2437  int* perm;
2438  int nvars;
2439  int i;
2440  int j;
2441 
2442  assert( scip != NULL );
2443  assert( conshdlr != NULL );
2444  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2445  assert( cons != NULL );
2446 
2447  consdata = SCIPconsGetData(cons);
2448  assert( consdata != NULL );
2449 
2450  SCIPdebugMsg(scip, "Printing method for symresack constraint handler\n");
2451 
2452  /* we do not have to take care of trivial constraints */
2453  if ( consdata->nvars < 2 )
2454  {
2455  SCIPinfoMessage(scip, file, "symresack()");
2456  return SCIP_OKAY;
2457  }
2458 
2459  assert( consdata->vars != NULL );
2460  assert( consdata->perm != NULL );
2461 
2462  vars = consdata->vars;
2463  nvars = consdata->nvars;
2464  perm = consdata->perm;
2465 
2466  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
2467  for (i = 0; i < nvars; ++i)
2468  covered[i] = FALSE;
2469 
2470  if ( consdata->ppupgrade )
2471  SCIPinfoMessage(scip, file, "ppSymresack(");
2472  else
2473  SCIPinfoMessage(scip, file, "symresack(");
2474 
2475  for (i = 0; i < nvars; ++i)
2476  {
2477  if ( covered[i] )
2478  continue;
2479 
2480  /* print cycle of perm containing i */
2481  SCIPinfoMessage(scip, file, "[%s", SCIPvarGetName(vars[i]));
2482  covered[i] = TRUE;
2483  j = perm[i];
2484  while ( j != i )
2485  {
2486  SCIPinfoMessage(scip, file, ",%s", SCIPvarGetName(vars[j]));
2487  covered[j] = TRUE;
2488  j = perm[j];
2489  }
2490  SCIPinfoMessage(scip, file, "]");
2491  }
2492  SCIPinfoMessage(scip, file, ")");
2493 
2494  SCIPfreeBufferArray(scip, &covered);
2495 
2496  return SCIP_OKAY;
2497 }
2498 
2499 
2500 /** constraint method of constraint handler which returns the variables (if possible) */
2501 static
2502 SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
2503 { /*lint --e{715}*/
2504  SCIP_CONSDATA* consdata;
2505 
2506  assert( cons != NULL );
2507  assert( success != NULL );
2508  assert( vars != NULL );
2509 
2510  consdata = SCIPconsGetData(cons);
2511  assert( consdata != NULL );
2512 
2513  if ( varssize < consdata->nvars )
2514  (*success) = FALSE;
2515  else
2516  {
2517  int cnt = 0;
2518  int i;
2519 
2520  for (i = 0; i < consdata->nvars; ++i)
2521  vars[cnt++] = consdata->vars[i];
2522  (*success) = TRUE;
2523  }
2524 
2525  return SCIP_OKAY;
2526 }
2527 
2528 
2529 /** constraint method of constraint handler which returns the number of variables (if possible) */
2530 static
2531 SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
2532 { /*lint --e{715}*/
2533  SCIP_CONSDATA* consdata;
2534 
2535  assert( cons != NULL );
2536  assert( success != NULL );
2537  assert( nvars != NULL );
2538 
2539  consdata = SCIPconsGetData(cons);
2540  assert( consdata != NULL );
2541 
2542  (*nvars) = consdata->nvars;
2543  (*success) = TRUE;
2544 
2545  return SCIP_OKAY;
2546 }
2547 
2548 
2549 /** creates the handler for symresack constraints and includes it in SCIP */
2550 SCIP_RETCODE SCIPincludeConshdlrSymresack(
2551  SCIP* scip /**< SCIP data structure */
2552  )
2553 {
2554  SCIP_CONSHDLRDATA* conshdlrdata = NULL;
2555  SCIP_CONSHDLR* conshdlr;
2556 
2557  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2558 
2559  /* include constraint handler */
2560  SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2561  CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2562  consEnfolpSymresack, consEnfopsSymresack, consCheckSymresack, consLockSymresack,
2563  conshdlrdata) );
2564  assert( conshdlr != NULL );
2565 
2566  /* set non-fundamental callbacks via specific setter functions */
2567  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySymresack, consCopySymresack) );
2568  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSymresack) );
2569  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSymresack) );
2570  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSymresack) );
2571  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSymresack) );
2572  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSymresack) );
2573  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSymresack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2574  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSymresack) );
2575  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSymresack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
2576  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSymresack) );
2577  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSymresack, consSepasolSymresack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2578  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSymresack) );
2579  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSymresack) );
2580  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSymresack) );
2581 
2582  /* whether we allow upgrading to packing/partioning symresack constraints*/
2583  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/ppsymresack",
2584  "Upgrade symresack constraints to packing/partioning symresacks?",
2585  &conshdlrdata->checkppsymresack, TRUE, DEFAULT_PPSYMRESACK, NULL, NULL) );
2586 
2587  /* whether we check for monotonicity of perm when upgrading to packing/partioning symresacks */
2588  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkmonotonicity",
2589  "Check whether permutation is monotone when upgrading to packing/partioning symresacks?",
2590  &conshdlrdata->checkmonotonicity, TRUE, DEFAULT_CHECKMONOTONICITY, NULL, NULL) );
2591 
2592  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
2593  "Whether symresack constraints should be forced to be copied to sub SCIPs.",
2594  &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
2595 
2596  return SCIP_OKAY;
2597 }
2598 
2599 
2600 /*
2601  * constraint specific interface methods
2602  */
2603 
2604 /** creates and captures a symresack constraint
2605  *
2606  * In a presolving step, we check whether the permutation acts only on binary points. Otherwise, we eliminate
2607  * the non-binary variables from the permutation.
2608  *
2609  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
2610  */
2611 SCIP_RETCODE SCIPcreateConsSymresack(
2612  SCIP* scip, /**< SCIP data structure */
2613  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2614  const char* name, /**< name of constraint */
2615  int* perm, /**< permutation */
2616  SCIP_VAR** vars, /**< variables */
2617  int nvars, /**< number of variables in vars array */
2618  SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
2619  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2620  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2621  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2622  * Usually set to TRUE. */
2623  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2624  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2625  SCIP_Bool check, /**< should the constraint be checked for feasibility?
2626  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2627  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2628  * Usually set to TRUE. */
2629  SCIP_Bool local, /**< is constraint only valid locally?
2630  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2631  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2632  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2633  * adds coefficients to this constraint. */
2634  SCIP_Bool dynamic, /**< is constraint subject to aging?
2635  * Usually set to FALSE. Set to TRUE for own cuts which
2636  * are separated as constraints. */
2637  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2638  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2639  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2640  * if it may be moved to a more global node?
2641  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2642  )
2643 {
2644  SCIP_CONSHDLR* conshdlr;
2645  SCIP_CONSDATA* consdata;
2646 
2647  assert( cons != NULL );
2648  assert( nvars > 0 );
2649 
2650  /* find the symresack constraint handler */
2651  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2652  if ( conshdlr == NULL )
2653  {
2654  SCIPerrorMessage("Symresack constraint handler not found.\n");
2655  return SCIP_PLUGINNOTFOUND;
2656  }
2657 
2658  /* create constraint data */
2659  SCIP_CALL( consdataCreate(scip, conshdlr, &consdata, vars, nvars, perm, ismodelcons) );
2660 
2661  /* create constraint */
2662  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate && (! consdata->ppupgrade), enforce, check, propagate,
2663  local, modifiable, dynamic, removable, stickingatnode) );
2664 
2665  return SCIP_OKAY;
2666 }
2667 
2668 
2669 /** creates and captures a symresack constraint
2670  * in its most basic variant, i.e., with all constraint flags set to their default values
2671  *
2672  * In a presolving step, we remove all fixed points and cycles that act on non-binary variables of the permutation
2673  *
2674  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
2675  */
2676 SCIP_RETCODE SCIPcreateConsBasicSymresack(
2677  SCIP* scip, /**< SCIP data structure */
2678  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2679  const char* name, /**< name of constraint */
2680  int* perm, /**< permutation */
2681  SCIP_VAR** vars, /**< variables */
2682  int nvars, /**< number of variables in vars array */
2683  SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
2684  )
2685 {
2686  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
2687  TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2688 
2689  return SCIP_OKAY;
2690 }
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_DIDNOTRUN
Definition: type_result.h:33
CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY
Definition: cons_symresack.c:78
SCIP_INFEASIBLE
Definition: type_result.h:37
SCIPisConflictAnalysisApplicable
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:292
CONSHDLR_PRESOLTIMING
#define CONSHDLR_PRESOLTIMING
Definition: cons_symresack.c:91
SCIPsetConshdlrTrans
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIPvarIsNegated
SCIP_EXPORT SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17172
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_DECL_CONSPROP
static SCIP_DECL_CONSPROP(consPropSymresack)
Definition: cons_symresack.c:2085
scip_param.h
public methods for SCIP parameter handling
SCIPcreateCons
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
SCIPconsIsLocal
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8328
scip_mem.h
public methods for memory management
SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:50
SCIPsetConshdlrEnforelax
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
SCIP_DECL_CONSFREE
static SCIP_DECL_CONSFREE(consFreeSymresack)
Definition: cons_symresack.c:1518
SCIPallocClearBufferArray
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition: cons_symresack.c:75
consdataFree
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_symresack.c:143
SCIPconsIsChecked
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8288
SCIPincludeConshdlrBasic
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
SCIPaddVarLocksType
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4263
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:273
SCIPgetTransformedVars
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1484
scip_conflict.h
public methods for conflict handler plugins and conflict analysis
SCIP_SUCCESS
Definition: type_result.h:49
SCIPsetConshdlrGetVars
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:816
SCIP_SETPPCTYPE_COVERING
Definition: cons_setppc.h:80
SCIP_DECL_CONSENFORELAX
static SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
Definition: cons_symresack.c:1972
SCIPcaptureVar
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1218
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIPsetConshdlrPrint
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:770
SCIP_Var
Definition: struct_var.h:198
SCIPconshdlrGetNConss
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4594
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
SCIP_DECL_CONSCOPY
static SCIP_DECL_CONSCOPY(consCopySymresack)
Definition: cons_symresack.c:2361
SCIPinitConflictAnalysis
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:314
SCIPinferVarUbCons
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:5596
SCIPvarIsBinary
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
initLP
static SCIP_RETCODE initLP(SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkmonotonicity, SCIP_Bool *infeasible)
Definition: cons_symresack.c:594
SCIPcreateEmptyRowCons
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1368
FALSE
#define FALSE
Definition: def.h:73
CONSHDLR_PROPFREQ
#define CONSHDLR_PROPFREQ
Definition: cons_symresack.c:81
cons_orbisack.h
constraint handler for orbisack constraints
TRUE
#define TRUE
Definition: def.h:72
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
consdataCreate
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA **consdata, SCIP_VAR *const *inputvars, int inputnvars, int *inputperm, SCIP_Bool ismodelcons)
Definition: cons_symresack.c:452
SCIPincludeConshdlrSymresack
SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
Definition: cons_symresack.c:2551
SCIPconsIsInitial
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8258
SCIPaddConflictLb
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:343
checkSymresackSolution
static SCIP_RETCODE checkSymresackSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
Definition: cons_symresack.c:1241
CONSHDLR_MAXPREROUNDS
#define CONSHDLR_MAXPREROUNDS
Definition: cons_symresack.c:85
SCIPsetConshdlrDelete
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
SCIP_SETPPCTYPE_PACKING
Definition: cons_setppc.h:79
SCIPgetVarsSetppc
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9272
pub_var.h
public methods for problem variables
SCIPaddBoolParam
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
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_SEPARATED
Definition: type_result.h:40
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1604
SCIPsetConshdlrPresol
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:525
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_DECL_CONSPRESOL
static SCIP_DECL_CONSPRESOL(consPresolSymresack)
Definition: cons_symresack.c:2132
SCIPsetConshdlrGetNVars
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:839
cons_setppc.h
Constraint handler for the set partitioning / packing / covering constraints .
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
scip_var.h
public methods for SCIP variables
SCIP_DECL_CONSGETNVARS
static SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
Definition: cons_symresack.c:2532
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:874
separateSymresackCovers
static SCIP_RETCODE separateSymresackCovers(SCIP *scip, SCIP_CONS *cons, const SCIP_CONSDATA *consdata, SCIP_Real *vals, int *ngen, SCIP_Bool *infeasible)
Definition: cons_symresack.c:984
SCIP_DECL_CONSINITLP
static SCIP_DECL_CONSINITLP(consInitlpSymresack)
Definition: cons_symresack.c:1632
SCIPisTransformed
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:559
SCIPsetConshdlrFree
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
scip_numerics.h
public methods for numerical tolerances
SCIPdelCons
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2837
SCIP_DECL_CONSPRINT
static SCIP_DECL_CONSPRINT(consPrintSymresack)
Definition: cons_symresack.c:2433
SCIP_Sol
Definition: struct_sol.h:64
CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS
Definition: cons_symresack.c:88
SCIPgetVarCopy
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:697
cons_symresack.h
constraint handler for symresack constraints
SCIPduplicateBlockMemoryArray
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIPmarkDoNotMultaggrVar
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8648
pub_cons.h
public methods for managing constraints
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1581
addSymresackInequality
static SCIP_RETCODE addSymresackInequality(SCIP *scip, SCIP_CONS *cons, int nvars, SCIP_VAR **vars, int *coeffs, SCIP_Real rhs, SCIP_Bool *infeasible)
Definition: cons_symresack.c:928
orbisackUpgrade
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)
Definition: cons_symresack.c:1321
SCIPvarGetName
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIP_DECL_CONSSEPALP
static SCIP_DECL_CONSSEPALP(consSepalpSymresack)
Definition: cons_symresack.c:1702
CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ
Definition: cons_symresack.c:82
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIP_Cons
Definition: struct_cons.h:37
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIPcreateConsBasicSymresack
SCIP_RETCODE SCIPcreateConsBasicSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons)
Definition: cons_symresack.c:2677
SCIP_Conshdlr
Definition: struct_cons.h:117
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1508
SCIP_DECL_CONSENFOLP
static SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
Definition: cons_symresack.c:1851
SCIPsetConshdlrInitsol
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
SCIPgetTransformedVar
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1443
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIP_FEASIBLE
Definition: type_result.h:36
SCIP_DECL_CONSLOCK
static SCIP_DECL_CONSLOCK(consLockSymresack)
Definition: cons_symresack.c:2310
SCIP_DECL_CONSDELETE
static SCIP_DECL_CONSDELETE(consDeleteSymresack)
Definition: cons_symresack.c:1503
NULL
#define NULL
Definition: lpi_spx1.cpp:155
SCIPvarGetLbAtIndex
SCIP_EXPORT SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16308
CONSHDLR_SEPAFREQ
#define CONSHDLR_SEPAFREQ
Definition: cons_symresack.c:80
SCIP_OKAY
Definition: type_retcode.h:33
SCIP_SETPPCTYPE_PARTITIONING
Definition: cons_setppc.h:78
SCIPconsGetData
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8119
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:364
SCIPsetConshdlrResprop
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:632
SCIP_REDUCEDDOM
Definition: type_result.h:42
SCIP_DECL_CONSSEPASOL
static SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
Definition: cons_symresack.c:1776
SCIP_CONSDATA
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
packingUpgrade
static SCIP_RETCODE packingUpgrade(SCIP *scip, SCIP_CONSDATA **consdata, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool checkmonotonicity, SCIP_Bool *upgrade)
Definition: cons_symresack.c:202
scip_cons.h
public methods for constraint handler plugins and constraints
SCIPconsIsRemovable
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8358
DEFAULT_CHECKMONOTONICITY
#define DEFAULT_CHECKMONOTONICITY
Definition: cons_symresack.c:94
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIPaddConflictUb
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:410
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:503
SCIPsetConshdlrSepa
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
pub_misc.h
public data structures and miscellaneous methods
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
SCIPsortIntInt
SCIP_EXPORT void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIPsetConshdlrCopy
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
SCIPconshdlrGetData
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
SCIP_Row
Definition: struct_lp.h:192
SCIP_DECL_CONSHDLRCOPY
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
Definition: cons_symresack.c:1486
SCIP_DECL_CONSRESPROP
static SCIP_DECL_CONSRESPROP(consRespropSymresack)
Definition: cons_symresack.c:2195
scip_cut.h
public methods for cuts and aggregation rows
SCIP_DECL_CONSCHECK
static SCIP_DECL_CONSCHECK(consCheckSymresack)
Definition: cons_symresack.c:2048
SCIPaddConflictBinvar
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:547
SCIPconsIsSeparated
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8268
SCIPanalyzeConflictCons
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip_conflict.c:694
SCIPconsIsDynamic
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8348
SCIPvarGetLbLocal
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
scip_lp.h
public methods for the LP relaxation, rows and columns
CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA
Definition: cons_symresack.c:86
r
SCIP_Real * r
Definition: circlepacking.c:50
SCIPvarGetUbLocal
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1390
scip_branch.h
public methods for branching rule plugins and branching
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:221
scip_general.h
general public methods
SCIPinferVarLbCons
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:5482
CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING
Definition: cons_symresack.c:90
scip_sol.h
public methods for solutions
SCIPconsIsEnforced
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8278
SCIP_DECL_CONSGETVARS
static SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
Definition: cons_symresack.c:2503
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1641
DEFAULT_PPSYMRESACK
#define DEFAULT_PPSYMRESACK
Definition: cons_symresack.c:93
SCIPconshdlrGetConss
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4551
DEFAULT_FORCECONSCOPY
#define DEFAULT_FORCECONSCOPY
Definition: cons_symresack.c:95
pub_message.h
public methods for message output
SCIPcreateSymbreakCons
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)
Definition: cons_symresack.c:1426
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10590
SCIPgetNVarsSetppc
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9249
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8089
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1252
SCIP_Real
#define SCIP_Real
Definition: def.h:163
SCIPvarGetUbAtIndex
SCIP_EXPORT SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16427
CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY
Definition: cons_symresack.c:79
scip_message.h
public methods for message handling
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:45
SCIPconsIsStickingAtNode
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8368
CONSHDLR_DESC
#define CONSHDLR_DESC
Definition: cons_symresack.c:76
SCIPconshdlrGetName
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4179
SCIP_DECL_CONSENFOPS
static SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
Definition: cons_symresack.c:1929
CONSHDLR_SEPAPRIORITY
#define CONSHDLR_SEPAPRIORITY
Definition: cons_symresack.c:77
SCIPgetTypeSetppc
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9295
SCIPvarGetProbindex
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17360
SCIP_CONSHDLRDATA
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
SCIPcreateConsOrbisack
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)
Definition: cons_orbisack.c:2064
SCIPfreeBlockMemoryArrayNull
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP
Definition: cons_symresack.c:87
propVariables
static SCIP_RETCODE propVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *ngen)
Definition: cons_symresack.c:793
SCIPaddVarsToRow
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1667
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIPsetConshdlrProp
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
ISFIXED0
#define ISFIXED0(x)
Definition: cons_symresack.c:98
scip_prob.h
public methods for global and local (sub)problems
SCIP_DECL_CONSINITSOL
static SCIP_DECL_CONSINITSOL(consInitsolSymresack)
Definition: cons_symresack.c:1666
SCIP_DECL_CONSTRANS
static SCIP_DECL_CONSTRANS(consTransSymresack)
Definition: cons_symresack.c:1537
ISFIXED1
#define ISFIXED1(x)
Definition: cons_symresack.c:99
SCIPisEfficacious
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:106
SCIPconsIsPropagated
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8308
SCIP_CUTOFF
Definition: type_result.h:39
SCIPcreateConsSymresack
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)
Definition: cons_symresack.c:2612
SCIPsetConshdlrInitlp
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:609
scip.h
SCIP callable library.
SCIPconsIsModifiable
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8338
memory.h
memory allocation routines