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_orbisack.c
26   	 * @ingroup DEFPLUGINS_CONS
27   	 * @brief  constraint handler for orbisack constraints
28   	 * @author Christopher Hojny
29   	 * @author Jasper van Doornmalen
30   	 *
31   	 *
32   	 * The type of constraints of this constraint handler is described in cons_orbisack.h.
33   	 *
34   	 * The details of the method implemented here are described in the following papers:
35   	 *
36   	 * Describing Orbitopes by Linear Inequalities and Projection Based Tools@n
37   	 * Andreas Loos,@n
38   	 * PhD thesis, Otto-von-Guericke-Universitaet Magdeburg (2010).
39   	 *
40   	 * This thesis provides a complete linear description of orbisacks and a separation
41   	 * routine for its inequalities.
42   	 *
43   	 * Polytopes Associated with Symmetry Handling@n
44   	 * Christopher Hojny and Marc E. Pfetsch,@n
45   	 * (2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/01/5835.html
46   	 *
47   	 * This paper describes a linear time separation routine for so-called cover inequalities of
48   	 * orbisacks.
49   	 */
50   	
51   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
52   	
53   	#include "blockmemshell/memory.h"
54   	#include "scip/cons_orbisack.h"
55   	#include "scip/cons_orbitope.h"
56   	#include "scip/cons_setppc.h"
57   	#include "scip/pub_cons.h"
58   	#include "scip/pub_message.h"
59   	#include "scip/pub_var.h"
60   	#include "scip/scip.h"
61   	#include "scip/scip_branch.h"
62   	#include "scip/scip_conflict.h"
63   	#include "scip/scip_cons.h"
64   	#include "scip/scip_cut.h"
65   	#include "scip/scip_general.h"
66   	#include "scip/scip_lp.h"
67   	#include "scip/scip_mem.h"
68   	#include "scip/scip_message.h"
69   	#include "scip/scip_numerics.h"
70   	#include "scip/scip_param.h"
71   	#include "scip/scip_sol.h"
72   	#include "scip/scip_var.h"
73   	#include "scip/symmetry.h"
74   	
75   	
76   	/* constraint handler properties */
77   	#define CONSHDLR_NAME          "orbisack"
78   	#define CONSHDLR_DESC          "symmetry breaking constraint handler for orbisacks"
79   	#define CONSHDLR_SEPAPRIORITY    +40100 /**< priority of the constraint handler for separation */
80   	#define CONSHDLR_ENFOPRIORITY  -1005200 /**< priority of the constraint handler for constraint enforcing */
81   	#define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
82   	#define CONSHDLR_SEPAFREQ             5 /**< frequency for separating cuts; zero means to separate only in the root node */
83   	#define CONSHDLR_PROPFREQ             5 /**< frequency for propagating domains; zero means only preprocessing propagation */
84   	#define CONSHDLR_EAGERFREQ           -1 /**< frequency for using all instead of only the useful constraints in separation,
85   	                                         *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
86   	#define CONSHDLR_MAXPREROUNDS        -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
87   	#define CONSHDLR_DELAYSEPA        FALSE /**< should separation method be delayed, if other separators found cuts? */
88   	#define CONSHDLR_DELAYPROP        FALSE /**< should propagation method be delayed, if other propagators found reductions? */
89   	#define CONSHDLR_NEEDSCONS         TRUE /**< should the constraint handler be skipped, if no constraints are available? */
90   	
91   	#define CONSHDLR_PROP_TIMING       SCIP_PROPTIMING_BEFORELP
92   	#define CONSHDLR_PRESOLTIMING      SCIP_PRESOLTIMING_EXHAUSTIVE
93   	
94   	/* default parameters for separation routines: */
95   	#define DEFAULT_ORBISEPARATION               FALSE     /**< whether orbisack inequalities should be separated */
96   	#define DEFAULT_COVERSEPARATION               TRUE     /**< whether cover inequalities should be separated */
97   	
98   	/* default parameters for constraints */
99   	#define DEFAULT_COEFFBOUND               1000000.0     /**< maximum size of coefficients in orbisack inequalities */
100  	#define DEFAULT_PPORBISACK         TRUE /**< whether we allow upgrading to packing/partitioning orbisacks */
101  	#define DEFAULT_FORCECONSCOPY     FALSE /**< whether orbisack constraints should be forced to be copied to sub SCIPs */
102  	
103  	/* Constants to store fixings */
104  	#define FIXED0    1                     /* When a variable is fixed to 0. */
105  	#define FIXED1    2                     /* When a variable is fixed to 1. */
106  	#define UNFIXED   3                     /* When a variable is neither fixed to 0 or to 1. */
107  	
108  	
109  	/*
110  	 * Data structures
111  	 */
112  	
113  	/** constraint handler data */
114  	struct SCIP_ConshdlrData
115  	{
116  	   SCIP_Bool             coverseparation;    /**< whether only cover inequalities should be separated */
117  	   SCIP_Bool             orbiseparation;     /**< whether orbisack as well as cover inequalities should be separated */
118  	   SCIP_Real             coeffbound;         /**< maximum size of coefficients in orbisack inequalities */
119  	   SCIP_Bool             checkpporbisack;    /**< whether we allow upgrading to packing/partitioning orbisacks */
120  	   int                   maxnrows;           /**< maximal number of rows in an orbisack constraint */
121  	   SCIP_Bool             forceconscopy;      /**< whether orbisack constraints should be forced to be copied to sub SCIPs */
122  	};
123  	
124  	/** constraint data for orbisack constraints */
125  	struct SCIP_ConsData
126  	{
127  	   SCIP_VAR**            vars1;              /**< first column of variable matrix */
128  	   SCIP_VAR**            vars2;              /**< second column of variable matrix */
129  	   int                   nrows;              /**< number of rows of variable matrix */
130  	   SCIP_Bool             ismodelcons;        /**< whether the orbisack is a model constraint */
131  	};
132  	
133  	
134  	/*
135  	 * Local methods
136  	 */
137  	
138  	/** frees orbisack constraint data */
139  	static
140  	SCIP_RETCODE consdataFree(
141  	   SCIP*                 scip,               /**< SCIP data structure */
142  	   SCIP_CONSDATA**       consdata            /**< pointer to orbisack constraint data */
143  	   )
144  	{
145  	   int nrows;
146  	   int i;
147  	
148  	   assert( consdata != NULL );
149  	   assert( *consdata != NULL );
150  	
151  	   nrows = (*consdata)->nrows;
152  	
153  	   /* release variables in vars1 and vars2 array */
154  	   for (i = 0; i < nrows; ++i)
155  	   {
156  	      assert( (*consdata)->vars1[i] != NULL );
157  	      SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars1[i] ) );
158  	
159  	      assert( (*consdata)->vars2[i] != NULL );
160  	      SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars2[i] ) );
161  	   }
162  	
163  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars2), nrows);
164  	   SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars1), nrows);
165  	
166  	   SCIPfreeBlockMemory(scip, consdata);
167  	
168  	   return SCIP_OKAY;
169  	}
170  	
171  	
172  	/** creates orbisack constraint data */
173  	static
174  	SCIP_RETCODE consdataCreate(
175  	   SCIP*                 scip,               /**< SCIP data structure */
176  	   SCIP_CONSDATA**       consdata,           /**< pointer to store constraint data */
177  	   SCIP_VAR*const*       vars1,              /**< first column of variable matrix */
178  	   SCIP_VAR*const*       vars2,              /**< second column of variable matrix */
179  	   int                   nrows,              /**< number of rows in variable matrix */
180  	   SCIP_Bool             ismodelcons         /**< whether the orbisack is a model constraint */
181  	   )
182  	{
183  	   int i;
184  	
185  	   assert( consdata != NULL );
186  	
187  	   SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
188  	
189  	   SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars1, vars1, nrows) );
190  	   SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars2, vars2, nrows) );
191  	
192  	#ifndef NDEBUG
193  	   {
194  	      for (i = 0; i < nrows; ++i)
195  	      {
196  	         assert( SCIPvarIsBinary(vars1[i]) );
197  	         assert( SCIPvarIsBinary(vars2[i]) );
198  	      }
199  	   }
200  	#endif
201  	
202  	   (*consdata)->nrows = nrows;
203  	   (*consdata)->ismodelcons = ismodelcons;
204  	
205  	   /* get transformed variables, if we are in the transformed problem */
206  	   if ( SCIPisTransformed(scip) )
207  	   {
208  	      /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_orbisack, since one cannot
209  	       * easily eliminate single variables from an orbisack constraint. */
210  	      for (i = 0; i < nrows; ++i)
211  	      {
212  	         SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars1[i], &(*consdata)->vars1[i]) );
213  	         SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars1[i]) );
214  	
215  	         SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars2[i], &(*consdata)->vars2[i]) );
216  	         SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars2[i]) );
217  	      }
218  	   }
219  	
220  	   /* capture vars in vars1 and vars2 array */
221  	   for (i = 0; i < nrows; ++i)
222  	   {
223  	      SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars1[i] ) );
224  	      SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars2[i] ) );
225  	   }
226  	
227  	   return SCIP_OKAY;
228  	}
229  	
230  	
231  	/** check wether an orbisack is even a packing/partitioning orbisack */
232  	static
233  	SCIP_RETCODE packingUpgrade(
234  	   SCIP*                 scip,               /**< SCIP pointer */
235  	   SCIP_VAR*const*       vars1,              /**< first column of matrix of variables on which the symmetry acts */
236  	   SCIP_VAR*const*       vars2,              /**< variables of second column */
237  	   int                   nrows,              /**< number of rows of orbisack */
238  	   SCIP_Bool*            success,            /**< memory address to store whether constraint can be upgraded */
239  	   SCIP_Bool*            isparttype          /**< memory address to store whether upgraded orbisack is partitioning orbisack */
240  	   )
241  	{
242  	   SCIP_VAR*** vars;
243  	   SCIP_ORBITOPETYPE type;
244  	   int i;
245  	
246  	   assert( scip != NULL );
247  	   assert( vars1 != NULL );
248  	   assert( vars2 != NULL );
249  	   assert( success != NULL );
250  	   assert( isparttype != NULL );
251  	
252  	   *success = FALSE;
253  	   *isparttype = FALSE;
254  	
255  	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) );
256  	   for (i = 0; i < nrows; ++i)
257  	   {
258  	      SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], 2) );
259  	      vars[i][0] = vars1[i];
260  	      vars[i][1] = vars2[i];
261  	   }
262  	
263  	   SCIP_CALL( SCIPisPackingPartitioningOrbitope(scip, vars, nrows, 2, NULL, NULL, &type) );
264  	
265  	   if ( type == SCIP_ORBITOPETYPE_PACKING )
266  	      *success = TRUE;
267  	   else if ( type == SCIP_ORBITOPETYPE_PARTITIONING )
268  	   {
269  	      *success = TRUE;
270  	      *isparttype = TRUE;
271  	   }
272  	
273  	   for (i = nrows - 1; i >= 0; --i)
274  	   {
275  	      SCIPfreeBufferArray(scip, &vars[i]);
276  	   }
277  	   SCIPfreeBufferArray(scip, &vars);
278  	
279  	   return SCIP_OKAY;
280  	}
281  	
282  	
283  	/** generate initial LP cut
284  	 *
285  	 *  We generate the inequality of the orbisack on the elements of the first row, i.e.,
286  	 *  the inequality \f$-x_{1,1} + x_{1,2} \leq 0\f$.
287  	 */
288  	static
289  	SCIP_RETCODE initLP(
290  	   SCIP*                 scip,               /**< SCIP pointer */
291  	   SCIP_CONS*            cons,               /**< constraint */
292  	   SCIP_Bool*            infeasible          /**< pointer to store whether we detected infeasibility */
293  	   )
294  	{
295  	   SCIP_CONSDATA* consdata;
296  	   SCIP_VAR** vars1;
297  	   SCIP_VAR** vars2;
298  	   SCIP_VAR* tmpvars[2];
299  	   SCIP_ROW* row;
300  	
301  	   assert( scip != NULL );
302  	   assert( cons != NULL );
303  	   assert( infeasible != NULL );
304  	
305  	   *infeasible = FALSE;
306  	
307  	   consdata = SCIPconsGetData(cons);
308  	   assert( consdata != 0 );
309  	   assert( consdata->nrows > 0 );
310  	   assert( consdata->vars1 != NULL );
311  	   assert( consdata->vars2 != NULL );
312  	
313  	   vars1 = consdata->vars1;
314  	   vars2 = consdata->vars2;
315  	
316  	   tmpvars[0] = vars1[0];
317  	   tmpvars[1] = vars2[0];
318  	
319  	   SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisack0#0", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
320  	   SCIP_CALL( SCIPaddVarToRow(scip, row, tmpvars[0], -1.0) );
321  	   SCIP_CALL( SCIPaddVarToRow(scip, row, tmpvars[1], 1.0) );
322  	
323  	   SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
324  	#ifdef SCIP_DEBUG
325  	   SCIP_CALL( SCIPprintRow(scip, row, NULL) );
326  	#endif
327  	   SCIP_CALL( SCIPreleaseRow(scip, &row) );
328  	
329  	   return SCIP_OKAY;
330  	}
331  	
332  	
333  	/** add orbisack cover inequality */
334  	static
335  	SCIP_RETCODE addOrbisackCover(
336  	   SCIP*                 scip,               /**< SCIP pointer */
337  	   SCIP_CONS*            cons,               /**< constraint */
338  	   int                   nrows,              /**< number of rows of orbisack */
339  	   SCIP_VAR*const*       vars1,              /**< first column of matrix of variables on which the symmetry acts */
340  	   SCIP_VAR*const*       vars2,              /**< variables of second column */
341  	   SCIP_Real*            coeffs1,            /**< coefficients of the variables of the first column of the inequality to be added */
342  	   SCIP_Real*            coeffs2,            /**< coefficients of the variables of the second column of the inequality to be added */
343  	   SCIP_Real             rhs,                /**< right-hand side of inequality to be added */
344  	   SCIP_Bool*            infeasible          /**< pointer to store whether we detected infeasibility */
345  	   )
346  	{
347  	   SCIP_ROW* row;
348  	   int i;
349  	
350  	   assert( scip != NULL );
351  	   assert( cons != NULL );
352  	   assert( vars1 != NULL );
353  	   assert( vars2 != NULL );
354  	   assert( coeffs1 != NULL );
355  	   assert( coeffs2 != NULL );
356  	   assert( infeasible != NULL );
357  	
358  	   *infeasible = FALSE;
359  	
360  	   SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
361  	   SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
362  	   for (i = 0; i < nrows; ++i)
363  	   {
364  	      SCIP_CALL( SCIPaddVarToRow(scip, row, vars1[i], coeffs1[i]) );
365  	      SCIP_CALL( SCIPaddVarToRow(scip, row, vars2[i], coeffs2[i]) );
366  	   }
367  	   SCIP_CALL( SCIPflushRowExtensions(scip, row) );
368  	
369  	   SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
370  	#ifdef SCIP_DEBUG
371  	   SCIP_CALL( SCIPprintRow(scip, row, NULL) );
372  	#endif
373  	   SCIP_CALL( SCIPreleaseRow(scip, &row) );
374  	
375  	   return SCIP_OKAY;
376  	}
377  	
378  	
379  	/** Separate lifted orbisack cover inequalities
380  	 *
381  	 *  We currently do NOT enter cuts into the pool.
382  	 *
383  	 *  We iterate over the nrows-many cover inequalities which are potentially
384  	 *  maximal w.r.t. their violation.
385  	 */
386  	static
387  	SCIP_RETCODE separateOrbisackCovers(
388  	   SCIP*                 scip,               /**< SCIP pointer */
389  	   SCIP_CONS*            cons,               /**< constraint */
390  	   int                   nrows,              /**< number of rows of orbisack */
391  	   SCIP_VAR*const*       vars1,              /**< first column of matrix of variables on which the symmetry acts */
392  	   SCIP_VAR*const*       vars2,              /**< variables of second column */
393  	   SCIP_Real*            vals1,              /**< LP-solution for those variables in first column */
394  	   SCIP_Real*            vals2,              /**< LP-solution for those variables in second column */
395  	   int*                  ngen,               /**< number of separated covers */
396  	   SCIP_Bool*            infeasible          /**< pointer to store whether we detected infeasibility */
397  	   )
398  	{
399  	   SCIP_Real rhs = 0.0;
400  	   SCIP_Real lhs = 0.0;
401  	   SCIP_Real* coeff1;
402  	   SCIP_Real* coeff2;
403  	   int i;
404  	
405  	   assert( scip != NULL );
406  	   assert( cons != NULL );
407  	   assert( nrows > 0 );
408  	   assert( vars1 != NULL );
409  	   assert( vars2 != NULL );
410  	   assert( infeasible != NULL );
411  	   assert( ngen != NULL );
412  	
413  	   *infeasible = FALSE;
414  	   *ngen = 0;
415  	
416  	   /* allocate memory for inequality coefficients */
417  	   SCIP_CALL( SCIPallocBufferArray(scip, &coeff1, nrows) );
418  	   SCIP_CALL( SCIPallocBufferArray(scip, &coeff2, nrows) );
419  	
420  	   /* initialize coefficient matrix */
421  	   for (i = 0; i < nrows; ++i)
422  	   {
423  	      coeff1[i] = 0.0;
424  	      coeff2[i] = 0.0;
425  	   }
426  	
427  	   /* detect violated covers */
428  	   for (i = 0; i < nrows; ++i)
429  	   {
430  	      /* cover inequality is violated */
431  	      if ( SCIPisEfficacious(scip, -vals1[i] + vals2[i] + lhs - rhs) )
432  	      {
433  	         /* set coefficients for inequality */
434  	         coeff1[i] = -1.0;
435  	         coeff2[i] = 1.0;
436  	
437  	         SCIP_CALL( addOrbisackCover(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) );
438  	         ++(*ngen);
439  	         if ( *infeasible )
440  	            break;
441  	
442  	         /* reset coefficients for next inequality */
443  	         coeff1[i] = 0.0;
444  	         coeff2[i] = 0.0;
445  	      }
446  	
447  	      /* add argmax( 1 - vals[i][0], vals[i][1] ) as coefficient and ensure that both vars1[0] and vars2[0] are
448  	       * contained in the LIFTED cover inequality */
449  	      if ( SCIPisEfficacious(scip, 1.0 - vals1[i] - vals2[i]) )
450  	      {
451  	         coeff1[i] = -1.0;
452  	         lhs = lhs - vals1[i];
453  	
454  	         /* lifting */
455  	         if ( i == 0 )
456  	         {
457  	            coeff2[0] = 1.0;
458  	            lhs += vals2[i];
459  	         }
460  	      }
461  	      else
462  	      {
463  	         coeff2[i] = 1.0;
464  	         rhs += 1.0;
465  	         lhs = lhs + vals2[i];
466  	
467  	         /* lifting */
468  	         if ( i == 0 )
469  	         {
470  	            coeff1[0] = -1.0;
471  	            lhs -= vals1[i];
472  	            rhs -= 1.0;
473  	         }
474  	      }
475  	   }
476  	
477  	   /* free coefficient matrix */
478  	   SCIPfreeBufferArray(scip, &coeff2);
479  	   SCIPfreeBufferArray(scip, &coeff1);
480  	
481  	   return SCIP_OKAY;
482  	}
483  	
484  	
485  	/** add orbisack inequality */
486  	static
487  	SCIP_RETCODE addOrbisackInequality(
488  	   SCIP*                 scip,               /**< SCIP pointer */
489  	   SCIP_CONS*            cons,               /**< constraint */
490  	   int                   nrows,              /**< number of rows of orbisack */
491  	   SCIP_VAR*const*       vars1,              /**< first column of matrix of variables on which the symmetry acts */
492  	   SCIP_VAR*const*       vars2,              /**< variables of second column */
493  	   SCIP_Real*            coeffs1,            /**< first column of coefficient matrix of inequality to be added */
494  	   SCIP_Real*            coeffs2,            /**< second column of coefficient matrix of inequality to be added */
495  	   SCIP_Real             rhs,                /**< right-hand side of inequality to be added */
496  	   SCIP_Bool*            infeasible          /**< pointer to store whether we detected infeasibility */
497  	   )
498  	{
499  	   SCIP_ROW* row;
500  	   int i;
501  	
502  	   assert( scip != NULL );
503  	   assert( cons != NULL );
504  	   assert( vars1 != NULL );
505  	   assert( vars2 != NULL );
506  	   assert( coeffs1 != NULL );
507  	   assert( coeffs2 != NULL );
508  	   assert( infeasible != NULL );
509  	
510  	   *infeasible = FALSE;
511  	
512  	   SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisack", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
513  	   SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
514  	
515  	   for (i = 0; i < nrows; ++i)
516  	   {
517  	      SCIP_CALL( SCIPaddVarToRow(scip, row, vars1[i], coeffs1[i]) );
518  	      SCIP_CALL( SCIPaddVarToRow(scip, row, vars2[i], coeffs2[i]) );
519  	   }
520  	   SCIP_CALL( SCIPflushRowExtensions(scip, row) );
521  	
522  	   SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
523  	#ifdef SCIP_DEBUG
524  	   SCIP_CALL( SCIPprintRow(scip, row, NULL) );
525  	#endif
526  	   SCIP_CALL( SCIPreleaseRow(scip, &row) );
527  	
528  	   return SCIP_OKAY;
529  	}
530  	
531  	
532  	/** separate orbisack inequalities
533  	 *
534  	 *  We currently do NOT enter cuts into the pool.
535  	 *
536  	 *  We stop if we checked for each possible basement row, whether a cut could be added. If the coefficients grow too
537  	 *  large, we start separating cover inequalities.
538  	 *
539  	 *  We implement the separation algorithm for orbisacks described in@n
540  	 *  A. Loos. Describing Orbitopes by Linear Inequalities and Projection Based Tools.
541  	 *  PhD thesis, Otto-von-Guericke-Universitaet Magdeburg, 2010.
542  	 */
543  	static
544  	SCIP_RETCODE separateOrbisack(
545  	   SCIP*                 scip,               /**< SCIP pointer */
546  	   SCIP_CONS*            cons,               /**< constraint */
547  	   int                   nrows,              /**< number of rows of orbisack */
548  	   SCIP_VAR*const*       vars1,              /**< first column of matrix of variables on which the symmetry acts */
549  	   SCIP_VAR*const*       vars2,              /**< variables of second column */
550  	   SCIP_Real*            vals1,              /**< LP-solution for those variables in first column */
551  	   SCIP_Real*            vals2,              /**< LP-solution for those variables in second column */
552  	   SCIP_Bool             coverseparation,    /**< whether we separate cover inequalities */
553  	   SCIP_Real             coeffbound,         /**< maximum size of coefficients in orbisack inequalities */
554  	   int*                  ngen,               /**< pointer to store the number of generated cuts */
555  	   SCIP_Bool*            infeasible          /**< pointer to store whether we detected infeasibility */
556  	   )
557  	{
558  	   SCIP_Real* coeff1;
559  	   SCIP_Real* coeff2;
560  	   SCIP_Real rhs;
561  	   SCIP_Real lhs;
562  	   SCIP_Real valueA;
563  	   SCIP_Real valueB;
564  	   SCIP_Real valueC;
565  	   int basement;
566  	   int i;
567  	
568  	   assert( scip != NULL );
569  	   assert( cons != NULL );
570  	   assert( nrows > 0 );
571  	   assert( vars1 != NULL );
572  	   assert( vars2 != NULL );
573  	   assert( coeffbound >= 0.0 );
574  	   assert( ngen != NULL );
575  	   assert( infeasible != NULL );
576  	
577  	   *infeasible = FALSE;
578  	   *ngen = 0;
579  	
580  	   /* if there is only one row, all cuts are added by initLP */
581  	   if ( nrows < 2 )
582  	      return SCIP_OKAY;
583  	
584  	   /* allocate memory for inequality coefficients */
585  	   SCIP_CALL( SCIPallocBufferArray(scip, &coeff1, nrows) );
586  	   SCIP_CALL( SCIPallocBufferArray(scip, &coeff2, nrows) );
587  	
588  	   /* initialize coefficient matrix row 0 */
589  	   coeff1[0] = -1.0;
590  	   coeff2[0] = 1.0;
591  	   for (i = 2; i < nrows; ++i)
592  	   {
593  	      coeff1[i] = 0.0;
594  	      coeff2[i] = 0.0;
595  	   }
596  	
597  	   /* initialize right-hand side and left-hand side (lhs for row 0) */
598  	   rhs = 0.0;
599  	   lhs = - vals1[0] + vals2[0];
600  	
601  	   /* basement row of orbisack */
602  	   basement = 1;
603  	
604  	   /* update value of left-hand side and coefficients for basement row = 1 */
605  	   lhs += - vals1[1] + vals2[1];
606  	   coeff1[1] = -1.0;
607  	   coeff2[1] = 1.0;
608  	
609  	   /* check whether cut for basement row = 1 is violated */
610  	   if ( SCIPisEfficacious(scip, lhs - rhs) )
611  	   {
612  	      SCIP_CALL( addOrbisackInequality(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) );
613  	      ++(*ngen);
614  	   }
615  	
616  	   /* check whether there exists a cut with basement rows > 1 that is violated */
617  	   while ( basement < nrows - 1 && ! *infeasible )
618  	   {
619  	      valueA = lhs + vals1[basement] - vals1[basement + 1] + vals2[basement + 1] - rhs - 1.0; /*lint !e679, !e834*/
620  	      valueB = lhs - vals2[basement] - vals1[basement + 1] + vals2[basement + 1] - rhs; /*lint !e679, !e834*/
621  	      valueC = 2.0 * lhs + vals1[basement] - vals2[basement] - vals1[basement + 1] + vals2[basement + 1] - 2.0 * rhs; /*lint !e679, !e834*/
622  	
623  	      /* update inequality */
624  	      if ( valueA >= valueB && valueA >= valueC )
625  	      {
626  	         ++rhs;
627  	         coeff1[basement] = 0.0;
628  	         lhs += vals1[basement++];
629  	         coeff1[basement] = -1.0;
630  	         coeff2[basement] = 1.0;
631  	         lhs += - vals1[basement] + vals2[basement];
632  	      }
633  	      else if ( valueB >= valueA && valueB >= valueC )
634  	      {
635  	         coeff2[basement] = 0.0;
636  	         lhs -= vals2[basement++];
637  	         coeff1[basement] = -1.0;
638  	         coeff2[basement] = 1.0;
639  	         lhs += - vals1[basement] + vals2[basement];
640  	      }
641  	      else
642  	      {
643  	         rhs *= 2.0;
644  	         lhs = 0.0;
645  	         for (i = 0; i < basement; ++i)
646  	         {
647  	            coeff1[i] = 2.0 * coeff1[i];
648  	            coeff2[i] = 2.0 * coeff2[i];
649  	            lhs += coeff1[i] * vals1[i] + coeff2[i] * vals2[i];
650  	         }
651  	         coeff1[basement] = -1.0;
652  	         coeff2[basement] = 1.0;
653  	         lhs -= vals1[basement];
654  	         lhs += vals2[basement++];
655  	         coeff1[basement] = -1.0;
656  	         coeff2[basement] = 1.0;
657  	         lhs -= vals1[basement];
658  	         lhs += vals2[basement];
659  	      }
660  	
661  	      /* to avoid numerical troubles, we bound the size of coefficients and rhs */
662  	      if ( rhs > coeffbound || -coeff1[0] > coeffbound || coeff2[0] > coeffbound )
663  	      {
664  	         /* avoid separating cover inequalities twice */
665  	         if ( ! coverseparation )
666  	         {
667  	            int ncuts;
668  	            SCIP_CALL( separateOrbisackCovers(scip, cons, nrows, vars1, vars2, vals1, vals2, &ncuts, infeasible) );
669  	            *ngen += ncuts;
670  	         }
671  	         break;
672  	      }
673  	
674  	      /* if current inequality is violated */
675  	      if ( SCIPisEfficacious(scip, lhs - rhs) )
676  	      {
677  	         SCIP_CALL( addOrbisackInequality(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) );
678  	         ++(*ngen);
679  	      }
680  	   }
681  	
682  	   /* free allocated memory */
683  	   SCIPfreeBufferArray(scip, &coeff2);
684  	   SCIPfreeBufferArray(scip, &coeff1);
685  	
686  	   return SCIP_OKAY;
687  	}
688  	
689  	
690  	/** Determines if a vector with additional fixings could exist that is lexicographically larger than another vector.
691  	 *
692  	 * Given two vectors of variables with local lower and upper bounds, and a set of additional (virtual) fixings.
693  	 * Assuming that the entries of both vectors are equal until entry "start", this function determines if there exists
694  	 * a vector where the left vector is lexicographically larger or equal to the right vector.
695  	 * If a vector exsits, infeasible is set to FALSE, otherwise TRUE.
696  	 */
697  	static
698  	SCIP_RETCODE checkFeasible(
699  	   SCIP*                 scip,               /**< SCIP pointer */
700  	   SCIP_VAR**            vars1,              /**< array of variables in first vector */
701  	   SCIP_VAR**            vars2,              /**< array of variables in second vector */
702  	   int                   nrows,              /**< number of rows */
703  	   int                   start,              /**< at which row to start (assuming previous rows are equal) */
704  	   SCIP_Bool*            infeasible,         /**< pointer to store whether infeasibility is detected in these fixings */
705  	   int*                  infeasiblerow       /**< pointer to store at which row a (0, 1) pattern is found */
706  	   )
707  	{
708  	   SCIP_VAR* var1;
709  	   SCIP_VAR* var2;
710  	   int var1fix;
711  	   int var2fix;
712  	   int i;
713  	
714  	   assert( scip != NULL );
715  	   assert( vars1 != NULL );
716  	   assert( vars2 != NULL );
717  	   assert( infeasible != NULL );
718  	   assert( start >= 0 );
719  	
720  	   *infeasible = FALSE;
721  	
722  	   for (i = start; i < nrows; ++i)
723  	   {
724  	      /* get variables of first and second vector */
725  	      var1 = vars1[i];
726  	      var2 = vars2[i];
727  	
728  	      assert( var1 != NULL );
729  	      assert( var2 != NULL );
730  	
731  	      /* Get virtual fixing of variable in first vector, for var1 */
732  	      if ( SCIPvarGetUbLocal(var1) < 0.5 )
733  	      {
734  	         var1fix = FIXED0;
735  	         assert( SCIPvarGetLbLocal(var1) <= 0.5 );
736  	      }
737  	      else if ( SCIPvarGetLbLocal(var1) > 0.5 )
738  	         var1fix = FIXED1;
739  	      else
740  	         var1fix = UNFIXED;
741  	
742  	      /* Get virtual fixing of variable in second vector, for var2 */
743  	      if ( SCIPvarGetUbLocal(var2) < 0.5 )
744  	      {
745  	         var2fix = FIXED0;
746  	         assert( SCIPvarGetLbLocal(var2) <= 0.5 );
747  	      }
748  	      else if ( SCIPvarGetLbLocal(var2) > 0.5 )
749  	         var2fix = FIXED1;
750  	      else
751  	         var2fix = UNFIXED;
752  	
753  	      /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). In all cases (1, 0) can be constructed. Thus feasible. */
754  	      if ( var1fix != FIXED0 && var2fix != FIXED1 )
755  	         break;
756  	      /* Encounter (0, 1). Infeasible. */
757  	      else if ( var1fix == FIXED0 && var2fix == FIXED1 )
758  	      {
759  	         *infeasible = TRUE;
760  	         *infeasiblerow = i;
761  	         break;
762  	      }
763  	      /* Remaining cases are (0, _), (_, 1), (0, 0) and (1, 1). In all cases: continue. */
764  	   }
765  	
766  	   return SCIP_OKAY;
767  	}
768  	
769  	
770  	/** propagation */
771  	static
772  	SCIP_RETCODE propVariables(
773  	   SCIP*                 scip,               /**< SCIP pointer */
774  	   SCIP_CONS*            cons,               /**< constraint to be propagated */
775  	   SCIP_Bool*            infeasible,         /**< pointer to store whether it was detected that the node is infeasible */
776  	   SCIP_Bool*            found,              /**< pointer to store whether a new propagation could be found */
777  	   int*                  ngen                /**< pointer to store the number of generated bound strengthenings */
778  	   )
779  	{
780  	   SCIP_CONSDATA* consdata;
781  	   SCIP_VAR** vars1;
782  	   SCIP_VAR** vars2;
783  	   SCIP_VAR* var1;
784  	   SCIP_VAR* var2;
785  	   int var1fix;
786  	   int var2fix;
787  	   SCIP_Bool tightened;
788  	   SCIP_Bool peekinfeasible;
789  	   int peekinfeasiblerow;
790  	   int nrows;
791  	   int i;
792  	
793  	   assert( scip != NULL );
794  	   assert( cons != NULL );
795  	   assert( infeasible != NULL );
796  	   assert( ngen != NULL );
797  	   assert( found != NULL );
798  	
799  	   SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons));
800  	
801  	   *ngen = 0;
802  	   *infeasible = FALSE;
803  	   *found = FALSE;
804  	
805  	   /* get data of constraint */
806  	   consdata = SCIPconsGetData(cons);
807  	   assert( consdata != NULL );
808  	   assert( consdata->vars1 != NULL );
809  	   assert( consdata->vars2 != NULL );
810  	   assert( consdata->nrows > 0 );
811  	
812  	   nrows = consdata->nrows;
813  	   vars1 = consdata->vars1;
814  	   vars2 = consdata->vars2;
815  	
816  	   /* loop through all variables */
817  	   for (i = 0; i < nrows; ++i)
818  	   {
819  	      /* get variables of first and second column */
820  	      var1 = vars1[i];
821  	      var2 = vars2[i];
822  	      assert( var1 != NULL );
823  	      assert( var2 != NULL );
824  	
825  	      /* Get the fixing status of the left column variable var1 */
826  	      if ( SCIPvarGetUbLocal(var1) < 0.5 )
827  	      {
828  	         var1fix = FIXED0;
829  	         assert( SCIPvarGetLbLocal(var1) <= 0.5 );
830  	      }
831  	      else if ( SCIPvarGetLbLocal(var1) > 0.5 )
832  	         var1fix = FIXED1;
833  	      else
834  	         var1fix = UNFIXED;
835  	
836  	      /* Get the fixing status of the right column variable var2 */
837  	      if ( SCIPvarGetUbLocal(var2) < 0.5 )
838  	      {
839  	         var2fix = FIXED0;
840  	         assert( SCIPvarGetLbLocal(var2) <= 0.5 );
841  	      }
842  	      else if ( SCIPvarGetLbLocal(var2) > 0.5 )
843  	         var2fix = FIXED1;
844  	      else
845  	         var2fix = UNFIXED;
846  	
847  	      /* Encounter one of (1, 0). All above rows are constant. This is a feasible situation. Stop. */
848  	      if ( var1fix == FIXED1 && var2fix == FIXED0 )
849  	      {
850  	         assert( SCIPvarGetLbLocal(var1) > 0.5 );
851  	         assert( SCIPvarGetUbLocal(var2) < 0.5 );
852  	
853  	         SCIPdebugMsg(scip, "Row %d is (1, 0)\n", i);
854  	         break;
855  	      }
856  	      /* Encounter one of (_, _), (_, 0), (1, _). Check if a constant row is possible, otherwise fix to (1, 0). */
857  	      if ( var1fix != FIXED0 && var2fix != FIXED1 )
858  	      {
859  	         assert( SCIPvarGetUbLocal(var1) > 0.5 );
860  	         assert( SCIPvarGetLbLocal(var2) < 0.5 );
861  	
862  	         SCIPdebugMsg(scip, "Row %d is (_, _), (_, 0) or (1, _).\n", i);
863  	
864  	         SCIP_CALL( checkFeasible(scip, vars1, vars2, nrows, i + 1, &peekinfeasible, &peekinfeasiblerow) );
865  	
866  	         if ( peekinfeasible )
867  	         {
868  	            /* If row i is constant, then we end up in an infeasible solution. Hence, row i must be (1, 0). */
869  	            SCIPdebugMsg(scip, "Making row %d constant is infeasible. Fix to (1, 0).\n", i);
870  	
871  	            assert( peekinfeasiblerow > i );
872  	            assert( peekinfeasiblerow < nrows );
873  	
874  	            if ( var1fix != FIXED1 )
875  	            {
876  	               /* Fix variable in first column to 1 */
877  	               SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i + nrows * peekinfeasiblerow, FALSE, infeasible,
878  	                     &tightened) ); /*lint !e713*/
879  	               assert( ! *infeasible );
880  	
881  	               *found = *found || tightened;
882  	               if ( tightened )
883  	                  ++(*ngen);
884  	            }
885  	
886  	            if ( var2fix != FIXED0 )
887  	            {
888  	               /* Fix variable in second column to 0 */
889  	               SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i + nrows * peekinfeasiblerow, FALSE, infeasible,
890  	                     &tightened) ); /*lint !e713*/
891  	               assert( ! *infeasible );
892  	
893  	               *found = *found || tightened;
894  	               if ( tightened )
895  	                  ++(*ngen);
896  	            }
897  	         }
898  	
899  	         /* In all cases, we could make this row (1, 0), so it is feasible. Stop. */
900  	         break;
901  	      }
902  	      /* Encounter (0, 1): if variable in first column is fixed to 0 and variable in second column is fixed to 1 */
903  	      else if ( var1fix == FIXED0 && var2fix == FIXED1 )
904  	      {
905  	         assert( SCIPvarGetUbLocal(var1) < 0.5 );
906  	         assert( SCIPvarGetLbLocal(var2) > 0.5 );
907  	
908  	         SCIPdebugMsg(scip, "Row %d is (0, 1). Infeasible!\n", i);
909  	
910  	         /* Mark solution as infeasible. */
911  	         *infeasible = TRUE;
912  	
913  	         /* Perform conflict analysis */
914  	         if ( SCIPisConflictAnalysisApplicable(scip) )
915  	         {
916  	            SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
917  	
918  	            /* Mark all variables from row i and above as part of the conflict */
919  	            while (i >= 0)
920  	            {
921  	               SCIP_CALL( SCIPaddConflictBinvar(scip, vars1[i]) );
922  	               SCIP_CALL( SCIPaddConflictBinvar(scip, vars2[i--]) ); /*lint !e850*/
923  	            }
924  	
925  	            SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
926  	         }
927  	
928  	         break;
929  	      }
930  	      /* Encounter (0, _): Fix second part to 0 */
931  	      else if ( var1fix == FIXED0 && var2fix != FIXED0 )
932  	      {
933  	         assert( SCIPvarGetUbLocal(var1) < 0.5 );
934  	         assert( SCIPvarGetLbLocal(var2) < 0.5 );
935  	         assert( SCIPvarGetUbLocal(var2) > 0.5 );
936  	
937  	         SCIPdebugMsg(scip, "Row %d is (0, _). Fixing to (0, 0).\n", i);
938  	
939  	         SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
940  	         assert( ! *infeasible );
941  	
942  	         *found = *found || tightened;
943  	         if ( tightened )
944  	            ++(*ngen);
945  	      }
946  	      /* Encounter (_, 1): fix first part to 1 */
947  	      else if ( var1fix != FIXED1 && var2fix == FIXED1 )
948  	      {
949  	         assert( SCIPvarGetLbLocal(var1) < 0.5 );
950  	         assert( SCIPvarGetUbLocal(var1) > 0.5 );
951  	         assert( SCIPvarGetLbLocal(var2) > 0.5 );
952  	
953  	         SCIPdebugMsg(scip, "Row %d is (_, 1). Fixing to (1, 1).\n", i);
954  	
955  	         SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
956  	         assert( ! *infeasible );
957  	
958  	         *found = *found || tightened;
959  	         if ( tightened )
960  	            ++(*ngen);
961  	      }
962  	      /* Remaining cases are (0, 0) and (1, 1). In these cases we can continue! */
963  	   }
964  	
965  	   SCIPdebugMsg(scip, "No further fixings possible. Stopping at row %d\n", i);
966  	   return SCIP_OKAY;
967  	}
968  	
969  	
970  	/** separate orbisack and cover inequalities */
971  	static
972  	SCIP_RETCODE separateInequalities(
973  	   SCIP*                 scip,               /**< pointer to scip */
974  	   SCIP_RESULT*          result,             /**< pointer to store the result of separation */
975  	   SCIP_CONS*            cons,               /**< constraint */
976  	   int                   nrows,              /**< number of rows of orbisack */
977  	   SCIP_VAR*const*       vars1,              /**< first column of matrix of variables on which the symmetry acts */
978  	   SCIP_VAR*const*       vars2,              /**< variables of second column */
979  	   SCIP_Real*            vals1,              /**< LP-solution for those variables in first column */
980  	   SCIP_Real*            vals2               /**< LP-solution for those variables in second column */
981  	   )
982  	{
983  	   SCIP_CONSHDLRDATA* conshdlrdata;
984  	   SCIP_Bool infeasible = FALSE;
985  	   int ngen1 = 0;
986  	   int ngen2 = 0;
987  	
988  	   assert( scip != NULL );
989  	   assert( result != NULL );
990  	   assert( cons != NULL );
991  	   assert( vars1 != NULL );
992  	   assert( vars2 != NULL );
993  	   assert( vals1 != NULL );
994  	   assert( vals2 != NULL );
995  	
996  	   conshdlrdata = SCIPconshdlrGetData(SCIPconsGetHdlr(cons));
997  	   assert( conshdlrdata != NULL );
998  	
999  	   if ( conshdlrdata->orbiseparation )
1000 	   {
1001 	      SCIP_CALL( separateOrbisack(scip, cons, nrows, vars1, vars2, vals1, vals2, FALSE, conshdlrdata->coeffbound, &ngen1, &infeasible) );
1002 	   }
1003 	
1004 	   if ( ! infeasible && conshdlrdata->coverseparation )
1005 	   {
1006 	      SCIP_CALL( separateOrbisackCovers(scip, cons, nrows, vars1, vars2, vals1, vals2, &ngen2, &infeasible) );
1007 	   }
1008 	
1009 	   if ( infeasible )
1010 	   {
1011 	      *result = SCIP_CUTOFF;
1012 	      return SCIP_OKAY;
1013 	   }
1014 	
1015 	   if ( ngen1 + ngen2 > 0 )
1016 	      *result = SCIP_SEPARATED;
1017 	
1018 	   return SCIP_OKAY;
1019 	}
1020 	
1021 	
1022 	/*--------------------------------------------------------------------------------------------
1023 	 *--------------------------------- SCIP functions -------------------------------------------
1024 	 *--------------------------------------------------------------------------------------------*/
1025 	
1026 	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1027 	static
1028 	SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbisack)
1029 	{  /*lint --e{715}*/
1030 	   assert(scip != NULL);
1031 	   assert(conshdlr != NULL);
1032 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1033 	
1034 	   /* call inclusion method of constraint handler */
1035 	   SCIP_CALL( SCIPincludeConshdlrOrbisack(scip) );
1036 	
1037 	   *valid = TRUE;
1038 	
1039 	   return SCIP_OKAY;
1040 	}
1041 	
1042 	/** frees specific constraint data */
1043 	static
1044 	SCIP_DECL_CONSDELETE(consDeleteOrbisack)
1045 	{  /*lint --e{715}*/
1046 	   assert( scip != 0 );
1047 	   assert( conshdlr != 0 );
1048 	   assert( consdata != 0 );
1049 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1050 	
1051 	   SCIP_CALL( consdataFree(scip, consdata) );
1052 	
1053 	   return SCIP_OKAY;
1054 	}
1055 	
1056 	
1057 	/** frees constraint handler */
1058 	static
1059 	SCIP_DECL_CONSFREE(consFreeOrbisack)
1060 	{   /*lint --e{715}*/
1061 	   SCIP_CONSHDLRDATA* conshdlrdata;
1062 	
1063 	   assert( scip != 0 );
1064 	   assert( conshdlr != 0 );
1065 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1066 	
1067 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
1068 	   assert( conshdlrdata != NULL );
1069 	
1070 	   SCIPfreeBlockMemory(scip, &conshdlrdata);
1071 	
1072 	   return SCIP_OKAY;
1073 	}
1074 	
1075 	
1076 	/** transforms constraint data into data belonging to the transformed problem */
1077 	static
1078 	SCIP_DECL_CONSTRANS(consTransOrbisack)
1079 	{
1080 	   SCIP_CONSDATA* sourcedata;
1081 	   SCIP_CONSDATA* consdata = NULL;
1082 	
1083 	   assert( scip != NULL );
1084 	   assert( conshdlr != NULL );
1085 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1086 	   assert( sourcecons != NULL );
1087 	   assert( targetcons != NULL );
1088 	
1089 	   SCIPdebugMsg(scip, "Transforming constraint.\n");
1090 	
1091 	   /* get data of original constraint */
1092 	   sourcedata = SCIPconsGetData(sourcecons);
1093 	
1094 	   /* create constraint data */
1095 	   SCIP_CALL( consdataCreate(scip, &consdata, sourcedata->vars1, sourcedata->vars2,
1096 	         sourcedata->nrows, sourcedata->ismodelcons) );
1097 	
1098 	   /* create transformed constraint */
1099 	   SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1100 	         SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1101 	         SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1102 	         SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1103 	         SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1104 	         SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1105 	
1106 	   return SCIP_OKAY;
1107 	}
1108 	
1109 	
1110 	/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1111 	static
1112 	SCIP_DECL_CONSINITLP(consInitlpOrbisack)
1113 	{
1114 	   int c;
1115 	
1116 	   assert( infeasible != NULL );
1117 	   *infeasible = FALSE;
1118 	
1119 	   assert( scip != 0 );
1120 	   assert( conshdlr != 0 );
1121 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1122 	
1123 	   /* loop through constraints */
1124 	   for (c = 0; c < nconss; ++c)
1125 	   {
1126 	      assert( conss[c] != 0 );
1127 	
1128 	      SCIPdebugMsg(scip, "Generating initial orbisack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1129 	
1130 	      SCIP_CALL( initLP(scip, conss[c], infeasible) );
1131 	      if ( *infeasible )
1132 	         break;
1133 	
1134 	      SCIPdebugMsg(scip, "Generated initial orbisack cut.\n");
1135 	   }
1136 	
1137 	   return SCIP_OKAY;
1138 	}
1139 	
1140 	
1141 	/** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1142 	static
1143 	SCIP_DECL_CONSINITSOL(consInitsolOrbisack)
1144 	{
1145 	   SCIP_CONSHDLRDATA* conshdlrdata;
1146 	   int c;
1147 	
1148 	   assert( scip != NULL );
1149 	   assert( conshdlr != NULL );
1150 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1151 	
1152 	   /* determine maximum number of rows in an orbisack constraint */
1153 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
1154 	   assert( conshdlrdata != NULL );
1155 	
1156 	   conshdlrdata->maxnrows = 0;
1157 	
1158 	   /* loop through constraints */
1159 	   for (c = 0; c < nconss; ++c)
1160 	   {
1161 	      SCIP_CONSDATA* consdata;
1162 	
1163 	      assert( conss[c] != NULL );
1164 	
1165 	      consdata = SCIPconsGetData(conss[c]);
1166 	      assert( consdata != NULL );
1167 	
1168 	      /* update conshdlrdata if necessary */
1169 	      if ( consdata->nrows > conshdlrdata->maxnrows )
1170 	         conshdlrdata->maxnrows = consdata->nrows;
1171 	   }
1172 	
1173 	   return SCIP_OKAY;
1174 	}
1175 	
1176 	
1177 	/** separation method of constraint handler for LP solution */
1178 	static
1179 	SCIP_DECL_CONSSEPALP(consSepalpOrbisack)
1180 	{  /*lint --e{715}*/
1181 	   SCIP_CONSDATA* consdata;
1182 	   SCIP_Real* vals1;
1183 	   SCIP_Real* vals2;
1184 	   int c;
1185 	
1186 	   assert( scip != NULL );
1187 	   assert( conshdlr != NULL );
1188 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1189 	   assert( result != NULL );
1190 	
1191 	   SCIPdebugMsg(scip, "Separation method for orbisack constraints.\n");
1192 	
1193 	   *result = SCIP_DIDNOTRUN;
1194 	
1195 	   /* if solution is not integer */
1196 	   if ( SCIPgetNLPBranchCands(scip) > 0 )
1197 	   {
1198 	      SCIP_CONSHDLRDATA* conshdlrdata;
1199 	      int nvals;
1200 	
1201 	      *result = SCIP_DIDNOTFIND;
1202 	
1203 	      conshdlrdata = SCIPconshdlrGetData(conshdlr);
1204 	      assert( conshdlrdata != NULL );
1205 	
1206 	      nvals = conshdlrdata->maxnrows;
1207 	      assert( nvals > 0 );
1208 	
1209 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1210 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1211 	
1212 	      /* loop through constraints */
1213 	      for (c = 0; c < nconss; ++c)
1214 	      {
1215 	         /* get data of constraint */
1216 	         assert( conss[c] != NULL );
1217 	         consdata = SCIPconsGetData(conss[c]);
1218 	
1219 	         /* get solution */
1220 	         SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) );
1221 	         SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) );
1222 	
1223 	         SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1224 	
1225 	         SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) );
1226 	
1227 	         if ( *result == SCIP_CUTOFF )
1228 	            break;
1229 	      }
1230 	
1231 	      SCIPfreeBufferArray(scip, &vals2);
1232 	      SCIPfreeBufferArray(scip, &vals1);
1233 	   }
1234 	
1235 	   return SCIP_OKAY;
1236 	}
1237 	
1238 	
1239 	/** separation method of constraint handler for arbitrary primal solution */
1240 	static
1241 	SCIP_DECL_CONSSEPASOL(consSepasolOrbisack)
1242 	{  /*lint --e{715}*/
1243 	   SCIP_CONSDATA* consdata;
1244 	   SCIP_Real* vals1;
1245 	   SCIP_Real* vals2;
1246 	   int c;
1247 	
1248 	   assert( scip != NULL );
1249 	   assert( conshdlr != NULL );
1250 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1251 	   assert( result != NULL );
1252 	
1253 	   SCIPdebugMsg(scip, "Separation method for orbisack constraints\n");
1254 	
1255 	   *result = SCIP_DIDNOTFIND;
1256 	
1257 	   if ( nconss > 0 )
1258 	   {
1259 	      SCIP_CONSHDLRDATA* conshdlrdata;
1260 	      int nvals;
1261 	
1262 	      conshdlrdata = SCIPconshdlrGetData(conshdlr);
1263 	      assert( conshdlrdata != NULL );
1264 	
1265 	      nvals = conshdlrdata->maxnrows;
1266 	      assert( nvals > 0 );
1267 	
1268 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1269 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1270 	
1271 	      /* loop through constraints */
1272 	      for (c = 0; c < nconss; ++c)
1273 	      {
1274 	         /* get data of constraint */
1275 	         assert( conss[c] != NULL );
1276 	         consdata = SCIPconsGetData(conss[c]);
1277 	
1278 	         /* get solution */
1279 	         assert( consdata->nrows <= nvals );
1280 	         SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) );
1281 	         SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) );
1282 	
1283 	         SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1284 	
1285 	         SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) );
1286 	         if ( *result == SCIP_CUTOFF )
1287 	            break;
1288 	      }
1289 	
1290 	      SCIPfreeBufferArray(scip, &vals2);
1291 	      SCIPfreeBufferArray(scip, &vals1);
1292 	   }
1293 	
1294 	   return SCIP_OKAY;
1295 	}
1296 	
1297 	
1298 	/** constraint enforcing method of constraint handler for LP solutions
1299 	 *
1300 	 *  @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
1301 	 */
1302 	static
1303 	SCIP_DECL_CONSENFOLP(consEnfolpOrbisack)
1304 	{  /*lint --e{715}*/
1305 	   SCIP_CONSDATA* consdata;
1306 	   SCIP_Bool infeasible = FALSE;
1307 	   SCIP_Real* vals1;
1308 	   SCIP_Real* vals2;
1309 	   int ngen = 0;
1310 	   int c;
1311 	
1312 	   assert( scip != 0 );
1313 	   assert( conshdlr != 0 );
1314 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1315 	   assert( result != 0 );
1316 	
1317 	   SCIPdebugMsg(scip, "Enfolp method for orbisack constraints\n");
1318 	
1319 	   /* we have a negative priority, so we should come after the integrality conshdlr. */
1320 	   assert( SCIPgetNLPBranchCands(scip) == 0 );
1321 	
1322 	   *result = SCIP_FEASIBLE;
1323 	
1324 	   if ( nconss > 0 )
1325 	   {
1326 	      SCIP_CONSHDLRDATA* conshdlrdata;
1327 	      int nvals;
1328 	
1329 	      conshdlrdata = SCIPconshdlrGetData(conshdlr);
1330 	      assert( conshdlrdata != NULL );
1331 	
1332 	      nvals = conshdlrdata->maxnrows;
1333 	      assert( nvals > 0 );
1334 	
1335 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1336 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1337 	
1338 	      /* loop through constraints */
1339 	      for (c = 0; c < nconss; ++c)
1340 	      {
1341 	         /* get data of constraint */
1342 	         assert( conss[c] != 0 );
1343 	         consdata = SCIPconsGetData(conss[c]);
1344 	         assert( consdata != NULL );
1345 	
1346 	         /* do not enforce non-model constraints */
1347 	         if ( !consdata->ismodelcons )
1348 	            continue;
1349 	
1350 	         /* get solution */
1351 	         assert( consdata->nrows <= nvals );
1352 	         SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) );
1353 	         SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) );
1354 	
1355 	         SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1356 	
1357 	         /* Separate only cover inequalities to ensure that enforcing works correctly. */
1358 	         /* Otherwise, it may happen that infeasible solutions cannot be detected, since */
1359 	         /* we bound the size of the coefficients for the orbisack inequalities. */
1360 	         SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) );
1361 	
1362 	         if ( infeasible )
1363 	         {
1364 	            *result = SCIP_CUTOFF;
1365 	            break;
1366 	         }
1367 	
1368 	         SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen);
1369 	
1370 	         if ( ngen > 0 )
1371 	            *result = SCIP_SEPARATED;
1372 	      }
1373 	
1374 	      SCIPfreeBufferArray(scip, &vals2);
1375 	      SCIPfreeBufferArray(scip, &vals1);
1376 	   }
1377 	
1378 	   return SCIP_OKAY;
1379 	}
1380 	
1381 	
1382 	/** constraint enforcing method of constraint handler for pseudo solutions */
1383 	static
1384 	SCIP_DECL_CONSENFOPS(consEnfopsOrbisack)
1385 	{  /*lint --e{715}*/
1386 	   SCIP_Bool feasible = TRUE;
1387 	   SCIP_CONSDATA* consdata;
1388 	   int c;
1389 	
1390 	   assert( scip != NULL );
1391 	   assert( conshdlr != NULL );
1392 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1393 	   assert( result != NULL );
1394 	
1395 	   SCIPdebugMsg(scip, "Enforcing method for orbisack constraints (pseudo solutions) ...\n");
1396 	
1397 	   *result = SCIP_FEASIBLE;
1398 	
1399 	   if ( objinfeasible || solinfeasible )
1400 	      return SCIP_OKAY;
1401 	
1402 	   /* loop through constraints */
1403 	   for (c = 0; c < nconss; ++c)
1404 	   {
1405 	      /* get data of constraint */
1406 	      assert( conss[c] != NULL );
1407 	      consdata = SCIPconsGetData(conss[c]);
1408 	      assert( consdata != NULL);
1409 	      assert( consdata->nrows > 0 );
1410 	      assert( consdata->vars1 != NULL );
1411 	      assert( consdata->vars2 != NULL );
1412 	
1413 	      /* do not enforce non-model constraints */
1414 	      if ( !consdata->ismodelcons )
1415 	         continue;
1416 	
1417 	      SCIP_CALL( SCIPcheckSolutionOrbisack(scip, NULL, consdata->vars1, consdata->vars2, consdata->nrows, FALSE, &feasible) );
1418 	
1419 	      if ( ! feasible )
1420 	      {
1421 	         *result = SCIP_INFEASIBLE;
1422 	         break;
1423 	      }
1424 	   }
1425 	
1426 	   return SCIP_OKAY;
1427 	}
1428 	
1429 	
1430 	/** constraint enforcing method of constraint handler for relaxation solutions */
1431 	static
1432 	SCIP_DECL_CONSENFORELAX(consEnforelaxOrbisack)
1433 	{  /*lint --e{715}*/
1434 	   SCIP_CONSDATA* consdata;
1435 	   SCIP_Bool infeasible = FALSE;
1436 	   SCIP_Real* vals1;
1437 	   SCIP_Real* vals2;
1438 	   int ngen = 0;
1439 	   int c;
1440 	
1441 	   assert( scip != 0 );
1442 	   assert( conshdlr != 0 );
1443 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1444 	   assert( result != 0 );
1445 	
1446 	   SCIPdebugMsg(scip, "Enforelax method for orbisack constraints.\n");
1447 	
1448 	   /* we have a negative priority, so we should come after the integrality conshdlr. */
1449 	   assert( SCIPgetNLPBranchCands(scip) == 0 );
1450 	
1451 	   *result = SCIP_FEASIBLE;
1452 	
1453 	   if ( nconss > 0 )
1454 	   {
1455 	      SCIP_CONSHDLRDATA* conshdlrdata;
1456 	      int nvals;
1457 	
1458 	      conshdlrdata = SCIPconshdlrGetData(conshdlr);
1459 	      assert( conshdlrdata != NULL );
1460 	
1461 	      nvals = conshdlrdata->maxnrows;
1462 	      assert( nvals > 0 );
1463 	
1464 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1465 	      SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1466 	
1467 	      /* loop through constraints */
1468 	      for (c = 0; c < nconss; ++c)
1469 	      {
1470 	         /* get data of constraint */
1471 	         assert( conss[c] != 0 );
1472 	         consdata = SCIPconsGetData(conss[c]);
1473 	         assert( consdata != NULL );
1474 	
1475 	         /* do not enforce non-model constraints */
1476 	         if ( !consdata->ismodelcons )
1477 	            continue;
1478 	
1479 	         /* get solution */
1480 	         assert( consdata->nrows <= nvals );
1481 	         SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) );
1482 	         SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) );
1483 	
1484 	         SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1485 	
1486 	         /* Separate only cover inequalities to ensure that enforcing works correctly. */
1487 	         /* Otherwise, it may happen that infeasible solutions cannot be detected, since */
1488 	         /* we bound the size of the coefficients for the orbisack inequalities. */
1489 	         SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) );
1490 	
1491 	         if ( infeasible )
1492 	         {
1493 	            *result = SCIP_CUTOFF;
1494 	            break;
1495 	         }
1496 	
1497 	         SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen);
1498 	
1499 	         if ( ngen > 0 )
1500 	            *result = SCIP_SEPARATED;
1501 	      }
1502 	
1503 	      SCIPfreeBufferArray(scip, &vals2);
1504 	      SCIPfreeBufferArray(scip, &vals1);
1505 	   }
1506 	
1507 	   return SCIP_OKAY;
1508 	}
1509 	
1510 	
1511 	/** feasibility check method of constraint handler for integral solutions */
1512 	static
1513 	SCIP_DECL_CONSCHECK(consCheckOrbisack)
1514 	{  /*lint --e{715}*/
1515 	   SCIP_Bool feasible = TRUE;
1516 	   SCIP_CONSDATA* consdata;
1517 	   int c;
1518 	
1519 	   assert( scip != NULL );
1520 	   assert( conshdlr != NULL );
1521 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1522 	   assert( result != NULL );
1523 	
1524 	   *result = SCIP_FEASIBLE;
1525 	
1526 	   /* loop through constraints */
1527 	   for (c = 0; c < nconss; ++c)
1528 	   {
1529 	      /* get data of constraint */
1530 	      assert( conss[c] != NULL );
1531 	      consdata = SCIPconsGetData(conss[c]);
1532 	      assert( consdata != NULL);
1533 	      assert( consdata->nrows > 0 );
1534 	      assert( consdata->vars1 != NULL );
1535 	      assert( consdata->vars2 != NULL );
1536 	
1537 	      SCIPdebugMsg(scip, "Check method for orbisack constraint <%s> (%d rows) ...\n", SCIPconsGetName(conss[c]), consdata->nrows);
1538 	
1539 	      /* do not check non-model constraints */
1540 	      if ( !consdata->ismodelcons )
1541 	         continue;
1542 	
1543 	      SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, consdata->vars1, consdata->vars2, consdata->nrows, printreason, &feasible) );
1544 	
1545 	      if ( ! feasible )
1546 	      {
1547 	         *result = SCIP_INFEASIBLE;
1548 	         SCIPdebugMsg(scip, "Solution is feasible.\n");
1549 	         break;
1550 	      }
1551 	   }
1552 	
1553 	   if ( feasible )
1554 	      SCIPdebugMsg(scip, "Solution is feasible.\n");
1555 	
1556 	   return SCIP_OKAY;
1557 	}
1558 	
1559 	
1560 	/** domain propagation method of constraint handler */
1561 	static
1562 	SCIP_DECL_CONSPROP(consPropOrbisack)
1563 	{  /*lint --e{715}*/
1564 	   int c;
1565 	
1566 	   assert( scip != NULL );
1567 	   assert( conshdlr != NULL );
1568 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1569 	   assert( result != NULL );
1570 	
1571 	   *result = SCIP_DIDNOTRUN;
1572 	
1573 	   SCIPdebugMsg(scip, "Propagation method of orbisack constraint handler.\n");
1574 	
1575 	   /* loop through constraints */
1576 	   for (c = 0; c < nconss; ++c)
1577 	   {
1578 	      SCIP_Bool infeasible = FALSE;
1579 	      SCIP_Bool found = FALSE;
1580 	      int ngen = 0;
1581 	
1582 	      assert( conss[c] != NULL );
1583 	
1584 	      SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &ngen) );
1585 	
1586 	      if ( infeasible )
1587 	      {
1588 	         *result = SCIP_CUTOFF;
1589 	         return SCIP_OKAY;
1590 	      }
1591 	
1592 	      if ( found )
1593 	         *result = SCIP_REDUCEDDOM;
1594 	   }
1595 	
1596 	   return SCIP_OKAY;
1597 	}
1598 	
1599 	
1600 	/** presolving method of constraint handler */
1601 	static
1602 	SCIP_DECL_CONSPRESOL(consPresolOrbisack)
1603 	{  /*lint --e{715}*/
1604 	   int c;
1605 	   int ngen = 0;
1606 	
1607 	   assert( scip != NULL );
1608 	   assert( conshdlr != NULL );
1609 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1610 	   assert( result != NULL );
1611 	
1612 	   SCIPdebugMsg(scip, "Presolving method of orbisack constraint handler. Propagating orbisack inequalities.\n");
1613 	
1614 	   *result = SCIP_DIDNOTFIND;
1615 	
1616 	   /* loop through constraints */
1617 	   for (c = 0; c < nconss; ++c)
1618 	   {
1619 	      SCIP_Bool infeasible = FALSE;
1620 	      SCIP_Bool found = FALSE;
1621 	      int curngen = 0;
1622 	
1623 	      assert( conss[c] != NULL );
1624 	      SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &curngen) );
1625 	
1626 	      if ( infeasible )
1627 	      {
1628 	         *result = SCIP_CUTOFF;
1629 	         break;
1630 	      }
1631 	
1632 	      ngen += curngen;
1633 	   }
1634 	
1635 	   if ( ngen > 0 )
1636 	   {
1637 	      *nfixedvars += ngen;
1638 	      *result = SCIP_SUCCESS;
1639 	   }
1640 	
1641 	   return SCIP_OKAY;
1642 	}
1643 	
1644 	
1645 	/** Propagation resolution for conflict analysis */
1646 	static
1647 	SCIP_DECL_CONSRESPROP(consRespropOrbisack)
1648 	{  /*lint --e{715}*/
1649 	   SCIP_CONSDATA* consdata;
1650 	   SCIP_VAR** vars1;
1651 	   SCIP_VAR** vars2;
1652 	   int i;
1653 	   int varrow;
1654 	   int infrow;
1655 	
1656 	   assert( scip != NULL );
1657 	   assert( conshdlr != NULL );
1658 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1659 	   assert( cons != NULL );
1660 	   assert( infervar != NULL );
1661 	   assert( bdchgidx != NULL );
1662 	   assert( result != NULL );
1663 	
1664 	   SCIPdebugMsg(scip, "Propagation resolution method of orbisack constraint handler.\n");
1665 	
1666 	   *result = SCIP_DIDNOTFIND;
1667 	
1668 	   consdata = SCIPconsGetData(cons);
1669 	   assert( consdata != NULL);
1670 	   assert( consdata->nrows > 0 );
1671 	   assert( consdata->vars1 != NULL );
1672 	   assert( consdata->vars2 != NULL );
1673 	
1674 	   vars1 = consdata->vars1;
1675 	   vars2 = consdata->vars2;
1676 	
1677 	   /* inferinfo == varrow + infrow * nrows. infrow is 0 if the fixing is not caused by a lookahead. */
1678 	   varrow = inferinfo % consdata->nrows;
1679 	   infrow = inferinfo / consdata->nrows;
1680 	
1681 	   assert( varrow >= 0 );
1682 	   assert( varrow < consdata->nrows );
1683 	   assert( infrow >= 0 );
1684 	   assert( infrow < consdata->nrows );
1685 	
1686 	   /* In both cases, the rows until "varrow" are constants. */
1687 	   for (i = 0; i < varrow; ++i)
1688 	   {
1689 	      /* Conflict caused by bounds of previous variables */
1690 	      SCIP_CALL( SCIPaddConflictUb(scip, vars1[i], bdchgidx) );
1691 	      SCIP_CALL( SCIPaddConflictLb(scip, vars1[i], bdchgidx) );
1692 	      SCIP_CALL( SCIPaddConflictUb(scip, vars2[i], bdchgidx) );
1693 	      SCIP_CALL( SCIPaddConflictLb(scip, vars2[i], bdchgidx) );
1694 	   }
1695 	
1696 	   if ( infrow > 0 )
1697 	   {
1698 	      /* The fixing of infervar is caused by a lookahead (checkFeasible).
1699 	       * The rows until "varrow" are constants, and row "varrow" is (_, _), (1, _), (_, 0).
1700 	       * If we assume "varrow" is constant, then the next rows until infrow are constants, and infrow is (0, 1).
1701 	       */
1702 	      for (i = varrow + 1; i < infrow; ++i)
1703 	      {
1704 	         /* These rows are one of (0, 0), (1, 1), (0, _), (_, 1), making them constants. */
1705 	         SCIP_CALL( SCIPaddConflictUb(scip, vars1[i], bdchgidx) );
1706 	         SCIP_CALL( SCIPaddConflictLb(scip, vars1[i], bdchgidx) );
1707 	         SCIP_CALL( SCIPaddConflictUb(scip, vars2[i], bdchgidx) );
1708 	         SCIP_CALL( SCIPaddConflictLb(scip, vars2[i], bdchgidx) );
1709 	      }
1710 	
1711 	      /* And infrow itself is (0, 1). */
1712 	      assert( SCIPvarGetUbAtIndex(vars1[infrow], bdchgidx, TRUE) < 0.5 );
1713 	      assert( SCIPvarGetUbAtIndex(vars1[infrow], bdchgidx, FALSE) < 0.5 );
1714 	      assert( SCIPvarGetLbAtIndex(vars2[infrow], bdchgidx, TRUE) > 0.5 );
1715 	      assert( SCIPvarGetLbAtIndex(vars2[infrow], bdchgidx, FALSE) > 0.5 );
1716 	
1717 	      SCIP_CALL( SCIPaddConflictUb(scip, vars1[infrow], bdchgidx) );
1718 	      SCIP_CALL( SCIPaddConflictLb(scip, vars2[infrow], bdchgidx) );
1719 	   }
1720 	   else
1721 	   {
1722 	      /* This is not a fixing caused by lookahead (checkFeasible),
1723 	       * so row "varrow" was (0, _) or (_, 1) and its previous rows are constants.
1724 	       */
1725 	      if ( boundtype == SCIP_BOUNDTYPE_LOWER )
1726 	      {
1727 	         /* We changed the lower bound of infervar to 1. This means that this fixing is due to (_, 1) */
1728 	         assert( infervar == vars1[varrow] );
1729 	         assert( SCIPvarGetLbAtIndex(vars1[varrow], bdchgidx, FALSE) < 0.5 );
1730 	         assert( SCIPvarGetLbAtIndex(vars1[varrow], bdchgidx, TRUE) > 0.5 );
1731 	         assert( SCIPvarGetLbAtIndex(vars2[varrow], bdchgidx, FALSE ) > 0.5);
1732 	         assert( SCIPvarGetUbAtIndex(vars2[varrow], bdchgidx, FALSE ) > 0.5);
1733 	
1734 	         SCIP_CALL( SCIPaddConflictUb(scip, vars2[varrow], bdchgidx) );
1735 	         SCIP_CALL( SCIPaddConflictLb(scip, vars2[varrow], bdchgidx) );
1736 	      }
1737 	      else
1738 	      {
1739 	         /* We changed the upper bound to 0. This means that this fixing is due to (0, _) */
1740 	         assert( infervar == vars2[varrow] );
1741 	         assert( SCIPvarGetLbAtIndex(vars1[varrow], bdchgidx, FALSE ) < 0.5);
1742 	         assert( SCIPvarGetUbAtIndex(vars1[varrow], bdchgidx, FALSE ) < 0.5);
1743 	         assert( SCIPvarGetUbAtIndex(vars2[varrow], bdchgidx, FALSE) > 0.5 );
1744 	         assert( SCIPvarGetUbAtIndex(vars2[varrow], bdchgidx, TRUE) < 0.5 );
1745 	
1746 	         SCIP_CALL( SCIPaddConflictUb(scip, vars1[varrow], bdchgidx) );
1747 	         SCIP_CALL( SCIPaddConflictLb(scip, vars1[varrow], bdchgidx) );
1748 	      }
1749 	   }
1750 	
1751 	   *result = SCIP_SUCCESS;
1752 	   return SCIP_OKAY;
1753 	}
1754 	
1755 	
1756 	/** Lock variables
1757 	 *
1758 	 *  We assume we have only one global (void) constraint and lock all variables.
1759 	 *
1760 	 * - Orbisack constraints may get violated if the variables of the first column
1761 	 *   are rounded down, we therefor call SCIPaddVarLocksType(..., nlockspos, nlocksneg).
1762 	 * - Orbisack constraints may get violated if the variables of the second column
1763 	 *   are rounded up , we therefor call SCIPaddVarLocksType(..., nlocksneg, nlockspo ).
1764 	 */
1765 	static
1766 	SCIP_DECL_CONSLOCK(consLockOrbisack)
1767 	{  /*lint --e{715}*/
1768 	   SCIP_CONSDATA* consdata;
1769 	   SCIP_VAR** vars1;
1770 	   SCIP_VAR** vars2;
1771 	   int nrows;
1772 	   int i;
1773 	
1774 	   assert( scip != NULL );
1775 	   assert( conshdlr != NULL );
1776 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1777 	   assert( cons != NULL );
1778 	
1779 	   SCIPdebugMsg(scip, "Locking method for orbisack constraint handler.\n");
1780 	
1781 	   /* get data of original constraint */
1782 	   consdata = SCIPconsGetData(cons);
1783 	   assert( consdata != NULL);
1784 	   assert( consdata->nrows > 0 );
1785 	   assert( consdata->vars1 != NULL );
1786 	   assert( consdata->vars2 != NULL );
1787 	
1788 	   nrows = consdata->nrows;
1789 	   vars1 = consdata->vars1;
1790 	   vars2 = consdata->vars2;
1791 	
1792 	   for (i = 0; i < nrows; ++i)
1793 	   {
1794 	      SCIP_CALL( SCIPaddVarLocksType(scip, vars1[i], locktype, nlockspos, nlocksneg) );
1795 	      SCIP_CALL( SCIPaddVarLocksType(scip, vars2[i], locktype, nlocksneg, nlockspos) );
1796 	   }
1797 	
1798 	   return SCIP_OKAY;
1799 	}
1800 	
1801 	
1802 	/** constraint copying method of constraint handler */
1803 	static
1804 	SCIP_DECL_CONSCOPY(consCopyOrbisack)
1805 	{
1806 	   SCIP_CONSHDLRDATA* conshdlrdata;
1807 	   SCIP_CONSDATA* sourcedata;
1808 	   SCIP_VAR** sourcevars1;
1809 	   SCIP_VAR** sourcevars2;
1810 	   SCIP_VAR** vars1;
1811 	   SCIP_VAR** vars2;
1812 	   int nrows;
1813 	   int i;
1814 	
1815 	   assert( scip != NULL );
1816 	   assert( cons != NULL );
1817 	   assert( sourcescip != NULL );
1818 	   assert( sourceconshdlr != NULL );
1819 	   assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
1820 	   assert( sourcecons != NULL );
1821 	   assert( varmap != NULL );
1822 	   assert( valid != NULL );
1823 	
1824 	   *valid = TRUE;
1825 	
1826 	   SCIPdebugMsg(scip, "Copying method for orbisack constraint handler.\n");
1827 	
1828 	   sourcedata = SCIPconsGetData(sourcecons);
1829 	   assert( sourcedata != NULL );
1830 	   assert( sourcedata->vars1 != NULL );
1831 	   assert( sourcedata->vars2 != NULL );
1832 	   assert( sourcedata->nrows > 0 );
1833 	
1834 	   conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
1835 	   assert( conshdlrdata != NULL );
1836 	
1837 	   /* do not copy non-model constraints */
1838 	   if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
1839 	   {
1840 	      *valid = FALSE;
1841 	
1842 	      return SCIP_OKAY;
1843 	   }
1844 	
1845 	   sourcevars1 = sourcedata->vars1;
1846 	   sourcevars2 = sourcedata->vars2;
1847 	   nrows = sourcedata->nrows;
1848 	
1849 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) );
1850 	
1851 	   for (i = 0; i < nrows && *valid; ++i)
1852 	   {
1853 	      SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars1[i], &(vars1[i]), varmap, consmap, global, valid) );
1854 	      assert( !(*valid) || vars1[i] != NULL );
1855 	   }
1856 	
1857 	   /* only create the target constraint, if all variables could be copied */
1858 	   if ( !(*valid) )
1859 	   {
1860 	      SCIPfreeBufferArray(scip, &vars1);
1861 	
1862 	      return SCIP_OKAY;
1863 	   }
1864 	
1865 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) );
1866 	
1867 	   for (i = 0; i < nrows && *valid; ++i)
1868 	   {
1869 	      SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars2[i], &(vars2[i]), varmap, consmap, global, valid) );
1870 	      assert( !(*valid) || vars2[i] != NULL );
1871 	   }
1872 	
1873 	   /* only create the target constraint, if all variables could be copied */
1874 	   if ( *valid )
1875 	   {
1876 	      /* create copied constraint */
1877 	      if ( name == NULL )
1878 	         name = SCIPconsGetName(sourcecons);
1879 	
1880 	      SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, sourcedata->ismodelcons,
1881 	            initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1882 	   }
1883 	
1884 	   SCIPfreeBufferArray(scip, &vars2);
1885 	   SCIPfreeBufferArray(scip, &vars1);
1886 	
1887 	   return SCIP_OKAY;
1888 	}
1889 	
1890 	
1891 	/** constraint parsing method of constraint handler */
1892 	static
1893 	SCIP_DECL_CONSPARSE(consParseOrbisack)
1894 	{  /*lint --e{715}*/
1895 	   const char* s;
1896 	   char* endptr;
1897 	   SCIP_VAR** vars1;
1898 	   SCIP_VAR** vars2;
1899 	   SCIP_VAR* var;
1900 	   int nrows = 0;
1901 	   int maxnrows = 128;
1902 	   SCIP_Bool firstcolumn = TRUE;
1903 	   SCIP_Bool ispporbisack = FALSE;
1904 	   SCIP_Bool isparttype = FALSE;
1905 	
1906 	   assert( success != NULL );
1907 	
1908 	   *success = TRUE;
1909 	   s = str;
1910 	
1911 	   /* skip white space */
1912 	   SCIP_CALL( SCIPskipSpace((char**)&s) );
1913 	
1914 	   if( strncmp(s, "partOrbisack(", 13) == 0 )
1915 	   {
1916 	      ispporbisack = TRUE;
1917 	      isparttype = TRUE;
1918 	   }
1919 	   else if( strncmp(s, "packOrbisack(", 13) == 0 )
1920 	      ispporbisack = TRUE;
1921 	   else
1922 	   {
1923 	      if( strncmp(s, "fullOrbisack(", 13) != 0 )
1924 	      {
1925 	         SCIPerrorMessage("Syntax error - expected \"fullOrbisack(\", \"partOrbisack\" or \"packOrbisacj\": %s\n", s);
1926 	         *success = FALSE;
1927 	         return SCIP_OKAY;
1928 	      }
1929 	   }
1930 	   s += 13;
1931 	
1932 	   /* loop through string */
1933 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars1, maxnrows) );
1934 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars2, maxnrows) );
1935 	
1936 	   do
1937 	   {
1938 	      /* parse variable name */
1939 	      SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
1940 	
1941 	      if( var == NULL )
1942 	      {
1943 	         endptr = strchr(endptr, ')');
1944 	
1945 	         if( endptr == NULL || !firstcolumn )
1946 	         {
1947 	            SCIPerrorMessage("variable is missing.\n");
1948 	            *success = FALSE;
1949 	         }
1950 	
1951 	         break;
1952 	      }
1953 	
1954 	      s = endptr;
1955 	      assert( s != NULL );
1956 	
1957 	      /* skip white space */
1958 	      SCIP_CALL( SCIPskipSpace((char**)&s) );
1959 	
1960 	      if( firstcolumn == ( *s == '.' || *s == ')' ) )
1961 	      {
1962 	         SCIPerrorMessage("there are not two variables per row.\n");
1963 	         *success = FALSE;
1964 	         break;
1965 	      }
1966 	
1967 	      /* begin new row if required */
1968 	      if( firstcolumn )
1969 	      {
1970 	         ++nrows;
1971 	
1972 	         if( nrows > maxnrows )
1973 	         {
1974 	            maxnrows = SCIPcalcMemGrowSize(scip, nrows);
1975 	            SCIP_CALL( SCIPreallocBufferArray(scip, &vars1, maxnrows) );
1976 	            SCIP_CALL( SCIPreallocBufferArray(scip, &vars2, maxnrows) );
1977 	            assert( nrows <= maxnrows );
1978 	         }
1979 	
1980 	         vars1[nrows-1] = var;
1981 	      }
1982 	      else
1983 	         vars2[nrows-1] = var;
1984 	
1985 	      firstcolumn = !firstcolumn;
1986 	
1987 	      /* skip ',' or '.' */
1988 	      if( *s == ',' || *s == '.' )
1989 	         ++s;
1990 	   }
1991 	   while( *s != ')' );
1992 	
1993 	   if( *success )
1994 	      SCIP_CALL( SCIPcreateConsBasicOrbisack(scip, cons, name, vars1, vars2, nrows, ispporbisack, isparttype, TRUE) );
1995 	
1996 	   SCIPfreeBufferArray(scip, &vars2);
1997 	   SCIPfreeBufferArray(scip, &vars1);
1998 	
1999 	   return SCIP_OKAY;
2000 	}
2001 	
2002 	
2003 	/** constraint display method of constraint handler
2004 	 *
2005 	 *  The constraint handler should output a representation of the constraint into the given text file.
2006 	 */
2007 	static
2008 	SCIP_DECL_CONSPRINT(consPrintOrbisack)
2009 	{   /*lint --e{715}*/
2010 	   SCIP_CONSDATA* consdata;
2011 	   SCIP_VAR** vars1;
2012 	   SCIP_VAR** vars2;
2013 	   int nrows;
2014 	   int i;
2015 	
2016 	   assert( scip != NULL );
2017 	   assert( conshdlr != NULL );
2018 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2019 	   assert( cons != NULL );
2020 	
2021 	   consdata = SCIPconsGetData(cons);
2022 	   assert( consdata != NULL );
2023 	   assert( consdata->vars1 != NULL );
2024 	   assert( consdata->vars2 != NULL );
2025 	   assert( consdata->nrows > 0 );
2026 	
2027 	   vars1 = consdata->vars1;
2028 	   vars2 = consdata->vars2;
2029 	   nrows = consdata->nrows;
2030 	
2031 	   SCIPdebugMsg(scip, "Printing method for orbisack constraint handler\n");
2032 	
2033 	   SCIPinfoMessage(scip, file, "fullOrbisack(");
2034 	
2035 	   for (i = 0; i < nrows; ++i)
2036 	   {
2037 	      SCIP_CALL( SCIPwriteVarName(scip, file, vars1[i], TRUE) );
2038 	      SCIPinfoMessage(scip, file, ",");
2039 	      SCIP_CALL( SCIPwriteVarName(scip, file, vars2[i], TRUE) );
2040 	      if ( i < nrows-1 )
2041 	         SCIPinfoMessage(scip, file, ".");
2042 	   }
2043 	
2044 	   SCIPinfoMessage(scip, file, ")");
2045 	
2046 	   return SCIP_OKAY;
2047 	}
2048 	
2049 	
2050 	/** checks given solution for feasibility */
2051 	SCIP_RETCODE SCIPcheckSolutionOrbisack(
2052 	   SCIP*                 scip,               /**< SCIP data structure */
2053 	   SCIP_SOL*             sol,                /**< solution to check for feasibility */
2054 	   SCIP_VAR**            vars1,              /**< variables of first column */
2055 	   SCIP_VAR**            vars2,              /**< variables of second column */
2056 	   int                   nrows,              /**< number of rows */
2057 	   SCIP_Bool             printreason,        /**< whether reason for infeasibility should be printed */
2058 	   SCIP_Bool*            feasible            /**< memory address to store whether sol is feasible */
2059 	   )
2060 	{
2061 	   int i;
2062 	   int val1;
2063 	   int val2;
2064 	
2065 	   assert( scip != NULL );
2066 	   assert( vars1 != NULL );
2067 	   assert( vars2 != NULL );
2068 	   assert( nrows > 0 );
2069 	   assert( feasible != NULL );
2070 	
2071 	   *feasible = TRUE;
2072 	
2073 	   /* find first non-constant row and check for feasibility */
2074 	   for (i = 0; i < nrows; ++i)
2075 	   {
2076 	      assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars1[i])) );
2077 	      assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars2[i])) );
2078 	
2079 	      /* get values of i-th row */
2080 	      val1 = SCIPgetSolVal(scip, sol, vars1[i]) > 0.5 ? 1 : 0;
2081 	      val2 = SCIPgetSolVal(scip, sol, vars2[i]) > 0.5 ? 1 : 0;
2082 	
2083 	      /* if row i is constrant */
2084 	      if ( val1 == val2 )
2085 	         continue;
2086 	      /* row i has type (1,0) -> feasible */
2087 	      else if ( val1 == 1 )
2088 	      {
2089 	         assert( val2 == 0 );
2090 	         break;
2091 	      }
2092 	      else /* infeasible */
2093 	      {
2094 	         if ( printreason )
2095 	            SCIPinfoMessage(scip, NULL, "First non-constant row %d is fixed to (0,1).\n", i);
2096 	         *feasible = FALSE;
2097 	         break;
2098 	      }
2099 	   }
2100 	
2101 	   return SCIP_OKAY;
2102 	}
2103 	
2104 	
2105 	/** constraint method of constraint handler which returns the variables (if possible) */
2106 	static
2107 	SCIP_DECL_CONSGETVARS(consGetVarsOrbisack)
2108 	{  /*lint --e{715}*/
2109 	   SCIP_CONSDATA* consdata;
2110 	
2111 	   assert( cons != NULL );
2112 	   assert( success != NULL );
2113 	   assert( vars != NULL );
2114 	
2115 	   consdata = SCIPconsGetData(cons);
2116 	   assert( consdata != NULL );
2117 	
2118 	   if ( varssize < 2 * consdata->nrows )
2119 	      (*success) = FALSE;
2120 	   else
2121 	   {
2122 	      int cnt = 0;
2123 	      int i;
2124 	
2125 	      for (i = 0; i < consdata->nrows; ++i)
2126 	      {
2127 	         vars[cnt++] = consdata->vars1[i];
2128 	         vars[cnt++] = consdata->vars2[i];
2129 	      }
2130 	      (*success) = TRUE;
2131 	   }
2132 	
2133 	   return SCIP_OKAY;
2134 	}
2135 	
2136 	
2137 	/** constraint method of constraint handler which returns the number of variables (if possible) */
2138 	static
2139 	SCIP_DECL_CONSGETNVARS(consGetNVarsOrbisack)
2140 	{  /*lint --e{715}*/
2141 	   SCIP_CONSDATA* consdata;
2142 	
2143 	   assert( cons != NULL );
2144 	
2145 	   consdata = SCIPconsGetData(cons);
2146 	   assert( consdata != NULL );
2147 	
2148 	   (*nvars) = 2 * consdata->nrows;
2149 	   (*success) = TRUE;
2150 	
2151 	   return SCIP_OKAY;
2152 	}
2153 	
2154 	
2155 	/** creates the handler for orbisack constraints and includes it in SCIP */
2156 	SCIP_RETCODE SCIPincludeConshdlrOrbisack(
2157 	   SCIP*                 scip                /**< SCIP data structure */
2158 	   )
2159 	{
2160 	   SCIP_CONSHDLRDATA* conshdlrdata = NULL;
2161 	   SCIP_CONSHDLR* conshdlr;
2162 	
2163 	   SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2164 	
2165 	   /* include constraint handler */
2166 	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2167 	         CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
2168 	         CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2169 	         consEnfolpOrbisack, consEnfopsOrbisack, consCheckOrbisack, consLockOrbisack,
2170 	         conshdlrdata) );
2171 	   assert( conshdlr != NULL );
2172 	
2173 	   /* set non-fundamental callbacks via specific setter functions */
2174 	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbisack, consCopyOrbisack) );
2175 	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbisack) );
2176 	   SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbisack) );
2177 	   SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbisack) );
2178 	   SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbisack) );
2179 	   SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbisack) );
2180 	   SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbisack) );
2181 	   SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbisack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2182 	   SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbisack) );
2183 	   SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbisack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
2184 	   SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbisack) );
2185 	   SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbisack, consSepasolOrbisack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2186 	   SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbisack) );
2187 	   SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOrbisack) );
2188 	   SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolOrbisack) );
2189 	
2190 	   /* separation methods */
2191 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/coverseparation",
2192 	         "Separate cover inequalities for orbisacks?",
2193 	         &conshdlrdata->coverseparation, TRUE, DEFAULT_COVERSEPARATION, NULL, NULL) );
2194 	
2195 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/orbiSeparation",
2196 	         "Separate orbisack inequalities?",
2197 	         &conshdlrdata->orbiseparation, TRUE, DEFAULT_ORBISEPARATION, NULL, NULL) );
2198 	
2199 	   SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/coeffbound",
2200 	         "Maximum size of coefficients for orbisack inequalities",
2201 	         &conshdlrdata->coeffbound, TRUE, DEFAULT_COEFFBOUND, 0.0, DBL_MAX, NULL, NULL) );
2202 	
2203 	   /* whether we allow upgrading to packing/partioning orbisack constraints*/
2204 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbisack",
2205 	         "Upgrade orbisack constraints to packing/partioning orbisacks?",
2206 	         &conshdlrdata->checkpporbisack, TRUE, DEFAULT_PPORBISACK, NULL, NULL) );
2207 	
2208 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
2209 	         "Whether orbisack constraints should be forced to be copied to sub SCIPs.",
2210 	         &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
2211 	
2212 	   return SCIP_OKAY;
2213 	}
2214 	
2215 	
2216 	/*
2217 	 * constraint specific interface methods
2218 	 */
2219 	
2220 	/** creates and captures a orbisack constraint
2221 	 *
2222 	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2223 	 */
2224 	SCIP_RETCODE SCIPcreateConsOrbisack(
2225 	   SCIP*                 scip,               /**< SCIP data structure */
2226 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
2227 	   const char*           name,               /**< name of constraint */
2228 	   SCIP_VAR*const*       vars1,              /**< first column of matrix of variables on which the symmetry acts */
2229 	   SCIP_VAR*const*       vars2,              /**< second column of matrix of variables on which the symmetry acts */
2230 	   int                   nrows,              /**< number of rows in variable matrix */
2231 	   SCIP_Bool             ispporbisack,       /**< whether the orbisack is a packing/partitioning orbisack */
2232 	   SCIP_Bool             isparttype,         /**< whether the orbisack is a partitioning orbisack */
2233 	   SCIP_Bool             ismodelcons,        /**< whether the orbisack is a model constraint */
2234 	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
2235 	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2236 	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
2237 	                                              *   Usually set to TRUE. */
2238 	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
2239 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
2240 	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
2241 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
2242 	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
2243 	                                              *   Usually set to TRUE. */
2244 	   SCIP_Bool             local,              /**< is constraint only valid locally?
2245 	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2246 	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
2247 	                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
2248 	                                              *   adds coefficients to this constraint. */
2249 	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
2250 	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
2251 	                                              *   are separated as constraints. */
2252 	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
2253 	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2254 	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
2255 	                                              *   if it may be moved to a more global node?
2256 	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2257 	   )
2258 	{
2259 	   SCIP_CONSHDLR* conshdlr;
2260 	   SCIP_CONSHDLRDATA* conshdlrdata;
2261 	   SCIP_CONSDATA* consdata;
2262 	   SCIP_VAR*** vars;
2263 	   SCIP_Bool success;
2264 	   SCIP_ORBITOPETYPE orbitopetype;
2265 	   int i;
2266 	
2267 	   /* find the orbisack constraint handler */
2268 	   conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2269 	   if ( conshdlr == NULL )
2270 	   {
2271 	      SCIPerrorMessage("orbisack constraint handler not found\n");
2272 	      return SCIP_PLUGINNOTFOUND;
2273 	   }
2274 	
2275 	   assert( nrows > 0 );
2276 	
2277 	   /* check for upgrade to packing/partitioning orbisacks*/
2278 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
2279 	   if ( ! ispporbisack && conshdlrdata->checkpporbisack )
2280 	   {
2281 	      SCIP_CALL( packingUpgrade(scip, vars1, vars2, nrows, &success, &isparttype) );
2282 	
2283 	      if ( success )
2284 	         ispporbisack = TRUE;
2285 	   }
2286 	
2287 	   /* create constraint, if it is a packing/partitioning orbisack, add orbitope constraint
2288 	    * instead of orbitsack constraint */
2289 	   if (  ispporbisack )
2290 	   {
2291 	      SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) );
2292 	      for (i = 0; i < nrows; ++i)
2293 	      {
2294 	         SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], 2) ); /*lint !e866*/
2295 	         vars[i][0] = vars1[i];
2296 	         vars[i][1] = vars2[i];
2297 	      }
2298 	
2299 	      if ( isparttype )
2300 	         orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
2301 	      else
2302 	         orbitopetype = SCIP_ORBITOPETYPE_PACKING;
2303 	
2304 	      SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, "pporbisack", vars, orbitopetype, nrows,
2305 	            2, FALSE, TRUE, TRUE, ismodelcons, initial, separate, enforce, check, propagate, local,
2306 	            modifiable, dynamic, removable, stickingatnode) );
2307 	
2308 	      for (i = 0; i < nrows; ++i)
2309 	         SCIPfreeBufferArray(scip, &vars[i]);
2310 	      SCIPfreeBufferArray(scip, &vars);
2311 	   }
2312 	   else
2313 	   {
2314 	      /* create constraint data */
2315 	      SCIP_CALL( consdataCreate(scip, &consdata, vars1, vars2, nrows, ismodelcons) );
2316 	
2317 	      SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2318 	            local, modifiable, dynamic, removable, stickingatnode) );
2319 	   }
2320 	
2321 	   return SCIP_OKAY;
2322 	}
2323 	
2324 	
2325 	/** creates and captures an orbisack constraint in its most basic variant
2326 	 *
2327 	 *  All constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h.
2328 	 *
2329 	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2330 	 */
2331 	SCIP_RETCODE SCIPcreateConsBasicOrbisack(
2332 	   SCIP*                 scip,               /**< SCIP data structure */
2333 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
2334 	   const char*           name,               /**< name of constraint */
2335 	   SCIP_VAR**            vars1,              /**< first column of matrix of variables on which the symmetry acts */
2336 	   SCIP_VAR**            vars2,              /**< second column of matrix of variables on which the symmetry acts */
2337 	   int                   nrows,              /**< number of rows in constraint matrix */
2338 	   SCIP_Bool             ispporbisack,       /**< whether the orbisack is a packing/partitioning orbisack */
2339 	   SCIP_Bool             isparttype,         /**< whether the orbisack is a partitioning orbisack */
2340 	   SCIP_Bool             ismodelcons         /**< whether the orbisack is a model constraint */
2341 	   )
2342 	{
2343 	   SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, ispporbisack, isparttype, ismodelcons,
2344 	         TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2345 	
2346 	   return SCIP_OKAY;
2347 	}
2348