SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
Detailed Descriptionconstraint handler for SOS type 1 constraints A specially ordered set of type 1 (SOS1) is a sequence of variables such that at most one variable is nonzero. The special case of two variables arises, for instance, from equilibrium or complementary conditions like This implementation of this constraint handler is based on classical ideas, see e.g. The order of the variables is determined as follows:
The validity of the SOS1 constraints can be enforced by different branching rules:
Definition in file cons_sos1.c. #include <assert.h>#include "scip/cons_sos1.h"#include "scip/cons_linear.h"#include "scip/cons_setppc.h"#include "scip/pub_misc.h"#include "scip/misc.h"#include "scip/struct_misc.h"#include "tclique/tclique.h"#include <string.h>#include <ctype.h>Go to the source code of this file.
Macro Definition Documentation
Definition at line 86 of file cons_sos1.c. Referenced by freeConflictgraph(), generateBoundInequalityFromSOS1Cons(), SCIPaddVarSOS1(), SCIPcreateConsSOS1(), and SCIPmakeSOS1sFeasible().
Definition at line 87 of file cons_sos1.c.
priority of the constraint handler for separation Definition at line 88 of file cons_sos1.c.
priority of the constraint handler for constraint enforcing Definition at line 89 of file cons_sos1.c.
priority of the constraint handler for checking feasibility Definition at line 90 of file cons_sos1.c.
frequency for separating cuts; zero means to separate only in the root node Definition at line 91 of file cons_sos1.c.
frequency for propagating domains; zero means only preprocessing propagation Definition at line 92 of file cons_sos1.c.
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 93 of file cons_sos1.c.
maximal number of presolving rounds the constraint handler participates in (-1: no limit) Definition at line 96 of file cons_sos1.c.
should separation method be delayed, if other separators found cuts? Definition at line 97 of file cons_sos1.c.
should propagation method be delayed, if other propagators found reductions? Definition at line 98 of file cons_sos1.c.
should the constraint handler be skipped, if no constraints are available? Definition at line 99 of file cons_sos1.c.
Definition at line 100 of file cons_sos1.c.
Definition at line 101 of file cons_sos1.c.
do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit) Definition at line 104 of file cons_sos1.c.
maximal number of extensions that will be computed for each SOS1 constraint Definition at line 109 of file cons_sos1.c.
maximal number of bound tightening rounds per presolving round (-1: no limit) Definition at line 110 of file cons_sos1.c.
if TRUE then perform implication graph analysis (might add additional SOS1 constraints) Definition at line 111 of file cons_sos1.c.
number of recursive calls of implication graph analysis (-1: no limit) Definition at line 112 of file cons_sos1.c.
whether to use conflict graph propagation Definition at line 115 of file cons_sos1.c.
whether to use implication graph propagation Definition at line 116 of file cons_sos1.c.
whether to use SOS1 constraint propagation Definition at line 117 of file cons_sos1.c.
possible branching strategies (see parameter DEFAULT_BRANCHINGRULE) Definition at line 120 of file cons_sos1.c.
which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique) (note: in some cases an automatic switching to SOS1 branching is possible) Definition at line 121 of file cons_sos1.c.
if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap Definition at line 124 of file cons_sos1.c.
if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance Definition at line 125 of file cons_sos1.c.
if TRUE then add complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching) Definition at line 128 of file cons_sos1.c.
maximal number of complementarity constraints added per branching node (-1: no limit) Definition at line 131 of file cons_sos1.c.
only add complementarity constraints to branching nodes for predefined depth (-1: no limit) Definition at line 132 of file cons_sos1.c.
minimal feasibility value for complementarity constraints in order to be added to the branching node Definition at line 133 of file cons_sos1.c.
minimal feasibility value for bound inequalities in order to be added to the branching node Definition at line 134 of file cons_sos1.c.
should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities Definition at line 135 of file cons_sos1.c.
maximal number of strong branching rounds to perform for each node (-1: auto) (only available for neighborhood and bipartite branching) Definition at line 138 of file cons_sos1.c.
maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) Definition at line 141 of file cons_sos1.c.
if TRUE separate bound inequalities from SOS1 constraints Definition at line 144 of file cons_sos1.c.
if TRUE separate bound inequalities from the conflict graph Definition at line 145 of file cons_sos1.c.
if TRUE then automatically switch to separating from SOS1 constraints if the SOS1 constraints do not overlap Definition at line 146 of file cons_sos1.c.
frequency for separating bound cuts; zero means to separate only in the root node Definition at line 147 of file cons_sos1.c.
node depth of separating bound cuts (-1: no limit) Definition at line 148 of file cons_sos1.c.
maximal number of bound cuts separated per branching node Definition at line 149 of file cons_sos1.c.
maximal number of bound cuts separated per iteration in the root node Definition at line 150 of file cons_sos1.c.
if TRUE then bound cuts are strengthened in case bound variables are available Definition at line 151 of file cons_sos1.c.
frequency for separating implied bound cuts; zero means to separate only in the root node Definition at line 152 of file cons_sos1.c.
node depth of separating implied bound cuts (-1: no limit) Definition at line 153 of file cons_sos1.c.
maximal number of implied bound cuts separated per branching node Definition at line 154 of file cons_sos1.c.
maximal number of implied bound cuts separated per iteration in the root node Definition at line 155 of file cons_sos1.c.
Definition at line 158 of file cons_sos1.c.
Definition at line 159 of file cons_sos1.c.
Definition at line 162 of file cons_sos1.c. Referenced by getDiveBdChgsSOS1conflictgraph(), and getDiveBdChgsSOS1constraints(). Typedef Documentation
Definition at line 192 of file cons_sos1.c.
Definition at line 201 of file cons_sos1.c. Function Documentation
returns whether two vertices are adjacent in the conflict graph
Definition at line 299 of file cons_sos1.c. References FALSE, isViolatedSOS1(), NULL, SCIP_Bool, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPsortInt(), SCIPswapInts(), and TRUE. Referenced by addBranchingComplementaritiesSOS1(), computeVarsCoverSOS1(), enforceConflictgraph(), extensionOperatorSOS1(), getBoundConsFromVertices(), performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable
Definition at line 359 of file cons_sos1.c. References FALSE, nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE. Referenced by getDiveBdChgsSOS1conflictgraph(), and isConnectedSOS1().
returns solution value of imaginary binary big-M variable of a given node from the conflict graph
Definition at line 404 of file cons_sos1.c. References nodeGetSolvalVarboundLbSOS1(), NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal(). Referenced by computeVarsCoverSOS1(), getBoundConsFromVertices(), and isViolatedSOS1().
gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph
Definition at line 454 of file cons_sos1.c. References nodeGetSolvalVarboundUbSOS1(), NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetLbLocal(). Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalBinaryBigMSOS1(), and updateWeightsTCliquegraph().
gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph
Definition at line 481 of file cons_sos1.c. References NULL, SCIP_Bool, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), SCIPvarGetUbLocal(), and varIsSOS1(). Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalVarboundLbSOS1(), and updateWeightsTCliquegraph().
returns whether variable is part of the SOS1 conflict graph
Definition at line 508 of file cons_sos1.c. Referenced by checkLinearConssVarboundSOS1(), and nodeGetSolvalVarboundUbSOS1().
returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph
Definition at line 525 of file cons_sos1.c. Referenced by checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), detectVarboundSOS1(), enforceConflictgraph(), genConflictgraphLinearCons(), generateBoundInequalityFromSOS1Cons(), getSOS1Implications(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
fix variable in given node to 0 or add constraint if variable is multi-aggregated
Definition at line 546 of file cons_sos1.c. References FALSE, fixVariableZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMessage, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE. Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), enforceConssSOS1(), and getBranchingDecisionStrongbranchSOS1().
try to fix variable to 0 Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
we can express the fixing
Definition at line 601 of file cons_sos1.c. References FALSE, inferVariableZero(), 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 presolRoundConsSOS1().
fix variable in local node to 0, and return whether the operation was feasible
Definition at line 675 of file cons_sos1.c. References FALSE, lockVariableSOS1(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE. Referenced by fixVariableZero(), propConsSOS1(), and propVariableNonzero().
add lock on variable
Definition at line 718 of file cons_sos1.c. Referenced by handleNewVariableSOS1(), inferVariableZero(), and presolRoundConsSOS1().
remove lock on variable
Definition at line 737 of file cons_sos1.c. Referenced by deleteVarSOS1(), and presolRoundConsSOS1().
ensures that the vars and weights array can store at least num entries
Definition at line 756 of file cons_sos1.c. References handleNewVariableSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray. Referenced by addVarSOS1(), and appendVarSOS1().
handle new variable
Definition at line 784 of file cons_sos1.c. References addVarSOS1(), lockVariableSOS1(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPdebugMessage, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPsortInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1(). Referenced by addVarSOS1(), appendVarSOS1(), consdataEnsurevarsSizeSOS1(), and SCIPcreateConsSOS1().
adds a variable to an SOS1 constraint, at position given by weight - ascending order
Definition at line 919 of file cons_sos1.c. References appendVarSOS1(), consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE. Referenced by addBranchingComplementaritiesSOS1(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), and SCIPaddVarSOS1().
appends a variable to an SOS1 constraint
Definition at line 989 of file cons_sos1.c. References consdataEnsurevarsSizeSOS1(), deleteVarSOS1(), FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), and SCIPvarIsTransformed(). Referenced by addVarSOS1().
deletes a variable of an SOS1 constraint
Definition at line 1035 of file cons_sos1.c. References extensionOperatorSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1(). Referenced by appendVarSOS1(), and presolRoundConsSOS1().
extends a given clique of the conflict graph Implementation of the Bron-Kerbosch Algorithm from the paper: Algorithm 457: Finding all Cliques of an Undirected Graph, Bron & Kerbosch, Commun. ACM, 1973
Definition at line 1074 of file cons_sos1.c. References FALSE, genConflictgraphLinearCons(), isConnectedSOS1(), MAX, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), and TRUE. Referenced by deleteVarSOS1(), and presolRoundConssSOS1().
generates conflict graph that is induced by the variables of a linear constraint
Definition at line 1336 of file cons_sos1.c. References cliqueGetCommonSuccessorsSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1(). Referenced by extensionOperatorSOS1(), and tightenVarsBoundsSOS1().
determine the common successors of the vertices from the considered clique
Definition at line 1389 of file cons_sos1.c. References getSOS1Implications(), NULL, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1(). Referenced by genConflictgraphLinearCons(), and presolRoundConssSOS1().
get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero
Definition at line 1486 of file cons_sos1.c. References NULL, presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, and varGetNodeSOS1(). Referenced by cliqueGetCommonSuccessorsSOS1(), and tightenVarsBoundsSOS1().
perform one presolving round for a single SOS1 constraint We perform the following presolving steps.
Definition at line 1552 of file cons_sos1.c. References deleteVarSOS1(), FALSE, fixVariableZero(), lockVariableSOS1(), NULL, presolRoundConssSOS1(), SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcatchVarEvent(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMessage, SCIPdelCons(), SCIPdropVarEvent(), SCIPfindConshdlr(), SCIPfixVar(), SCIPgetProbvarSum(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, and unlockVariableSOS1(). Referenced by getSOS1Implications(), and presolRoundConssSOS1().
perform one presolving round for all SOS1 constraints We perform the following presolving steps.
If the adjacency matrix of the conflict graph is present, then we perform the following additional presolving steps
Definition at line 1776 of file cons_sos1.c. References cliqueGetCommonSuccessorsSOS1(), extensionOperatorSOS1(), FALSE, MAX, NULL, performImplicationGraphAnalysis(), presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPcomputeArraysIntersection(), SCIPconsGetData(), SCIPconsIsModifiable(), SCIPdelCons(), SCIPdigraphAddArcSafe(), SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownIntInt(), SCIPsortInt(), TRUE, and varGetNodeSOS1(). Referenced by presolRoundConsSOS1().
performs implication graph analysis Tentatively fixes a variable to nonzeero and extracts consequences from it:
Definition at line 2045 of file cons_sos1.c. References addVarSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), SCIPvarGetName(), TRUE, and varGetNodeSOS1(). Referenced by presolRoundConssSOS1(), and presolRoundVarsSOS1().
returns whether node is implied to be zero; this information is taken from the input array 'implnodes'
Definition at line 2202 of file cons_sos1.c. Referenced by performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
updates arc data of implication graph
Definition at line 2231 of file cons_sos1.c. References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPceil(), SCIPdebugMessage, SCIPdigraphAddArc(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfloor(), SCIPhashmapGetImage(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), SCIPvarIsIntegral(), TRUE, and updateImplicationGraphSOS1(). Referenced by updateImplicationGraphSOS1().
updates implication graph Assume the variable from the input is nonzero. If this implies that some other variable is also nonzero, then store this information in an implication graph
Definition at line 2357 of file cons_sos1.c. References computeVarsCoverSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, updateArcData(), and varGetNodeSOS1(). Referenced by tightenVarsBoundsSOS1(), and updateArcData().
search new disjoint clique that covers given node For a given vertex
Definition at line 2513 of file cons_sos1.c. References isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasLT(), tightenVarsBoundsSOS1(), and TRUE. Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
try to tighten upper and lower bounds for variables
Definition at line 2624 of file cons_sos1.c. References computeVarsCoverSOS1(), FALSE, genConflictgraphLinearCons(), getSOS1Implications(), isConnectedSOS1(), isImpliedZero(), MAX, MIN, NULL, presolRoundVarsSOS1(), REALABS, scalars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPallocBufferArray, SCIPceil(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdebugMessage, SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfloor(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetProbvarLinearSum(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPreallocBufferArray, SCIPsortDownRealInt(), SCIPsortRealInt(), SCIPswapPointers(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetName(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, updateImplicationGraphSOS1(), and varGetNodeSOS1(). Referenced by computeVarsCoverSOS1(), initImplGraphSOS1(), and presolRoundVarsSOS1().
perform one presolving round for variables We perform the following presolving steps:
Definition at line 3332 of file cons_sos1.c. References FALSE, performImplicationGraphAnalysis(), propConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMessage, SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfixVar(), SCIPfreeBufferArrayNull, SCIPfreeMemory, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenVarsBoundsSOS1(), and TRUE. Referenced by tightenVarsBoundsSOS1().
propagate variables of SOS1 constraint
Definition at line 3506 of file cons_sos1.c. References FALSE, inferVariableZero(), NULL, propVariableNonzero(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsIsModifiable(), SCIPdebugMessage, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE. Referenced by enforceConflictgraph(), enforceConssSOS1(), and presolRoundVarsSOS1().
propagate a variable that is known to be nonzero
Definition at line 3604 of file cons_sos1.c. References FALSE, inferVariableZero(), initImplGraphSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE. Referenced by propConsSOS1().
initialize implication graph
Definition at line 3746 of file cons_sos1.c. References FALSE, freeImplGraphSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemory, SCIPblkmem(), SCIPdebugMessage, SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPnodeGetVarSOS1(), tightenVarsBoundsSOS1(), and TRUE. Referenced by propVariableNonzero(), and sepaImplBoundCutsSOS1().
deinitialize implication graph
Definition at line 3913 of file cons_sos1.c. Referenced by initImplGraphSOS1().
get the vertices whose neighbor set covers a subset of the neighbor set of a given other vertex. This function can be used to compute sets of variables to branch on.
Definition at line 3972 of file cons_sos1.c. References getBranchingVerticesSOS1(), NULL, SCIP_Bool, SCIP_OKAY, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors(). Referenced by addBranchingComplementaritiesSOS1(), and getBranchingVerticesSOS1().
get vertices of variables that will be fixed to zero for each node
Definition at line 4079 of file cons_sos1.c. References FALSE, getBranchingPrioritiesSOS1(), getCoverVertices(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and TRUE. Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), and getCoverVertices().
gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision
Definition at line 4191 of file cons_sos1.c. References FALSE, getBranchingVerticesSOS1(), NULL, performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), and TRUE. Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), and getBranchingVerticesSOS1().
performs strong branching with given domain fixings
Definition at line 4292 of file cons_sos1.c. References FALSE, getBranchingDecisionStrongbranchSOS1(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPendProbing(), SCIPfeastol(), SCIPfixVarProbing(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPpropagateProbing(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE. Referenced by getBranchingDecisionStrongbranchSOS1(), and getBranchingPrioritiesSOS1().
apply strong branching to determine the vertex for the next branching decision
Definition at line 4434 of file cons_sos1.c. References FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), MAX, MIN, NULL, performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPallocBufferArray, SCIPdebugMessage, SCIPfeastol(), SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPgetLPObjval(), SCIPgetNDualResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNNodeInitLPIterations(), SCIPgetNNodeInitLPs(), SCIPgetNNodes(), SCIPinfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), and SCIPsortDownRealInt(). Referenced by enforceConflictgraph(), and performStrongbranchSOS1().
for two given vertices
Definition at line 4647 of file cons_sos1.c. References addBranchingComplementaritiesSOS1(), FALSE, isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPallocBufferArray, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE. Referenced by addBranchingComplementaritiesSOS1(), and getBranchingDecisionStrongbranchSOS1().
tries to add feasible complementarity constraints to a given child branching node.
Definition at line 4874 of file cons_sos1.c. References addVarSOS1(), FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getCoverVertices(), isConnectedSOS1(), NULL, resetConflictgraphSOS1(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPcomputeArraysSetminus(), SCIPcreateConsLinear(), SCIPcreateConsSOS1(), SCIPdigraphAddArc(), SCIPdigraphCreate(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisGT(), SCIPisInfinity(), SCIPnodeGetNumber(), SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE. Referenced by enforceConflictgraph(), and getBoundConsFromVertices().
resets local conflict graph to the conflict graph of the root node
Definition at line 5238 of file cons_sos1.c. References enforceConflictgraph(), SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminus(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors(). Referenced by addBranchingComplementaritiesSOS1(), and enforceConflictgraph().
Conflict graph enforcement method The conflict graph can be enforced by different branching rules:
We make use of different selection rules that define on which system of SOS1 variables to branch next:
Definition at line 5294 of file cons_sos1.c. References addBranchingComplementaritiesSOS1(), enforceConssSOS1(), FALSE, fixVariableZeroNode(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), isConnectedSOS1(), log(), MAX, MIN, NULL, pow(), propConsSOS1(), resetConflictgraphSOS1(), SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VARSTATUS_MULTAGGR, SCIPallocBufferArray, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMessage, SCIPdigraphAddArcSafe(), SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPerrorMessage, SCIPfeastol(), SCIPfloor(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPinfinity(), SCIPisFeasZero(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPsortInt(), SCIPupdateNodeLowerbound(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), TRUE, and varGetNodeSOS1(). Referenced by resetConflictgraphSOS1().
SOS1 branching enforcement method We check whether the current solution is feasible, i.e., contains at most one nonzero variable. If not, we branch along the lines indicated by Beale and Tomlin: We first compute
The branches are then
If the constraint contains two variables, the branching of course simplifies. Depending on the parameters (
Constraint branching can also be turned off using parameter
Definition at line 5747 of file cons_sos1.c. References branchCons(), fixVariableZeroNode(), initTCliquegraph(), NULL, propConsSOS1(), REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIP_REAL_MAX, SCIP_REDUCEDDOM, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMessage, SCIPerrorMessage, SCIPfloor(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetName(), and SCIPvarIsBinary(). Referenced by enforceConflictgraph().
initialitze tclique graph and create clique data
Definition at line 5994 of file cons_sos1.c. References TCLIQUE_Data::conflictgraph, TCLIQUE_Data::conshdlr, TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, TCLIQUE_Data::scip, SCIP_CALL, SCIP_NOMEMORY, SCIP_OKAY, SCIPallocMemory, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPnodeGetVarSOS1(), SCIPvarIsActive(), TCLIQUE_Data::sol, TCLIQUE_Data::strthenboundcuts, tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), tcliqueFlush(), and updateWeightsTCliquegraph(). Referenced by enforceConssSOS1().
update weights of tclique graph
Definition at line 6063 of file cons_sos1.c. References addBoundCutSepa(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), REALABS, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tcliqueChangeWeight(). Referenced by initTCliquegraph(), and sepaBoundInequalitiesFromGraph().
adds bound cut(s) to separation storage
Definition at line 6123 of file cons_sos1.c. References FALSE, generateBoundInequalityFromSOS1Nodes(), TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPdebug, SCIPisCutEfficacious(), SCIPprintRow(), SCIProwIsInLP(), and TRUE. Referenced by updateWeightsTCliquegraph().
Generate bound constraint We generate the row corresponding to the following simple valid inequalities:
where 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.
Definition at line 6197 of file cons_sos1.c. References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowCons(), SCIPdebug, SCIPdigraphGetNodeData(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPprintRow(), SCIPsnprintf(), SCIPvarCompare(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TCLIQUE_NEWSOL(), and TRUE. Referenced by addBoundCutSepa(), and generateBoundInequalityFromSOS1Cons().
generates bound cuts using a clique found by algorithm for maximum weight clique and decides whether to stop generating cliques with the algorithm for maximum weight clique Definition at line 6489 of file cons_sos1.c. Referenced by generateBoundInequalityFromSOS1Nodes().
separate bound inequalities from conflict graph
Definition at line 6624 of file cons_sos1.c. References TCLIQUE_Data::cutoff, FALSE, generateBoundInequalityFromSOS1Cons(), TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), TCLIQUE_Data::sol, tcliqueMaxClique(), and updateWeightsTCliquegraph(). Referenced by separateSOS1().
Generate a bound constraint from the variables of an SOS1 constraint (see generateBoundInequalityFromSOS1Nodes() for more information)
Definition at line 6698 of file cons_sos1.c. References CONSHDLR_NAME, generateBoundInequalityFromSOS1Nodes(), initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varGetNodeSOS1(). Referenced by initsepaBoundInequalityFromSOS1Cons(), and sepaBoundInequalitiesFromGraph().
initialize or separate bound inequalities from SOS1 constraints
Definition at line 6761 of file cons_sos1.c. References FALSE, generateBoundInequalityFromSOS1Cons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMessage, SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIProwIsInLP(), sepaImplBoundCutsSOS1(), and TRUE. Referenced by generateBoundInequalityFromSOS1Cons(), and separateSOS1().
separate implied bound cuts
Definition at line 6871 of file cons_sos1.c. References FALSE, initImplGraphSOS1(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPdebugMessage, SCIPdigraphGetNArcs(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPflushRowExtensions(), SCIPgetDepth(), SCIPgetSolVal(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasZero(), SCIPisInfinity(), SCIPprintRow(), SCIPreleaseRow(), SCIProwIsInLP(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), separateSOS1(), and TRUE. Referenced by initsepaBoundInequalityFromSOS1Cons(), and separateSOS1().
separates SOS1 constraints for arbitrary solutions
Definition at line 7088 of file cons_sos1.c. References getVectorOfWeights(), initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMessage, SCIPgetDepth(), SCIPisStopped(), sepaBoundInequalitiesFromGraph(), sepaImplBoundCutsSOS1(), and TRUE. Referenced by sepaImplBoundCutsSOS1().
gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem
Definition at line 7209 of file cons_sos1.c. References markNeighborsMWISHeuristic(), MIN, NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and SCIPsumepsilon(). Referenced by maxWeightIndSetHeuristic(), and separateSOS1().
Definition at line 7280 of file cons_sos1.c. References FALSE, maxWeightIndSetHeuristic(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_NEGATED, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetAggrConstant(), SCIPvarGetAggrVar(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetNodeSOS1(), SCIPvarGetStatus(), and TRUE. Referenced by getVectorOfWeights(), and maxWeightIndSetHeuristic().
calls greedy algorithm for the maximum weighted independent set problem (MWIS) We compute a feasible solution to
by the algorithm GGWMIN of Shuichi Sakai, Mitsunori Togasaki and Koichi Yamazaki in "A note on greedy algorithms for the
maximum weighted independent set problem", Discrete Applied Mathematics. Here
Definition at line 7421 of file cons_sos1.c. References FALSE, getVectorOfWeights(), makeSOS1conflictgraphFeasible(), markNeighborsMWISHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownRealInt(), and TRUE. Referenced by makeSOS1conflictgraphFeasible(), and markNeighborsMWISHeuristic().
based on solution values of the variables, fixes variables of the conflict graph to zero to turn all SOS1 constraints feasible if the SOS1 constraints do not overlap, the method makeSOS1constraintsFeasible() may be faster
Definition at line 7527 of file cons_sos1.c. References FALSE, makeSOS1constraintsFeasible(), maxWeightIndSetHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE. Referenced by maxWeightIndSetHeuristic(), and SCIPmakeSOS1sFeasible().
based on solution values of the variables, fixes variables of the SOS1 constraints to zero to turn these constraints feasible if the SOS1 constraints overlap, the method makeSOS1constraintsFeasible() may result in better primal solutions
Definition at line 7656 of file cons_sos1.c. References FALSE, getDiveBdChgsSOS1conflictgraph(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPgetSolVal(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE. Referenced by makeSOS1conflictgraphFeasible(), and SCIPmakeSOS1sFeasible().
determine a diving variables and boundchanges of diving variables by analyzing the conflict graph if the SOS1 constraints do not overlap, the method getDiveBdChgsSOS1constraints() may be faster
Definition at line 7790 of file cons_sos1.c. References DIVINGCUTOFFVALUE, FALSE, getDiveBdChgsSOS1constraints(), isViolatedSOS1(), MIN, nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdivesetSupportsType(), SCIPgetConflictgraphSOS1(), SCIPgetDivesetScore(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE. Referenced by makeSOS1constraintsFeasible().
determine a diving variables and boundchanges of diving variables by analyzing the SOS1 constraints if the SOS1 constraints overlap, the method getDiveBdChgsSOS1conflictgraph() may produce better results (e.g., due to more diving candidates)
Definition at line 7930 of file cons_sos1.c. References detectVarboundSOS1(), DIVINGCUTOFFVALUE, FALSE, MIN, NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdivesetSupportsType(), SCIPgetDivesetScore(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisPositive(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE. Referenced by getDiveBdChgsSOS1conflictgraph().
check whether
Definition at line 8108 of file cons_sos1.c. References NULL, passConComponentVarbound(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1(). Referenced by checkLinearConssVarboundSOS1(), and getDiveBdChgsSOS1constraints().
pass connected component
Definition at line 8184 of file cons_sos1.c. References checkConComponentsVarbound(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE. Referenced by checkConComponentsVarbound(), and detectVarboundSOS1().
for each connected component
Definition at line 8257 of file cons_sos1.c. References checkLinearConssVarboundSOS1(), FALSE, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, and TRUE. Referenced by passConComponentVarbound().
check all linear constraints for variable bound constraints of the form
Definition at line 8346 of file cons_sos1.c. References checkSwitchNonoverlappingSOS1Methods(), detectVarboundSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasZero(), and varIsSOS1(). Referenced by checkConComponentsVarbound().
switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap
Definition at line 8419 of file cons_sos1.c. References computeNodeDataSOS1(), FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPdebugMessage, SCIPdigraphGetNSuccessors(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1(). Referenced by checkLinearConssVarboundSOS1().
sets node data of conflict graph nodes
Definition at line 8500 of file cons_sos1.c. Referenced by checkSwitchNonoverlappingSOS1Methods().
initialize conflictgraph and create hashmap for SOS1 variables
Definition at line 8537 of file cons_sos1.c. References FALSE, freeConflictgraph(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemory, SCIPblkmem(), SCIPconsGetData(), SCIPdigraphAddArcSafe(), SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArray, SCIPgetNTotalVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisFeasZero(), SCIPsortInt(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
free conflict graph, nodedata and hashmap
Definition at line 8732 of file cons_sos1.c. References CONSHDLR_NAME, NULL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphSetNodeData(), SCIPfreeMemory, and SCIPhashmapFree(). Referenced by initConflictgraph().
copy method for constraint handler plugins (called when SCIP copies plugins) Definition at line 8777 of file cons_sos1.c. Referenced by freeConflictgraph().
destructor of constraint handler to free constraint handler data (called when SCIP is exiting) Definition at line 8794 of file cons_sos1.c.
solving process initialization method of constraint handler (called when branch and bound process is about to begin) Definition at line 8813 of file cons_sos1.c.
solving process deinitialization method of constraint handler (called before branch and bound process data is freed) Definition at line 8866 of file cons_sos1.c.
frees specific constraint data Definition at line 8938 of file cons_sos1.c.
transforms constraint data into data belonging to the transformed problem Definition at line 8992 of file cons_sos1.c.
presolving method of constraint handler Definition at line 9084 of file cons_sos1.c.
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) Definition at line 9207 of file cons_sos1.c.
separation method of constraint handler for LP solutions Definition at line 9232 of file cons_sos1.c.
separation method of constraint handler for arbitrary primal solutions Definition at line 9248 of file cons_sos1.c.
constraint enforcing method of constraint handler for LP solutions Definition at line 9264 of file cons_sos1.c.
constraint enforcing method of constraint handler for pseudo solutions Definition at line 9319 of file cons_sos1.c.
feasibility check method of constraint handler for integral solutions We simply check whether at most one variable is nonzero in the given solution. Definition at line 9377 of file cons_sos1.c.
domain propagation method of constraint handler Definition at line 9445 of file cons_sos1.c.
propagation conflict resolving method of constraint handler We check which bound changes were the reason for infeasibility. We use that inferinfo stores the index of the variable that has bounds that fix it to be nonzero (these bounds are the reason). Definition at line 9590 of file cons_sos1.c.
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 9666 of file cons_sos1.c.
constraint display method of constraint handler Definition at line 9710 of file cons_sos1.c.
constraint copying method of constraint handler Definition at line 9740 of file cons_sos1.c.
constraint parsing method of constraint handler Definition at line 9806 of file cons_sos1.c.
constraint method of constraint handler which returns the variables (if possible) Definition at line 9870 of file cons_sos1.c. References BMScopyMemoryArray, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
constraint method of constraint handler which returns the number of variables (if possible) Definition at line 9893 of file cons_sos1.c. Referenced by SCIP_DECL_CONSGETVARS().
exec the event handler We update the number of variables fixed to be nonzero Definition at line 9914 of file cons_sos1.c.
constraint handler method to determine a diving variable by assigning a variable and two values for diving Definition at line 10011 of file cons_sos1.c.
creates the handler for SOS1 constraints and includes it in SCIP
Definition at line 10052 of file cons_sos1.c. Referenced by SCIPincludeDefaultPlugins().
creates and captures a SOS1 constraint We set the constraint to not be modifable. If the weights are non NULL, the variables are ordered according to these weights (in ascending order).
Definition at line 10266 of file cons_sos1.c. References CONSHDLR_NAME, FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STAGE_TRANSFORMED, SCIPallocBlockMemory, SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPcreateCons(), SCIPcreateConsBasicSOS1(), SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfindConshdlr(), SCIPgetStage(), SCIPgetTransformedVar(), SCIPmarkDoNotMultaggrVar(), SCIPsortRealPtr(), and SCIPvarIsTransformed(). Referenced by addBranchingComplementaritiesSOS1(), extensionOperatorSOS1(), performImplicationGraphAnalysis(), readSOS(), readSos(), readSOScons(), and SCIPcreateConsBasicSOS1().
creates and captures a SOS1 constraint with all constraint flags set to their default values.
Definition at line 10387 of file cons_sos1.c. References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarSOS1(), SCIPcreateConsSOS1(), and TRUE. Referenced by SCIPcreateConsSOS1().
adds variable to SOS1 constraint, the position is determined by the given weight
Definition at line 10403 of file cons_sos1.c. References addVarSOS1(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPappendVarSOS1(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPerrorMessage, and SCIPvarGetName(). Referenced by readSOS(), readSos(), readSOScons(), and SCIPcreateConsBasicSOS1().
appends variable to SOS1 constraint
Definition at line 10437 of file cons_sos1.c. Referenced by SCIPaddVarSOS1(). gets number of variables in SOS1 constraint
Definition at line 10470 of file cons_sos1.c. Referenced by SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp(). gets array of variables in SOS1 constraint
Definition at line 10495 of file cons_sos1.c. Referenced by SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp(). gets array of weights in SOS1 constraint (or NULL if not existent)
Definition at line 10520 of file cons_sos1.c. Referenced by SCIP_DECL_READERWRITE(), and SCIPwriteLp().
gets conflict graph of SOS1 constraints (or NULL if not existent)
Definition at line 10548 of file cons_sos1.c. Referenced by getDiveBdChgsSOS1conflictgraph(), makeSOS1conflictgraphFeasible(), SCIP_DECL_SEPAEXECLP(), and sepaBoundInequalitiesFromGraph().
gets number of problem variables that are part of the SOS1 conflict graph
Definition at line 10570 of file cons_sos1.c. Referenced by getDiveBdChgsSOS1conflictgraph(), makeSOS1conflictgraphFeasible(), SCIP_DECL_SEPAEXECLP(), SCIPperformGenericDivingAlgorithm(), and sepaBoundInequalitiesFromGraph().
returns whether variable is part of the SOS1 conflict graph
Definition at line 10592 of file cons_sos1.c.
returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph
Definition at line 10616 of file cons_sos1.c. Referenced by markNeighborsMWISHeuristic().
returns variable that belongs to a given node from the conflict graph
Definition at line 10647 of file cons_sos1.c. Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), extensionOperatorSOS1(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), getDiveBdChgsSOS1conflictgraph(), getVectorOfWeights(), initImplGraphSOS1(), initTCliquegraph(), isViolatedSOS1(), makeSOS1conflictgraphFeasible(), markNeighborsMWISHeuristic(), nodeGetSolvalBinaryBigMSOS1(), performImplicationGraphAnalysis(), performStrongbranchSOS1(), presolRoundVarsSOS1(), propVariableNonzero(), SCIP_DECL_SEPAEXECLP(), tightenVarsBoundsSOS1(), and updateWeightsTCliquegraph().
based on solution values of the variables, fixes variables to zero to turn all SOS1 constraints feasible
Definition at line 10672 of file cons_sos1.c. References CONSHDLR_NAME, FALSE, makeSOS1conflictgraphFeasible(), makeSOS1constraintsFeasible(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrGetNConss(), SCIPerrorMessage, SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPgetUpperbound(), SCIPisLT(), and TRUE. Referenced by SCIPperformGenericDivingAlgorithm(). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
. Note that it is in principle allowed that a variables appears twice, but it then can be fixed to 0.
is fixed to zero and in the other its neighbors from the conflict graph.![\[ x = \sum_{i=1}^n \alpha_i x_i + c, \]](form_262.png)
by fixing all 
and the lower bounds of 
or the upper bounds are nonpositive if 
. 
) 
implies a new lower/upper bound for 
) 
and 
. Then we search for the index 
that satisfies ![\[ k \leq \frac{w}{W} < k+1. \]](form_273.png)
![\[ x_1 = 0, \ldots, x_k = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0. \]](form_274.png)
![\[ \frac{x_1}{u_1} + \ldots + \frac{x_n}{u_n} \leq 1\qquad\mbox{and}\qquad \frac{x_1}{\ell_1} + \ldots + \frac{x_n}{\ell_1} \leq 1, \]](form_275.png)
and 
are the nonzero and finite lower and upper bounds of the variables 
. If an upper bound < 0 or a lower bound > 0, the constraint itself is redundant, so the cut is not applied (lower bounds > 0 and upper bounds < 0 are usually detected in presolving or propagation). Infinite bounds and zero are skipped. Thus 
inequality. In case of the presence of variable upper bounds, the bound inequality can be further strengthened.![\[ \begin{array}{ll} \min\limits_{z} & {x^*}^T z \\ & z_i + z_j \leq 1, \qquad (i,j)\in E \\ & z_i \in \{0,1\}, \qquad\quad i\in V \end{array} \]](form_279.png)
denotes the current LP relaxation solution. Note that the solution of the MWIS is the indicator vector of an independent set. 
is a bound variable of 
; i.e., 
or 
for positive values 
. If true, then add this information to the node data of the conflict graph. 
of the conflict graph and check whether all the variables correspond to a unique variable upper bound variable 
, i.e., 
for every 
.
, where