Detailed Description

constraint handler for cardinality constraints

Author: Tobias Fischer

This constraint handler handles cardinality constraints of the form

\[ |\mbox{supp}(x)| \leq b \]

with integer right-hand side \(b\). Here, \(|\mbox{supp}(x)|\) denotes the number of nonzero entries of the vector \(x\).

Note that cardinality constraints generalize special ordered set of type one (SOS1) constraints in which \(b = 1\).

The implementation of this constraint handler is based on
"On the Structure of Linear Programs with Overlapping Cardinality Constraints"
T. Fischer and M. E. Pfetsch, Tech. rep., 2016

Definition in file cons_cardinality.c.

#include "blockmemshell/memory.h"
#include "scip/cons_cardinality.h"
#include "scip/cons_knapsack.h"
#include "scip/cons_linear.h"
#include "scip/pub_cons.h"
#include "scip/pub_event.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/symmetry_graph.h"
#include "symmetry/struct_symmetry.h"
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

Macros
#define	CONSHDLR_NAME "cardinality"

#define	CONSHDLR_DESC "cardinality constraint handler"

#define	CONSHDLR_SEPAPRIORITY 10

#define	CONSHDLR_ENFOPRIORITY 100

#define	CONSHDLR_CHECKPRIORITY -10

#define	CONSHDLR_SEPAFREQ 10

#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	DEFAULT_BRANCHBALANCED FALSE

#define	DEFAULT_BALANCEDDEPTH 20

#define	DEFAULT_BALANCEDCUTOFF 2.0

#define	EVENTHDLR_NAME "cardinality"

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

#define	EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED \| SCIP_EVENTTYPE_GBDCHANGED)

Functions
static SCIP_RETCODE	catchVarEventCardinality (SCIP scip, SCIP_EVENTHDLR eventhdlr, SCIP_CONSDATA consdata, SCIP_VAR var, SCIP_VAR indvar, int pos, SCIP_EVENTDATA *eventdata)

static SCIP_RETCODE	dropVarEventCardinality (SCIP scip, SCIP_EVENTHDLR eventhdlr, SCIP_CONSDATA consdata, SCIP_VAR var, SCIP_VAR indvar, SCIP_EVENTDATA *eventdata)

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

static SCIP_RETCODE	fixVariableZero (SCIP scip, SCIP_VAR var, SCIP_Bool infeasible, SCIP_Bool tightened)

static SCIP_RETCODE	lockVariableCardinality (SCIP scip, SCIP_CONS cons, SCIP_VAR var, SCIP_VAR indvar)

static SCIP_RETCODE	unlockVariableCardinality (SCIP scip, SCIP_CONS cons, SCIP_VAR var, SCIP_VAR indvar)

static SCIP_RETCODE	consdataEnsurevarsSizeCardinality (SCIP scip, SCIP_CONSDATA consdata, int num, SCIP_Bool reserveweights)

static SCIP_RETCODE	handleNewVariableCardinality (SCIP scip, SCIP_CONS cons, SCIP_CONSDATA consdata, SCIP_CONSHDLRDATA conshdlrdata, SCIP_VAR var, SCIP_VAR indvar, int pos, SCIP_Bool transformed, SCIP_EVENTDATA **eventdata)

static SCIP_RETCODE	addVarCardinality (SCIP scip, SCIP_CONS cons, SCIP_CONSHDLRDATA conshdlrdata, SCIP_VAR var, SCIP_VAR *indvar, SCIP_Real weight)

static SCIP_RETCODE	appendVarCardinality (SCIP scip, SCIP_CONS cons, SCIP_CONSHDLRDATA conshdlrdata, SCIP_VAR var, SCIP_VAR *indvar)

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

static SCIP_RETCODE	polishPrimalSolution (SCIP scip, SCIP_CONS conss, int nconss, SCIP_SOL sol, SCIP_SOL *primsol)

static void	consdataUnmarkEventdataVars (SCIP_CONSDATA *consdata)

