Scippy

SCIP

Solving Constraint Integer Programs

Macros | Functions
cons_sos2.c File Reference

Detailed Description

constraint handler for SOS type 2 constraints

Author
Marc Pfetsch

A specially ordered set of type 2 (SOS2) is a sequence of variables such that at most two variables are nonzero and if two variables are nonzero they must be adjacent in the specified sequence. Note that it is in principle allowed that a variable appears twice, but it then can be fixed to 0 if it is at least two apart in the sequence.

This constraint is useful when considering a piecewise affine approximation of a univariate (nonlinear) function \(: [a,b] \rightarrow R\): Let \(x_1 < \ldots < x_n\) be points in \([a,b]\) and introduce variables \(\lambda_1, \ldots, \lambda_n\). To evaluate \(f(x')\) at some point \(x' \in [a,b]\) one can use the following constraints:

\[ \lambda_1 + \cdots + \lambda_n = 1,\quad x' = x_1 \lambda_1 + \cdots + x_n \lambda_n. \]

The value of \(f(x')\) can the be approximated as

\[ f(x_1) \lambda_1 + \cdots + f(x_n) \lambda_n. \]

To get a valid piecewise affine approximation, \(\lambda_1, \ldots, \lambda_n\) have to obey an SOS constraint of type 2.

This implementation of this constraint handler is based on classical ideas, see e.g.
"Special Facilities in General Mathematical Programming System for Non-Convex Problems Using Ordered Sets of Variables"
E. Beale and J. Tomlin, Proc. 5th IFORS Conference, 447-454 (1970)

The order of the variables is determined as follows:

  • If the constraint is created with SCIPcreateConsSOS2() and weights are given, the weights determine the order (decreasing weights). Additional variables can be added with SCIPaddVarSOS2(), which adds a variable with given weight.
  • If an empty constraint is created and then variables are added with SCIPaddVarSOS2(), weights are needed and stored.
  • All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are added with SCIPappendVarSOS2().

Definition in file cons_sos2.c.

#include <assert.h>
#include "scip/cons_sos2.h"
#include "scip/cons_linear.h"
#include "scip/pub_misc.h"
#include <string.h>
#include <ctype.h>

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "SOS2"
 
#define CONSHDLR_DESC   "SOS2 constraint handler"
 
#define CONSHDLR_SEPAPRIORITY   10
 
#define CONSHDLR_ENFOPRIORITY   100
 
#define CONSHDLR_CHECKPRIORITY   -10
 
#define CONSHDLR_SEPAFREQ   0
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST
 
#define EVENTHDLR_NAME   "SOS2"
 
#define EVENTHDLR_DESC   "bound change event handler for SOS2 constraints"
 

Functions

static SCIP_RETCODE fixVariableZeroNode (SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible)
 
static SCIP_RETCODE inferVariableZero (SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened, SCIP_Bool *success)
 
static SCIP_RETCODE lockVariableSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE unlockVariableSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE consdataEnsurevarsSizeSOS2 (SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveWeights)
 
static SCIP_RETCODE handleNewVariableSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_Bool transformed)
 
static SCIP_RETCODE addVarSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
 
static SCIP_RETCODE appendVarSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE deleteVarSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
 
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)
 
static SCIP_RETCODE propSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *ngen)
 
static SCIP_RETCODE enforceSOS2 (SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
 
static SCIP_RETCODE generateRowSOS2 (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool local)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopySOS2)
 
static SCIP_DECL_CONSFREE (consFreeSOS2)
 
static SCIP_DECL_CONSEXITSOL (consExitsolSOS2)
 
static SCIP_DECL_CONSDELETE (consDeleteSOS2)
 
static SCIP_DECL_CONSTRANS (consTransSOS2)
 
static SCIP_DECL_CONSPRESOL (consPresolSOS2)
 
static SCIP_DECL_CONSINITLP (consInitlpSOS2)
 
static SCIP_DECL_CONSSEPALP (consSepalpSOS2)
 
static SCIP_DECL_CONSSEPASOL (consSepasolSOS2)
 
static SCIP_DECL_CONSENFOLP (consEnfolpSOS2)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxSOS2)
 
static SCIP_DECL_CONSENFOPS (consEnfopsSOS2)
 
static SCIP_DECL_CONSCHECK (consCheckSOS2)
 
static SCIP_DECL_CONSPROP (consPropSOS2)
 
static SCIP_DECL_CONSRESPROP (consRespropSOS2)
 
static SCIP_DECL_CONSLOCK (consLockSOS2)
 
static SCIP_DECL_CONSPRINT (consPrintSOS2)
 
