Detailed Description

constraint handler for SOS type 1 constraints

Author: Tobias Fischer; Marc Pfetsch

A specially ordered set of type 1 (SOS1) is a sequence of variables such that at most one variable is nonzero. The special case of two variables arises, for instance, from equilibrium or complementary conditions like $x \cdot y = 0$ . Note that it is in principle allowed that a variables appears twice, but it then can be fixed to 0.

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 SCIPcreateConsSOS1() and weights are given, the weights determine the order (decreasing weights). Additional variables can be added with SCIPaddVarSOS1(), which adds a variable with given weight.
If an empty constraint is created and then variables are added with SCIPaddVarSOS1(), weights are needed and stored.
All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are added with SCIPappendVarSOS1().

The validity of the constraint is enforced by the classical SOS branching. Depending on the parameters there are two ways to choose the branching constraint. Either the constraint with the most number of nonzeros is chosen or the constraint with the largest nonzero-variable weight. The later version allows the user to specify an order for the branching importance of the constraints. Constraint branching can also be turned off.

Definition in file cons_sos1.c.

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

Go to the source code of this file.

Macros
#define	CONSHDLR_NAME "SOS1"

#define	CONSHDLR_DESC "SOS1 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_DELAYPRESOL FALSE

#define	CONSHDLR_NEEDSCONS TRUE

#define	CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

#define	EVENTHDLR_NAME "SOS1"

#define	EVENTHDLR_DESC "bound change event handler for SOS1 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	lockVariableSOS1 (SCIP scip, SCIP_CONS cons, SCIP_VAR *var)

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

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

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

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

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

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

static SCIP_RETCODE	presolRoundSOS1 (SCIP scip, SCIP_CONS cons, SCIP_CONSDATA consdata, SCIP_EVENTHDLR eventhdlr, SCIP_Bool cutoff, SCIP_Bool success, int ndelconss, int nupgdconss, int nfixedvars, int nremovedvars)

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

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

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

static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopySOS1)

static	SCIP_DECL_CONSFREE (consFreeSOS1)

static	SCIP_DECL_CONSEXITSOL (consExitsolSOS1)

static	SCIP_DECL_CONSDELETE (consDeleteSOS1)

static	SCIP_DECL_CONSTRANS (consTransSOS1)

static	SCIP_DECL_CONSPRESOL (consPresolSOS1)

static	SCIP_DECL_CONSINITLP (consInitlpSOS1)

static	SCIP_DECL_CONSSEPALP (consSepalpSOS1)

static	SCIP_DECL_CONSSEPASOL (consSepasolSOS1)

static	SCIP_DECL_CONSENFOLP (consEnfolpSOS1)

static	SCIP_DECL_CONSENFOPS (consEnfopsSOS1)

static	SCIP_DECL_CONSCHECK (consCheckSOS1)

static	SCIP_DECL_CONSPROP (consPropSOS1)

static	SCIP_DECL_CONSRESPROP (consRespropSOS1)

static	SCIP_DECL_CONSLOCK (consLockSOS1)

static	SCIP_DECL_CONSPRINT (consPrintSOS1)

static	SCIP_DECL_CONSCOPY (consCopySOS1)

static	SCIP_DECL_CONSPARSE (consParseSOS1)

static	SCIP_DECL_CONSGETVARS (consGetVarsSOS1)

static	SCIP_DECL_CONSGETNVARS (consGetNVarsSOS1)

static	SCIP_DECL_EVENTEXEC (eventExecSOS1)

SCIP_RETCODE	SCIPincludeConshdlrSOS1 (SCIP *scip)