static SCIP_RETCODE	presolRoundCardinality (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	propCardinality (SCIP scip, SCIP_CONS cons, SCIP_CONSDATA consdata, SCIP_Bool cutoff, int *nchgdomain)

static SCIP_RETCODE	branchUnbalancedCardinality (SCIP scip, SCIP_SOL sol, SCIP_CONS branchcons, SCIP_VAR vars, SCIP_VAR *indvars, int nvars, int cardval, int branchnnonzero, int branchpos)

static SCIP_RETCODE	branchBalancedCardinality (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_SOL sol, SCIP_CONS branchcons, SCIP_VAR vars, SCIP_VAR indvars, int nvars, int cardval, int branchnnonzero, int branchpos, SCIP_Real balancedcutoff)

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

static SCIP_RETCODE	generateRowCardinality (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_CONS cons, SCIP_Bool local, SCIP_ROW rowlb, SCIP_ROW *rowub)

static SCIP_RETCODE	initsepaBoundInequalityFromCardinality (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_CONS *conss, int nconss, SCIP_SOL sol, SCIP_Bool solvedinitlp, int ngen, SCIP_Bool cutoff)

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

static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopyCardinality)

static	SCIP_DECL_CONSFREE (consFreeCardinality)

static	SCIP_DECL_CONSEXITSOL (consExitsolCardinality)

static	SCIP_DECL_CONSDELETE (consDeleteCardinality)

static	SCIP_DECL_CONSTRANS (consTransCardinality)

static	SCIP_DECL_CONSPRESOL (consPresolCardinality)

static	SCIP_DECL_CONSINITLP (consInitlpCardinality)

static	SCIP_DECL_CONSSEPALP (consSepalpCardinality)

static	SCIP_DECL_CONSSEPASOL (consSepasolCardinality)

static	SCIP_DECL_CONSENFOLP (consEnfolpCardinality)

static	SCIP_DECL_CONSENFORELAX (consEnforelaxCardinality)

static	SCIP_DECL_CONSENFOPS (consEnfopsCardinality)

static	SCIP_DECL_CONSCHECK (consCheckCardinality)

static	SCIP_DECL_CONSPROP (consPropCardinality)

static	SCIP_DECL_CONSLOCK (consLockCardinality)

static	SCIP_DECL_CONSPRINT (consPrintCardinality)

static	SCIP_DECL_CONSCOPY (consCopyCardinality)

static	SCIP_DECL_CONSPARSE (consParseCardinality)

static	SCIP_DECL_CONSGETVARS (consGetVarsCardinality)

static	SCIP_DECL_CONSGETNVARS (consGetNVarsCardinality)

static	SCIP_DECL_CONSGETPERMSYMGRAPH (consGetPermsymGraphCardinality)

static	SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH (consGetSignedPermsymGraphCardinality)

static	SCIP_DECL_EVENTEXEC (eventExecCardinality)

SCIP_RETCODE	SCIPincludeConshdlrCardinality (SCIP *scip)

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

SCIP_RETCODE	SCIPchgCardvalCardinality (SCIP scip, SCIP_CONS cons, int cardval)

SCIP_RETCODE	SCIPaddVarCardinality (SCIP scip, SCIP_CONS cons, SCIP_VAR var, SCIP_VAR indvar, SCIP_Real weight)

SCIP_RETCODE	SCIPappendVarCardinality (SCIP scip, SCIP_CONS cons, SCIP_VAR var, SCIP_VAR indvar)

int	SCIPgetNVarsCardinality (SCIP scip, SCIP_CONS cons)

SCIP_VAR **	SCIPgetVarsCardinality (SCIP scip, SCIP_CONS cons)

int	SCIPgetCardvalCardinality (SCIP scip, SCIP_CONS cons)

SCIP_Real *	SCIPgetWeightsCardinality (SCIP scip, SCIP_CONS cons)

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "cardinality"

Definition at line 80 of file cons_cardinality.c.

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "cardinality constraint handler"

Definition at line 81 of file cons_cardinality.c.

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY 10

priority of the constraint handler for separation

