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_orbitope.c
26   	 * @ingroup DEFPLUGINS_CONS
27   	 * @brief  constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group
28   	 * @author Timo Berthold
29   	 * @author Marc Pfetsch
30   	 * @author Christopher Hojny
31   	 *
32   	 * The type of constraints of this constraint handler is described in cons_orbitope.h.
33   	 *
34   	 * The details of the method implemented here are described in the following papers.
35   	 *
36   	 * Packing and Partitioning Orbitopes@n
37   	 * Volker Kaibel and Marc E. Pfetsch,@n
38   	 * Math. Program. 114, No. 1, 1-36 (2008)
39   	 *
40   	 * Among other things, this paper describes so-called shifted column inequalities of the following
41   	 * form \f$x(S) \leq x(B)\f$, where \f$S\f$ is a so-called shifted column and \f$B\f$ is a so-called
42   	 * bar. These inequalities can be used to handle symmetry and they are separated in this constraint
43   	 * handler. We use the linear time separation algorithm of the paper.@par
44   	 *
45   	 * Orbitopal Fixing@n
46   	 * Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,@n
47   	 * Discrete Optimization 8, No. 4, 595-610 (2011)
48   	 * (A preliminary version appears in Proc. IPCO 2007.)
49   	 *
50   	 * In this paper a linear time propagation algorithm is described, a variant of which is implemented
51   	 * here. The implemented variant does not run in linear time, but is very fast in practice.
52   	 *
53   	 * <table>
54   	 *   <caption>translation table</caption>
55   	 *   <tr><td>here</td><td>paper</td></tr>
56   	 *   <tr><td></td><td></td></tr>
57   	 *   <tr><td>nspcons      </td><td>p       </td></tr>
58   	 *   <tr><td>nblocks      </td><td>q       </td></tr>
59   	 *   <tr><td>vars         </td><td>x       </td></tr>
60   	 *   <tr><td>vals         </td><td>A^\\star</td></tr>
61   	 *   <tr><td>weights      </td><td>\\omega </td></tr>
62   	 *   <tr><td>cases        </td><td>\\tau   </td></tr>
63   	 *   <tr><td>fixtriangle  </td><td>--      </td></tr>
64   	 *   <tr><td>resolveprop  </td><td>--      </td></tr>
65   	 *   <tr><td>firstnonzeros</td><td>\\mu    </td></tr>
66   	 *   <tr><td>lastones     </td><td>\\alpha </td></tr>
67   	 *   <tr><td>frontiersteps</td><td>\\Gamma </td></tr>
68   	 * </table>
69   	 *
70   	 * Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem@n
71   	 * Pascale Bendotti, Pierre Fouilhoux, and Cecile Rottner,@n
72   	 * Optimization Online: http://www.optimization-online.org/DB_HTML/2017/10/6301.html
73   	 *
74   	 * Two linear time propagation algorithms for full orbitopes are described in this paper, a static
75   	 * version and a dynamic one. While the static version uses a fixed variable order, the dynamic
76   	 * version determines the variable order during the solving process via branching descisions.
77   	 * We implemented the static version as well as a modified version of the dynamic one. The reason
78   	 * for the latter is to simplify the compatibility with full orbitope cutting planes.
79   	 *
80   	 * Note, however, that the dynamic version may lead to conflicts if orbitopes are copied to subSCIPs.
81   	 * Since the dynamic version is based on branching decisions, which may be different in main SCIP
82   	 * and subSCIPs, orbitopes using the dynamic algorithm are not allowed to be copied. However, as a
83   	 * user might use orbitopes to enforce a certain variable ordering in a solution, we distinguish
84   	 * whether an orbitope is a model constraint or not. If it is a model constraint, we assume that
85   	 * a variable order has already been fixed and disable the dynamic algorithm. In this case, orbitope
86   	 * constraints are copied to subSCIPs. If it is not a model constraint, the orbitope was added to
87   	 * handle symmetries but not to enforce a solution to have a certain structure. In this case, the
88   	 * dynamic algorithm can be used and we do not copy orbitope constraints to subSCIPs.
89   	 *
90   	 * Polytopes associated with symmetry handling@n
91   	 * Christopher Hojny and Marc E. Pfetsch,@n
92   	 * Math. Program. (2018)
93   	 *
94   	 * In this paper, a linear time separation algorithm for orbisacks (full orbitopes with two columnes)
95   	 * is described. We use this algorithm for every pair of adjacent columns within the orbitope as well
96   	 * as a version that is adapted to the reordering based on the dynamic full orbitope propagation
97   	 * algorithm to ensure validity of binary points via cutting planes.
98   	 */
99   	
100  	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
101  	
102  	#include "blockmemshell/memory.h"
103  	#include "scip/cons_orbisack.h"
104  	#include "scip/cons_orbitope.h"
105  	#include "scip/cons_setppc.h"
106  	#include "scip/pub_cons.h"
107  	#include "scip/pub_message.h"
108  	#include "scip/pub_var.h"
109  	#include "scip/scip.h"
110  	#include "scip/scip_branch.h"
111  	#include "scip/scip_conflict.h"
112  	#include "scip/scip_cons.h"
113  	#include "scip/scip_copy.h"
114  	#include "scip/scip_cut.h"
115  	#include "scip/scip_general.h"
116  	#include "scip/scip_lp.h"
117  	#include "scip/scip_mem.h"
118  	#include "scip/scip_message.h"
119  	#include "scip/scip_numerics.h"
120  	#include "scip/scip_param.h"
121  	#include "scip/scip_prob.h"
122  	#include "scip/scip_probing.h"
123  	#include "scip/scip_sol.h"
124  	#include "scip/scip_var.h"
125  	#include "scip/symmetry.h"
126  	#include <symmetry/type_symmetry.h>
127  	
128  	/* constraint handler properties */
129  	#define CONSHDLR_NAME          "orbitope"
130  	#define CONSHDLR_DESC          "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes"
131  	#define CONSHDLR_SEPAPRIORITY    +40100 /**< priority of the constraint handler for separation */
132  	#define CONSHDLR_ENFOPRIORITY  -1005200 /**< priority of the constraint handler for constraint enforcing */
133  	#define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
134  	#define CONSHDLR_SEPAFREQ            -1 /**< frequency for separating cuts; zero means to separate only in the root node */
135  	#define CONSHDLR_PROPFREQ             1 /**< frequency for propagating domains; zero means only preprocessing propagation */
136  	#define CONSHDLR_EAGERFREQ           -1 /**< frequency for using all instead of only the useful constraints in separation,
137  	                                         *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
138  	#define CONSHDLR_MAXPREROUNDS        -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
139  	#define CONSHDLR_DELAYSEPA        FALSE /**< should separation method be delayed, if other separators found cuts? */
140  	#define CONSHDLR_DELAYPROP        FALSE /**< should propagation method be delayed, if other propagators found reductions? */
141  	#define CONSHDLR_NEEDSCONS         TRUE /**< should the constraint handler be skipped, if no constraints are available? */
142  	
143  	#define CONSHDLR_PROP_TIMING             SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
144  	#define CONSHDLR_PRESOLTIMING            SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
145  	
146  	#define DEFAULT_PPORBITOPE         TRUE /**< whether we check if full orbitopes can be strengthened to packing/partitioning orbitopes */
147  	#define DEFAULT_SEPAFULLORBITOPE  FALSE /**< whether we separate inequalities for full orbitopes */
148  	#define DEFAULT_FORCECONSCOPY     FALSE /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
149  	
150  	/*
151  	 * Data structures
152  	 */
153  	
154  	/** constraint handler data */
155  	struct SCIP_ConshdlrData
156  	{
157  	   SCIP_Bool             checkpporbitope;    /**< whether we allow upgrading to packing/partitioning orbitopes */
158  	   SCIP_Bool             sepafullorbitope;   /**< whether we separate inequalities for full orbitopes orbitopes */
159  	   SCIP_Bool             forceconscopy;      /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
160  	};
161  	
162  	/** constraint data for orbitope constraints */
163  	struct SCIP_ConsData
164  	{
165  	   SCIP_VAR***           vars;               /**< matrix of variables on which the symmetry acts            */
166  	   SCIP_VAR**            tmpvars;            /**< temporary storage for variables                           */
167  	   SCIP_HASHMAP*         rowindexmap;        /**< map of variables to row index in orbitope matrix */
168  	   SCIP_Real**           vals;               /**< LP-solution for those variables                           */
169  	   SCIP_Real*            tmpvals;            /**< temporary storage for values                              */
170  	   SCIP_Real**           weights;            /**< SC weight table                                           */
171  	   int**                 cases;              /**< indicator of the SC cases                                 */
172  	   int                   nspcons;            /**< number of set partitioning/packing constraints  <=> p     */
173  	   int                   nblocks;            /**< number of symmetric variable blocks             <=> q     */
174  	   SCIP_ORBITOPETYPE     orbitopetype;       /**< type of orbitope constraint                               */
175  	   SCIP_Bool             resolveprop;        /**< should propagation be resolved?                           */
176  	   SCIP_Bool             istrianglefixed;    /**< has the upper right triangle already globally been fixed to zero?  */
177  	   int*                  roworder;           /**< order of orbitope rows if dynamic propagation for full orbitopes
178  	                                              *   is used. */
179  	   SCIP_Bool*            rowused;            /**< whether a row has been considered in roworder */
180  	   int                   nrowsused;          /**< number of rows that have already been considered in roworder */
181  	   SCIP_Bool             ismodelcons;        /**< whether the orbitope is a model constraint */
182  	   SCIP_Bool             mayinteract;        /**< whether symmetries corresponding to orbitope might interact
183  	                                              *   with symmetries handled by other routines */
184  	   SCIP_Bool             usedynamicprop;     /**< whether we use a dynamic version of the propagation routine */
185  	};
186  	
187  	
188  	/*
189  	 * Local methods
190  	 */
191  	
192  	/** frees an orbitope constraint data */
193  	static
194  	SCIP_RETCODE consdataFree(
195  	   SCIP*                 scip,               /**< SCIP data structure */
196  	   SCIP_CONSDATA**       consdata            /**< pointer to orbitope constraint data */
197  	   )
198  	{
199  	   int i;
200  	   int j;
201  	   int p;
202  	   int q;
203  	
204  	   assert( consdata != NULL );
205  	   assert( *consdata != NULL );
206  	
207  	   if ( (*consdata)->usedynamicprop && (*consdata)->rowindexmap != NULL )
208  	   {
209  	      SCIPhashmapFree(&((*consdata)->rowindexmap));
210  	   }
211  	
212  	   p = (*consdata)->nspcons;
213  	   q = (*consdata)->nblocks;
214  	   for (i = 0; i < p; ++i)
215  	   {
216  	      /* release variables in vars array */
217  	      for (j = 0; j < q; ++j)
218  	      {
219  	         assert( (*consdata)->vars[i] != NULL );
220  	         SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i][j]) );
221  	      }
222  	
223  	      SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases[i]), q);    /*lint !e866*/
224  	      SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars[i]), q);     /*lint !e866*/
225  	      SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights[i]), q);  /*lint !e866*/
226  	      SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals[i]), q);     /*lint !e866*/
227  	   }
228  	
229  	   if ( (*consdata)->usedynamicprop )
230  	   {
231  	      SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->rowused), p);
232  	   }
233  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->roworder), p);
234  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases), p);
235  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), p);
236  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights), p);
237  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals), p);
238  	
239  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvals), p + q);
240  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvars), p + q);
241  	
242  	   SCIPfreeBlockMemory(scip, consdata);
243  	
244  	   return SCIP_OKAY;
245  	}
246  	
247  	
248  	/** creates orbitope constraint data */
249  	static
250  	SCIP_RETCODE consdataCreate(
251  	   SCIP*                 scip,               /**< SCIP data structure                                     */
252  	   SCIP_CONSDATA**       consdata,           /**< pointer to store constraint data                        */
253  	   SCIP_VAR***           vars,               /**< variables array, must have size nspcons x nblocks       */
254  	   int                   nspcons,            /**< number of set partitioning (packing) constraints  <=> p */
255  	   int                   nblocks,            /**< number of symmetric variable blocks               <=> q */
256  	   SCIP_ORBITOPETYPE     orbitopetype,       /**< type of orbitope constraint                             */
257  	   SCIP_Bool             resolveprop,        /**< should propagation be resolved?                         */
258  	   SCIP_Bool             usedynamicprop,     /**< whether we use a dynamic version of the propagation routine */
259  	   SCIP_Bool             ismodelcons,        /**< whether the orbitope is a model constraint */
260  	   SCIP_Bool             mayinteract         /**< whether symmetries corresponding to orbitope might interact
261  	                                              *   with symmetries handled by other routines */
262  	   )
263  	{
264  	   int i;
265  	   int j;
266  	
267  	   assert(consdata != NULL);
268  	#ifndef NDEBUG
269  	   if ( usedynamicprop )
270  	   {
271  	      assert( ! mayinteract );
272  	   }
273  	#endif
274  	
275  	   SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
276  	
277  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals, nspcons) );
278  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights, nspcons) );
279  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vars, nspcons) );
280  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases, nspcons) );
281  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->roworder, nspcons) );
282  	
283  	   /* if orbitope might interact with other symmetries, we cannot adapt the row order of orbitopes dynamically */
284  	   if ( usedynamicprop )
285  	   {
286  	      SCIP_CALL( SCIPhashmapCreate(&(*consdata)->rowindexmap, SCIPblkmem(scip), nspcons) );
287  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->rowused, nspcons) );
288  	   }
289  	
290  	   for (i = 0; i < nspcons; ++i)
291  	   {
292  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals[i], nblocks) );                 /*lint !e866*/
293  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights[i], nblocks) );              /*lint !e866*/
294  	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars[i], vars[i], nblocks) );    /*lint !e866*/
295  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases[i], nblocks) );                /*lint !e866*/
296  	      (*consdata)->roworder[i] = i;
297  	
298  	      if ( usedynamicprop )
299  	      {
300  	         (*consdata)->rowused[i] = FALSE;
301  	      }
302  	   }
303  	   (*consdata)->nrowsused = 0;
304  	
305  	   (*consdata)->tmpvals = NULL;
306  	   (*consdata)->tmpvars = NULL;
307  	   (*consdata)->nspcons = nspcons;
308  	   (*consdata)->nblocks = nblocks;
309  	   (*consdata)->orbitopetype = orbitopetype;
310  	   (*consdata)->resolveprop = resolveprop;
311  	   (*consdata)->istrianglefixed = FALSE;
312  	   (*consdata)->ismodelcons = ismodelcons;
313  	   (*consdata)->mayinteract = mayinteract;
314  	   (*consdata)->usedynamicprop = usedynamicprop;
315  	
316  	   /* get transformed variables, if we are in the transformed problem */
317  	   if ( SCIPisTransformed(scip) )
318  	   {
319  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvals, nspcons + nblocks) );
320  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvars, nspcons + nblocks) );
321  	
322  	      for (i = 0; i < nspcons; ++i)
323  	      {
324  	         /* make sure that no variable gets multiaggregated (cannot be handled by cons_orbitope, since one cannot easily
325  	          * eliminate single variables from an orbitope constraint).
326  	          */
327  	         for (j = 0; j < nblocks; ++j)
328  	         {
329  	            SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i][j], &(*consdata)->vars[i][j]) );
330  	            SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i][j]) );
331  	            if ( usedynamicprop )
332  	            {
333  	               SCIP_CALL( SCIPhashmapInsert((*consdata)->rowindexmap, (*consdata)->vars[i][j], (void*) (size_t) i) );
334  	            }
335  	         }
336  	      }
337  	   }
338  	
339  	   /* capture vars contained in vars array */
340  	   for (i = 0; i < nspcons; ++i)
341  	   {
342  	      for (j = 0; j < nblocks; ++j)
343  	      {
344  	         assert( (*consdata)->vars[i][j] != NULL );
345  	         SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i][j]) );
346  	      }
347  	   }
348  	
349  	   return SCIP_OKAY;
350  	}
351  	
352  	
353  	/** strengthen full orbitopes to packing/partitioning orbitopes if possible */
354  	static
355  	SCIP_RETCODE strengthenOrbitopeConstraint(
356  	   SCIP*                 scip,               /**< SCIP data structure */
357  	   SCIP_VAR***           vars,               /**< variable matrix of orbitope constraint */
358  	   int*                  nrows,              /**< pointer to number of rows of variable matrix */
359  	   int                   ncols,              /**< number of columns of variable matrix */
360  	   SCIP_ORBITOPETYPE*    type,               /**< pointer to store type of orbitope constraint after strengthening */
361  	   SCIP_Bool             mayinteract         /**< whether symmetries corresponding to orbitope might interact
362  	                                              *   with symmetries handled by other routines */
363  	   )
364  	{
365  	   SCIP_Bool* pprows = NULL;
366  	   int npprows;
367  	   int nrowsorig;
368  	
369  	   assert( scip != NULL );
370  	   assert( vars != NULL );
371  	   assert( vars != NULL );
372  	   assert( *nrows > 0 );
373  	   assert( ncols > 0 );
374  	   assert( type != NULL );
375  	
376  	   nrowsorig = *nrows;
377  	   SCIP_CALL( SCIPisPackingPartitioningOrbitope(scip, vars, *nrows, ncols, &pprows, &npprows, type) );
378  	
379  	   /* If only some rows are contained in set packing/partitioning constraints, it may still be worth it
380  	    * to exploit the packing/partitioning structure on these rows, because packing/partitioning orbitopes
381  	    * or more restrictive than full orbitopes. If at least three rows have this property, we discard
382  	    * all rows not contained in set packing/partitioning constraints and add the smaller sub packing orbitope.
383  	    * This is only possible if the orbitope's symmetries do not interact with other symmetry handling
384  	    * methods (otherwise, dropping rows might change the variable order).
385  	    */
386  	   if ( npprows >= 3 && ! mayinteract )
387  	   {
388  	      int r = *nrows - 1;
389  	      int i;
390  	
391  	      assert( pprows != NULL );
392  	
393  	      while ( r >= 0 )
394  	      {
395  	         if ( ! pprows[r] )
396  	         {
397  	            for (i = r; i < *nrows - 1; ++i)
398  	            {
399  	               SCIP_VAR** row;
400  	               row = vars[i];
401  	               vars[i] = vars[i+1];
402  	               vars[i+1] = row;
403  	            }
404  	            *nrows -= 1;
405  	         }
406  	         --r;
407  	      }
408  	      *type = SCIP_ORBITOPETYPE_PACKING;
409  	   }
410  	
411  	   /* pprows might not have been initialized if there are no setppc conss */
412  	   if ( pprows != NULL )
413  	   {
414  	      SCIPfreeBlockMemoryArray(scip, &pprows, nrowsorig);
415  	   }
416  	
417  	   return SCIP_OKAY;
418  	}
419  	
420  	#ifdef PRINT_MATRIX
421  	/** debug method, prints variable matrix */
422  	static
423  	void printMatrix(
424  	   SCIP*                 scip,               /**< SCIP data structure */
425  	   SCIP_CONSDATA*        consdata            /**< the constraint data */
426  	   )
427  	{
428  	   int i;
429  	   int j;
430  	
431  	   assert( consdata != NULL );
432  	   assert( consdata->nspcons > 0 );
433  	   assert( consdata->nblocks > 0 );
434  	   assert( consdata->vars != NULL );
435  	
436  	   for (j = 0; j < consdata->nblocks; ++j)
437  	      SCIPinfoMessage(scip, NULL, "-");
438  	
439  	   SCIPinfoMessage(scip, NULL, "\n");
440  	   for (i = 0; i < consdata->nspcons; ++i)
441  	   {
442  	      for (j = 0; j < consdata->nblocks; ++j)
443  	      {
444  	         if ( SCIPvarGetUbLocal(consdata->vars[i][j]) - SCIPvarGetLbLocal(consdata->vars[i][j]) < 0.5 )
445  	            SCIPinfoMessage(scip, NULL, "%1.0f", REALABS(SCIPvarGetUbLocal(consdata->vars[i][j])));
446  	         else
447  	            SCIPinfoMessage(scip, NULL, " ");
448  	      }
449  	      SCIPinfoMessage(scip, NULL, "|\n");
450  	   }
451  	   for (j = 0; j < consdata->nblocks; ++j)
452  	      SCIPinfoMessage(scip, NULL, "-");
453  	   SCIPinfoMessage(scip, NULL, "\n");
454  	}
455  	#endif
456  	
457  	
458  	#ifdef SHOW_SCI
459  	/** Print SCI in nice form for debugging */
460  	static
461  	SCIP_RETCODE printSCI(
462  	   SCIP*                 scip,               /**< SCIP pointer */
463  	   int                   p,                  /**< number of rows */
464  	   int                   q,                  /**< number of columns */
465  	   int**                 cases,              /**< SCI dynamic programming table */
466  	   int                   i,                  /**< row position of bar */
467  	   int                   j                   /**< column position of bar */
468  	   )
469  	{
470  	   int k;
471  	   int l;
472  	   int** M;
473  	   int p1;
474  	   int p2;
475  	
476  	   SCIP_CALL( SCIPallocBufferArray(scip, &M, p) );
477  	   for (k = 0; k < p; ++k)
478  	   {
479  	      SCIP_CALL( SCIPallocBufferArray(scip, &M[k], q) ); /*lint !e866*/
480  	      for (l = 0; l < q; ++l)
481  	         M[k][l] = 0;
482  	   }
483  	
484  	   /* first add bar */
485  	   for (l = j; l < q; ++l)
486  	   {
487  	      assert( M[i][l] == 0 );
488  	      M[i][l] = 1;
489  	   }
490  	
491  	   /* then add shifted column */
492  	   p1 = i-1;
493  	   p2 = j-1;
494  	   do
495  	   {
496  	      assert( cases[p1][p2] != -1 );
497  	      assert( p1 >= 0 && p1 < i );
498  	      assert( p2 >= 0 && p2 < j );
499  	
500  	      /* if case 1 */
501  	      if ( cases[p1][p2] == 1 )
502  	         --p2;   /* decrease column */
503  	      else
504  	      {
505  	         /* case 2 or 3: */
506  	         assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
507  	         assert( M[p1][p2] == 0 );
508  	         M[p1][p2] = -1;
509  	         if ( cases[p1][p2] == 3 )
510  	            break;
511  	      }
512  	      --p1;  /* decrease row */
513  	   }
514  	   while ( p1 >= 0 );   /* should always be true, i.e. the break should end the loop */
515  	   assert( cases[p1][p2] == 3 );
516  	
517  	   /* now output matrix M */
518  	   for (l = 0; l < q; ++l)
519  	      SCIPinfoMessage(scip, NULL, "-");
520  	   SCIPinfoMessage(scip, NULL, "\n");
521  	
522  	   for (k = 0; k < p; ++k)
523  	   {
524  	      for (l = 0; l < q; ++l)
525  	      {
526  	         if ( l > k )
527  	            SCIPinfoMessage(scip, NULL, "*");
528  	         else
529  	         {
530  	            switch (M[k][l])
531  	            {
532  	            case 1:
533  	               SCIPinfoMessage(scip, NULL, "+");
534  	               break;
535  	            case -1:
536  	               SCIPinfoMessage(scip, NULL, "-");
537  	               break;
538  	            case 0:
539  	               SCIPinfoMessage(scip, NULL, "#");
540  	               break;
541  	            default:
542  	               SCIPerrorMessage("unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]);
543  	               SCIPABORT();
544  	            }
545  	         }
546  	      }
547  	      SCIPinfoMessage(scip, NULL, "\n");
548  	   }
549  	
550  	   for (l = 0; l < q; ++l)
551  	      SCIPinfoMessage(scip, NULL, "-");
552  	   SCIPinfoMessage(scip, NULL, "\n");
553  	
554  	   for (k = 0; k < p; ++k)
555  	      SCIPfreeBufferArray(scip, &M[k]);
556  	   SCIPfreeBufferArray(scip, &M);
557  	
558  	   return SCIP_OKAY;
559  	}
560  	#endif
561  	
562  	
563  	/** copies the variables values from the solution to the constraint data structure */
564  	static
565  	void copyValues(
566  	   SCIP*                 scip,               /**< the SCIP data structure */
567  	   SCIP_CONSDATA*        consdata,           /**< the constraint data     */
568  	   SCIP_SOL*             sol                 /**< a primal solution or NULL for the current LP optimum */
569  	   )
570  	{
571  	   int i;
572  	   int j;
573  	
574  	   assert( scip != NULL );
575  	   assert( consdata != NULL );
576  	   assert( consdata->nspcons > 0 );
577  	   assert( consdata->nblocks > 0 );
578  	   assert( consdata->vars != NULL );
579  	   assert( consdata->vals != NULL );
580  	
581  	   for (i = 0; i < consdata->nspcons; ++i)
582  	   {
583  	      for (j = 0; j < consdata->nblocks; ++j)
584  	         consdata->vals[i][j] = SCIPgetSolVal(scip, sol, consdata->vars[i][j]);
585  	   }
586  	}
587  	
588  	
589  	/** compute the dynamic programming table for SC
590  	 *
591  	 *  Build up dynamic programming table in order to find SCs with minimum weight.
592  	 *
593  	 *  The values of the minimal SCIs are stored in @a weights.
594  	 *  The array @a cases[i][j] stores which of the cases were applied to get @a weights[i][j].
595  	 *  Here, 3 means that we have reached the upper limit.
596  	 *
597  	 *  We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a
598  	 *  bit more efficient.
599  	 */
600  	static
601  	void computeSCTable(
602  	   SCIP*                 scip,               /**< SCIP pointer                                              */
603  	   int                   nspcons,            /**< number of set partitioning (packing) constraints  <=> p   */
604  	   int                   nblocks,            /**< number of symmetric variable blocks               <=> q   */
605  	   SCIP_Real**           weights,            /**< SC weight table                                           */
606  	   int**                 cases,              /**< indicator of the SC cases                                 */
607  	   SCIP_Real**           vals                /**< current solution                                          */
608  	   )
609  	{
610  	   SCIP_Real minvalue;
611  	   int diagsize;
612  	   int i;
613  	   int j;
614  	
615  	   assert( weights != NULL );
616  	   assert( cases != NULL );
617  	   assert( vals != NULL );
618  	
619  	#ifndef NDEBUG
620  	   /* for debugging */
621  	   for (i = 0; i < nspcons; ++i)
622  	   {
623  	      for (j = 0; j < nblocks; ++j)
624  	      {
625  	         if ( i >= j )
626  	         {
627  	            weights[i][j] = -1.0;
628  	            cases[i][j] = -1;
629  	         }
630  	      }
631  	   }
632  	#endif
633  	
634  	   /* initialize diagonal */
635  	   minvalue = vals[0][0];
636  	   weights[0][0] = minvalue;
637  	   cases[0][0] = 3;
638  	
639  	   /* get last row of triangle */
640  	   diagsize = nblocks;
641  	   if ( nspcons < nblocks )
642  	      diagsize = nspcons;
643  	
644  	   for (j = 1; j < diagsize; ++j)
645  	   {
646  	      /* use LT to move entry as far to the left as possible */
647  	      if ( SCIPisLT(scip, vals[j][j], minvalue) )
648  	      {
649  	         minvalue = vals[j][j];
650  	         cases[j][j] = 3;
651  	      }
652  	      else
653  	         cases[j][j] = 1;
654  	      weights[j][j] = minvalue;
655  	   }
656  	
657  	   /* initialize first column */
658  	   for (i = 1; i < nspcons; ++i)
659  	   {
660  	      weights[i][0] = weights[i-1][0] + vals[i][0];
661  	      cases[i][0] = 2;  /* second case */
662  	   }
663  	
664  	   /* build the table */
665  	   for (i = 2; i < nspcons; ++i)
666  	   {
667  	      for (j = 1; j < nblocks && j < i; ++j)
668  	      {
669  	         SCIP_Real weightleft;
670  	         SCIP_Real weightright;
671  	
672  	         assert( cases[i-1][j] != -1 );
673  	         assert( cases[i-1][j-1] != -1 );
674  	
675  	         weightleft = weights[i-1][j-1];
676  	         weightright = vals[i][j] + weights[i-1][j];
677  	
678  	         /* For first column: cannot take left possibility */
679  	         if ( SCIPisLT(scip, weightleft, weightright) )
680  	         {
681  	            weights[i][j] = weightleft;
682  	            cases[i][j] = 1;
683  	         }
684  	         else
685  	         {
686  	            weights[i][j] = weightright;
687  	            cases[i][j] = 2;
688  	         }
689  	      }
690  	   }
691  	}
692  	
693  	
694  	/** fix upper right triangle if necessary */
695  	static
696  	SCIP_RETCODE fixTriangle(
697  	   SCIP*                 scip,               /**< SCIP data structure */
698  	   SCIP_CONS*            cons,               /**< constraint to be processed */
699  	   SCIP_Bool*            infeasible,         /**< pointer to store TRUE, if the node can be cut off */
700  	   int*                  nfixedvars          /**< pointer to add up the number of found domain reductions */
701  	   )
702  	{
703  	   SCIP_CONSDATA* consdata;
704  	   SCIP_VAR*** vars;
705  	   SCIP_Bool fixedglobal;
706  	   SCIP_Bool fixed;
707  	   int diagsize;
708  	   int nspcons;
709  	   int nblocks;
710  	   int i;
711  	   int j;
712  	
713  	   assert( scip != NULL );
714  	   assert( cons != NULL );
715  	   assert( infeasible != NULL );
716  	   assert( nfixedvars != NULL );
717  	
718  	   consdata = SCIPconsGetData(cons);
719  	   assert( consdata != NULL );
720  	   assert( consdata->nspcons > 0 );
721  	   assert( consdata->nblocks > 0 );
722  	   assert( consdata->vars != NULL );
723  	
724  	   *infeasible = FALSE;
725  	   *nfixedvars = 0;
726  	
727  	   if ( consdata->istrianglefixed )
728  	      return SCIP_OKAY;
729  	
730  	   nspcons = consdata->nspcons;
731  	   nblocks = consdata->nblocks;
732  	   vars = consdata->vars;
733  	   fixedglobal = TRUE;
734  	
735  	   /* get last row of triangle */
736  	   diagsize = nblocks;
737  	   if ( nspcons < nblocks )
738  	      diagsize = nspcons;
739  	
740  	   /* fix variables to 0 */
741  	   for (i = 0; i < diagsize; ++i)
742  	   {
743  	      for (j = i+1; j < nblocks; ++j)
744  	      {
745  	         /* fix variable, if not in the root the fixation is local */
746  	         SCIP_CALL( SCIPfixVar(scip, vars[i][j], 0.0, infeasible, &fixed) );
747  	
748  	         if ( *infeasible )
749  	         {
750  	            SCIPdebugMsg(scip, "The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n");
751  	            return SCIP_OKAY;
752  	         }
753  	
754  	         if ( fixed )
755  	            ++(*nfixedvars);
756  	
757  	         if ( SCIPvarGetUbGlobal(vars[i][j]) > 0.5 )
758  	            fixedglobal = FALSE;
759  	      }
760  	   }
761  	   if ( *nfixedvars > 0 )
762  	   {
763  	      SCIPdebugMsg(scip, "<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n", SCIPconsGetName(cons), fixedglobal ? "globally" : "locally", *nfixedvars);
764  	   }
765  	   else
766  	   {
767  	      SCIPdebugMsg(scip, "<%s>: Upper right triangle already fixed to 0.\n", SCIPconsGetName(cons));
768  	   }
769  	
770  	   if ( fixedglobal )
771  	      consdata->istrianglefixed = TRUE;
772  	
773  	   return SCIP_OKAY;
774  	}
775  	
776  	
777  	/** separates shifted column inequalities according to the solution stored in consdata->vals */
778  	static
779  	SCIP_RETCODE separateSCIs(
780  	   SCIP*                 scip,               /**< the SCIP data structure */
781  	   SCIP_CONSHDLR*        conshdlr,           /**< constraint handler */
782  	   SCIP_CONS*            cons,               /**< constraint */
783  	   SCIP_CONSDATA*        consdata,           /**< the constraint data */
784  	   SCIP_Bool*            infeasible,         /**< whether we detected infeasibility */
785  	   int*                  nfixedvars,         /**< pointer to store the number of variables fixed */
786  	   int*                  ncuts               /**< pointer to store number of separated SCIs */
787  	   )
788  	{
789  	   SCIP_Real** vals;
790  	   SCIP_Real** weights;
791  	   SCIP_Real* tmpvals;
792  	   SCIP_VAR*** vars;
793  	   SCIP_VAR** tmpvars;
794  	   int** cases;
795  	   int nspcons;
796  	   int nblocks;
797  	   int i;
798  	   int j;
799  	   int l;
800  	
801  	   assert( scip != NULL );
802  	   assert( conshdlr != NULL );
803  	   assert( cons != NULL );
804  	   assert( infeasible != NULL);
805  	   assert( nfixedvars != NULL );
806  	   assert( ncuts != NULL );
807  	
808  	   assert( consdata != NULL );
809  	   assert( consdata->nspcons > 0 );
810  	   assert( consdata->nblocks > 0 );
811  	   assert( consdata->vars != NULL );
812  	   assert( consdata->vals != NULL );
813  	   assert( consdata->tmpvars != NULL );
814  	   assert( consdata->tmpvals != NULL );
815  	   assert( consdata->weights != NULL );
816  	   assert( consdata->cases != NULL );
817  	
818  	   *infeasible = FALSE;
819  	   *nfixedvars = 0;
820  	   *ncuts = 0;
821  	
822  	   nspcons = consdata->nspcons;
823  	   nblocks = consdata->nblocks;
824  	   vars = consdata->vars;
825  	   vals = consdata->vals;
826  	   tmpvars = consdata->tmpvars;
827  	   tmpvals = consdata->tmpvals;
828  	   weights = consdata->weights;
829  	   cases = consdata->cases;
830  	
831  	   /* check for upper right triangle */
832  	   if ( ! consdata->istrianglefixed )
833  	   {
834  	      SCIP_CALL( fixTriangle(scip, cons, infeasible, nfixedvars) );
835  	      if ( *infeasible )
836  	         return SCIP_OKAY;
837  	      if ( *nfixedvars > 0 )
838  	         return SCIP_OKAY;
839  	   }
840  	
841  	   /* compute table if necessary (i.e., not computed before) */
842  	   computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
843  	
844  	   /* loop through rows */
845  	   for (i = 1; i < nspcons && ! (*infeasible); ++i)
846  	   {
847  	      SCIP_Real bar;       /* value of bar: */
848  	      int lastcolumn;      /* last column considered as part of the bar */
849  	
850  	      bar = 0.0;
851  	      lastcolumn = nblocks - 1;
852  	      if ( lastcolumn > i )
853  	         lastcolumn = i;
854  	
855  	      /* traverse row from right to left: */
856  	      /* j >= 1, since for j = 0, i.e., the bar is a complete row, there does not exist an SCI */
857  	      for (j = lastcolumn; j > 0; --j)
858  	      {
859  	         bar += vals[i][j];
860  	
861  	         /* check whether weights[i-1][j-1] < bar  (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
862  	         if ( SCIPisEfficacious(scip, bar - weights[i-1][j-1]) )
863  	         {
864  	#ifndef NDEBUG
865  	            SCIP_Real weight = 0.0;
866  	#endif
867  	            SCIP_ROW* row;
868  	#ifdef SCIP_DEBUG
869  	            char name[SCIP_MAXSTRLEN];
870  	#endif
871  	            int nvars;
872  	            int p1;
873  	            int p2;
874  	
875  	            nvars = 0;
876  	            p1 = i-1;
877  	            p2 = j-1;
878  	
879  	            /* first add bar */
880  	            for (l = j; l <= lastcolumn; ++l)
881  	            {
882  	               tmpvars[nvars] = vars[i][l];
883  	               tmpvals[nvars] = 1.0;
884  	               nvars++;
885  	            }
886  	
887  	            /* then add shifted column */
888  	            do
889  	            {
890  	               assert( cases[p1][p2] != -1 );
891  	               assert( p1 >= 0 && p1 < i );
892  	               assert( p2 >= 0 && p2 < j );
893  	
894  	               /* if case 1 */
895  	               if (cases[p1][p2] == 1)
896  	                  p2--;   /* decrease column */
897  	               else
898  	               {
899  	                  /* case 2 or 3: */
900  	                  assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
901  	                  tmpvars[nvars] = vars[p1][p2];
902  	                  tmpvals[nvars] = -1.0;
903  	                  nvars++;
904  	#ifndef NDEBUG
905  	                  weight += vals[p1][p2];
906  	#endif
907  	                  if ( cases[p1][p2] == 3 )
908  	                     break;
909  	               }
910  	               p1--;  /* decrease row */
911  	            }
912  	            while ( p1 >= 0 );   /* should always be true, i.e. the break should end the loop */
913  	            assert( cases[p1][p2] == 3 );
914  	
915  	            /* generate cut */
916  	#ifdef SCIP_DEBUG
917  	            (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sci_%d_%d", i, j);
918  	            SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
919  	#else
920  	            SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
921  	#endif
922  	            SCIP_CALL( SCIPaddVarsToRow(scip, row, nvars, tmpvars, tmpvals) );
923  	            /*SCIP_CALL( SCIPprintRow(scip, row, NULL) ); */
924  	            SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
925  	            SCIP_CALL( SCIPreleaseRow(scip, &row) );
926  	            ++(*ncuts);
927  	
928  	#ifdef SHOW_SCI
929  	            SCIP_CALL( printSCI(scip, nspcons, nblocks, cases, i, j) );
930  	#endif
931  	
932  	            assert( SCIPisSumEQ(scip, weights[i-1][j-1], weight) );
933  	         }
934  	      }
935  	   }
936  	   return SCIP_OKAY;
937  	}
938  	
939  	
940  	/** propagation method for a single packing or partitioning orbitope constraint */
941  	static
942  	SCIP_RETCODE propagatePackingPartitioningCons(
943  	   SCIP*                 scip,               /**< SCIP data structure */
944  	   SCIP_CONS*            cons,               /**< constraint to be processed */
945  	   SCIP_Bool*            infeasible,         /**< pointer to store TRUE, if the node can be cut off */
946  	   int*                  nfixedvars          /**< pointer to add up the number of found domain reductions */
947  	   )
948  	{
949  	   SCIP_CONSDATA* consdata;
950  	   SCIP_VAR*** vars;
951  	   SCIP_ORBITOPETYPE orbitopetype;
952  	   int* firstnonzeros;
953  	   int* lastones;
954  	   int* frontiersteps;
955  	   int lastoneprevrow;
956  	   int nspcons;
957  	   int nblocks;
958  	   int nsteps;
959  	   int i;
960  	   int j;
961  	
962  	   assert( scip != NULL );
963  	   assert( cons != NULL );
964  	   assert( infeasible != NULL );
965  	   assert( nfixedvars != NULL );
966  	
967  	   *nfixedvars = 0;
968  	
969  	   if( !SCIPallowStrongDualReds(scip) )
970  	      return SCIP_OKAY;
971  	
972  	   consdata = SCIPconsGetData(cons);
973  	   assert( consdata != NULL );
974  	   assert( consdata->nspcons > 0 );
975  	   assert( consdata->nblocks > 0 );
976  	   assert( consdata->vars != NULL );
977  	
978  	   nspcons = consdata->nspcons;
979  	   nblocks = consdata->nblocks;
980  	   vars = consdata->vars;
981  	   orbitopetype = consdata->orbitopetype;
982  	
983  	   assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
984  	
985  	   /* fix upper right triangle if still necessary */
986  	   if ( ! consdata->istrianglefixed )
987  	   {
988  	      int nfixed = 0;
989  	      SCIP_CALL( fixTriangle(scip, cons, infeasible, &nfixed) );
990  	      *nfixedvars += nfixed;
991  	   }
992  	
993  	   /* prepare further propagation */
994  	   SCIP_CALL( SCIPallocBufferArray(scip, &firstnonzeros, nspcons) );
995  	   SCIP_CALL( SCIPallocBufferArray(scip, &lastones, nspcons) );
996  	   SCIP_CALL( SCIPallocBufferArray(scip, &frontiersteps, nblocks) );
997  	
998  	#ifdef PRINT_MATRIX
999  	   SCIPdebugMsg(scip, "Matrix:\n");
1000 	   printMatrix(scip, consdata);
1001 	#endif
1002 	
1003 	   /* propagate */
1004 	   lastoneprevrow = 0;
1005 	   lastones[0] = 0;
1006 	
1007 	   if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING )
1008 	   {
1009 	      /* packing case: if entry (0,0) is fixed to 0 */
1010 	      if ( SCIPvarGetUbLocal(vars[0][0]) < 0.5 )
1011 	      {
1012 	         lastoneprevrow = -1;
1013 	         lastones[0] = -1;
1014 	      }
1015 	   }
1016 	   nsteps = 0;
1017 	
1018 	   for (i = 1; i < nspcons; ++i)
1019 	   {
1020 	      int lastcolumn;
1021 	      int firstnonzeroinrow;
1022 	      int lastoneinrow;
1023 	      SCIP_Bool infrontier;
1024 	
1025 	      /* last column considered as part of the bar: */
1026 	      lastcolumn = nblocks - 1;
1027 	      if ( lastcolumn > i )
1028 	         lastcolumn = i;
1029 	
1030 	      /* find first position not fixed to 0 (partitioning) or fixed to 1 (packing) */
1031 	      firstnonzeroinrow = -1;
1032 	      for (j = 0; j <= lastcolumn; ++j)
1033 	      {
1034 	         if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1035 	         {
1036 	            /* partitioning case: if variable is not fixed to 0 */
1037 	            if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1038 	            {
1039 	               firstnonzeroinrow = j;
1040 	               break;
1041 	            }
1042 	         }
1043 	         else
1044 	         {
1045 	            /* packing case: if variable is fixed to 1 */
1046 	            if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
1047 	            {
1048 	               firstnonzeroinrow = j;
1049 	               break;
1050 	            }
1051 	         }
1052 	      }
1053 	      /* if all variables are fixed to 0 in the partitioning case - should not happen */
1054 	      if ( firstnonzeroinrow == -1 && orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1055 	      {
1056 	         SCIPdebugMsg(scip, " -> Infeasible node: all variables in row %d are fixed to 0.\n", i);
1057 	         *infeasible = TRUE;
1058 	         /* conflict should be analyzed by setppc constraint handler */
1059 	         goto TERMINATE;
1060 	      }
1061 	      firstnonzeros[i] = firstnonzeroinrow;
1062 	      assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || firstnonzeroinrow >= 0 );
1063 	      assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn );
1064 	
1065 	      /* compute rightmost possible position for a 1 */
1066 	      assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneprevrow );
1067 	      assert( lastoneprevrow <= lastcolumn );
1068 	
1069 	      /* if we are at right border or if entry in column lastoneprevrow+1 is fixed to 0 */
1070 	      infrontier = FALSE;
1071 	      assert( lastoneprevrow + 1 >= 0 );
1072 	      if ( lastoneprevrow == nblocks-1 || SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 ) /*lint !e679*/
1073 	         lastoneinrow = lastoneprevrow;
1074 	      else
1075 	      {
1076 	         lastoneinrow = lastoneprevrow + 1;
1077 	         frontiersteps[nsteps++] = i;
1078 	         infrontier = TRUE;
1079 	      }
1080 	
1081 	      /* store lastoneinrow */
1082 	      assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneinrow );
1083 	      assert( lastoneinrow <= lastcolumn );
1084 	      lastones[i] = lastoneinrow;
1085 	
1086 	      /* check whether we are infeasible */
1087 	      if ( firstnonzeroinrow > lastoneinrow )
1088 	      {
1089 	         int k;
1090 	
1091 	#ifdef SCIP_DEBUG
1092 	         if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1093 	         {
1094 	            SCIPdebugMsg(scip, " -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n",
1095 	               i, firstnonzeroinrow, lastoneinrow);
1096 	         }
1097 	         else
1098 	         {
1099 	            SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n",
1100 	               i, firstnonzeroinrow, lastoneinrow);
1101 	         }
1102 	#endif
1103 	         /* check if conflict analysis is applicable */
1104 	         if ( SCIPisConflictAnalysisApplicable(scip) )
1105 	         {
1106 	            /* conflict analysis only applicable in SOLVING stage */
1107 	            assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) );
1108 	
1109 	            /* perform conflict analysis */
1110 	            SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
1111 	
1112 	            if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1113 	            {
1114 	               /* add bounds (variables fixed to 0) that result in the first nonzero entry */
1115 	               for (j = 0; j <= lastcolumn; ++j)
1116 	               {
1117 	                  /* add varaibles in row up to the first variable fixed to 0 */
1118 	                  if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1119 	                     break;
1120 	
1121 	                  assert( SCIPvarGetUbLocal(vars[i][j]) < 0.5 );
1122 	                  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1123 	               }
1124 	            }
1125 	            else
1126 	            {
1127 	               /* add bounds that result in the last one - check top left entry for packing case */
1128 	               if ( lastones[0] == -1 )
1129 	               {
1130 	                  assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1131 	                  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1132 	               }
1133 	
1134 	               /* mark variable fixed to 1 */
1135 	               assert( SCIPvarGetLbLocal(vars[i][firstnonzeroinrow]) > 0.5 );
1136 	               SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][firstnonzeroinrow]) );
1137 	            }
1138 	
1139 	            /* add bounds that result in the last one - pass through rows */
1140 	            for (k = 1; k < i; ++k)
1141 	            {
1142 	               int l;
1143 	               l = lastones[k] + 1;
1144 	
1145 	               /* if the frontier has not moved and we are not beyond the matrix boundaries */
1146 	               if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1147 	               {
1148 	                  assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1149 	                  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1150 	               }
1151 	            }
1152 	            SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1153 	         }
1154 	
1155 	         *infeasible = TRUE;
1156 	         goto TERMINATE;
1157 	      }
1158 	
1159 	      /* fix entries beyond the last possible position for a 1 in the row to 0 (see Lemma 1 in the paper) */
1160 	      for (j = lastoneinrow+1; j <= lastcolumn; ++j)
1161 	      {
1162 	         /* if the entry is not yet fixed to 0 */
1163 	         if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1164 	         {
1165 	            SCIP_Bool tightened;
1166 	            int inferInfo;
1167 	
1168 	            SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 0.\n", i, j);
1169 	
1170 	            tightened = FALSE;
1171 	
1172 	            /* fix variable to 0 and store position of (i,lastoneinrow+1) for conflict resolution */
1173 	            inferInfo = i * nblocks + lastoneinrow + 1;
1174 	            /* correction according to Lemma 1 in the paper (second part): store (i,lastoneinrow+2) */
1175 	            if ( !infrontier )
1176 	               ++inferInfo;
1177 	            SCIP_CALL( SCIPinferBinvarCons(scip, vars[i][j], FALSE, cons, inferInfo, infeasible, &tightened) );
1178 	
1179 	            /* if entry is fixed to one -> infeasible node */
1180 	            if ( *infeasible )
1181 	            {
1182 	               SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow);
1183 	               /* check if conflict analysis is applicable */
1184 	               if( SCIPisConflictAnalysisApplicable(scip) )
1185 	               {
1186 	                  int k;
1187 	
1188 	                  /* conflict analysis only applicable in SOLVING stage */
1189 	                  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip));
1190 	
1191 	                  /* perform conflict analysis */
1192 	                  SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
1193 	
1194 	                  /* add current bound */
1195 	                  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1196 	
1197 	                  /* add bounds that result in the last one - check top left entry for packing case */
1198 	                  if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING && lastones[0] == -1 )
1199 	                  {
1200 	                     assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1201 	                     SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1202 	                  }
1203 	
1204 	                  /* add bounds that result in the last one - pass through rows */
1205 	                  for (k = 1; k < i; ++k)
1206 	                  {
1207 	                     int l;
1208 	                     l = lastones[k] + 1;
1209 	
1210 	                     /* if the frontier has not moved and we are not beyond the matrix boundaries */
1211 	                     if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1212 	                     {
1213 	                        assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1214 	                        SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1215 	                     }
1216 	                  }
1217 	                  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1218 	               }
1219 	
1220 	               goto TERMINATE;
1221 	            }
1222 	            if ( tightened )
1223 	               ++(*nfixedvars);
1224 	         }
1225 	      }
1226 	
1227 	      lastoneprevrow = lastoneinrow;
1228 	   }
1229 	
1230 	   /* check whether fixing any entry to 0 results in a contradiction -> loop through rows in frontiersteps (a.k.a. gamma) */
1231 	   for (j = 0; j < nsteps; ++j)
1232 	   {
1233 	      int s;
1234 	      int lastoneinrow;
1235 	
1236 	      s = frontiersteps[j];
1237 	      lastoneinrow = lastones[s];
1238 	      /* note for packing case: if we are in a frontier step then lastoneinrow >= 0 */
1239 	      assert( 0 <= lastoneinrow && lastoneinrow < nblocks );
1240 	
1241 	      /* if entry is not fixed */
1242 	      if ( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 && SCIPvarGetUbLocal(vars[s][lastoneinrow]) > 0.5 )
1243 	      {
1244 	         int betaprev;
1245 	         betaprev = lastoneinrow - 1;
1246 	
1247 	         /* loop through rows below s */
1248 	         for (i = s+1; i < nspcons; ++i)
1249 	         {
1250 	            int beta;
1251 	
1252 	            assert( betaprev + 1 >= 0 );
1253 	            if ( betaprev == nblocks-1 || SCIPvarGetUbLocal(vars[i][betaprev+1]) < 0.5 ) /*lint !e679*/
1254 	               beta = betaprev;
1255 	            else
1256 	               beta = betaprev + 1;
1257 	            assert( -1 <= beta && beta < nblocks );
1258 	
1259 	            if ( firstnonzeros[i] > beta )
1260 	            {
1261 	               SCIP_Bool tightened;
1262 	               int inferInfo;
1263 	
1264 	               /* can fix (s,lastoneinrow) (a.k.a (s,alpha)) to 1
1265 	                * (do not need to fix other entries to 0, since they will be
1266 	                * automatically fixed by SCIPtightenVarLb.)
1267 	                */
1268 	               assert( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 );
1269 	               SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow);
1270 	
1271 	               tightened = FALSE;
1272 	
1273 	               /* store position (i,firstnonzeros[i]) */
1274 	               inferInfo = nblocks * nspcons + i * nblocks + firstnonzeros[i];
1275 	               SCIP_CALL( SCIPinferBinvarCons(scip, vars[s][lastoneinrow], TRUE, cons, inferInfo, infeasible, &tightened) );
1276 	
1277 	               assert( !(*infeasible) );
1278 	               if ( tightened )
1279 	                  ++(*nfixedvars);
1280 	               break;
1281 	            }
1282 	            betaprev = beta;
1283 	         }
1284 	      }
1285 	   }
1286 	
1287 	 TERMINATE:
1288 	   SCIPfreeBufferArray(scip, &frontiersteps);
1289 	   SCIPfreeBufferArray(scip, &lastones);
1290 	   SCIPfreeBufferArray(scip, &firstnonzeros);
1291 	
1292 	   return SCIP_OKAY;
1293 	}
1294 	
1295 	
1296 	/* Compute dynamic order of rows based on the branching decisions, i.e., the row of the first branching variable
1297 	 * determines the first row in the new ordering, the row of the second branching variable determines the second
1298 	 * row in the new ordering if it differs from the row of the first branching variable, and so on.
1299 	 *
1300 	 * The roworder array stores this reordering, where acutally only the first maxrowlabel entries encode the
1301 	 * reordering.
1302 	 */
1303 	static
1304 	SCIP_RETCODE computeDynamicRowOrder(
1305 	   SCIP*                 scip,               /**< SCIP pointer */
1306 	   SCIP_HASHMAP*         rowindexmap,        /**< map of variables to indices in orbitope vars matrix */
1307 	   SCIP_Bool*            rowused,            /**< bitset marking whether a row has been considered in the new order */
1308 	   int*                  roworder,           /**< reordering of the rows w.r.t. branching decisions */
1309 	   int                   nrows,              /**< number of rows in orbitope */
1310 	   int                   ncols,              /**< number of columns in orbitope */
1311 	   int*                  maxrowlabel         /**< maximum row label in ordering */
1312 	   )
1313 	{
1314 	   int i;
1315 	   SCIP_NODE* node;
1316 	   int* branchdecisions;
1317 	   int nbranchdecision;
1318 	
1319 	   assert( scip != NULL );
1320 	   assert( rowindexmap != NULL );
1321 	   assert( roworder != NULL );
1322 	   assert( nrows > 0 );
1323 	   assert( maxrowlabel != NULL );
1324 	
1325 	   SCIP_CALL( SCIPallocBufferArray(scip, &branchdecisions, nrows * ncols) );
1326 	   nbranchdecision = 0;
1327 	
1328 	   /* get current node */
1329 	   node = SCIPgetCurrentNode(scip);
1330 	
1331 	   /* follow path to the root (in the root no domains were changed due to branching) */
1332 	   while ( SCIPnodeGetDepth(node) != 0 )
1333 	   {
1334 	      SCIP_BOUNDCHG* boundchg;
1335 	      SCIP_DOMCHG* domchg;
1336 	      SCIP_VAR* branchvar;
1337 	      int nboundchgs;
1338 	
1339 	      /* get domain changes of current node */
1340 	      domchg = SCIPnodeGetDomchg(node);
1341 	      assert( domchg != NULL );
1342 	
1343 	      /* loop through all bound changes */
1344 	      nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
1345 	      for (i = 0; i < nboundchgs; ++i)
1346 	      {
1347 	         /* get bound change info */
1348 	         boundchg = SCIPdomchgGetBoundchg(domchg, i);
1349 	         assert( boundchg != NULL );
1350 	
1351 	         /* branching decisions have to be in the beginning of the bound change array */
1352 	         if ( SCIPboundchgGetBoundchgtype(boundchg) != SCIP_BOUNDCHGTYPE_BRANCHING )
1353 	            break;
1354 	
1355 	         /* get corresponding branching variable */
1356 	         branchvar = SCIPboundchgGetVar(boundchg);
1357 	
1358 	         /* we only consider binary variables */
1359 	         if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY )
1360 	         {
1361 	            int rowidx;
1362 	
1363 	            /* make sure that branching variable is present in the orbitope */
1364 	            if ( ! SCIPhashmapExists(rowindexmap, (void*) branchvar) )
1365 	               continue;
1366 	
1367 	            rowidx = (int) (size_t) SCIPhashmapGetImage(rowindexmap, (void*) branchvar);
1368 	            branchdecisions[nbranchdecision++] = rowidx;
1369 	         }
1370 	      }
1371 	
1372 	      node = SCIPnodeGetParent(node);
1373 	   }
1374 	
1375 	   /* Insert branching decisions of current path into global row order.
1376 	    * Iterate in reverse order over branching decisions to get the path
1377 	    * from the root to the current node.
1378 	    */
1379 	   for (i = nbranchdecision - 1; i >= 0; --i)
1380 	   {
1381 	      if ( ! rowused[branchdecisions[i]] )
1382 	      {
1383 	         roworder[*maxrowlabel] = branchdecisions[i];
1384 	         rowused[branchdecisions[i]] = TRUE;
1385 	         *maxrowlabel += 1;
1386 	      }
1387 	   }
1388 	
1389 	   SCIPfreeBufferArray(scip, &branchdecisions);
1390 	
1391 	   return SCIP_OKAY;
1392 	}
1393 	
1394 	
1395 	/* Compute lexicographically minimal face of the hypercube w.r.t. some coordinate fixing */
1396 	static
1397 	SCIP_RETCODE findLexMinFace(
1398 	   SCIP_VAR***           vars,               /**< variable matrix */
1399 	   int**                 lexminfixes,        /**< fixings characterzing lex-min face */
1400 	   int*                  minfixedrowlexmin,  /**< index of minimum fixed row for each column or
1401 	                                              *   NULL (if in prop) */
1402 	   SCIP_Bool*            infeasible,         /**< pointer to store whether infeasibility has been
1403 	                                              *   detected or NULL (if in resprop) */
1404 	   int                   m,                  /**< number of rows in vars */
1405 	   int                   n,                  /**< number of columns in vars */
1406 	   int                   nrowsused,          /**< number of rows considered in propagation */
1407 	   SCIP_Bool             resprop             /**< whether we are in resprop (TRUE) or prop (FALSE) */
1408 	   )
1409 	{
1410 	   int i;
1411 	   int j;
1412 	   *infeasible = FALSE;
1413 	
1414 	   assert( vars != NULL );
1415 	   assert( lexminfixes != NULL );
1416 	   assert( !resprop || minfixedrowlexmin != NULL );
1417 	   assert( m > 0 );
1418 	   assert( n > 0 );
1419 	   assert( nrowsused > 0 );
1420 	   assert( nrowsused <= m );
1421 	   assert( infeasible != NULL );
1422 	
1423 	   /* iterate over columns in reverse order and find the lexicographically minimal face
1424 	    * of the hypercube containing lexminfixes
1425 	    */
1426 	   for (j = n - 2; j >= 0; --j)
1427 	   {
1428 	      int maxdiscriminating = m;
1429 	      int minfixed = -1;
1430 	
1431 	      /* fix free entries in column j to the corresponding value in column j + 1 and collect some information */
1432 	      for (i = 0; i < nrowsused; ++i)
1433 	      {
1434 	         /* is row i j-discriminating? */
1435 	         if ( minfixed == -1 && lexminfixes[i][j] != 0 && lexminfixes[i][j + 1] != 1 )
1436 	         {
1437 	            assert( lexminfixes[i][j + 1] == 0 );
1438 	
1439 	            maxdiscriminating = i;
1440 	         }
1441 	
1442 	         /* is row i j-fixed? */
1443 	         if ( minfixed == -1 && lexminfixes[i][j] != lexminfixes[i][j + 1] && lexminfixes[i][j] != 2 )
1444 	         {
1445 	            assert( lexminfixes[i][j + 1] != 2 );
1446 	
1447 	            minfixed = i;
1448 	
1449 	            /* detect infeasibility */
1450 	            if ( maxdiscriminating > minfixed )
1451 	            {
1452 	               *infeasible = TRUE;
1453 	
1454 	               return SCIP_OKAY;
1455 	            }
1456 	         }
1457 	      }
1458 	
1459 	      /* ensure that column j is lexicographically not smaller than column j + 1 */
1460 	      for (i = 0; i < nrowsused; ++i)
1461 	      {
1462 	         if ( lexminfixes[i][j] == 2 )
1463 	         {
1464 	            if ( i < maxdiscriminating || minfixed == -1 )
1465 	               lexminfixes[i][j] = lexminfixes[i][j + 1];
1466 	            else if ( i == maxdiscriminating )
1467 	               lexminfixes[i][j] = 1;
1468 	            else
1469 	               lexminfixes[i][j] = 0;
1470 	         }
1471 	      }
1472 	
1473 	      if ( resprop )
1474 	      {
1475 	         assert( minfixedrowlexmin != NULL );
1476 	
1477 	         /* store minimum fixed row */
1478 	         if ( minfixed == -1 )
1479 	            minfixedrowlexmin[j] = nrowsused - 1;
1480 	         else
1481 	            minfixedrowlexmin[j] = minfixed;
1482 	
1483 	         /* columns 1, ..., n-2 are contained in two columns (take the minimum) and
1484 	          * the minimum fixed row of column n-1 is determined by column n-2 */
1485 	         if ( minfixedrowlexmin[j + 1] < minfixedrowlexmin[j] )
1486 	            minfixedrowlexmin[j + 1] = minfixedrowlexmin[j];
1487 	      }
1488 	   }
1489 	
1490 	   return SCIP_OKAY;
1491 	}
1492 	
1493 	
1494 	/* Compute lexicographically maximal face of the hypercube w.r.t. some coordinate fixing */
1495 	static
1496 	SCIP_RETCODE findLexMaxFace(
1497 	   SCIP_VAR***           vars,               /**< variable matrix */
1498 	   int**                 lexmaxfixes,        /**< fixings characterzing lex-max face */
1499 	   int*                  minfixedrowlexmax,  /**< index of minimum fixed row for each column or
1500 	                                              *   NULL (if in prop) */
1501 	   SCIP_Bool*            infeasible,         /**< pointer to store whether infeasibility has been
1502 	                                              *   detected or NULL (if in resprop) */
1503 	   int                   m,                  /**< number of rows in vars */
1504 	   int                   n,                  /**< number of columns in vars */
1505 	   int                   nrowsused,          /**< number of rows considered in propagation */
1506 	   SCIP_Bool             resprop             /**< whether we are in resprop (TRUE) or prop (FALSE) */
1507 	   )
1508 	{
1509 	   int i;
1510 	   int j;
1511 	   *infeasible = FALSE;
1512 	
1513 	   assert( vars != NULL );
1514 	   assert( lexmaxfixes != NULL );
1515 	   assert( !resprop || minfixedrowlexmax != NULL );
1516 	   assert( m > 0 );
1517 	   assert( n > 0 );
1518 	   assert( nrowsused > 0 );
1519 	   assert( nrowsused <= m );
1520 	   assert( infeasible != NULL );
1521 	
1522 	   for (j = 1; j < n; ++j)
1523 	   {
1524 	      int maxdiscriminating = m;
1525 	      int minfixed = -1;
1526 	
1527 	      /* fix free entries in column j to the corresponding value in column j - 1 and collect some information */
1528 	      for (i = 0; i < nrowsused; ++i)
1529 	      {
1530 	         /* is row i j-discriminating? */
1531 	         if ( minfixed == -1 && lexmaxfixes[i][j - 1] != 0 && lexmaxfixes[i][j] != 1 )
1532 	         {
1533 	            assert( lexmaxfixes[i][j - 1] == 1 );
1534 	
1535 	            maxdiscriminating = i;
1536 	         }
1537 	
1538 	         /* is row i j-fixed? */
1539 	         if ( minfixed == -1 && lexmaxfixes[i][j - 1] != lexmaxfixes[i][j] && lexmaxfixes[i][j] != 2 )
1540 	         {
1541 	            assert( lexmaxfixes[i][j - 1] != 2 );
1542 	
1543 	            minfixed = i;
1544 	
1545 	            /* detect infeasibility */
1546 	            if ( maxdiscriminating > minfixed )
1547 	            {
1548 	               *infeasible = TRUE;
1549 	
1550 	               return SCIP_OKAY;
1551 	            }
1552 	         }
1553 	      }
1554 	
1555 	      /* ensure that column j is lexicographically not greater than column j - 1 */
1556 	      for (i = 0; i < nrowsused; ++i)
1557 	      {
1558 	         if ( lexmaxfixes[i][j] == 2 )
1559 	         {
1560 	            if ( i < maxdiscriminating || minfixed == -1 )
1561 	               lexmaxfixes[i][j] = lexmaxfixes[i][j - 1];
1562 	            else if ( i == maxdiscriminating )
1563 	               lexmaxfixes[i][j] = 0;
1564 	            else
1565 	               lexmaxfixes[i][j] = 1;
1566 	         }
1567 	      }
1568 	
1569 	      if ( resprop )
1570 	      {
1571 	         assert( minfixedrowlexmax != NULL );
1572 	
1573 	         /* store minimum fixed row */
1574 	         if ( minfixed == -1 )
1575 	            minfixedrowlexmax[j] = nrowsused - 1;
1576 	         else
1577 	            minfixedrowlexmax[j] = minfixed;
1578 	
1579 	         /* columns 1, ..., n-2 are contained in two columns (take the minimum) and
1580 	          * the minimum fixed row of column 0 is determined by column 1 */
1581 	         if ( minfixedrowlexmax[j - 1] < minfixedrowlexmax[j] )
1582 	            minfixedrowlexmax[j - 1] = minfixedrowlexmax[j];
1583 	      }
1584 	   }
1585 	
1586 	   return SCIP_OKAY;
1587 	}
1588 	
1589 	
1590 	/** propagation method for a single packing or partitioning orbitope constraint */
1591 	static
1592 	SCIP_RETCODE propagateFullOrbitopeCons(
1593 	   SCIP*                 scip,               /**< SCIP data structure */
1594 	   SCIP_CONS*            cons,               /**< constraint to be processed */
1595 	   SCIP_Bool*            infeasible,         /**< pointer to store TRUE, if the node can be cut off */
1596 	   int*                  nfixedvars,         /**< pointer to add up the number of found domain reductions */
1597 	   SCIP_Bool             dynamic             /**< whether we use a dynamic propagation routine */
1598 	   )
1599 	{
1600 	   SCIP_CONSDATA* consdata;
1601 	   SCIP_VAR*** vars;
1602 	   int** lexminfixes;
1603 	   int** lexmaxfixes;
1604 	   int* roworder;
1605 	   int nrowsused;
1606 	   int i;
1607 	   int j;
1608 	   int m;
1609 	   int n;
1610 	
1611 	   assert( scip != NULL );
1612 	   assert( cons != NULL );
1613 	   assert( infeasible != NULL );
1614 	   assert( nfixedvars != NULL );
1615 	
1616 	   *nfixedvars = 0;
1617 	   *infeasible = FALSE;
1618 	
1619 	   /* @todo Can the following be removed? */
1620 	   if ( ! SCIPallowStrongDualReds(scip) )
1621 	      return SCIP_OKAY;
1622 	
1623 	   /* do nothing if we use dynamic propagation and if we are in a probing node */
1624 	   if ( dynamic && SCIPinProbing(scip) )
1625 	      return SCIP_OKAY;
1626 	
1627 	   consdata = SCIPconsGetData(cons);
1628 	   assert( consdata != NULL );
1629 	   assert( consdata->nspcons > 0 );
1630 	   assert( consdata->nblocks > 0 );
1631 	   assert( consdata->vars != NULL );
1632 	   assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL );
1633 	
1634 	   m = consdata->nspcons;
1635 	   n = consdata->nblocks;
1636 	   vars = consdata->vars;
1637 	
1638 	   /* determine order of orbitope rows dynamically by branching decisions */
1639 	   if ( dynamic )
1640 	   {
1641 	      SCIP_CALL( computeDynamicRowOrder(scip, consdata->rowindexmap, consdata->rowused,
1642 	            consdata->roworder, m, n, &(consdata->nrowsused)) );
1643 	
1644 	      /* if no branching variable is contained in the full orbitope */
1645 	      if ( consdata->nrowsused == 0 )
1646 	         return SCIP_OKAY;
1647 	
1648 	      nrowsused = consdata->nrowsused;
1649 	   }
1650 	   else
1651 	      nrowsused = m;
1652 	   roworder = consdata->roworder;
1653 	
1654 	   /* Initialize lexicographically minimal matrix by fixed entries at the current node.
1655 	    * Free entries in the last column are set to 0.
1656 	    */
1657 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) );
1658 	   for (i = 0; i < nrowsused; ++i)
1659 	   {
1660 	      SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/
1661 	   }
1662 	
1663 	   for (i = 0; i < nrowsused; ++i)
1664 	   {
1665 	      int origrow;
1666 	
1667 	      origrow = roworder[i];
1668 	
1669 	      for (j = 0; j < n; ++j)
1670 	      {
1671 	         if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 )
1672 	            lexminfixes[i][j] = 1;
1673 	         else if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 || j == n - 1 )
1674 	            lexminfixes[i][j] = 0;
1675 	         else
1676 	            lexminfixes[i][j] = 2;
1677 	      }
1678 	   }
1679 	
1680 	   /* find lexicographically minimal face of hypercube containing lexmin fixes */
1681 	   SCIP_CALL( findLexMinFace(vars, lexminfixes, NULL, infeasible, m, n, nrowsused, FALSE) );
1682 	
1683 	   if ( *infeasible == TRUE )
1684 	      goto FREELEXMIN;
1685 	
1686 	   /* Initialize lexicographically maximal matrix by fixed entries at the current node.
1687 	    * Free entries in the first column are set to 1.
1688 	    */
1689 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) );
1690 	   for (i = 0; i < nrowsused; ++i)
1691 	   {
1692 	      SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/
1693 	   }
1694 	
1695 	   for (i = 0; i < nrowsused; ++i)
1696 	   {
1697 	      int origrow;
1698 	
1699 	      origrow = roworder[i];
1700 	
1701 	      for (j = 0; j < n; ++j)
1702 	      {
1703 	         if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 )
1704 	            lexmaxfixes[i][j] = 0;
1705 	         else if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 || j == 0 )
1706 	            lexmaxfixes[i][j] = 1;
1707 	         else
1708 	            lexmaxfixes[i][j] = 2;
1709 	      }
1710 	   }
1711 	
1712 	   /* find lexicographically maximal face of hypercube containing lexmax fixes */
1713 	   SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, NULL, infeasible, m, n, nrowsused, FALSE) );
1714 	
1715 	   if ( *infeasible )
1716 	      goto FREELEXMAX;
1717 	
1718 	   /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this
1719 	    * row to the corresponding value in lexminfixes (or lexmaxfixes).
1720 	    */
1721 	   for (j = 0; j < n; ++j)
1722 	   {
1723 	      for (i = 0; i < nrowsused; ++i)
1724 	      {
1725 	         int origrow;
1726 	
1727 	         origrow = roworder[i];
1728 	
1729 	         if ( lexminfixes[i][j] != lexmaxfixes[i][j] )
1730 	            break;
1731 	
1732 	         if ( SCIPvarGetLbLocal(vars[origrow][j]) < 0.5 && SCIPvarGetUbLocal(vars[origrow][j]) > 0.5 )
1733 	         {
1734 	            SCIP_Bool success;
1735 	
1736 	            SCIP_CALL( SCIPinferBinvarCons(scip, vars[origrow][j], (SCIP_Bool) lexminfixes[i][j],
1737 	                  cons, 0, infeasible, &success) );
1738 	
1739 	            if ( success )
1740 	               *nfixedvars += 1;
1741 	         }
1742 	      }
1743 	   }
1744 	
1745 	 FREELEXMAX:
1746 	   for (i = 0; i < nrowsused; ++i)
1747 	      SCIPfreeBufferArray(scip, &lexmaxfixes[i]);
1748 	   SCIPfreeBufferArray(scip, &lexmaxfixes);
1749 	
1750 	 FREELEXMIN:
1751 	   for (i = 0; i < nrowsused; ++i)
1752 	      SCIPfreeBufferArray(scip, &lexminfixes[i]);
1753 	   SCIPfreeBufferArray(scip, &lexminfixes);
1754 	
1755 	   return SCIP_OKAY;
1756 	}
1757 	
1758 	
1759 	/** propagation method for a single orbitope constraint */
1760 	static
1761 	SCIP_RETCODE propagateCons(
1762 	   SCIP*                 scip,               /**< SCIP data structure */
1763 	   SCIP_CONS*            cons,               /**< constraint to be processed */
1764 	   SCIP_Bool*            infeasible,         /**< pointer to store TRUE, if the node can be cut off */
1765 	   int*                  nfixedvars          /**< pointer to add up the number of found domain reductions */
1766 	   )
1767 	{
1768 	   SCIP_CONSDATA* consdata;
1769 	   SCIP_ORBITOPETYPE orbitopetype;
1770 	
1771 	   assert( scip != NULL );
1772 	   assert( cons != NULL );
1773 	   assert( infeasible != NULL );
1774 	   assert( nfixedvars != NULL );
1775 	
1776 	   consdata = SCIPconsGetData(cons);
1777 	   assert( consdata != NULL );
1778 	
1779 	   orbitopetype = consdata->orbitopetype;
1780 	
1781 	   if ( orbitopetype == SCIP_ORBITOPETYPE_FULL )
1782 	   {
1783 	      SCIP_CALL( propagateFullOrbitopeCons(scip, cons, infeasible, nfixedvars,
1784 	            consdata->usedynamicprop && !consdata->ismodelcons) );
1785 	   }
1786 	   else
1787 	   {
1788 	      assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
1789 	      SCIP_CALL( propagatePackingPartitioningCons(scip, cons, infeasible, nfixedvars) );
1790 	   }
1791 	
1792 	   return SCIP_OKAY;
1793 	}
1794 	
1795 	
1796 	/** Propagation conflict resolving method of propagator
1797 	 *
1798 	 *  In this function we use that all variable reductions that can be found by the propagation algorithm
1799 	 *  are only due to the fixed variables that are in or above the minimum fixed row of each pair of adjacent
1800 	 *  columns of the lexmin and lexmax matrices.
1801 	 *
1802 	 *  Since the storage of an integer is not enough to store the complete information about the fixing,
1803 	 *  we have to use the linear time algorithm for finding the lexmin and lexmax
1804 	 *  matrices and determine from this the minimum fixed rows.
1805 	 */
1806 	static
1807 	SCIP_RETCODE resolvePropagationFullOrbitope(
1808 	   SCIP*                 scip,               /**< SCIP data structure */
1809 	   SCIP_CONSHDLR*        conshdlr,           /**< constraint handler of the corresponding constraint */
1810 	   SCIP_CONS*            cons,               /**< constraint that inferred the bound change */
1811 	   int                   inferinfo,          /**< inference information */
1812 	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
1813 	   SCIP_RESULT*          result              /**< pointer to store the result of the propagation conflict resolving call */
1814 	   )
1815 	{  /*lint --e{715}*/
1816 	   SCIP_CONSDATA* consdata;
1817 	   SCIP_VAR*** vars;
1818 	   int** lexminfixes;
1819 	   int** lexmaxfixes;
1820 	   int* roworder;
1821 	   int* minfixedrowlexmin;
1822 	   int* minfixedrowlexmax;
1823 	   int i;
1824 	   int j;
1825 	   int m;
1826 	   int n;
1827 	   int nrowsused;
1828 	   SCIP_Bool dynamic;
1829 	   SCIP_Bool terminate;
1830 	
1831 	   *result = SCIP_DIDNOTFIND;
1832 	
1833 	   assert( scip != NULL );
1834 	   assert( conshdlr != NULL );
1835 	   assert( cons != NULL );
1836 	   assert( result != NULL );
1837 	
1838 	   consdata = SCIPconsGetData(cons);
1839 	   assert( consdata != NULL );
1840 	   assert( consdata->nspcons > 0 );
1841 	   assert( consdata->nblocks > 0 );
1842 	   assert( consdata->vars != NULL );
1843 	   assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL );
1844 	
1845 	   dynamic = consdata->usedynamicprop && !consdata->ismodelcons;
1846 	   m = consdata->nspcons;
1847 	   n = consdata->nblocks;
1848 	   vars = consdata->vars;
1849 	
1850 	   if ( dynamic )
1851 	   {
1852 	      assert( consdata->roworder != NULL );
1853 	      assert( consdata->nrowsused > 0 );
1854 	
1855 	      nrowsused = consdata->nrowsused;
1856 	   }
1857 	   else
1858 	      nrowsused = m;
1859 	   roworder = consdata->roworder;
1860 	
1861 	   assert( inferinfo <= consdata->nspcons );
1862 	
1863 	   /* Initialize lexicographically minimal matrix by fixed entries at the current node.
1864 	    * Free entries in the last column are set to 0.
1865 	    */
1866 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) );
1867 	   for (i = 0; i < nrowsused; ++i)
1868 	   {
1869 	      SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/
1870 	   }
1871 	
1872 	   /* store minimum fixed row for each column */
1873 	   SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmin, n) );
1874 	   minfixedrowlexmin[n - 1] = -1;
1875 	
1876 	   for (i = 0; i < nrowsused; ++i)
1877 	   {
1878 	      int origrow;
1879 	
1880 	      origrow = roworder[i];
1881 	
1882 	      for (j = 0; j < n; ++j)
1883 	      {
1884 	         if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 )
1885 	            lexminfixes[i][j] = 1;
1886 	         else if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 || j == n - 1 )
1887 	            lexminfixes[i][j] = 0;
1888 	         else
1889 	            lexminfixes[i][j] = 2;
1890 	      }
1891 	   }
1892 	
1893 	   /* find lexicographically minimal face of hypercube containing lexmin fixes */
1894 	   SCIP_CALL( findLexMinFace(vars, lexminfixes, minfixedrowlexmin, &terminate, m, n, nrowsused, TRUE) );
1895 	
1896 	   if ( terminate )
1897 	      goto FREELEXMIN;
1898 	
1899 	   /* Initialize lexicographically maximal matrix by fixed entries at the current node.
1900 	    * Free entries in the first column are set to 1.
1901 	    */
1902 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) );
1903 	   for (i = 0; i < nrowsused; ++i)
1904 	   {
1905 	      SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/
1906 	   }
1907 	
1908 	   /* store minimum fixed row for each column */
1909 	   SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmax, n) );
1910 	   minfixedrowlexmax[0] = -1;
1911 	
1912 	   for (i = 0; i < nrowsused; ++i)
1913 	   {
1914 	      int origrow;
1915 	
1916 	      origrow = roworder[i];
1917 	
1918 	      for (j = 0; j < n; ++j)
1919 	      {
1920 	         if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 )
1921 	            lexmaxfixes[i][j] = 0;
1922 	         else if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 || j == 0 )
1923 	            lexmaxfixes[i][j] = 1;
1924 	         else
1925 	            lexmaxfixes[i][j] = 2;
1926 	      }
1927 	   }
1928 	
1929 	   /* find lexicographically maximal face of hypercube containing lexmax fixes */
1930 	   SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, minfixedrowlexmax, &terminate, m, n, nrowsused, TRUE) );
1931 	
1932 	   if ( terminate )
1933 	      goto FREELEXMAX;
1934 	
1935 	   /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this
1936 	    * row to the corresponding value in lexminfixes (or lexmaxfixes).
1937 	    */
1938 	   for (j = 0; j < n; ++j)
1939 	   {
1940 	      int ub = MAX(minfixedrowlexmin[j], minfixedrowlexmax[j]);
1941 	
1942 	      for (i = 0; i <= ub; ++i)
1943 	      {
1944 	         int origrow;
1945 	
1946 	         origrow = roworder[i];
1947 	
1948 	         if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 ||
1949 	            SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 )
1950 	         {
1951 	            SCIP_CALL( SCIPaddConflictBinvar(scip, vars[origrow][j]) );
1952 	            *result = SCIP_SUCCESS;
1953 	         }
1954 	      }
1955 	   }
1956 	
1957 	 FREELEXMAX:
1958 	   SCIPfreeBufferArray(scip, &minfixedrowlexmax);
1959 	   for (i = 0; i < nrowsused; ++i)
1960 	      SCIPfreeBufferArray(scip, &lexmaxfixes[i]);
1961 	   SCIPfreeBufferArray(scip, &lexmaxfixes);
1962 	
1963 	 FREELEXMIN:
1964 	   SCIPfreeBufferArray(scip, &minfixedrowlexmin);
1965 	   for (i = 0; i < nrowsused; ++i)
1966 	      SCIPfreeBufferArray(scip, &lexminfixes[i]);
1967 	   SCIPfreeBufferArray(scip, &lexminfixes);
1968 	
1969 	   return SCIP_OKAY;
1970 	}
1971 	
1972 	
1973 	/** Propagation conflict resolving method of propagator
1974 	 *
1975 	 *  In this function we use that the propagation method above implicitly propagates SCIs, i.e., every
1976 	 *  fixing can also be gotten via an SCI-fixing.
1977 	 *
1978 	 *  Since the storage of an integer is not enough to store the complete information about the fixing
1979 	 *  nor a complete shifted column, we have to use the linear time algorithm for SCIs.
1980 	 *
1981 	 *  The inferinfo integer is set as follows:
1982 	 *
1983 	 *  - If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1
1984 	 *    then we fix these entries to 0 and inferinfo is i * nblocks + j, where (i,j) is the leader of the
1985 	 *    bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments
1986 	 *    above).
1987 	 *
1988 	 *  - If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to
1989 	 *    1 and inferinfo is (nspcons*nblocks) + i * nblocks + j, where (i,j) is the leader of the bar; see
1990 	 *    Proposition 1 (2c).
1991 	 */
1992 	static
1993 	SCIP_RETCODE resolvePropagation(
1994 	   SCIP*                 scip,               /**< SCIP data structure */
1995 	   SCIP_CONS*            cons,               /**< constraint that inferred the bound change */
1996 	   int                   inferinfo,          /**< inference information */
1997 	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
1998 	   SCIP_RESULT*          result              /**< pointer to store the result of the propagation conflict resolving call */
1999 	   )
2000 	{  /*lint --e{715}*/
2001 	   SCIP_CONSDATA* consdata;
2002 	   SCIP_Real** vals;
2003 	   SCIP_Real** weights;
2004 	   SCIP_VAR*** vars;
2005 	   SCIP_ORBITOPETYPE orbitopetype;
2006 	   int** cases;
2007 	
2008 	   int i;
2009 	   int j;
2010 	   int nspcons;
2011 	   int nblocks;
2012 	
2013 	   assert( scip != NULL );
2014 	   assert( cons != NULL );
2015 	   assert( result != NULL );
2016 	
2017 	   consdata = SCIPconsGetData(cons);
2018 	   assert( consdata != NULL );
2019 	   assert( consdata->nspcons > 0 );
2020 	   assert( consdata->nblocks > 0 );
2021 	   assert( consdata->vars != NULL );
2022 	   assert( consdata->vals != NULL );
2023 	   assert( consdata->weights != NULL );
2024 	   assert( consdata->cases != NULL );
2025 	   assert( consdata->istrianglefixed );
2026 	
2027 	   *result = SCIP_DIDNOTFIND;
2028 	   if ( ! consdata->resolveprop )
2029 	      return SCIP_OKAY;
2030 	
2031 	   nspcons = consdata->nspcons;
2032 	   nblocks = consdata->nblocks;
2033 	   vars = consdata->vars;
2034 	   vals = consdata->vals;
2035 	   weights = consdata->weights;
2036 	   orbitopetype = consdata->orbitopetype;
2037 	   cases = consdata->cases;
2038 	
2039 	   SCIPdebugMsg(scip, "Propagation resolution method of orbitope constraint using orbitopal fixing\n");
2040 	
2041 	   /* fill table */
2042 	   for (i = 0; i < nspcons; ++i)
2043 	   {
2044 	      int lastcolumn;
2045 	
2046 	      /* last column considered as part of the bar: */
2047 	      lastcolumn = nblocks - 1;
2048 	      if ( lastcolumn > i )
2049 	         lastcolumn = i;
2050 	      for (j = 0; j <= lastcolumn; ++j)
2051 	      {
2052 	         /* if the variable was fixed to zero at conflict time */
2053 	         if ( SCIPgetVarUbAtIndex(scip, vars[i][j], bdchgidx, FALSE) < 0.5 )
2054 	            vals[i][j] = 0.0;
2055 	         else
2056 	         {
2057 	            /* if the variable was fixed to one at conflict time */
2058 	            if ( SCIPgetVarLbAtIndex(scip, vars[i][j], bdchgidx, FALSE) > 0.5 )
2059 	               vals[i][j] = 2.0;
2060 	            else
2061 	               vals[i][j] = 1.0;
2062 	         }
2063 	      }
2064 	   }
2065 	
2066 	#ifdef PRINT_MATRIX
2067 	   SCIPdebugMsg(scip, "Matrix:\n");
2068 	   printMatrix(scip, consdata);
2069 	#endif
2070 	
2071 	   /* computation of table: this now minimizes the value of the shifted column */
2072 	   assert( consdata->istrianglefixed );
2073 	   computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2074 	
2075 	   /* if we fixed variables in the bar to zero */
2076 	   assert( inferinfo >= 0 && inferinfo < 2 * nspcons * nblocks );
2077 	   if ( inferinfo < nspcons * nblocks )
2078 	   {
2079 	      int p1;
2080 	      int p2;
2081 	#ifdef SCIP_DEBUG
2082 	      char str[SCIP_MAXSTRLEN];
2083 	      char tmpstr[SCIP_MAXSTRLEN];
2084 	#endif
2085 	
2086 	      i = (int) (inferinfo / nblocks);
2087 	      j = inferinfo % nblocks;
2088 	      assert( 0 <= i && i < nspcons );
2089 	      assert( 0 <= j && j < nblocks );
2090 	
2091 	      /* find SCI with value 0 */
2092 	      assert( weights[i-1][j-1] < 0.5 );
2093 	
2094 	      SCIPdebugMsg(scip, " -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i, MIN(i,nblocks));
2095 	#ifdef SCIP_DEBUG
2096 	      str[0] = '\0';
2097 	#endif
2098 	
2099 	      p1 = i-1;
2100 	      p2 = j-1;
2101 	      do
2102 	      {
2103 	         assert( cases[p1][p2] != -1 );
2104 	         assert( p1 >= 0 && p1 < i );
2105 	         assert( p2 >= 0 && p2 < j );
2106 	
2107 	         /* if case 1 */
2108 	         if ( cases[p1][p2] == 1 )
2109 	            --p2;   /* decrease column */
2110 	         else
2111 	         {
2112 	            /* case 2 or 3: */
2113 	            assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2114 	            assert( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
2115 	            SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
2116 	            *result = SCIP_SUCCESS;
2117 	
2118 	#ifdef SCIP_DEBUG
2119 	            (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
2120 	            (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2121 	#endif
2122 	
2123 	            if ( cases[p1][p2] == 3 )
2124 	               break;
2125 	         }
2126 	         --p1;  /* decrease row */
2127 	      }
2128 	      while ( p1 >= 0 );   /* should always be true, i.e. the break should end the loop */
2129 	      assert( cases[p1][p2] == 3 );
2130 	
2131 	#ifdef SCIP_DEBUG
2132 	      SCIPdebugMsg(scip, "%s\n", str);
2133 	#endif
2134 	   }
2135 	   else
2136 	   {
2137 	      int k;
2138 	      int p1;
2139 	      int p2;
2140 	#ifndef NDEBUG
2141 	      int pos1;
2142 	      int pos2;
2143 	#endif
2144 	#ifdef SCIP_DEBUG
2145 	      char str[SCIP_MAXSTRLEN];
2146 	      char tmpstr[SCIP_MAXSTRLEN];
2147 	#endif
2148 	
2149 	      /* if we fixed a variable in the SC to 1 */
2150 	      inferinfo -= nspcons * nblocks;
2151 	      i = (int) inferinfo / nblocks;
2152 	      j = inferinfo % nblocks;
2153 	      assert( 0 <= i && i < nspcons );
2154 	      assert( 0 <= j && j < nblocks );
2155 	
2156 	      /* In rare cases it might happen that we fixed a variable to 1, but the node later becomes infeasible by globally
2157 	       * fixing variables to 0. In this case, it might happen that we find a SC with value 0 instead of 1. We then
2158 	       * cannot use this SC to repropagate (and do not know how to reconstruct the original reasoning). */
2159 	      if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 )
2160 	      {
2161 	         SCIPdebugMsg(scip, " -> reason for x[%d][%d] = 1 was the following SC:\n", i, j);
2162 	#ifdef SCIP_DEBUG
2163 	         (void) SCIPsnprintf(str, SCIP_MAXSTRLEN, "SC:");
2164 	#endif
2165 	
2166 	         p1 = i-1;
2167 	         p2 = j-1;
2168 	#ifndef NDEBUG
2169 	         pos1 = -1;
2170 	         pos2 = -1;
2171 	#endif
2172 	         do
2173 	         {
2174 	            assert( cases[p1][p2] != -1 );
2175 	            assert( p1 >= 0 && p1 < i );
2176 	            assert( p2 >= 0 && p2 < j );
2177 	
2178 	            /* if case 1 */
2179 	            if ( cases[p1][p2] == 1 )
2180 	               --p2;   /* decrease column */
2181 	            else
2182 	            {
2183 	               /* case 2 or 3: reason are formed by variables in SC fixed to 0 */
2184 	               assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2185 	               if ( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 )
2186 	               {
2187 	                  SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
2188 	                  *result = SCIP_SUCCESS;
2189 	
2190 	#ifdef SCIP_DEBUG
2191 	                  (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
2192 	                  (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2193 	#endif
2194 	               }
2195 	#ifndef NDEBUG
2196 	               else
2197 	               {
2198 	                  assert( SCIPgetVarLbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
2199 	                  assert( pos1 == -1 && pos2 == -1 );
2200 	                  pos1 = p1;
2201 	                  pos2 = p2;
2202 	               }
2203 	#endif
2204 	               if ( cases[p1][p2] == 3 )
2205 	                  break;
2206 	            }
2207 	            --p1;  /* decrease row */
2208 	         }
2209 	         while ( p1 >= 0 );   /* should always be true, i.e., the break should end the loop */
2210 	         assert( cases[p1][p2] == 3 );
2211 	         assert( pos1 >= 0 && pos2 >= 0 );
2212 	
2213 	         /* distinguish partitioning/packing */
2214 	         if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2215 	         {
2216 	            /* partitioning case */
2217 	#ifdef SCIP_DEBUG
2218 	            (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, "  before bar: ");
2219 	            (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2220 	#endif
2221 	            /* add variables before the bar in the partitioning case */
2222 	            for (k = 0; k < j; ++k)
2223 	            {
2224 	               assert( SCIPgetVarUbAtIndex(scip, vars[i][k], bdchgidx, FALSE) < 0.5 );
2225 	               SCIP_CALL( SCIPaddConflictUb(scip, vars[i][k], bdchgidx) );
2226 	               *result = SCIP_SUCCESS;
2227 	#ifdef SCIP_DEBUG
2228 	               (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", i, k);
2229 	               (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2230 	#endif
2231 	            }
2232 	
2233 	#ifdef SCIP_DEBUG
2234 	            SCIPdebugMsg(scip, "%s\n", str);
2235 	#endif
2236 	         }
2237 	         else
2238 	         {
2239 	            /* packing case */
2240 	            int lastcolumn;
2241 	
2242 	            /* last column considered as part of the bar: */
2243 	            lastcolumn = nblocks - 1;
2244 	            if ( lastcolumn > i )
2245 	               lastcolumn = i;
2246 	
2247 	            /* search for variable in the bar that is fixed to 1 in the packing case */
2248 	            for (k = j; k <= lastcolumn; ++k)
2249 	            {
2250 	               if ( SCIPgetVarLbAtIndex(scip, vars[i][k], bdchgidx, FALSE) > 0.5 )
2251 	               {
2252 	                  SCIP_CALL( SCIPaddConflictLb(scip, vars[i][k], bdchgidx) );
2253 	                  *result = SCIP_SUCCESS;
2254 	                  SCIPdebugMsg(scip, "   and variable x[%d][%d] fixed to 1.\n", i, k);
2255 	                  break;
2256 	               }
2257 	            }
2258 	         }
2259 	      }
2260 	   }
2261 	
2262 	   return SCIP_OKAY;
2263 	}
2264 	
2265 	
2266 	/** check packing/partitioning orbitope solution for feasibility */
2267 	static
2268 	SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution(
2269 	   SCIP*                 scip,               /**< SCIP data structure */
2270 	   SCIP_CONS*            cons,               /**< pointer to orbitope constraint */
2271 	   SCIP_RESULT*          result              /**< pointer to store the result of the enforcing call */
2272 	   )
2273 	{
2274 	   SCIP_CONSDATA* consdata;
2275 	   SCIP_Real** weights;
2276 	   SCIP_Real** vals;
2277 	   int** cases;
2278 	   int nspcons;
2279 	   int nblocks;
2280 	   int i;
2281 	   int j;
2282 	
2283 	   assert( cons != NULL );
2284 	
2285 	   consdata = SCIPconsGetData(cons);
2286 	
2287 	   assert( scip != NULL );
2288 	   assert( consdata != NULL );
2289 	   assert( consdata->nspcons > 0 );
2290 	   assert( consdata->nblocks > 0 );
2291 	   assert( consdata->vals != NULL );
2292 	   assert( consdata->weights != NULL );
2293 	   assert( consdata->cases != NULL );
2294 	
2295 	   /* check for upper right triangle */
2296 	   if ( ! consdata->istrianglefixed )
2297 	   {
2298 	      SCIP_Bool infeasible = FALSE;
2299 	      int nfixedvars = 0;
2300 	
2301 	      SCIP_CALL( fixTriangle(scip, cons, &infeasible, &nfixedvars) );
2302 	      if ( infeasible )
2303 	      {
2304 	         *result = SCIP_CUTOFF;
2305 	         return SCIP_OKAY;
2306 	      }
2307 	      if ( nfixedvars > 0 )
2308 	      {
2309 	         *result = SCIP_REDUCEDDOM;
2310 	         return SCIP_OKAY;
2311 	      }
2312 	   }
2313 	
2314 	   nspcons = consdata->nspcons;
2315 	   nblocks = consdata->nblocks;
2316 	   vals = consdata->vals;
2317 	   weights = consdata->weights;
2318 	   cases = consdata->cases;
2319 	
2320 	   /* get solution */
2321 	   copyValues(scip, consdata, NULL);
2322 	   SCIPdebugMsg(scip, "Enforcing (pseudo solutions) for orbitope constraint <%s>\n", SCIPconsGetName(cons));
2323 	
2324 	   /* compute table */
2325 	   assert( consdata->istrianglefixed );
2326 	   computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2327 	
2328 	   /* loop through rows */
2329 	   for (i = 1; i < nspcons; ++i)
2330 	   {
2331 	      SCIP_Real bar = 0.0;
2332 	      int lastcolumn;
2333 	
2334 	      lastcolumn = nblocks - 1;
2335 	
2336 	      /* last column considered as part of the bar: */
2337 	      if ( lastcolumn > i )
2338 	         lastcolumn = i;
2339 	
2340 	      /* traverse row from right to left */
2341 	      for (j = lastcolumn; j > 0; --j)
2342 	      {
2343 	         bar += vals[i][j];
2344 	         assert( SCIPisIntegral(scip, vals[i][j]) );
2345 	
2346 	         /* check whether weights[i-1][j-1] < bar  (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2347 	         if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2348 	         {
2349 	            SCIPdebugMsg(scip, "Solution is infeasible.\n");
2350 	            *result = SCIP_INFEASIBLE;
2351 	            return SCIP_OKAY;
2352 	         }
2353 	      }
2354 	   }
2355 	
2356 	   return SCIP_OKAY;
2357 	}
2358 	
2359 	
2360 	/** check packing/partitioning orbitope solution for feasibility */
2361 	static
2362 	SCIP_RETCODE checkPackingPartitioningOrbitopeSolution(
2363 	   SCIP*                 scip,               /**< SCIP data structure */
2364 	   SCIP_CONS*            cons,               /**< pointer to orbitope constraint */
2365 	   SCIP_SOL*             sol,                /**< solution to be checked */
2366 	   SCIP_RESULT*          result,             /**< pointer to store the result of the enforcing call */
2367 	   SCIP_Bool             printreason         /**< whether reason for infeasibility should be printed */
2368 	   )
2369 	{
2370 	   SCIP_CONSDATA* consdata;
2371 	   SCIP_VAR*** vars;
2372 	   SCIP_Real** vals;
2373 	   SCIP_Real** weights;
2374 	   int** cases;
2375 	   int nspcons;
2376 	   int nblocks;
2377 	   int i;
2378 	   int j;
2379 	
2380 	   /* get data of constraint */
2381 	   assert( cons != 0 );
2382 	   consdata = SCIPconsGetData(cons);
2383 	
2384 	   assert( consdata != NULL );
2385 	   assert( consdata->nspcons > 0 );
2386 	   assert( consdata->nblocks > 0 );
2387 	   assert( consdata->vars != NULL );
2388 	   assert( consdata->vals != NULL );
2389 	   assert( consdata->weights != NULL );
2390 	   assert( consdata->cases != NULL );
2391 	
2392 	   nspcons = consdata->nspcons;
2393 	   nblocks = consdata->nblocks;
2394 	   vars = consdata->vars;
2395 	   vals = consdata->vals;
2396 	   weights  = consdata->weights;
2397 	   cases = consdata->cases;
2398 	
2399 	   /* get solution */
2400 	   copyValues(scip, consdata, sol);
2401 	   SCIPdebugMsg(scip, "Checking orbitope constraint <%s> ...\n", SCIPconsGetName(cons));
2402 	
2403 	   /* check upper right triangle (if not yet fixed to zero or in debug mode */
2404 	#ifdef NDEBUG
2405 	   if ( ! consdata->istrianglefixed )
2406 	#endif
2407 	   {
2408 	      int diagsize;
2409 	
2410 	      /* get last row of triangle */
2411 	      diagsize = nblocks;
2412 	      if ( nspcons < nblocks )
2413 	         diagsize = nspcons;
2414 	
2415 	      /* check variables */
2416 	      for (i = 0; i < diagsize; ++i)
2417 	      {
2418 	         for (j = i+1; j < nblocks; ++j)
2419 	         {
2420 	            if ( ! SCIPisFeasZero(scip, vals[i][j]) )
2421 	            {
2422 	               if ( printreason )
2423 	                  SCIPinfoMessage(scip, NULL, "variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]);
2424 	               *result = SCIP_INFEASIBLE;
2425 	            }
2426 	         }
2427 	      }
2428 	   }
2429 	
2430 	   /* compute table */
2431 	   computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2432 	
2433 	   /* loop through rows */
2434 	   for (i = 1; i < nspcons; ++i)
2435 	   {
2436 	      SCIP_Real bar;
2437 	      int lastcolumn;
2438 	
2439 	      lastcolumn = nblocks - 1;
2440 	      bar = 0.0;
2441 	      /* last column considered as part of the bar: */
2442 	      if ( lastcolumn > i )
2443 	         lastcolumn = i;
2444 	
2445 	      /* traverse row from right to left */
2446 	      for (j = lastcolumn; j > 0; --j)
2447 	      {
2448 	         bar += vals[i][j];
2449 	         assert( SCIPisFeasIntegral(scip, vals[i][j]) );
2450 	
2451 	         /* check whether weights[i-1][j-1] < bar  (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2452 	         if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2453 	         {
2454 	            SCIPdebugMsg(scip, "Solution is infeasible.\n");
2455 	            *result = SCIP_INFEASIBLE;
2456 	
2457 	            if ( printreason )
2458 	            {
2459 	               int l;
2460 	               int p1;
2461 	               int p2;
2462 	
2463 	               SCIPinfoMessage(scip, NULL, "violated SCI: bar(");
2464 	
2465 	               /* first output bar */
2466 	               for (l = j; l < nblocks; ++l)
2467 	                  SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[i][l]), consdata->vals[i][l]);
2468 	
2469 	               SCIPinfoMessage(scip, NULL, ")  SC(");
2470 	
2471 	               /* output shifted column */
2472 	               p1 = i-1;
2473 	               p2 = j-1;
2474 	               do
2475 	               {
2476 	                  assert( cases[p1][p2] != -1 );
2477 	                  assert( p1 >= 0 && p1 < i );
2478 	                  assert( p2 >= 0 && p2 < j );
2479 	
2480 	                  /* if case 1 */
2481 	                  if (cases[p1][p2] == 1)
2482 	                     --p2;   /* decrease column */
2483 	                  else
2484 	                  {
2485 	                     /* case 2 or 3: */
2486 	                     assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2487 	                     SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[p1][p2]), consdata->vals[p1][p2]);
2488 	                     if ( cases[p1][p2] == 3 )
2489 	                        break;
2490 	                  }
2491 	                  --p1;  /* decrease row */
2492 	               }
2493 	               while ( p1 >= 0 );   /* should always be true, i.e. the break should end the loop */
2494 	               assert( cases[p1][p2] == 3 );
2495 	
2496 	               SCIPinfoMessage(scip, NULL, ")");
2497 	            }
2498 	         }
2499 	      }
2500 	   }
2501 	
2502 	   return SCIP_OKAY;
2503 	}
2504 	
2505 	
2506 	/** check full orbitope solution for feasibility */
2507 	static
2508 	SCIP_RETCODE checkFullOrbitopeSolution(
2509 	   SCIP*                 scip,               /**< SCIP data structure */
2510 	   SCIP_CONS*            cons,               /**< constraint to process */
2511 	   SCIP_SOL*             sol,                /**< solution to be checked */
2512 	   SCIP_Bool             printreason,        /**< whether reason for infeasibility should be printed */
2513 	   SCIP_Bool*            feasible            /**< memory address to store whether solution is feasible */
2514 	   )
2515 	{
2516 	   SCIP_CONSDATA* consdata;
2517 	   SCIP_VAR*** vars;
2518 	   SCIP_VAR** vars1;
2519 	   SCIP_VAR** vars2;
2520 	   int nrows;
2521 	   int ncols;
2522 	   int j;
2523 	   int i;
2524 	
2525 	   assert( scip != NULL );
2526 	   assert( cons != NULL );
2527 	   assert( feasible != NULL );
2528 	
2529 	   consdata = SCIPconsGetData(cons);
2530 	
2531 	   assert( consdata != NULL );
2532 	   assert( consdata->vars != NULL );
2533 	   assert( consdata->nspcons > 0 );
2534 	   assert( consdata->nblocks > 0 );
2535 	   assert( ! consdata->ismodelcons ); /* non-model constraints are never checked */
2536 	
2537 	   vars = consdata->vars;
2538 	   nrows = consdata->nspcons;
2539 	   ncols = consdata->nblocks;
2540 	
2541 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) );
2542 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) );
2543 	
2544 	   /* iterate over adjacent columns of orbitope and check whether the first column in this
2545 	    * column pair is lexicographically not smaller than the second column in the pair */
2546 	   *feasible = TRUE;
2547 	   for (j = 1; j < ncols && *feasible; ++j)
2548 	   {
2549 	      for (i = 0; i < nrows; ++i)
2550 	      {
2551 	         vars1[i] = vars[i][j - 1];
2552 	         vars2[i] = vars[i][j];
2553 	      }
2554 	
2555 	      SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, vars1, vars2, nrows, printreason, feasible) );
2556 	   }
2557 	
2558 	   SCIPfreeBufferArray(scip, &vars2);
2559 	   SCIPfreeBufferArray(scip, &vars1);
2560 	
2561 	   return SCIP_OKAY;
2562 	}
2563 	
2564 	
2565 	/** separate orbisack cover inequalities */
2566 	static
2567 	SCIP_RETCODE separateCoversOrbisack(
2568 	   SCIP*                 scip,               /**< SCIP data structure */
2569 	   SCIP_CONS*            cons,               /**< constraint to process */
2570 	   SCIP_SOL*             sol,                /**< solution to separate (NULL for the LP solution) */
2571 	   SCIP_Bool             dynamic,            /**< whether we use a dynamic row order */
2572 	   int*                  ngen,               /**< pointer to store number of generated cuts */
2573 	   SCIP_Bool*            infeasible          /**< pointer to store whether infeasibility has been detected */
2574 	   )
2575 	{
2576 	   SCIP_CONSDATA* consdata;
2577 	   SCIP_VAR*** vars;
2578 	   int* roworder;
2579 	   int nrowsused;
2580 	   int nrows;
2581 	   int ncols;
2582 	   int i;
2583 	   int j;
2584 	   int origrow;
2585 	   SCIP_Real rhs;
2586 	   SCIP_Real lhs;
2587 	   SCIP_Real* coeffs1;
2588 	   SCIP_Real* coeffs2;
2589 	
2590 	   assert( scip != NULL );
2591 	   assert( cons != NULL );
2592 	   assert( ngen != NULL );
2593 	   assert( infeasible != NULL );
2594 	
2595 	   *ngen = 0;
2596 	   *infeasible = FALSE;
2597 	
2598 	   /* get basic data */
2599 	   consdata = SCIPconsGetData(cons);
2600 	   assert( consdata != NULL );
2601 	
2602 	   vars = consdata->vars;
2603 	   nrows = consdata->nspcons;
2604 	   ncols = consdata->nblocks;
2605 	   nrowsused = dynamic ? consdata->nrowsused : nrows;
2606 	   roworder = consdata->roworder;
2607 	
2608 	   /* allocate memory for cover inequalities */
2609 	   SCIP_CALL( SCIPallocBufferArray(scip, &coeffs1, nrowsused) );
2610 	   SCIP_CALL( SCIPallocBufferArray(scip, &coeffs2, nrowsused) );
2611 	
2612 	   lhs = 0.0;
2613 	   rhs = 0.0;
2614 	
2615 	   /* separate orbisack cover inequalities for adjacent columns */
2616 	   for (j = 0; j < ncols - 1 && ! *infeasible; ++j)
2617 	   {
2618 	      SCIP_Real rowval;
2619 	
2620 	      for (i = 0; i < nrowsused; ++i)
2621 	      {
2622 	         origrow = roworder[i];
2623 	
2624 	         assert( origrow >= 0 );
2625 	         assert( origrow < nrows );
2626 	
2627 	         rowval = SCIPgetSolVal(scip, sol, vars[origrow][j + 1]) - SCIPgetSolVal(scip, sol, vars[origrow][j]);
2628 	
2629 	         /* check whether cover inequality is violated */
2630 	         if ( SCIPisEfficacious(scip, rowval + lhs - rhs) )
2631 	         {
2632 	            SCIP_ROW* row;
2633 	            int k;
2634 	
2635 	            /* set coefficients for current inequality */
2636 	            coeffs1[i] = -1.0;
2637 	            coeffs2[i] = 1.0;
2638 	
2639 	            /* add violated orbisack cover inequality */
2640 	            SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
2641 	            SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
2642 	
2643 	            for (k = 0; k <= i; ++k)
2644 	            {
2645 	               int origrow2;
2646 	
2647 	               origrow2 = roworder[k];
2648 	
2649 	               SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j], coeffs1[k]) );
2650 	               SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j + 1], coeffs2[k]) );
2651 	            }
2652 	            SCIP_CALL( SCIPflushRowExtensions(scip, row) );
2653 	
2654 	            SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
2655 	#ifdef SCIP_DEBUG
2656 	            SCIP_CALL( SCIPprintRow(scip, row, NULL) );
2657 	#endif
2658 	            SCIP_CALL( SCIPreleaseRow(scip, &row) );
2659 	
2660 	            *ngen += 1;
2661 	            if ( *infeasible )
2662 	               break;
2663 	
2664 	            /* reset coefficients for next inequality */
2665 	            coeffs1[i] = 0.0;
2666 	            coeffs2[i] = 0.0;
2667 	         }
2668 	
2669 	         /* add argmax( 1 - vals[i][0], vals[i][1] ) as coefficient and ensure that both vars1[0] and vars2[0] are
2670 	          * contained in the LIFTED cover inequality */
2671 	         rowval = SCIPgetSolVal(scip, sol, vars[origrow][j]) + SCIPgetSolVal(scip, sol, vars[origrow][j + 1]);
2672 	         if ( SCIPisEfficacious(scip, 1.0 - rowval) )
2673 	         {
2674 	            coeffs1[i] = -1.0;
2675 	            coeffs2[i] = 0.0;
2676 	            lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]);
2677 	
2678 	            /* apply lifting? */
2679 	            if ( i == 0 )
2680 	            {
2681 	               coeffs2[i] = 1.0;
2682 	               lhs += SCIPgetSolVal(scip, sol, vars[origrow][j + 1]);
2683 	            }
2684 	         }
2685 	         else
2686 	         {
2687 	            coeffs1[i] = 0.0;
2688 	            coeffs2[i] = 1.0;
2689 	            lhs += SCIPgetSolVal(scip, sol, vars[origrow][j]);
2690 	            rhs += 1.0;
2691 	
2692 	            /* apply lifting? */
2693 	            if ( i == 0 )
2694 	            {
2695 	               coeffs1[i] = -1.0;
2696 	               lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]);
2697 	               rhs -= 1.0;
2698 	            }
2699 	         }
2700 	      }
2701 	   }
2702 	
2703 	   SCIPfreeBufferArray(scip, &coeffs1);
2704 	   SCIPfreeBufferArray(scip, &coeffs2);
2705 	
2706 	   return SCIP_OKAY;
2707 	}
2708 	
2709 	
2710 	/** separate or enforce constraints */
2711 	static
2712 	SCIP_RETCODE separateConstraints(
2713 	   SCIP*                 scip,               /**< SCIP data structure */
2714 	   SCIP_CONSHDLR*        conshdlr,           /**< constraint handler */
2715 	   SCIP_CONS**           conss,              /**< constraints to process */
2716 	   int                   nconss,             /**< number of constraints */
2717 	   int                   nusefulconss,       /**< number of useful (non-obsolete) constraints to process */
2718 	   SCIP_SOL*             sol,                /**< solution to separate (NULL for the LP solution) */
2719 	   SCIP_RESULT*          result,             /**< pointer to store the result (should be initialized) */
2720 	   SCIP_Bool             enforce             /**< whether we enforce orbitope constraints */
2721 	   )
2722 	{
2723 	   SCIP_Bool infeasible = FALSE;
2724 	   int nfixedvars = 0;
2725 	   int ncuts = 0;
2726 	   int c;
2727 	
2728 	   assert( scip != NULL );
2729 	   assert( conshdlr != NULL );
2730 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2731 	   assert( result != NULL );
2732 	
2733 	   /* loop through constraints */
2734 	   for (c = 0; c < nconss && ! infeasible; c++)
2735 	   {
2736 	      SCIP_CONSHDLRDATA* conshdlrdata;
2737 	      SCIP_CONSDATA* consdata;
2738 	      int nconsfixedvars = 0;
2739 	      int nconscuts = 0;
2740 	      SCIP_ORBITOPETYPE orbitopetype;
2741 	
2742 	      assert( conss[c] != NULL );
2743 	
2744 	      /* get data of constraint */
2745 	      consdata = SCIPconsGetData(conss[c]);
2746 	      assert( consdata != NULL );
2747 	
2748 	      /* do not enforce non-model constraints */
2749 	      if ( enforce && !consdata->ismodelcons )
2750 	         continue;
2751 	
2752 	      /* get solution */
2753 	      copyValues(scip, consdata, sol);
2754 	
2755 	      /* separate */
2756 	      orbitopetype = consdata->orbitopetype;
2757 	
2758 	      conshdlrdata = SCIPconshdlrGetData(conshdlr);
2759 	      if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2760 	      {
2761 	         SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
2762 	         nfixedvars += nconsfixedvars;
2763 	      }
2764 	      else if ( conshdlrdata->sepafullorbitope )
2765 	      {
2766 	         SCIP_CALL( separateCoversOrbisack(scip, conss[c], sol, consdata->usedynamicprop && !consdata->ismodelcons, &nconscuts, &infeasible) );
2767 	      }
2768 	      ncuts += nconscuts;
2769 	
2770 	      /* stop after the useful constraints if we found cuts of fixed variables */
2771 	      if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
2772 	         break;
2773 	   }
2774 	
2775 	   if ( infeasible )
2776 	   {
2777 	      SCIPdebugMsg(scip, "Infeasible node.\n");
2778 	      *result = SCIP_CUTOFF;
2779 	   }
2780 	   else if ( nfixedvars > 0 )
2781 	   {
2782 	      SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars);
2783 	      *result = SCIP_REDUCEDDOM;
2784 	   }
2785 	   else if ( ncuts > 0 )
2786 	   {
2787 	      SCIPdebugMsg(scip, "Separated %dinequalities.\n", ncuts);
2788 	      *result = SCIP_SEPARATED;
2789 	   }
2790 	   else
2791 	   {
2792 	      SCIPdebugMsg(scip, "No violated inequality found during separation.\n");
2793 	   }
2794 	
2795 	   return SCIP_OKAY;
2796 	}
2797 	
2798 	
2799 	/** check whether all variables in an orbitope constraint are fixed */
2800 	static
2801 	SCIP_RETCODE checkRedundantCons(
2802 	   SCIP*                 scip,               /**< SCIP data structure */
2803 	   SCIP_CONS*            cons,               /**< constraint to be processed */
2804 	   SCIP_Bool*            redundant           /**< pointer to store whether constraint is redundant (contains no active vars) */
2805 	   )
2806 	{
2807 	   SCIP_CONSDATA* consdata;
2808 	   SCIP_VAR*** vars;
2809 	   int i;
2810 	   int j;
2811 	   int nrows;
2812 	   int ncols;
2813 	
2814 	   assert( scip != NULL );
2815 	   assert( cons != NULL );
2816 	   assert( redundant != NULL );
2817 	
2818 	   *redundant = FALSE;
2819 	
2820 	   consdata = SCIPconsGetData(cons);
2821 	   assert( consdata != NULL );
2822 	   assert( consdata->vars != NULL );
2823 	   assert( consdata->nspcons > 0 );
2824 	   assert( consdata->nblocks > 0 );
2825 	
2826 	   vars = consdata->vars;
2827 	   nrows = consdata->nspcons;
2828 	   ncols = consdata->nblocks;
2829 	
2830 	   /* check whether there exists an active variable in the orbitope */
2831 	   for (i = 0; i < nrows; ++i)
2832 	   {
2833 	      for (j = 0; j < ncols; ++j)
2834 	      {
2835 	         if ( SCIPvarIsActive(vars[i][j]) )
2836 	            return SCIP_OKAY;
2837 	      }
2838 	   }
2839 	
2840 	   *redundant = TRUE;
2841 	
2842 	   return SCIP_OKAY;
2843 	}
2844 	
2845 	
2846 	/*
2847 	 * Callback methods of constraint handler
2848 	 */
2849 	
2850 	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2851 	static
2852 	SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
2853 	{  /*lint --e{715}*/
2854 	   assert(scip != NULL);
2855 	   assert(conshdlr != NULL);
2856 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2857 	
2858 	   /* call inclusion method of constraint handler */
2859 	   SCIP_CALL( SCIPincludeConshdlrOrbitope(scip) );
2860 	
2861 	   *valid = TRUE;
2862 	
2863 	   return SCIP_OKAY;
2864 	}
2865 	
2866 	/** frees constraint handler */
2867 	static
2868 	SCIP_DECL_CONSFREE(consFreeOrbitope)
2869 	{  /*lint --e{715}*/
2870 	   SCIP_CONSHDLRDATA* conshdlrdata;
2871 	
2872 	   assert( scip != 0 );
2873 	   assert( conshdlr != 0 );
2874 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2875 	
2876 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
2877 	   assert( conshdlrdata != NULL );
2878 	
2879 	   SCIPfreeBlockMemory(scip, &conshdlrdata);
2880 	
2881 	   return SCIP_OKAY;
2882 	}
2883 	
2884 	/** frees specific constraint data */
2885 	static
2886 	SCIP_DECL_CONSDELETE(consDeleteOrbitope)
2887 	{  /*lint --e{715}*/
2888 	   assert(conshdlr != NULL);
2889 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2890 	
2891 	   SCIP_CALL( consdataFree(scip, consdata) );
2892 	
2893 	   return SCIP_OKAY;
2894 	}
2895 	
2896 	/** transforms constraint data into data belonging to the transformed problem */
2897 	static
2898 	SCIP_DECL_CONSTRANS(consTransOrbitope)
2899 	{  /*lint --e{715}*/
2900 	   SCIP_CONSDATA* sourcedata;
2901 	   SCIP_CONSDATA* targetdata;
2902 	
2903 	   assert(conshdlr != NULL);
2904 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2905 	   assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
2906 	   assert(sourcecons != NULL);
2907 	   assert(targetcons != NULL);
2908 	
2909 	   sourcedata = SCIPconsGetData(sourcecons);
2910 	   assert(sourcedata != NULL);
2911 	
2912 	   /* create linear constraint data for target constraint */
2913 	   SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nspcons, sourcedata->nblocks,
2914 	         sourcedata->orbitopetype, sourcedata->resolveprop, sourcedata->usedynamicprop, sourcedata->ismodelcons,
2915 	         sourcedata->mayinteract) );
2916 	
2917 	   /* create target constraint */
2918 	   SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2919 	         SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2920 	         SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2921 	         SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2922 	         SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2923 	
2924 	   return SCIP_OKAY;
2925 	}
2926 	
2927 	/** separation method of constraint handler for LP solutions */
2928 	static
2929 	SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
2930 	{  /*lint --e{715}*/
2931 	   assert( scip != NULL );
2932 	   assert( result != NULL );
2933 	
2934 	   SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2935 	
2936 	   *result = SCIP_DIDNOTRUN;
2937 	
2938 	   /* if solution is integer, skip separation */
2939 	   if ( SCIPgetNLPBranchCands(scip) <= 0 )
2940 	      return SCIP_OKAY;
2941 	
2942 	   *result = SCIP_DIDNOTFIND;
2943 	
2944 	   /* separate constraints */
2945 	   SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, FALSE) );
2946 	
2947 	   return SCIP_OKAY;
2948 	}
2949 	
2950 	/** separation method of constraint handler for arbitrary primal solutions */
2951 	static
2952 	SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
2953 	{  /*lint --e{715}*/
2954 	   assert( scip != NULL );
2955 	   assert( result != NULL );
2956 	
2957 	   SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for primal solution.\n", SCIPconshdlrGetName(conshdlr));
2958 	
2959 	   *result = SCIP_DIDNOTFIND;
2960 	
2961 	   /* separate constraints */
2962 	   SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, FALSE) );
2963 	
2964 	   return SCIP_OKAY;
2965 	}
2966 	
2967 	
2968 	/** constraint enforcing method of constraint handler for LP solutions */
2969 	static
2970 	SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
2971 	{  /*lint --e{715}*/
2972 	   assert( scip != NULL );
2973 	   assert( result != NULL );
2974 	
2975 	   /* we have a negative priority, so we should come after the integrality conshdlr */
2976 	   assert( SCIPgetNLPBranchCands(scip) == 0 );
2977 	
2978 	   SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2979 	
2980 	   *result = SCIP_FEASIBLE;
2981 	
2982 	   /* separate constraints */
2983 	   SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, TRUE) );
2984 	
2985 	   return SCIP_OKAY;
2986 	}
2987 	
2988 	
2989 	/** constraint enforcing method of constraint handler for relaxation solutions */
2990 	static
2991 	SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
2992 	{  /*lint --e{715}*/
2993 	   assert( result != NULL );
2994 	   assert( scip != NULL );
2995 	
2996 	   SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for relaxation solution.\n", SCIPconshdlrGetName(conshdlr));
2997 	
2998 	   *result = SCIP_FEASIBLE;
2999 	
3000 	   /* separate constraints */
3001 	   SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, TRUE) );
3002 	
3003 	   return SCIP_OKAY;
3004 	}
3005 	
3006 	
3007 	/** constraint enforcing method of constraint handler for pseudo solutions */
3008 	static
3009 	SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
3010 	{  /*lint --e{715}*/
3011 	   int c;
3012 	
3013 	   assert( scip != NULL );
3014 	   assert( conshdlr != NULL );
3015 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3016 	   assert( result != NULL );
3017 	
3018 	   *result = SCIP_FEASIBLE;
3019 	   if ( objinfeasible || solinfeasible )
3020 	      return SCIP_OKAY;
3021 	
3022 	   /* loop through constraints */
3023 	   for (c = 0; c < nconss; ++c)
3024 	   {
3025 	      SCIP_CONS* cons;
3026 	      SCIP_CONSDATA* consdata;
3027 	      SCIP_ORBITOPETYPE orbitopetype;
3028 	      SCIP_Bool feasible;
3029 	
3030 	      /* get data of constraint */
3031 	      cons = conss[c];
3032 	      assert( cons != 0 );
3033 	      consdata = SCIPconsGetData(cons);
3034 	
3035 	      assert( consdata != NULL );
3036 	
3037 	      /* do not enforce non-model constraints */
3038 	      if ( !consdata->ismodelcons )
3039 	         continue;
3040 	
3041 	      orbitopetype = consdata->orbitopetype;
3042 	
3043 	      if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3044 	      {
3045 	         SCIP_CALL( enfopsPackingPartitioningOrbitopeSolution(scip, cons, result) );
3046 	      }
3047 	      else
3048 	      {
3049 	         SCIP_CALL( checkFullOrbitopeSolution(scip, cons, NULL, FALSE, &feasible) );
3050 	
3051 	         if ( ! feasible )
3052 	            *result = SCIP_INFEASIBLE;
3053 	      }
3054 	
3055 	      if ( *result == SCIP_INFEASIBLE )
3056 	         break;
3057 	   }
3058 	
3059 	   return SCIP_OKAY;
3060 	}
3061 	
3062 	
3063 	/** feasibility check method of constraint handler for integral solutions */
3064 	static
3065 	SCIP_DECL_CONSCHECK(consCheckOrbitope)
3066 	{  /*lint --e{715}*/
3067 	   int c;
3068 	   SCIP_CONSDATA* consdata;
3069 	   SCIP_ORBITOPETYPE orbitopetype;
3070 	   SCIP_Bool feasible;
3071 	
3072 	   assert( scip != NULL );
3073 	   assert( conshdlr != NULL );
3074 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3075 	   assert( result != NULL );
3076 	
3077 	   *result = SCIP_FEASIBLE;
3078 	
3079 	   /* loop through constraints */
3080 	   for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
3081 	   {
3082 	      assert( conss[c] != 0 );
3083 	      consdata = SCIPconsGetData(conss[c]);
3084 	
3085 	      assert( consdata != NULL );
3086 	
3087 	      /* do not check non-model constraints */
3088 	      if ( !consdata->ismodelcons )
3089 	         continue;
3090 	
3091 	      orbitopetype = consdata->orbitopetype;
3092 	
3093 	      if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3094 	      {
3095 	         SCIP_CALL( checkPackingPartitioningOrbitopeSolution(scip, conss[c], sol, result, printreason) );
3096 	      }
3097 	      else
3098 	      {
3099 	         SCIP_CALL( checkFullOrbitopeSolution(scip, conss[c], sol, printreason, &feasible) );
3100 	
3101 	         if ( ! feasible )
3102 	            *result = SCIP_INFEASIBLE;
3103 	      }
3104 	   }
3105 	   SCIPdebugMsg(scip, "Solution is feasible.\n");
3106 	
3107 	   return SCIP_OKAY;
3108 	}
3109 	
3110 	
3111 	/** domain propagation method of constraint handler */
3112 	static
3113 	SCIP_DECL_CONSPROP(consPropOrbitope)
3114 	{  /*lint --e{715}*/
3115 	   SCIP_Bool infeasible = FALSE;
3116 	   int nfixedvars = 0;
3117 	   int c;
3118 	
3119 	   assert( scip != NULL );
3120 	   assert( conshdlr != NULL );
3121 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3122 	   assert( result != NULL );
3123 	
3124 	   *result = SCIP_DIDNOTRUN;
3125 	
3126 	   /* propagate all useful constraints */
3127 	   for (c = 0; c < nusefulconss && !infeasible; ++c)
3128 	   {
3129 	      assert( conss[c] != 0 );
3130 	
3131 	      SCIPdebugMsg(scip, "Propagation of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
3132 	
3133 	      SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixedvars) );
3134 	   }
3135 	
3136 	   /* return the correct result */
3137 	   if ( infeasible )
3138 	   {
3139 	      *result = SCIP_CUTOFF;
3140 	      SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n");
3141 	   }
3142 	   else if ( nfixedvars > 0 )
3143 	   {
3144 	      *result = SCIP_REDUCEDDOM;
3145 	      SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars);
3146 	   }
3147 	   else if ( nusefulconss > 0 )
3148 	   {
3149 	      *result = SCIP_DIDNOTFIND;
3150 	      SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n");
3151 	   }
3152 	
3153 	   return SCIP_OKAY;
3154 	}
3155 	
3156 	
3157 	/** presolving method of constraint handler */
3158 	static
3159 	SCIP_DECL_CONSPRESOL(consPresolOrbitope)
3160 	{  /*lint --e{715}*/
3161 	   SCIP_Bool infeasible = FALSE;
3162 	   int noldfixedvars;
3163 	   int c;
3164 	   SCIP_Bool redundant;
3165 	
3166 	   assert( scip != NULL );
3167 	   assert( conshdlr != NULL );
3168 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3169 	   assert( result != NULL );
3170 	
3171 	   *result = SCIP_DIDNOTRUN;
3172 	   noldfixedvars = *nfixedvars;
3173 	
3174 	   /* propagate all useful constraints
3175 	    *
3176 	    * @todo use an event handler to only propagate if a variable in the orbitope has been fixed
3177 	    */
3178 	   for (c = 0; c < nconss && !infeasible; ++c)
3179 	   {
3180 	      int nfixed = 0;
3181 	
3182 	      assert( conss[c] != 0 );
3183 	
3184 	      SCIPdebugMsg(scip, "Presolving of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
3185 	
3186 	      /* first propagate */
3187 	      SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
3188 	      *nfixedvars += nfixed;
3189 	
3190 	      if ( ! infeasible )
3191 	      {
3192 	         SCIP_CALL( checkRedundantCons(scip, conss[c], &redundant) );
3193 	
3194 	         if ( redundant )
3195 	         {
3196 	            SCIPdebugMsg(scip, "Orbitope constraint <%s> is redundant: it does not contain active variables\n",
3197 	               SCIPconsGetName(conss[c]));
3198 	            SCIP_CALL( SCIPdelCons(scip, conss[c]) );
3199 	            assert( ! SCIPconsIsActive(conss[c]) );
3200 	            (*ndelconss)++;
3201 	            continue;
3202 	         }
3203 	      }
3204 	   }
3205 	
3206 	   if ( infeasible )
3207 	   {
3208 	      *result = SCIP_CUTOFF;
3209 	      SCIPdebugMsg(scip, "Presolving detected infeasibility.\n");
3210 	   }
3211 	   else if ( *nfixedvars > noldfixedvars )
3212 	   {
3213 	      *result = SCIP_SUCCESS;
3214 	   }
3215 	   else if ( nconss > 0 )
3216 	   {
3217 	      *result = SCIP_DIDNOTFIND;
3218 	      SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n");
3219 	   }
3220 	
3221 	   return SCIP_OKAY;
3222 	}
3223 	
3224 	
3225 	/** propagation conflict resolving method of constraint handler */
3226 	static
3227 	SCIP_DECL_CONSRESPROP(consRespropOrbitope)
3228 	{  /*lint --e{715}*/
3229 	   SCIP_CONSDATA* consdata;
3230 	   SCIP_ORBITOPETYPE orbitopetype;
3231 	
3232 	   assert( scip != NULL );
3233 	   assert( cons != NULL );
3234 	   assert( infervar != NULL );
3235 	   assert( bdchgidx != NULL );
3236 	   assert( result != NULL );
3237 	
3238 	   consdata = SCIPconsGetData(cons);
3239 	   assert( consdata != NULL );
3240 	
3241 	   orbitopetype = consdata->orbitopetype;
3242 	
3243 	   /* resolution for full orbitopes not availabe yet */
3244 	   if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3245 	   {
3246 	      SCIP_CALL( resolvePropagation(scip, cons, inferinfo, bdchgidx, result) );
3247 	   }
3248 	   else
3249 	   {
3250 	      SCIP_CALL( resolvePropagationFullOrbitope(scip, conshdlr, cons, inferinfo, bdchgidx, result) );
3251 	   }
3252 	
3253 	   return SCIP_OKAY;
3254 	}
3255 	
3256 	
3257 	/** variable rounding lock method of constraint handler */
3258 	static
3259 	SCIP_DECL_CONSLOCK(consLockOrbitope)
3260 	{  /*lint --e{715}*/
3261 	   SCIP_CONSDATA* consdata;
3262 	   SCIP_VAR*** vars;
3263 	   int i;
3264 	   int j;
3265 	   int nspcons;
3266 	   int nblocks;
3267 	
3268 	   assert( scip != NULL );
3269 	   assert( conshdlr != NULL );
3270 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3271 	   assert( cons != NULL );
3272 	   assert( locktype == SCIP_LOCKTYPE_MODEL );
3273 	
3274 	   consdata = SCIPconsGetData(cons);
3275 	   assert( consdata != NULL );
3276 	   assert( consdata->nspcons > 0 );
3277 	   assert( consdata->nblocks > 0 );
3278 	   assert( consdata->vars != NULL );
3279 	
3280 	   SCIPdebugMsg(scip, "Locking method for orbitope constraint handler\n");
3281 	
3282 	   nspcons = consdata->nspcons;
3283 	   nblocks = consdata->nblocks;
3284 	   vars = consdata->vars;
3285 	
3286 	   /* add up locks and down locks on each variable */
3287 	   for (i = 0; i < nspcons; ++i)
3288 	   {
3289 	      for (j = 0; j < nblocks; ++j)
3290 	         SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3291 	   }
3292 	
3293 	   return SCIP_OKAY;
3294 	}
3295 	
3296 	
3297 	/** constraint display method of constraint handler */
3298 	static
3299 	SCIP_DECL_CONSPRINT(consPrintOrbitope)
3300 	{
3301 	   SCIP_CONSDATA* consdata;
3302 	   SCIP_VAR*** vars;
3303 	   int i;
3304 	   int j;
3305 	   int nspcons;
3306 	   int nblocks;
3307 	   SCIP_ORBITOPETYPE orbitopetype;
3308 	
3309 	   assert( scip != NULL );
3310 	   assert( conshdlr != NULL );
3311 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3312 	   assert( cons != NULL );
3313 	
3314 	   consdata = SCIPconsGetData(cons);
3315 	   assert( consdata != NULL );
3316 	   assert( consdata->nspcons > 0 );
3317 	   assert( consdata->nblocks > 0 );
3318 	   assert( consdata->vars != NULL );
3319 	
3320 	   nspcons = consdata->nspcons;
3321 	   nblocks = consdata->nblocks;
3322 	   vars = consdata->vars;
3323 	   orbitopetype = consdata->orbitopetype;
3324 	
3325 	   SCIPdebugMsg(scip, "Printing method for orbitope constraint handler\n");
3326 	
3327 	   switch ( orbitopetype )
3328 	   {
3329 	   case SCIP_ORBITOPETYPE_PARTITIONING:
3330 	      SCIPinfoMessage(scip, file, "partOrbitope(");
3331 	      break;
3332 	   case SCIP_ORBITOPETYPE_PACKING:
3333 	      SCIPinfoMessage(scip, file, "packOrbitope(");
3334 	      break;
3335 	   case SCIP_ORBITOPETYPE_FULL:
3336 	      SCIPinfoMessage(scip, file, "fullOrbitope(");
3337 	      break;
3338 	   default:
3339 	      SCIPABORT();
3340 	   }
3341 	
3342 	   for (i = 0; i < nspcons; ++i)
3343 	   {
3344 	      for (j = 0; j < nblocks; ++j)
3345 	      {
3346 	         if ( j > 0 )
3347 	            SCIPinfoMessage(scip, file, ",");
3348 	         SCIP_CALL( SCIPwriteVarName(scip, file, vars[i][j], TRUE) );
3349 	      }
3350 	      if ( i < nspcons-1 )
3351 	         SCIPinfoMessage(scip, file, ".");
3352 	   }
3353 	   SCIPinfoMessage(scip, file, ")");
3354 	
3355 	   return SCIP_OKAY;
3356 	}
3357 	
3358 	
3359 	/** constraint copying method of constraint handler */
3360 	static
3361 	SCIP_DECL_CONSCOPY(consCopyOrbitope)
3362 	{
3363 	   SCIP_CONSHDLRDATA* conshdlrdata;
3364 	   SCIP_CONSDATA* sourcedata;
3365 	   SCIP_VAR*** sourcevars;
3366 	   SCIP_VAR*** vars;
3367 	   int nspcons;
3368 	   int nblocks;
3369 	   int i;
3370 	   int k;
3371 	   int j;
3372 	
3373 	   assert( scip != NULL );
3374 	   assert( cons != NULL );
3375 	   assert( sourcescip != NULL );
3376 	   assert( sourceconshdlr != NULL );
3377 	   assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
3378 	   assert( sourcecons != NULL );
3379 	   assert( varmap != NULL );
3380 	   assert( valid != NULL );
3381 	
3382 	   *valid = TRUE;
3383 	
3384 	   SCIPdebugMsg(scip, "Copying method for orbitope constraint handler.\n");
3385 	
3386 	   sourcedata = SCIPconsGetData(sourcecons);
3387 	   assert( sourcedata != NULL );
3388 	   assert( sourcedata->nspcons > 0 );
3389 	   assert( sourcedata->nblocks > 0 );
3390 	   assert( sourcedata->vars != NULL );
3391 	
3392 	   conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
3393 	   assert( conshdlrdata != NULL );
3394 	
3395 	   /* do not copy non-model constraints */
3396 	   if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
3397 	   {
3398 	      *valid = FALSE;
3399 	
3400 	      return SCIP_OKAY;
3401 	   }
3402 	
3403 	   nspcons = sourcedata->nspcons;
3404 	   nblocks = sourcedata->nblocks;
3405 	   sourcevars = sourcedata->vars;
3406 	
3407 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, nspcons) );
3408 	   for (i = 0; i < nspcons && *valid; ++i)
3409 	   {
3410 	      SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), nblocks) );  /*lint !e866*/
3411 	
3412 	      for (j = 0; j < nblocks && *valid; ++j)
3413 	      {
3414 	         SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
3415 	         assert( !(*valid) || vars[i][j] != NULL );
3416 	      }
3417 	   }
3418 	
3419 	   /* only create the target constraint, if all variables could be copied */
3420 	   if ( *valid )
3421 	   {
3422 	      /* create copied constraint */
3423 	      if ( name == NULL )
3424 	         name = SCIPconsGetName(sourcecons);
3425 	
3426 	      SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name,
3427 	            vars, sourcedata->orbitopetype, nspcons, nblocks, sourcedata->usedynamicprop,
3428 	            sourcedata->resolveprop, sourcedata->ismodelcons, sourcedata->mayinteract,
3429 	            initial, separate, enforce, check, propagate,
3430 	            local, modifiable, dynamic, removable, stickingatnode) );
3431 	   }
3432 	
3433 	   /* free space; only up to row i if copying failed */
3434 	   assert( 0 <= i && i <= nspcons );
3435 	   for (k = i - 1; k >= 0; --k)
3436 	      SCIPfreeBufferArray(scip, &vars[k]);
3437 	   SCIPfreeBufferArray(scip, &vars);
3438 	
3439 	   return SCIP_OKAY;
3440 	}
3441 	
3442 	
3443 	/** constraint parsing method of constraint handler */
3444 	static
3445 	SCIP_DECL_CONSPARSE(consParseOrbitope)
3446 	{  /*lint --e{715}*/
3447 	   const char* s;
3448 	   char* endptr;
3449 	   SCIP_ORBITOPETYPE orbitopetype;
3450 	   SCIP_VAR*** vars;
3451 	   SCIP_VAR* var;
3452 	   int nspcons;
3453 	   int maxnspcons;
3454 	   int nblocks;
3455 	   int maxnblocks;
3456 	   int k;
3457 	   int j;
3458 	
3459 	   assert( success != NULL );
3460 	
3461 	   *success = TRUE;
3462 	   s = str;
3463 	
3464 	   /* skip white space */
3465 	   SCIP_CALL( SCIPskipSpace((char**)&s) );
3466 	
3467 	   if( strncmp(s, "partOrbitope(", 13) == 0 )
3468 	      orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
3469 	   else if( strncmp(s, "packOrbitope(", 13) == 0 )
3470 	      orbitopetype = SCIP_ORBITOPETYPE_PACKING;
3471 	   else
3472 	   {
3473 	      if( strncmp(s, "fullOrbitope(", 13) != 0 )
3474 	      {
3475 	         SCIPerrorMessage("Syntax error - expected \"fullOrbitope(\", \"partOrbitope\" or \"packOrbitope\": %s\n", s);
3476 	         *success = FALSE;
3477 	         return SCIP_OKAY;
3478 	      }
3479 	      orbitopetype = SCIP_ORBITOPETYPE_FULL;
3480 	   }
3481 	   s += 13;
3482 	
3483 	   /* loop through string */
3484 	   nspcons = 0;
3485 	   nblocks = 0;
3486 	   maxnspcons = 10;
3487 	   maxnblocks = 10;
3488 	
3489 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnspcons) );
3490 	
3491 	   j = 0;
3492 	   do
3493 	   {
3494 	      /* parse variable name */
3495 	      SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
3496 	
3497 	      if( var == NULL )
3498 	      {
3499 	         endptr = strchr(endptr, ')');
3500 	
3501 	         if( endptr == NULL || j > 0 )
3502 	         {
3503 	            SCIPerrorMessage("not enough variables.\n");
3504 	            *success = FALSE;
3505 	         }
3506 	
3507 	         break;
3508 	      }
3509 	
3510 	      s = endptr;
3511 	      assert( s != NULL );
3512 	
3513 	      /* skip white space */
3514 	      SCIP_CALL( SCIPskipSpace((char**)&s) );
3515 	
3516 	      /* begin new row if required */
3517 	      if( j == 0 )
3518 	      {
3519 	         ++nspcons;
3520 	
3521 	         if( nspcons > maxnspcons )
3522 	         {
3523 	            maxnspcons = SCIPcalcMemGrowSize(scip, nspcons);
3524 	            SCIP_CALL( SCIPreallocBufferArray(scip, &vars, maxnspcons) );
3525 	            assert( nspcons <= maxnspcons );
3526 	         }
3527 	
3528 	         SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nspcons-1]), nspcons == 1 ? maxnblocks : nblocks) ); /*lint !e866*/
3529 	      }
3530 	
3531 	      /* determine number of columns */
3532 	      if( nspcons == 1 )
3533 	      {
3534 	         nblocks = j+1;
3535 	
3536 	         if( *s == '.' || *s == ')' )
3537 	            SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons-1]), nblocks) ); /*lint !e866*/
3538 	         else if( nblocks > maxnblocks )
3539 	         {
3540 	            maxnblocks = SCIPcalcMemGrowSize(scip, nblocks);
3541 	            SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons-1]), maxnblocks) ); /*lint !e866*/
3542 	            assert( nblocks <= maxnblocks );
3543 	         }
3544 	      }
3545 	      else if( ( j < nblocks-1 ) == ( *s == '.' || *s == ')' ) )
3546 	      {
3547 	         SCIPerrorMessage("variables per row do not match.\n");
3548 	         *success = FALSE;
3549 	         break;
3550 	      }
3551 	
3552 	      vars[nspcons-1][j] = var;
3553 	
3554 	      if( *s == '.' )
3555 	         j = 0;
3556 	      else
3557 	         ++j;
3558 	
3559 	      /* skip ',' or '.' */
3560 	      if( *s == ',' || *s == '.' )
3561 	         ++s;
3562 	   }
3563 	   while( *s != ')' );
3564 	
3565 	   /* to ensure consistency, we disable dynamic propagation and tell SCIP that the orbitope could potentially
3566 	    * interact with other symmetry handling constraints
3567 	    */
3568 	   if( *success )
3569 	      SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, FALSE, TRUE, TRUE, TRUE,
3570 	            initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3571 	
3572 	   for( k = nspcons - 1; k >= 0; --k )
3573 	      SCIPfreeBufferArray(scip, &vars[k]);
3574 	   SCIPfreeBufferArray(scip, &vars);
3575 	
3576 	   return SCIP_OKAY;
3577 	}
3578 	
3579 	
3580 	/** constraint method of constraint handler which returns the variables (if possible) */
3581 	static
3582 	SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
3583 	{  /*lint --e{715}*/
3584 	   SCIP_CONSDATA* consdata;
3585 	
3586 	   assert( cons != NULL );
3587 	   assert( success != NULL );
3588 	   assert( vars != NULL );
3589 	
3590 	   consdata = SCIPconsGetData(cons);
3591 	   assert( consdata != NULL );
3592 	
3593 	   if ( varssize < consdata->nblocks * consdata->nspcons )
3594 	      (*success) = FALSE;
3595 	   else
3596 	   {
3597 	      int cnt = 0;
3598 	      int i;
3599 	      int j;
3600 	
3601 	      for (i = 0; i < consdata->nspcons; ++i)
3602 	      {
3603 	         for (j = 0; j < consdata->nblocks; ++j)
3604 	            vars[cnt++] = consdata->vars[i][j];
3605 	      }
3606 	      (*success) = TRUE;
3607 	   }
3608 	
3609 	   return SCIP_OKAY;
3610 	}
3611 	
3612 	
3613 	/** constraint method of constraint handler which returns the number of variables (if possible) */
3614 	static
3615 	SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
3616 	{  /*lint --e{715}*/
3617 	   SCIP_CONSDATA* consdata;
3618 	
3619 	   assert( cons != NULL );
3620 	
3621 	   consdata = SCIPconsGetData(cons);
3622 	   assert( consdata != NULL );
3623 	
3624 	   (*nvars) = consdata->nblocks * consdata->nspcons;
3625 	   (*success) = TRUE;
3626 	
3627 	   return SCIP_OKAY;
3628 	}
3629 	
3630 	
3631 	/*
3632 	 * constraint specific interface methods
3633 	 */
3634 	
3635 	/** creates the handler for orbitope constraints and includes it in SCIP */
3636 	SCIP_RETCODE SCIPincludeConshdlrOrbitope(
3637 	   SCIP*                 scip                /**< SCIP data structure */
3638 	   )
3639 	{
3640 	   SCIP_CONSHDLRDATA* conshdlrdata;
3641 	   SCIP_CONSHDLR* conshdlr;
3642 	
3643 	   /* create orbitope constraint handler data */
3644 	   SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3645 	
3646 	   /* include constraint handler */
3647 	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
3648 	         CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
3649 	         CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
3650 	         consEnfolpOrbitope, consEnfopsOrbitope, consCheckOrbitope, consLockOrbitope,
3651 	         conshdlrdata) );
3652 	   assert(conshdlr != NULL);
3653 	
3654 	   /* set non-fundamental callbacks via specific setter functions */
3655 	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitope, consCopyOrbitope) );
3656 	   SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbitope) );
3657 	   SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitope) );
3658 	   SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitope) );
3659 	   SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitope) );
3660 	   SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitope) );
3661 	   SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbitope, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3662 	   SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitope) );
3663 	   SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbitope, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3664 	         CONSHDLR_PROP_TIMING) );
3665 	   SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitope) );
3666 	   SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitope, consSepasolOrbitope, CONSHDLR_SEPAFREQ,
3667 	         CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
3668 	   SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitope) );
3669 	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitope) );
3670 	
3671 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbitope",
3672 	         "Strengthen orbitope constraints to packing/partioning orbitopes?",
3673 	         &conshdlrdata->checkpporbitope, TRUE, DEFAULT_PPORBITOPE, NULL, NULL) );
3674 	
3675 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/sepafullorbitope",
3676 	         "Whether we separate inequalities for full orbitopes?",
3677 	         &conshdlrdata->sepafullorbitope, TRUE, DEFAULT_SEPAFULLORBITOPE, NULL, NULL) );
3678 	
3679 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
3680 	         "Whether orbitope constraints should be forced to be copied to sub SCIPs.",
3681 	         &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
3682 	
3683 	   return SCIP_OKAY;
3684 	}
3685 	
3686 	
3687 	/** creates and captures a orbitope constraint
3688 	 *
3689 	 *  @pre If packing/partitioning orbitopes are used, this constraint handler assumes that constraints which enforce
3690 	 *  the packing/partitioning constraints are contained in the problem. It does not implement, e.g., separation and
3691 	 *  propagation of set packing/partitioning constraints, since this would just copy large parts of the code of the
3692 	 *  setppc constraint handler.
3693 	 *
3694 	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3695 	 */
3696 	SCIP_RETCODE SCIPcreateConsOrbitope(
3697 	   SCIP*                 scip,               /**< SCIP data structure */
3698 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
3699 	   const char*           name,               /**< name of constraint */
3700 	   SCIP_VAR***           vars,               /**< matrix of variables on which the symmetry acts */
3701 	   SCIP_ORBITOPETYPE     orbitopetype,       /**< type of orbitope constraint */
3702 	   int                   nspcons,            /**< number of set partitioning/packing constraints  <=> p */
3703 	   int                   nblocks,            /**< number of symmetric variable blocks             <=> q */
3704 	   SCIP_Bool             usedynamicprop,     /**< whether dynamic propagation should be used */
3705 	   SCIP_Bool             mayinteract,        /**< whether symmetries corresponding to orbitope might interact
3706 	                                              *   with symmetries handled by other routines */
3707 	   SCIP_Bool             resolveprop,        /**< should propagation be resolved? */
3708 	   SCIP_Bool             ismodelcons,        /**< whether the orbitope is a model constraint */
3709 	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
3710 	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3711 	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
3712 	                                              *   Usually set to TRUE. */
3713 	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
3714 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
3715 	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
3716 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
3717 	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
3718 	                                              *   Usually set to TRUE. */
3719 	   SCIP_Bool             local,              /**< is constraint only valid locally?
3720 	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3721 	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
3722 	                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
3723 	                                              *   adds coefficients to this constraint. */
3724 	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
3725 	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
3726 	                                              *   are separated as constraints. */
3727 	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
3728 	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3729 	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
3730 	                                              *   if it may be moved to a more global node?
3731 	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3732 	   )
3733 	{
3734 	   SCIP_CONSHDLRDATA* conshdlrdata;
3735 	   SCIP_CONSHDLR* conshdlr;
3736 	   SCIP_CONSDATA* consdata;
3737 	
3738 	   /* find the orbitope constraint handler */
3739 	   conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3740 	   if ( conshdlr == NULL )
3741 	   {
3742 	      SCIPerrorMessage("orbitope constraint handler not found\n");
3743 	      return SCIP_PLUGINNOTFOUND;
3744 	   }
3745 	
3746 	   /* check for consistency */
3747 	   if ( usedynamicprop && mayinteract )
3748 	   {
3749 	      SCIPwarningMessage(scip, "Dynamic propagation is only possible if orbitope does not interact with \
3750 	                          other symmetry handling constraints. Ignore value of <usedynamicprop>.\n");
3751 	   }
3752 	
3753 	   assert( nspcons > 0 );
3754 	   assert( nblocks > 0 );
3755 	
3756 	   /* run some checks */
3757 	#ifndef NDEBUG
3758 	   {
3759 	      SCIP_Real obj;
3760 	      int i;
3761 	      int j;
3762 	      for (i = 0; i < nspcons; ++i)
3763 	      {
3764 	         /* initialize obj to infinity */
3765 	         obj = SCIPinfinity(scip);
3766 	         for (j = 0; j < nblocks; ++j)
3767 	         {
3768 	            SCIP_Bool fixedZero;
3769 	            SCIP_VAR* var;
3770 	
3771 	            var = vars[i][j];
3772 	            assert(var != NULL);
3773 	
3774 	            if ( SCIPvarIsNegated(var) )
3775 	               var = SCIPvarGetNegatedVar(var);
3776 	
3777 	            /* all variables need to be binary */
3778 	            assert( SCIPvarIsBinary(var) );
3779 	
3780 	            /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no
3781 	               problem (but we cannot always check it, e.g., when in the original problem
3782 	               variables were fixed and this problem was copied.) */
3783 	            fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) );
3784 	
3785 	            /* @todo adapt correctness of the following check for sub-scips */
3786 	            if ( SCIPgetSubscipDepth(scip) == 0 )
3787 	            {
3788 	               /* check whether all variables in a row have the same objective */
3789 	               if ( ! fixedZero && SCIPisInfinity(scip, obj) )
3790 	                  obj = SCIPvarGetObj(var);
3791 	               else
3792 	               {
3793 	                  assert( fixedZero || ! SCIPvarIsActive(var) || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) );
3794 	               }
3795 	            }
3796 	         }
3797 	      }
3798 	   }
3799 	#endif
3800 	
3801 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
3802 	   if ( conshdlrdata->checkpporbitope && orbitopetype != SCIP_ORBITOPETYPE_PARTITIONING
3803 	      && orbitopetype != SCIP_ORBITOPETYPE_PACKING )
3804 	   {
3805 	      SCIP_CALL( strengthenOrbitopeConstraint(scip, vars, &nspcons, nblocks, &orbitopetype, mayinteract) );
3806 	   }
3807 	
3808 	   /* create constraint data */
3809 	   SCIP_CALL( consdataCreate(scip, &consdata, vars, nspcons, nblocks, orbitopetype,
3810 	         resolveprop, usedynamicprop && ! mayinteract, ismodelcons, mayinteract) );
3811 	
3812 	   /* create constraint */
3813 	   SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3814 	         local, modifiable, dynamic, removable, stickingatnode) );
3815 	
3816 	   return SCIP_OKAY;
3817 	}
3818 	
3819 	/** creates and captures an orbitope constraint
3820 	 *  in its most basic variant, i. e., with all constraint flags set to their default values
3821 	 *
3822 	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3823 	 */
3824 	SCIP_RETCODE SCIPcreateConsBasicOrbitope(
3825 	   SCIP*                 scip,               /**< SCIP data structure */
3826 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
3827 	   const char*           name,               /**< name of constraint */
3828 	   SCIP_VAR***           vars,               /**< matrix of variables on which the symmetry acts */
3829 	   SCIP_ORBITOPETYPE     orbitopetype,       /**< type of orbitope constraint */
3830 	   int                   nspcons,            /**< number of set partitioning/packing constraints  <=> p */
3831 	   int                   nblocks,            /**< number of symmetric variable blocks             <=> q */
3832 	   SCIP_Bool             usedynamicprop,     /**< whether dynamic propagation should be used */
3833 	   SCIP_Bool             resolveprop,        /**< should propagation be resolved? */
3834 	   SCIP_Bool             ismodelcons,        /**< whether the orbitope is a model constraint */
3835 	   SCIP_Bool             mayinteract         /**< whether symmetries corresponding to orbitope might interact
3836 	                                              *   with symmetries handled by other routines */
3837 	   )
3838 	{
3839 	   SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, usedynamicprop,
3840 	         resolveprop, ismodelcons, mayinteract, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3841 	
3842 	   return SCIP_OKAY;
3843 	}
3844