SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
constraint 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 \(x \cdot y = 0\). Note that it is in principle allowed that a variables appears twice, but it then can be fixed to 0.
This implementation of this constraint handler is based on classical ideas, see e.g.
"Special Facilities in General Mathematical Programming System for
Non-Convex Problems Using Ordered Sets of Variables"
E. Beale and J. Tomlin, Proc. 5th IFORS Conference, 447-454 (1970)
The order of the variables is determined as follows:
The validity of the SOS1 constraints can be enforced by different branching rules:
i, i.e., in one branch \(x_i\) is fixed to zero and in the other its neighbors from the conflict graph.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.
Typedefs | |
| typedef struct SCIP_NodeData | SCIP_NODEDATA |
| typedef struct SCIP_SuccData | SCIP_SUCCDATA |
Functions | |
| static SCIP_Bool | isConnectedSOS1 (SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *conflictgraph, int vertex1, int vertex2) |
| static SCIP_Bool | isViolatedSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_SOL *sol) |
| static SCIP_Real | nodeGetSolvalBinaryBigMSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node) |
| static SCIP_Real | nodeGetSolvalVarboundLbSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node) |
| static SCIP_Real | nodeGetSolvalVarboundUbSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node) |
| static SCIP_Bool | varIsSOS1 (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var) |
| static int | varGetNodeSOS1 (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var) |
| static SCIP_RETCODE | fixVariableZeroNode (SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible) |
| static SCIP_RETCODE | fixVariableZero (SCIP *scip, SCIP_VAR *var, SCIP_Bool *infeasible, SCIP_Bool *tightened) |
| static SCIP_RETCODE | inferVariableZero (SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened, SCIP_Bool *success) |
| static SCIP_RETCODE | lockVariableSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) |
| static SCIP_RETCODE | unlockVariableSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) |
| static SCIP_RETCODE | consdataEnsurevarsSizeSOS1 (SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveWeights) |
| static SCIP_RETCODE | handleNewVariableSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Bool transformed) |
| static SCIP_RETCODE | addVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Real weight) |
| static SCIP_RETCODE | appendVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var) |
| static SCIP_RETCODE | deleteVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos) |
| static SCIP_RETCODE | extensionOperatorSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *vertexcliquegraph, int nsos1vars, int nconss, SCIP_CONS *cons, SCIP_VAR **vars, SCIP_Real *weights, SCIP_Bool firstcall, SCIP_Bool usebacktrack, int **cliques, int *ncliques, int *cliquesizes, int *newclique, int *workingset, int nworkingset, int nexts, int pos, int *maxextensions, int *naddconss, SCIP_Bool *success) |
| static SCIP_RETCODE | genConflictgraphLinearCons (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraphlin, SCIP_DIGRAPH *conflictgraphorig, SCIP_VAR **linvars, int nlinvars, int *posinlinvars) |
| static SCIP_RETCODE | cliqueGetCommonSuccessorsSOS1 (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int *clique, SCIP_VAR **vars, int nvars, int *comsucc, int *ncomsucc) |
| static SCIP_RETCODE | getSOS1Implications (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR **vars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, int node) |
| static SCIP_RETCODE | presolRoundConsSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *substituted, SCIP_Bool *cutoff, SCIP_Bool *success, int *ndelconss, int *nupgdconss, int *nfixedvars, int *nremovedvars) |
| static SCIP_RETCODE | presolRoundConssSOS1 (SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, SCIP_CONS **conss, int nconss, int nsos1vars, int *naddconss, int *ndelconss, int *nupgdconss, int *nfixedvars, int *nremovedvars, SCIP_RESULT *result) |
| static SCIP_RETCODE | performImplicationGraphAnalysis (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **totalvars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool **adjacencymatrix, int givennode, int nonznode, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Bool *implnodes, int *naddconss, int *probingdepth, SCIP_Bool *infeasible) |
| static SCIP_Bool | isImpliedZero (SCIP_DIGRAPH *conflictgraph, SCIP_Bool *implnodes, int node) |
| static SCIP_RETCODE | updateArcData (SCIP *scip, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_VAR **totalvars, SCIP_VAR *varv, SCIP_VAR *varw, SCIP_Real lb, SCIP_Real ub, SCIP_Real newbound, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible) |
| static SCIP_RETCODE | updateImplicationGraphSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, SCIP_VAR **totalvars, int **cliquecovers, int *cliquecoversizes, int *varincover, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_Real *bounds, SCIP_VAR *var, SCIP_Real bound, SCIP_Real boundnonzero, int ninftynonzero, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible) |
| static SCIP_RETCODE | computeVarsCoverSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraphroot, SCIP_DIGRAPH *conflictgraphlin, SCIP_VAR **linvars, SCIP_Bool *coveredvars, int *clique, int *cliquesize, int v, SCIP_Bool considersolvals) |
| static SCIP_RETCODE | tightenVarsBoundsSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool **adjacencymatrix, SCIP_VAR **totalvars, int ntotalvars, int nsos1vars, int *nchgbds, SCIP_Bool *implupdate, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | presolRoundVarsSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, int nsos1vars, int *nfixedvars, int *nchgbds, int *naddconss, SCIP_RESULT *result) |
| static SCIP_RETCODE | propConsSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *ngen) |
| static SCIP_RETCODE | propVariableNonzero (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *implgraph, SCIP_CONS *cons, int node, SCIP_Bool implprop, SCIP_Bool *cutoff, int *ngen) |
| static SCIP_RETCODE | initImplGraphSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars, int maxrounds, int *nchgbds, SCIP_Bool *cutoff, SCIP_Bool *success) |
| static SCIP_RETCODE | freeImplGraphSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata) |
| static SCIP_RETCODE | getCoverVertices (SCIP_DIGRAPH *conflictgraph, SCIP_Bool *verticesarefixed, int vertex, int *neightocover, int nneightocover, int *coververtices, int *ncoververtices) |
| static SCIP_RETCODE | getBranchingVerticesSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int branchvertex, int *fixingsnode1, int *nfixingsnode1, int *fixingsnode2, int *nfixingsnode2) |
| static SCIP_RETCODE | getBranchingPrioritiesSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int *fixingsnode1, int *fixingsnode2, SCIP_Real *branchpriors, int *vertexbestprior, SCIP_Bool *relsolfeas) |
| static SCIP_RETCODE | performStrongbranchSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, int *fixingsexec, int nfixingsexec, int *fixingsop, int nfixingsop, int inititer, SCIP_Bool fixnonzero, int *domainfixings, int *ndomainfixings, SCIP_Bool *infeasible, SCIP_Real *objval, SCIP_Bool *lperror) |
| static SCIP_RETCODE | getBranchingDecisionStrongbranchSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars, SCIP_Real lpobjval, SCIP_Bool bipbranch, int nstrongrounds, SCIP_Bool *verticesarefixed, int *fixingsnode1, int *fixingsnode2, int *vertexbestprior, SCIP_Real *bestobjval1, SCIP_Real *bestobjval2, SCIP_RESULT *result) |
| static SCIP_RETCODE | getBoundConsFromVertices (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int v1, int v2, SCIP_VAR *boundvar, SCIP_Bool extend, SCIP_CONS *cons, SCIP_Real *feas) |
| static SCIP_RETCODE | addBranchingComplementaritiesSOS1 (SCIP *scip, SCIP_NODE *node, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, SCIP_SOL *sol, int nsos1vars, SCIP_Bool *verticesarefixed, int *fixingsnode1, int nfixingsnode1, int *fixingsnode2, int nfixingsnode2, int *naddedconss, SCIP_Bool onlyviolsos1) |
| static SCIP_RETCODE | resetConflictgraphSOS1 (SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, int nsos1vars) |
| static SCIP_RETCODE | enforceConflictgraph (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result) |
| static SCIP_RETCODE | enforceConssSOS1 (SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result) |
| static SCIP_RETCODE | enforceSOS1 (SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result) |
| static SCIP_RETCODE | initTCliquegraph (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars) |
| static SCIP_RETCODE | updateWeightsTCliquegraph (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, TCLIQUE_DATA *tcliquedata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars) |
| static SCIP_RETCODE | addBoundCutSepa (SCIP *scip, TCLIQUE_DATA *tcliquedata, SCIP_ROW *rowlb, SCIP_ROW *rowub, SCIP_Bool *success, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | generateBoundInequalityFromSOS1Nodes (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int *nodes, int nnodes, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool global, SCIP_Bool strengthen, SCIP_Bool removable, const char *nameext, SCIP_ROW **rowlb, SCIP_ROW **rowub) |
| static | TCLIQUE_NEWSOL (tcliqueNewsolClique) |
| static SCIP_RETCODE | sepaBoundInequalitiesFromGraph (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_SOL *sol, int maxboundcuts, int *ngen, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | generateBoundInequalityFromSOS1Cons (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool local, SCIP_Bool global, SCIP_Bool strengthen, SCIP_Bool removable, SCIP_ROW **rowlb, SCIP_ROW **rowub) |
| static SCIP_RETCODE | initsepaBoundInequalityFromSOS1Cons (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool solvedinitlp, int maxboundcuts, int *ngen, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | sepaImplBoundCutsSOS1 (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_SOL *sol, int maxcuts, int *ngen, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | separateSOS1 (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, SCIP_RESULT *result) |
| static SCIP_RETCODE | getVectorOfWeights (SCIP *scip, SCIP_SOL *sol, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *indicatorzero, SCIP_Real *weights) |
| static SCIP_RETCODE | markNeighborsMWISHeuristic (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int node, SCIP_Bool *mark, SCIP_Bool *indset, int *cnt, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | maxWeightIndSetHeuristic (SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *indicatorzero, SCIP_Bool *indset) |
| static SCIP_RETCODE | makeSOS1conflictgraphFeasible (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *allroundable) |
| static SCIP_RETCODE | makeSOS1constraintsFeasible (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *allroundable) |
| static SCIP_RETCODE | getDiveBdChgsSOS1conflictgraph (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success) |
| static SCIP_RETCODE | getDiveBdChgsSOS1constraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success) |
| static SCIP_RETCODE | detectVarboundSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var0, SCIP_VAR *var1, SCIP_Real val0, SCIP_Real val1) |
| static SCIP_RETCODE | passConComponentVarbound (SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_VAR *boundvar, SCIP_Bool checklb, SCIP_Bool *processed, int *concomp, int *nconcomp, SCIP_Bool *unique) |
| static SCIP_RETCODE | checkConComponentsVarbound (SCIP *scip, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool checklb) |
| static SCIP_RETCODE | checkLinearConssVarboundSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **linconss, int nlinconss) |
| static SCIP_RETCODE | checkSwitchNonoverlappingSOS1Methods (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_CONS **conss, int nconss) |
| static SCIP_RETCODE | computeNodeDataSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nsos1vars) |
| static SCIP_RETCODE | initConflictgraph (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss) |
| static SCIP_RETCODE | freeConflictgraph (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata) |
| static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopySOS1) |
| static | SCIP_DECL_CONSFREE (consFreeSOS1) |
| static | SCIP_DECL_CONSINITSOL (consInitsolSOS1) |
| static | SCIP_DECL_CONSEXITSOL (consExitsolSOS1) |
| static | SCIP_DECL_CONSDELETE (consDeleteSOS1) |
| static | SCIP_DECL_CONSTRANS (consTransSOS1) |
| static | SCIP_DECL_CONSPRESOL (consPresolSOS1) |
| static | SCIP_DECL_CONSINITLP (consInitlpSOS1) |
| static | SCIP_DECL_CONSSEPALP (consSepalpSOS1) |
| static | SCIP_DECL_CONSSEPASOL (consSepasolSOS1) |
| static | SCIP_DECL_CONSENFOLP (consEnfolpSOS1) |
| static | SCIP_DECL_CONSENFORELAX (consEnforelaxSOS1) |
| static | SCIP_DECL_CONSENFOPS (consEnfopsSOS1) |
| static | SCIP_DECL_CONSCHECK (consCheckSOS1) |
| static | SCIP_DECL_CONSPROP (consPropSOS1) |
| static | SCIP_DECL_CONSRESPROP (consRespropSOS1) |
| static | SCIP_DECL_CONSLOCK (consLockSOS1) |
| static | SCIP_DECL_CONSPRINT (consPrintSOS1) |
| static | SCIP_DECL_CONSCOPY (consCopySOS1) |
| static | SCIP_DECL_CONSPARSE (consParseSOS1) |
| static | SCIP_DECL_CONSGETVARS (consGetVarsSOS1) |
| static | SCIP_DECL_CONSGETNVARS (consGetNVarsSOS1) |
| static | SCIP_DECL_EVENTEXEC (eventExecSOS1) |
| static | SCIP_DECL_CONSGETDIVEBDCHGS (consGetDiveBdChgsSOS1) |
| SCIP_RETCODE | SCIPincludeConshdlrSOS1 (SCIP *scip) |
| SCIP_RETCODE | SCIPcreateConsSOS1 (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) |
| SCIP_RETCODE | SCIPcreateConsBasicSOS1 (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights) |
| SCIP_RETCODE | SCIPaddVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight) |
| SCIP_RETCODE | SCIPappendVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) |
| int | SCIPgetNVarsSOS1 (SCIP *scip, SCIP_CONS *cons) |
| SCIP_VAR ** | SCIPgetVarsSOS1 (SCIP *scip, SCIP_CONS *cons) |
| SCIP_Real * | SCIPgetWeightsSOS1 (SCIP *scip, SCIP_CONS *cons) |
| SCIP_DIGRAPH * | SCIPgetConflictgraphSOS1 (SCIP_CONSHDLR *conshdlr) |
| int | SCIPgetNSOS1Vars (SCIP_CONSHDLR *conshdlr) |
| SCIP_Bool | SCIPvarIsSOS1 (SCIP_CONSHDLR *conshdlr, SCIP_VAR *var) |
| int | SCIPvarGetNodeSOS1 (SCIP_CONSHDLR *conshdlr, SCIP_VAR *var) |
| SCIP_VAR * | SCIPnodeGetVarSOS1 (SCIP_DIGRAPH *conflictgraph, int node) |
| SCIP_RETCODE | SCIPmakeSOS1sFeasible (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success) |
| #define CONSHDLR_NAME "SOS1" |
Definition at line 86 of file cons_sos1.c.
Referenced by freeConflictgraph(), generateBoundInequalityFromSOS1Cons(), SCIPaddVarSOS1(), SCIPcreateConsSOS1(), and SCIPmakeSOS1sFeasible().
| #define CONSHDLR_DESC "SOS1 constraint handler" |
Definition at line 87 of file cons_sos1.c.
| #define CONSHDLR_SEPAPRIORITY 1000 |
priority of the constraint handler for separation
Definition at line 88 of file cons_sos1.c.
| #define CONSHDLR_ENFOPRIORITY 100 |
priority of the constraint handler for constraint enforcing
Definition at line 89 of file cons_sos1.c.
| #define CONSHDLR_CHECKPRIORITY -10 |
priority of the constraint handler for checking feasibility
Definition at line 90 of file cons_sos1.c.
| #define CONSHDLR_SEPAFREQ 10 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 91 of file cons_sos1.c.
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 92 of file cons_sos1.c.
| #define CONSHDLR_EAGERFREQ 100 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 93 of file cons_sos1.c.
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 96 of file cons_sos1.c.
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 97 of file cons_sos1.c.
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 98 of file cons_sos1.c.
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 99 of file cons_sos1.c.
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 100 of file cons_sos1.c.
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM |
Definition at line 101 of file cons_sos1.c.
| #define DEFAULT_MAXSOSADJACENCY 10000 |
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.
| #define DEFAULT_MAXEXTENSIONS 1 |
maximal number of extensions that will be computed for each SOS1 constraint
Definition at line 109 of file cons_sos1.c.
| #define DEFAULT_MAXTIGHTENBDS 5 |
maximal number of bound tightening rounds per presolving round (-1: no limit)
Definition at line 110 of file cons_sos1.c.
| #define DEFAULT_PERFIMPLANALYSIS FALSE |
if TRUE then perform implication graph analysis (might add additional SOS1 constraints)
Definition at line 111 of file cons_sos1.c.
| #define DEFAULT_DEPTHIMPLANALYSIS -1 |
number of recursive calls of implication graph analysis (-1: no limit)
Definition at line 112 of file cons_sos1.c.
| #define DEFAULT_CONFLICTPROP TRUE |
whether to use conflict graph propagation
Definition at line 115 of file cons_sos1.c.
| #define DEFAULT_IMPLPROP TRUE |
whether to use implication graph propagation
Definition at line 116 of file cons_sos1.c.
| #define DEFAULT_SOSCONSPROP FALSE |
whether to use SOS1 constraint propagation
Definition at line 117 of file cons_sos1.c.
| #define DEFAULT_BRANCHSTRATEGIES "nbs" |
possible branching strategies (see parameter DEFAULT_BRANCHINGRULE)
Definition at line 120 of file cons_sos1.c.
| #define DEFAULT_BRANCHINGRULE 'n' |
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.
| #define DEFAULT_AUTOSOS1BRANCH TRUE |
if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap
Definition at line 124 of file cons_sos1.c.
| #define DEFAULT_FIXNONZERO FALSE |
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.
| #define DEFAULT_ADDCOMPS FALSE |
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.
| #define DEFAULT_MAXADDCOMPS -1 |
maximal number of complementarity constraints added per branching node (-1: no limit)
Definition at line 131 of file cons_sos1.c.
| #define DEFAULT_ADDCOMPSDEPTH 30 |
only add complementarity constraints to branching nodes for predefined depth (-1: no limit)
Definition at line 132 of file cons_sos1.c.
| #define DEFAULT_ADDCOMPSFEAS -0.6 |
minimal feasibility value for complementarity constraints in order to be added to the branching node
Definition at line 133 of file cons_sos1.c.
| #define DEFAULT_ADDBDSFEAS 1.0 |
minimal feasibility value for bound inequalities in order to be added to the branching node
Definition at line 134 of file cons_sos1.c.
| #define DEFAULT_ADDEXTENDEDBDS TRUE |
should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities
Definition at line 135 of file cons_sos1.c.
| #define DEFAULT_NSTRONGROUNDS 0 |
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.
| #define DEFAULT_NSTRONGITER 10000 |
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.
| #define DEFAULT_BOUNDCUTSFROMSOS1 FALSE |
if TRUE separate bound inequalities from SOS1 constraints
Definition at line 144 of file cons_sos1.c.
| #define DEFAULT_BOUNDCUTSFROMGRAPH TRUE |
if TRUE separate bound inequalities from the conflict graph
Definition at line 145 of file cons_sos1.c.
| #define DEFAULT_AUTOCUTSFROMSOS1 TRUE |
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.
| #define DEFAULT_BOUNDCUTSFREQ 10 |
frequency for separating bound cuts; zero means to separate only in the root node
Definition at line 147 of file cons_sos1.c.
| #define DEFAULT_BOUNDCUTSDEPTH 40 |
node depth of separating bound cuts (-1: no limit)
Definition at line 148 of file cons_sos1.c.
| #define DEFAULT_MAXBOUNDCUTS 50 |
maximal number of bound cuts separated per branching node
Definition at line 149 of file cons_sos1.c.
| #define DEFAULT_MAXBOUNDCUTSROOT 150 |
maximal number of bound cuts separated per iteration in the root node
Definition at line 150 of file cons_sos1.c.
| #define DEFAULT_STRTHENBOUNDCUTS TRUE |
if TRUE then bound cuts are strengthened in case bound variables are available
Definition at line 151 of file cons_sos1.c.
| #define DEFAULT_IMPLCUTSFREQ 0 |
frequency for separating implied bound cuts; zero means to separate only in the root node
Definition at line 152 of file cons_sos1.c.
| #define DEFAULT_IMPLCUTSDEPTH 40 |
node depth of separating implied bound cuts (-1: no limit)
Definition at line 153 of file cons_sos1.c.
| #define DEFAULT_MAXIMPLCUTS 50 |
maximal number of implied bound cuts separated per branching node
Definition at line 154 of file cons_sos1.c.
| #define DEFAULT_MAXIMPLCUTSROOT 150 |
maximal number of implied bound cuts separated per iteration in the root node
Definition at line 155 of file cons_sos1.c.
| #define EVENTHDLR_NAME "SOS1" |
Definition at line 158 of file cons_sos1.c.
| #define EVENTHDLR_DESC "bound change event handler for SOS1 constraints" |
Definition at line 159 of file cons_sos1.c.
| #define DIVINGCUTOFFVALUE 1e6 |
Definition at line 162 of file cons_sos1.c.
Referenced by getDiveBdChgsSOS1conflictgraph(), and getDiveBdChgsSOS1constraints().
| typedef struct SCIP_NodeData SCIP_NODEDATA |
Definition at line 192 of file cons_sos1.c.
| typedef struct SCIP_SuccData SCIP_SUCCDATA |
Definition at line 201 of file cons_sos1.c.
|
static |
returns whether two vertices are adjacent in the conflict graph
| adjacencymatrix | adjacency matrix of conflict graph (lower half) (or NULL if an adjacencymatrix is not at hand) |
| conflictgraph | conflict graph (or NULL if an adjacencymatrix is at hand) |
| vertex1 | first vertex |
| vertex2 | second vertex |
Definition at line 299 of file cons_sos1.c.
References FALSE, isViolatedSOS1(), SCIP_Bool, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPsortInt(), SCIPswapInts(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), computeVarsCoverSOS1(), enforceConflictgraph(), extensionOperatorSOS1(), getBoundConsFromVertices(), performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
|
static |
checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable
| scip | SCIP data structure |
| conflictgraph | conflict graph (or NULL if an adjacencymatrix is at hand) |
| node | node of variable in the conflict graph |
| sol | solution, or NULL to use current node's solution |
Definition at line 359 of file cons_sos1.c.
References FALSE, nodeGetSolvalBinaryBigMSOS1(), SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by getDiveBdChgsSOS1conflictgraph(), and isConnectedSOS1().
|
static |
returns solution value of imaginary binary big-M variable of a given node from the conflict graph
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| sol | primal solution, or NULL for current LP/pseudo solution |
| node | node of the conflict graph |
Definition at line 404 of file cons_sos1.c.
References bound, nodeGetSolvalVarboundLbSOS1(), SCIP_Real, SCIPdigraphGetNNodes(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by computeVarsCoverSOS1(), getBoundConsFromVertices(), and isViolatedSOS1().
|
static |
gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| sol | primal solution, or NULL for current LP/pseudo solution |
| node | node of the conflict graph |
Definition at line 454 of file cons_sos1.c.
References nodedata, nodeGetSolvalVarboundUbSOS1(), SCIP_Real, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetLbLocal().
Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalBinaryBigMSOS1(), and updateWeightsTCliquegraph().
|
static |
gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| sol | primal solution, or NULL for current LP/pseudo solution |
| node | node of the conflict graph |
Definition at line 481 of file cons_sos1.c.
References nodedata, SCIP_Bool, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), SCIPvarGetUbLocal(), and varIsSOS1().
Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalVarboundLbSOS1(), and updateWeightsTCliquegraph().
|
static |
returns whether variable is part of the SOS1 conflict graph
| conshdlrdata | SOS1 constraint handler |
| var | variable |
Definition at line 508 of file cons_sos1.c.
Referenced by checkLinearConssVarboundSOS1(), and nodeGetSolvalVarboundUbSOS1().
|
static |
returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph
| conshdlrdata | SOS1 constraint handler |
| var | variable |
Definition at line 525 of file cons_sos1.c.
Referenced by checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), detectVarboundSOS1(), enforceConflictgraph(), genConflictgraphLinearCons(), generateBoundInequalityFromSOS1Cons(), getSOS1Implications(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
|
static |
fix variable in given node to 0 or add constraint if variable is multi-aggregated
| scip | SCIP pointer |
| var | variable to be fixed to 0 |
| node | node |
| infeasible | if fixing is infeasible |
Definition at line 546 of file cons_sos1.c.
References FALSE, fixVariableZero(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), enforceConssSOS1(), and getBranchingDecisionStrongbranchSOS1().
|
static |
try to fix variable to 0
Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
\[ x = \sum_{i=1}^n \alpha_i x_i + c, \]
we can express the fixing \(x = 0\) by fixing all \(x_i\) to 0 if \(c = 0\) and the lower bounds of \(x_i\) are nonnegative if \(\alpha_i > 0\) or the upper bounds are nonpositive if \(\alpha_i < 0\).
| scip | SCIP pointer |
| var | variable to be fixed to 0 |
| infeasible | if fixing is infeasible |
| tightened | if fixing was performed |
Definition at line 601 of file cons_sos1.c.
References FALSE, inferVariableZero(), 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().
|
static |
fix variable in local node to 0, and return whether the operation was feasible
| scip | SCIP pointer |
| var | variable to be fixed to 0 |
| cons | constraint |
| inferinfo | info for reverse prop. |
| infeasible | if fixing is infeasible |
| tightened | if fixing was performed |
| success | whether fixing was successful, i.e., variable is not multi-aggregated |
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().
|
static |
add lock on variable
| scip | SCIP data structure |
| cons | constraint |
| var | variable |
Definition at line 718 of file cons_sos1.c.
Referenced by handleNewVariableSOS1(), inferVariableZero(), and presolRoundConsSOS1().
|
static |
remove lock on variable
| scip | SCIP data structure |
| cons | constraint |
| var | variable |
Definition at line 737 of file cons_sos1.c.
Referenced by deleteVarSOS1(), and presolRoundConsSOS1().
|
static |
ensures that the vars and weights array can store at least num entries
| scip | SCIP data structure |
| consdata | constraint data |
| num | minimum number of entries to store |
| reserveWeights | whether the weights array is handled |
Definition at line 756 of file cons_sos1.c.
References handleNewVariableSOS1(), SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addVarSOS1(), and appendVarSOS1().
|
static |
handle new variable
| scip | SCIP data structure |
| cons | constraint |
| consdata | constraint data |
| conshdlrdata | constraint handler data |
| var | variable |
| transformed | whether original variable was transformed |
Definition at line 784 of file cons_sos1.c.
References addVarSOS1(), lockVariableSOS1(), SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPdebugMsg, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPsortInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().
Referenced by addVarSOS1(), appendVarSOS1(), consdataEnsurevarsSizeSOS1(), and SCIPcreateConsSOS1().
|
static |
adds a variable to an SOS1 constraint, at position given by weight - ascending order
| scip | SCIP data structure |
| cons | constraint |
| conshdlrdata | constraint handler data |
| var | variable to add to the constraint |
| weight | weight to determine position |
Definition at line 919 of file cons_sos1.c.
References appendVarSOS1(), consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), and SCIPaddVarSOS1().
|
static |
appends a variable to an SOS1 constraint
| scip | SCIP data structure |
| cons | constraint |
| conshdlrdata | constraint handler data |
| var | variable to add to the constraint |
Definition at line 989 of file cons_sos1.c.
References consdataEnsurevarsSizeSOS1(), deleteVarSOS1(), FALSE, handleNewVariableSOS1(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), and SCIPvarIsTransformed().
Referenced by addVarSOS1().
|
static |
deletes a variable of an SOS1 constraint
| scip | SCIP data structure |
| cons | constraint |
| consdata | constraint data |
| eventhdlr | corresponding event handler |
| pos | position of variable in array |
Definition at line 1035 of file cons_sos1.c.
References extensionOperatorSOS1(), SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1().
Referenced by appendVarSOS1(), and presolRoundConsSOS1().
|
static |
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
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| adjacencymatrix | adjacencymatrix of the conflict graph (only lower half filled) |
| vertexcliquegraph | graph that contains the information which cliques contain a given vertex vertices of variables = 0, ..., nsos1vars-1; vertices of cliques = nsos1vars, ..., nsos1vars+ncliques-1 |
| nsos1vars | number of SOS1 variables |
| nconss | number of SOS1 constraints |
| cons | constraint to be extended |
| vars | variables of extended clique |
| weights | weights of extended clique |
| firstcall | whether this is the first call of extension operator |
| usebacktrack | whether backtracking is needed for the computation |
| cliques | all cliques found so far |
| ncliques | number of clique found so far |
| cliquesizes | number of variables of current clique |
| newclique | clique we want to extended |
| workingset | set of vertices that already served as extension and set of candidates that probably will lead to an extension |
| nworkingset | length of array workingset |
| nexts | number of vertices that already served as extension |
| pos | position of potential candidate |
| maxextensions | maximal number of extensions |
| naddconss | number of added constraints |
| success | pointer to store if at least one new clique was found |
Definition at line 1074 of file cons_sos1.c.
References FALSE, genConflictgraphLinearCons(), isConnectedSOS1(), MAX, 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().
|
static |
generates conflict graph that is induced by the variables of a linear constraint
| conshdlrdata | constraint handler data |
| conflictgraphlin | conflict graph of linear constraint (nodes: 1, ..., nlinvars) |
| conflictgraphorig | original conflict graph (nodes: 1, ..., nsos1vars) |
| linvars | linear variables in linear constraint |
| nlinvars | number of linear variables in linear constraint |
| posinlinvars | posinlinvars[i] = position (index) of SOS1 variable i in linear constraint, posinlinvars[i]= -1 if i is not a SOS1 variable or not a variable of the linear constraint |
Definition at line 1336 of file cons_sos1.c.
References cliqueGetCommonSuccessorsSOS1(), SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().
Referenced by extensionOperatorSOS1(), and tightenVarsBoundsSOS1().
|
static |
determine the common successors of the vertices from the considered clique
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| clique | current clique |
| vars | clique variables |
| nvars | number of clique variables |
| comsucc | pointer to store common successors of clique vertices (size = nvars) |
| ncomsucc | pointer to store number common successors of clique vertices |
Definition at line 1389 of file cons_sos1.c.
References getSOS1Implications(), SCIP_INVALIDDATA, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().
Referenced by genConflictgraphLinearCons(), and presolRoundConssSOS1().
|
static |
get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| vars | problem and SOS1 variables |
| implgraph | implication graph (j is successor of i if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)) |
| implhash | hash map from variable to node in implication graph |
| implnodes | implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero |
| node | node of the implication graph |
Definition at line 1490 of file cons_sos1.c.
References presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, and varGetNodeSOS1().
Referenced by cliqueGetCommonSuccessorsSOS1(), and tightenVarsBoundsSOS1().
|
static |
perform one presolving round for a single SOS1 constraint
We perform the following presolving steps.
| scip | SCIP pointer |
| cons | constraint |
| consdata | constraint data |
| eventhdlr | event handler |
| substituted | whether a variable was substituted |
| cutoff | whether a cutoff happened |
| success | whether we performed a successful reduction |
| ndelconss | number of deleted constraints |
| nupgdconss | number of upgraded constraints |
| nfixedvars | number of fixed variables |
| nremovedvars | number of variables removed |
Definition at line 1556 of file cons_sos1.c.
References deleteVarSOS1(), FALSE, fixVariableZero(), lockVariableSOS1(), 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(), SCIPdebugMsg, SCIPdelCons(), SCIPdropVarEvent(), SCIPfindConshdlr(), SCIPfixVar(), SCIPgetProbvarSum(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, and unlockVariableSOS1().
Referenced by getSOS1Implications(), and presolRoundConssSOS1().
|
static |
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
| scip | SCIP pointer |
| eventhdlr | event handler |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| adjacencymatrix | adjacency matrix of conflict graph (or NULL) |
| conss | SOS1 constraints |
| nconss | number of SOS1 constraints |
| nsos1vars | number of SOS1 variables |
| naddconss | number of added constraints |
| ndelconss | number of deleted constraints |
| nupgdconss | number of upgraded constraints |
| nfixedvars | number of fixed variables |
| nremovedvars | number of variables removed |
| result | result |
Definition at line 1780 of file cons_sos1.c.
References cliqueGetCommonSuccessorsSOS1(), extensionOperatorSOS1(), FALSE, MAX, performImplicationGraphAnalysis(), presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPcomputeArraysIntersection(), SCIPconsGetData(), SCIPconsIsModifiable(), SCIPcreateDigraph(), SCIPdelCons(), SCIPdigraphAddArcSafe(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownIntInt(), SCIPsortInt(), TRUE, and varGetNodeSOS1().
Referenced by presolRoundConsSOS1().
|
static |
performs implication graph analysis
Tentatively fixes a variable to nonzeero and extracts consequences from it:
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| totalvars | problem and SOS1 variables |
| implgraph | implication graph (j is successor of i if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)) |
| implhash | hash map from variable to node in implication graph |
| adjacencymatrix | adjacencymatrix of the conflict graph (only lower half filled) |
| givennode | node of the conflict graph |
| nonznode | node of the conflict graph that is implied to be nonzero if given node is nonzero |
| impllbs | current lower variable bounds if given node is nonzero (update possible) |
| implubs | current upper variable bounds if given node is nonzero (update possible) |
| implnodes | indicates which variables are currently implied to be nonzero if given node is nonzero (update possible) |
| naddconss | pointer to store number of added SOS1 constraints |
| probingdepth | pointer to store current probing depth |
| infeasible | pointer to store whether the subproblem gets infeasible if variable to 'nonznode' is nonzero |
Definition at line 2049 of file cons_sos1.c.
References addVarSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPgetDepth(), SCIPhashmapGetImage(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), SCIPvarGetName(), TRUE, and varGetNodeSOS1().
Referenced by presolRoundConssSOS1(), and presolRoundVarsSOS1().
|
static |
returns whether node is implied to be zero; this information is taken from the input array 'implnodes'
| conflictgraph | conflict graph |
| implnodes | implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero |
| node | node of the conflict graph (or -1) |
Definition at line 2207 of file cons_sos1.c.
Referenced by performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
|
static |
updates arc data of implication graph
| scip | SCIP pointer |
| implgraph | implication graph |
| implhash | hash map from variable to node in implication graph |
| totalvars | problem and SOS1 variables |
| varv | variable that is assumed to be nonzero |
| varw | implication variable |
| lb | old lower bound of \(x_w\) |
| ub | old upper bound of \(x_w\) |
| newbound | new bound of \(x_w\) |
| lower | whether to consider lower bound implication (otherwise upper bound) |
| nchgbds | pointer to store number of changed bounds |
| update | pointer to store whether implication graph has been updated |
| infeasible | pointer to store whether an infeasibility has been detected |
Definition at line 2236 of file cons_sos1.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPceil(), SCIPdebugMsg, SCIPdigraphAddArc(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfloor(), SCIPhashmapGetImage(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), SCIPvarIsIntegral(), TRUE, and updateImplicationGraphSOS1().
Referenced by updateImplicationGraphSOS1().
|
static |
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
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| adjacencymatrix | adjacency matrix of conflict graph (lower half) |
| implgraph | implication graph (j is successor of i if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)) |
| implhash | hash map from variable to node in implication graph |
| implnodes | implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero |
| totalvars | problem and SOS1 variables |
| cliquecovers | clique covers of linear constraint |
| cliquecoversizes | size of clique covers |
| varincover | array with varincover[i] = cover of SOS1 index i |
| vars | variables to be checked |
| coefs | coefficients of variables in linear constraint |
| nvars | number of variables to be checked |
| bounds | bounds of variables |
| var | variable that is assumed to be nonzero |
| bound | bound of variable |
| boundnonzero | bound of variable if it is known to be nonzero if infinity values are not summarized |
| ninftynonzero | number of times infinity/-infinity has to be summarized to boundnonzero |
| lower | TRUE if lower bounds are consideres; FALSE for upper bounds |
| nchgbds | pointer to store number of changed bounds |
| update | pointer to store whether implication graph has been updated |
| infeasible | pointer to store whether an infeasibility has been detected |
Definition at line 2362 of file cons_sos1.c.
References bound, computeVarsCoverSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), 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().
|
static |
search new disjoint clique that covers given node
For a given vertex v search for a clique of the conflict graph induced by the variables of a linear constraint that
v and| scip | SCIP pointer |
| conflictgraphroot | conflict graph of the root node (nodes: 1, ..., nsos1vars) |
| conflictgraphlin | conflict graph of linear constraint (nodes: 1, ..., nlinvars) |
| linvars | variables in linear constraint |
| coveredvars | states which variables of the linear constraint are currently covered by a clique |
| clique | array to store new clique in cover |
| cliquesize | pointer to store the size of clique |
| v | position of variable in linear constraint that should be covered |
| considersolvals | TRUE if largest auxiliary bigM values of variables should be prefered |
Definition at line 2521 of file cons_sos1.c.
References isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasLT(), tightenVarsBoundsSOS1(), and TRUE.
Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
|
static |
try to tighten upper and lower bounds for variables
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| implgraph | implication graph (j is successor of i if and only if \( x_i\not = 0 \) implies a new lower/upper bound for \( x_j\)) |
| implhash | hash map from variable to node in implication graph |
| adjacencymatrix | adjacencymatrix of conflict graph |
| totalvars | problem and SOS1 vars |
| ntotalvars | number of problem and SOS1 variables |
| nsos1vars | number of SOS1 variables |
| nchgbds | pointer to store number of changed bounds |
| implupdate | pointer to store whether the implication graph has been updated in this function call |
| cutoff | pointer to store if current nodes LP is infeasible |
Definition at line 2632 of file cons_sos1.c.
References computeVarsCoverSOS1(), FALSE, genConflictgraphLinearCons(), getSOS1Implications(), isConnectedSOS1(), isImpliedZero(), MAX, presolRoundVarsSOS1(), REALABS, scalars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPallocBufferArray, SCIPceil(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateDigraph(), SCIPdebugMsg, 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(), 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().
|
static |
perform one presolving round for variables
We perform the following presolving steps:
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| adjacencymatrix | adjacencymatrix of conflict graph |
| nsos1vars | number of SOS1 variables |
| nfixedvars | pointer to store number of fixed variables |
| nchgbds | pointer to store number of changed bounds |
| naddconss | pointer to store number of addded constraints |
| result | result |
Definition at line 3356 of file cons_sos1.c.
References FALSE, performImplicationGraphAnalysis(), propConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPblkmem(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfixVar(), SCIPfreeBlockMemory, SCIPfreeBufferArrayNull, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenVarsBoundsSOS1(), and TRUE.
Referenced by tightenVarsBoundsSOS1().
|
static |
propagate variables of SOS1 constraint
| scip | SCIP pointer |
| cons | constraint |
| consdata | constraint data |
| cutoff | whether a cutoff happened |
| ngen | number of domain changes |
Definition at line 3530 of file cons_sos1.c.
References FALSE, inferVariableZero(), propVariableNonzero(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by enforceConflictgraph(), enforceConssSOS1(), and presolRoundVarsSOS1().
|
static |
propagate a variable that is known to be nonzero
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| implgraph | implication graph |
| cons | some arbitrary SOS1 constraint |
| node | conflict graph node of variable that is known to be nonzero |
| implprop | whether implication graph propagation shall be applied |
| cutoff | whether a cutoff happened |
| ngen | number of domain changes |
Definition at line 3628 of file cons_sos1.c.
References FALSE, inferVariableZero(), initImplGraphSOS1(), nodedata, 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().
|
static |
initialize implication graph
j is successor of i if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| nsos1vars | number of SOS1 variables |
| maxrounds | maximal number of propagation rounds for generating implications |
| nchgbds | pointer to store number of bound changes |
| cutoff | pointer to store whether a cutoff occurred |
| success | whether initialization was successful |
Definition at line 3772 of file cons_sos1.c.
References FALSE, freeImplGraphSOS1(), nodedata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPnodeGetVarSOS1(), tightenVarsBoundsSOS1(), and TRUE.
Referenced by propVariableNonzero(), and sepaImplBoundCutsSOS1().
|
static |
deinitialize implication graph
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
Definition at line 3943 of file cons_sos1.c.
Referenced by initImplGraphSOS1().
|
static |
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.
| conflictgraph | conflict graph |
| verticesarefixed | array that indicates which variables are currently fixed to zero |
| vertex | vertex (-1 if not needed) |
| neightocover | neighbors of given vertex to be covered (or NULL if all neighbors shall be covered) |
| nneightocover | number of entries of neightocover (or 0 if all neighbors shall be covered ) |
| coververtices | array to store the vertices whose neighbor set covers the neighbor set of the given vertex |
| ncoververtices | pointer to store size of coververtices |
Definition at line 4002 of file cons_sos1.c.
References getBranchingVerticesSOS1(), SCIP_Bool, SCIP_OKAY, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().
Referenced by addBranchingComplementaritiesSOS1(), and getBranchingVerticesSOS1().
|
static |
get vertices of variables that will be fixed to zero for each node
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| sol | solution to be enforced (NULL for LP solution) |
| verticesarefixed | vector that indicates which variables are currently fixed to zero |
| bipbranch | TRUE if bipartite branching method should be used |
| branchvertex | branching vertex |
| fixingsnode1 | vertices of variables that will be fixed to zero for the first node |
| nfixingsnode1 | pointer to store number of fixed variables for the first node |
| fixingsnode2 | vertices of variables that will be fixed to zero for the second node |
| nfixingsnode2 | pointer to store number of fixed variables for the second node |
Definition at line 4109 of file cons_sos1.c.
References FALSE, getBranchingPrioritiesSOS1(), getCoverVertices(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and TRUE.
Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), and getCoverVertices().
|
static |
gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| sol | solution to be enforced (NULL for LP solution) |
| nsos1vars | number of SOS1 variables |
| verticesarefixed | vector that indicates which variables are currently fixed to zero |
| bipbranch | TRUE if bipartite branching method should be used |
| fixingsnode1 | vertices of variables that will be fixed to zero for the first node (size = nsos1vars) |
| fixingsnode2 | vertices of variables that will be fixed to zero for the second node (size = nsos1vars) |
| branchpriors | pointer to store branching priorities (size = nsos1vars) or NULL if not needed |
| vertexbestprior | pointer to store vertex with the best branching priority or NULL if not needed |
| relsolfeas | pointer to store if LP relaxation solution is feasible |
Definition at line 4222 of file cons_sos1.c.
References FALSE, getBranchingVerticesSOS1(), performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), and TRUE.
Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), and getBranchingVerticesSOS1().
|
static |
performs strong branching with given domain fixings
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| fixingsexec | vertices of variables to be fixed to zero for this strong branching execution |
| nfixingsexec | number of vertices of variables to be fixed to zero for this strong branching execution |
| fixingsop | vertices of variables to be fixed to zero for the opposite strong branching execution |
| nfixingsop | number of vertices of variables to be fixed to zero for the opposite strong branching execution |
| inititer | maximal number of LP iterations to perform |
| fixnonzero | shall opposite variable (if positive in sign) fixed to the feasibility tolerance (only possible if nfixingsop = 1) |
| domainfixings | vertices that can be used to reduce the domain (should have size equal to number of variables) |
| ndomainfixings | pointer to store number of vertices that can be used to reduce the domain, could be filled by earlier calls |
| infeasible | pointer to store whether branch is infeasible |
| objval | pointer to store objective value of LP with fixed variables (SCIP_INVALID if reddomain = TRUE or lperror = TRUE) |
| lperror | pointer to store whether an unresolved LP error or a strange solution status occurred |
Definition at line 4324 of file cons_sos1.c.
References FALSE, getBranchingDecisionStrongbranchSOS1(), 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().
|
static |
apply strong branching to determine the vertex for the next branching decision
| scip | SCIP pointer |
| conshdlrdata | SOS1 constraint handler data |
| conflictgraph | conflict graph |
| sol | solution to be enforced (NULL for LP solution) |
| nsos1vars | number of SOS1 variables |
| lpobjval | current LP relaxation solution |
| bipbranch | TRUE if bipartite branching method should be used |
| nstrongrounds | number of strong branching rounds |
| verticesarefixed | vector that indicates which variables are currently fixed to zero |
| fixingsnode1 | pointer to store vertices of variables that will be fixed to zero for the first node (size = nsos1vars) |
| fixingsnode2 | pointer to store vertices of variables that will be fixed to zero for the second node (size = nsos1vars) |
| vertexbestprior | pointer to store vertex with the best strong branching priority |
| bestobjval1 | pointer to store LP objective for left child node of branching decision with best priority |
| bestobjval2 | pointer to store LP objective for right child node of branching decision with best priority |
| result | pointer to store result of strong branching |
Definition at line 4466 of file cons_sos1.c.
References FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), MAX, performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPallocBufferArray, SCIPdebugMsg, SCIPfeastol(), SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPgetLPObjval(), SCIPgetNDualResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNNodeInitLPIterations(), SCIPgetNNodeInitLPs(), SCIPgetNNodes(), SCIPinfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), and SCIPsortDownRealInt().
Referenced by enforceConflictgraph(), and performStrongbranchSOS1().
|
static |
for two given vertices v1 and v2 search for a clique in the conflict graph that contains these vertices. From this clique, we create a bound constraint.
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| sol | solution to be enforced (NULL for LP solution) |
| v1 | first vertex that shall be contained in bound constraint |
| v2 | second vertex that shall be contained in bound constraint |
| boundvar | bound variable of v1 and v2 (or NULL if not existent) |
| extend | should v1 and v2 be greedily extended to a clique of larger size |
| cons | bound constraint |
| feas | feasibility value of bound constraint |
Definition at line 4680 of file cons_sos1.c.
References addBranchingComplementaritiesSOS1(), FALSE, isConnectedSOS1(), nodedata, nodeGetSolvalBinaryBigMSOS1(), 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().
|
static |
tries to add feasible complementarity constraints to a given child branching node.
| scip | SCIP pointer |
| node | branching node |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph of the current node |
| localconflicts | local conflicts (updates to local conflicts of child node) |
| sol | solution to be enforced (NULL for LP solution) |
| nsos1vars | number of SOS1 variables |
| verticesarefixed | vector that indicates which variables are currently fixed to zerox |
| fixingsnode1 | vertices of variables that will be fixed to zero for the branching node in the input of this function |
| nfixingsnode1 | number of entries of array nfixingsnode1 |
| fixingsnode2 | vertices of variables that will be fixed to zero for the other branching node |
| nfixingsnode2 | number of entries of array nfixingsnode2 |
| naddedconss | pointer to store the number of added SOS1 constraints |
| onlyviolsos1 | should only SOS1 constraints be added that are violated by the LP solution |
Definition at line 4908 of file cons_sos1.c.
References addVarSOS1(), FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getCoverVertices(), isConnectedSOS1(), nodedata, resetConflictgraphSOS1(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPblkmem(), 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().
|
static |
resets local conflict graph to the conflict graph of the root node
| conflictgraph | conflict graph of root node |
| localconflicts | local conflicts that should be removed from conflict graph |
| nsos1vars | number of SOS1 variables |
Definition at line 5273 of file cons_sos1.c.
References enforceConflictgraph(), SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminus(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors().
Referenced by addBranchingComplementaritiesSOS1(), and enforceConflictgraph().
|
static |
Conflict graph enforcement method
The conflict graph can be enforced by different branching rules:
i, i.e., in one branch \(x_i\) is fixed to zero and in the other its neighbors from the conflict graph.We make use of different selection rules that define on which system of SOS1 variables to branch next:
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conshdlr | constraint handler |
| nconss | number of constraints |
| conss | SOS1 constraints |
| sol | solution to be enforced (NULL for LP solution) |
| result | result |
Definition at line 5329 of file cons_sos1.c.
References addBranchingComplementaritiesSOS1(), enforceConssSOS1(), FALSE, fixVariableZeroNode(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), isConnectedSOS1(), log(), MAX, pow(), propConsSOS1(), resetConflictgraphSOS1(), SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VARSTATUS_MULTAGGR, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMsg, 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 enforceSOS1(), and resetConflictgraphSOS1().
|
static |
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 \(W = \sum_{j=1}^n |x_i|\) and \(w = \sum_{j=1}^n j\, |x_i|\). Then we search for the index \(k\) that satisfies
\[ k \leq \frac{w}{W} < k+1. \]
The branches are then
\[ x_1 = 0, \ldots, x_k = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0. \]
If the constraint contains two variables, the branching of course simplifies.
Depending on the parameters (branchnonzeros, branchweight) there are three ways to choose the branching constraint.
branchnonzeros | branchweight | constraint chosen |
true | ? | most number of nonzeros |
false | true | maximal weight corresponding to nonzero variable |
false | true | largest sum of variable values |
branchnonzeros = false, branchweight = true allows the user to specify an order for the branching importance of the constraints (setting the weights accordingly).
Constraint branching can also be turned off using parameter branchsos.
| scip | SCIP pointer |
| conshdlr | constraint handler |
| nconss | number of constraints |
| conss | indicator constraints |
| sol | solution to be enforced (NULL for LP solution) |
| result | result |
Definition at line 5791 of file cons_sos1.c.
References branchCons(), enforceSOS1(), fixVariableZeroNode(), 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(), SCIPdebugMsg, SCIPerrorMessage, SCIPfloor(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetName(), and SCIPvarIsBinary().
Referenced by enforceConflictgraph(), and enforceSOS1().
|
static |
constraint enforcing method of constraint handler
| scip | SCIP pointer |
| conshdlr | constraint handler |
| nconss | number of constraints |
| conss | indicator constraints |
| sol | solution to be enforced (NULL for LP solution) |
| result | result |
Definition at line 6037 of file cons_sos1.c.
References enforceConflictgraph(), enforceConssSOS1(), initTCliquegraph(), SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIPconshdlrGetData(), and SCIPerrorMessage.
Referenced by enforceConssSOS1().
|
static |
initialitze tclique graph and create clique data
| scip | SCIP pointer |
| conshdlr | constraint handler |
| conshdlrdata | constraint handler data |
| conflictgraph | conflict graph |
| nsos1vars | number of SOS1 variables |
Definition at line 6100 of file cons_sos1.c.
References TCLIQUE_Data::conflictgraph, TCLIQUE_Data::conshdlr, TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, TCLIQUE_Data::scaleval, TCLIQUE_Data::scip, SCIP_CALL, SCIP_NOMEMORY, SCIP_OKAY, SCIPallocBlockMemory, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPnodeGetVarSOS1(), SCIPvarIsActive(), TCLIQUE_Data::sol, TCLIQUE_Data::strthenboundcuts, tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), tcliqueFlush(), and updateWeightsTCliquegraph().
Referenced by enforceSOS1().
|
static |
update weights of tclique graph
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| tcliquedata | tclique data |
| conflictgraph | conflict graph |
| sol | LP solution to be separated (or NULL) |
| nsos1vars | number of SOS1 variables |
Definition at line 6169 of file cons_sos1.c.
References addBoundCutSepa(), bound, 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().
|
static |
adds bound cut(s) to separation storage
| scip | SCIP pointer |
| tcliquedata | clique data |
| rowlb | row for lower bounds (or NULL) |
| rowub | row for upper bounds (or NULL) |
| success | pointer to store if bound cut was added |
| cutoff | pointer to store if a cutoff occurred |
Definition at line 6229 of file cons_sos1.c.
References FALSE, generateBoundInequalityFromSOS1Nodes(), TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPdebug, SCIPisCutEfficacious(), SCIPprintRow(), SCIProwIsInLP(), and TRUE.
Referenced by updateWeightsTCliquegraph().
|
static |
Generate bound constraint
We generate the row corresponding to the following simple valid inequalities:
\[ \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, \]
where \(\ell_1, \ldots, \ell_n\) and \(u_1, \ldots, u_n\) are the nonzero and finite lower and upper bounds of the variables \(x_1, \ldots, x_n\). 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 \(\ell_1, \ldots, \ell_n\) are all negative, which results in the \(\leq\) inequality. In case of the presence of variable upper bounds, the bound inequality can be further strengthened.
Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most interesting.
| scip | SCIP pointer |
| conshdlr | constraint handler |
| conflictgraph | conflict graph |
| nodes | conflict graph nodes for bound constraint |
| nnodes | number of conflict graph nodes for bound constraint |
| rhs | right hand side of bound constraint |
| local | in any case produce a local cut (even if local bounds of variables are valid globally) |
| global | in any case produce a global cut |
| strengthen | whether trying to strengthen bound constraint |
| removable | should the inequality be removed from the LP due to aging or cleanup? |
| nameext | part of name of bound constraints |
| rowlb | output: row for lower bounds (or NULL if not needed) |
| rowub | output: row for upper bounds (or NULL if not needed) |
Definition at line 6303 of file cons_sos1.c.
References FALSE, nnodes, nodedata, 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().
|
static |
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 6595 of file cons_sos1.c.
Referenced by generateBoundInequalityFromSOS1Nodes().
|
static |
separate bound inequalities from conflict graph
| scip | SCIP pointer |
| conshdlr | constraint handler |
| conshdlrdata | constraint handler data |
| sol | LP solution to be separated (or NULL) |
| maxboundcuts | maximal number of bound cuts separated per separation round (-1: no limit) |
| ngen | pointer to store number of cuts generated |
| cutoff | pointer whether a cutoff occurred |
Definition at line 6730 of file cons_sos1.c.
References TCLIQUE_Data::cutoff, FALSE, generateBoundInequalityFromSOS1Cons(), TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), TCLIQUE_Data::sol, tcliqueMaxClique(), and updateWeightsTCliquegraph().
Referenced by separateSOS1().
|
static |
Generate a bound constraint from the variables of an SOS1 constraint (see generateBoundInequalityFromSOS1Nodes() for more information)
| scip | SCIP pointer |
| conshdlr | constraint handler |
| cons | SOS1 constraint |
| local | in any case produce a local cut (even if local bounds of variables are valid globally) |
| global | in any case produce a global cut |
| strengthen | whether trying to strengthen bound constraint |
| removable | should the inequality be removed from the LP due to aging or cleanup? |
| rowlb | output: row for lower bounds (or NULL if not needed) |
| rowub | output: row for upper bounds (or NULL if not needed) |
Definition at line 6804 of file cons_sos1.c.
References CONSHDLR_NAME, generateBoundInequalityFromSOS1Nodes(), initsepaBoundInequalityFromSOS1Cons(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varGetNodeSOS1().
Referenced by initsepaBoundInequalityFromSOS1Cons(), and sepaBoundInequalitiesFromGraph().
|
static |
initialize or separate bound inequalities from SOS1 constraints
| scip | SCIP pointer |
| conshdlr | constraint handler |
| conshdlrdata | constraint handler data |
| conss | SOS1 constraints |
| nconss | number of SOS1 constraints |
| sol | LP solution to be separated (or NULL) |
| solvedinitlp | TRUE if initial LP relaxation at a node is solved |
| maxboundcuts | maximal number of bound cuts separated per separation round (-1: no limit) |
| ngen | pointer to store number of cuts generated (or NULL) |
| cutoff | pointer to store whether a cutoff occurred |
Definition at line 6867 of file cons_sos1.c.
References FALSE, generateBoundInequalityFromSOS1Cons(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMsg, SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIProwIsInLP(), sepaImplBoundCutsSOS1(), and TRUE.
Referenced by generateBoundInequalityFromSOS1Cons(), and separateSOS1().
|
static |
separate implied bound cuts
| scip | SCIP pointer |
| conshdlr | constraint handler |
| conshdlrdata | constraint handler data |
| sol | LP solution to be separated (or NULL) |
| maxcuts | maximal number of implied bound cuts separated per separation round (-1: no limit) |
| ngen | pointer to store number of cuts generated |
| cutoff | pointer whether a cutoff occurred |
Definition at line 6981 of file cons_sos1.c.
References FALSE, initImplGraphSOS1(), nodedata, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPdebugMsg, 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().
|
static |
separates SOS1 constraints for arbitrary solutions
| scip | SCIP pointer |
| conshdlr | constraint handler |
| sol | solution to be separated (or NULL) |
| nconss | number of constraints |
| conss | SOS1 constraints |
| result | result |
Definition at line 7206 of file cons_sos1.c.
References getVectorOfWeights(), initsepaBoundInequalityFromSOS1Cons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPgetDepth(), SCIPisStopped(), sepaBoundInequalitiesFromGraph(), sepaImplBoundCutsSOS1(), and TRUE.
Referenced by sepaImplBoundCutsSOS1().
|
static |
gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem
| scip | SCIP pointer |
| sol | primal solution or NULL for current LP solution |
| conflictgraph | conflict graph |
| nsos1vars | number of SOS1 variables |
| indicatorzero | vector that indicates which variables are currently fixed to zero |
| weights | pointer to store weights determining the order of the variables (length = nsos1vars) |
Definition at line 7327 of file cons_sos1.c.
References markNeighborsMWISHeuristic(), REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and SCIPsumepsilon().
Referenced by maxWeightIndSetHeuristic(), and separateSOS1().
|
static |
| scip | SCIP pointer |
| conshdlr | SOS1 constraint handler |
| conflictgraph | conflict graph |
| node | node of the conflict graph |
| mark | indicator vector of processed nodes |
| indset | indicator vector of current independent |
| cnt | pointer to store number of marked nodes |
| cutoff | pointer to store whether operation is infeasible |
Definition at line 7398 of file cons_sos1.c.
References FALSE, maxWeightIndSetHeuristic(), 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().
|
static |
calls greedy algorithm for the maximum weighted independent set problem (MWIS)
We compute a feasible solution to
\[ \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} \]
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 \(x^*\) denotes the current LP relaxation solution. Note that the solution of the MWIS is the indicator vector of an independent set.
| scip | SCIP pointer |
| sol | primal solution or NULL for current LP solution |
| conshdlr | SOS1 constraint handler |
| conflictgraph | conflict graph |
| nsos1vars | number of SOS1 variables |
| indicatorzero | vector that indicates which variables are currently fixed to zero |
| indset | pointer to store indicator vector of an independent set |
Definition at line 7539 of file cons_sos1.c.
References FALSE, getVectorOfWeights(), makeSOS1conflictgraphFeasible(), markNeighborsMWISHeuristic(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownRealInt(), and TRUE.
Referenced by makeSOS1conflictgraphFeasible(), and markNeighborsMWISHeuristic().
|
static |
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
| scip | SCIP pointer |
| conshdlr | SOS1 constraint handler |
| sol | solution |
| changed | pointer to store whether the solution has been changed |
| allroundable | pointer to store whether all variables are roundable |
Definition at line 7645 of file cons_sos1.c.
References FALSE, makeSOS1constraintsFeasible(), maxWeightIndSetHeuristic(), 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().
|
static |
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
| scip | SCIP pointer |
| conshdlr | SOS1 constraint handler |
| sol | solution |
| changed | pointer to store whether the solution has been changed |
| allroundable | pointer to store whether all variables are roundable |
Definition at line 7774 of file cons_sos1.c.
References FALSE, getDiveBdChgsSOS1conflictgraph(), 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().
|
static |
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
| scip | SCIP pointer |
| conshdlr | SOS1 constraint handler |
| diveset | diving settings |
| sol | solution |
| success | pointer to store |
Definition at line 7908 of file cons_sos1.c.
References bound, DIVINGCUTOFFVALUE, FALSE, getDiveBdChgsSOS1constraints(), isViolatedSOS1(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), 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().
|
static |
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)
| scip | SCIP pointer |
| conshdlr | SOS1 constraint handler |
| diveset | diving settings |
| sol | solution |
| success | pointer to store |
Definition at line 8049 of file cons_sos1.c.
References bound, detectVarboundSOS1(), DIVINGCUTOFFVALUE, FALSE, 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().
|
static |
check whether \(x_1\) is a bound variable of \(x_0\); i.e., \(x_0 \leq c\cdot x_1\) or \(x_0 \geq d\cdot x_1\) for positive values \(c, d\). If true, then add this information to the node data of the conflict graph.
| scip | SCIP pointer |
| conshdlrdata | SOS1 constraint handler data |
| var0 | first variable |
| var1 | second variable |
| val0 | first coefficient |
| val1 | second coefficient |
Definition at line 8230 of file cons_sos1.c.
References nodedata, passConComponentVarbound(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1().
Referenced by checkLinearConssVarboundSOS1(), and getDiveBdChgsSOS1constraints().
|
static |
pass connected component \(C\) of the conflict graph and check whether all the variables correspond to a unique variable upper bound variable \(z\), i.e., \(x_i \leq u_i z\) for every \(i\in C\).
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| node | current node of connected component |
| boundvar | bound variable of connected component |
| checklb | whether to check lower bound variable (else upper bound variable) |
| processed | states for each variable whether it has been processed |
| concomp | current connected component |
| nconcomp | pointer to store number of elements of connected component |
| unique | pointer to store whether bound variable is unique |
Definition at line 8306 of file cons_sos1.c.
References checkConComponentsVarbound(), FALSE, nodedata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE.
Referenced by checkConComponentsVarbound(), and detectVarboundSOS1().
|
static |
for each connected component \(C\) of the conflict graph check whether all the variables correspond to a unique variable upper bound variable \(z\) (e.g., for the upper bound case this means that \(x_i \leq u_i z\) for every \(i\in C\)).
| scip | SCIP pointer |
| conflictgraph | conflict graph |
| nsos1vars | number of SOS1 variables |
| checklb | whether to check lower bound variable (else check upper bound variable) |
Definition at line 8379 of file cons_sos1.c.
References checkLinearConssVarboundSOS1(), FALSE, nodedata, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, and TRUE.
Referenced by passConComponentVarbound().
|
static |
check all linear constraints for variable bound constraints of the form \(c\cdot z \leq x \leq d\cdot z\), where x is some SOS1 variable and z is some arbitrary variable (not necessarily binary)
| scip | SCIP pointer |
| conshdlrdata | SOS1 constraint handler data |
| linconss | linear constraints |
| nlinconss | number of linear constraints |
Definition at line 8468 of file cons_sos1.c.
References checkSwitchNonoverlappingSOS1Methods(), detectVarboundSOS1(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasZero(), and varIsSOS1().
Referenced by checkConComponentsVarbound().
|
static |
switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap
| scip | SCIP pointer |
| conshdlrdata | SOS1 constraint handler data |
| conflictgraph | conflict graph |
| conss | SOS1 constraints |
| nconss | number of SOS1 constraints |
Definition at line 8541 of file cons_sos1.c.
References computeNodeDataSOS1(), FALSE, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().
Referenced by checkLinearConssVarboundSOS1().
|
static |
sets node data of conflict graph nodes
| scip | SCIP pointer |
| conshdlrdata | SOS1 constraint handler data |
| nsos1vars | number of SOS1 variables |
Definition at line 8622 of file cons_sos1.c.
Referenced by checkSwitchNonoverlappingSOS1Methods().
|
static |
initialize conflictgraph and create hashmap for SOS1 variables
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
| conss | SOS1 constraints |
| nconss | number of SOS1 constraints |
Definition at line 8659 of file cons_sos1.c.
References FALSE, freeConflictgraph(), nodedata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPblkmem(), SCIPconsGetData(), SCIPdigraphAddArcSafe(), SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArray, SCIPgetNTotalVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisFeasZero(), SCIPsortInt(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
|
static |
free conflict graph, nodedata and hashmap
| scip | SCIP pointer |
| conshdlrdata | constraint handler data |
Definition at line 8854 of file cons_sos1.c.
References CONSHDLR_NAME, nodedata, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphSetNodeData(), SCIPfreeBlockMemory, and SCIPhashmapFree().
Referenced by initConflictgraph().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 8900 of file cons_sos1.c.
Referenced by freeConflictgraph().
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 8917 of file cons_sos1.c.
|
static |
solving process initialization method of constraint handler (called when branch and bound process is about to begin)
Definition at line 8939 of file cons_sos1.c.
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 8992 of file cons_sos1.c.
|
static |
frees specific constraint data
Definition at line 9064 of file cons_sos1.c.
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 9118 of file cons_sos1.c.
|
static |
presolving method of constraint handler
Definition at line 9210 of file cons_sos1.c.
|
static |
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 9337 of file cons_sos1.c.
|
static |
separation method of constraint handler for LP solutions
Definition at line 9362 of file cons_sos1.c.
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 9378 of file cons_sos1.c.
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 9394 of file cons_sos1.c.
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 9410 of file cons_sos1.c.
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 9426 of file cons_sos1.c.
|
static |
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 9445 of file cons_sos1.c.
|
static |
domain propagation method of constraint handler
Definition at line 9517 of file cons_sos1.c.
|
static |
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 9663 of file cons_sos1.c.
|
static |
variable rounding lock method of constraint handler
Let lb and ub be the lower and upper bounds of a variable. Preprocessing usually makes sure that lb <= 0 <= ub.
Definition at line 9739 of file cons_sos1.c.
|
static |
constraint display method of constraint handler
Definition at line 9783 of file cons_sos1.c.
|
static |
constraint copying method of constraint handler
Definition at line 9813 of file cons_sos1.c.
|
static |
constraint parsing method of constraint handler
Definition at line 9879 of file cons_sos1.c.
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 9943 of file cons_sos1.c.
References BMScopyMemoryArray, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 9966 of file cons_sos1.c.
Referenced by SCIP_DECL_CONSGETVARS().
|
static |
exec the event handler
We update the number of variables fixed to be nonzero
Definition at line 9987 of file cons_sos1.c.
|
static |
constraint handler method to determine a diving variable by assigning a variable and two values for diving
Definition at line 10084 of file cons_sos1.c.