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