Scippy

SCIP

Solving Constraint Integer Programs

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_RealSCIPgetWeightsCardinality (SCIP *scip, SCIP_CONS *cons)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "cardinality constraint handler"

Definition at line 81 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   10

priority of the constraint handler for separation

Definition at line 82 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   100

priority of the constraint handler for constraint enforcing

Definition at line 83 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -10

priority of the constraint handler for checking feasibility

Definition at line 84 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ 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.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 86 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

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

Referenced by SCIPincludeConshdlrCardinality().

◆ 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.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 93 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

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

Definition at line 94 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

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

Definition at line 95 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 97 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST

Definition at line 98 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ DEFAULT_BRANCHBALANCED

#define DEFAULT_BRANCHBALANCED   FALSE

whether to use balanced instead of unbalanced branching

Definition at line 101 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ DEFAULT_BALANCEDDEPTH

#define DEFAULT_BALANCEDDEPTH   20

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

Definition at line 102 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

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

Referenced by SCIPincludeConshdlrCardinality().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "cardinality"

Definition at line 108 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ EVENTHDLR_DESC

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

Definition at line 109 of file cons_cardinality.c.

Referenced by SCIPincludeConshdlrCardinality().

◆ EVENTHDLR_EVENT_TYPE

#define EVENTHDLR_EVENT_TYPE   (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

Definition at line 111 of file cons_cardinality.c.

Referenced by catchVarEventCardinality(), and dropVarEventCardinality().

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
scipSCIP data structure
eventhdlrevent handler for bound change events
consdataconstraint data
varimplied variable
indvarindicator variable
posposition in constraint
eventdatapointer to store event data for bound change events

Definition at line 159 of file cons_cardinality.c.

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

Referenced by handleNewVariableCardinality(), and presolRoundCardinality().

◆ 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
scipSCIP data structure
eventhdlrevent handler for bound change events
consdataconstraint data
varimplied variable
indvarindicator variable
eventdatapointer of event data for bound change events

Definition at line 194 of file cons_cardinality.c.

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

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

◆ 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
infeasiblepointer to store if fixing is infeasible

Definition at line 225 of file cons_cardinality.c.

References FALSE, fixVariableZero(), 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(), dropVarEventCardinality(), 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
scipSCIP pointer
varvariable to be fixed to 0
infeasibleif fixing is infeasible
tightenedif fixing was performed

Definition at line 284 of file cons_cardinality.c.

References FALSE, lockVariableCardinality(), 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 fixVariableZeroNode(), and propCardinality().

◆ lockVariableCardinality()

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

add lock on variable

Parameters
scipSCIP data structure
consconstraint
varvariable
indvarindicator variable

Definition at line 353 of file cons_cardinality.c.

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

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

◆ unlockVariableCardinality()

static SCIP_RETCODE unlockVariableCardinality ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_VAR indvar 
)
static
Parameters
scipSCIP data structure
consconstraint
varvariable
indvarindicator variable

Definition at line 374 of file cons_cardinality.c.

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

Referenced by deleteVarCardinality(), lockVariableCardinality(), 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
scipSCIP data structure
consdataconstraint data
numminimum number of entries to store
reserveweightswhether the weights array is handled

Definition at line 395 of file cons_cardinality.c.

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

Referenced by addVarCardinality(), appendVarCardinality(), and unlockVariableCardinality().

◆ 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
scipSCIP data structure
consconstraint
consdataconstraint data
conshdlrdataconstraint handler data
varvariable
indvarindicator variable to indicate whether variable may be treated as nonzero in cardinality constraint
posposition in constraint
transformedwhether original variable was transformed
eventdatapointer to store event data for bound change events

Definition at line 437 of file cons_cardinality.c.

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

Referenced by addVarCardinality(), appendVarCardinality(), consdataEnsurevarsSizeCardinality(), and SCIPcreateConsCardinality().

◆ 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
scipSCIP data structure
consconstraint
conshdlrdataconstraint handler data
varvariable to add to the constraint
indvarindicator variable to indicate whether variable may be treated as nonzero in cardinality constraint (or NULL)
weightweight to determine position

Definition at line 494 of file cons_cardinality.c.

References appendVarCardinality(), 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 handleNewVariableCardinality(), and 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
scipSCIP data structure
consconstraint
conshdlrdataconstraint handler data
varvariable to add to the constraint
indvarindicator variable to indicate whether variable may be treated as nonzero in cardinality constraint

Definition at line 622 of file cons_cardinality.c.

References consdataEnsurevarsSizeCardinality(), deleteVarCardinality(), 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 addVarCardinality(), and 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
scipSCIP data structure
consconstraint
consdataconstraint data
eventhdlrcorresponding event handler
posposition of variable in array

Definition at line 723 of file cons_cardinality.c.

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

Referenced by appendVarCardinality(), and 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
scipSCIP pointer
conssconstraints
nconssnumber of constraints
solsolution to be enforced (or NULL)
primsolprimal solution

Definition at line 764 of file cons_cardinality.c.

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

Referenced by deleteVarCardinality(), and enforceCardinality().

◆ consdataUnmarkEventdataVars()