Definition at line 82 of file cons_cardinality.c.

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY 100

priority of the constraint handler for constraint enforcing

Definition at line 83 of file cons_cardinality.c.

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY -10

priority of the constraint handler for checking feasibility

Definition at line 84 of file cons_cardinality.c.

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ 10

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

Definition at line 85 of file cons_cardinality.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 86 of file cons_cardinality.c.

◆ 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 88 of file cons_cardinality.c.

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS -1

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

Definition at line 90 of file cons_cardinality.c.

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 91 of file cons_cardinality.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 92 of file cons_cardinality.c.

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 93 of file cons_cardinality.c.

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 95 of file cons_cardinality.c.

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST

Definition at line 96 of file cons_cardinality.c.

◆ DEFAULT_BRANCHBALANCED

#define DEFAULT_BRANCHBALANCED FALSE

whether to use balanced instead of unbalanced branching

Definition at line 99 of file cons_cardinality.c.

◆ DEFAULT_BALANCEDDEPTH

#define DEFAULT_BALANCEDDEPTH 20

maximum depth for using balanced branching (-1: no limit)

Definition at line 100 of file cons_cardinality.c.

◆ DEFAULT_BALANCEDCUTOFF

#define DEFAULT_BALANCEDCUTOFF 2.0

determines that balanced branching is only used if the branching cut off value w.r.t. the current LP solution is greater than a given value

Definition at line 102 of file cons_cardinality.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "cardinality"

Definition at line 105 of file cons_cardinality.c.

◆ EVENTHDLR_DESC

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

Definition at line 106 of file cons_cardinality.c.

◆ EVENTHDLR_EVENT_TYPE

#define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

Definition at line 108 of file cons_cardinality.c.

Function Documentation

◆ catchVarEventCardinality()

static SCIP_RETCODE catchVarEventCardinality	(	SCIP *	scip,
		SCIP_EVENTHDLR *	eventhdlr,
		SCIP_CONSDATA *	consdata,
		SCIP_VAR *	var,
		SCIP_VAR *	indvar,
		int	pos,
		SCIP_EVENTDATA **	eventdata
	)

static

catches bound change events for a variable and its indicator variable

Parameters

scip	SCIP data structure
eventhdlr	event handler for bound change events
consdata	constraint data
var	implied variable
indvar	indicator variable
pos	position in constraint
eventdata	pointer to store event data for bound change events

Definition at line 156 of file cons_cardinality.c.

References EVENTHDLR_EVENT_TYPE, FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPallocBlockMemory, and SCIPcatchVarEvent().

Referenced by handleNewVariableCardinality(), presolRoundCardinality(), and SCIP_DECL_CONSTRANS().

◆ dropVarEventCardinality()

static SCIP_RETCODE dropVarEventCardinality	(	SCIP *	scip,
		SCIP_EVENTHDLR *	eventhdlr,
		SCIP_CONSDATA *	consdata,
		SCIP_VAR *	var,
		SCIP_VAR *	indvar,
		SCIP_EVENTDATA **	eventdata
	)

static

drops bound change events for a variable and its indicator variable

Parameters

scip	SCIP data structure
eventhdlr	event handler for bound change events
consdata	constraint data
var	implied variable
indvar	indicator variable
eventdata	pointer of event data for bound change events

Definition at line 191 of file cons_cardinality.c.

References EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), and SCIPfreeBlockMemory.

Referenced by deleteVarCardinality(), presolRoundCardinality(), and SCIP_DECL_CONSDELETE().

◆ 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

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

Definition at line 222 of file cons_cardinality.c.

References FALSE, NULL, 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 branchBalancedCardinality(), branchUnbalancedCardinality(), and enforceCardinality().

◆ fixVariableZero()

static SCIP_RETCODE fixVariableZero	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Bool *	infeasible,
		SCIP_Bool *	tightened
	)

static

try to fix variable to 0

Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation

\[ x = \sum_{i=1}^n \alpha_i x_i + c, \]

