SCIP
Solving Constraint Integer Programs
cons_sos1.c File Reference
Detailed Description
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:
- If the constraint is created with SCIPcreateConsSOS1() and weights are given, the weights determine the order (decreasing weights). Additional variables can be added with SCIPaddVarSOS1(), which adds a variable with given weight.
- If an empty constraint is created and then variables are added with SCIPaddVarSOS1(), weights are needed and stored.
- All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are added with SCIPappendVarSOS1().
The validity of the SOS1 constraints can be enforced by different branching rules:
- If classical SOS branching is used, branching is performed on only one SOS1 constraint. Depending on the parameters, there are two ways to choose this branching constraint. Either the constraint with the most number of nonzeros or the one with the largest nonzero-variable weight. The later version allows the user to specify an order for the branching importance of the constraints. Constraint branching can also be turned off.
- Another way is to branch on the neighborhood of a single variable
i, i.e., in one branch \(x_i\) is fixed to zero and in the other its neighbors from the conflict graph. - If bipartite branching is used, then we branch using complete bipartite subgraphs of the conflict graph, i.e., in one branch fix the variables from the first bipartite partition and the variables from the second bipartite partition in the other.
- In addition to variable domain fixings, it is sometimes also possible to add new SOS1 constraints to the branching nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.
Definition in file cons_sos1.c.
#include "blockmemshell/memory.h"#include "scip/cons_linear.h"#include "scip/cons_setppc.h"#include "scip/cons_sos1.h"#include "scip/pub_cons.h"#include "scip/pub_event.h"#include "scip/pub_heur.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_misc_sort.h"#include "scip/pub_tree.h"#include "scip/pub_var.h"#include "scip/scip_branch.h"#include "scip/scip_conflict.h"#include "scip/scip_cons.h"#include "scip/scip_copy.h"#include "scip/scip_cut.h"#include "scip/scip_datastructures.h"#include "scip/scip_event.h"#include "scip/scip_general.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_prob.h"#include "scip/scip_probing.h"#include "scip/scip_sol.h"#include "scip/scip_solvingstats.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"#include "tclique/tclique.h"Go to the source code of this file.
Data Structures | |
| struct | TCLIQUE_Data |
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) |
Macro Definition Documentation
◆ CONSHDLR_NAME
| #define CONSHDLR_NAME "SOS1" |
Definition at line 118 of file cons_sos1.c.
Referenced by freeConflictgraph(), generateBoundInequalityFromSOS1Cons(), SCIPaddVarSOS1(), SCIPcreateConsSOS1(), and SCIPmakeSOS1sFeasible().
◆ CONSHDLR_DESC
| #define CONSHDLR_DESC "SOS1 constraint handler" |
Definition at line 119 of file cons_sos1.c.
◆ CONSHDLR_SEPAPRIORITY
| #define CONSHDLR_SEPAPRIORITY 1000 |
priority of the constraint handler for separation
Definition at line 120 of file cons_sos1.c.
◆ CONSHDLR_ENFOPRIORITY
| #define CONSHDLR_ENFOPRIORITY 100 |
priority of the constraint handler for constraint enforcing
Definition at line 121 of file cons_sos1.c.
◆ CONSHDLR_CHECKPRIORITY
| #define CONSHDLR_CHECKPRIORITY -10 |
priority of the constraint handler for checking feasibility
Definition at line 122 of file cons_sos1.c.
◆ CONSHDLR_SEPAFREQ
| #define CONSHDLR_SEPAFREQ 10 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 123 of file cons_sos1.c.
◆ CONSHDLR_PROPFREQ
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 124 of file cons_sos1.c.
◆ CONSHDLR_EAGERFREQ
| #define CONSHDLR_EAGERFREQ 100 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 125 of file cons_sos1.c.
◆ CONSHDLR_MAXPREROUNDS
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 128 of file cons_sos1.c.
◆ CONSHDLR_DELAYSEPA
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 129 of file cons_sos1.c.
◆ CONSHDLR_DELAYPROP
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 130 of file cons_sos1.c.
◆ CONSHDLR_NEEDSCONS
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 131 of file cons_sos1.c.
◆ CONSHDLR_PROP_TIMING
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 132 of file cons_sos1.c.
◆ CONSHDLR_PRESOLTIMING
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM |
Definition at line 133 of file cons_sos1.c.
◆ DEFAULT_MAXSOSADJACENCY
| #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 136 of file cons_sos1.c.
◆ DEFAULT_MAXEXTENSIONS
| #define DEFAULT_MAXEXTENSIONS 1 |
maximal number of extensions that will be computed for each SOS1 constraint
Definition at line 141 of file cons_sos1.c.
◆ DEFAULT_MAXTIGHTENBDS
| #define DEFAULT_MAXTIGHTENBDS 5 |
maximal number of bound tightening rounds per presolving round (-1: no limit)
Definition at line 142 of file cons_sos1.c.
◆ DEFAULT_PERFIMPLANALYSIS
| #define DEFAULT_PERFIMPLANALYSIS FALSE |
if TRUE then perform implication graph analysis (might add additional SOS1 constraints)
Definition at line 143 of file cons_sos1.c.
◆ DEFAULT_DEPTHIMPLANALYSIS
| #define DEFAULT_DEPTHIMPLANALYSIS -1 |
number of recursive calls of implication graph analysis (-1: no limit)
Definition at line 144 of file cons_sos1.c.
◆ DEFAULT_CONFLICTPROP
| #define DEFAULT_CONFLICTPROP TRUE |
whether to use conflict graph propagation
Definition at line 147 of file cons_sos1.c.
◆ DEFAULT_IMPLPROP
| #define DEFAULT_IMPLPROP TRUE |
whether to use implication graph propagation
Definition at line 148 of file cons_sos1.c.
◆ DEFAULT_SOSCONSPROP
| #define DEFAULT_SOSCONSPROP FALSE |
whether to use SOS1 constraint propagation
Definition at line 149 of file cons_sos1.c.
◆ DEFAULT_BRANCHSTRATEGIES
| #define DEFAULT_BRANCHSTRATEGIES "nbs" |
possible branching strategies (see parameter DEFAULT_BRANCHINGRULE)
Definition at line 152 of file cons_sos1.c.
◆ DEFAULT_BRANCHINGRULE
| #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 153 of file cons_sos1.c.
◆ DEFAULT_AUTOSOS1BRANCH
| #define DEFAULT_AUTOSOS1BRANCH TRUE |
if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap
Definition at line 156 of file cons_sos1.c.
◆ DEFAULT_FIXNONZERO
| #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 157 of file cons_sos1.c.
◆ DEFAULT_ADDCOMPS
| #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 160 of file cons_sos1.c.
◆ DEFAULT_MAXADDCOMPS
| #define DEFAULT_MAXADDCOMPS -1 |
maximal number of complementarity constraints added per branching node (-1: no limit)
Definition at line 163 of file cons_sos1.c.
◆ DEFAULT_ADDCOMPSDEPTH
| #define DEFAULT_ADDCOMPSDEPTH 30 |
only add complementarity constraints to branching nodes for predefined depth (-1: no limit)
Definition at line 164 of file cons_sos1.c.
◆ DEFAULT_ADDCOMPSFEAS
| #define DEFAULT_ADDCOMPSFEAS -0.6 |
minimal feasibility value for complementarity constraints in order to be added to the branching node
Definition at line 165 of file cons_sos1.c.
◆ DEFAULT_ADDBDSFEAS
| #define DEFAULT_ADDBDSFEAS 1.0 |
minimal feasibility value for bound inequalities in order to be added to the branching node
Definition at line 166 of file cons_sos1.c.
◆ DEFAULT_ADDEXTENDEDBDS
| #define DEFAULT_ADDEXTENDEDBDS TRUE |
should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities
Definition at line 167 of file cons_sos1.c.
◆ DEFAULT_NSTRONGROUNDS
| #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 170 of file cons_sos1.c.
◆ DEFAULT_NSTRONGITER
| #define DEFAULT_NSTRONGITER 10000 |
maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit)
Definition at line 173 of file cons_sos1.c.
◆ DEFAULT_BOUNDCUTSFROMSOS1
| #define DEFAULT_BOUNDCUTSFROMSOS1 FALSE |
if TRUE separate bound inequalities from SOS1 constraints
Definition at line 176 of file cons_sos1.c.
◆ DEFAULT_BOUNDCUTSFROMGRAPH
| #define DEFAULT_BOUNDCUTSFROMGRAPH TRUE |
if TRUE separate bound inequalities from the conflict graph
Definition at line 177 of file cons_sos1.c.
◆ DEFAULT_AUTOCUTSFROMSOS1
| #define DEFAULT_AUTOCUTSFROMSOS1 TRUE |
if TRUE then automatically switch to separating from SOS1 constraints if the SOS1 constraints do not overlap
Definition at line 178 of file cons_sos1.c.
◆ DEFAULT_BOUNDCUTSFREQ
| #define DEFAULT_BOUNDCUTSFREQ 10 |
frequency for separating bound cuts; zero means to separate only in the root node
Definition at line 179 of file cons_sos1.c.
◆ DEFAULT_BOUNDCUTSDEPTH
| #define DEFAULT_BOUNDCUTSDEPTH 40 |
node depth of separating bound cuts (-1: no limit)
Definition at line 180 of file cons_sos1.c.
◆ DEFAULT_MAXBOUNDCUTS
| #define DEFAULT_MAXBOUNDCUTS 50 |
maximal number of bound cuts separated per branching node
Definition at line 181 of file cons_sos1.c.
◆ DEFAULT_MAXBOUNDCUTSROOT
| #define DEFAULT_MAXBOUNDCUTSROOT 150 |
maximal number of bound cuts separated per iteration in the root node
Definition at line 182 of file cons_sos1.c.
◆ DEFAULT_STRTHENBOUNDCUTS
| #define DEFAULT_STRTHENBOUNDCUTS TRUE |
if TRUE then bound cuts are strengthened in case bound variables are available
Definition at line 183 of file cons_sos1.c.
◆ DEFAULT_IMPLCUTSFREQ
| #define DEFAULT_IMPLCUTSFREQ 0 |
frequency for separating implied bound cuts; zero means to separate only in the root node
Definition at line 184 of file cons_sos1.c.
◆ DEFAULT_IMPLCUTSDEPTH
| #define DEFAULT_IMPLCUTSDEPTH 40 |
node depth of separating implied bound cuts (-1: no limit)
Definition at line 185 of file cons_sos1.c.
◆ DEFAULT_MAXIMPLCUTS
| #define DEFAULT_MAXIMPLCUTS 50 |
maximal number of implied bound cuts separated per branching node
Definition at line 186 of file cons_sos1.c.
◆ DEFAULT_MAXIMPLCUTSROOT
| #define DEFAULT_MAXIMPLCUTSROOT 150 |
maximal number of implied bound cuts separated per iteration in the root node
Definition at line 187 of file cons_sos1.c.
◆ EVENTHDLR_NAME
| #define EVENTHDLR_NAME "SOS1" |
Definition at line 190 of file cons_sos1.c.
◆ EVENTHDLR_DESC
| #define EVENTHDLR_DESC "bound change event handler for SOS1 constraints" |
Definition at line 191 of file cons_sos1.c.
◆ EVENTHDLR_EVENT_TYPE
| #define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) |
Definition at line 193 of file cons_sos1.c.
Referenced by deleteVarSOS1(), handleNewVariableSOS1(), and presolRoundConsSOS1().
◆ DIVINGCUTOFFVALUE
| #define DIVINGCUTOFFVALUE 1e6 |
Definition at line 196 of file cons_sos1.c.
Referenced by getDiveBdChgsSOS1conflictgraph(), and getDiveBdChgsSOS1constraints().
Typedef Documentation
◆ SCIP_NODEDATA
| typedef struct SCIP_NodeData SCIP_NODEDATA |
Definition at line 226 of file cons_sos1.c.
◆ SCIP_SUCCDATA
| typedef struct SCIP_SuccData SCIP_SUCCDATA |
Definition at line 235 of file cons_sos1.c.
Function Documentation
◆ isConnectedSOS1()
|
static |
returns whether two vertices are adjacent in the conflict graph
- Parameters
-
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 333 of file cons_sos1.c.
References FALSE, isViolatedSOS1(), NULL, SCIP_Bool, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPsortInt(), SCIPswapInts(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), computeVarsCoverSOS1(), enforceConflictgraph(), extensionOperatorSOS1(), getBoundConsFromVertices(), performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
◆ isViolatedSOS1()
|
static |
checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable
- Parameters
-
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 393 of file cons_sos1.c.
References FALSE, nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by getDiveBdChgsSOS1conflictgraph(), and isConnectedSOS1().
◆ nodeGetSolvalBinaryBigMSOS1()
|
static |
returns solution value of imaginary binary big-M variable of a given node from the conflict graph
- Parameters
-
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 438 of file cons_sos1.c.
References bound, nodeGetSolvalVarboundLbSOS1(), NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by computeVarsCoverSOS1(), getBoundConsFromVertices(), and isViolatedSOS1().
◆ nodeGetSolvalVarboundLbSOS1()
|
static |
gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph
- Parameters
-
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 488 of file cons_sos1.c.
References nodedata, nodeGetSolvalVarboundUbSOS1(), NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetLbLocal().
Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalBinaryBigMSOS1(), and updateWeightsTCliquegraph().
◆ nodeGetSolvalVarboundUbSOS1()
|
static |
gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph
- Parameters
-
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 515 of file cons_sos1.c.
References nodedata, NULL, SCIP_Bool, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), SCIPvarGetUbLocal(), and varIsSOS1().
Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalVarboundLbSOS1(), and updateWeightsTCliquegraph().
◆ varIsSOS1()
|
static |
returns whether variable is part of the SOS1 conflict graph
- Parameters
-
conshdlrdata SOS1 constraint handler var variable
Definition at line 542 of file cons_sos1.c.
Referenced by checkLinearConssVarboundSOS1(), and nodeGetSolvalVarboundUbSOS1().
◆ varGetNodeSOS1()
|
static |
returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph
- Parameters
-
conshdlrdata SOS1 constraint handler var variable
Definition at line 559 of file cons_sos1.c.
Referenced by checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), detectVarboundSOS1(), enforceConflictgraph(), genConflictgraphLinearCons(), generateBoundInequalityFromSOS1Cons(), getSOS1Implications(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
◆ fixVariableZeroNode()
|
static |
fix variable in given node to 0 or add constraint if variable is multi-aggregated
- Parameters
-
scip SCIP pointer var variable to be fixed to 0 node node infeasible if fixing is infeasible
Definition at line 580 of file cons_sos1.c.
References FALSE, fixVariableZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), enforceConssSOS1(), and getBranchingDecisionStrongbranchSOS1().
◆ fixVariableZero()
|
static |
try to fix variable to 0
Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
\[ x = \sum_{i=1}^n \alpha_i x_i + c, \]
we can express the fixing \(x = 0\) by fixing all \(x_i\) to 0 if \(c = 0\) and the lower bounds of \(x_i\) are nonnegative if \(\alpha_i > 0\) or the upper bounds are nonpositive if \(\alpha_i < 0\).
- Parameters
-
scip SCIP pointer var variable to be fixed to 0 infeasible if fixing is infeasible tightened if fixing was performed
Definition at line 635 of file cons_sos1.c.
References FALSE, inferVariableZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPfixVar(), SCIPflattenVarAggregationGraph(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.
Referenced by fixVariableZeroNode(), and presolRoundConsSOS1().
◆ inferVariableZero()
|
static |
fix variable in local node to 0, and return whether the operation was feasible
- Note
- We do not add a linear constraint if the variable is multi-aggregated as in fixVariableZeroNode(), since this would be too time consuming.
- Parameters
-
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 709 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().
◆ lockVariableSOS1()
|
static |
add lock on variable
- Parameters
-
scip SCIP data structure cons constraint var variable
Definition at line 752 of file cons_sos1.c.
Referenced by handleNewVariableSOS1(), inferVariableZero(), and presolRoundConsSOS1().
◆ unlockVariableSOS1()
|
static |
remove lock on variable
- Parameters
-
scip SCIP data structure cons constraint var variable
Definition at line 772 of file cons_sos1.c.
Referenced by deleteVarSOS1(), and presolRoundConsSOS1().
◆ consdataEnsurevarsSizeSOS1()
|
static |
ensures that the vars and weights array can store at least num entries
- Parameters
-
scip SCIP data structure consdata constraint data num minimum number of entries to store reserveWeights whether the weights array is handled
Definition at line 792 of file cons_sos1.c.
References handleNewVariableSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addVarSOS1(), and appendVarSOS1().
◆ handleNewVariableSOS1()
|
static |
handle new variable
- Parameters
-
scip SCIP data structure cons constraint consdata constraint data conshdlrdata constraint handler data var variable transformed whether original variable was transformed
Definition at line 820 of file cons_sos1.c.
References addVarSOS1(), EVENTHDLR_EVENT_TYPE, lockVariableSOS1(), NULL, SCIP_CALL, 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().
◆ addVarSOS1()
|
static |
adds a variable to an SOS1 constraint, at position given by weight - ascending order
- Parameters
-
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 955 of file cons_sos1.c.
References appendVarSOS1(), consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), and SCIPaddVarSOS1().
◆ appendVarSOS1()
|
static |
appends a variable to an SOS1 constraint
- Parameters
-
scip SCIP data structure cons constraint conshdlrdata constraint handler data var variable to add to the constraint
Definition at line 1025 of file cons_sos1.c.
References consdataEnsurevarsSizeSOS1(), deleteVarSOS1(), FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.
Referenced by addVarSOS1().
◆ deleteVarSOS1()
|
static |
deletes a variable of an SOS1 constraint
- Parameters
-
scip SCIP data structure cons constraint consdata constraint data eventhdlr corresponding event handler pos position of variable in array
Definition at line 1083 of file cons_sos1.c.
References EVENTHDLR_EVENT_TYPE, extensionOperatorSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1().
Referenced by appendVarSOS1(), and presolRoundConsSOS1().
◆ extensionOperatorSOS1()
|
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
- Parameters
-
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 1122 of file cons_sos1.c.
References FALSE, genConflictgraphLinearCons(), isConnectedSOS1(), MAX, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), TRUE, and w.
Referenced by deleteVarSOS1(), and presolRoundConssSOS1().
◆ genConflictgraphLinearCons()
|
static |
generates conflict graph that is induced by the variables of a linear constraint
- Parameters
-
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 iis not a SOS1 variable or not a variable of the linear constraint
Definition at line 1383 of file cons_sos1.c.
References cliqueGetCommonSuccessorsSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().
Referenced by extensionOperatorSOS1(), and tightenVarsBoundsSOS1().
◆ cliqueGetCommonSuccessorsSOS1()
|
static |
determine the common successors of the vertices from the considered clique
- Parameters
-
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 1436 of file cons_sos1.c.
References getSOS1Implications(), NULL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().
Referenced by genConflictgraphLinearCons(), and presolRoundConssSOS1().
◆ getSOS1Implications()
|
static |
get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data vars problem and SOS1 variables implgraph implication graph ( jis successor ofiif 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 1537 of file cons_sos1.c.
References NULL, presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImageInt(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, and varGetNodeSOS1().
Referenced by cliqueGetCommonSuccessorsSOS1(), and tightenVarsBoundsSOS1().
◆ presolRoundConsSOS1()
|
static |
perform one presolving round for a single SOS1 constraint
We perform the following presolving steps.
- If the bounds of some variable force it to be nonzero, we can fix all other variables to zero and remove the SOS1 constraints that contain it.
- If a variable is fixed to zero, we can remove the variable.
- If a variable appears twice, it can be fixed to 0.
- We substitute appregated variables.
- Parameters
-
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 1603 of file cons_sos1.c.
References deleteVarSOS1(), EVENTHDLR_EVENT_TYPE, FALSE, fixVariableZero(), lockVariableSOS1(), NULL, presolRoundConssSOS1(), SCIP_Bool, SCIP_CALL, 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().
◆ presolRoundConssSOS1()
|
static |
perform one presolving round for all SOS1 constraints
We perform the following presolving steps.
- If the bounds of some variable force it to be nonzero, we can fix all other variables to zero and remove the SOS1 constraints that contain it.
- If a variable is fixed to zero, we can remove the variable.
- If a variable appears twice, it can be fixed to 0.
- We substitute appregated variables.
- Remove redundant SOS1 constraints
If the adjacency matrix of the conflict graph is present, then we perform the following additional presolving steps
- Search for larger SOS1 constraints in the conflict graph
- Parameters
-
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 1829 of file cons_sos1.c.
References cliqueGetCommonSuccessorsSOS1(), extensionOperatorSOS1(), FALSE, MAX, NULL, performImplicationGraphAnalysis(), presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcomputeArraysIntersectionInt(), SCIPconsGetData(), SCIPconsIsModifiable(), SCIPcreateDigraph(), SCIPdelCons(), SCIPdigraphAddArcSafe(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArrayNull, SCIPsortDownIntInt(), SCIPsortInt(), TRUE, and varGetNodeSOS1().
Referenced by presolRoundConsSOS1().
◆ performImplicationGraphAnalysis()
|
static |
performs implication graph analysis
Tentatively fixes a variable to nonzeero and extracts consequences from it:
- adds (possibly new) complementarity constraints to the problem if variables are implied to be zero
- returns that the subproblem is infeasible if the domain of a variable turns out to be empty
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph totalvars problem and SOS1 variables implgraph implication graph ( jis successor ofiif 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 2101 of file cons_sos1.c.
References addVarSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPgetDepth(), SCIPhashmapGetImageInt(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), SCIPvarGetName(), TRUE, and varGetNodeSOS1().
Referenced by presolRoundConssSOS1(), and presolRoundVarsSOS1().
◆ isImpliedZero()
|
static |
returns whether node is implied to be zero; this information is taken from the input array 'implnodes'
- Parameters
-
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 2259 of file cons_sos1.c.
Referenced by performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
◆ updateArcData()
|
static |
updates arc data of implication graph
- Parameters
-
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 2288 of file cons_sos1.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPceil(), SCIPdebugMsg, SCIPdigraphAddArc(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfloor(), SCIPhashmapGetImageInt(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), SCIPvarIsIntegral(), TRUE, and updateImplicationGraphSOS1().
Referenced by updateImplicationGraphSOS1().
◆ 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
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph adjacencymatrix adjacency matrix of conflict graph (lower half) implgraph implication graph ( jis successor ofiif 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 ivars 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 2414 of file cons_sos1.c.
References bound, computeVarsCoverSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, updateArcData(), varGetNodeSOS1(), and w.
Referenced by tightenVarsBoundsSOS1(), and updateArcData().
◆ computeVarsCoverSOS1()
|
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
- covers
vand - has an an empty intersection with already computed clique cover.
- Parameters
-
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 cliquev 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 2576 of file cons_sos1.c.
References isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasLT(), tightenVarsBoundsSOS1(), and TRUE.
Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
◆ tightenVarsBoundsSOS1()
|
static |
try to tighten upper and lower bounds for variables
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph implgraph implication graph ( jis successor ofiif 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 2687 of file cons_sos1.c.
References computeVarsCoverSOS1(), FALSE, genConflictgraphLinearCons(), getSOS1Implications(), isConnectedSOS1(), isImpliedZero(), MAX, NULL, presolRoundVarsSOS1(), REALABS, 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(), SCIPhashmapGetImageInt(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPreallocBufferArray, SCIPsortDownRealInt(), SCIPsortRealInt(), SCIPswapReals(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, updateImplicationGraphSOS1(), varGetNodeSOS1(), and w.
Referenced by computeVarsCoverSOS1(), initImplGraphSOS1(), and presolRoundVarsSOS1().
◆ presolRoundVarsSOS1()
|
static |
perform one presolving round for variables
We perform the following presolving steps:
- Tighten the bounds of the variables
- Update conflict graph based on bound implications of the variables
- Parameters
-
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 3368 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(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenVarsBoundsSOS1(), and TRUE.
Referenced by tightenVarsBoundsSOS1().
◆ propConsSOS1()
|
static |
propagate variables of SOS1 constraint
- Parameters
-
scip SCIP pointer cons constraint consdata constraint data cutoff whether a cutoff happened ngen number of domain changes
Definition at line 3542 of file cons_sos1.c.
References FALSE, inferVariableZero(), NULL, propVariableNonzero(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by enforceConflictgraph(), enforceConssSOS1(), and presolRoundVarsSOS1().
◆ propVariableNonzero()
|
static |
propagate a variable that is known to be nonzero
- Parameters
-
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 3640 of file cons_sos1.c.
References FALSE, inferVariableZero(), initImplGraphSOS1(), nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propConsSOS1().
◆ initImplGraphSOS1()
|
static |
initialize implication graph
j is successor of i if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)
- Note
- By construction the implication graph is globally valid.
- Parameters
-
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 3783 of file cons_sos1.c.
References FALSE, freeImplGraphSOS1(), nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPblkmem(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPnodeGetVarSOS1(), tightenVarsBoundsSOS1(), and TRUE.
Referenced by propVariableNonzero(), and sepaImplBoundCutsSOS1().
◆ freeImplGraphSOS1()
|
static |
deinitialize implication graph
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data
Definition at line 3954 of file cons_sos1.c.
Referenced by initImplGraphSOS1().
◆ getCoverVertices()
|
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.
- Parameters
-
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 4013 of file cons_sos1.c.
References getBranchingVerticesSOS1(), NULL, SCIP_Bool, SCIP_OKAY, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().
Referenced by addBranchingComplementaritiesSOS1(), and getBranchingVerticesSOS1().
◆ getBranchingVerticesSOS1()
|
static |
get vertices of variables that will be fixed to zero for each node
- Parameters
-
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 4120 of file cons_sos1.c.
References FALSE, getBranchingPrioritiesSOS1(), getCoverVertices(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and TRUE.
Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), and getCoverVertices().
◆ getBranchingPrioritiesSOS1()
|
static |
gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision
- Parameters
-
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 4233 of file cons_sos1.c.
References FALSE, getBranchingVerticesSOS1(), NULL, performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), and TRUE.
Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), and getBranchingVerticesSOS1().
◆ performStrongbranchSOS1()
|
static |
performs strong branching with given domain fixings
- Parameters
-
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 4337 of file cons_sos1.c.
References FALSE, getBranchingDecisionStrongbranchSOS1(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPendProbing(), SCIPfeastol(), SCIPfixVarProbing(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPpropagateProbing(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.
Referenced by getBranchingDecisionStrongbranchSOS1(), and getBranchingPrioritiesSOS1().
◆ getBranchingDecisionStrongbranchSOS1()
|
static |
apply strong branching to determine the vertex for the next branching decision
- Parameters
-
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 4479 of file cons_sos1.c.
References FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), MAX, NULL, 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().
◆ getBoundConsFromVertices()
|
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.
- Parameters
-
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 v1andv2(or NULL if not existent)extend should v1andv2be greedily extended to a clique of larger sizecons bound constraint feas feasibility value of bound constraint
Definition at line 4696 of file cons_sos1.c.
References addBranchingComplementaritiesSOS1(), FALSE, isConnectedSOS1(), nodedata, nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPallocBufferArray, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), and getBranchingDecisionStrongbranchSOS1().
◆ addBranchingComplementaritiesSOS1()
|
static |
tries to add feasible complementarity constraints to a given child branching node.
- Note
- In this function the conflict graph is updated to the conflict graph of the considered child branching node.
- Parameters
-
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 4924 of file cons_sos1.c.
References addVarSOS1(), FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getCoverVertices(), isConnectedSOS1(), nodedata, NULL, resetConflictgraphSOS1(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPcomputeArraysSetminusInt(), SCIPcreateConsLinear(), SCIPcreateConsSOS1(), SCIPcreateDigraph(), SCIPdigraphAddArc(), 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().
◆ resetConflictgraphSOS1()
|
static |
resets local conflict graph to the conflict graph of the root node
- Parameters
-
conflictgraph conflict graph of root node localconflicts local conflicts that should be removed from conflict graph nsos1vars number of SOS1 variables
Definition at line 5288 of file cons_sos1.c.
References enforceConflictgraph(), SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminusInt(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors().
Referenced by addBranchingComplementaritiesSOS1(), and enforceConflictgraph().
◆ enforceConflictgraph()
|
static |
Conflict graph enforcement method
The conflict graph can be enforced by different branching rules:
- Branch on the neighborhood of a single variable
i, i.e., in one branch \(x_i\) is fixed to zero and in the other its neighbors from the conflict graph. - Branch on complete bipartite subgraphs of the conflict graph, i.e., in one branch fix the variables from the first bipartite partition and the variables from the second bipartite partition in the other.
- In addition to variable domain fixings, it is sometimes also possible to add new SOS1 constraints to the branching nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.
We make use of different selection rules that define on which system of SOS1 variables to branch next:
- Most infeasible branching: Branch on the system of SOS1 variables with largest violation.
- Strong branching: Here, the LP-relaxation is partially solved for each branching decision among a candidate list. Then the decision with best progress is chosen.
- Parameters
-
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 5344 of file cons_sos1.c.
References addBranchingComplementaritiesSOS1(), enforceConssSOS1(), FALSE, fixVariableZeroNode(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), isConnectedSOS1(), MAX, NULL, 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, SCIPcalcChildEstimateIncrease(), SCIPcalcNodeselPriority(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPerrorMessage, SCIPfeastol(), SCIPfloor(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPgetLocalTransEstimate(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPsortInt(), SCIPupdateNodeLowerbound(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), TRUE, and varGetNodeSOS1().
Referenced by enforceSOS1(), and resetConflictgraphSOS1().
◆ enforceConssSOS1()
|
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.
- Parameters
-
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 5816 of file cons_sos1.c.
References branchCons(), enforceSOS1(), fixVariableZeroNode(), NULL, propConsSOS1(), REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIP_REAL_MAX, SCIP_REDUCEDDOM, SCIPcalcChildEstimate(), SCIPcalcChildEstimateIncrease(), SCIPcalcNodeselPriority(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMsg, SCIPerrorMessage, SCIPfloor(), SCIPgetLocalTransEstimate(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetName(), SCIPvarIsBinary(), and w.
Referenced by enforceConflictgraph(), and enforceSOS1().
◆ enforceSOS1()
|
static |
constraint enforcing method of constraint handler
- Parameters
-
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 6062 of file cons_sos1.c.
References enforceConflictgraph(), enforceConssSOS1(), initTCliquegraph(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIPconshdlrGetData(), and SCIPerrorMessage.
Referenced by enforceConssSOS1().
◆ initTCliquegraph()
|
static |
initialitze tclique graph and create clique data
- Parameters
-
scip SCIP pointer conshdlr constraint handler conshdlrdata constraint handler data conflictgraph conflict graph nsos1vars number of SOS1 variables
Definition at line 6125 of file cons_sos1.c.
References TCLIQUE_Data::conflictgraph, TCLIQUE_Data::conshdlr, TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, TCLIQUE_Data::scip, SCIP_CALL, SCIP_NOMEMORY, SCIP_OKAY, SCIPallocBlockMemory, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPnodeGetVarSOS1(), SCIPvarIsActive(), TCLIQUE_Data::sol, TCLIQUE_Data::strthenboundcuts, tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), tcliqueFlush(), and updateWeightsTCliquegraph().
Referenced by enforceSOS1().
◆ updateWeightsTCliquegraph()
|
static |
update weights of tclique graph
- Parameters
-
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 6194 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().
◆ addBoundCutSepa()
|
static |
adds bound cut(s) to separation storage
- Parameters
-
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 6254 of file cons_sos1.c.
References FALSE, generateBoundInequalityFromSOS1Nodes(), TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPdebug, SCIPisCutEfficacious(), SCIPprintRow(), SCIProwIsInLP(), and TRUE.
Referenced by updateWeightsTCliquegraph().
◆ generateBoundInequalityFromSOS1Nodes()
|
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.
- Parameters
-
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 6328 of file cons_sos1.c.
References FALSE, nnodes, nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowConshdlr(), 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().
◆ TCLIQUE_NEWSOL()
|
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 6618 of file cons_sos1.c.
Referenced by generateBoundInequalityFromSOS1Nodes().
◆ sepaBoundInequalitiesFromGraph()
|
static |
separate bound inequalities from conflict graph
- Parameters
-
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 6753 of file cons_sos1.c.
References TCLIQUE_Data::cutoff, FALSE, generateBoundInequalityFromSOS1Cons(), TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), TCLIQUE_Data::sol, tcliqueMaxClique(), and updateWeightsTCliquegraph().
Referenced by separateSOS1().
◆ generateBoundInequalityFromSOS1Cons()
|
static |
Generate a bound constraint from the variables of an SOS1 constraint (see generateBoundInequalityFromSOS1Nodes() for more information)
- Parameters
-
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 6827 of file cons_sos1.c.
References CONSHDLR_NAME, generateBoundInequalityFromSOS1Nodes(), initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varGetNodeSOS1().
Referenced by initsepaBoundInequalityFromSOS1Cons(), and sepaBoundInequalitiesFromGraph().
◆ initsepaBoundInequalityFromSOS1Cons()
|
static |
initialize or separate bound inequalities from SOS1 constraints
- Parameters
-
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 6890 of file cons_sos1.c.
References FALSE, generateBoundInequalityFromSOS1Cons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMsg, SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIProwIsInLP(), sepaImplBoundCutsSOS1(), and TRUE.
Referenced by generateBoundInequalityFromSOS1Cons(), and separateSOS1().
◆ sepaImplBoundCutsSOS1()
|
static |
separate implied bound cuts
- Parameters
-
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 7004 of file cons_sos1.c.
References FALSE, initImplGraphSOS1(), nodedata, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), 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().
◆ separateSOS1()
|
static |
separates SOS1 constraints for arbitrary solutions
- Parameters
-
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 7229 of file cons_sos1.c.
References getVectorOfWeights(), initsepaBoundInequalityFromSOS1Cons(), NULL, 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().
◆ getVectorOfWeights()
|
static |
gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem
- Parameters
-
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 7350 of file cons_sos1.c.
References markNeighborsMWISHeuristic(), NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and SCIPsumepsilon().
Referenced by maxWeightIndSetHeuristic(), and separateSOS1().
◆ markNeighborsMWISHeuristic()
|
static |
- Parameters
-
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 7421 of file cons_sos1.c.
References FALSE, maxWeightIndSetHeuristic(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_NEGATED, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetAggrConstant(), SCIPvarGetAggrVar(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetNodeSOS1(), SCIPvarGetStatus(), and TRUE.
Referenced by getVectorOfWeights(), and maxWeightIndSetHeuristic().
◆ 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.
- Parameters
-
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 7562 of file cons_sos1.c.
References FALSE, getVectorOfWeights(), makeSOS1conflictgraphFeasible(), markNeighborsMWISHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownRealInt(), and TRUE.
Referenced by makeSOS1conflictgraphFeasible(), and markNeighborsMWISHeuristic().
◆ makeSOS1conflictgraphFeasible()
|
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
- Parameters
-
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 7668 of file cons_sos1.c.
References FALSE, makeSOS1constraintsFeasible(), maxWeightIndSetHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by maxWeightIndSetHeuristic(), and SCIPmakeSOS1sFeasible().
◆ makeSOS1constraintsFeasible()
|
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
- Parameters
-
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 7798 of file cons_sos1.c.
References FALSE, getDiveBdChgsSOS1conflictgraph(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPgetSolVal(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by makeSOS1conflictgraphFeasible(), and SCIPmakeSOS1sFeasible().
◆ getDiveBdChgsSOS1conflictgraph()
|
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
- Parameters
-
scip SCIP pointer conshdlr SOS1 constraint handler diveset diving settings sol solution success pointer to store
Definition at line 7933 of file cons_sos1.c.
References bound, DIVINGCUTOFFVALUE, FALSE, getDiveBdChgsSOS1constraints(), isViolatedSOS1(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdivesetSupportsType(), SCIPgetConflictgraphSOS1(), SCIPgetDivesetScore(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by makeSOS1constraintsFeasible().
◆ getDiveBdChgsSOS1constraints()
|
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)
- Parameters
-
scip SCIP pointer conshdlr SOS1 constraint handler diveset diving settings sol solution success pointer to store
Definition at line 8074 of file cons_sos1.c.
References bound, detectVarboundSOS1(), DIVINGCUTOFFVALUE, FALSE, NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdivesetSupportsType(), SCIPgetDivesetScore(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisPositive(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by getDiveBdChgsSOS1conflictgraph().
◆ detectVarboundSOS1()
|
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.
- Parameters
-
scip SCIP pointer conshdlrdata SOS1 constraint handler data var0 first variable var1 second variable val0 first coefficient val1 second coefficient
Definition at line 8255 of file cons_sos1.c.
References nodedata, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1().
Referenced by checkLinearConssVarboundSOS1(), and getDiveBdChgsSOS1constraints().
◆ passConComponentVarbound()
|
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\).
- Note
- if the bound variable is unique, then bound inequalities can be strengthened.
- Parameters
-
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 8331 of file cons_sos1.c.
References checkConComponentsVarbound(), FALSE, nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE.
Referenced by checkConComponentsVarbound(), and detectVarboundSOS1().
◆ checkConComponentsVarbound()
|
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\)).
- Note
- if the bound variable is unique, then bound inequalities can be strengthened.
- Parameters
-
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 8404 of file cons_sos1.c.
References checkLinearConssVarboundSOS1(), FALSE, nodedata, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, and TRUE.
Referenced by passConComponentVarbound().
◆ checkLinearConssVarboundSOS1()
|
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)
- Parameters
-
scip SCIP pointer conshdlrdata SOS1 constraint handler data linconss linear constraints nlinconss number of linear constraints
Definition at line 8493 of file cons_sos1.c.
References checkSwitchNonoverlappingSOS1Methods(), detectVarboundSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasZero(), and varIsSOS1().
Referenced by checkConComponentsVarbound().
◆ checkSwitchNonoverlappingSOS1Methods()
|
static |
switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap
- Parameters
-
scip SCIP pointer conshdlrdata SOS1 constraint handler data conflictgraph conflict graph conss SOS1 constraints nconss number of SOS1 constraints
Definition at line 8566 of file cons_sos1.c.
References computeNodeDataSOS1(), FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().
Referenced by checkLinearConssVarboundSOS1().
◆ computeNodeDataSOS1()
|
static |
sets node data of conflict graph nodes
- Parameters
-
scip SCIP pointer conshdlrdata SOS1 constraint handler data nsos1vars number of SOS1 variables
Definition at line 8647 of file cons_sos1.c.
Referenced by checkSwitchNonoverlappingSOS1Methods().
◆ initConflictgraph()
|
static |
initialize conflictgraph and create hashmap for SOS1 variables
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data conss SOS1 constraints nconss number of SOS1 constraints
Definition at line 8684 of file cons_sos1.c.
References FALSE, freeConflictgraph(), nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPblkmem(), SCIPconsGetData(), SCIPcreateDigraph(), SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArray, SCIPgetNTotalVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPisFeasZero(), SCIPsortInt(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
◆ freeConflictgraph()
|
static |
free conflict graph, nodedata and hashmap
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data
Definition at line 8879 of file cons_sos1.c.
References CONSHDLR_NAME, nodedata, NULL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphSetNodeData(), SCIPfreeBlockMemory, and SCIPhashmapFree().
Referenced by initConflictgraph().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 8925 of file cons_sos1.c.
Referenced by freeConflictgraph().
◆ SCIP_DECL_CONSFREE()
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 8942 of file cons_sos1.c.
◆ SCIP_DECL_CONSINITSOL()
|
static |
solving process initialization method of constraint handler (called when branch and bound process is about to begin)
Definition at line 8964 of file cons_sos1.c.
◆ SCIP_DECL_CONSEXITSOL()
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 9017 of file cons_sos1.c.
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 9089 of file cons_sos1.c.
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 9143 of file cons_sos1.c.
◆ SCIP_DECL_CONSPRESOL()
|
static |
presolving method of constraint handler
Definition at line 9237 of file cons_sos1.c.
◆ SCIP_DECL_CONSINITLP()
|
static |
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 9356 of file cons_sos1.c.
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 9381 of file cons_sos1.c.
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 9397 of file cons_sos1.c.
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 9413 of file cons_sos1.c.
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 9429 of file cons_sos1.c.
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 9445 of file cons_sos1.c.
◆ SCIP_DECL_CONSCHECK()
|
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 9464 of file cons_sos1.c.
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 9536 of file cons_sos1.c.
◆ SCIP_DECL_CONSRESPROP()
|
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 9682 of file cons_sos1.c.
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Let lb and ub be the lower and upper bounds of a variable. Preprocessing usually makes sure that lb <= 0 <= ub.
- If lb < 0 then rounding down may violate the constraint.
- If ub > 0 then rounding up may violated the constraint.
- If lb > 0 or ub < 0 then the constraint is infeasible and we do not have to deal with it here.
- If lb == 0 then rounding down does not violate the constraint.
- If ub == 0 then rounding up does not violate the constraint.
Definition at line 9758 of file cons_sos1.c.
◆ SCIP_DECL_CONSPRINT()
|
static |
constraint display method of constraint handler
Definition at line 9804 of file cons_sos1.c.
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 9834 of file cons_sos1.c.
◆ SCIP_DECL_CONSPARSE()
|
static |
constraint parsing method of constraint handler
Definition at line 9898 of file cons_sos1.c.
◆ SCIP_DECL_CONSGETVARS()
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 9988 of file cons_sos1.c.
References BMScopyMemoryArray, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
◆ SCIP_DECL_CONSGETNVARS()
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 10011 of file cons_sos1.c.
Referenced by SCIP_DECL_CONSGETVARS().
◆ SCIP_DECL_EVENTEXEC()
|
static |
exec the event handler
We update the number of variables fixed to be nonzero
Definition at line 10032 of file cons_sos1.c.
◆ SCIP_DECL_CONSGETDIVEBDCHGS()
|
static |
constraint handler method to determine a diving variable by assigning a variable and two values for diving
Definition at line 10154 of file cons_sos1.c.