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 "scip/symmetry_graph.h"#include "symmetry/struct_symmetry.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) |
| static | SCIP_DECL_CONSGETPERMSYMGRAPH (consGetPermsymGraphSOS1) |
| static | SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH (consGetSignedPermsymGraphSOS1) |
| 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 120 of file cons_sos1.c.
◆ CONSHDLR_DESC
| #define CONSHDLR_DESC "SOS1 constraint handler" |
Definition at line 121 of file cons_sos1.c.
◆ CONSHDLR_SEPAPRIORITY
| #define CONSHDLR_SEPAPRIORITY 1000 |
priority of the constraint handler for separation
Definition at line 122 of file cons_sos1.c.
◆ CONSHDLR_ENFOPRIORITY
| #define CONSHDLR_ENFOPRIORITY 100 |
priority of the constraint handler for constraint enforcing
Definition at line 123 of file cons_sos1.c.
◆ CONSHDLR_CHECKPRIORITY
| #define CONSHDLR_CHECKPRIORITY -10 |
priority of the constraint handler for checking feasibility
Definition at line 124 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 125 of file cons_sos1.c.
◆ CONSHDLR_PROPFREQ
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 126 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 128 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 129 of file cons_sos1.c.
◆ CONSHDLR_DELAYSEPA
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 130 of file cons_sos1.c.
◆ CONSHDLR_DELAYPROP
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 131 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 132 of file cons_sos1.c.
◆ CONSHDLR_PROP_TIMING
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 133 of file cons_sos1.c.
◆ CONSHDLR_PRESOLTIMING
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM |
Definition at line 134 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 138 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 154 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 155 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 159 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 160 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 161 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 162 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 163 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 164 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 168 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 169 of file cons_sos1.c.
◆ DEFAULT_BOUNDCUTSFROMSOS1
| #define DEFAULT_BOUNDCUTSFROMSOS1 FALSE |
if TRUE separate bound inequalities from SOS1 constraints
Definition at line 172 of file cons_sos1.c.
◆ DEFAULT_BOUNDCUTSFROMGRAPH
| #define DEFAULT_BOUNDCUTSFROMGRAPH TRUE |
if TRUE separate bound inequalities from the conflict graph
Definition at line 173 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 174 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 175 of file cons_sos1.c.
◆ DEFAULT_BOUNDCUTSDEPTH
| #define DEFAULT_BOUNDCUTSDEPTH 40 |
node depth of separating bound cuts (-1: no limit)
Definition at line 176 of file cons_sos1.c.
◆ DEFAULT_MAXBOUNDCUTS
| #define DEFAULT_MAXBOUNDCUTS 50 |
maximal number of bound cuts separated per branching node
Definition at line 177 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 178 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 179 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 180 of file cons_sos1.c.
◆ DEFAULT_IMPLCUTSDEPTH
| #define DEFAULT_IMPLCUTSDEPTH 40 |
node depth of separating implied bound cuts (-1: no limit)
Definition at line 181 of file cons_sos1.c.
◆ DEFAULT_MAXIMPLCUTS
| #define DEFAULT_MAXIMPLCUTS 50 |
maximal number of implied bound cuts separated per branching node
Definition at line 182 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 183 of file cons_sos1.c.
◆ EVENTHDLR_NAME
| #define EVENTHDLR_NAME "SOS1" |
Definition at line 186 of file cons_sos1.c.
◆ EVENTHDLR_DESC
| #define EVENTHDLR_DESC "bound change event handler for SOS1 constraints" |
Definition at line 187 of file cons_sos1.c.
◆ EVENTHDLR_EVENT_TYPE
| #define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) |
Definition at line 189 of file cons_sos1.c.
◆ DIVINGCUTOFFVALUE
| #define DIVINGCUTOFFVALUE 1e6 |
Definition at line 192 of file cons_sos1.c.
Typedef Documentation
◆ SCIP_NODEDATA
| typedef struct SCIP_NodeData SCIP_NODEDATA |
Definition at line 222 of file cons_sos1.c.
◆ SCIP_SUCCDATA
| typedef struct SCIP_SuccData SCIP_SUCCDATA |
Definition at line 231 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 329 of file cons_sos1.c.
References FALSE, NULL, 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 389 of file cons_sos1.c.
References FALSE, NULL, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by getDiveBdChgsSOS1conflictgraph().
◆ 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 434 of file cons_sos1.c.
References bound, NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by computeVarsCoverSOS1(), and getBoundConsFromVertices().
◆ 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 484 of file cons_sos1.c.
References nodedata, NULL, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetLbLocal().
Referenced by getDiveBdChgsSOS1conflictgraph(), TCLIQUE_NEWSOL(), 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 511 of file cons_sos1.c.
References nodedata, NULL, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetUbLocal().
Referenced by getDiveBdChgsSOS1conflictgraph(), TCLIQUE_NEWSOL(), and updateWeightsTCliquegraph().
◆ varIsSOS1()
|
static |
returns whether variable is part of the SOS1 conflict graph
- Parameters
-
conshdlrdata SOS1 constraint handler var variable
Definition at line 538 of file cons_sos1.c.
References FALSE, NULL, SCIPhashmapExists(), and TRUE.
Referenced by checkLinearConssVarboundSOS1(), and SCIPvarIsSOS1().
◆ 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 555 of file cons_sos1.c.
References NULL, SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), detectVarboundSOS1(), enforceConflictgraph(), genConflictgraphLinearCons(), generateBoundInequalityFromSOS1Cons(), getSOS1Implications(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), SCIP_DECL_CONSPROP(), SCIPvarGetNodeSOS1(), 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 576 of file cons_sos1.c.
References FALSE, NULL, 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 631 of file cons_sos1.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPfixVar(), SCIPflattenVarAggregationGraph(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.
Referenced by presolRoundConsSOS1().
◆ 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 705 of file cons_sos1.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propConsSOS1(), and propVariableNonzero().
◆ lockVariableSOS1()
|
static |
add lock on variable
- Parameters
-
scip SCIP data structure cons constraint var variable
Definition at line 748 of file cons_sos1.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by handleNewVariableSOS1(), and presolRoundConsSOS1().
◆ unlockVariableSOS1()
|
static |
remove lock on variable
- Parameters
-
scip SCIP data structure cons constraint var variable
Definition at line 768 of file cons_sos1.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
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 788 of file cons_sos1.c.
References 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 816 of file cons_sos1.c.
References EVENTHDLR_EVENT_TYPE, lockVariableSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPdebugMsg, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPsortInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().
Referenced by addVarSOS1(), appendVarSOS1(), 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 951 of file cons_sos1.c.
References consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), 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 1021 of file cons_sos1.c.
References consdataEnsurevarsSizeSOS1(), FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.
Referenced by SCIPappendVarSOS1().
◆ 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 1079 of file cons_sos1.c.
References EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1().
Referenced by 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 1118 of file cons_sos1.c.
References extensionOperatorSOS1(), FALSE, 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 extensionOperatorSOS1(), 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 1379 of file cons_sos1.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().
Referenced by 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 1432 of file cons_sos1.c.
References NULL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().
Referenced by 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 1533 of file cons_sos1.c.
References getSOS1Implications(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImageInt(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, and varGetNodeSOS1().
Referenced by getSOS1Implications(), 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 1599 of file cons_sos1.c.
References deleteVarSOS1(), EVENTHDLR_EVENT_TYPE, FALSE, fixVariableZero(), lockVariableSOS1(), NULL, 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 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 1825 of file cons_sos1.c.
References cliqueGetCommonSuccessorsSOS1(), extensionOperatorSOS1(), FALSE, MAX, NULL, 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 SCIP_DECL_CONSPRESOL().
◆ 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 2097 of file cons_sos1.c.
References addVarSOS1(), FALSE, isConnectedSOS1(), NULL, performImplicationGraphAnalysis(), 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 performImplicationGraphAnalysis(), 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 2255 of file cons_sos1.c.
References FALSE, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and TRUE.
Referenced by 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 2284 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(), and TRUE.
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 ( \(j\) is successor of \(i\) if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)) implhash hash map from variable to node in implication graph implnodes implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero totalvars problem and SOS1 variables cliquecovers clique covers of linear constraint cliquecoversizes size of clique covers varincover array with varincover[i] = cover of SOS1 index \(i\) vars variables to be checked coefs coefficients of variables in linear constraint nvars number of variables to be checked bounds bounds of variables var variable that is assumed to be nonzero bound bound of variable boundnonzero bound of variable if it is known to be nonzero if infinity values are not summarized ninftynonzero number of times infinity/-infinity has to be summarized to boundnonzero lower TRUE if lower bounds are consideres; FALSE for upper bounds nchgbds pointer to store number of changed bounds update pointer to store whether implication graph has been updated infeasible pointer to store whether an infeasibility has been detected
Definition at line 2410 of file cons_sos1.c.
References bound, 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().
◆ 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 v and
- 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 clique v position of variable in linear constraint that should be covered considersolvals TRUE if largest auxiliary bigM values of variables should be prefered
Definition at line 2572 of file cons_sos1.c.
References isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasLT(), and TRUE.
Referenced by tightenVarsBoundsSOS1().
◆ 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 2683 of file cons_sos1.c.
References computeVarsCoverSOS1(), FALSE, genConflictgraphLinearCons(), getSOS1Implications(), isConnectedSOS1(), isImpliedZero(), MAX, MIN, NULL, 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 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 3364 of file cons_sos1.c.
References FALSE, performImplicationGraphAnalysis(), 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 SCIP_DECL_CONSPRESOL().
◆ 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 3538 of file cons_sos1.c.
References FALSE, inferVariableZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by enforceConflictgraph(), enforceConssSOS1(), and SCIP_DECL_CONSPROP().
◆ 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 3636 of file cons_sos1.c.
References FALSE, inferVariableZero(), 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 SCIP_DECL_CONSPROP().
◆ 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 3779 of file cons_sos1.c.
References FALSE, 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 SCIP_DECL_CONSPROP(), and sepaImplBoundCutsSOS1().
◆ freeImplGraphSOS1()
|
static |
deinitialize implication graph
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data
Definition at line 3950 of file cons_sos1.c.
References nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPdigraphSetNodeData(), and SCIPfreeBlockMemory.
Referenced by SCIP_DECL_CONSEXITSOL().
◆ 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 4009 of file cons_sos1.c.
References NULL, 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 4116 of file cons_sos1.c.
References FALSE, getCoverVertices(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and TRUE.
Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), and getBranchingPrioritiesSOS1().
◆ 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 4229 of file cons_sos1.c.
References FALSE, getBranchingVerticesSOS1(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), and TRUE.
Referenced by enforceConflictgraph(), and getBranchingDecisionStrongbranchSOS1().
◆ 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 4333 of file cons_sos1.c.
References FALSE, NULL, SCIP_CALL, SCIP_INVALID, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPendProbing(), SCIPfeastol(), SCIPfixVarProbing(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPpropagateProbing(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.
Referenced by getBranchingDecisionStrongbranchSOS1().
◆ 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 4475 of file cons_sos1.c.
References FALSE, fixVariableZeroNode(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), MAX, MIN, NULL, performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPallocBufferArray, SCIPdebugMsg, SCIPfeastol(), SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPgetLPObjval(), SCIPgetNDualResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNNodeInitLPIterations(), SCIPgetNNodeInitLPs(), SCIPgetNNodes(), SCIPinfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), and SCIPsortDownRealInt().
Referenced by enforceConflictgraph().
◆ 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 4692 of file cons_sos1.c.
References 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().
◆ 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 4920 of file cons_sos1.c.
References addVarSOS1(), FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getCoverVertices(), isConnectedSOS1(), nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, 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().
◆ 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 5284 of file cons_sos1.c.
References SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminusInt(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors().
Referenced by 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 5340 of file cons_sos1.c.
References addBranchingComplementaritiesSOS1(), FALSE, fixVariableZeroNode(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), isConnectedSOS1(), MAX, MIN, 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().
◆ 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 5812 of file cons_sos1.c.
References branchCons(), fixVariableZeroNode(), NULL, propConsSOS1(), REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_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 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 6058 of file cons_sos1.c.
References enforceConflictgraph(), enforceConssSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIPconshdlrGetData(), and SCIPerrorMessage.
Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().
◆ 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 6121 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(), and tcliqueFlush().
Referenced by SCIP_DECL_CONSINITSOL().
◆ 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 6190 of file cons_sos1.c.
References bound, nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), REALABS, TCLIQUE_Data::scaleval, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tcliqueChangeWeight().
Referenced by 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 6250 of file cons_sos1.c.
References FALSE, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPdebug, SCIPisCutEfficacious(), SCIPprintRow(), SCIProwIsInLP(), and TRUE.
Referenced by TCLIQUE_NEWSOL().
◆ 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 6324 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(), and TRUE.
Referenced by generateBoundInequalityFromSOS1Cons(), and TCLIQUE_NEWSOL().
◆ 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 6614 of file cons_sos1.c.
References addBoundCutSepa(), bound, FALSE, generateBoundInequalityFromSOS1Nodes(), MAX, nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), NULL, REALABS, SCIP_Bool, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPdebugMsg, SCIPerrorMessage, SCIPgetSolVal(), SCIPisEfficacious(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPreleaseRow(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
◆ 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 6749 of file cons_sos1.c.
References TCLIQUE_Data::cutoff, FALSE, TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), TCLIQUE_Data::sol, tcliqueMaxClique(), and updateWeightsTCliquegraph().
Referenced by separateSOS1().
◆ 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 6823 of file cons_sos1.c.
References CONSHDLR_NAME, generateBoundInequalityFromSOS1Nodes(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varGetNodeSOS1().
Referenced by initsepaBoundInequalityFromSOS1Cons().
◆ 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 6886 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(), and TRUE.
Referenced by SCIP_DECL_CONSINITLP(), 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 7000 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(), and TRUE.
Referenced by 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 7225 of file cons_sos1.c.
References 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 SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
◆ 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 7346 of file cons_sos1.c.
References MIN, NULL, REALABS, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and SCIPsumepsilon().
Referenced by maxWeightIndSetHeuristic().
◆ 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 7417 of file cons_sos1.c.
References FALSE, markNeighborsMWISHeuristic(), 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 markNeighborsMWISHeuristic(), 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 7558 of file cons_sos1.c.
References FALSE, getVectorOfWeights(), markNeighborsMWISHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownRealInt(), and TRUE.
Referenced by makeSOS1conflictgraphFeasible().
◆ 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 7664 of file cons_sos1.c.
References FALSE, 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 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 7794 of file cons_sos1.c.
References FALSE, 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 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 7929 of file cons_sos1.c.
References bound, DIVINGCUTOFFVALUE, FALSE, isViolatedSOS1(), MIN, nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdivesetSupportsType(), SCIPgetConflictgraphSOS1(), SCIPgetDivesetScore(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by SCIP_DECL_CONSGETDIVEBDCHGS().
◆ 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 8070 of file cons_sos1.c.
References bound, DIVINGCUTOFFVALUE, FALSE, MIN, NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdivesetSupportsType(), SCIPgetDivesetScore(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisPositive(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by SCIP_DECL_CONSGETDIVEBDCHGS().
◆ 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 8251 of file cons_sos1.c.
References nodedata, NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1().
Referenced by checkLinearConssVarboundSOS1().
◆ 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 8327 of file cons_sos1.c.
References FALSE, nodedata, NULL, passConComponentVarbound(), SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE.
Referenced by checkConComponentsVarbound(), and passConComponentVarbound().
◆ 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 8400 of file cons_sos1.c.
References FALSE, nodedata, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, and TRUE.
Referenced by computeNodeDataSOS1().
◆ 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 8489 of file cons_sos1.c.
References detectVarboundSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasZero(), and varIsSOS1().
Referenced by computeNodeDataSOS1().
◆ 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 8562 of file cons_sos1.c.
References FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().
Referenced by SCIP_DECL_CONSINITSOL().
◆ 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 8643 of file cons_sos1.c.
References checkConComponentsVarbound(), checkLinearConssVarboundSOS1(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), and TRUE.
Referenced by SCIP_DECL_CONSINITSOL().
◆ 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 8680 of file cons_sos1.c.
References FALSE, 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.
Referenced by SCIP_DECL_CONSINITSOL(), and SCIP_DECL_CONSPRESOL().
◆ freeConflictgraph()
|
static |
free conflict graph, nodedata and hashmap
- Parameters
-
scip SCIP pointer conshdlrdata constraint handler data
Definition at line 8875 of file cons_sos1.c.
References nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphSetNodeData(), SCIPfreeBlockMemory, and SCIPhashmapFree().
Referenced by SCIP_DECL_CONSEXITSOL(), and SCIP_DECL_CONSPRESOL().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 8921 of file cons_sos1.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrSOS1(), and TRUE.
◆ SCIP_DECL_CONSFREE()
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 8938 of file cons_sos1.c.
References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.
◆ SCIP_DECL_CONSINITSOL()
|
static |
solving process initialization method of constraint handler (called when branch and bound process is about to begin)
Definition at line 8960 of file cons_sos1.c.
References checkSwitchNonoverlappingSOS1Methods(), computeNodeDataSOS1(), CONSHDLR_NAME, initConflictgraph(), initTCliquegraph(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPcreateDigraph().
◆ SCIP_DECL_CONSEXITSOL()
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 9013 of file cons_sos1.c.
References CONSHDLR_NAME, freeConflictgraph(), freeImplGraphSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPdigraphFree(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPreleaseRow(), and tcliqueFree().
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 9085 of file cons_sos1.c.
References CONSHDLR_NAME, EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPdropVarEvent(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseRow().
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 9139 of file cons_sos1.c.
References CONSHDLR_NAME, EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcatchVarEvent(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetNTotalVars(), SCIPgetTransformedVar(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPsnprintf(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
◆ SCIP_DECL_CONSPRESOL()
|
static |
presolving method of constraint handler
Definition at line 9233 of file cons_sos1.c.
References CONSHDLR_NAME, freeConflictgraph(), initConflictgraph(), NULL, presolRoundConssSOS1(), presolRoundVarsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPfreeBufferArrayNull.
◆ SCIP_DECL_CONSINITLP()
|
static |
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 9352 of file cons_sos1.c.
References CONSHDLR_NAME, FALSE, initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 9377 of file cons_sos1.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), and separateSOS1().
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 9393 of file cons_sos1.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), and separateSOS1().
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 9409 of file cons_sos1.c.
References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 9425 of file cons_sos1.c.
References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 9441 of file cons_sos1.c.
References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
◆ 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 9460 of file cons_sos1.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasZero(), SCIPprintCons(), SCIPresetConsAge(), SCIPupdateSolConsViolation(), and SCIPvarGetName().
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 9532 of file cons_sos1.c.
References CONSHDLR_NAME, FALSE, initImplGraphSOS1(), NULL, propConsSOS1(), propVariableNonzero(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetDepth(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisTransformed(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and varGetNodeSOS1().
◆ 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 9678 of file cons_sos1.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisFeasNegative(), SCIPisFeasPositive(), and SCIPnodeGetVarSOS1().
◆ 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 9754 of file cons_sos1.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
◆ SCIP_DECL_CONSPRINT()
|
static |
constraint display method of constraint handler
Definition at line 9800 of file cons_sos1.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), and SCIPwriteVarName().
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 9830 of file cons_sos1.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsSOS1(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetVarCopy(), and TRUE.
◆ SCIP_DECL_CONSPARSE()
|
static |
constraint parsing method of constraint handler
Definition at line 9894 of file cons_sos1.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarSOS1(), SCIPconshdlrGetName(), SCIPcreateConsSOS1(), SCIPerrorMessage, SCIPparseVarName(), SCIPreleaseCons(), SCIPskipSpace(), and TRUE.
◆ SCIP_DECL_CONSGETVARS()
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 9984 of file cons_sos1.c.
References BMScopyMemoryArray, FALSE, NULL, 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 10007 of file cons_sos1.c.
References NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.
◆ SCIP_DECL_EVENTEXEC()
|
static |
exec the event handler
We update the number of variables fixed to be nonzero
Definition at line 10028 of file cons_sos1.c.
References EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_EVENTTYPE_LBRELAXED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBRELAXED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPerrorMessage, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPgetNTotalVars(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPunlockVarCons(), SCIPvarGetName(), and TRUE.
◆ SCIP_DECL_CONSGETDIVEBDCHGS()
|
static |
constraint handler method to determine a diving variable by assigning a variable and two values for diving
Definition at line 10150 of file cons_sos1.c.
References CONSHDLR_NAME, FALSE, getDiveBdChgsSOS1conflictgraph(), getDiveBdChgsSOS1constraints(), NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPerrorMessage.
◆ SCIP_DECL_CONSGETPERMSYMGRAPH()
|
static |
constraint handler method which returns the permutation symmetry detection graph of a constraint
Definition at line 10190 of file cons_sos1.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphVarAggregation(), SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSymActiveVariables(), SCIPgetSymgraphVarnodeidx(), SCIPgetVarsSOS1(), SCIPisEQ(), SCIPisTransformed(), SCIPisZero(), SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_PERM, and TRUE.
◆ SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH()
|
static |
constraint handler method which returns the signed permutation symmetry detection graph of a constraint
Definition at line 10256 of file cons_sos1.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSymActiveVariables(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphVarnodeidx(), SCIPgetVarsSOS1(), SCIPisEQ(), SCIPisInfinity(), SCIPisTransformed(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_PERM, and TRUE.