Scippy

SCIP

Solving Constraint Integer Programs

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