we can express the fixing \(x = 0\) by fixing all \(x_i\) to 0 if \(c = 0\) and the lower bounds of \(x_i\) are nonnegative if \(\alpha_i > 0\) or the upper bounds are nonpositive if \(\alpha_i < 0\).

Parameters

scip	SCIP pointer
var	variable to be fixed to 0
infeasible	if fixing is infeasible
tightened	if fixing was performed

Definition at line 281 of file cons_cardinality.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPfixVar(), SCIPflattenVarAggregationGraph(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propCardinality().

◆ lockVariableCardinality()

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

static

add lock on variable

Parameters

scip	SCIP data structure
cons	constraint
var	variable
indvar	indicator variable

Definition at line 350 of file cons_cardinality.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by handleNewVariableCardinality(), and presolRoundCardinality().

◆ unlockVariableCardinality()

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

static

Parameters

scip	SCIP data structure
cons	constraint
var	variable
indvar	indicator variable

Definition at line 371 of file cons_cardinality.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by deleteVarCardinality(), and presolRoundCardinality().

◆ consdataEnsurevarsSizeCardinality()

static SCIP_RETCODE consdataEnsurevarsSizeCardinality	(	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 392 of file cons_cardinality.c.

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

Referenced by addVarCardinality(), and appendVarCardinality().

◆ handleNewVariableCardinality()

static SCIP_RETCODE handleNewVariableCardinality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSDATA *	consdata,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_VAR *	var,
		SCIP_VAR *	indvar,
		int	pos,
		SCIP_Bool	transformed,
		SCIP_EVENTDATA **	eventdata
	)

static

handle new variable that was added to the constraint

We perform the following steps:

catch bound change events of variable.
update rounding locks of variable.
don't allow multiaggregation of variable, since this cannot be handled by branching in the current implementation
update lower and upper bound row, i.e., the linear representations of the cardinality constraints

Parameters

scip	SCIP data structure
cons	constraint
consdata	constraint data
conshdlrdata	constraint handler data
var	variable
indvar	indicator variable to indicate whether variable may be treated as nonzero in cardinality constraint
pos	position in constraint
transformed	whether original variable was transformed
eventdata	pointer to store event data for bound change events

Definition at line 434 of file cons_cardinality.c.

References catchVarEventCardinality(), lockVariableCardinality(), NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarToRow(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), and SCIPvarGetUbGlobal().

Referenced by addVarCardinality(), and appendVarCardinality().

◆ addVarCardinality()

static SCIP_RETCODE addVarCardinality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_VAR *	var,
		SCIP_VAR *	indvar,
		SCIP_Real	weight
	)

static

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

Parameters

scip	SCIP data structure
cons	constraint
conshdlrdata	constraint handler data
var	variable to add to the constraint
indvar	indicator variable to indicate whether variable may be treated as nonzero in cardinality constraint (or NULL)
weight	weight to determine position

Definition at line 491 of file cons_cardinality.c.