static void consdataUnmarkEventdataVars ( SCIP_CONSDATA consdata)
static

unmark variables that are marked for propagation

Parameters
consdataconstraint data

Definition at line 811 of file cons_cardinality.c.

References FALSE, NULL, and presolRoundCardinality().

Referenced by polishPrimalSolution(), and 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
scipSCIP pointer
consconstraint
consdataconstraint data
eventhdlrevent handler
cutoffwhether a cutoff happened
successwhether we performed a successful reduction
ndelconssnumber of deleted constraints
nupgdconssnumber of upgraded constraints
nfixedvarsnumber of fixed variables
nremovedvarsnumber of variables removed

Definition at line 845 of file cons_cardinality.c.

References catchVarEventCardinality(), consdataUnmarkEventdataVars(), deleteVarCardinality(), dropVarEventCardinality(), FALSE, lockVariableCardinality(), NULL, propCardinality(), 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 consdataUnmarkEventdataVars().

◆ 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
scipSCIP pointer
consconstraint
consdataconstraint data
cutoffwhether a cutoff happened
nchgdomainnumber of domain changes

Definition at line 1132 of file cons_cardinality.c.

References branchUnbalancedCardinality(), 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 presolRoundCardinality().

◆ 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
scipSCIP pointer
solsolution to be enforced (or NULL)
branchconscardinality constraint
varsvariables of constraint
indvarsindicator variables
nvarsnumber of variables of constraint
cardvalcardinality value of constraint
branchnnonzeronumber of variables that are fixed to be nonzero
branchposposition in array 'vars'

Definition at line 1349 of file cons_cardinality.c.

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

◆ 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
scipSCIP pointer
conshdlrconstraint handler
solsolution to be enforced (or NULL)
branchconscardinality constraint
varsvariables of constraint
indvarsindicator variables
nvarsnumber of variables of constraint
cardvalcardinality value of constraint
branchnnonzeronumber of variables that are fixed to be nonzero
branchposposition in array 'vars'
balancedcutoffcut off value for deciding whether to apply balanced branching

Definition at line 1453 of file cons_cardinality.c.

References branchUnbalancedCardinality(), enforceCardinality(), 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 branchUnbalancedCardinality(), and 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
scipSCIP pointer
conshdlrconstraint handler
solsolution to be enforced (or NULL)
nconssnumber of constraints
conssindicator constraints
resultresult

Definition at line 1740 of file cons_cardinality.c.

References branchBalancedCardinality(), branchUnbalancedCardinality(), FALSE, fixVariableZeroNode(), generateRowCardinality(), 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 branchBalancedCardinality().

◆ 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
scipSCIP pointer
conshdlrconstraint handler
consconstraint
localproduce local cut?
rowlboutput: row for lower bounds (or NULL if not needed)
rowuboutput: row for upper bounds (or NULL if not needed)

Definition at line 2009 of file cons_cardinality.c.

References FALSE, initsepaBoundInequalityFromCardinality(), 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 enforceCardinality(), and 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
scipSCIP pointer
conshdlrconstraint handler
consscardinality constraints
nconssnumber of cardinality constraints
solLP solution to be separated (or NULL)
solvedinitlpTRUE if initial LP relaxation at a node is solved
ngenpointer to store number of cuts generated (or NULL)
cutoffpointer to store whether a cutoff occurred

Definition at line 2135 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(), separateCardinality(), and TRUE.

Referenced by generateRowCardinality(), 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
scipSCIP pointer
conshdlrconstraint handler
solsolution to be separated (or NULL)
nconssnumber of constraints
consscardinality constraints
resultresult

Definition at line 2248 of file cons_cardinality.c.

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

Referenced by initsepaBoundInequalityFromCardinality().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyCardinality  )
static

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

Definition at line 2296 of file cons_cardinality.c.

Referenced by separateCardinality().

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

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

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteCardinality  )
static

frees specific constraint data

Definition at line 2382 of file cons_cardinality.c.

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransCardinality  )
static

transforms constraint data into data belonging to the transformed problem

Definition at line 2440 of file cons_cardinality.c.

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolCardinality  )
static

presolving method of constraint handler

Definition at line 2538 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpCardinality  )
static

separation method of constraint handler for LP solutions

Definition at line 2630 of file cons_cardinality.c.

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolCardinality  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 2644 of file cons_cardinality.c.

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpCardinality  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 2658 of file cons_cardinality.c.

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxCardinality  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 2673 of file cons_cardinality.c.

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsCardinality  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 2688 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropCardinality  )
static

domain propagation method of constraint handler

Definition at line 2777 of file cons_cardinality.c.

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

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintCardinality  )
static

constraint display method of constraint handler

Definition at line 2885 of file cons_cardinality.c.

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyCardinality  )
static

constraint copying method of constraint handler

Definition at line 2915 of file cons_cardinality.c.

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseCardinality  )
static

constraint parsing method of constraint handler

Definition at line 2994 of file cons_cardinality.c.

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsCardinality  )
static

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

Definition at line 3110 of file cons_cardinality.c.

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

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

◆ 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.

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecCardinality  )
static

Definition at line 3394 of file cons_cardinality.c.