SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
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? */
118
119#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
120#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
121
122/* event handler properties */
123#define EVENTHDLR_NAME "SOS2"
124#define EVENTHDLR_DESC "bound change event handler for SOS2 constraints"
125
126#define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)
127
128
129/** constraint data for SOS2 constraints */
130struct 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 */
141struct 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 */
148static
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
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 {
185 SCIP_CALL( SCIPchgVarLbNode(scip, node, var, 0.0) );
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 */
199static
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 */
242static
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 */
256
257 return SCIP_OKAY;
258}
259
260
261/* remove lock on variable */
262static
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 */
276
277 return SCIP_OKAY;
278}
279
280
281/** ensures that the vars and weights array can store at least num entries */
282static
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
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 */
310static
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 */
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 */
367static
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 {
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 */
435static
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 {
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 */
491static
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 */
551static
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;
569 int lastzero;
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 );
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;
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) );
634
635 /* change the rounding locks */
636 SCIP_CALL( unlockVariableSOS2(scip, cons, consdata->vars[j]) );
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 */
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)
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 */
697 {
698 assert(lastzero >= 0);
699
700 for( j = lastzero; j >= 0; --j )
701 {
702 /* the variables should all be fixed to zero */
704
705 SCIPdebugMsg(scip, "deleting variable <%s> fixed to 0.\n", SCIPvarGetName(vars[j]));
706 SCIP_CALL( deleteVarSOS2(scip, cons, consdata, eventhdlr, j) );
707 }
709 *success = TRUE;
710 }
711
712 /* check that our variable array is still correct */
713 assert(vars == consdata->vars);
714
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 {
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 {
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 {
787 /* the previous variable need also to be nonzero, otherwise the infeasibility should have been detected earlier */
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 */
832static
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");
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;
869 int nvars;
870 int j;
871
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 {
881 {
883 break;
884 }
885 }
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 {
911 SCIPdebugMsg(scip, "the node is infeasible: variable <%s> is fixed nonzero and variable <%s> with distance at least 2 as well.\n",
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;
931 int nvars;
932 int j;
933
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 {
943 {
945 break;
946 }
947 }
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 */
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 );
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 {
974 SCIPdebugMsg(scip, "the node is infeasible: variable <%s> is fixed nonzero and variable <%s> with distance at least 2 as well.\n",
976 *cutoff = TRUE;
977 return SCIP_OKAY;
978 }
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));
991 }
992 }
993
994 /* reset constraint age counter */
995 if ( *ngen > ngenold )
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 */
1030static
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) );
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 {
1099 return SCIP_OKAY;
1100 }
1101 if ( ngen > 0 )
1102 {
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
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 */
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]),
1174
1175 /* calculate node selection and objective estimate for node 1 */
1176 nodeselest = 0.0;
1178 for (j = 0; j < maxInd; ++j)
1179 {
1182 }
1184
1185 /* create node 1 */
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;
1197 for (j = maxInd+1; j < nvars; ++j)
1198 {
1201 }
1203
1204 /* create node 2 */
1206 for (j = maxInd+1; j < nvars; ++j)
1207 {
1208 SCIP_CALL( fixVariableZeroNode(scip, vars[j], node2, &infeasible) );
1209 assert( ! infeasible );
1210 }
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 */
1232static
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) );
1319 consdata->row = row;
1320
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) */
1331static
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) */
1348static
1350{
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) */
1367static
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 */
1399static
1401{
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 */
1448static
1450{
1451 SCIP_CONSDATA* consdata;
1452 SCIP_CONSHDLRDATA* conshdlrdata;
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 */
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 */
1505 SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
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,
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 */
1531static
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
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
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 {
1583 return SCIP_OKAY;
1584 }
1585
1586 if ( 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) */
1600static
1602{
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 */
1644static
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
1658
1659 /* check each constraint */
1660 for (c = 0; c < nconss && ! cutoff; ++c)
1661 {
1662 SCIP_CONSDATA* consdata;
1663 SCIP_ROW* row;
1664
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) );
1685 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
1686 ++ngen;
1687 }
1688 }
1689 SCIPdebugMsg(scip, "Separated %d SOS2 constraints.\n", ngen);
1690 if ( cutoff )
1692 else if ( ngen > 0 )
1694
1695 return SCIP_OKAY;
1696}
1697
1698
1699/** separation method of constraint handler for arbitrary primal solutions */
1700static
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
1714
1715 /* check each constraint */
1716 for (c = 0; c < nconss && ! cutoff; ++c)
1717 {
1718 SCIP_CONSDATA* consdata;
1719 SCIP_ROW* row;
1720
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) );
1741 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
1742 ++ngen;
1743 }
1744 }
1745 SCIPdebugMsg(scip, "Separated %d SOS2 constraints.\n", ngen);
1746 if ( cutoff )
1748 else if ( ngen > 0 )
1750
1751 return SCIP_OKAY;
1752}
1753
1754
1755/** constraint enforcing method of constraint handler for LP solutions */
1756static
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 */
1772static
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 */
1788static
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 */
1809static
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
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]) );
1850
1851 /* update constraint violation in solution */
1852 if ( sol != NULL )
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 */
1878static
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 );
1890
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
1907 SCIP_CALL( propSOS2(scip, cons, consdata, &cutoff, &ngen) );
1908 if ( cutoff )
1909 {
1911 return SCIP_OKAY;
1912 }
1913 }
1914 SCIPdebugMsg(scip, "Propagated %d domains.\n", ngen);
1915 if ( ngen > 0 )
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). */
1927static
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
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 */
1951 {
1952 SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1954 }
1955
1956 /* check if upper bound of var was the reason */
1958 {
1959 SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
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 */
1979static
1981{
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 );
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 */
2009 SCIP_CALL( SCIPaddVarLocksType(scip, var, locktype, nlockspos, nlocksneg) );
2010
2011 /* additionally: if upper bound is positive, rounding up may violate constraint */
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 */
2021static
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 */
2051static
2053{ /*lint --e{715}*/
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 );
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
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 {
2088 }
2089
2090 /* get copied variables in target SCIP */
2091 sourcevars = sourceconsdata->vars;
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 {
2103 initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
2104 }
2105
2106 /* free buffer array */
2107 SCIPfreeBufferArray(sourcescip, &targetvars);
2109
2110 return SCIP_OKAY;
2111}
2112
2113
2114/** constraint parsing method of constraint handler */
2115static
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) */
2199static
2201{ /*lint --e{715}*/
2202 SCIP_CONSDATA* consdata;
2203
2204 consdata = SCIPconsGetData(cons);
2205 assert(consdata != NULL);
2206
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) */
2222static
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 */
2243static
2245{
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;
2291 assert(var != NULL);
2292
2293 /* global lower bound is not negative anymore -> remove down lock */
2294 if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) )
2296 /* global lower bound turned negative -> add down lock */
2297 else if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
2299 break;
2302 assert(var != NULL);
2303
2304 /* global upper bound is not positive anymore -> remove up lock */
2305 if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) )
2307 /* global upper bound turned positive -> add up lock */
2308 else if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
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 */
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 */
2351 assert(conshdlr != NULL);
2352
2353 /* set non-fundamental callbacks via specific setter functions */
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
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
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 */
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
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
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
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}
SCIP_VAR * w
static SCIP_RETCODE branchCons(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result)
Constraint handler for linear constraints in their most general form, .
#define CONSHDLR_NEEDSCONS
Definition cons_sos2.c:117
#define CONSHDLR_SEPAFREQ
Definition cons_sos2.c:110
static SCIP_RETCODE propSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *ngen)
Definition cons_sos2.c:833
#define CONSHDLR_CHECKPRIORITY
Definition cons_sos2.c:109
#define CONSHDLR_DESC
Definition cons_sos2.c:106
#define CONSHDLR_PROP_TIMING
Definition cons_sos2.c:119
static SCIP_RETCODE handleNewVariableSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_Bool transformed)
Definition cons_sos2.c:311
static SCIP_RETCODE deleteVarSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition cons_sos2.c:492
#define CONSHDLR_MAXPREROUNDS
Definition cons_sos2.c:114
#define CONSHDLR_SEPAPRIORITY
Definition cons_sos2.c:107
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:552
static SCIP_RETCODE unlockVariableSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_sos2.c:263
static SCIP_RETCODE appendVarSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_sos2.c:436
static SCIP_RETCODE fixVariableZeroNode(SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible)
Definition cons_sos2.c:149
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:200
#define CONSHDLR_PROPFREQ
Definition cons_sos2.c:111
#define CONSHDLR_PRESOLTIMING
Definition cons_sos2.c:120
#define CONSHDLR_EAGERFREQ
Definition cons_sos2.c:112
#define EVENTHDLR_DESC
Definition cons_sos2.c:124
#define EVENTHDLR_EVENT_TYPE
Definition cons_sos2.c:126
#define CONSHDLR_ENFOPRIORITY
Definition cons_sos2.c:108
#define CONSHDLR_DELAYSEPA
Definition cons_sos2.c:115
static SCIP_RETCODE generateRowSOS2(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool local)
Definition cons_sos2.c:1233
static SCIP_RETCODE lockVariableSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_sos2.c:243
static SCIP_RETCODE addVarSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
Definition cons_sos2.c:368
static SCIP_RETCODE consdataEnsurevarsSizeSOS2(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveWeights)
Definition cons_sos2.c:283
#define CONSHDLR_NAME
Definition cons_sos2.c:105
static SCIP_RETCODE enforceSOS2(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition cons_sos2.c:1031
#define EVENTHDLR_NAME
Definition cons_sos2.c:123
#define CONSHDLR_DELAYPROP
Definition cons_sos2.c:116
constraint handler for SOS type 2 constraints
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
SCIP_Real * SCIPgetWeightsSOS2(SCIP *scip, SCIP_CONS *cons)
Definition cons_sos2.c:2582
SCIP_VAR ** SCIPgetVarsSOS2(SCIP *scip, SCIP_CONS *cons)
Definition cons_sos2.c:2557
SCIP_RETCODE SCIPappendVarSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_sos2.c:2507
int SCIPgetNVarsSOS2(SCIP *scip, SCIP_CONS *cons)
Definition cons_sos2.c:2532
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:2382
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPaddVarSOS2(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
Definition cons_sos2.c:2481
SCIP_RETCODE SCIPcreateConsBasicSOS2(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
Definition cons_sos2.c:2465
SCIP_RETCODE SCIPincludeConshdlrSOS2(SCIP *scip)
Definition cons_sos2.c:2327
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_Bool SCIPisTransformed(SCIP *scip)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2843
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3474
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition scip_prob.c:3323
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition scip_prob.c:3546
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:366
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition scip_cons.c:534
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
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
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:317
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
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:802
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:825
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:779
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4180
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
Definition scip_cons.c:341
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:572
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4200
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:595
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:641
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:462
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:618
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:848
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition cons.c:8118
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8347
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8108
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8257
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition scip_cons.c:2482
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8287
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition cons.c:8397
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8277
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_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8307
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8327
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8088
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1758
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8337
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8367
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8267
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8357
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition scip_cut.c:117
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:250
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
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition event.c:324
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition event.c:1030
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_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition scip_event.c:400
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
Definition event.c:1218
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition event.c:1053
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition event.c:1242
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition scip_lp.c:1583
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition scip_lp.c:1773
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
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
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition scip_lp.c:2212
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition scip_lp.c:1607
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition lp.c:17523
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition scip_sol.c:273
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:4351
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition var.c:17383
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 SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4890
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition scip_var.c:533
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition scip_var.c:1794
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition scip_var.c:4259
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:4437
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:2128
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8276
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
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:1992
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4846
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition scip_var.c:230
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition scip_var.c:1439
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
SCIP_RETCODE SCIPskipSpace(char **s)
Definition misc.c:10777
return SCIP_OKAY
int c
SCIP_Bool cutoff
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_Bool propagate
static SCIP_VAR ** vars
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition memory.h:136
public methods for managing constraints
public methods for managing events
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebug(x)
Definition pub_message.h:93
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for problem variables
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for solutions
public methods for SCIP variables
#define SCIP_DECL_CONSENFOLP(x)
Definition type_cons.h:362
#define SCIP_DECL_CONSDELETE(x)
Definition type_cons.h:228
#define SCIP_DECL_CONSGETVARS(x)
Definition type_cons.h:865
#define SCIP_DECL_CONSPRINT(x)
Definition type_cons.h:767
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition type_cons.h:64
#define SCIP_DECL_CONSSEPALP(x)
Definition type_cons.h:287
#define SCIP_DECL_CONSENFORELAX(x)
Definition type_cons.h:387
#define SCIP_DECL_CONSPROP(x)
Definition type_cons.h:504
#define SCIP_DECL_CONSGETNVARS(x)
Definition type_cons.h:883
#define SCIP_DECL_CONSRESPROP(x)
Definition type_cons.h:610
#define SCIP_DECL_CONSENFOPS(x)
Definition type_cons.h:430
#define SCIP_DECL_CONSPARSE(x)
Definition type_cons.h:843
#define SCIP_DECL_CONSTRANS(x)
Definition type_cons.h:238
#define SCIP_DECL_CONSPRESOL(x)
Definition type_cons.h:559
#define SCIP_DECL_CONSINITLP(x)
Definition type_cons.h:258
#define SCIP_DECL_CONSLOCK(x)
Definition type_cons.h:674
#define SCIP_DECL_CONSCOPY(x)
Definition type_cons.h:808
struct SCIP_ConsData SCIP_CONSDATA
Definition type_cons.h:65
#define SCIP_DECL_CONSCHECK(x)
Definition type_cons.h:473
#define SCIP_DECL_CONSHDLRCOPY(x)
Definition type_cons.h:107
#define SCIP_DECL_CONSEXITSOL(x)
Definition type_cons.h:215
#define SCIP_DECL_CONSFREE(x)
Definition type_cons.h:115
#define SCIP_DECL_CONSSEPASOL(x)
Definition type_cons.h:319
#define SCIP_EVENTTYPE_GUBCHANGED
Definition type_event.h:76
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition type_event.h:79
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_LBRELAXED
Definition type_event.h:78
#define SCIP_EVENTTYPE_GLBCHANGED
Definition type_event.h:75
uint64_t SCIP_EVENTTYPE
Definition type_event.h:151
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition type_event.h:77
#define SCIP_EVENTTYPE_UBRELAXED
Definition type_event.h:80
@ SCIP_BRANCHDIR_DOWNWARDS
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_FEASIBLE
Definition type_result.h:45
@ SCIP_REDUCEDDOM
Definition type_result.h:51
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_BRANCHED
Definition type_result.h:54
@ SCIP_SEPARATED
Definition type_result.h:49
@ SCIP_SUCCESS
Definition type_result.h:58
@ SCIP_INFEASIBLE
Definition type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_INVALIDDATA
@ SCIP_PLUGINNOTFOUND
@ SCIP_INVALIDCALL
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97