References consdataEnsurevarsSizeCardinality(), FALSE, handleNewVariableCardinality(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddVar(), SCIPblkmem(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPcreateVar(), SCIPerrorMessage, SCIPgetNTotalVars(), SCIPgetTransformedVar(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarIsBinary(), SCIPvarIsTransformed(), and TRUE.

Referenced by SCIPaddVarCardinality().

◆ appendVarCardinality()

static SCIP_RETCODE appendVarCardinality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_VAR *	var,
		SCIP_VAR *	indvar
	)

static

appends a variable to a cardinality constraint

Parameters

scip	SCIP data structure
cons	constraint
conshdlrdata	constraint handler data
var	variable to add to the constraint
indvar	indicator variable to indicate whether variable may be treated as nonzero in cardinality constraint

Definition at line 619 of file cons_cardinality.c.

References consdataEnsurevarsSizeCardinality(), FALSE, handleNewVariableCardinality(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddVar(), SCIPblkmem(), SCIPconsGetData(), SCIPconsIsTransformed(), SCIPcreateVar(), SCIPgetNTotalVars(), SCIPgetTransformedVar(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarIsBinary(), and SCIPvarIsTransformed().

Referenced by SCIPappendVarCardinality().

◆ deleteVarCardinality()

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

static

deletes a variable from a cardinality constraint

Parameters

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

Definition at line 720 of file cons_cardinality.c.

References dropVarEventCardinality(), NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasEQ(), SCIPvarGetLbLocal(), and unlockVariableCardinality().

Referenced by presolRoundCardinality().

◆ polishPrimalSolution()

static SCIP_RETCODE polishPrimalSolution	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_SOL *	sol,
		SCIP_SOL *	primsol
	)

static

for each indicator variable sets solution to 1.0 if the solution value of the implied variable is nonzero

Parameters

scip	SCIP pointer
conss	constraints
nconss	number of constraints
sol	solution to be enforced (or NULL)
primsol	primal solution

Definition at line 761 of file cons_cardinality.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPgetSolVal(), SCIPisFeasZero(), and SCIPsetSolVal().

Referenced by enforceCardinality().

◆ consdataUnmarkEventdataVars()

static void consdataUnmarkEventdataVars ( SCIP_CONSDATA * consdata )

static

unmark variables that are marked for propagation

Parameters

consdata constraint data

Definition at line 808 of file cons_cardinality.c.

References FALSE, and NULL.

Referenced by presolRoundCardinality().

◆ presolRoundCardinality()

static SCIP_RETCODE presolRoundCardinality	(	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 cardinality 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 842 of file cons_cardinality.c.

References catchVarEventCardinality(), consdataUnmarkEventdataVars(), deleteVarCardinality(), dropVarEventCardinality(), FALSE, lockVariableCardinality(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsKnapsack(), SCIPdebugMsg, SCIPdelCons(), SCIPfixVar(), SCIPfreeBufferArray, SCIPgetProbvarSum(), SCIPisFeasEQ(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, and unlockVariableCardinality().

Referenced by SCIP_DECL_CONSPRESOL().

◆ propCardinality()

static SCIP_RETCODE propCardinality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSDATA *	consdata,
		SCIP_Bool *	cutoff,
		int *	nchgdomain
	)

static

propagates a cardinality constraint and its variables

The number 'ntreatnonzeros' that is assigned to the constraint data returns the number of variables that are either known to be nonzero or can be treated as nonzero. We say that a variable is known to be nonzero, if zero is outside the domain of this variable. A variable can be treated as nonzero, if its corresponding indicator variable 'indvar' is fixed to 1.0, e.g., by branching.

We perform the following propagation steps:

if the number 'ntreatnonzeros' is greater than the cardinality value of the constraint, then the current subproblem is marked as infeasible.
if the cardinality constraint is saturated, i.e., the number 'ntreatnonzeros' is equal to the cardinality value of the constraint, then fix all the other variables of the constraint to zero.
remove the cardinality constraint locally if all variables are either fixed to zero or can be treated as nonzero.
if a (binary) indicator variable is fixed to zero, then fix the corresponding implied variable to zero.
if zero is outside of the domain of an implied variable, then fix the corresponding indicator variable to one.

Parameters

scip	SCIP pointer
cons	constraint
consdata	constraint data
cutoff	whether a cutoff happened
nchgdomain	number of domain changes

Definition at line 1129 of file cons_cardinality.c.

References FALSE, fixVariableZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPchgVarLb(), SCIPconsGetName(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPisFeasEQ(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and TRUE.

Referenced by enforceCardinality(), and SCIP_DECL_CONSPROP().

◆ branchUnbalancedCardinality()

static SCIP_RETCODE branchUnbalancedCardinality	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_CONS *	branchcons,
		SCIP_VAR **	vars,
		SCIP_VAR **	indvars,
		int	nvars,
		int	cardval,
		int	branchnnonzero,
		int	branchpos
	)

static

apply unbalanced branching (see the function enforceCardinality() for further information)

Parameters

scip	SCIP pointer
sol	solution to be enforced (or NULL)
branchcons	cardinality constraint
vars	variables of constraint
indvars	indicator variables
nvars	number of variables of constraint
cardval	cardinality value of constraint
branchnnonzero	number of variables that are fixed to be nonzero
branchpos	position in array 'vars'

Definition at line 1346 of file cons_cardinality.c.

References fixVariableZeroNode(), SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcChildEstimate(), SCIPcalcChildEstimateIncrease(), SCIPcalcNodeselPriority(), SCIPchgVarLbNode(), SCIPconsGetName(), SCIPcreateChild(), SCIPdebugMsg, SCIPgetLocalTransEstimate(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by branchBalancedCardinality(), and enforceCardinality().

◆ branchBalancedCardinality()

static SCIP_RETCODE branchBalancedCardinality	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_SOL *	sol,
		SCIP_CONS *	branchcons,
		SCIP_VAR **	vars,
		SCIP_VAR **	indvars,
		int	nvars,
		int	cardval,
		int	branchnnonzero,
		int	branchpos,
		SCIP_Real	balancedcutoff
	)

static

apply balanced branching (see the function enforceCardinality() for further information)

Parameters

scip	SCIP pointer
conshdlr	constraint handler
sol	solution to be enforced (or NULL)
branchcons	cardinality constraint
vars	variables of constraint
indvars	indicator variables
nvars	number of variables of constraint
cardval	cardinality value of constraint
branchnnonzero	number of variables that are fixed to be nonzero
branchpos	position in array 'vars'
balancedcutoff	cut off value for deciding whether to apply balanced branching

Definition at line 1450 of file cons_cardinality.c.

References branchUnbalancedCardinality(), FALSE, fixVariableZeroNode(), MAX, MIN, NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPcalcChildEstimateIncrease(), SCIPcalcNodeselPriority(), SCIPconsGetName(), SCIPconshdlrGetSepaFreq(), SCIPcreateChild(), SCIPcreateConsCardinality(), SCIPdebugMsg, SCIPerrorMessage, SCIPfloor(), SCIPfreeBufferArray, SCIPgetLocalTransEstimate(), SCIPgetNNodes(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and w.

Referenced by enforceCardinality().

◆ enforceCardinality()

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

static

enforcement method

We check whether the current solution is feasible. If not, the cardinality constraints can be enforced by different branching rules:

Unbalanced branching: Branch on the neighborhood of a single variable \(i\), i.e., in one branch \(x_i\) is fixed to zero and in the other we modify cardinality constraints \(|\mbox{supp}(x)| \leq k\) with \(i\in D\) to \(|\mbox{supp}(x_{D\setminus i}) \leq k-1\)
Balanced branching: First, choose a cardinality constraint \(|\mbox{supp}(x_D) \leq k\) that is violated by the current LP solution. Then, we compute \(W = \sum_{j=1}^n |x_i|\) and \(w = \sum_{j=1}^n j\, |x_i|\). Next, search for the index \(r\) that satisfies
\[ r \leq \frac{w}{W} < r+1. \]
Choose a number \(s\) with \(0\leq s < \min\{k, r\}\). The branches are then
\[ |\mbox{supp}(x_{d_1}, \ldots, x_{d_r})| \leq s \qquad \mbox{and}\qquad |\mbox{supp}(x_{d_{r+1}}, \ldots, x_{d_{n}})| \leq k-s-1, \]
where \(d_1, \ldots, d_n\) are the elements of the set \(D\).

The branching constraint is chosen by the largest sum of variable values.

Parameters

scip	SCIP pointer
conshdlr	constraint handler
sol	solution to be enforced (or NULL)
nconss	number of constraints
conss	indicator constraints
result	result

Definition at line 1737 of file cons_cardinality.c.

References branchBalancedCardinality(), branchUnbalancedCardinality(), FALSE, fixVariableZeroNode(), NULL, polishPrimalSolution(), propCardinality(), REALABS, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_REDUCEDDOM, SCIP_VARSTATUS_MULTAGGR, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateSolCopy(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPtrySol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

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

◆ generateRowCardinality()

static SCIP_RETCODE generateRowCardinality	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS *	cons,
		SCIP_Bool	local,
		SCIP_ROW **	rowlb,
		SCIP_ROW **	rowub
	)

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 k\qquad\mbox{and}\qquad \frac{x_1}{\ell_1} + \ldots + \frac{x_n}{\ell_1} \leq k, \]

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\) and k is the right hand side of the cardinality constraint. If at least k upper bounds < 0 or a lower bounds > 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?
rowlb	output: row for lower bounds (or NULL if not needed)
rowub	output: row for upper bounds (or NULL if not needed)

Definition at line 2006 of file cons_cardinality.c.

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

Referenced by initsepaBoundInequalityFromCardinality().

◆ initsepaBoundInequalityFromCardinality()

static SCIP_RETCODE initsepaBoundInequalityFromCardinality	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_SOL *	sol,
		SCIP_Bool	solvedinitlp,
		int *	ngen,
		SCIP_Bool *	cutoff
	)

static

initialize or separate bound inequalities from cardinality constraints (see the function generateRowCardinality() for an explanation of bound inequalities)

Parameters

scip	SCIP pointer
conshdlr	constraint handler
conss	cardinality constraints
nconss	number of cardinality constraints
sol	LP solution to be separated (or NULL)
solvedinitlp	TRUE if initial LP relaxation at a node is solved
ngen	pointer to store number of cuts generated (or NULL)
cutoff	pointer to store whether a cutoff occurred

Definition at line 2132 of file cons_cardinality.c.

References FALSE, generateRowCardinality(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsLocal(), SCIPdebug, SCIPdebugMsg, SCIPisCutEfficacious(), SCIPisInfinity(), SCIPisLE(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIProwGetLhs(), SCIProwGetRhs(), SCIProwIsInLP(), and TRUE.

Referenced by SCIP_DECL_CONSINITLP(), and separateCardinality().

◆ separateCardinality()

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

static

separates cardinality constraints for arbitrary solutions

Parameters

scip	SCIP pointer
conshdlr	constraint handler
sol	solution to be separated (or NULL)
nconss	number of constraints
conss	cardinality constraints
result	result

Definition at line 2245 of file cons_cardinality.c.

References initsepaBoundInequalityFromCardinality(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPisStopped(), and TRUE.

Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyCardinality )

static

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

Definition at line 2293 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeCardinality )

static

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

Definition at line 2309 of file cons_cardinality.c.

References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBlockMemory, and SCIPhashmapFree().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolCardinality )

static

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

Definition at line 2333 of file cons_cardinality.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPhashmapFree(), and SCIPreleaseRow().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteCardinality )

static

frees specific constraint data

Definition at line 2379 of file cons_cardinality.c.

References CONSHDLR_NAME, dropVarEventCardinality(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseRow().

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransCardinality )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 2437 of file cons_cardinality.c.

References catchVarEventCardinality(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetTransformedVar(), SCIPisFeasEQ(), SCIPisGT(), SCIPsnprintf(), and SCIPvarGetLbLocal().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolCardinality )

static

presolving method of constraint handler

Definition at line 2535 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpCardinality )

static

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

Definition at line 2611 of file cons_cardinality.c.

References FALSE, initsepaBoundInequalityFromCardinality(), NULL, SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpCardinality )

static

separation method of constraint handler for LP solutions

Definition at line 2627 of file cons_cardinality.c.

References NULL, SCIP_CALL, SCIP_OKAY, and separateCardinality().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolCardinality )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 2641 of file cons_cardinality.c.