SCIP_RETCODE	SCIPcreateConsSOS1 (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	SCIPcreateConsBasicSOS1 (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR *vars, SCIP_Real weights)

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

SCIP_RETCODE	SCIPappendVarSOS1 (SCIP scip, SCIP_CONS cons, SCIP_VAR *var)

int	SCIPgetNVarsSOS1 (SCIP scip, SCIP_CONS cons)

SCIP_VAR **	SCIPgetVarsSOS1 (SCIP scip, SCIP_CONS cons)

SCIP_Real *	SCIPgetWeightsSOS1 (SCIP scip, SCIP_CONS cons)

Macro Definition Documentation

#define CONSHDLR_DESC "SOS1 constraint handler"

Definition at line 67 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_SEPAPRIORITY 10

priority of the constraint handler for separation

Definition at line 68 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_ENFOPRIORITY 100

priority of the constraint handler for constraint enforcing

Definition at line 69 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_CHECKPRIORITY -10

priority of the constraint handler for checking feasibility

Definition at line 70 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_SEPAFREQ 0

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

Definition at line 71 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 72 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#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 73 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_MAXPREROUNDS -1

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

Definition at line 76 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 77 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 78 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_DELAYPRESOL FALSE

should presolving method be delayed, if other presolvers found reductions?

Definition at line 79 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 80 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 82 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

#define EVENTHDLR_NAME "SOS1"

Definition at line 85 of file cons_sos1.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrSOS1().

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

Definition at line 86 of file cons_sos1.c.

Referenced by SCIPincludeConshdlrSOS1().

Function Documentation

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

scip	SCIP pointer
var	variable to be fixed to 0
node	node
infeasible	if fixing is infeasible

Definition at line 113 of file cons_sos1.c.

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

Referenced by enforceSOS1().

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

scip	SCIP pointer
var	variable to be fixed to 0
cons	constraint
inferinfo	info for reverse prop.
infeasible	if fixing is infeasible
tightened	if fixing was performed
success	whether fixing was successful, i.e., variable is not multi-aggregated

Definition at line 164 of file cons_sos1.c.

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

Referenced by propSOS1().

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

static

add lock on variable

Parameters

scip	SCIP data structure
cons	constraint
var	variable

Definition at line 207 of file cons_sos1.c.

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

Referenced by handleNewVariableSOS1(), and presolRoundSOS1().

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

static

Parameters

scip	SCIP data structure
cons	constraint
var	variable

Definition at line 226 of file cons_sos1.c.

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

Referenced by deleteVarSOS1(), and presolRoundSOS1().

static SCIP_RETCODE consdataEnsurevarsSizeSOS1	(	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

scip	SCIP data structure
consdata	constraint data
num	minimum number of entries to store
reserveWeights	whether the weights array is handled

Definition at line 245 of file cons_sos1.c.

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

Referenced by addVarSOS1(), and appendVarSOS1().

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

static

handle new variable

Parameters

scip	SCIP data structure
cons	constraint
consdata	constraint data
var	variable
transformed	whether original variable was transformed

Definition at line 273 of file cons_sos1.c.

References lockVariableSOS1(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by addVarSOS1(), appendVarSOS1(), and SCIPcreateConsSOS1().

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

static

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

Parameters

scip	SCIP data structure
cons	constraint
var	variable to add to the constraint
weight	weight to determine position

Definition at line 329 of file cons_sos1.c.

References consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.

Referenced by SCIPaddVarSOS1().

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

static

appends a variable to an SOS1 constraint

Parameters

scip	SCIP data structure
cons	constraint
var	variable to add to the constraint

Definition at line 397 of file cons_sos1.c.

References consdataEnsurevarsSizeSOS1(), FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), and SCIPvarIsTransformed().

Referenced by SCIPappendVarSOS1().

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

static

deletes a variable of an SOS1 constraint

Parameters

scip	SCIP data structure
cons	constraint
consdata	constraint data
eventhdlr	corresponding event handler
pos	position of variable in array

Definition at line 441 of file cons_sos1.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1().

Referenced by presolRoundSOS1().

static SCIP_RETCODE presolRoundSOS1	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSDATA *	consdata,
		SCIP_EVENTHDLR *	eventhdlr,
		SCIP_Bool *	cutoff,
		SCIP_Bool *	success,
		int *	ndelconss,
		int *	nupgdconss,
		int *	nfixedvars,
		int *	nremovedvars
	)

static

perform one presolving round

We perform the following presolving steps.

If the bounds of some variable force it to be nonzero, we can fix all other variables to zero and remove the SOS1 constraints that contain it.
If a variable is fixed to zero, we can remove the variable.
If a variable appears twice, it can be fixed to 0.
We substitute appregated variables.

Parameters

scip	SCIP pointer
cons	constraint
consdata	constraint data
eventhdlr	event handler
cutoff	whether a cutoff happened
success	whether we performed a successful reduction
ndelconss	number of deleted constraints
nupgdconss	number of upgraded constraints
nfixedvars	number of fixed variables
nremovedvars	number of variables removed

Definition at line 484 of file cons_sos1.c.

References deleteVarSOS1(), FALSE, lockVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcatchVarEvent(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMessage, SCIPdelCons(), SCIPdropVarEvent(), SCIPfixVar(), SCIPgetProbvarSum(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, and unlockVariableSOS1().

Referenced by SCIP_DECL_CONSPRESOL().

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

static

propagate variables

Parameters

scip	SCIP pointer
cons	constraint
consdata	constraint data
cutoff	whether a cutoff happened
ngen	pointer to incremental counter for domain changes

Definition at line 684 of file cons_sos1.c.

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

Referenced by enforceSOS1(), and SCIP_DECL_CONSPROP().

static SCIP_RETCODE enforceSOS1	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		int	nconss,
		SCIP_CONS **	conss,
		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 = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0.$

If the constraint contains two variables, the branching of course simplifies.

Depending on the parameters (branchnonzeros, branchweight) there are three ways to choose the branching constraint.

`branchnonzeros`	`branchweight`	constraint chosen
`true`	?	most number of nonzeros
`false`	`true`	maximal weight corresponding to nonzero variable
`false`	`true`	largest sum of variable values

branchnonzeros = false, branchweight = true allows the user to specify an order for the branching importance of the constraints (setting the weights accordingly).

Constraint branching can also be turned off using parameter branchsos.

Parameters

scip	SCIP pointer
conshdlr	constraint handler
nconss	number of constraints
conss	indicator constraints
result	result

Definition at line 815 of file cons_sos1.c.

References branchCons(), fixVariableZeroNode(), NULL, propSOS1(), REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_REDUCEDDOM, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMessage, SCIPfloor(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPresetConsAge(), and SCIPvarGetName().

Referenced by SCIP_DECL_CONSENFOLP(), and SCIP_DECL_CONSENFOPS().

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

static

Generate row

We generate the row corresponding to the following simple valid inequalities:

$\frac{x_1}{u_1} + \ldots + \frac{x_n}{u_n} \leq 1\qquad\mbox{and}\qquad \frac{x_1}{\ell_1} + \ldots + \frac{x_n}{\ell_1} \leq 1,$

where $\ell_1, \ldots, \ell_n$ and $u_1, \ldots, u_n$ are the nonzero and finite lower and upper bounds of the variables $x_1, \ldots, x_n$ . If an upper bound < 0 or a lower bound > 0, the constraint itself is redundant, so the cut is not applied (lower bounds > 0 and upper bounds < 0 are usually detected in presolving or propagation). Infinite bounds and zero are skipped. Thus $\ell_1, \ldots, \ell_n$ are all negative, which results in the $\leq$ inequality.

Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most interesting.

Parameters

scip	SCIP pointer
conshdlr	constraint handler
cons	constraint
local	produce local cut?

Definition at line 1059 of file cons_sos1.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPfreeBufferArray, SCIPinfinity(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPprintRow(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

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

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySOS1 )

static

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

Definition at line 1167 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrSOS1(), and TRUE.

static SCIP_DECL_CONSFREE ( consFreeSOS1 )

static

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

Definition at line 1184 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfreeMemory.

static SCIP_DECL_CONSEXITSOL ( consExitsolSOS1 )

static

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

Definition at line 1203 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMessage, and SCIPreleaseRow().

static SCIP_DECL_CONSDELETE ( consDeleteSOS1 )

static

frees specific constraint data

Definition at line 1239 of file cons_sos1.c.

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

static SCIP_DECL_CONSTRANS ( consTransSOS1 )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 1293 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, 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(), SCIPdebugMessage, SCIPduplicateBlockMemoryArray, SCIPgetTransformedVar(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPsnprintf(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

static SCIP_DECL_CONSPRESOL ( consPresolSOS1 )

static

presolving method of constraint handler

Definition at line 1377 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, presolRoundSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsModifiable(), and SCIPdebugMessage.

static SCIP_DECL_CONSINITLP ( consInitlpSOS1 )

static

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

Definition at line 1451 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, generateRowSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMessage, SCIPisEQ(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetLhs(), SCIProwGetRhs(), and SCIProwIsInLP().

static SCIP_DECL_CONSSEPALP ( consSepalpSOS1 )

static

separation method of constraint handler for LP solutions

Definition at line 1506 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, generateRowSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMessage, SCIPisCutEfficacious(), SCIPisEQ(), SCIPisInfinity(), SCIPprintRow(), SCIPresetConsAge(), SCIProwGetLhs(), SCIProwGetRhs(), and SCIProwIsInLP().

static SCIP_DECL_CONSSEPASOL ( consSepasolSOS1 )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 1574 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, generateRowSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMessage, SCIPisCutEfficacious(), SCIPisEQ(), SCIPisInfinity(), SCIPprintRow(), SCIPresetConsAge(), SCIProwGetLhs(), SCIProwGetRhs(), and SCIProwIsInLP().

static SCIP_DECL_CONSENFOLP ( consEnfolpSOS1 )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 1642 of file cons_sos1.c.

References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().

static SCIP_DECL_CONSENFOPS ( consEnfopsSOS1 )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 1658 of file cons_sos1.c.

References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().

static SCIP_DECL_CONSCHECK ( consCheckSOS1 )

static

feasibility check method of constraint handler for integral solutions

We simply check whether at most one variable is nonzero in the given solution.

Definition at line 1677 of file cons_sos1.c.

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

static SCIP_DECL_CONSPROP ( consPropSOS1 )

static

domain propagation method of constraint handler

Definition at line 1745 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, propSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMessage, and SCIPisTransformed().

static SCIP_DECL_CONSRESPROP ( consRespropSOS1 )

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 1794 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbAtIndex(), and SCIPvarGetUbAtIndex().

static SCIP_DECL_CONSLOCK ( consLockSOS1 )

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 1846 of file cons_sos1.c.

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

static SCIP_DECL_CONSPRINT ( consPrintSOS1 )

static

constraint display method of constraint handler

Definition at line 1890 of file cons_sos1.c.

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

static SCIP_DECL_CONSCOPY ( consCopySOS1 )

static

constraint copying method of constraint handler

Definition at line 1920 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsSOS1(), SCIPdebugMessage, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetVarCopy(), and TRUE.

static SCIP_DECL_CONSPARSE ( consParseSOS1 )

static

constraint parsing method of constraint handler

Definition at line 1986 of file cons_sos1.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPaddVarSOS1(), SCIPcreateConsSOS1(), SCIPparseVarName(), SCIPverbMessage(), and TRUE.

static SCIP_DECL_CONSGETVARS ( consGetVarsSOS1 )

static

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

Definition at line 2044 of file cons_sos1.c.

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

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSOS1 )

static

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

Definition at line 2067 of file cons_sos1.c.

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

static SCIP_DECL_EVENTEXEC ( eventExecSOS1 )

static

SCIP_RETCODE SCIPincludeConshdlrSOS1 ( SCIP * scip )

creates the handler for SOS1 constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2146 of file cons_sos1.c.

References CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPRESOL, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPaddBoolParam(), SCIPallocMemory, SCIPerrorMessage, SCIPincludeConshdlrBasic(), SCIPincludeEventhdlrBasic(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDelete(), SCIPsetConshdlrExitsol(), SCIPsetConshdlrFree(), SCIPsetConshdlrGetNVars(), SCIPsetConshdlrGetVars(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrParse(), SCIPsetConshdlrPresol(), SCIPsetConshdlrPrint(), SCIPsetConshdlrProp(), SCIPsetConshdlrResprop(), SCIPsetConshdlrSepa(), SCIPsetConshdlrTrans(), and TRUE.

Referenced by SCIP_DECL_CONSHDLRCOPY(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPcreateConsSOS1	(	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
	)

creates and captures a SOS1 constraint

We set the constraint to not be modifable. If the weights are non NULL, the variables are ordered according to these weights (in ascending order).

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries
weights	weights determining the variable order, or NULL if natural order should be used
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnode	should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 2213 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STAGE_TRANSFORMED, SCIPallocBlockMemory, SCIPconsIsTransformed(), SCIPcreateCons(), SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfindConshdlr(), SCIPgetStage(), SCIPgetTransformedVar(), SCIPsortRealPtr(), and SCIPvarIsTransformed().

Referenced by readSOS(), readSos(), readSOScons(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), and SCIPcreateConsBasicSOS1().

SCIP_RETCODE SCIPcreateConsBasicSOS1	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_Real *	weights
	)

creates and captures a SOS1 constraint with all constraint flags set to their default values.

Warning: Do NOT set the constraint to be modifiable manually, because this might lead to wrong results as the variable array will not be resorted

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries
weights	weights determining the variable order, or NULL if natural order should be used

Definition at line 2321 of file cons_sos1.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPcreateConsSOS1(), and TRUE.

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

adds variable to SOS1 constraint, the position is determined by the given weight

Parameters

scip	SCIP data structure
cons	constraint
var	variable to add to the constraint
weight	weight determining position of variable

Definition at line 2337 of file cons_sos1.c.

References addVarSOS1(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPerrorMessage, and SCIPvarGetName().

Referenced by readSOS(), readSos(), readSOScons(), and SCIP_DECL_CONSPARSE().

SCIP_RETCODE SCIPappendVarSOS1	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

appends variable to SOS1 constraint

Parameters

scip	SCIP data structure
cons	constraint
var	variable to add to the constraint

Definition at line 2363 of file cons_sos1.c.

References appendVarSOS1(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPerrorMessage, and SCIPvarGetName().

int SCIPgetNVarsSOS1	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets number of variables in SOS1 constraint

Parameters

scip	SCIP data structure
cons	constraint

Definition at line 2388 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp().

SCIP_VAR** SCIPgetVarsSOS1	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets array of variables in SOS1 constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 2413 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp().

SCIP_Real* SCIPgetWeightsSOS1	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets array of weights in SOS1 constraint (or NULL if not existent)

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 2438 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by SCIP_DECL_READERWRITE(), and SCIPwriteLp().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation