SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
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 generateBoundInequalityFromSOS1Cons(), SCIPaddVarSOS1(), SCIPappendVarSOS1(), and SCIPcreateConsSOS1().
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 update conflict graph during presolving procedure Definition at line 111 of file cons_sos1.c.
whether to use conflict graph propagation Definition at line 114 of file cons_sos1.c.
whether to use implication graph propagation Definition at line 115 of file cons_sos1.c.
whether to use SOS1 constraint propagation Definition at line 116 of file cons_sos1.c.
if TRUE turn neighborhood branching method on (note: an automatic switching to SOS1 branching is possible) Definition at line 119 of file cons_sos1.c.
if TRUE turn bipartite branching method on (note: an automatic switching to SOS1 branching is possible) Definition at line 120 of file cons_sos1.c.
if TRUE turn SOS1 branching method on 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 122 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 123 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 126 of file cons_sos1.c.
maximal number of complementarity constraints added per branching node (-1: no limit) Definition at line 129 of file cons_sos1.c.
only add complementarity constraints to branching nodes for predefined depth (-1: no limit) Definition at line 130 of file cons_sos1.c.
minimal feasibility value for complementarity constraints in order to be added to the branching node Definition at line 131 of file cons_sos1.c.
minimal feasibility value for bound inequalities in order to be added to the branching node Definition at line 132 of file cons_sos1.c.
should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities Definition at line 133 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 136 of file cons_sos1.c.
maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) Definition at line 139 of file cons_sos1.c.
if TRUE separate bound inequalities from SOS1 constraints Definition at line 142 of file cons_sos1.c.
if TRUE separate bound inequalities from the conflict graph Definition at line 143 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 144 of file cons_sos1.c.
frequency for separating bound cuts; zero means to separate only in the root node Definition at line 145 of file cons_sos1.c.
node depth of separating bound cuts (-1: no limit) Definition at line 146 of file cons_sos1.c.
maximal number of bound cuts separated per branching node Definition at line 147 of file cons_sos1.c.
maximal number of bound cuts separated per iteration in the root node Definition at line 148 of file cons_sos1.c.
if TRUE then bound cuts are strengthened in case bound variables are available Definition at line 149 of file cons_sos1.c.
frequency for separating implied bound cuts; zero means to separate only in the root node Definition at line 150 of file cons_sos1.c.
node depth of separating implied bound cuts (-1: no limit) Definition at line 151 of file cons_sos1.c.
maximal number of implied bound cuts separated per branching node Definition at line 152 of file cons_sos1.c.
maximal number of implied bound cuts separated per iteration in the root node Definition at line 153 of file cons_sos1.c.
Definition at line 156 of file cons_sos1.c.
Definition at line 157 of file cons_sos1.c.
Definition at line 160 of file cons_sos1.c. Typedef Documentation
Definition at line 190 of file cons_sos1.c.
Definition at line 199 of file cons_sos1.c. Function Documentation
returns whether two vertices are adjacent in the conflict graph
Definition at line 297 of file cons_sos1.c. References FALSE, NULL, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPsortInt(), SCIPswapInts(), and TRUE. Referenced by addBranchingComplementaritiesSOS1(), computeVarsCoverSOS1(), extensionOperatorSOS1(), getBoundConsFromVertices(), tightenVarsBoundsSOS1(), updateConflictGraphSOS1(), and updateImplicationGraphSOS1().
checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable
Definition at line 357 of file cons_sos1.c. References FALSE, NULL, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
returns solution value of imaginary binary big-M variable of a given node from the conflict graph
Definition at line 402 of file cons_sos1.c. References NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal(). Referenced by computeVarsCoverSOS1(), and getBoundConsFromVertices().
gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph
Definition at line 452 of file cons_sos1.c. References NULL, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetLbLocal(). Referenced by updateWeightsTCliquegraph().
gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph
Definition at line 479 of file cons_sos1.c. References NULL, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetUbLocal(). Referenced by updateWeightsTCliquegraph().
returns whether variable is part of the SOS1 conflict graph
Definition at line 506 of file cons_sos1.c. Referenced by checkLinearConssVarboundSOS1().
returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph
Definition at line 523 of file cons_sos1.c. Referenced by checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), detectVarboundSOS1(), enforceConflictgraph(), genConflictgraphLinearCons(), generateBoundInequalityFromSOS1Cons(), getSOS1Implications(), handleNewVariableSOS1(), presolRoundConssSOS1(), tightenVarsBoundsSOS1(), updateConflictGraphSOS1(), and updateImplicationGraphSOS1().
fix variable in given node to 0 or add constraint if variable is multi-aggregated
Definition at line 544 of file cons_sos1.c. References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMessage, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE. Referenced by 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 599 of file cons_sos1.c. References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPfixVar(), SCIPflattenVarAggregationGraph(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE. Referenced by presolRoundConsSOS1().
fix variable in local node to 0, and return whether the operation was feasible
Definition at line 673 of file cons_sos1.c. References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE. Referenced by propConsSOS1(), and propVariableNonzero().
add lock on variable
Definition at line 716 of file cons_sos1.c. References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal(). Referenced by handleNewVariableSOS1(), and presolRoundConsSOS1().
remove lock on variable
Definition at line 735 of file cons_sos1.c. References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPunlockVarCons(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal(). Referenced by deleteVarSOS1(), and presolRoundConsSOS1().
ensures that the vars and weights array can store at least num entries
Definition at line 754 of file cons_sos1.c. References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray. Referenced by addVarSOS1(), and appendVarSOS1().
handle new variable
Definition at line 782 of file cons_sos1.c. References lockVariableSOS1(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPdebugMessage, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPsortInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1(). Referenced by addVarSOS1(), appendVarSOS1(), and SCIPcreateConsSOS1().
adds a variable to an SOS1 constraint, at position given by weight - ascending order
Definition at line 917 of file cons_sos1.c. References consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE. Referenced by addBranchingComplementaritiesSOS1(), SCIPaddVarSOS1(), and updateConflictGraphSOS1().
appends a variable to an SOS1 constraint
Definition at line 987 of file cons_sos1.c. References consdataEnsurevarsSizeSOS1(), FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), and SCIPvarIsTransformed(). Referenced by SCIPappendVarSOS1().
deletes a variable of an SOS1 constraint
Definition at line 1033 of file cons_sos1.c. References NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1(). Referenced by 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 1072 of file cons_sos1.c. References FALSE, 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 presolRoundConssSOS1().
generates conflict graph that is induced by the variables of a linear constraint
Definition at line 1334 of file cons_sos1.c. References NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1(). Referenced by tightenVarsBoundsSOS1().
determine the common successors of the vertices from the considered clique
Definition at line 1387 of file cons_sos1.c. References NULL, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1(). Referenced by presolRoundConssSOS1().
get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero
Definition at line 1484 of file cons_sos1.c. References NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, and varGetNodeSOS1(). Referenced by tightenVarsBoundsSOS1().
perform one presolving round for a single SOS1 constraint We perform the following presolving steps.
Definition at line 1550 of file cons_sos1.c. References deleteVarSOS1(), FALSE, fixVariableZero(), lockVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcatchVarEvent(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMessage, SCIPdelCons(), SCIPdropVarEvent(), SCIPfixVar(), SCIPgetProbvarSum(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, and unlockVariableSOS1(). Referenced by 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 1774 of file cons_sos1.c. References cliqueGetCommonSuccessorsSOS1(), extensionOperatorSOS1(), FALSE, MAX, NULL, 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().
updates conflict graph based on the information of an implication graph
Definition at line 2038 of file cons_sos1.c. References addVarSOS1(), FALSE, isConnectedSOS1(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSOS1(), SCIPdigraphAddArc(), SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), TRUE, and varGetNodeSOS1(). Referenced by presolRoundVarsSOS1().
returns whether node is implied to be zero; this information is taken from the input array 'implnodes'
Definition at line 2140 of file cons_sos1.c. References FALSE, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and TRUE. Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
updates arc data of implication graph
Definition at line 2169 of file cons_sos1.c. References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPdebugMessage, SCIPdigraphAddArc(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), and TRUE. 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 2281 of file cons_sos1.c. References 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().
search new disjoint clique that covers given node For a given vertex
Definition at line 2435 of file cons_sos1.c. References isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasLT(), and TRUE. Referenced by tightenVarsBoundsSOS1().
try to tighten upper and lower bounds for variables
Definition at line 2546 of file cons_sos1.c. References computeVarsCoverSOS1(), FALSE, genConflictgraphLinearCons(), getSOS1Implications(), isConnectedSOS1(), isImpliedZero(), MAX, MIN, NULL, 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 initImplGraphSOS1(), and presolRoundVarsSOS1().
perform one presolving round for variables We perform the following presolving steps:
Definition at line 3246 of file cons_sos1.c. References FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_SUCCESS, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMessage, SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfreeBufferArrayNull, SCIPfreeMemory, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPnodeGetVarSOS1(), tightenVarsBoundsSOS1(), TRUE, and updateConflictGraphSOS1().
propagate variables of SOS1 constraint
Definition at line 3380 of file cons_sos1.c. References FALSE, inferVariableZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsIsModifiable(), SCIPdebugMessage, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE. Referenced by enforceConflictgraph(), and enforceConssSOS1().
propagate a variable that is known to be nonzero
Definition at line 3478 of file cons_sos1.c. References FALSE, inferVariableZero(), 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.
initialize implication graph
Definition at line 3620 of file cons_sos1.c. References FALSE, 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 sepaImplBoundCutsSOS1().
deinitialize implication graph
Definition at line 3784 of file cons_sos1.c.
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 3839 of file cons_sos1.c. References NULL, 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 3946 of file cons_sos1.c. References FALSE, getCoverVertices(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and TRUE. Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), and getBranchingPrioritiesSOS1().
gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision
Definition at line 4058 of file cons_sos1.c. References FALSE, getBranchingVerticesSOS1(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), and TRUE. Referenced by enforceConflictgraph(), and getBranchingDecisionStrongbranchSOS1().
performs strong branching with given domain fixings
Definition at line 4159 of file cons_sos1.c. References FALSE, 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(), and TRUE. Referenced by getBranchingDecisionStrongbranchSOS1().
apply strong branching to determine the vertex for the next branching decision
Definition at line 4287 of file cons_sos1.c. References FALSE, fixVariableZeroNode(), 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().
for two given vertices
Definition at line 4500 of file cons_sos1.c. References 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().
tries to add feasible complementarity constraints to a given child branching node.
Definition at line 4727 of file cons_sos1.c. References addVarSOS1(), FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getCoverVertices(), isConnectedSOS1(), NULL, 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().
resets local conflict graph to the conflict graph of the root node
Definition at line 5091 of file cons_sos1.c. References SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminus(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors(). Referenced by 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 5147 of file cons_sos1.c. References addBranchingComplementaritiesSOS1(), FALSE, fixVariableZeroNode(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), log(), MAX, MIN, NULL, pow(), propConsSOS1(), resetConflictgraphSOS1(), SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VARSTATUS_MULTAGGR, SCIPallocBufferArray, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMessage, SCIPdigraphAddArcSafe(), SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfeastol(), SCIPfloor(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPinfinity(), SCIPisFeasZero(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPsortInt(), SCIPupdateNodeLowerbound(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().
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 5570 of file cons_sos1.c. References branchCons(), fixVariableZeroNode(), NULL, propConsSOS1(), REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_REDUCEDDOM, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMessage, SCIPfloor(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPresetConsAge(), and SCIPvarGetName().
initialitze tclique graph and create clique data
Definition at line 5800 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(), and tcliqueFlush().
update weights of tclique graph
Definition at line 5869 of file cons_sos1.c. References nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), REALABS, TCLIQUE_Data::scaleval, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tcliqueChangeWeight(). Referenced by sepaBoundInequalitiesFromGraph().
adds bound cut(s) to separation storage
Definition at line 5929 of file cons_sos1.c. References FALSE, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPdebug, SCIPisCutEfficacious(), SCIPprintRow(), SCIProwIsInLP(), and TRUE.
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 6003 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(), and TRUE. Referenced by 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 6261 of file cons_sos1.c.
separate bound inequalities from conflict graph
Definition at line 6396 of file cons_sos1.c. References TCLIQUE_Data::cutoff, FALSE, TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, 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 6470 of file cons_sos1.c. References CONSHDLR_NAME, generateBoundInequalityFromSOS1Nodes(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varGetNodeSOS1(). Referenced by initsepaBoundInequalityFromSOS1Cons().
initialize or separate bound inequalities from SOS1 constraints
Definition at line 6533 of file cons_sos1.c. References FALSE, generateBoundInequalityFromSOS1Cons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMessage, SCIPisCutEfficacious(), SCIPisEQ(), SCIPisInfinity(), SCIPprintRow(), SCIPresetConsAge(), SCIProwGetLhs(), SCIProwGetRhs(), SCIProwIsInLP(), and TRUE. Referenced by separateSOS1().
separate implied bound cuts
Definition at line 6625 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(), and TRUE. Referenced by separateSOS1().
separates SOS1 constraints for arbitrary solutions
Definition at line 6842 of file cons_sos1.c. References initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMessage, SCIPgetDepth(), SCIPisStopped(), sepaBoundInequalitiesFromGraph(), sepaImplBoundCutsSOS1(), and TRUE.
gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem
Definition at line 6963 of file cons_sos1.c. References MIN, NULL, REALABS, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and SCIPsumepsilon(). Referenced by maxWeightIndSetHeuristic().
Definition at line 7034 of file cons_sos1.c. References FALSE, 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 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 7171 of file cons_sos1.c. References FALSE, getVectorOfWeights(), markNeighborsMWISHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownRealInt(), and TRUE. Referenced by SCIPmakeSOS1sFeasible().
check whether
Definition at line 7273 of file cons_sos1.c. References NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1(). Referenced by checkLinearConssVarboundSOS1().
pass connected component
Definition at line 7349 of file cons_sos1.c. References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE. Referenced by checkConComponentsVarbound().
for each connected component
Definition at line 7422 of file cons_sos1.c. References FALSE, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, and TRUE. Referenced by computeNodeDataSOS1().
check all linear constraints for variable bound constraints of the form
Definition at line 7511 of file cons_sos1.c. References detectVarboundSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasZero(), and varIsSOS1(). Referenced by computeNodeDataSOS1().
switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap
Definition at line 7584 of file cons_sos1.c. References FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPdebugMessage, SCIPdigraphGetNSuccessors(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().
sets node data of conflict graph nodes
Definition at line 7665 of file cons_sos1.c. References checkConComponentsVarbound(), checkLinearConssVarboundSOS1(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), and TRUE.
initialize conflictgraph and create hashmap for SOS1 variables
Definition at line 7702 of file cons_sos1.c. References FALSE, 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 7897 of file cons_sos1.c.
copy method for constraint handler plugins (called when SCIP copies plugins) Definition at line 7935 of file cons_sos1.c.
destructor of constraint handler to free constraint handler data (called when SCIP is exiting) Definition at line 7952 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 7971 of file cons_sos1.c.
solving process deinitialization method of constraint handler (called before branch and bound process data is freed) Definition at line 8025 of file cons_sos1.c.
frees specific constraint data Definition at line 8094 of file cons_sos1.c.
transforms constraint data into data belonging to the transformed problem Definition at line 8148 of file cons_sos1.c.
presolving method of constraint handler Definition at line 8240 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 8361 of file cons_sos1.c.
separation method of constraint handler for LP solutions Definition at line 8386 of file cons_sos1.c.
separation method of constraint handler for arbitrary primal solutions Definition at line 8402 of file cons_sos1.c.
constraint enforcing method of constraint handler for LP solutions Definition at line 8418 of file cons_sos1.c.
constraint enforcing method of constraint handler for pseudo solutions Definition at line 8473 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 8531 of file cons_sos1.c.
domain propagation method of constraint handler Definition at line 8599 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 8744 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 8820 of file cons_sos1.c.
constraint display method of constraint handler Definition at line 8864 of file cons_sos1.c.
constraint copying method of constraint handler Definition at line 8894 of file cons_sos1.c.
constraint parsing method of constraint handler Definition at line 8960 of file cons_sos1.c.
constraint method of constraint handler which returns the variables (if possible) Definition at line 9024 of file cons_sos1.c.
constraint method of constraint handler which returns the number of variables (if possible) Definition at line 9047 of file cons_sos1.c.
exec the event handler We update the number of variables fixed to be nonzero Definition at line 9068 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 9165 of file cons_sos1.c.
creates the handler for SOS1 constraints and includes it in SCIP
Definition at line 9299 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 9517 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(), SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfindConshdlr(), SCIPgetStage(), SCIPgetTransformedVar(), SCIPmarkDoNotMultaggrVar(), SCIPsortRealPtr(), and SCIPvarIsTransformed(). Referenced by addBranchingComplementaritiesSOS1(), extensionOperatorSOS1(), readSOS(), readSos(), readSOScons(), SCIPcreateConsBasicSOS1(), and updateConflictGraphSOS1().
creates and captures a SOS1 constraint with all constraint flags set to their default values.
Definition at line 9638 of file cons_sos1.c. References FALSE, SCIP_CALL, SCIP_OKAY, SCIPcreateConsSOS1(), and TRUE.
adds variable to SOS1 constraint, the position is determined by the given weight
Definition at line 9654 of file cons_sos1.c. References addVarSOS1(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPerrorMessage, and SCIPvarGetName(). Referenced by readSOS(), readSos(), and readSOScons().
appends variable to SOS1 constraint
Definition at line 9688 of file cons_sos1.c. References appendVarSOS1(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPerrorMessage, and SCIPvarGetName(). gets number of variables in SOS1 constraint
Definition at line 9721 of file cons_sos1.c. Referenced by SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp(). gets array of variables in SOS1 constraint
Definition at line 9746 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 9771 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 9799 of file cons_sos1.c. Referenced by SCIP_DECL_SEPAEXECLP(), SCIPmakeSOS1sFeasible(), and sepaBoundInequalitiesFromGraph().
gets number of problem variables that are part of the SOS1 conflict graph
Definition at line 9821 of file cons_sos1.c. Referenced by SCIP_DECL_SEPAEXECLP(), SCIPmakeSOS1sFeasible(), SCIPperformGenericDivingAlgorithm(), and sepaBoundInequalitiesFromGraph().
returns whether variable is part of the SOS1 conflict graph
Definition at line 9843 of file cons_sos1.c.
returns SOS1 index of variable or -1 if variable is part of the SOS1 conflict graph
Definition at line 9867 of file cons_sos1.c. Referenced by markNeighborsMWISHeuristic().
returns variable that belongs to a given node from the conflict graph
Definition at line 9898 of file cons_sos1.c. Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), extensionOperatorSOS1(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), getVectorOfWeights(), initImplGraphSOS1(), initTCliquegraph(), isViolatedSOS1(), markNeighborsMWISHeuristic(), nodeGetSolvalBinaryBigMSOS1(), performStrongbranchSOS1(), presolRoundVarsSOS1(), propVariableNonzero(), SCIP_DECL_SEPAEXECLP(), SCIPmakeSOS1sFeasible(), tightenVarsBoundsSOS1(), updateConflictGraphSOS1(), and updateWeightsTCliquegraph().
based on solution values of the variables, fixes variables to zero to turn all SOS1 constraints feasible
Definition at line 9923 of file cons_sos1.c. References FALSE, maxWeightIndSetHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetUpperbound(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisLT(), SCIPnodeGetVarSOS1(), SCIPsetSolVal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), 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_489.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_212.png)
![\[ x_1 = 0, \ldots, x_k = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0. \]](form_213.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_214.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_496.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