static SCIP_DECL_CONSCOPY (consCopySOS2)
 
static SCIP_DECL_CONSPARSE (consParseSOS2)
 
static SCIP_DECL_CONSGETVARS (consGetVarsSOS2)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsSOS2)
 
static SCIP_DECL_EVENTEXEC (eventExecSOS2)
 
SCIP_RETCODE SCIPincludeConshdlrSOS2 (SCIP *scip)
 
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)
 
SCIP_RETCODE SCIPcreateConsBasicSOS2 (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
 
SCIP_RETCODE SCIPaddVarSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
 
SCIP_RETCODE SCIPappendVarSOS2 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
int SCIPgetNVarsSOS2 (SCIP *scip, SCIP_CONS *cons)
 
SCIP_VAR ** SCIPgetVarsSOS2 (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real * SCIPgetWeightsSOS2 (SCIP *scip, SCIP_CONS *cons)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME   "SOS2"

Definition at line 79 of file cons_sos2.c.

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSENFORELAX(), SCIP_DECL_CONSEXITSOL(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_CONSPRINT(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSRESPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), SCIP_DECL_CONSTRANS(), SCIPaddVarSOS2(), SCIPappendVarSOS2(), SCIPcreateConsSOS2(), SCIPgetNVarsSOS2(), SCIPgetVarsSOS2(), SCIPgetWeightsSOS2(), and SCIPincludeConshdlrSOS2().

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "SOS2 constraint handler"

Definition at line 80 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   10

priority of the constraint handler for separation

Definition at line 81 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   100

priority of the constraint handler for constraint enforcing

Definition at line 82 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -10

priority of the constraint handler for checking feasibility

Definition at line 83 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   0

frequency for separating cuts; zero means to separate only in the root node

Definition at line 84 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 85 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 86 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 89 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 90 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 91 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 92 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 94 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST

Definition at line 95 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "SOS2"

Definition at line 98 of file cons_sos2.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrSOS2().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC   "bound change event handler for SOS2 constraints"

Definition at line 99 of file cons_sos2.c.

Referenced by SCIPincludeConshdlrSOS2().

Function Documentation

◆ fixVariableZeroNode()

static SCIP_RETCODE fixVariableZeroNode ( SCIP *  scip,
SCIP_VAR *  var,
SCIP_NODE *  node,
SCIP_Bool *  infeasible 
)
static

fix variable in given node to 0 or add constraint if variable is multi-aggregated

Parameters
scipSCIP pointer
varvariable to be fixed to 0
nodenode
infeasibleif fixing is infeasible

Definition at line 122 of file cons_sos2.c.

References FALSE, inferVariableZero(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

Referenced by enforceSOS2().

◆ inferVariableZero()

static SCIP_RETCODE inferVariableZero ( SCIP *  scip,
SCIP_VAR *  var,
SCIP_CONS *  cons,
int  inferinfo,
SCIP_Bool *  infeasible,
SCIP_Bool *  tightened,
SCIP_Bool *  success 
)
static

fix variable in local node to 0, and return whether the operation was feasible

Note
We do not add a linear constraint if the variable is multi-aggregated as in fixVariableZeroNode(), since this would be too time consuming.
Parameters
scipSCIP pointer
varvariable to be fixed to 0
consconstraint
inferinfoinfo for reverse prop.
infeasibleif fixing is infeasible
tightenedif fixing was performed
successwhether fixing was successful, i.e., variable is not multi-aggregated

Definition at line 173 of file cons_sos2.c.

References FALSE, lockVariableSOS2(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

Referenced by fixVariableZeroNode(), and propSOS2().

◆ lockVariableSOS2()

static SCIP_RETCODE lockVariableSOS2 ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_VAR *  var 
)
static

add lock on variable

Parameters
scipSCIP data structure
consconstraint
varvariable

Definition at line 216 of file cons_sos2.c.

References SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and unlockVariableSOS2().

Referenced by handleNewVariableSOS2(), inferVariableZero(), and presolRoundSOS2().

◆ unlockVariableSOS2()

static SCIP_RETCODE unlockVariableSOS2 ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_VAR *  var 
)
static
Parameters
scipSCIP data structure
consconstraint
varvariable

Definition at line 235 of file cons_sos2.c.

References consdataEnsurevarsSizeSOS2(), SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPunlockVarCons(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by deleteVarSOS2(), lockVariableSOS2(), and presolRoundSOS2().

◆ consdataEnsurevarsSizeSOS2()

static SCIP_RETCODE consdataEnsurevarsSizeSOS2 ( SCIP *  scip,
SCIP_CONSDATA *  consdata,
int  num,
SCIP_Bool  reserveWeights 
)
static

ensures that the vars and weights array can store at least num entries

Parameters
scipSCIP data structure
consdataconstraint data
numminimum number of entries to store
reserveWeightswhether the weights array is handled

Definition at line 254 of file cons_sos2.c.

References handleNewVariableSOS2(), SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by addVarSOS2(), appendVarSOS2(), and unlockVariableSOS2().

◆ handleNewVariableSOS2()

static SCIP_RETCODE handleNewVariableSOS2 ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_CONSDATA *  consdata,
SCIP_VAR *  var,
SCIP_Bool  transformed 
)
static

handle new variable

Parameters
scipSCIP data structure
consconstraint
consdataconstraint data
varvariable
transformedwhether original variable was transformed

Definition at line 282 of file cons_sos2.c.

References addVarSOS2(), lockVariableSOS2(), SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIProwGetLhs(), SCIProwGetRhs(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by addVarSOS2(), appendVarSOS2(), and consdataEnsurevarsSizeSOS2().

◆ addVarSOS2()

static SCIP_RETCODE addVarSOS2 ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_VAR *  var,
SCIP_Real  weight 
)
static

adds a variable to an SOS2 constraint, a position given by weight - ascending order

Parameters
scipSCIP data structure
consconstraint
varvariable to add to the constraint
weightweight to determine position

Definition at line 339 of file cons_sos2.c.

References appendVarSOS2(), consdataEnsurevarsSizeSOS2(), handleNewVariableSOS2(), SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.

Referenced by handleNewVariableSOS2(), and SCIPaddVarSOS2().

◆ appendVarSOS2()

static SCIP_RETCODE appendVarSOS2 ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_VAR *  var 
)
static

appends a variable to an SOS2 constraint

Parameters
scipSCIP data structure
consconstraint
varvariable to add to the constraint

Definition at line 407 of file cons_sos2.c.

References consdataEnsurevarsSizeSOS2(), deleteVarSOS2(), FALSE, handleNewVariableSOS2(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), and SCIPvarIsTransformed().

Referenced by addVarSOS2(), and SCIPappendVarSOS2().

◆ deleteVarSOS2()

static SCIP_RETCODE deleteVarSOS2 ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_CONSDATA *  consdata,
SCIP_EVENTHDLR *  eventhdlr,
int  pos 
)
static

deletes a variable of an SOS2 constraint

Parameters
scipSCIP data structure
consconstraint
consdataconstraint data
eventhdlrcorresponding event handler
posposition of variable in array

Definition at line 451 of file cons_sos2.c.

References presolRoundSOS2(), SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS2().

Referenced by appendVarSOS2(), and presolRoundSOS2().

◆ presolRoundSOS2()

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 
)
static

