Scippy

SCIP

Solving Constraint Integer Programs

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