Scippy

SCIP

Solving Constraint Integer Programs

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