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