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