perform one presolving round

We perform the following presolving steps.

  • If the bounds of one variable force it to be nonzero, we can fix all other variables with distance at least two to zero. If two variables are certain to be nonzero, we can fix all other variables to 0 and remove the constraint.
  • All variables fixed to zero, that are at the beginning or end of the constraint can be removed.
  • We substitute appregated variables.
  • If a constraint has at most two variables, we delete it.

We currently do not handle the following:

  • If we have at least two variables fixed to zero next to each-other, that are positioned in the inner part of this constraint, we can delete all but one of these variables.
  • If a variable appears twice not next to each-other, it can be fixed to 0. If one variable appears next to each-other and is already certain to be nonzero, we can fix all variables.
  • If a binary variable and its negation appear in the constraint, we might fix variables to zero or can forbid a zero value for them.
  • When, after removing all zero "border" variables, a constraint with more than two variables has at most two variables that are not fixed to 0, only one of these can take a nonzero value, because these variables need to be the "border" variables of this constraint. The same holds if we have exactly three variables in one constraint and the middle variable is certain to be not zero. In both cases we can upgrade this constraint constraint to an sos1 consisting only of the "border" variables. If these "border" variables are negations of each other, we can delete this constraint.
  • When, after removing all variables fixed to 0, that are possible, in a constraint each even positioned variable is fixed to 0, we can upgrade this constraint to an sos1 that holds all non-fixed variables.
  • Extract cliques for all odd and also for all even positioned binary variables
Parameters
scipSCIP pointer
consconstraint
consdataconstraint data
eventhdlrevent handler
cutoffwhether a cutoff happened
successwhether we performed a successful reduction
ndelconssnumber of deleted constraints
nfixedvarsnumber of fixed variables
nremovedvarsnumber of variables removed

Definition at line 511 of file cons_sos2.c.

