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