constraint handler for cardinality constraints
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) |
#define CONSHDLR_NAME "cardinality" |
Definition at line 80 of file cons_cardinality.c.
#define CONSHDLR_DESC "cardinality constraint handler" |
Definition at line 81 of file cons_cardinality.c.
#define CONSHDLR_SEPAPRIORITY 10 |
priority of the constraint handler for separation
Definition at line 82 of file cons_cardinality.c.
#define CONSHDLR_ENFOPRIORITY 100 |
priority of the constraint handler for constraint enforcing
Definition at line 83 of file cons_cardinality.c.
#define CONSHDLR_CHECKPRIORITY -10 |
priority of the constraint handler for checking feasibility
Definition at line 84 of file cons_cardinality.c.
#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.
#define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 86 of file cons_cardinality.c.
#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.
#define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 89 of file cons_cardinality.c.
#define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 91 of file cons_cardinality.c.
#define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 92 of file cons_cardinality.c.
#define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 93 of file cons_cardinality.c.
#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 95 of file cons_cardinality.c.
#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST |
Definition at line 96 of file cons_cardinality.c.
#define DEFAULT_BRANCHBALANCED FALSE |
whether to use balanced instead of unbalanced branching
Definition at line 99 of file cons_cardinality.c.
Referenced by SCIPincludeConshdlrCardinality().
#define DEFAULT_BALANCEDDEPTH 20 |
maximum depth for using balanced branching (-1: no limit)
Definition at line 100 of file cons_cardinality.c.
Referenced by SCIPincludeConshdlrCardinality().
#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 101 of file cons_cardinality.c.
Referenced by SCIPincludeConshdlrCardinality().
#define EVENTHDLR_NAME "cardinality" |
Definition at line 105 of file cons_cardinality.c.
#define EVENTHDLR_DESC "bound change event handler for cardinality constraints" |
Definition at line 106 of file cons_cardinality.c.
#define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) |
Definition at line 108 of file cons_cardinality.c.
Referenced by catchVarEventCardinality(), deleteVarSOS1(), deleteVarSOS2(), dropVarEventCardinality(), handleNewVariableSOS1(), handleNewVariableSOS2(), presolRoundConsSOS1(), presolRoundSOS2(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSTRANS(), and SCIP_DECL_CONSTRANS().
|
static |
catches bound change events for a variable and its indicator variable
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 assert(), EVENTHDLR_EVENT_TYPE, FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPallocBlockMemory, SCIPcatchVarEvent(), and var.
Referenced by handleNewVariableCardinality(), presolRoundCardinality(), and SCIP_DECL_CONSTRANS().
|
static |
drops bound change events for a variable and its indicator variable
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 assert(), EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), SCIPfreeBlockMemory, and var.
Referenced by deleteVarCardinality(), presolRoundCardinality(), and SCIP_DECL_CONSDELETE().
|
static |
fix variable in given node to 0 or add constraint if variable is multi-aggregated
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_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by branchBalancedCardinality(), branchUnbalancedCardinality(), and enforceCardinality().
|
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\).
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 assert(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPfixVar(), SCIPflattenVarAggregationGraph(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by propCardinality().
|
static |
add lock on variable
scip | SCIP data structure |
cons | constraint |
var | variable |
indvar | indicator variable |
Definition at line 350 of file cons_cardinality.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, and var.
Referenced by handleNewVariableCardinality(), and presolRoundCardinality().
|
static |
scip | SCIP data structure |
cons | constraint |
var | variable |
indvar | indicator variable |
Definition at line 371 of file cons_cardinality.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, and var.
Referenced by deleteVarCardinality(), and presolRoundCardinality().
|
static |
ensures that the vars and weights array can store at least num entries
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 assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addVarCardinality(), and appendVarCardinality().
|
static |
handle new variable that was added to the constraint
We perform the following steps:
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 assert(), catchVarEventCardinality(), lockVariableCardinality(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddVarToRow(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and var.
Referenced by addVarCardinality(), appendVarCardinality(), and SCIPcreateConsCardinality().
|
static |
adds a variable to a cardinality constraint, at position given by weight - ascending order
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 assert(), consdataEnsurevarsSizeCardinality(), FALSE, handleNewVariableCardinality(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddVar(), SCIPblkmem(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPcreateVar(), SCIPerrorMessage, SCIPgetNTotalVars(), SCIPgetTransformedVar(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarIsBinary(), SCIPvarIsTransformed(), TRUE, and var.
Referenced by SCIPaddVarCardinality().
|
static |
appends a variable to a cardinality constraint
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 assert(), 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(), SCIPvarIsTransformed(), and var.
Referenced by SCIPappendVarCardinality().
|
static |
deletes a variable from a cardinality constraint
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 assert(), dropVarEventCardinality(), NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPisFeasEQ(), SCIPvarGetLbLocal(), and unlockVariableCardinality().
Referenced by presolRoundCardinality().
|
static |
for each indicator variable sets solution to 1.0 if the solution value of the implied variable is nonzero
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 assert(), c, NULL, nvars, primsol, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPsetSolVal(), sol, and vars.
Referenced by enforceCardinality().
|
static |
unmark variables that are marked for propagation
consdata | constraint data |
Definition at line 808 of file cons_cardinality.c.
References assert(), FALSE, NULL, and nvars.
Referenced by presolRoundCardinality().
|
static |
perform one presolving round
We perform the following presolving steps:
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 assert(), catchVarEventCardinality(), consdataUnmarkEventdataVars(), cutoff, deleteVarCardinality(), dropVarEventCardinality(), FALSE, lockVariableCardinality(), NULL, nvars, 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, unlockVariableCardinality(), var, and vars.
Referenced by SCIP_DECL_CONSPRESOL().
|
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:
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 assert(), cutoff, FALSE, fixVariableZero(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPchgVarLb(), SCIPconsGetName(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPisFeasEQ(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, var, and vars.
Referenced by enforceCardinality(), and SCIP_DECL_CONSPROP().
|
static |
apply unbalanced branching (see the function enforceCardinality() for further information)
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 assert(), fixVariableZeroNode(), nvars, 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(), SCIPvarGetUbLocal(), sol, and vars.
Referenced by branchBalancedCardinality(), and enforceCardinality().
|
static |
apply balanced branching (see the function enforceCardinality() for further information)
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 assert(), branchUnbalancedCardinality(), FALSE, fixVariableZeroNode(), MAX, MIN, NULL, nvars, 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(), sol, TRUE, var, vars, and w.
Referenced by enforceCardinality().
|
static |
enforcement method
We check whether the current solution is feasible. If not, the cardinality constraints can be enforced by different branching rules:
\[ 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.
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 assert(), branchBalancedCardinality(), branchUnbalancedCardinality(), c, cutoff, FALSE, fixVariableZeroNode(), NULL, nvars, polishPrimalSolution(), primsol, propCardinality(), REALABS, result, 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(), sol, TRUE, var, and vars.
Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().
|
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.
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 assert(), FALSE, NULL, nvars, SCIP_Bool, 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(), TRUE, and vars.
Referenced by initsepaBoundInequalityFromCardinality().
|
static |
initialize or separate bound inequalities from cardinality constraints (see the function generateRowCardinality() for an explanation of bound inequalities)
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 assert(), c, cutoff, 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(), sol, and TRUE.
Referenced by SCIP_DECL_CONSINITLP(), and separateCardinality().
|
static |
separates cardinality constraints for arbitrary solutions
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 assert(), cutoff, initsepaBoundInequalityFromCardinality(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPisStopped(), sol, and TRUE.
Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 2293 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrCardinality(), TRUE, and valid.
|
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 assert(), CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBlockMemory, and SCIPhashmapFree().
|
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 assert(), c, CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPhashmapFree(), and SCIPreleaseRow().
|
static |
frees specific constraint data
Definition at line 2379 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, dropVarEventCardinality(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseRow().
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 2437 of file cons_cardinality.c.
References assert(), 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().
|
static |
presolving method of constraint handler
Definition at line 2535 of file cons_cardinality.c.
References assert(), c, CONSHDLR_NAME, cutoff, NULL, presolRoundCardinality(), result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsModifiable(), SCIPdebug, and SCIPdebugMsg.
|
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 assert(), cutoff, FALSE, initsepaBoundInequalityFromCardinality(), NULL, SCIP_Bool, SCIP_CALL, and SCIP_OKAY.
|
static |
separation method of constraint handler for LP solutions
Definition at line 2627 of file cons_cardinality.c.
References assert(), NULL, result, SCIP_CALL, SCIP_OKAY, and separateCardinality().
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 2641 of file cons_cardinality.c.
References assert(), NULL, result, SCIP_CALL, SCIP_OKAY, separateCardinality(), and sol.
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 2655 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, enforceCardinality(), NULL, result, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 2670 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, enforceCardinality(), NULL, result, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), and sol.
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 2685 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, enforceCardinality(), NULL, result, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
|
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 assert(), c, CONSHDLR_NAME, NULL, result, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasZero(), SCIPprintCons(), SCIPresetConsAge(), SCIPupdateSolConsViolation(), SCIPvarGetName(), and sol.
|
static |
domain propagation method of constraint handler
Definition at line 2774 of file cons_cardinality.c.
References assert(), c, CONSHDLR_NAME, cutoff, NULL, propCardinality(), result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, and SCIPisTransformed().
|
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.
Definition at line 2830 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, NULL, nvars, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), var, and vars.
|
static |
constraint display method of constraint handler
Definition at line 2882 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), and SCIPwriteVarName().
|
static |
constraint copying method of constraint handler
Definition at line 2912 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, NULL, nvars, propagate, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsCardinality(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetVarCopy(), SCIPisTransformed(), TRUE, and valid.
|
static |
constraint parsing method of constraint handler
Definition at line 2991 of file cons_cardinality.c.
References assert(), CONSHDLR_NAME, FALSE, NULL, propagate, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarCardinality(), SCIPchgCardvalCardinality(), SCIPconshdlrGetName(), SCIPcreateConsCardinality(), SCIPerrorMessage, SCIPparseVarName(), SCIPreleaseCons(), SCIPskipSpace(), TRUE, and var.
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 3107 of file cons_cardinality.c.
References assert(), BMScopyMemoryArray, FALSE, NULL, nvars, SCIP_OKAY, SCIPconsGetData(), TRUE, and vars.
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 3129 of file cons_cardinality.c.
References assert(), NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.
|
static |
constraint handler method which returns the permutation symmetry detection graph of a constraint
Definition at line 3144 of file cons_cardinality.c.
References assert(), FALSE, i, NULL, nvars, 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, TRUE, and vars.
|
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 assert(), FALSE, i, NULL, nvars, 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, TRUE, and vars.
|
static |
Definition at line 3397 of file cons_cardinality.c.
References assert(), EVENTHDLR_NAME, FALSE, i, NULL, SCIP_CALL, SCIP_EVENTTYPE_GBDCHANGED, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_EVENTTYPE_LBRELAXED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPdebugMsg, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPunlockVarCons(), SCIPvarGetName(), SCIPvarIsBinary(), TRUE, and var.