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