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