References NULL, SCIP_CALL, SCIP_OKAY, and separateCardinality().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpCardinality )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 2655 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxCardinality )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 2670 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsCardinality )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 2685 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckCardinality )

static

feasibility check method of constraint handler for integral solutions

We simply check whether more variables than allowed are nonzero in the given solution.

Definition at line 2703 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropCardinality )

static

domain propagation method of constraint handler

Definition at line 2774 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockCardinality )

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 rhs of the constraint can be updated and the variable can be removed from the constraint. Thus, 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 2830 of file cons_cardinality.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintCardinality )

static

constraint display method of constraint handler

Definition at line 2882 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyCardinality )

static

constraint copying method of constraint handler

Definition at line 2912 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseCardinality )

static

constraint parsing method of constraint handler

Definition at line 2991 of file cons_cardinality.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarCardinality(), SCIPchgCardvalCardinality(), SCIPconshdlrGetName(), SCIPcreateConsCardinality(), SCIPerrorMessage, SCIPparseVarName(), SCIPreleaseCons(), SCIPskipSpace(), and TRUE.

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsCardinality )

static

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

Definition at line 3107 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsCardinality )

static

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

Definition at line 3129 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSGETPERMSYMGRAPH()

static SCIP_DECL_CONSGETPERMSYMGRAPH ( consGetPermsymGraphCardinality )

