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_sos2.c
26   	 * @ingroup DEFPLUGINS_CONS
27   	 * @brief  constraint handler for SOS type 2 constraints
28   	 * @author Marc Pfetsch
29   	 *
30   	 * A specially ordered set of type 2 (SOS2) is a sequence of variables such that at most two
31   	 * variables are nonzero and if two variables are nonzero they must be adjacent in the specified
32   	 * sequence. Note that it is in principle allowed that a variable appears twice, but it then can be
33   	 * fixed to 0 if it is at least two apart in the sequence.
34   	 *
35   	 * This constraint is useful when considering a piecewise affine approximation of a univariate
36   	 * (nonlinear) function \f$: [a,b] \rightarrow R\f$: Let \f$x_1 < \ldots < x_n\f$ be points in
37   	 * \f$[a,b]\f$ and introduce variables \f$\lambda_1, \ldots, \lambda_n\f$. To evaluate \f$f(x')\f$
38   	 * at some point \f$x' \in [a,b]\f$ one can use the following constraints:
39   	 * \f[
40   	 *     \lambda_1 + \cdots + \lambda_n = 1,\quad x' = x_1 \lambda_1 + \cdots + x_n \lambda_n.
41   	 * \f]
42   	 * The value of \f$f(x')\f$ can the be approximated as
43   	 * \f[
44   	 *     f(x_1) \lambda_1 + \cdots + f(x_n) \lambda_n.
45   	 * \f]
46   	 * To get a valid piecewise affine approximation, \f$\lambda_1, \ldots, \lambda_n\f$ have to obey an
47   	 * SOS constraint of type 2.
48   	 *
49   	 * This implementation of this constraint handler is based on classical ideas, see e.g.@n
50   	 *  "Special Facilities in General Mathematical Programming System for
51   	 *  Non-Convex Problems Using Ordered Sets of Variables"@n
52   	 *  E. Beale and J. Tomlin, Proc. 5th IFORS Conference, 447-454 (1970)
53   	 *
54   	 * The order of the variables is determined as follows:
55   	 *
56   	 * - If the constraint is created with SCIPcreateConsSOS2() and weights are given, the weights
57   	 *   determine the order (decreasing weights). Additional variables can be added with
58   	 *   SCIPaddVarSOS2(), which adds a variable with given weight.
59   	 *
60   	 * - If an empty constraint is created and then variables are added with SCIPaddVarSOS2(), weights
61   	 *   are needed and stored.
62   	 *
63   	 * - All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are
64   	 *   added with SCIPappendVarSOS2().
65   	 *
66   	 * @todo Allow to adapt the order of the constraints, e.g. by priorities. This for instance
67   	 *   determines the branching order.
68   	 * @todo Separate the following cuts for each pair of variables x, y of at least distance 2 in the
69   	 *   SOS2 constraint: \f$ \min \{l_x, l_y\} \leq x + y \leq \max \{u_x, u_y\}\f$, where \f$l_x, u_x,
70   	 *   l_y, u_y\f$ are the lower and upper bounds of x and y, respectively.
71   	 * @todo Possibly allow to generate local cuts via strengthened local cuts (would affect lhs/rhs of rows)
72   	 * @todo Try to compute better estimations for the child nodes in enforceSOS2 when called for a relaxation solution;
73   	 *   currently pseudo costs are used, which are not computed for the relaxation.
74   	 */
75   	
76   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
77   	
78   	#include "blockmemshell/memory.h"
79   	#include "scip/cons_linear.h"
80   	#include "scip/cons_sos2.h"
81   	#include "scip/pub_cons.h"
82   	#include "scip/pub_event.h"
83   	#include "scip/pub_lp.h"
84   	#include "scip/pub_message.h"
85   	#include "scip/pub_misc.h"
86   	#include "scip/pub_misc_sort.h"
87   	#include "scip/pub_var.h"
88   	#include "scip/scip_branch.h"
89   	#include "scip/scip_conflict.h"
90   	#include "scip/scip_cons.h"
91   	#include "scip/scip_copy.h"
92   	#include "scip/scip_cut.h"
93   	#include "scip/scip_event.h"
94   	#include "scip/scip_general.h"
95   	#include "scip/scip_lp.h"
96   	#include "scip/scip_mem.h"
97   	#include "scip/scip_message.h"
98   	#include "scip/scip_numerics.h"
99   	#include "scip/scip_prob.h"
100  	#include "scip/scip_sol.h"
101  	#include "scip/scip_var.h"
102  	#include "scip/symmetry_graph.h"
103  	#include "symmetry/struct_symmetry.h"
104  	#include <ctype.h>
105  	#include <stdlib.h>
106  	#include <string.h>
107  	
108  	
109  	/* constraint handler properties */
110  	#define CONSHDLR_NAME          "SOS2"
111  	#define CONSHDLR_DESC          "SOS2 constraint handler"
112  	#define CONSHDLR_SEPAPRIORITY        10 /**< priority of the constraint handler for separation */
113  	#define CONSHDLR_ENFOPRIORITY       100 /**< priority of the constraint handler for constraint enforcing */
114  	#define CONSHDLR_CHECKPRIORITY      -10 /**< priority of the constraint handler for checking feasibility */
115  	#define CONSHDLR_SEPAFREQ             0 /**< frequency for separating cuts; zero means to separate only in the root node */
116  	#define CONSHDLR_PROPFREQ             1 /**< frequency for propagating domains; zero means only preprocessing propagation */
117  	#define CONSHDLR_EAGERFREQ          100 /**< frequency for using all instead of only the useful constraints in separation,
118  	                                         *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
119  	#define CONSHDLR_MAXPREROUNDS        -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
120  	#define CONSHDLR_DELAYSEPA        FALSE /**< should separation method be delayed, if other separators found cuts? */
121  	#define CONSHDLR_DELAYPROP        FALSE /**< should propagation method be delayed, if other propagators found reductions? */
122  	#define CONSHDLR_NEEDSCONS         TRUE /**< should the constraint handler be skipped, if no constraints are available? */
123  	
124  	#define CONSHDLR_PROP_TIMING             SCIP_PROPTIMING_BEFORELP
125  	#define CONSHDLR_PRESOLTIMING            SCIP_PRESOLTIMING_FAST
126  	
127  	/* event handler properties */
128  	#define EVENTHDLR_NAME         "SOS2"
129  	#define EVENTHDLR_DESC         "bound change event handler for SOS2 constraints"
130  	
131  	#define EVENTHDLR_EVENT_TYPE   (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)
132  	
133  	
134  	/** constraint data for SOS2 constraints */
135  	struct SCIP_ConsData
136  	{
137  	   int                   nvars;              /**< number of variables in the constraint */
138  	   int                   maxvars;            /**< maximal number of variables (= size of storage) */
139  	   int                   nfixednonzeros;     /**< number of variables fixed to be nonzero */
140  	   SCIP_VAR**            vars;               /**< variables in constraint */
141  	   SCIP_ROW*             row;                /**< row corresponding to upper and lower bound inequalities, or NULL if not yet created */
142  	   SCIP_Real*            weights;            /**< weights determining the order (ascending), or NULL if not used */
143  	};
144  	
145  	/** SOS2 constraint handler data */
146  	struct SCIP_ConshdlrData
147  	{
148  	   SCIP_EVENTHDLR*       eventhdlr;          /**< event handler for bound change events */
149  	};
150  	
151  	
152  	/** fix variable in given node to 0 or add constraint if variable is multi-aggregated */
153  	static
154  	SCIP_RETCODE fixVariableZeroNode(
155  	   SCIP*                 scip,               /**< SCIP pointer */
156  	   SCIP_VAR*             var,                /**< variable to be fixed to 0*/
157  	   SCIP_NODE*            node,               /**< node */
158  	   SCIP_Bool*            infeasible          /**< if fixing is infeasible */
159  	   )
160  	{
161  	   /* if variable cannot be nonzero */
162  	   *infeasible = FALSE;
163  	   if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
164  	   {
165  	      *infeasible = TRUE;
166  	      return SCIP_OKAY;
167  	   }
168  	
169  	   /* if variable is multi-aggregated */
170  	   if ( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
171  	   {
172  	      SCIP_CONS* cons;
173  	      SCIP_Real val;
174  	
175  	      val = 1.0;
176  	
177  	      if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
178  	      {
179  	         SCIPdebugMsg(scip, "creating constraint to force multi-aggregated variable <%s> to 0.\n", SCIPvarGetName(var));
180  	         /* we have to insert a local constraint var = 0 */
181  	         SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "branch", 1, &var, &val, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
182  	               TRUE, FALSE, FALSE, FALSE, FALSE) );
183  	         SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) );
184  	         SCIP_CALL( SCIPreleaseCons(scip, &cons) );
185  	      }
186  	   }
187  	   else
188  	   {
189  	      if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
190  	         SCIP_CALL( SCIPchgVarLbNode(scip, node, var, 0.0) );
191  	      if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
192  	         SCIP_CALL( SCIPchgVarUbNode(scip, node, var, 0.0) );
193  	   }
194  	
195  	   return SCIP_OKAY;
196  	}
197  	
198  	
199  	/** fix variable in local node to 0, and return whether the operation was feasible
200  	 *
201  	 *  @note We do not add a linear constraint if the variable is multi-aggregated as in
202  	 *  fixVariableZeroNode(), since this would be too time consuming.
203  	 */
204  	static
205  	SCIP_RETCODE inferVariableZero(
206  	   SCIP*                 scip,               /**< SCIP pointer */
207  	   SCIP_VAR*             var,                /**< variable to be fixed to 0*/
208  	   SCIP_CONS*            cons,               /**< constraint */
209  	   int                   inferinfo,          /**< info for reverse prop. */
210  	   SCIP_Bool*            infeasible,         /**< if fixing is infeasible */
211  	   SCIP_Bool*            tightened,          /**< if fixing was performed */
212  	   SCIP_Bool*            success             /**< whether fixing was successful, i.e., variable is not multi-aggregated */
213  	   )
214  	{
215  	   *infeasible = FALSE;
216  	   *tightened = FALSE;
217  	   *success = FALSE;
218  	
219  	   /* if variable cannot be nonzero */
220  	   if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
221  	   {
222  	      *infeasible = TRUE;
223  	      return SCIP_OKAY;
224  	   }
225  	
226  	   /* directly fix variable if it is not multi-aggregated, do nothing otherwise */
227  	   if ( SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR )
228  	   {
229  	      SCIP_Bool tighten;
230  	
231  	      /* fix lower bound */
232  	      SCIP_CALL( SCIPinferVarLbCons(scip, var, 0.0, cons, inferinfo, FALSE, infeasible, &tighten) );
233  	      *tightened = *tightened || tighten;
234  	
235  	      /* fix upper bound */
236  	      SCIP_CALL( SCIPinferVarUbCons(scip, var, 0.0, cons, inferinfo, FALSE, infeasible, &tighten) );
237  	      *tightened = *tightened || tighten;
238  	
239  	      *success = TRUE;
240  	   }
241  	
242  	   return SCIP_OKAY;
243  	}
244  	
245  	
246  	/** add lock on variable */
247  	static
248  	SCIP_RETCODE lockVariableSOS2(
249  	   SCIP*                 scip,               /**< SCIP data structure */
250  	   SCIP_CONS*            cons,               /**< constraint */
251  	   SCIP_VAR*             var                 /**< variable */
252  	   )
253  	{
254  	   assert( scip != NULL );
255  	   assert( cons != NULL );
256  	   assert( var != NULL );
257  	
258  	   /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */
259  	   SCIP_CALL( SCIPlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)),
260  	         SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var))) );
261  	
262  	   return SCIP_OKAY;
263  	}
264  	
265  	
266  	/** remove lock on variable */
267  	static
268  	SCIP_RETCODE unlockVariableSOS2(
269  	   SCIP*                 scip,               /**< SCIP data structure */
270  	   SCIP_CONS*            cons,               /**< constraint */
271  	   SCIP_VAR*             var                 /**< variable */
272  	   )
273  	{
274  	   assert( scip != NULL );
275  	   assert( cons != NULL );
276  	   assert( var != NULL );
277  	
278  	   /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */
279  	   SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)),
280  	         SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var))) );
281  	
282  	   return SCIP_OKAY;
283  	}
284  	
285  	
286  	/** ensures that the vars and weights array can store at least num entries */
287  	static
288  	SCIP_RETCODE consdataEnsurevarsSizeSOS2(
289  	   SCIP*                 scip,               /**< SCIP data structure */
290  	   SCIP_CONSDATA*        consdata,           /**< constraint data */
291  	   int                   num,                /**< minimum number of entries to store */
292  	   SCIP_Bool             reserveWeights      /**< whether the weights array is handled */
293  	   )
294  	{
295  	   assert( consdata != NULL );
296  	   assert( consdata->nvars <= consdata->maxvars );
297  	
298  	   if ( num > consdata->maxvars )
299  	   {
300  	      int newsize;
301  	
302  	      newsize = SCIPcalcMemGrowSize(scip, num);
303  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->maxvars, newsize) );
304  	      if ( reserveWeights )
305  	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->maxvars, newsize) );
306  	      consdata->maxvars = newsize;
307  	   }
308  	   assert( num <= consdata->maxvars );
309  	
310  	   return SCIP_OKAY;
311  	}
312  	
313  	
314  	/** handle new variable */
315  	static
316  	SCIP_RETCODE handleNewVariableSOS2(
317  	   SCIP*                 scip,               /**< SCIP data structure */
318  	   SCIP_CONS*            cons,               /**< constraint */
319  	   SCIP_CONSDATA*        consdata,           /**< constraint data */
320  	   SCIP_VAR*             var,                /**< variable */
321  	   SCIP_Bool             transformed         /**< whether original variable was transformed */
322  	   )
323  	{
324  	   assert( scip != NULL );
325  	   assert( cons != NULL );
326  	   assert( consdata != NULL );
327  	   assert( var != NULL );
328  	
329  	   /* if we are in transformed problem, catch the variable's events */
330  	   if ( transformed )
331  	   {
332  	      SCIP_CONSHDLR* conshdlr;
333  	      SCIP_CONSHDLRDATA* conshdlrdata;
334  	
335  	      /* get event handler */
336  	      conshdlr = SCIPconsGetHdlr(cons);
337  	      conshdlrdata = SCIPconshdlrGetData(conshdlr);
338  	      assert( conshdlrdata != NULL );
339  	      assert( conshdlrdata->eventhdlr != NULL );
340  	
341  	      /* catch bound change events of variable */
342  	      SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr,
343  	            (SCIP_EVENTDATA*)cons, NULL) );
344  	
345  	      /* if the variable if fixed to nonzero */
346  	      assert( consdata->nfixednonzeros >= 0 );
347  	      if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
348  	         ++consdata->nfixednonzeros;
349  	   }
350  	
351  	   /* install the rounding locks for the new variable */
352  	   SCIP_CALL( lockVariableSOS2(scip, cons, var) );
353  	
354  	   /* add the new coefficient to the LP row, if necessary */
355  	   if ( consdata->row != NULL )
356  	   {
357  	      /* this is currently dead code, since the constraint is not modifiable */
358  	      SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, 1.0) );
359  	
360  	      /* update lhs and rhs if necessary */
361  	      if ( SCIPisFeasGT(scip, SCIPvarGetUbLocal(var), SCIProwGetRhs(consdata->row)) )
362  	         SCIP_CALL( SCIPchgRowRhs(scip, consdata->row, SCIPvarGetUbLocal(var) ) );
363  	      if ( SCIPisFeasLT(scip, SCIPvarGetLbLocal(var), SCIProwGetLhs(consdata->row)) )
364  	         SCIP_CALL( SCIPchgRowLhs(scip, consdata->row, SCIPvarGetLbLocal(var) ) );
365  	   }
366  	
367  	   return SCIP_OKAY;
368  	}
369  	
370  	
371  	/** adds a variable to an SOS2 constraint, a position given by weight - ascending order */
372  	static
373  	SCIP_RETCODE addVarSOS2(
374  	   SCIP*                 scip,               /**< SCIP data structure */
375  	   SCIP_CONS*            cons,               /**< constraint */
376  	   SCIP_VAR*             var,                /**< variable to add to the constraint */
377  	   SCIP_Real             weight              /**< weight to determine position */
378  	   )
379  	{
380  	   SCIP_CONSDATA* consdata;
381  	   SCIP_Bool transformed;
382  	   int j;
383  	   int pos;
384  	
385  	   assert( var != NULL );
386  	   assert( cons != NULL );
387  	
388  	   consdata = SCIPconsGetData(cons);
389  	   assert( consdata != NULL );
390  	
391  	   if ( consdata->weights == NULL && consdata->maxvars > 0 )
392  	   {
393  	      SCIPerrorMessage("cannot add variable to SOS2 constraint <%s> that does not contain weights.\n", SCIPconsGetName(cons));
394  	      return SCIP_INVALIDCALL;
395  	   }
396  	
397  	   /* are we in the transformed problem? */
398  	   transformed = SCIPconsIsTransformed(cons);
399  	
400  	   /* always use transformed variables in transformed constraints */
401  	   if ( transformed )
402  	   {
403  	      SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
404  	   }
405  	   assert( var != NULL );
406  	   assert( transformed == SCIPvarIsTransformed(var) );
407  	
408  	   SCIP_CALL( consdataEnsurevarsSizeSOS2(scip, consdata, consdata->nvars + 1, TRUE) );
409  	   assert( consdata->weights != NULL );
410  	   assert( consdata->maxvars >= consdata->nvars+1 );
411  	
412  	   /* find variable position */
413  	   for (pos = 0; pos < consdata->nvars; ++pos)
414  	   {
415  	      if ( consdata->weights[pos] > weight )
416  	         break;
417  	   }
418  	   assert( 0 <= pos && pos <= consdata->nvars );
419  	
420  	   /* move other variables, if necessary */
421  	   for (j = consdata->nvars; j > pos; --j)
422  	   {
423  	      consdata->vars[j] = consdata->vars[j-1];
424  	      consdata->weights[j] = consdata->weights[j-1];
425  	   }
426  	
427  	   /* insert variable */
428  	   consdata->vars[pos] = var;
429  	   consdata->weights[pos] = weight;
430  	   ++consdata->nvars;
431  	
432  	   /* handle the new variable */
433  	   SCIP_CALL( handleNewVariableSOS2(scip, cons, consdata, var, transformed) );
434  	
435  	   return SCIP_OKAY;
436  	}
437  	
438  	
439  	/** appends a variable to an SOS2 constraint */
440  	static
441  	SCIP_RETCODE appendVarSOS2(
442  	   SCIP*                 scip,               /**< SCIP data structure */
443  	   SCIP_CONS*            cons,               /**< constraint */
444  	   SCIP_VAR*             var                 /**< variable to add to the constraint */
445  	   )
446  	{
447  	   SCIP_CONSDATA* consdata;
448  	   SCIP_Bool transformed;
449  	
450  	   assert( var != NULL );
451  	   assert( cons != NULL );
452  	
453  	   consdata = SCIPconsGetData(cons);
454  	   assert( consdata != NULL );
455  	   assert( consdata->nvars >= 0 );
456  	
457  	   /* are we in the transformed problem? */
458  	   transformed = SCIPconsIsTransformed(cons);
459  	
460  	   /* always use transformed variables in transformed constraints */
461  	   if ( transformed )
462  	   {
463  	      SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
464  	   }
465  	   assert( var != NULL );
466  	   assert( transformed == SCIPvarIsTransformed(var) );
467  	
468  	   if ( consdata->weights != NULL )
469  	   {
470  	      SCIP_CALL( consdataEnsurevarsSizeSOS2(scip, consdata, consdata->nvars + 1, TRUE) );
471  	   }
472  	   else
473  	   {
474  	      SCIP_CALL( consdataEnsurevarsSizeSOS2(scip, consdata, consdata->nvars + 1, FALSE) );
475  	   }
476  	
477  	   /* insert variable */
478  	   consdata->vars[consdata->nvars] = var;
479  	   if ( consdata->weights != NULL )
480  	   {
481  	      if ( consdata->nvars > 0 )
482  	         consdata->weights[consdata->nvars] = consdata->weights[consdata->nvars-1] + 1.0;
483  	      else
484  	         consdata->weights[consdata->nvars] = 0.0;
485  	   }
486  	   ++consdata->nvars;
487  	
488  	   /* handle the new variable */
489  	   SCIP_CALL( handleNewVariableSOS2(scip, cons, consdata, var, transformed) );
490  	
491  	   return SCIP_OKAY;
492  	}
493  	
494  	
495  	/** deletes a variable of an SOS2 constraint */
496  	static
497  	SCIP_RETCODE deleteVarSOS2(
498  	   SCIP*                 scip,               /**< SCIP data structure */
499  	   SCIP_CONS*            cons,               /**< constraint */
500  	   SCIP_CONSDATA*        consdata,           /**< constraint data */
501  	   SCIP_EVENTHDLR*       eventhdlr,          /**< corresponding event handler */
502  	   int                   pos                 /**< position of variable in array */
503  	   )
504  	{
505  	   int j;
506  	
507  	   assert( 0 <= pos && pos < consdata->nvars );
508  	
509  	   /* remove lock of variable */
510  	   SCIP_CALL( unlockVariableSOS2(scip, cons, consdata->vars[pos]) );
511  	
512  	   /* drop events on variable */
513  	   SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, -1) );
514  	
515  	   /* delete variable - need to copy since order is important */
516  	   for (j = pos; j < consdata->nvars-1; ++j)
517  	   {
518  	      consdata->vars[j] = consdata->vars[j+1]; /*lint !e679*/
519  	      if ( consdata->weights != NULL )
520  	         consdata->weights[j] = consdata->weights[j+1]; /*lint !e679*/
521  	   }
522  	   --consdata->nvars;
523  	
524  	   return SCIP_OKAY;
525  	}
526  	
527  	
528  	/** perform one presolving round
529  	 *
530  	 *  We perform the following presolving steps.
531  	 *
532  	 *  - If the bounds of one variable force it to be nonzero, we can fix all other variables with distance at least two to
533  	 *    zero. If two variables are certain to be nonzero, we can fix all other variables to 0 and remove the constraint.
534  	 *  - All variables fixed to zero, that are at the beginning or end of the constraint can be removed.
535  	 *  - We substitute appregated variables.
536  	 *  - If a constraint has at most two variables, we delete it.
537  	 *
538  	 *  We currently do not handle the following:
539  	 *
540  	 *  - If we have at least two variables fixed to zero next to each-other, that are positioned in the inner part of this
541  	 *    constraint, we can delete all but one of these variables.
542  	 *  - If a variable appears twice not next to each-other, it can be fixed to 0. If one variable appears next to
543  	 *    each-other and is already certain to be nonzero, we can fix all variables.
544  	 *  - If a binary variable and its negation appear in the constraint, we might fix variables to zero or can forbid a zero
545  	 *    value for them.
546  	 *  - When, after removing all zero "border" variables, a constraint with more than two variables has at most two
547  	 *    variables that are not fixed to 0, only one of these can take a nonzero value, because these variables need to be
548  	 *    the "border" variables of this constraint. The same holds if we have exactly three variables in one constraint and
549  	 *    the middle variable is certain to be not zero. In both cases we can upgrade this constraint constraint to an sos1
550  	 *    consisting only of the "border" variables. If these "border" variables are negations of each other, we can delete
551  	 *    this constraint.
552  	 *  - When, after removing all variables fixed to 0, that are possible, in a constraint each even positioned variable is
553  	 *    fixed to 0, we can upgrade this constraint to an sos1 that holds all non-fixed variables.
554  	 *  - Extract cliques for all odd and also for all even positioned binary variables
555  	 */
556  	static
557  	SCIP_RETCODE presolRoundSOS2(
558  	   SCIP*                 scip,               /**< SCIP pointer */
559  	   SCIP_CONS*            cons,               /**< constraint */
560  	   SCIP_CONSDATA*        consdata,           /**< constraint data */
561  	   SCIP_EVENTHDLR*       eventhdlr,          /**< event handler */
562  	   SCIP_Bool*            cutoff,             /**< whether a cutoff happened */
563  	   SCIP_Bool*            success,            /**< whether we performed a successful reduction */
564  	   int*                  ndelconss,          /**< number of deleted constraints */
565  	   int*                  nfixedvars,         /**< number of fixed variables */
566  	   int*                  nremovedvars        /**< number of variables removed */
567  	   )
568  	{
569  	   SCIP_VAR** vars;
570  	   SCIP_Bool infeasible;
571  	   SCIP_Bool fixed;
572  	   int nfixednonzeros;
573  	   int lastFixedNonzero;
574  	   int lastzero;
575  	   int localnremovedvars;
576  	   int oldnfixedvars;
577  	   int j;
578  	
579  	   assert( scip != NULL );
580  	   assert( cons != NULL );
581  	   assert( consdata != NULL );
582  	   assert( eventhdlr != NULL );
583  	   assert( cutoff != NULL );
584  	   assert( success != NULL );
585  	   assert( ndelconss != NULL );
586  	   assert( nfixedvars != NULL );
587  	   assert( nremovedvars != NULL );
588  	
589  	   *cutoff = FALSE;
590  	   *success = FALSE;
591  	
592  	   SCIPdebugMsg(scip, "Presolving SOS2 constraint <%s>.\n", SCIPconsGetName(cons) );
593  	
594  	   /* if the number of variables is at most 2 */
595  	   if( consdata->nvars <= 2 )
596  	   {
597  	      SCIPdebugMsg(scip, "Deleting constraint with <= 2 variables.\n");
598  	
599  	      /* delete constraint */
600  	      assert( ! SCIPconsIsModifiable(cons) );
601  	      SCIP_CALL( SCIPdelCons(scip, cons) );
602  	      ++(*ndelconss);
603  	      *success = TRUE;
604  	
605  	      return SCIP_OKAY;
606  	   }
607  	
608  	   nfixednonzeros = 0;
609  	   lastFixedNonzero = -1;
610  	   vars = consdata->vars;
611  	   lastzero = consdata->nvars;
612  	   localnremovedvars = 0;
613  	
614  	   /* check for variables fixed to 0 and bounds that guarantee a variable to be nonzero; downward loop is important */
615  	   for( j = consdata->nvars - 1; j >= 0; --j )
616  	   {
617  	      SCIP_VAR* var;
618  	      SCIP_Real lb;
619  	      SCIP_Real ub;
620  	      SCIP_Real scalar;
621  	      SCIP_Real constant;
622  	
623  	      /* check that our vars array is still correct */
624  	      assert(vars == consdata->vars);
625  	
626  	      scalar = 1.0;
627  	      constant = 0.0;
628  	
629  	      /* check aggregation: if the constant is zero, the variable is zero iff the aggregated variable is 0 */
630  	      var = vars[j];
631  	      SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) );
632  	
633  	      /* if constant is zero and we get a different variable, substitute variable */
634  	      if ( SCIPisZero(scip, constant) && ! SCIPisZero(scip, scalar) && var != vars[j] )
635  	      {
636  	         SCIPdebugMsg(scip, "substituted variable <%s> by <%s>.\n", SCIPvarGetName(vars[j]), SCIPvarGetName(var));
637  	         SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[j], EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, -1) );
638  	         SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) );
639  	
640  	         /* change the rounding locks */
641  	         SCIP_CALL( unlockVariableSOS2(scip, cons, consdata->vars[j]) );
642  	         SCIP_CALL( lockVariableSOS2(scip, cons, var) );
643  	
644  	         vars[j] = var;
645  	      }
646  	
647  	      /* get bounds */
648  	      lb = SCIPvarGetLbLocal(vars[j]);
649  	      ub = SCIPvarGetUbLocal(vars[j]);
650  	
651  	      /* if the variable if fixed to nonzero */
652  	      if ( SCIPisFeasPositive(scip, lb) || SCIPisFeasNegative(scip, ub) )
653  	      {
654  	         ++nfixednonzeros;
655  	
656  	         /* two variables certain to be nonzero which are not next to each other, so we are infeasible */
657  	         if( lastFixedNonzero != -1 && lastFixedNonzero != j + 1 )
658  	         {
659  	            SCIPdebugMsg(scip, "The problem is infeasible: two non-consecutive variables have bounds that keep them from being 0.\n");
660  	            *cutoff = TRUE;
661  	            return SCIP_OKAY;
662  	         }
663  	
664  	         /* if more than two variables are fixed to be nonzero, we are infeasible */
665  	         if( nfixednonzeros > 2 )
666  	         {
667  	            SCIPdebugMsg(scip, "The problem is infeasible: more than two variables have bounds that keep them from being 0.\n");
668  	            *cutoff = TRUE;
669  	            return SCIP_OKAY;
670  	         }
671  	
672  	         if( lastFixedNonzero == -1)
673  	            lastFixedNonzero = j;
674  	      }
675  	
676  	      /* if the variable is fixed to 0 we may delete it from our constraint */
677  	      if( SCIPisFeasZero(scip, lb) && SCIPisFeasZero(scip, ub) )
678  	      {
679  	         /* all rear variables fixed to 0 can be deleted */
680  	         if( j == consdata->nvars - 1 )
681  	         {
682  	            ++(*nremovedvars);
683  	
684  	            SCIPdebugMsg(scip, "deleting variable <%s> fixed to 0.\n", SCIPvarGetName(vars[j]));
685  	            SCIP_CALL( deleteVarSOS2(scip, cons, consdata, eventhdlr, j) );
686  	
687  	            *success = TRUE;
688  	         }
689  	         /* remember position of last variable for which all up front and this one are fixed to 0 */
690  	         else if( lastzero > j + 1 )
691  	            lastzero = j;
692  	      }
693  	      else
694  	         lastzero = consdata->nvars;
695  	   }
696  	
697  	   /* check that our vars array is still correct */
698  	   assert(vars == consdata->vars);
699  	
700  	   /* remove first "lastzero" many variables, that are already fixed to 0 */
701  	   if( lastzero < consdata->nvars )
702  	   {
703  	      assert(lastzero >= 0);
704  	
705  	      for( j = lastzero; j >= 0; --j )
706  	      {
707  	         /* the variables should all be fixed to zero */
708  	         assert(SCIPisFeasZero(scip, SCIPvarGetLbGlobal(vars[j])) && SCIPisFeasZero(scip, SCIPvarGetUbGlobal(vars[j])));
709  	
710  	         SCIPdebugMsg(scip, "deleting variable <%s> fixed to 0.\n", SCIPvarGetName(vars[j]));
711  	         SCIP_CALL( deleteVarSOS2(scip, cons, consdata, eventhdlr, j) );
712  	      }
713  	      localnremovedvars += (lastzero + 1);
714  	      *success = TRUE;
715  	   }
716  	
717  	   /* check that our variable array is still correct */
718  	   assert(vars == consdata->vars);
719  	
720  	   *nremovedvars += localnremovedvars;
721  	
722  	   /* we might need to correct the position of the first variable which is certain to be not zero */
723  	   if( lastFixedNonzero >= 0 )
724  	   {
725  	      lastFixedNonzero -= localnremovedvars;
726  	      assert(0 <= lastFixedNonzero && lastFixedNonzero < consdata->nvars);
727  	      assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero])) || SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero])));
728  	   }
729  	
730  	   /* if the number of variables is at most 2 */
731  	   if( consdata->nvars <= 2 )
732  	   {
733  	      SCIPdebugMsg(scip, "Deleting constraint with <= 2 variables.\n");
734  	
735  	      /* delete constraint */
736  	      assert( ! SCIPconsIsModifiable(cons) );
737  	      SCIP_CALL( SCIPdelCons(scip, cons) );
738  	      ++(*ndelconss);
739  	      *success = TRUE;
740  	
741  	      return SCIP_OKAY;
742  	   }
743  	
744  	   oldnfixedvars = *nfixedvars;
745  	
746  	   /* if there is exactly one fixed nonzero variable */
747  	   if ( nfixednonzeros == 1 )
748  	   {
749  	      assert(0 <= lastFixedNonzero && lastFixedNonzero < consdata->nvars);
750  	      assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero])) ||
751  	         SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero])));
752  	
753  	      /* fix all other variables with distance two to zero */
754  	      for( j = 0; j < lastFixedNonzero - 1; ++j )
755  	      {
756  	         SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j]));
757  	         SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) );
758  	
759  	         if( infeasible )
760  	         {
761  	            *cutoff = TRUE;
762  	            return SCIP_OKAY;
763  	         }
764  	
765  	         if ( fixed )
766  	            ++(*nfixedvars);
767  	      }
768  	      for( j = lastFixedNonzero + 2; j < consdata->nvars; ++j )
769  	      {
770  	         SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j]));
771  	         SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) );
772  	
773  	         if( infeasible )
774  	         {
775  	            *cutoff = TRUE;
776  	            return SCIP_OKAY;
777  	         }
778  	
779  	         if ( fixed )
780  	            ++(*nfixedvars);
781  	      }
782  	
783  	      if( *nfixedvars > oldnfixedvars )
784  	         *success = TRUE;
785  	   }
786  	   /* if there are exactly two fixed nonzero variables */
787  	   else if ( nfixednonzeros == 2 )
788  	   {
789  	      assert(0 < lastFixedNonzero && lastFixedNonzero < consdata->nvars);
790  	      assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero])) ||
791  	         SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero])));
792  	      /* the previous variable need also to be nonzero, otherwise the infeasibility should have been detected earlier */
793  	      assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero - 1])) ||
794  	         SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero - 1])));
795  	
796  	      /* fix all variables before lastFixedNonzero to zero */
797  	      for( j = 0; j < lastFixedNonzero - 1; ++j )
798  	      {
799  	         SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j]));
800  	         SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) );
801  	
802  	         if( infeasible )
803  	         {
804  	            *cutoff = TRUE;
805  	            return SCIP_OKAY;
806  	         }
807  	         if ( fixed )
808  	            ++(*nfixedvars);
809  	      }
810  	      /* fix all variables after lastFixedNonzero + 1 to zero */
811  	      for( j = lastFixedNonzero + 1; j < consdata->nvars; ++j )
812  	      {
813  	         SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j]));
814  	         SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) );
815  	
816  	         if( infeasible )
817  	         {
818  	            *cutoff = TRUE;
819  	            return SCIP_OKAY;
820  	         }
821  	         if ( fixed )
822  	            ++(*nfixedvars);
823  	      }
824  	
825  	      /* delete constraint */
826  	      assert( ! SCIPconsIsModifiable(cons) );
827  	      SCIP_CALL( SCIPdelCons(scip, cons) );
828  	      ++(*ndelconss);
829  	      *success = TRUE;
830  	   }
831  	
832  	   return SCIP_OKAY;
833  	}
834  	
835  	
836  	/** propagate variables */
837  	static
838  	SCIP_RETCODE propSOS2(
839  	   SCIP*                 scip,               /**< SCIP pointer */
840  	   SCIP_CONS*            cons,               /**< constraint */
841  	   SCIP_CONSDATA*        consdata,           /**< constraint data */
842  	   SCIP_Bool*            cutoff,             /**< whether a cutoff happened */
843  	   int*                  ngen                /**< pointer to incremental counter for domain changes */
844  	   )
845  	{
846  	   int ngenold;
847  	
848  	   assert( scip != NULL );
849  	   assert( cons != NULL );
850  	   assert( consdata != NULL );
851  	   assert( cutoff != NULL );
852  	   assert( ngen != NULL );
853  	
854  	   *cutoff = FALSE;
855  	   ngenold = *ngen;
856  	
857  	   /* if more than two variables are fixed to be nonzero */
858  	   if ( consdata->nfixednonzeros > 2 )
859  	   {
860  	      SCIPdebugMsg(scip, "the node is infeasible, more than 2 variables are fixed to be nonzero.\n");
861  	      SCIP_CALL( SCIPresetConsAge(scip, cons) );
862  	      *cutoff = TRUE;
863  	      return SCIP_OKAY;
864  	   }
865  	
866  	   /* if exactly one variable is fixed to be nonzero */
867  	   if ( consdata->nfixednonzeros == 1 )
868  	   {
869  	      SCIP_VAR** vars;
870  	      SCIP_Bool infeasible;
871  	      SCIP_Bool tightened;
872  	      SCIP_Bool success;
873  	      int firstFixedNonzero;
874  	      int nvars;
875  	      int j;
876  	
877  	      firstFixedNonzero = -1;
878  	      nvars = consdata->nvars;
879  	      vars = consdata->vars;
880  	      assert( vars != NULL );
881  	
882  	      /* search nonzero variable */
883  	      for (j = 0; j < nvars; ++j)
884  	      {
885  	         if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) )
886  	         {
887  	            firstFixedNonzero = j;
888  	            break;
889  	         }
890  	      }
891  	      assert( firstFixedNonzero >= 0 );
892  	
893  	      SCIPdebugMsg(scip, "variable <%s> is nonzero, fixing variables with distance at least 2 to 0.\n", SCIPvarGetName(vars[firstFixedNonzero]));
894  	
895  	      /* fix variables before firstFixedNonzero-1 to 0 */
896  	      for (j = 0; j < firstFixedNonzero-1; ++j)
897  	      {
898  	         /* fix variable */
899  	         SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
900  	         assert( ! infeasible );
901  	
902  	         if ( tightened )
903  	            ++(*ngen);
904  	      }
905  	
906  	      /* fix variables after firstFixedNonzero+1 to 0 */
907  	      for (j = firstFixedNonzero+2; j < nvars; ++j)
908  	      {
909  	         /* fix variable */
910  	         SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
911  	
912  	         /* no variable after firstFixedNonzero+1 should be fixed to be nonzero */
913  	         if ( infeasible )
914  	         {
915  	            assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) );
916  	            SCIPdebugMsg(scip, "the node is infeasible: variable <%s> is fixed nonzero and variable <%s> with distance at least 2 as well.\n",
917  	               SCIPvarGetName(vars[firstFixedNonzero]), SCIPvarGetName(vars[j]));
918  	            *cutoff = TRUE;
919  	            return SCIP_OKAY;
920  	         }
921  	
922  	         if ( tightened )
923  	            ++(*ngen);
924  	      }
925  	      /* cannot locally delete constraint, since position of second entry is not fixed! */
926  	   } /*lint !e438*/
927  	   /* if exactly two variables are fixed to be nonzero */
928  	   else if ( consdata->nfixednonzeros == 2 )
929  	   {
930  	      SCIP_VAR** vars;
931  	      SCIP_Bool infeasible;
932  	      SCIP_Bool tightened;
933  	      SCIP_Bool success;
934  	      SCIP_Bool allVarFixed;
935  	      int firstFixedNonzero;
936  	      int nvars;
937  	      int j;
938  	
939  	      firstFixedNonzero = -1;
940  	      nvars = consdata->nvars;
941  	      vars = consdata->vars;
942  	      assert( vars != NULL );
943  	
944  	      /* search nonzero variable */
945  	      for (j = 0; j < nvars; ++j)
946  	      {
947  	         if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) )
948  	         {
949  	            firstFixedNonzero = j;
950  	            break;
951  	         }
952  	      }
953  	      assert( 0 <= firstFixedNonzero && firstFixedNonzero < nvars-1 );
954  	
955  	      SCIPdebugMsg(scip, "variable <%s> is fixed to be nonzero, fixing variables to 0.\n", SCIPvarGetName(vars[firstFixedNonzero]));
956  	
957  	      /* fix variables before firstFixedNonzero to 0 */
958  	      allVarFixed = TRUE;
959  	      for (j = 0; j < firstFixedNonzero; ++j)
960  	      {
961  	         /* fix variable */
962  	         SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero+1, &infeasible, &tightened, &success) );
963  	         assert( ! infeasible );
964  	         allVarFixed = allVarFixed && success;
965  	         if ( tightened )
966  	            ++(*ngen);
967  	      }
968  	
969  	      /* fix variables after firstFixedNonzero+1 to 0 */
970  	      for (j = firstFixedNonzero+2; j < nvars; ++j)
971  	      {
972  	         /* fix variable */
973  	         SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
974  	
975  	         /* no variable after firstFixedNonzero+1 should be fixed to be nonzero */
976  	         if ( infeasible )
977  	         {
978  	            assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) );
979  	            SCIPdebugMsg(scip, "the node is infeasible: variable <%s> is fixed nonzero and variable <%s> with distance at least 2 as well.\n",
980  	               SCIPvarGetName(vars[firstFixedNonzero]), SCIPvarGetName(vars[j]));
981  	            *cutoff = TRUE;
982  	            return SCIP_OKAY;
983  	         }
984  	         allVarFixed = allVarFixed && success;
985  	
986  	         if ( tightened )
987  	            ++(*ngen);
988  	      }
989  	
990  	      /* delete constraint locally, since the nonzero positions are fixed */
991  	      if ( allVarFixed )
992  	      {
993  	         SCIPdebugMsg(scip, "locally deleting constraint <%s>.\n", SCIPconsGetName(cons));
994  	         assert( !SCIPconsIsModifiable(cons) );
995  	         SCIP_CALL( SCIPdelConsLocal(scip, cons) );
996  	      }
997  	   }
998  	
999  	   /* reset constraint age counter */
1000 	   if ( *ngen > ngenold )
1001 	      SCIP_CALL( SCIPresetConsAge(scip, cons) );
1002 	
1003 	   return SCIP_OKAY;
1004 	}
1005 	
1006 	
1007 	/** enforcement method
1008 	 *
1009 	 *  We check whether the current solution is feasible, i.e., contains
1010 	 *  at most one nonzero variable. If not, we branch along the lines
1011 	 *  indicated by Beale and Tomlin:
1012 	 *
1013 	 *  We first compute \f$W = \sum_{j=1}^n |x_i|\f$ and \f$w =
1014 	 *  \sum_{j=1}^n j\, |x_i|\f$. Then we search for the index \f$k\f$ that
1015 	 *  satisfies
1016 	 *  \f[
1017 	 *        k \leq \frac{w}{W} < k+1.
1018 	 *  \f]
1019 	 *  The branches are then
1020 	 *  \f[
1021 	 *        x_1 = 0, \ldots, x_{k-1} = 0 \qquad \mbox{and}\qquad
1022 	 *        x_{k+1} = 0, \ldots, x_n = 0.
1023 	 *  \f]
1024 	 *
1025 	 *  There is one special case that we have to consider: It can happen
1026 	 *  that \f$k\f$ is one too small. Example: \f$x_1 = 1 - \epsilon, x_2
1027 	 *  = 0, x_3 = \epsilon\f$. Then \f$w = 1 - \epsilon + 3 \epsilon = 1
1028 	 *  + 2 \epsilon\f$. This yields \f$k = 1\f$ and hence the first
1029 	 *  branch does not change the solution. We therefore increase \f$k\f$
1030 	 *  by one if \f$x_k \neq 0\f$. This is valid, since we know that
1031 	 *  \f$x_{k+1} \neq 0\f$ (with respect to the original \f$k\f$); the
1032 	 *  corresponding branch will cut off the current solution, since
1033 	 *  \f$x_k \neq 0\f$.
1034 	 */
1035 	static
1036 	SCIP_RETCODE enforceSOS2(
1037 	   SCIP*                 scip,               /**< SCIP pointer */
1038 	   SCIP_CONSHDLR*        conshdlr,           /**< constraint handler */
1039 	   int                   nconss,             /**< number of constraints */
1040 	   SCIP_CONS**           conss,              /**< indicator constraints */
1041 	   SCIP_SOL*             sol,                /**< solution to be enforced (NULL for LP solution) */
1042 	   SCIP_RESULT*          result              /**< result */
1043 	   )
1044 	{
1045 	   SCIP_CONSDATA* consdata;
1046 	   SCIP_Bool infeasible;
1047 	   SCIP_NODE* node1;
1048 	   SCIP_NODE* node2;
1049 	   SCIP_CONS* branchCons = NULL;
1050 	   SCIP_VAR** vars;
1051 	   SCIP_Real nodeselest;
1052 	   SCIP_Real objest;
1053 	   int nvars;
1054 	   int maxNonzeros;
1055 	   int maxInd;
1056 	   int j;
1057 	   int c;
1058 	
1059 	   assert( scip != NULL );
1060 	   assert( conshdlr != NULL );
1061 	   assert( conss != NULL );
1062 	   assert( result != NULL );
1063 	
1064 	   maxNonzeros = 0;
1065 	   maxInd = -1;
1066 	
1067 	   SCIPdebugMsg(scip, "Enforcing SOS2 constraints <%s>.\n", SCIPconshdlrGetName(conshdlr) );
1068 	   *result = SCIP_FEASIBLE;
1069 	
1070 	   /* check each constraint */
1071 	   for (c = 0; c < nconss; ++c)
1072 	   {
1073 	      SCIP_CONS* cons;
1074 	      SCIP_Bool cutoff;
1075 	      SCIP_Real weight1;
1076 	      SCIP_Real weight2;
1077 	      SCIP_Real w;
1078 	      int lastNonzero;
1079 	      int ngen;
1080 	      int cnt;
1081 	      int ind;
1082 	
1083 	      cons = conss[c];
1084 	      assert( cons != NULL );
1085 	
1086 	      consdata = SCIPconsGetData(cons);
1087 	      assert( consdata != NULL );
1088 	
1089 	      nvars = consdata->nvars;
1090 	      vars = consdata->vars;
1091 	
1092 	      /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
1093 	      if ( nvars <= 2 )
1094 	         return SCIP_OKAY;
1095 	
1096 	      ngen = 0;
1097 	
1098 	      /* first perform propagation (it might happen that standard propagation is turned off) */
1099 	      SCIP_CALL( propSOS2(scip, cons, consdata, &cutoff, &ngen) );
1100 	      SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen);
1101 	      if ( cutoff )
1102 	      {
1103 	         *result = SCIP_CUTOFF;
1104 	         return SCIP_OKAY;
1105 	      }
1106 	      if ( ngen > 0 )
1107 	      {
1108 	         *result = SCIP_REDUCEDDOM;
1109 	         return SCIP_OKAY;
1110 	      }
1111 	
1112 	      cnt = 0;
1113 	      weight1 = 0.0;
1114 	      weight2 = 0.0;
1115 	      lastNonzero = -1;
1116 	
1117 	      /* compute weight */
1118 	      for (j = 0; j < nvars; ++j)
1119 	      {
1120 	         SCIP_Real val;
1121 	
1122 	         val = REALABS(SCIPgetSolVal(scip, sol, vars[j]));
1123 	         weight1 += val * (SCIP_Real) j;
1124 	         weight2 += val;
1125 	
1126 	         if ( ! SCIPisFeasZero(scip, val) )
1127 	         {
1128 	            lastNonzero = j;
1129 	            ++cnt;
1130 	         }
1131 	      }
1132 	
1133 	      /* if at most one variable is nonzero, the constraint is feasible */
1134 	      if ( cnt < 2 )
1135 	         continue;
1136 	
1137 	      /* if two adjacent variables are nonzero */
1138 	      assert( 0 < lastNonzero && lastNonzero < nvars );
1139 	      if ( cnt == 2 && ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[lastNonzero-1])) )
1140 	         continue;
1141 	
1142 	      assert( !SCIPisFeasZero(scip, weight2) );
1143 	      w = weight1/weight2;  /*lint !e795*/
1144 	
1145 	      ind = (int) SCIPfeasFloor(scip, w);
1146 	      assert( 0 <= ind && ind < nvars-1 );
1147 	
1148 	      /* correct index if necessary - see above for an explanation */
1149 	      if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[ind])) && ind < lastNonzero-1 )
1150 	         ++ind;
1151 	
1152 	      /* check if the constraint has more nonzeros */
1153 	      if ( cnt > maxNonzeros )
1154 	      {
1155 	         maxNonzeros = cnt;
1156 	         branchCons = cons;
1157 	         maxInd = ind;
1158 	      }
1159 	   }
1160 	
1161 	   /* if all constraints are feasible */
1162 	   if ( branchCons == NULL )
1163 	   {
1164 	      SCIPdebugMsg(scip, "All SOS2 constraints are feasible.\n");
1165 	      return SCIP_OKAY;
1166 	   }
1167 	
1168 	   /* create branches */
1169 	   consdata = SCIPconsGetData(branchCons);
1170 	   assert( consdata != NULL );
1171 	   nvars = consdata->nvars;
1172 	   vars = consdata->vars;
1173 	
1174 	   assert( 0 < maxInd && maxInd < nvars-1 );
1175 	
1176 	   /* branch on variable ind: either all variables before ind or all variables after ind are zero */
1177 	   SCIPdebugMsg(scip, "Branching on variable <%s> in constraint <%s> (nonzeros: %d).\n", SCIPvarGetName(vars[maxInd]),
1178 	      SCIPconsGetName(branchCons), maxNonzeros);
1179 	
1180 	   /* calculate node selection and objective estimate for node 1 */
1181 	   nodeselest = 0.0;
1182 	   objest = SCIPgetLocalTransEstimate(scip);
1183 	   for (j = 0; j < maxInd; ++j)
1184 	   {
1185 	      objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0);
1186 	      nodeselest += SCIPcalcNodeselPriority(scip, vars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1187 	   }
1188 	   assert( objest >= SCIPgetLocalTransEstimate(scip) );
1189 	
1190 	   /* create node 1 */
1191 	   SCIP_CALL( SCIPcreateChild(scip, &node1, nodeselest, objest) );
1192 	
1193 	   for (j = 0; j < maxInd; ++j)
1194 	   {
1195 	      SCIP_CALL( fixVariableZeroNode(scip, vars[j], node1, &infeasible) );
1196 	      assert( ! infeasible );
1197 	   }
1198 	
1199 	   /* calculate node selection and objective estimate for node 2 */
1200 	   nodeselest = 0.0;
1201 	   objest = SCIPgetLocalTransEstimate(scip);
1202 	   for (j = maxInd+1; j < nvars; ++j)
1203 	   {
1204 	      objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0);
1205 	      nodeselest += SCIPcalcNodeselPriority(scip, vars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1206 	   }
1207 	   assert( objest >= SCIPgetLocalTransEstimate(scip) );
1208 	
1209 	   /* create node 2 */
1210 	   SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) );
1211 	   for (j = maxInd+1; j < nvars; ++j)
1212 	   {
1213 	      SCIP_CALL( fixVariableZeroNode(scip, vars[j], node2, &infeasible) );
1214 	      assert( ! infeasible );
1215 	   }
1216 	   SCIP_CALL( SCIPresetConsAge(scip, branchCons) );
1217 	   *result = SCIP_BRANCHED;
1218 	
1219 	   return SCIP_OKAY;
1220 	}
1221 	
1222 	
1223 	/** Generate basic row
1224 	 *
1225 	 *  We generate the row corresponding to the following simple valid
1226 	 *  inequalities. Let \f$U\f$ and \f$U'\f$ be the largest and second
1227 	 *  largest upper bound of variables appearing in the
1228 	 *  constraint. Similarly let \f$L\f$ and \f$L'\f$ be the smallest and
1229 	 *  second smallest lower bound. The inequalities are:
1230 	 *  \f[
1231 	 *        x_1 + \ldots + x_n \leq U + U' \qquad\mbox{and}\qquad
1232 	 *        x_1 + \ldots + x_n \geq L + L'.
1233 	 *  \f]
1234 	 *  Of course, these inequalities are only added if the upper and
1235 	 *  lower bounds are all finite and \f$L+L' < 0\f$ or \f$U+U' > 0\f$.
1236 	 */
1237 	static
1238 	SCIP_RETCODE generateRowSOS2(
1239 	   SCIP*                 scip,               /**< SCIP pointer */
1240 	   SCIP_CONSHDLR*        conshdlr,           /**< constraint handler */
1241 	   SCIP_CONS*            cons,               /**< constraint */
1242 	   SCIP_Bool             local               /**< produce local cut? */
1243 	   )
1244 	{
1245 	   char name[SCIP_MAXSTRLEN];
1246 	   SCIP_CONSDATA* consdata;
1247 	   SCIP_VAR** vars;
1248 	   SCIP_Real minLb = SCIPinfinity(scip);
1249 	   SCIP_Real minLb2 = SCIPinfinity(scip);
1250 	   SCIP_Real maxUb = -SCIPinfinity(scip);
1251 	   SCIP_Real maxUb2 = -SCIPinfinity(scip);
1252 	   SCIP_Real lhs;
1253 	   SCIP_Real rhs;
1254 	   SCIP_ROW* row;
1255 	   int nvars;
1256 	   int j;
1257 	
1258 	   assert( scip != NULL );
1259 	   assert( conshdlr != NULL );
1260 	   assert( cons != NULL );
1261 	
1262 	   consdata = SCIPconsGetData(cons);
1263 	   assert( consdata != NULL );
1264 	   assert( consdata->row == NULL );
1265 	
1266 	   nvars = consdata->nvars;
1267 	   vars = consdata->vars;
1268 	   assert( vars != NULL );
1269 	
1270 	   /* find minimum and maximum lower and upper bounds */
1271 	   for (j = 0; j < nvars; ++j)
1272 	   {
1273 	      SCIP_Real val;
1274 	
1275 	      if ( local )
1276 	         val = SCIPvarGetLbLocal(vars[j]);
1277 	      else
1278 	         val = SCIPvarGetLbGlobal(vars[j]);
1279 	
1280 	      if ( val < minLb )
1281 	      {
1282 	         minLb2 = minLb;
1283 	         minLb = val;
1284 	      }
1285 	      else
1286 	      {
1287 	         if ( val < minLb2 )
1288 	            minLb2 = val;
1289 	      }
1290 	
1291 	      if ( local )
1292 	         val = SCIPvarGetUbLocal(vars[j]);
1293 	      else
1294 	         val = SCIPvarGetUbGlobal(vars[j]);
1295 	
1296 	      if ( val > maxUb )
1297 	      {
1298 	         maxUb2 = maxUb;
1299 	         maxUb = val;
1300 	      }
1301 	      else
1302 	      {
1303 	         if ( val > maxUb2 )
1304 	            maxUb2 = val;
1305 	      }
1306 	   }
1307 	   lhs = minLb + minLb2;
1308 	   rhs = maxUb + maxUb2;
1309 	
1310 	   /* ignore trivial inequality if left hand side would be 0 */
1311 	   if ( SCIPisFeasZero(scip, lhs) )
1312 	      lhs = -SCIPinfinity(scip);
1313 	
1314 	   /* ignore trivial inequality if right hand side would be 0 */
1315 	   if ( SCIPisFeasZero(scip, rhs) )
1316 	      rhs = SCIPinfinity(scip);
1317 	
1318 	   /* create upper and lower bound inequality if one of the bounds is finite */
1319 	   if ( ! SCIPisInfinity(scip, REALABS(lhs)) || ! SCIPisInfinity(scip, REALABS(rhs)) )
1320 	   {
1321 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sos2bnd#%s", SCIPconsGetName(cons));
1322 	      SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, lhs, rhs, local, FALSE, FALSE) );
1323 	      SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, row, nvars, vars, 1.0) );
1324 	      consdata->row = row;
1325 	
1326 	      SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
1327 	   }
1328 	
1329 	   return SCIP_OKAY;
1330 	}
1331 	
1332 	
1333 	/* ---------------------------- constraint handler callback methods ----------------------*/
1334 	
1335 	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1336 	static
1337 	SCIP_DECL_CONSHDLRCOPY(conshdlrCopySOS2)
1338 	{  /*lint --e{715}*/
1339 	   assert( scip != NULL );
1340 	   assert( conshdlr != NULL );
1341 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1342 	
1343 	   /* call inclusion method of constraint handler */
1344 	   SCIP_CALL( SCIPincludeConshdlrSOS2(scip) );
1345 	
1346 	   *valid = TRUE;
1347 	
1348 	   return SCIP_OKAY;
1349 	}
1350 	
1351 	
1352 	/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1353 	static
1354 	SCIP_DECL_CONSFREE(consFreeSOS2)
1355 	{
1356 	   SCIP_CONSHDLRDATA* conshdlrdata;
1357 	
1358 	   assert( scip != NULL );
1359 	   assert( conshdlr != NULL );
1360 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1361 	
1362 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
1363 	   assert(conshdlrdata != NULL);
1364 	
1365 	   SCIPfreeBlockMemory(scip, &conshdlrdata);
1366 	
1367 	   return SCIP_OKAY;
1368 	}
1369 	
1370 	
1371 	/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
1372 	static
1373 	SCIP_DECL_CONSEXITSOL(consExitsolSOS2)
1374 	{  /*lint --e{715}*/
1375 	   int c;
1376 	
1377 	   assert( scip != NULL );
1378 	   assert( conshdlr != NULL );
1379 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1380 	
1381 	   /* check each constraint */
1382 	   for (c = 0; c < nconss; ++c)
1383 	   {
1384 	      SCIP_CONSDATA* consdata;
1385 	
1386 	      assert( conss != NULL );
1387 	      assert( conss[c] != NULL );
1388 	      consdata = SCIPconsGetData(conss[c]);
1389 	      assert( consdata != NULL );
1390 	
1391 	      SCIPdebugMsg(scip, "Exiting SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
1392 	
1393 	      /* free row */
1394 	      if ( consdata->row != NULL )
1395 	      {
1396 	         SCIP_CALL( SCIPreleaseRow(scip, &consdata->row) );
1397 	      }
1398 	   }
1399 	   return SCIP_OKAY;
1400 	}
1401 	
1402 	
1403 	/** frees specific constraint data */
1404 	static
1405 	SCIP_DECL_CONSDELETE(consDeleteSOS2)
1406 	{
1407 	   assert( scip != NULL );
1408 	   assert( conshdlr != NULL );
1409 	   assert( cons != NULL );
1410 	   assert( consdata != NULL );
1411 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1412 	
1413 	   SCIPdebugMsg(scip, "Deleting SOS2 constraint <%s>.\n", SCIPconsGetName(cons) );
1414 	
1415 	   /* drop events on transformed variables */
1416 	   if ( SCIPconsIsTransformed(cons) )
1417 	   {
1418 	      SCIP_CONSHDLRDATA* conshdlrdata;
1419 	      int j;
1420 	
1421 	      /* get constraint handler data */
1422 	      conshdlrdata = SCIPconshdlrGetData(conshdlr);
1423 	      assert( conshdlrdata != NULL );
1424 	      assert( conshdlrdata->eventhdlr != NULL );
1425 	
1426 	      for (j = 0; j < (*consdata)->nvars; ++j)
1427 	      {
1428 	         SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[j], EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr,
1429 	               (SCIP_EVENTDATA*)cons, -1) );
1430 	      }
1431 	   }
1432 	
1433 	   SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->maxvars);
1434 	   if ( (*consdata)->weights != NULL )
1435 	   {
1436 	      SCIPfreeBlockMemoryArray(scip, &(*consdata)->weights, (*consdata)->maxvars);
1437 	   }
1438 	
1439 	   /* free row */
1440 	   if ( (*consdata)->row != NULL )
1441 	   {
1442 	      SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
1443 	   }
1444 	   assert( (*consdata)->row == NULL );
1445 	
1446 	   SCIPfreeBlockMemory(scip, consdata);
1447 	
1448 	   return SCIP_OKAY;
1449 	}
1450 	
1451 	
1452 	/** transforms constraint data into data belonging to the transformed problem */
1453 	static
1454 	SCIP_DECL_CONSTRANS(consTransSOS2)
1455 	{
1456 	   SCIP_CONSDATA* consdata;
1457 	   SCIP_CONSHDLRDATA* conshdlrdata;
1458 	   SCIP_CONSDATA* sourcedata;
1459 	   char s[SCIP_MAXSTRLEN];
1460 	   int j;
1461 	
1462 	   assert( scip != NULL );
1463 	   assert( conshdlr != NULL );
1464 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1465 	   assert( sourcecons != NULL );
1466 	   assert( targetcons != NULL );
1467 	
1468 	   /* get constraint handler data */
1469 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
1470 	   assert( conshdlrdata != NULL );
1471 	   assert( conshdlrdata->eventhdlr != NULL );
1472 	
1473 	   SCIPdebugMsg(scip, "Transforming SOS2 constraint: <%s>.\n", SCIPconsGetName(sourcecons) );
1474 	
1475 	   /* get data of original constraint */
1476 	   sourcedata = SCIPconsGetData(sourcecons);
1477 	   assert( sourcedata != NULL );
1478 	   assert( sourcedata->nvars > 0 );
1479 	   assert( sourcedata->nvars <= sourcedata->maxvars );
1480 	
1481 	   /* create constraint data */
1482 	   SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1483 	
1484 	   consdata->nvars = sourcedata->nvars;
1485 	   consdata->maxvars = sourcedata->nvars;
1486 	   consdata->row = NULL;
1487 	   consdata->nfixednonzeros = 0;
1488 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, consdata->nvars) );
1489 	
1490 	   /* if weights were used */
1491 	   if ( sourcedata->weights != NULL )
1492 	   {
1493 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, sourcedata->weights, consdata->nvars) );
1494 	   }
1495 	   else
1496 	      consdata->weights = NULL;
1497 	
1498 	   for (j = 0; j < sourcedata->nvars; ++j)
1499 	   {
1500 	      assert( sourcedata->vars[j] != 0 );
1501 	      SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->vars[j], &(consdata->vars[j])) );
1502 	
1503 	      /* if variable is fixed to be nonzero */
1504 	      if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(consdata->vars[j])) )
1505 	         ++(consdata->nfixednonzeros);
1506 	   }
1507 	
1508 	   /* create transformed constraint with the same flags */
1509 	   (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons));
1510 	   SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
1511 	         SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1512 	         SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1513 	         SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1514 	         SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1515 	         SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1516 	
1517 	   /* catch bound change events on variable */
1518 	   for (j = 0; j < consdata->nvars; ++j)
1519 	   {
1520 	      SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[j], EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr,
1521 	            (SCIP_EVENTDATA*)*targetcons, NULL) );
1522 	   }
1523 	
1524 	#ifdef SCIP_DEBUG
1525 	   if ( consdata->nfixednonzeros > 0 )
1526 	   {
1527 	      SCIPdebugMsg(scip, "constraint <%s> has %d variables fixed to be nonzero.\n", SCIPconsGetName(*targetcons), consdata->nfixednonzeros );
1528 	   }
1529 	#endif
1530 	
1531 	   return SCIP_OKAY;
1532 	}
1533 	
1534 	
1535 	/** presolving method of constraint handler */
1536 	static
1537 	SCIP_DECL_CONSPRESOL(consPresolSOS2)
1538 	{  /*lint --e{715}*/
1539 	   SCIPdebug( int oldnfixedvars = *nfixedvars; )
1540 	   SCIPdebug( int oldndelconss = *ndelconss; )
1541 	   int nremovedvars;
1542 	   SCIP_EVENTHDLR* eventhdlr;
1543 	   int c;
1544 	
1545 	   assert( scip != NULL );
1546 	   assert( conshdlr != NULL );
1547 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1548 	   assert( result != NULL );
1549 	
1550 	   *result = SCIP_DIDNOTRUN;
1551 	   nremovedvars = 0;
1552 	
1553 	   /* only run if success is possible */
1554 	   if( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgcoefs > 0 )
1555 	   {
1556 	      /* get constraint handler data */
1557 	      assert( SCIPconshdlrGetData(conshdlr) != NULL );
1558 	      eventhdlr = SCIPconshdlrGetData(conshdlr)->eventhdlr;
1559 	      assert( eventhdlr != NULL );
1560 	
1561 	      *result = SCIP_DIDNOTFIND;
1562 	
1563 	      /* check each constraint */
1564 	      for (c = 0; c < nconss; ++c)
1565 	      {
1566 	         SCIP_CONSDATA* consdata;
1567 	         SCIP_CONS* cons;
1568 	         SCIP_Bool cutoff;
1569 	         SCIP_Bool success;
1570 	
1571 	         assert( conss != NULL );
1572 	         assert( conss[c] != NULL );
1573 	
1574 	         cons = conss[c];
1575 	         consdata = SCIPconsGetData(cons);
1576 	
1577 	         assert( consdata != NULL );
1578 	         assert( consdata->nvars >= 0 );
1579 	         assert( consdata->nvars <= consdata->maxvars );
1580 	         assert( ! SCIPconsIsModifiable(cons) );
1581 	
1582 	         /* perform one presolving round */
1583 	         SCIP_CALL( presolRoundSOS2(scip, cons, consdata, eventhdlr, &cutoff, &success, ndelconss, nfixedvars, &nremovedvars) );
1584 	
1585 	         if ( cutoff )
1586 	         {
1587 	            *result = SCIP_CUTOFF;
1588 	            return SCIP_OKAY;
1589 	         }
1590 	
1591 	         if ( success )
1592 	            *result = SCIP_SUCCESS;
1593 	      }
1594 	   }
1595 	   (*nchgcoefs) += nremovedvars;
1596 	
1597 	   SCIPdebug( SCIPdebugMsg(scip, "presolving fixed %d variables, removed %d variables, and deleted %d constraints.\n",
1598 	      *nfixedvars - oldnfixedvars, nremovedvars, *ndelconss - oldndelconss); )
1599 	
1600 	   return SCIP_OKAY;
1601 	}
1602 	
1603 	
1604 	/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1605 	static
1606 	SCIP_DECL_CONSINITLP(consInitlpSOS2)
1607 	{
1608 	   int c;
1609 	
1610 	   assert( scip != NULL );
1611 	   assert( conshdlr != NULL );
1612 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1613 	
1614 	   *infeasible = FALSE;
1615 	
1616 	   /* check each constraint */
1617 	   for (c = 0; c < nconss && !(*infeasible); ++c)
1618 	   {
1619 	      SCIP_CONSDATA* consdata;
1620 	
1621 	      assert( conss != NULL );
1622 	      assert( conss[c] != NULL );
1623 	      consdata = SCIPconsGetData(conss[c]);
1624 	      assert( consdata != NULL );
1625 	
1626 	      SCIPdebugMsg(scip, "Checking for initial rows for SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
1627 	
1628 	      /* possibly generate row if not yet done */
1629 	      if ( consdata->row == NULL )
1630 	      {
1631 	         SCIP_CALL( generateRowSOS2(scip, conshdlr, conss[c], FALSE) );
1632 	      }
1633 	
1634 	      /* put corresponding rows into LP */
1635 	      if ( consdata->row != NULL && ! SCIProwIsInLP(consdata->row) )
1636 	      {
1637 	         assert( ! SCIPisInfinity(scip, REALABS(SCIProwGetLhs(consdata->row))) || ! SCIPisInfinity(scip, REALABS(SCIProwGetRhs(consdata->row))) );
1638 	
1639 	         SCIP_CALL( SCIPaddRow(scip, consdata->row, FALSE, infeasible) );
1640 	         SCIPdebug( SCIP_CALL( SCIPprintRow(scip, consdata->row, NULL) ) );
1641 	      }
1642 	   }
1643 	
1644 	   return SCIP_OKAY;
1645 	}
1646 	
1647 	
1648 	/** separation method of constraint handler for LP solutions */
1649 	static
1650 	SCIP_DECL_CONSSEPALP(consSepalpSOS2)
1651 	{  /*lint --e{715}*/
1652 	   SCIP_Bool cutoff = FALSE;
1653 	   int c;
1654 	   int ngen = 0;
1655 	
1656 	   assert( scip != NULL );
1657 	   assert( conshdlr != NULL );
1658 	   assert( conss != NULL );
1659 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1660 	   assert( result != NULL );
1661 	
1662 	   *result = SCIP_DIDNOTRUN;
1663 	
1664 	   /* check each constraint */
1665 	   for (c = 0; c < nconss && ! cutoff; ++c)
1666 	   {
1667 	      SCIP_CONSDATA* consdata;
1668 	      SCIP_ROW* row;
1669 	
1670 	      *result = SCIP_DIDNOTFIND;
1671 	      assert( conss[c] != NULL );
1672 	      consdata = SCIPconsGetData(conss[c]);
1673 	      assert( consdata != NULL );
1674 	      SCIPdebugMsg(scip, "Separating inequalities for SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
1675 	
1676 	      /* possibly generate row if not yet done */
1677 	      if ( consdata->row == NULL )
1678 	      {
1679 	         SCIP_CALL( generateRowSOS2(scip, conshdlr, conss[c], FALSE) );
1680 	      }
1681 	
1682 	      /* put corresponding rows into LP if they are useful */
1683 	      row = consdata->row;
1684 	
1685 	      /* possibly add row to LP if it is useful */
1686 	      if ( row != NULL && ! SCIProwIsInLP(row) && SCIPisCutEfficacious(scip, NULL, row) )
1687 	      {
1688 	         SCIP_CALL( SCIPaddRow(scip, row, FALSE, &cutoff) );
1689 	         SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
1690 	         SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
1691 	         ++ngen;
1692 	      }
1693 	   }
1694 	   SCIPdebugMsg(scip, "Separated %d SOS2 constraints.\n", ngen);
1695 	   if ( cutoff )
1696 	      *result = SCIP_CUTOFF;
1697 	   else if ( ngen > 0 )
1698 	      *result = SCIP_SEPARATED;
1699 	
1700 	   return SCIP_OKAY;
1701 	}
1702 	
1703 	
1704 	/** separation method of constraint handler for arbitrary primal solutions */
1705 	static
1706 	SCIP_DECL_CONSSEPASOL(consSepasolSOS2)
1707 	{  /*lint --e{715}*/
1708 	   SCIP_Bool cutoff = FALSE;
1709 	   int c;
1710 	   int ngen = 0;
1711 	
1712 	   assert( scip != NULL );
1713 	   assert( conshdlr != NULL );
1714 	   assert( conss != NULL );
1715 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1716 	   assert( result != NULL );
1717 	
1718 	   *result = SCIP_DIDNOTRUN;
1719 	
1720 	   /* check each constraint */
1721 	   for (c = 0; c < nconss && ! cutoff; ++c)
1722 	   {
1723 	      SCIP_CONSDATA* consdata;
1724 	      SCIP_ROW* row;
1725 	
1726 	      *result = SCIP_DIDNOTFIND;
1727 	      assert( conss[c] != NULL );
1728 	      consdata = SCIPconsGetData(conss[c]);
1729 	      assert( consdata != NULL );
1730 	      SCIPdebugMsg(scip, "Separating solution for SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
1731 	
1732 	      /* put corresponding row into LP if it is useful */
1733 	      row = consdata->row;
1734 	
1735 	      /* possibly generate row if not yet done */
1736 	      if ( row == NULL )
1737 	      {
1738 	         SCIP_CALL( generateRowSOS2(scip, conshdlr, conss[c], FALSE) );
1739 	      }
1740 	
1741 	      /* possibly add row to LP if it is useful */
1742 	      if ( row != NULL && ! SCIProwIsInLP(row) && SCIPisCutEfficacious(scip, sol, row) )
1743 	      {
1744 	         SCIP_CALL( SCIPaddRow(scip, row, FALSE, &cutoff) );
1745 	         SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
1746 	         SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
1747 	         ++ngen;
1748 	      }
1749 	   }
1750 	   SCIPdebugMsg(scip, "Separated %d SOS2 constraints.\n", ngen);
1751 	   if ( cutoff )
1752 	      *result = SCIP_CUTOFF;
1753 	   else if ( ngen > 0 )
1754 	      *result = SCIP_SEPARATED;
1755 	
1756 	   return SCIP_OKAY;
1757 	}
1758 	
1759 	
1760 	/** constraint enforcing method of constraint handler for LP solutions */
1761 	static
1762 	SCIP_DECL_CONSENFOLP(consEnfolpSOS2)
1763 	{  /*lint --e{715}*/
1764 	   assert( scip != NULL );
1765 	   assert( conshdlr != NULL );
1766 	   assert( conss != NULL );
1767 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1768 	   assert( result != NULL );
1769 	
1770 	   SCIP_CALL( enforceSOS2(scip, conshdlr, nconss, conss, NULL, result) );
1771 	
1772 	   return SCIP_OKAY;
1773 	}
1774 	
1775 	
1776 	/** constraint enforcing method of constraint handler for relaxation solutions */
1777 	static
1778 	SCIP_DECL_CONSENFORELAX(consEnforelaxSOS2)
1779 	{  /*lint --e{715}*/
1780 	   assert( scip != NULL );
1781 	   assert( conshdlr != NULL );
1782 	   assert( conss != NULL );
1783 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1784 	   assert( result != NULL );
1785 	
1786 	   SCIP_CALL( enforceSOS2(scip, conshdlr, nconss, conss, sol, result) );
1787 	
1788 	   return SCIP_OKAY;
1789 	}
1790 	
1791 	
1792 	/** constraint enforcing method of constraint handler for pseudo solutions */
1793 	static
1794 	SCIP_DECL_CONSENFOPS(consEnfopsSOS2)
1795 	{  /*lint --e{715}*/
1796 	   assert( scip != NULL );
1797 	   assert( conshdlr != NULL );
1798 	   assert( conss != NULL );
1799 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1800 	   assert( result != NULL );
1801 	
1802 	   SCIP_CALL( enforceSOS2(scip, conshdlr, nconss, conss, NULL, result) );
1803 	
1804 	   return SCIP_OKAY;
1805 	}
1806 	
1807 	
1808 	/** feasibility check method of constraint handler for integral solutions
1809 	 *
1810 	 *  We simply check whether at most two variable are nonzero and in the
1811 	 *  case there are exactly two nonzero, then they have to be direct
1812 	 *  neighbors in the given solution.
1813 	 */
1814 	static
1815 	SCIP_DECL_CONSCHECK(consCheckSOS2)
1816 	{  /*lint --e{715}*/
1817 	   int c;
1818 	
1819 	   assert( scip != NULL );
1820 	   assert( conshdlr != NULL );
1821 	   assert( conss != NULL );
1822 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1823 	   assert( result != NULL );
1824 	
1825 	   *result = SCIP_FEASIBLE;
1826 	
1827 	   /* check each constraint */
1828 	   for (c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c)
1829 	   {
1830 	      SCIP_CONSDATA* consdata;
1831 	      int firstNonzero;
1832 	      int j;
1833 	
1834 	      firstNonzero = -1;
1835 	      assert( conss[c] != NULL );
1836 	      consdata = SCIPconsGetData(conss[c]);
1837 	      assert( consdata != NULL );
1838 	      SCIPdebugMsg(scip, "Checking SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]));
1839 	
1840 	      /* check all variables */
1841 	      for (j = 0; j < consdata->nvars; ++j)
1842 	      {
1843 	         /* if variable is nonzero */
1844 	         if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->vars[j])) )
1845 	         {
1846 	            if ( firstNonzero < 0 )
1847 	               firstNonzero = j;
1848 	            else
1849 	            {
1850 	               /* if we are more than one position away from the firstNonzero variable */
1851 	               if ( j > firstNonzero+1 )
1852 	               {
1853 	                  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
1854 	                  *result = SCIP_INFEASIBLE;
1855 	
1856 	                  /* update constraint violation in solution */
1857 	                  if ( sol != NULL )
1858 	                     SCIPupdateSolConsViolation(scip, sol, 1.0, 1.0);
1859 	
1860 	                  if ( printreason )
1861 	                  {
1862 	                     SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) );
1863 	
1864 	                     SCIPinfoMessage(scip, NULL, ";\nviolation: <%s> = %.15g and  <%s> = %.15g\n",
1865 	                        SCIPvarGetName(consdata->vars[firstNonzero]),
1866 	                        SCIPgetSolVal(scip, sol, consdata->vars[firstNonzero]),
1867 	                        SCIPvarGetName(consdata->vars[j]),
1868 	                        SCIPgetSolVal(scip, sol, consdata->vars[j]));
1869 	                  }
1870 	
1871 	                  SCIPdebugMsg(scip, "SOS2 constraint <%s> infeasible.\n", SCIPconsGetName(conss[c]));
1872 	               }
1873 	            }
1874 	         }
1875 	      }
1876 	   }
1877 	
1878 	   return SCIP_OKAY;
1879 	}
1880 	
1881 	
1882 	/** domain propagation method of constraint handler */
1883 	static
1884 	SCIP_DECL_CONSPROP(consPropSOS2)
1885 	{  /*lint --e{715}*/
1886 	   int c;
1887 	   int ngen = 0;
1888 	
1889 	   assert( scip != NULL );
1890 	   assert( conshdlr != NULL );
1891 	   assert( conss != NULL );
1892 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1893 	   assert( result != NULL );
1894 	   *result = SCIP_DIDNOTRUN;
1895 	
1896 	   assert( SCIPisTransformed(scip) );
1897 	
1898 	   /* check each constraint */
1899 	   for (c = 0; c < nconss; ++c)
1900 	   {
1901 	      SCIP_CONS* cons;
1902 	      SCIP_CONSDATA* consdata;
1903 	      SCIP_Bool cutoff;
1904 	
1905 	      assert( conss[c] != NULL );
1906 	      cons = conss[c];
1907 	      consdata = SCIPconsGetData(cons);
1908 	      assert( consdata != NULL );
1909 	      SCIPdebugMsg(scip, "Propagating SOS2 constraint <%s>.\n", SCIPconsGetName(cons) );
1910 	
1911 	      *result = SCIP_DIDNOTFIND;
1912 	      SCIP_CALL( propSOS2(scip, cons, consdata, &cutoff, &ngen) );
1913 	      if ( cutoff )
1914 	      {
1915 	         *result = SCIP_CUTOFF;
1916 	         return SCIP_OKAY;
1917 	      }
1918 	   }
1919 	   SCIPdebugMsg(scip, "Propagated %d domains.\n", ngen);
1920 	   if ( ngen > 0 )
1921 	      *result = SCIP_REDUCEDDOM;
1922 	
1923 	   return SCIP_OKAY;
1924 	}
1925 	
1926 	
1927 	/** propagation conflict resolving method of constraint handler
1928 	 *
1929 	 *  We check which bound changes were the reason for infeasibility. We
1930 	 *  use that @a inferinfo stores the index of the variable that has
1931 	 *  bounds that fix it to be nonzero (these bounds are the reason). */
1932 	static
1933 	SCIP_DECL_CONSRESPROP(consRespropSOS2)
1934 	{  /*lint --e{715}*/
1935 	   SCIP_CONSDATA* consdata;
1936 	   SCIP_VAR* var;
1937 	
1938 	   assert( scip != NULL );
1939 	   assert( cons != NULL );
1940 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1941 	   assert( infervar != NULL );
1942 	   assert( bdchgidx != NULL );
1943 	   assert( result != NULL );
1944 	
1945 	   *result = SCIP_DIDNOTFIND;
1946 	   SCIPdebugMsg(scip, "Propagation resolution method of SOS2 constraint <%s>.\n", SCIPconsGetName(cons));
1947 	
1948 	   consdata = SCIPconsGetData(cons);
1949 	   assert( consdata != NULL );
1950 	   assert( 0 <= inferinfo && inferinfo < consdata->nvars );
1951 	   var = consdata->vars[inferinfo];
1952 	   assert( var != infervar );
1953 	
1954 	   /* check if lower bound of var was the reason */
1955 	   if ( SCIPisFeasPositive(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) )
1956 	   {
1957 	      SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1958 	      *result = SCIP_SUCCESS;
1959 	   }
1960 	
1961 	   /* check if upper bound of var was the reason */
1962 	   if ( SCIPisFeasNegative(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)) )
1963 	   {
1964 	      SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
1965 	      *result = SCIP_SUCCESS;
1966 	   }
1967 	
1968 	   return SCIP_OKAY;
1969 	}
1970 	
1971 	
1972 	/** variable rounding lock method of constraint handler
1973 	 *
1974 	 *  Let lb and ub be the lower and upper bounds of a
1975 	 *  variable. Preprocessing usually makes sure that lb <= 0 <= ub.
1976 	 *
1977 	 *  - If lb < 0 then rounding down may violate the constraint.
1978 	 *  - If ub > 0 then rounding up may violated the constraint.
1979 	 *  - If lb > 0 or ub < 0 then the constraint is infeasible and we do
1980 	 *    not have to deal with it here.
1981 	 *  - If lb == 0 then rounding down does not violate the constraint.
1982 	 *  - If ub == 0 then rounding up does not violate the constraint.
1983 	 */
1984 	static
1985 	SCIP_DECL_CONSLOCK(consLockSOS2)
1986 	{
1987 	   SCIP_CONSDATA* consdata;
1988 	   SCIP_VAR** vars;
1989 	   int nvars;
1990 	   int j;
1991 	
1992 	   assert( scip != NULL );
1993 	   assert( conshdlr != NULL );
1994 	   assert( cons != NULL );
1995 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1996 	   assert(locktype == SCIP_LOCKTYPE_MODEL);
1997 	
1998 	   consdata = SCIPconsGetData(cons);
1999 	   assert( consdata != NULL );
2000 	
2001 	   SCIPdebugMsg(scip, "Locking constraint <%s>.\n", SCIPconsGetName(cons));
2002 	
2003 	   vars = consdata->vars;
2004 	   nvars = consdata->nvars;
2005 	   assert( vars != NULL );
2006 	
2007 	   for (j = 0; j < nvars; ++j)
2008 	   {
2009 	      SCIP_VAR* var;
2010 	      var = vars[j];
2011 	
2012 	      /* if lower bound is negative, rounding down may violate constraint */
2013 	      if ( SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)) )
2014 	         SCIP_CALL( SCIPaddVarLocksType(scip, var, locktype, nlockspos, nlocksneg) );
2015 	
2016 	      /* additionally: if upper bound is positive, rounding up may violate constraint */
2017 	      if ( SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var)) )
2018 	         SCIP_CALL( SCIPaddVarLocksType(scip, var, locktype, nlocksneg, nlockspos) );
2019 	   }
2020 	
2021 	   return SCIP_OKAY;
2022 	}
2023 	
2024 	
2025 	/** constraint display method of constraint handler */
2026 	static
2027 	SCIP_DECL_CONSPRINT(consPrintSOS2)
2028 	{  /*lint --e{715}*/
2029 	   SCIP_CONSDATA* consdata;
2030 	   int j;
2031 	
2032 	   assert( scip != NULL );
2033 	   assert( conshdlr != NULL );
2034 	   assert( cons != NULL );
2035 	   assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2036 	
2037 	   consdata = SCIPconsGetData(cons);
2038 	   assert( consdata != NULL );
2039 	
2040 	   for (j = 0; j < consdata->nvars; ++j)
2041 	   {
2042 	      if ( j > 0 )
2043 	         SCIPinfoMessage(scip, file, ", ");
2044 	      SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[j], FALSE) );
2045 	      if ( consdata->weights == NULL )
2046 	         SCIPinfoMessage(scip, file, " (%d)", j+1);
2047 	      else
2048 	         SCIPinfoMessage(scip, file, " (%3.2f)", consdata->weights[j]);
2049 	   }
2050 	
2051 	   return SCIP_OKAY;
2052 	}
2053 	
2054 	
2055 	/** constraint copying method of constraint handler */
2056 	static
2057 	SCIP_DECL_CONSCOPY(consCopySOS2)
2058 	{  /*lint --e{715}*/
2059 	   SCIP_CONSDATA* sourceconsdata;
2060 	   SCIP_VAR** sourcevars;
2061 	   SCIP_VAR** targetvars;
2062 	   SCIP_Real* targetweights = NULL;
2063 	   const char* consname;
2064 	   int nvars;
2065 	   int v;
2066 	
2067 	   assert( scip != NULL );
2068 	   assert( sourcescip != NULL );
2069 	   assert( sourcecons != NULL );
2070 	   assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) == 0 );
2071 	   assert( valid != NULL );
2072 	
2073 	   *valid = TRUE;
2074 	
2075 	   if ( name != NULL )
2076 	      consname = name;
2077 	   else
2078 	      consname = SCIPconsGetName(sourcecons);
2079 	
2080 	   SCIPdebugMsg(scip, "Copying SOS2 constraint <%s> ...\n", consname);
2081 	
2082 	   sourceconsdata = SCIPconsGetData(sourcecons);
2083 	   assert( sourceconsdata != NULL );
2084 	
2085 	   /* get variables and weights of the source constraint */
2086 	   nvars = sourceconsdata->nvars;
2087 	   assert( nvars >= 0 );
2088 	
2089 	   /* duplicate weights array */
2090 	   if ( sourceconsdata->weights != NULL )
2091 	   {
2092 	      SCIP_CALL( SCIPduplicateBufferArray(sourcescip, &targetweights, sourceconsdata->weights, nvars) );
2093 	   }
2094 	
2095 	   /* get copied variables in target SCIP */
2096 	   sourcevars = sourceconsdata->vars;
2097 	   SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetvars, nvars) );
2098 	   for (v = 0; v < nvars && *valid; ++v)
2099 	   {
2100 	      assert( sourcevars != NULL );
2101 	      SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) );
2102 	   }
2103 	
2104 	   /* only create the target constraint, if all variables could be copied */
2105 	   if( *valid )
2106 	   {
2107 	      SCIP_CALL( SCIPcreateConsSOS2(scip, cons, consname, nvars, targetvars, targetweights,
2108 	            initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
2109 	   }
2110 	
2111 	   /* free buffer array */
2112 	   SCIPfreeBufferArray(sourcescip, &targetvars);
2113 	   SCIPfreeBufferArrayNull(sourcescip, &targetweights);
2114 	
2115 	   return SCIP_OKAY;
2116 	}
2117 	
2118 	
2119 	/** constraint parsing method of constraint handler */
2120 	static
2121 	SCIP_DECL_CONSPARSE(consParseSOS2)
2122 	{  /*lint --e{715}*/
2123 	   SCIP_VAR* var;
2124 	   SCIP_Real weight;
2125 	   const char* s;
2126 	   char* t;
2127 	
2128 	   *success = TRUE;
2129 	   s = str;
2130 	
2131 	   /* create empty SOS2 constraint */
2132 	   SCIP_CALL( SCIPcreateConsSOS2(scip, cons, name, 0, NULL, NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
2133 	
2134 	   /* loop through string */
2135 	   while( *s != '\0' )
2136 	   {
2137 	      /* parse variable name */
2138 	      SCIP_CALL( SCIPparseVarName(scip, s, &var, &t) );
2139 	
2140 	      if( var == NULL )
2141 	         break;
2142 	
2143 	      /* skip until beginning of weight */
2144 	      t = strchr(t, '(');
2145 	
2146 	      if( t == NULL )
2147 	      {
2148 	         SCIPerrorMessage("Syntax error: expected opening '(' at input: %s\n", s);
2149 	         *success = FALSE;
2150 	         break;
2151 	      }
2152 	
2153 	      s = t;
2154 	
2155 	      /* skip '(' */
2156 	      ++s;
2157 	
2158 	      /* find weight */
2159 	      weight = strtod(s, &t);
2160 	
2161 	      if( t == NULL )
2162 	      {
2163 	         SCIPerrorMessage("Syntax error during parsing of the weight: %s\n", s);
2164 	         *success = FALSE;
2165 	         break;
2166 	      }
2167 	
2168 	      s = t;
2169 	
2170 	      /* skip until ending of weight */
2171 	      t = strchr(t, ')');
2172 	
2173 	      if( t == NULL )
2174 	      {
2175 	         SCIPerrorMessage("Syntax error: expected closing ')' at input %s\n", s);
2176 	         *success = FALSE;
2177 	         break;
2178 	      }
2179 	
2180 	      s = t;
2181 	
2182 	      /* skip ')' */
2183 	      ++s;
2184 	
2185 	      /* skip white space */
2186 	      SCIP_CALL( SCIPskipSpace((char**)&s) );
2187 	
2188 	      /* skip ',' */
2189 	      if( *s == ',' )
2190 	         ++s;
2191 	
2192 	      /* add variable */
2193 	      SCIP_CALL( SCIPaddVarSOS2(scip, *cons, var, weight) );
2194 	   }
2195 	
2196 	   if( !*success )
2197 	      SCIP_CALL( SCIPreleaseCons(scip, cons) );
2198 	
2199 	   return SCIP_OKAY;
2200 	}
2201 	
2202 	
2203 	/** constraint method of constraint handler which returns the variables (if possible) */
2204 	static
2205 	SCIP_DECL_CONSGETVARS(consGetVarsSOS2)
2206 	{  /*lint --e{715}*/
2207 	   SCIP_CONSDATA* consdata;
2208 	
2209 	   consdata = SCIPconsGetData(cons);
2210 	   assert(consdata != NULL);
2211 	
2212 	   if( varssize < consdata->nvars )
2213 	      (*success) = FALSE;
2214 	   else
2215 	   {
2216 	      assert(vars != NULL);
2217 	
2218 	      BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
2219 	      (*success) = TRUE;
2220 	   }
2221 	
2222 	   return SCIP_OKAY;
2223 	}
2224 	
2225 	
2226 	/** constraint method of constraint handler which returns the number of variables (if possible) */
2227 	static
2228 	SCIP_DECL_CONSGETNVARS(consGetNVarsSOS2)
2229 	{  /*lint --e{715}*/
2230 	   SCIP_CONSDATA* consdata;
2231 	
2232 	   consdata = SCIPconsGetData(cons);
2233 	   assert(consdata != NULL);
2234 	
2235 	   (*nvars) = consdata->nvars;
2236 	   (*success) = TRUE;
2237 	
2238 	   return SCIP_OKAY;
2239 	}
2240 	
2241 	
2242 	/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
2243 	static
2244 	SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphSOS2)
2245 	{  /*lint --e{715}*/
2246 	   SCIP_CONSDATA* consdata;
2247 	   SCIP_VAR** consvars;
2248 	   SCIP_VAR** locvars;
2249 	   SCIP_Real* locvals;
2250 	   SCIP_Real constant = 0.0;
2251 	   int consnodeidx;
2252 	   int opnodeidx;
2253 	   int nodeidx;
2254 	   int nconsvars;
2255 	   int nlocvars;
2256 	   int nvars;
2257 	   int i;
2258 	   int j;
2259 	
2260 	   consdata = SCIPconsGetData(cons);
2261 	   assert(consdata != NULL);
2262 	
2263 	   /* get active variables of the constraint */
2264 	   nvars = SCIPgetNVars(scip);
2265 	   nconsvars = consdata->nvars;
2266 	   consvars = SCIPgetVarsSOS2(scip, cons);
2267 	   assert(consvars != NULL);
2268 	
2269 	   SCIP_CALL( SCIPallocBufferArray(scip, &locvars, nvars) );
2270 	   SCIP_CALL( SCIPallocBufferArray(scip, &locvals, nvars) );
2271 	
2272 	   /* add node initializing constraint (with artificial rhs) */
2273 	   SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &consnodeidx) );
2274 	
2275 	   /* for all pairs of variables, add a node indicating a tuple and add nodes for (aggregated) variables */
2276 	   for( i = 0; i < nconsvars - 1; ++i )
2277 	   {
2278 	      SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SOS2_TUPLE, &opnodeidx) ); /*lint !e641*/
2279 	      SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, opnodeidx, FALSE, 0.0) );
2280 	
2281 	      for( j = i; j < i + 2; ++j )
2282 	      {
2283 	         locvars[0] = consvars[j];
2284 	         locvals[0] = 1.0;
2285 	         constant = 0.0;
2286 	         nlocvars = 1;
2287 	
2288 	         /* ignore weights of SOS2 constraint (variables are sorted according to these weights) */
2289 	         SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &locvars, &locvals,
2290 	               &nlocvars, &constant, SCIPisTransformed(scip)) );
2291 	
2292 	         if( nlocvars == 1 && SCIPisZero(scip, constant) && SCIPisEQ(scip, locvals[0], 1.0) )
2293 	         {
2294 	            nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, locvars[0]);
2295 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) );
2296 	         }
2297 	         else
2298 	         {
2299 	            SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/
2300 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) );
2301 	            SCIP_CALL( SCIPaddSymgraphVarAggegration(scip, graph, nodeidx, locvars, locvals, nlocvars, constant) );
2302 	         }
2303 	      }
2304 	   }
2305 	
2306 	   SCIPfreeBufferArray(scip, &locvals);
2307 	   SCIPfreeBufferArray(scip, &locvars);
2308 	
2309 	   return SCIP_OKAY;
2310 	}
2311 	
2312 	
2313 	/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
2314 	static
2315 	SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphSOS2)
2316 	{  /*lint --e{715}*/
2317 	   SCIP_CONSDATA* consdata;
2318 	   SCIP_VAR** consvars;
2319 	   SCIP_VAR** locvars;
2320 	   SCIP_Real* locvals;
2321 	   SCIP_Real constant = 0.0;
2322 	   int consnodeidx;
2323 	   int opnodeidx;
2324 	   int nodeidx;
2325 	   int nconsvars;
2326 	   int nlocvars;
2327 	   int nvars;
2328 	   int i;
2329 	   int j;
2330 	
2331 	   consdata = SCIPconsGetData(cons);
2332 	   assert(consdata != NULL);
2333 	
2334 	   /* get active variables of the constraint */
2335 	   nvars = SCIPgetNVars(scip);
2336 	   nconsvars = consdata->nvars;
2337 	   consvars = SCIPgetVarsSOS2(scip, cons);
2338 	   assert(consvars != NULL);
2339 	
2340 	   SCIP_CALL( SCIPallocBufferArray(scip, &locvars, nvars) );
2341 	   SCIP_CALL( SCIPallocBufferArray(scip, &locvals, nvars) );
2342 	
2343 	   /* add node initializing constraint (with artificial rhs) */
2344 	   SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &consnodeidx) );
2345 	
2346 	   /* for all pairs of variables, add a node indicating a tuple and add nodes for (aggregated) variables */
2347 	   for( i = 0; i < nconsvars - 1; ++i )
2348 	   {
2349 	      SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SOS2_TUPLE, &opnodeidx) ); /*lint !e641*/
2350 	      SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, opnodeidx, FALSE, 0.0) );
2351 	
2352 	      for( j = i; j < i + 2; ++j )
2353 	      {
2354 	         locvars[0] = consvars[j];
2355 	         locvals[0] = 1.0;
2356 	         constant = 0.0;
2357 	         nlocvars = 1;
2358 	
2359 	         /* ignore weights of SOS2 constraint (variables are sorted according to these weights) */
2360 	
2361 	         /* use SYM_SYMTYPE_PERM here to NOT center variable domains at 0, as the latter might not preserve
2362 	          * SOS1 constraints */
2363 	         SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &locvars, &locvals,
2364 	               &nlocvars, &constant, SCIPisTransformed(scip)) );
2365 	
2366 	         if( nlocvars == 1 && SCIPisZero(scip, constant) && SCIPisEQ(scip, locvals[0], 1.0) )
2367 	         {
2368 	            SCIP_Bool allownegation = FALSE;
2369 	
2370 	            /* a negation is allowed if it is centered around 0 */
2371 	            if ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(locvars[0])) == SCIPisInfinity(scip, SCIPvarGetUbGlobal(locvars[0]))
2372 	               && (SCIPisInfinity(scip, SCIPvarGetUbGlobal(locvars[0]))
2373 	                  || SCIPisZero(scip, (SCIPvarGetLbGlobal(locvars[0]) + SCIPvarGetUbGlobal(locvars[0]))/2)) )
2374 	               allownegation = TRUE;
2375 	
2376 	            nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, locvars[0]);
2377 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, TRUE, 1.0) );
2378 	
2379 	            nodeidx = SCIPgetSymgraphNegatedVarnodeidx(scip, graph, locvars[0]);
2380 	            if( allownegation )
2381 	            {
2382 	               SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, TRUE, 1.0) );
2383 	            }
2384 	            else
2385 	            {
2386 	               SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, TRUE, -1.0) );
2387 	            }
2388 	         }
2389 	         else
2390 	         {
2391 	            int sumnodeidx;
2392 	            int k;
2393 	
2394 	            SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &sumnodeidx) ); /*lint !e641*/
2395 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, sumnodeidx, FALSE, 0.0) );
2396 	
2397 	            /* add nodes and edges for variables in aggregation, do not add edges to negated variables
2398 	             * since this might not necessarily be a symmetry of the SOS1 constraint; therefore,
2399 	             * do not use SCIPaddSymgraphVarAggegration() */
2400 	            for( k = 0; k < nlocvars; ++k )
2401 	            {
2402 	               nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, locvars[k]);
2403 	               SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, TRUE, locvals[k]) );
2404 	            }
2405 	
2406 	            /* possibly add node for constant */
2407 	            if( ! SCIPisZero(scip, constant) )
2408 	            {
2409 	               SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, constant, &nodeidx) );
2410 	               SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, FALSE, 0.0) );
2411 	            }
2412 	         }
2413 	      }
2414 	   }
2415 	
2416 	   SCIPfreeBufferArray(scip, &locvals);
2417 	   SCIPfreeBufferArray(scip, &locvars);
2418 	
2419 	   return SCIP_OKAY;
2420 	}
2421 	
2422 	
2423 	/* ---------------- Callback methods of event handler ---------------- */
2424 	
2425 	/** exec the event handler
2426 	 *
2427 	 * We update the number of variables fixed to be nonzero
2428 	 */
2429 	static
2430 	SCIP_DECL_EVENTEXEC(eventExecSOS2)
2431 	{
2432 	   SCIP_EVENTTYPE eventtype;
2433 	   SCIP_CONS* cons;
2434 	   SCIP_CONSDATA* consdata;
2435 	   SCIP_VAR* var;
2436 	   SCIP_Real oldbound, newbound;
2437 	
2438 	   assert( eventhdlr != NULL );
2439 	   assert( eventdata != NULL );
2440 	   assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0 );
2441 	   assert( event != NULL );
2442 	
2443 	   cons = (SCIP_CONS*)eventdata;
2444 	   assert( cons != NULL );
2445 	   consdata = SCIPconsGetData(cons);
2446 	   assert( consdata != NULL );
2447 	   assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
2448 	
2449 	   oldbound = SCIPeventGetOldbound(event);
2450 	   newbound = SCIPeventGetNewbound(event);
2451 	
2452 	   eventtype = SCIPeventGetType(event);
2453 	   switch ( eventtype )
2454 	   {
2455 	   case SCIP_EVENTTYPE_LBTIGHTENED:
2456 	      /* if variable is now fixed to be nonzero */
2457 	      if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
2458 	         ++(consdata->nfixednonzeros);
2459 	      break;
2460 	   case SCIP_EVENTTYPE_UBTIGHTENED:
2461 	      /* if variable is now fixed to be nonzero */
2462 	      if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
2463 	         ++(consdata->nfixednonzeros);
2464 	      break;
2465 	   case SCIP_EVENTTYPE_LBRELAXED:
2466 	      /* if variable is not fixed to be nonzero anymore */
2467 	      if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) )
2468 	         --(consdata->nfixednonzeros);
2469 	      break;
2470 	   case SCIP_EVENTTYPE_UBRELAXED:
2471 	      /* if variable is not fixed to be nonzero anymore */
2472 	      if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) )
2473 	         --(consdata->nfixednonzeros);
2474 	      break;
2475 	   case SCIP_EVENTTYPE_GLBCHANGED:
2476 	      var = SCIPeventGetVar(event);
2477 	      assert(var != NULL);
2478 	
2479 	      /* global lower bound is not negative anymore -> remove down lock */
2480 	      if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) )
2481 	         SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, FALSE) );
2482 	      /* global lower bound turned negative -> add down lock */
2483 	      else if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
2484 	         SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, FALSE) );
2485 	      break;
2486 	   case SCIP_EVENTTYPE_GUBCHANGED:
2487 	      var = SCIPeventGetVar(event);
2488 	      assert(var != NULL);
2489 	
2490 	      /* global upper bound is not positive anymore -> remove up lock */
2491 	      if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) )
2492 	         SCIP_CALL( SCIPunlockVarCons(scip, var, cons, FALSE, TRUE) );
2493 	      /* global upper bound turned positive -> add up lock */
2494 	      else if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
2495 	         SCIP_CALL( SCIPlockVarCons(scip, var, cons, FALSE, TRUE) );
2496 	      break;
2497 	   default:
2498 	      SCIPerrorMessage("invalid event type.\n");
2499 	      return SCIP_INVALIDDATA;
2500 	   }
2501 	   assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
2502 	
2503 	   SCIPdebugMsg(scip, "changed bound of variable <%s> from %f to %f (nfixednonzeros: %d).\n", SCIPvarGetName(SCIPeventGetVar(event)),
2504 	      oldbound, newbound, consdata->nfixednonzeros);
2505 	
2506 	   return SCIP_OKAY;
2507 	}
2508 	
2509 	
2510 	/* ---------------- Constraint specific interface methods ---------------- */
2511 	
2512 	/** creates the handler for SOS2 constraints and includes it in SCIP */
2513 	SCIP_RETCODE SCIPincludeConshdlrSOS2(
2514 	   SCIP*                 scip                /**< SCIP data structure */
2515 	   )
2516 	{
2517 	   SCIP_CONSHDLRDATA* conshdlrdata;
2518 	   SCIP_CONSHDLR* conshdlr;
2519 	
2520 	   /* create constraint handler data */
2521 	   SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2522 	
2523 	   conshdlrdata->eventhdlr = NULL;
2524 	   /* create event handler for bound change events */
2525 	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->eventhdlr), EVENTHDLR_NAME, EVENTHDLR_DESC,
2526 	         eventExecSOS2, NULL) );
2527 	   if ( conshdlrdata->eventhdlr == NULL )
2528 	   {
2529 	      SCIPerrorMessage("event handler for SOS2 constraints not found.\n");
2530 	      return SCIP_PLUGINNOTFOUND;
2531 	   }
2532 	
2533 	   /* include constraint handler */
2534 	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2535 	         CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2536 	         consEnfolpSOS2, consEnfopsSOS2, consCheckSOS2, consLockSOS2, conshdlrdata) );
2537 	   assert(conshdlr != NULL);
2538 	
2539 	   /* set non-fundamental callbacks via specific setter functions */
2540 	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySOS2, consCopySOS2) );
2541 	   SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSOS2) );
2542 	   SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolSOS2) );
2543 	   SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSOS2) );
2544 	   SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSOS2) );
2545 	   SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSOS2) );
2546 	   SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSOS2) );
2547 	   SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSOS2) );
2548 	   SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSOS2, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2549 	   SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSOS2) );
2550 	   SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSOS2, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
2551 	   SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSOS2) );
2552 	   SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSOS2, consSepasolSOS2, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2553 	   SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSOS2) );
2554 	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSOS2) );
2555 	   SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphSOS2) );
2556 	   SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphSOS2) );
2557 	
2558 	   return SCIP_OKAY;
2559 	}
2560 	
2561 	
2562 	/** creates and captures a SOS2 constraint
2563 	 *
2564 	 *  We set the constraint to not be modifable. If the weights are non
2565 	 *  NULL, the variables are ordered according to these weights (in
2566 	 *  ascending order).
2567 	 *
2568 	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2569 	 */
2570 	SCIP_RETCODE SCIPcreateConsSOS2(
2571 	   SCIP*                 scip,               /**< SCIP data structure */
2572 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
2573 	   const char*           name,               /**< name of constraint */
2574 	   int                   nvars,              /**< number of variables in the constraint */
2575 	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
2576 	   SCIP_Real*            weights,            /**< weights determining the variable order, or NULL if natural order should be used */
2577 	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
2578 	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2579 	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
2580 	                                              *   Usually set to TRUE. */
2581 	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
2582 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
2583 	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
2584 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
2585 	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
2586 	                                              *   Usually set to TRUE. */
2587 	   SCIP_Bool             local,              /**< is constraint only valid locally?
2588 	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2589 	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
2590 	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
2591 	                                              *   are separated as constraints. */
2592 	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
2593 	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2594 	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
2595 	                                              *   if it may be moved to a more global node?
2596 	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2597 	   )
2598 	{
2599 	   SCIP_CONSHDLR* conshdlr;
2600 	   SCIP_CONSDATA* consdata;
2601 	   SCIP_Bool modifiable;
2602 	
2603 	   modifiable = FALSE;
2604 	
2605 	   /* find the SOS2 constraint handler */
2606 	   conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2607 	   if ( conshdlr == NULL )
2608 	   {
2609 	      SCIPerrorMessage("<%s> constraint handler not found\n", CONSHDLR_NAME);
2610 	      return SCIP_PLUGINNOTFOUND;
2611 	   }
2612 	
2613 	   /* create constraint data */
2614 	   SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
2615 	   consdata->vars = NULL;
2616 	   consdata->nvars = nvars;
2617 	   consdata->maxvars = nvars;
2618 	   consdata->row = NULL;
2619 	   consdata->nfixednonzeros = -1;
2620 	   consdata->weights = NULL;
2621 	   if ( nvars > 0 )
2622 	   {
2623 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->vars, vars, nvars) );
2624 	
2625 	      /* check weights */
2626 	      if ( weights != NULL )
2627 	      {
2628 	         /* store weights */
2629 	         SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, weights, nvars) );
2630 	
2631 	         /* sort variables - ascending order */
2632 	         SCIPsortRealPtr(consdata->weights, (void**)consdata->vars, nvars);
2633 	      }
2634 	   }
2635 	   else
2636 	      assert( weights == NULL );
2637 	
2638 	   /* create constraint */
2639 	   SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2640 	         local, modifiable, dynamic, removable, stickingatnode) );
2641 	
2642 	   return SCIP_OKAY;
2643 	}
2644 	
2645 	
2646 	/** creates and captures a SOS2 constraint with all constraint flags set to their default values.
2647 	 *
2648 	 *  @warning Do NOT set the constraint to be modifiable manually, because this might lead
2649 	 *  to wrong results as the variable array will not be resorted
2650 	 *
2651 	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2652 	 */
2653 	SCIP_RETCODE SCIPcreateConsBasicSOS2(
2654 	   SCIP*                 scip,               /**< SCIP data structure */
2655 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
2656 	   const char*           name,               /**< name of constraint */
2657 	   int                   nvars,              /**< number of variables in the constraint */
2658 	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
2659 	   SCIP_Real*            weights             /**< weights determining the variable order, or NULL if natural order should be used */
2660 	   )
2661 	{
2662 	   SCIP_CALL( SCIPcreateConsSOS2( scip, cons, name, nvars, vars, weights, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
2663 	
2664 	   return SCIP_OKAY;
2665 	}
2666 	
2667 	
2668 	/** adds variable to SOS2 constraint, the position is determined by the given weight */
2669 	SCIP_RETCODE SCIPaddVarSOS2(
2670 	   SCIP*                 scip,               /**< SCIP data structure */
2671 	   SCIP_CONS*            cons,               /**< constraint */
2672 	   SCIP_VAR*             var,                /**< variable to add to the constraint */
2673 	   SCIP_Real             weight              /**< weight determining position of variable */
2674 	   )
2675 	{
2676 	   assert( scip != NULL );
2677 	   assert( var != NULL );
2678 	   assert( cons != NULL );
2679 	
2680 	   SCIPdebugMsg(scip, "adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var), SCIPconsGetName(cons), weight);
2681 	
2682 	   if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2683 	   {
2684 	      SCIPerrorMessage("constraint is not an SOS2 constraint.\n");
2685 	      return SCIP_INVALIDDATA;
2686 	   }
2687 	
2688 	   SCIP_CALL( addVarSOS2(scip, cons, var, weight) );
2689 	
2690 	   return SCIP_OKAY;
2691 	}
2692 	
2693 	
2694 	/** appends variable to SOS2 constraint */
2695 	SCIP_RETCODE SCIPappendVarSOS2(
2696 	   SCIP*                 scip,               /**< SCIP data structure */
2697 	   SCIP_CONS*            cons,               /**< constraint */
2698 	   SCIP_VAR*             var                 /**< variable to add to the constraint */
2699 	   )
2700 	{
2701 	   assert( scip != NULL );
2702 	   assert( var != NULL );
2703 	   assert( cons != NULL );
2704 	
2705 	   SCIPdebugMsg(scip, "appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons));
2706 	
2707 	   if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2708 	   {
2709 	      SCIPerrorMessage("constraint is not an SOS2 constraint.\n");
2710 	      return SCIP_INVALIDDATA;
2711 	   }
2712 	
2713 	   SCIP_CALL( appendVarSOS2(scip, cons, var) );
2714 	
2715 	   return SCIP_OKAY;
2716 	}
2717 	
2718 	
2719 	/** gets number of variables in SOS2 constraint */
2720 	int SCIPgetNVarsSOS2(
2721 	   SCIP*                 scip,               /**< SCIP data structure */
2722 	   SCIP_CONS*            cons                /**< constraint */
2723 	   )
2724 	{
2725 	   SCIP_CONSDATA* consdata;
2726 	
2727 	   assert( scip != NULL );
2728 	   assert( cons != NULL );
2729 	
2730 	   if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2731 	   {
2732 	      SCIPerrorMessage("constraint is not an SOS2 constraint.\n");
2733 	      SCIPABORT();
2734 	      return -1;  /*lint !e527*/
2735 	   }
2736 	
2737 	   consdata = SCIPconsGetData(cons);
2738 	   assert( consdata != NULL );
2739 	
2740 	   return consdata->nvars;
2741 	}
2742 	
2743 	
2744 	/** gets array of variables in SOS2 constraint */
2745 	SCIP_VAR** SCIPgetVarsSOS2(
2746 	   SCIP*                 scip,               /**< SCIP data structure */
2747 	   SCIP_CONS*            cons                /**< constraint data */
2748 	   )
2749 	{
2750 	   SCIP_CONSDATA* consdata;
2751 	
2752 	   assert( scip != NULL );
2753 	   assert( cons != NULL );
2754 	
2755 	   if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2756 	   {
2757 	      SCIPerrorMessage("constraint is not an SOS2 constraint.\n");
2758 	      SCIPABORT();
2759 	      return NULL;  /*lint !e527*/
2760 	   }
2761 	
2762 	   consdata = SCIPconsGetData(cons);
2763 	   assert( consdata != NULL );
2764 	
2765 	   return consdata->vars;
2766 	}
2767 	
2768 	
2769 	/** gets array of weights in SOS2 constraint (or NULL if not existent) */
2770 	SCIP_Real* SCIPgetWeightsSOS2(
2771 	   SCIP*                 scip,               /**< SCIP data structure */
2772 	   SCIP_CONS*            cons                /**< constraint data */
2773 	   )
2774 	{
2775 	   SCIP_CONSDATA* consdata;
2776 	
2777 	   assert( scip != NULL );
2778 	   assert( cons != NULL );
2779 	
2780 	   if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2781 	   {
2782 	      SCIPerrorMessage("constraint is not an SOS2 constraint.\n");
2783 	      SCIPABORT();
2784 	      return NULL;  /*lint !e527*/
2785 	   }
2786 	
2787 	   consdata = SCIPconsGetData(cons);
2788 	   assert( consdata != NULL );
2789 	
2790 	   return consdata->weights;
2791 	}
2792