References deleteVarSOS2(), FALSE, lockVariableSOS2(), propSOS2(), SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIP_Real, SCIPcatchVarEvent(), SCIPconsGetName(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelCons(), SCIPdropVarEvent(), SCIPfixVar(), SCIPgetProbvarSum(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and unlockVariableSOS2().

Referenced by deleteVarSOS2(), and SCIP_DECL_CONSPRESOL().

◆ propSOS2()

static SCIP_RETCODE propSOS2 ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_CONSDATA *  consdata,
SCIP_Bool *  cutoff,
int *  ngen 
)
static

propagate variables

Parameters
scipSCIP pointer
consconstraint
consdataconstraint data
cutoffwhether a cutoff happened
ngenpointer to incremental counter for domain changes

Definition at line 792 of file cons_sos2.c.

References enforceSOS2(), FALSE, inferVariableZero(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by enforceSOS2(), presolRoundSOS2(), and SCIP_DECL_CONSPROP().

◆ enforceSOS2()

static SCIP_RETCODE enforceSOS2 ( SCIP *  scip,
SCIP_CONSHDLR *  conshdlr,
int  nconss,
SCIP_CONS **  conss,
SCIP_SOL *  sol,
SCIP_RESULT *  result 
)
static

enforcement method

We check whether the current solution is feasible, i.e., contains at most one nonzero variable. If not, we branch along the lines indicated by Beale and Tomlin:

We first compute \(W = \sum_{j=1}^n |x_i|\) and \(w = \sum_{j=1}^n j\, |x_i|\). Then we search for the index \(k\) that satisfies

\[ k \leq \frac{w}{W} < k+1. \]

The branches are then

\[ x_1 = 0, \ldots, x_{k-1} = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0. \]

There is one special case that we have to consider: It can happen that \(k\) is one too small. Example: \(x_1 = 1 - \epsilon, x_2 = 0, x_3 = \epsilon\). Then \(w = 1 - \epsilon + 3 \epsilon = 1 + 2 \epsilon\). This yields \(k = 1\) and hence the first branch does not change the solution. We therefore increase \(k\) by one if \(x_k \neq 0\). This is valid, since we know that \(x_{k+1} \neq 0\) (with respect to the original \(k\)); the corresponding branch will cut off the current solution, since \(x_k \neq 0\).

Parameters
scipSCIP pointer
conshdlrconstraint handler
nconssnumber of constraints
conssindicator constraints
solsolution to be enforced (NULL for LP solution)
resultresult

Definition at line 990 of file cons_sos2.c.

References branchCons(), fixVariableZeroNode(), generateRowSOS2(), propSOS2(), REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMsg, SCIPfeasFloor(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPresetConsAge(), and SCIPvarGetName().

Referenced by propSOS2(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().

◆ generateRowSOS2()

static SCIP_RETCODE generateRowSOS2 ( SCIP *  scip,
SCIP_CONSHDLR *  conshdlr,
SCIP_CONS *  cons,
SCIP_Bool  local 
)
static

Generate basic row

We generate the row corresponding to the following simple valid inequalities. Let \(U\) and \(U'\) be the largest and second largest upper bound of variables appearing in the constraint. Similarly let \(L\) and \(L'\) be the smallest and second smallest lower bound. The inequalities are:

\[ x_1 + \ldots + x_n \leq U + U' \qquad\mbox{and}\qquad x_1 + \ldots + x_n \geq L + L'. \]

Of course, these inequalities are only added if the upper and lower bounds are all finite and \(L+L' < 0\) or \(U+U' > 0\).

Parameters
scipSCIP pointer
conshdlrconstraint handler
consconstraint
localproduce local cut?

Definition at line 1194 of file cons_sos2.c.

References FALSE, REALABS, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRowSameCoef(), SCIPconsGetData(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPprintRow(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by enforceSOS2(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySOS2  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 1293 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrSOS2(), and TRUE.

Referenced by generateRowSOS2().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeSOS2  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 1310 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolSOS2  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 1329 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, and SCIPreleaseRow().

Referenced by SCIP_DECL_CONSFREE().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteSOS2  )
static

frees specific constraint data

Definition at line 1361 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSTRANS(), SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPdropVarEvent(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseRow().

Referenced by SCIP_DECL_CONSEXITSOL().

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransSOS2  )
static

transforms constraint data into data belonging to the transformed problem

Definition at line 1410 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSPRESOL(), SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcatchVarEvent(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetTransformedVar(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPsnprintf(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_CONSDELETE().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolSOS2  )
static

presolving method of constraint handler

Definition at line 1493 of file cons_sos2.c.

References CONSHDLR_NAME, presolRoundSOS2(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSINITLP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsModifiable(), SCIPdebug, and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpSOS2  )
static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 1566 of file cons_sos2.c.

References CONSHDLR_NAME, FALSE, generateRowSOS2(), REALABS, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMsg, SCIPisInfinity(), SCIPprintRow(), SCIProwGetLhs(), SCIProwGetRhs(), and SCIProwIsInLP().

Referenced by SCIP_DECL_CONSPRESOL().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpSOS2  )
static

separation method of constraint handler for LP solutions

Definition at line 1610 of file cons_sos2.c.

References CONSHDLR_NAME, FALSE, generateRowSOS2(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSSEPASOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMsg, SCIPisCutEfficacious(), SCIPprintRow(), SCIPresetConsAge(), and SCIProwIsInLP().

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSOS2  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 1666 of file cons_sos2.c.

References CONSHDLR_NAME, FALSE, generateRowSOS2(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMsg, SCIPisCutEfficacious(), SCIPprintRow(), SCIPresetConsAge(), and SCIProwIsInLP().

Referenced by SCIP_DECL_CONSSEPALP().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpSOS2  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 1722 of file cons_sos2.c.

References CONSHDLR_NAME, enforceSOS2(), SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_OKAY, and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxSOS2  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 1738 of file cons_sos2.c.

References CONSHDLR_NAME, enforceSOS2(), SCIP_CALL, SCIP_DECL_CONSENFOPS(), SCIP_OKAY, and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsSOS2  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 1754 of file cons_sos2.c.

References CONSHDLR_NAME, enforceSOS2(), SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_OKAY, and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckSOS2  )
static

feasibility check method of constraint handler for integral solutions

We simply check whether at most two variable are nonzero and in the case there are exactly two nonzero, then they have to be direct neighbors in the given solution.

Definition at line 1775 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasZero(), SCIPprintCons(), SCIPresetConsAge(), SCIPupdateSolConsViolation(), and SCIPvarGetName().

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropSOS2  )
static

domain propagation method of constraint handler

Definition at line 1844 of file cons_sos2.c.

References CONSHDLR_NAME, propSOS2(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSRESPROP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, and SCIPisTransformed().

Referenced by SCIP_DECL_CONSCHECK().

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropSOS2  )
static

propagation conflict resolving method of constraint handler

We check which bound changes were the reason for infeasibility. We use that inferinfo stores the index of the variable that has bounds that fix it to be nonzero (these bounds are the reason).

Definition at line 1893 of file cons_sos2.c.

References CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_DECL_CONSLOCK(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisFeasNegative(), and SCIPisFeasPositive().

Referenced by SCIP_DECL_CONSPROP().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockSOS2  )
static

variable rounding lock method of constraint handler

Let lb and ub be the lower and upper bounds of a variable. Preprocessing usually makes sure that lb <= 0 <= ub.

  • If lb < 0 then rounding down may violate the constraint.
  • If ub > 0 then rounding up may violated the constraint.
  • If lb > 0 or ub < 0 then the constraint is infeasible and we do not have to deal with it here.
  • If lb == 0 then rounding down does not violate the constraint.
  • If ub == 0 then rounding up does not violate the constraint.

Definition at line 1945 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_OKAY, SCIPaddVarLocks(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintSOS2  )
static

constraint display method of constraint handler

Definition at line 1985 of file cons_sos2.c.

References CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), and SCIPwriteVarName().

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopySOS2  )
static

constraint copying method of constraint handler

Definition at line 2015 of file cons_sos2.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSPARSE(), SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsSOS2(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetVarCopy(), and TRUE.

Referenced by SCIP_DECL_CONSPRINT().

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseSOS2  )
static

constraint parsing method of constraint handler

Definition at line 2081 of file cons_sos2.c.

References FALSE, SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPaddVarSOS2(), SCIPcreateConsSOS2(), SCIPparseVarName(), SCIPverbMessage(), and TRUE.

Referenced by SCIP_DECL_CONSCOPY().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsSOS2  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 2139 of file cons_sos2.c.

References BMScopyMemoryArray, FALSE, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

Referenced by SCIP_DECL_CONSPARSE().

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSOS2  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 2162 of file cons_sos2.c.

References SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecSOS2  )
static

Definition at line 2183 of file cons_sos2.c.

References EVENTHDLR_NAME, SCIP_EVENTTYPE_LBRELAXED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBRELAXED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPerrorMessage, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPincludeConshdlrSOS2(), SCIPisFeasNegative(), SCIPisFeasPositive(), and SCIPvarGetName().

Referenced by SCIP_DECL_CONSGETNVARS().