static

constraint handler method which returns the permutation symmetry detection graph of a constraint

Definition at line 3144 of file cons_cardinality.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphVarAggregation(), SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSymActiveVariables(), SCIPgetSymgraphVarnodeidx(), SCIPinfinity(), SCIPisEQ(), SCIPisTransformed(), SCIPisZero(), SYM_CONSOPTYPE_CARD_TUPLE, SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_PERM, and TRUE.

◆ SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH()

static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH ( consGetSignedPermsymGraphCardinality )

static

constraint handler method which returns the signed permutation symmetry detection graph of a constraint

Definition at line 3249 of file cons_cardinality.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPaddSymgraphVarAggregation(), SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSymActiveVariables(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphVarnodeidx(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisTransformed(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SYM_CONSOPTYPE_CARD_TUPLE, SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_PERM, and TRUE.

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecCardinality )

static

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PROP_TIMING

◆ CONSHDLR_PRESOLTIMING

◆ DEFAULT_BRANCHBALANCED

◆ DEFAULT_BALANCEDDEPTH

◆ DEFAULT_BALANCEDCUTOFF

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ EVENTHDLR_EVENT_TYPE

Function Documentation

◆ catchVarEventCardinality()

◆ dropVarEventCardinality()

◆ fixVariableZeroNode()

◆ fixVariableZero()

◆ lockVariableCardinality()

◆ unlockVariableCardinality()

◆ consdataEnsurevarsSizeCardinality()

◆ handleNewVariableCardinality()

◆ addVarCardinality()

◆ appendVarCardinality()

◆ deleteVarCardinality()

◆ polishPrimalSolution()

◆ consdataUnmarkEventdataVars()

◆ presolRoundCardinality()

◆ propCardinality()

◆ branchUnbalancedCardinality()

◆ branchBalancedCardinality()

◆ enforceCardinality()

◆ generateRowCardinality()

◆ initsepaBoundInequalityFromCardinality()

◆ separateCardinality()

◆ SCIP_DECL_CONSHDLRCOPY()

◆ SCIP_DECL_CONSFREE()

◆ SCIP_DECL_CONSEXITSOL()

◆ SCIP_DECL_CONSDELETE()

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSPRESOL()

◆ SCIP_DECL_CONSINITLP()

◆ SCIP_DECL_CONSSEPALP()

◆ SCIP_DECL_CONSSEPASOL()

◆ SCIP_DECL_CONSENFOLP()

◆ SCIP_DECL_CONSENFORELAX()

◆ SCIP_DECL_CONSENFOPS()

◆ SCIP_DECL_CONSCHECK()

◆ SCIP_DECL_CONSPROP()

◆ SCIP_DECL_CONSLOCK()

◆ SCIP_DECL_CONSPRINT()

◆ SCIP_DECL_CONSCOPY()

◆ SCIP_DECL_CONSPARSE()

◆ SCIP_DECL_CONSGETVARS()

◆ SCIP_DECL_CONSGETNVARS()

◆ SCIP_DECL_CONSGETPERMSYMGRAPH()

◆ SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH()

◆ SCIP_DECL_EVENTEXEC()