constraint handler for SOS type 1 constraints
A specially ordered set of type 1 (SOS1) is a sequence of variables such that at most one variable is nonzero. The special case of two variables arises, for instance, from equilibrium or complementary conditions like \(x \cdot y = 0\). Note that it is in principle allowed that a variables appears twice, but it then can be fixed to 0.
This implementation of this constraint handler is based on classical ideas, see e.g.
"Special Facilities in General Mathematical Programming System for
Non-Convex Problems Using Ordered Sets of Variables"
E. Beale and J. Tomlin, Proc. 5th IFORS Conference, 447-454 (1970)
The order of the variables is determined as follows:
The validity of the SOS1 constraints can be enforced by different branching rules:
i
, i.e., in one branch \(x_i\) is fixed to zero and in the other its neighbors from the conflict graph.Definition in file cons_sos1.c.
#include "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 |
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) |
#define CONSHDLR_NAME "SOS1" |
Definition at line 120 of file cons_sos1.c.
#define CONSHDLR_DESC "SOS1 constraint handler" |
Definition at line 121 of file cons_sos1.c.
#define CONSHDLR_SEPAPRIORITY 1000 |
priority of the constraint handler for separation
Definition at line 122 of file cons_sos1.c.
#define CONSHDLR_ENFOPRIORITY 100 |
priority of the constraint handler for constraint enforcing
Definition at line 123 of file cons_sos1.c.
#define CONSHDLR_CHECKPRIORITY -10 |
priority of the constraint handler for checking feasibility
Definition at line 124 of file cons_sos1.c.
#define CONSHDLR_SEPAFREQ 10 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 125 of file cons_sos1.c.
#define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 126 of file cons_sos1.c.
#define CONSHDLR_EAGERFREQ 100 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 127 of file cons_sos1.c.
#define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 129 of file cons_sos1.c.
#define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 130 of file cons_sos1.c.
#define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 131 of file cons_sos1.c.
#define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 132 of file cons_sos1.c.
#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 133 of file cons_sos1.c.
#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM |
Definition at line 134 of file cons_sos1.c.
#define DEFAULT_MAXSOSADJACENCY 10000 |
do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit)
Definition at line 137 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_DEPTHIMPLANALYSIS -1 |
number of recursive calls of implication graph analysis (-1: no limit)
Definition at line 144 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_CONFLICTPROP TRUE |
whether to use conflict graph propagation
Definition at line 147 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_IMPLPROP TRUE |
whether to use implication graph propagation
Definition at line 148 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_SOSCONSPROP FALSE |
whether to use SOS1 constraint propagation
Definition at line 149 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_BRANCHSTRATEGIES "nbs" |
possible branching strategies (see parameter DEFAULT_BRANCHINGRULE)
Definition at line 152 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_BRANCHINGRULE 'n' |
which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique) (note: in some cases an automatic switching to SOS1 branching is possible)
Definition at line 153 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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 156 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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 158 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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 167 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_BOUNDCUTSFROMSOS1 FALSE |
if TRUE separate bound inequalities from SOS1 constraints
Definition at line 172 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_BOUNDCUTSFROMGRAPH TRUE |
if TRUE separate bound inequalities from the conflict graph
Definition at line 173 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_BOUNDCUTSDEPTH 40 |
node depth of separating bound cuts (-1: no limit)
Definition at line 176 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_MAXBOUNDCUTS 50 |
maximal number of bound cuts separated per branching node
Definition at line 177 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_IMPLCUTSDEPTH 40 |
node depth of separating implied bound cuts (-1: no limit)
Definition at line 181 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#define DEFAULT_MAXIMPLCUTS 50 |
maximal number of implied bound cuts separated per branching node
Definition at line 182 of file cons_sos1.c.
Referenced by SCIPincludeConshdlrSOS1().
#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.
Referenced by SCIPincludeConshdlrSOS1().
#define EVENTHDLR_NAME "SOS1" |
Definition at line 186 of file cons_sos1.c.
#define EVENTHDLR_DESC "bound change event handler for SOS1 constraints" |
Definition at line 187 of file cons_sos1.c.
#define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) |
Definition at line 189 of file cons_sos1.c.
#define DIVINGCUTOFFVALUE 1e6 |
Definition at line 192 of file cons_sos1.c.
Referenced by getDiveBdChgsSOS1conflictgraph(), and getDiveBdChgsSOS1constraints().
typedef struct SCIP_SuccData SCIP_SUCCDATA |
Definition at line 231 of file cons_sos1.c.
|
static |
returns whether two vertices are adjacent in the conflict graph
adjacencymatrix | adjacency matrix of conflict graph (lower half) (or NULL if an adjacencymatrix is not at hand) |
conflictgraph | conflict graph (or NULL if an adjacencymatrix is at hand) |
vertex1 | first vertex |
vertex2 | second vertex |
Definition at line 329 of file cons_sos1.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPsortInt(), SCIPswapInts(), and TRUE.
Referenced by addBranchingComplementaritiesSOS1(), computeVarsCoverSOS1(), enforceConflictgraph(), extensionOperatorSOS1(), getBoundConsFromVertices(), performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
|
static |
checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable
scip | SCIP data structure |
conflictgraph | conflict graph (or NULL if an adjacencymatrix is at hand) |
node | node of variable in the conflict graph |
sol | solution, or NULL to use current node's solution |
Definition at line 389 of file cons_sos1.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sol, TRUE, and var.
Referenced by getDiveBdChgsSOS1conflictgraph().
|
static |
returns solution value of imaginary binary big-M variable of a given node from the conflict graph
scip | SCIP pointer |
conflictgraph | conflict graph |
sol | primal solution, or NULL for current LP/pseudo solution |
node | node of the conflict graph |
Definition at line 434 of file cons_sos1.c.
References assert(), bound, NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sol, and var.
Referenced by computeVarsCoverSOS1(), and getBoundConsFromVertices().
|
static |
gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph
scip | SCIP pointer |
conflictgraph | conflict graph |
sol | primal solution, or NULL for current LP/pseudo solution |
node | node of the conflict graph |
Definition at line 484 of file cons_sos1.c.
References assert(), nodedata, NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), SCIPvarGetLbLocal(), and sol.
Referenced by getDiveBdChgsSOS1conflictgraph(), TCLIQUE_NEWSOL(), and updateWeightsTCliquegraph().
|
static |
gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph
scip | SCIP pointer |
conflictgraph | conflict graph |
sol | primal solution, or NULL for current LP/pseudo solution |
node | node of the conflict graph |
Definition at line 511 of file cons_sos1.c.
References assert(), nodedata, NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), SCIPvarGetUbLocal(), and sol.
Referenced by getDiveBdChgsSOS1conflictgraph(), TCLIQUE_NEWSOL(), and updateWeightsTCliquegraph().
|
static |
returns whether variable is part of the SOS1 conflict graph
conshdlrdata | SOS1 constraint handler |
var | variable |
Definition at line 538 of file cons_sos1.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIPhashmapExists(), TRUE, and var.
Referenced by checkLinearConssVarboundSOS1(), and SCIPvarIsSOS1().
|
static |
returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph
conshdlrdata | SOS1 constraint handler |
var | variable |
Definition at line 555 of file cons_sos1.c.
References assert(), NULL, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and var.
Referenced by checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), detectVarboundSOS1(), enforceConflictgraph(), genConflictgraphLinearCons(), generateBoundInequalityFromSOS1Cons(), getSOS1Implications(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), SCIP_DECL_CONSPROP(), SCIPvarGetNodeSOS1(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
|
static |
fix variable in given node to 0 or add constraint if variable is multi-aggregated
scip | SCIP pointer |
var | variable to be fixed to 0 |
node | node |
infeasible | if fixing is infeasible |
Definition at line 576 of file cons_sos1.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), enforceConssSOS1(), and getBranchingDecisionStrongbranchSOS1().
|
static |
try to fix variable to 0
Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
\[x = \sum_{i=1}^n \alpha_i x_i + c, \]
we can express the fixing \(x = 0\) by fixing all \(x_i\) to 0 if \(c = 0\) and the lower bounds of \(x_i\) are nonnegative if \(\alpha_i > 0\) or the upper bounds are nonpositive if \(\alpha_i < 0\).
scip | SCIP pointer |
var | variable to be fixed to 0 |
infeasible | if fixing is infeasible |
tightened | if fixing was performed |
Definition at line 631 of file cons_sos1.c.
References assert(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPfixVar(), SCIPflattenVarAggregationGraph(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by presolRoundConsSOS1().
|
static |
fix variable in local node to 0, and return whether the operation was feasible
scip | SCIP pointer |
var | variable to be fixed to 0 |
cons | constraint |
inferinfo | info for reverse prop. |
infeasible | if fixing is infeasible |
tightened | if fixing was performed |
success | whether fixing was successful, i.e., variable is not multi-aggregated |
Definition at line 705 of file cons_sos1.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by propConsSOS1(), and propVariableNonzero().
|
static |
add lock on variable
scip | SCIP data structure |
cons | constraint |
var | variable |
Definition at line 748 of file cons_sos1.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and var.
Referenced by handleNewVariableSOS1(), and presolRoundConsSOS1().
|
static |
remove lock on variable
scip | SCIP data structure |
cons | constraint |
var | variable |
Definition at line 768 of file cons_sos1.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and var.
Referenced by deleteVarSOS1(), and presolRoundConsSOS1().
|
static |
ensures that the vars and weights array can store at least num entries
scip | SCIP data structure |
consdata | constraint data |
num | minimum number of entries to store |
reserveWeights | whether the weights array is handled |
Definition at line 788 of file cons_sos1.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addVarSOS1(), and appendVarSOS1().
|
static |
handle new variable
scip | SCIP data structure |
cons | constraint |
consdata | constraint data |
conshdlrdata | constraint handler data |
var | variable |
transformed | whether original variable was transformed |
Definition at line 816 of file cons_sos1.c.
References assert(), EVENTHDLR_EVENT_TYPE, lockVariableSOS1(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPdebugMsg, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPsortInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, var, varGetNodeSOS1(), and vars.
Referenced by addVarSOS1(), appendVarSOS1(), and SCIPcreateConsSOS1().
|
static |
adds a variable to an SOS1 constraint, at position given by weight - ascending order
scip | SCIP data structure |
cons | constraint |
conshdlrdata | constraint handler data |
var | variable to add to the constraint |
weight | weight to determine position |
Definition at line 951 of file cons_sos1.c.
References assert(), consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), TRUE, and var.
Referenced by addBranchingComplementaritiesSOS1(), performImplicationGraphAnalysis(), and SCIPaddVarSOS1().
|
static |
appends a variable to an SOS1 constraint
scip | SCIP data structure |
cons | constraint |
conshdlrdata | constraint handler data |
var | variable to add to the constraint |
Definition at line 1021 of file cons_sos1.c.
References assert(), consdataEnsurevarsSizeSOS1(), FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), SCIPvarIsTransformed(), TRUE, and var.
Referenced by SCIPappendVarSOS1().
|
static |
deletes a variable of an SOS1 constraint
scip | SCIP data structure |
cons | constraint |
consdata | constraint data |
eventhdlr | corresponding event handler |
pos | position of variable in array |
Definition at line 1079 of file cons_sos1.c.
References assert(), EVENTHDLR_EVENT_TYPE, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1().
Referenced by presolRoundConsSOS1().
|
static |
extends a given clique of the conflict graph
Implementation of the Bron-Kerbosch Algorithm from the paper: Algorithm 457: Finding all Cliques of an Undirected Graph, Bron & Kerbosch, Commun. ACM, 1973
scip | SCIP pointer |
conshdlrdata | constraint handler data |
adjacencymatrix | adjacencymatrix of the conflict graph (only lower half filled) |
vertexcliquegraph | graph that contains the information which cliques contain a given vertex vertices of variables = 0, ..., nsos1vars-1; vertices of cliques = nsos1vars, ..., nsos1vars+ncliques-1 |
nsos1vars | number of SOS1 variables |
nconss | number of SOS1 constraints |
cons | constraint to be extended |
vars | variables of extended clique |
weights | weights of extended clique |
firstcall | whether this is the first call of extension operator |
usebacktrack | whether backtracking is needed for the computation |
cliques | all cliques found so far |
ncliques | number of clique found so far |
cliquesizes | number of variables of current clique |
newclique | clique we want to extended |
workingset | set of vertices that already served as extension and set of candidates that probably will lead to an extension |
nworkingset | length of array workingset |
nexts | number of vertices that already served as extension |
pos | position of potential candidate |
maxextensions | maximal number of extensions |
naddconss | number of added constraints |
success | pointer to store if at least one new clique was found |
Definition at line 1118 of file cons_sos1.c.
References assert(), extensionOperatorSOS1(), FALSE, i, isConnectedSOS1(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), TRUE, vars, and w.
Referenced by extensionOperatorSOS1(), and presolRoundConssSOS1().
|
static |
generates conflict graph that is induced by the variables of a linear constraint
conshdlrdata | constraint handler data |
conflictgraphlin | conflict graph of linear constraint (nodes: 1, ..., nlinvars) |
conflictgraphorig | original conflict graph (nodes: 1, ..., nsos1vars) |
linvars | linear variables in linear constraint |
nlinvars | number of linear variables in linear constraint |
posinlinvars | posinlinvars[i] = position (index) of SOS1 variable i in linear constraint, posinlinvars[i]= -1 if i is not a SOS1 variable or not a variable of the linear constraint |
Definition at line 1379 of file cons_sos1.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().
Referenced by tightenVarsBoundsSOS1().
|
static |
determine the common successors of the vertices from the considered clique
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
clique | current clique |
vars | clique variables |
nvars | number of clique variables |
comsucc | pointer to store common successors of clique vertices (size = nvars) |
ncomsucc | pointer to store number common successors of clique vertices |
Definition at line 1432 of file cons_sos1.c.
References assert(), i, NULL, nvars, SCIP_INVALIDDATA, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), varGetNodeSOS1(), and vars.
Referenced by presolRoundConssSOS1().
|
static |
get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero
scip | SCIP pointer |
conshdlrdata | constraint handler data |
vars | problem and SOS1 variables |
implgraph | implication graph (j is successor of i if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)) |
implhash | hash map from variable to node in implication graph |
implnodes | implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero |
node | node of the implication graph |
Definition at line 1533 of file cons_sos1.c.
References assert(), getSOS1Implications(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImageInt(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, varGetNodeSOS1(), and vars.
Referenced by getSOS1Implications(), and tightenVarsBoundsSOS1().
|
static |
perform one presolving round for a single SOS1 constraint
We perform the following presolving steps.
scip | SCIP pointer |
cons | constraint |
consdata | constraint data |
eventhdlr | event handler |
substituted | whether a variable was substituted |
cutoff | whether a cutoff happened |
success | whether we performed a successful reduction |
ndelconss | number of deleted constraints |
nupgdconss | number of upgraded constraints |
nfixedvars | number of fixed variables |
nremovedvars | number of variables removed |
Definition at line 1599 of file cons_sos1.c.
References assert(), cutoff, deleteVarSOS1(), EVENTHDLR_EVENT_TYPE, FALSE, fixVariableZero(), lockVariableSOS1(), NULL, nvars, 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, unlockVariableSOS1(), var, and vars.
Referenced by presolRoundConssSOS1().
|
static |
perform one presolving round for all SOS1 constraints
We perform the following presolving steps.
If the adjacency matrix of the conflict graph is present, then we perform the following additional presolving steps
scip | SCIP pointer |
eventhdlr | event handler |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
adjacencymatrix | adjacency matrix of conflict graph (or NULL) |
conss | SOS1 constraints |
nconss | number of SOS1 constraints |
nsos1vars | number of SOS1 variables |
naddconss | number of added constraints |
ndelconss | number of deleted constraints |
nupgdconss | number of upgraded constraints |
nfixedvars | number of fixed variables |
nremovedvars | number of variables removed |
result | result |
Definition at line 1825 of file cons_sos1.c.
References assert(), c, cliqueGetCommonSuccessorsSOS1(), cutoff, extensionOperatorSOS1(), FALSE, MAX, NULL, nvars, presolRoundConsSOS1(), result, 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, varGetNodeSOS1(), and vars.
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
performs implication graph analysis
Tentatively fixes a variable to nonzeero and extracts consequences from it:
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
totalvars | problem and SOS1 variables |
implgraph | implication graph (j is successor of i if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)) |
implhash | hash map from variable to node in implication graph |
adjacencymatrix | adjacencymatrix of the conflict graph (only lower half filled) |
givennode | node of the conflict graph |
nonznode | node of the conflict graph that is implied to be nonzero if given node is nonzero |
impllbs | current lower variable bounds if given node is nonzero (update possible) |
implubs | current upper variable bounds if given node is nonzero (update possible) |
implnodes | indicates which variables are currently implied to be nonzero if given node is nonzero (update possible) |
naddconss | pointer to store number of added SOS1 constraints |
probingdepth | pointer to store current probing depth |
infeasible | pointer to store whether the subproblem gets infeasible if variable to 'nonznode' is nonzero |
Definition at line 2097 of file cons_sos1.c.
References addVarSOS1(), assert(), FALSE, isConnectedSOS1(), NULL, performImplicationGraphAnalysis(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, 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().
|
static |
returns whether node is implied to be zero; this information is taken from the input array 'implnodes'
conflictgraph | conflict graph |
implnodes | implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero |
node | node of the conflict graph (or -1) |
Definition at line 2255 of file cons_sos1.c.
References FALSE, SCIP_Bool, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and TRUE.
Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().
|
static |
updates arc data of implication graph
scip | SCIP pointer |
implgraph | implication graph |
implhash | hash map from variable to node in implication graph |
totalvars | problem and SOS1 variables |
varv | variable that is assumed to be nonzero |
varw | implication variable |
lb | old lower bound of \(x_w\) |
ub | old upper bound of \(x_w\) |
newbound | new bound of \(x_w\) |
lower | whether to consider lower bound implication (otherwise upper bound) |
nchgbds | pointer to store number of changed bounds |
update | pointer to store whether implication graph has been updated |
infeasible | pointer to store whether an infeasibility has been detected |
Definition at line 2284 of file cons_sos1.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPceil(), SCIPdebugMsg, SCIPdigraphAddArc(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfloor(), SCIPhashmapGetImageInt(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), SCIPvarIsIntegral(), and TRUE.
Referenced by updateImplicationGraphSOS1().
|
static |
updates implication graph
Assume the variable from the input is nonzero. If this implies that some other variable is also nonzero, then store this information in an implication graph
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
adjacencymatrix | adjacency matrix of conflict graph (lower half) |
implgraph | implication graph ( \(j\) is successor of \(i\) if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)) |
implhash | hash map from variable to node in implication graph |
implnodes | implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero |
totalvars | problem and SOS1 variables |
cliquecovers | clique covers of linear constraint |
cliquecoversizes | size of clique covers |
varincover | array with varincover[i] = cover of SOS1 index \(i\) |
vars | variables to be checked |
coefs | coefficients of variables in linear constraint |
nvars | number of variables to be checked |
bounds | bounds of variables |
var | variable that is assumed to be nonzero |
bound | bound of variable |
boundnonzero | bound of variable if it is known to be nonzero if infinity values are not summarized |
ninftynonzero | number of times infinity/-infinity has to be summarized to boundnonzero |
lower | TRUE if lower bounds are consideres; FALSE for upper bounds |
nchgbds | pointer to store number of changed bounds |
update | pointer to store whether implication graph has been updated |
infeasible | pointer to store whether an infeasibility has been detected |
Definition at line 2410 of file cons_sos1.c.
References assert(), bound, FALSE, isConnectedSOS1(), isImpliedZero(), NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, updateArcData(), var, varGetNodeSOS1(), vars, and w.
Referenced by tightenVarsBoundsSOS1().
|
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
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 assert(), isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasLT(), and TRUE.
Referenced by tightenVarsBoundsSOS1().
|
static |
try to tighten upper and lower bounds for variables
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
implgraph | implication graph (j is successor of i if and only if \( x_i\not = 0 \) implies a new lower/upper bound for \( x_j\)) |
implhash | hash map from variable to node in implication graph |
adjacencymatrix | adjacencymatrix of conflict graph |
totalvars | problem and SOS1 vars |
ntotalvars | number of problem and SOS1 variables |
nsos1vars | number of SOS1 variables |
nchgbds | pointer to store number of changed bounds |
implupdate | pointer to store whether the implication graph has been updated in this function call |
cutoff | pointer to store if current nodes LP is infeasible |
Definition at line 2683 of file cons_sos1.c.
References assert(), c, computeVarsCoverSOS1(), cutoff, FALSE, genConflictgraphLinearCons(), getSOS1Implications(), i, 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(), var, varGetNodeSOS1(), and w.
Referenced by initImplGraphSOS1(), and presolRoundVarsSOS1().
|
static |
perform one presolving round for variables
We perform the following presolving steps:
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
adjacencymatrix | adjacencymatrix of conflict graph |
nsos1vars | number of SOS1 variables |
nfixedvars | pointer to store number of fixed variables |
nchgbds | pointer to store number of changed bounds |
naddconss | pointer to store number of addded constraints |
result | result |
Definition at line 3364 of file cons_sos1.c.
References assert(), cutoff, FALSE, i, performImplicationGraphAnalysis(), result, 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(), TRUE, and var.
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
propagate variables of SOS1 constraint
scip | SCIP pointer |
cons | constraint |
consdata | constraint data |
cutoff | whether a cutoff happened |
ngen | number of domain changes |
Definition at line 3538 of file cons_sos1.c.
References assert(), cutoff, FALSE, inferVariableZero(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, and vars.
Referenced by enforceConflictgraph(), enforceConssSOS1(), and SCIP_DECL_CONSPROP().
|
static |
propagate a variable that is known to be nonzero
scip | SCIP pointer |
conflictgraph | conflict graph |
implgraph | implication graph |
cons | some arbitrary SOS1 constraint |
node | conflict graph node of variable that is known to be nonzero |
implprop | whether implication graph propagation shall be applied |
cutoff | whether a cutoff happened |
ngen | number of domain changes |
Definition at line 3636 of file cons_sos1.c.
References assert(), cutoff, 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(), TRUE, and var.
Referenced by SCIP_DECL_CONSPROP().
|
static |
initialize implication graph
j
is successor of i
if and only if \( x_i\not = 0 \Rightarrow x_j\not = 0\)
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
nsos1vars | number of SOS1 variables |
maxrounds | maximal number of propagation rounds for generating implications |
nchgbds | pointer to store number of bound changes |
cutoff | pointer to store whether a cutoff occurred |
success | whether initialization was successful |
Definition at line 3779 of file cons_sos1.c.
References assert(), cutoff, FALSE, i, 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(), TRUE, and var.
Referenced by SCIP_DECL_CONSPROP(), and sepaImplBoundCutsSOS1().
|
static |
deinitialize implication graph
scip | SCIP pointer |
conshdlrdata | constraint handler data |
Definition at line 3950 of file cons_sos1.c.
References assert(), nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPdigraphSetNodeData(), and SCIPfreeBlockMemory.
Referenced by SCIP_DECL_CONSEXITSOL().
|
static |
get the vertices whose neighbor set covers a subset of the neighbor set of a given other vertex.
This function can be used to compute sets of variables to branch on.
conflictgraph | conflict graph |
verticesarefixed | array that indicates which variables are currently fixed to zero |
vertex | vertex (-1 if not needed) |
neightocover | neighbors of given vertex to be covered (or NULL if all neighbors shall be covered) |
nneightocover | number of entries of neightocover (or 0 if all neighbors shall be covered ) |
coververtices | array to store the vertices whose neighbor set covers the neighbor set of the given vertex |
ncoververtices | pointer to store size of coververtices |
Definition at line 4009 of file cons_sos1.c.
References assert(), NULL, SCIP_Bool, SCIP_OKAY, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().
Referenced by addBranchingComplementaritiesSOS1(), and getBranchingVerticesSOS1().
|
static |
get vertices of variables that will be fixed to zero for each node
scip | SCIP pointer |
conflictgraph | conflict graph |
sol | solution to be enforced (NULL for LP solution) |
verticesarefixed | vector that indicates which variables are currently fixed to zero |
bipbranch | TRUE if bipartite branching method should be used |
branchvertex | branching vertex |
fixingsnode1 | vertices of variables that will be fixed to zero for the first node |
nfixingsnode1 | pointer to store number of fixed variables for the first node |
fixingsnode2 | vertices of variables that will be fixed to zero for the second node |
nfixingsnode2 | pointer to store number of fixed variables for the second node |
Definition at line 4116 of file cons_sos1.c.
References assert(), FALSE, getCoverVertices(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), sol, and TRUE.
Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), and getBranchingPrioritiesSOS1().
|
static |
gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
sol | solution to be enforced (NULL for LP solution) |
nsos1vars | number of SOS1 variables |
verticesarefixed | vector that indicates which variables are currently fixed to zero |
bipbranch | TRUE if bipartite branching method should be used |
fixingsnode1 | vertices of variables that will be fixed to zero for the first node (size = nsos1vars) |
fixingsnode2 | vertices of variables that will be fixed to zero for the second node (size = nsos1vars) |
branchpriors | pointer to store branching priorities (size = nsos1vars) or NULL if not needed |
vertexbestprior | pointer to store vertex with the best branching priority or NULL if not needed |
relsolfeas | pointer to store if LP relaxation solution is feasible |
Definition at line 4229 of file cons_sos1.c.
References assert(), FALSE, getBranchingVerticesSOS1(), i, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), sol, and TRUE.
Referenced by enforceConflictgraph(), and getBranchingDecisionStrongbranchSOS1().
|
static |
performs strong branching with given domain fixings
scip | SCIP pointer |
conflictgraph | conflict graph |
fixingsexec | vertices of variables to be fixed to zero for this strong branching execution |
nfixingsexec | number of vertices of variables to be fixed to zero for this strong branching execution |
fixingsop | vertices of variables to be fixed to zero for the opposite strong branching execution |
nfixingsop | number of vertices of variables to be fixed to zero for the opposite strong branching execution |
inititer | maximal number of LP iterations to perform |
fixnonzero | shall opposite variable (if positive in sign) fixed to the feasibility tolerance (only possible if nfixingsop = 1) |
domainfixings | vertices that can be used to reduce the domain (should have size equal to number of variables) |
ndomainfixings | pointer to store number of vertices that can be used to reduce the domain, could be filled by earlier calls |
infeasible | pointer to store whether branch is infeasible |
objval | pointer to store objective value of LP with fixed variables (SCIP_INVALID if reddomain = TRUE or lperror = TRUE) |
lperror | pointer to store whether an unresolved LP error or a strange solution status occurred |
Definition at line 4333 of file cons_sos1.c.
References assert(), FALSE, i, lperror, NULL, objval, SCIP_Bool, 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(), TRUE, and var.
Referenced by getBranchingDecisionStrongbranchSOS1().
|
static |
apply strong branching to determine the vertex for the next branching decision
scip | SCIP pointer |
conshdlrdata | SOS1 constraint handler data |
conflictgraph | conflict graph |
sol | solution to be enforced (NULL for LP solution) |
nsos1vars | number of SOS1 variables |
lpobjval | current LP relaxation solution |
bipbranch | TRUE if bipartite branching method should be used |
nstrongrounds | number of strong branching rounds |
verticesarefixed | vector that indicates which variables are currently fixed to zero |
fixingsnode1 | pointer to store vertices of variables that will be fixed to zero for the first node (size = nsos1vars) |
fixingsnode2 | pointer to store vertices of variables that will be fixed to zero for the second node (size = nsos1vars) |
vertexbestprior | pointer to store vertex with the best strong branching priority |
bestobjval1 | pointer to store LP objective for left child node of branching decision with best priority |
bestobjval2 | pointer to store LP objective for right child node of branching decision with best priority |
result | pointer to store result of strong branching |
Definition at line 4475 of file cons_sos1.c.
References assert(), FALSE, fixVariableZeroNode(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), i, lperror, MAX, MIN, nlpiterations, nlps, NULL, performStrongbranchSOS1(), REALABS, result, 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(), SCIPsortDownRealInt(), and sol.
Referenced by enforceConflictgraph().
|
static |
for two given vertices v1
and v2
search for a clique in the conflict graph that contains these vertices. From this clique, we create a bound constraint.
scip | SCIP pointer |
conflictgraph | conflict graph |
sol | solution to be enforced (NULL for LP solution) |
v1 | first vertex that shall be contained in bound constraint |
v2 | second vertex that shall be contained in bound constraint |
boundvar | bound variable of v1 and v2 (or NULL if not existent) |
extend | should v1 and v2 be greedily extended to a clique of larger size |
cons | bound constraint |
feas | feasibility value of bound constraint |
Definition at line 4692 of file cons_sos1.c.
References assert(), 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(), sol, TRUE, and var.
Referenced by addBranchingComplementaritiesSOS1().
|
static |
tries to add feasible complementarity constraints to a given child branching node.
scip | SCIP pointer |
node | branching node |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph of the current node |
localconflicts | local conflicts (updates to local conflicts of child node) |
sol | solution to be enforced (NULL for LP solution) |
nsos1vars | number of SOS1 variables |
verticesarefixed | vector that indicates which variables are currently fixed to zerox |
fixingsnode1 | vertices of variables that will be fixed to zero for the branching node in the input of this function |
nfixingsnode1 | number of entries of array nfixingsnode1 |
fixingsnode2 | vertices of variables that will be fixed to zero for the other branching node |
nfixingsnode2 | number of entries of array nfixingsnode2 |
naddedconss | pointer to store the number of added SOS1 constraints |
onlyviolsos1 | should only SOS1 constraints be added that are violated by the LP solution |
Definition at line 4920 of file cons_sos1.c.
References addVarSOS1(), assert(), FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getCoverVertices(), i, 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(), sol, and TRUE.
Referenced by enforceConflictgraph().
|
static |
resets local conflict graph to the conflict graph of the root node
conflictgraph | conflict graph of root node |
localconflicts | local conflicts that should be removed from conflict graph |
nsos1vars | number of SOS1 variables |
Definition at line 5284 of file cons_sos1.c.
References SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminusInt(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors().
Referenced by enforceConflictgraph().
|
static |
Conflict graph enforcement method
The conflict graph can be enforced by different branching rules:
i
, i.e., in one branch \(x_i\) is fixed to zero and in the other its neighbors from the conflict graph.We make use of different selection rules that define on which system of SOS1 variables to branch next:
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conshdlr | constraint handler |
nconss | number of constraints |
conss | SOS1 constraints |
sol | solution to be enforced (NULL for LP solution) |
result | result |
Definition at line 5340 of file cons_sos1.c.
References addBranchingComplementaritiesSOS1(), assert(), c, cutoff, FALSE, fixVariableZeroNode(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), i, isConnectedSOS1(), MAX, MIN, NULL, nvars, propConsSOS1(), resetConflictgraphSOS1(), result, 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(), sol, TRUE, var, varGetNodeSOS1(), and vars.
Referenced by enforceSOS1().
|
static |
SOS1 branching enforcement method
We check whether the current solution is feasible, i.e., contains at most one nonzero variable. If not, we branch along the lines indicated by Beale and Tomlin:
We first compute \(W = \sum_{j=1}^n |x_i|\) and \(w = \sum_{j=1}^n j\, |x_i|\). Then we search for the index \(k\) that satisfies
\[ k \leq \frac{w}{W} < k+1. \]
The branches are then
\[ x_1 = 0, \ldots, x_k = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0. \]
If the constraint contains two variables, the branching of course simplifies.
Depending on the parameters (branchnonzeros
, branchweight
) there are three ways to choose the branching constraint.
branchnonzeros | branchweight | constraint chosen |
true | ? | most number of nonzeros |
false | true | maximal weight corresponding to nonzero variable |
false | true | largest sum of variable values |
branchnonzeros
= false
, branchweight
= true
allows the user to specify an order for the branching importance of the constraints (setting the weights accordingly).
Constraint branching can also be turned off using parameter branchsos
.
scip | SCIP pointer |
conshdlr | constraint handler |
nconss | number of constraints |
conss | indicator constraints |
sol | solution to be enforced (NULL for LP solution) |
result | result |
Definition at line 5812 of file cons_sos1.c.
References assert(), branchCons(), c, cutoff, fixVariableZeroNode(), NULL, nvars, propConsSOS1(), REALABS, result, 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(), sol, vars, and w.
Referenced by enforceSOS1().
|
static |
constraint enforcing method of constraint handler
scip | SCIP pointer |
conshdlr | constraint handler |
nconss | number of constraints |
conss | indicator constraints |
sol | solution to be enforced (NULL for LP solution) |
result | result |
Definition at line 6058 of file cons_sos1.c.
References assert(), enforceConflictgraph(), enforceConssSOS1(), NULL, result, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIPconshdlrGetData(), SCIPerrorMessage, and sol.
Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().
|
static |
initialitze tclique graph and create clique data
scip | SCIP pointer |
conshdlr | constraint handler |
conshdlrdata | constraint handler data |
conflictgraph | conflict graph |
nsos1vars | number of SOS1 variables |
Definition at line 6121 of file cons_sos1.c.
References TCLIQUE_Data::conflictgraph, TCLIQUE_Data::conshdlr, i, 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().
|
static |
update weights of tclique graph
scip | SCIP pointer |
conshdlrdata | constraint handler data |
tcliquedata | tclique data |
conflictgraph | conflict graph |
sol | LP solution to be separated (or NULL) |
nsos1vars | number of SOS1 variables |
Definition at line 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(), sol, tcliqueChangeWeight(), and var.
Referenced by sepaBoundInequalitiesFromGraph().
|
static |
adds bound cut(s) to separation storage
scip | SCIP pointer |
tcliquedata | clique data |
rowlb | row for lower bounds (or NULL) |
rowub | row for upper bounds (or NULL) |
success | pointer to store if bound cut was added |
cutoff | pointer to store if a cutoff occurred |
Definition at line 6250 of file cons_sos1.c.
References assert(), cutoff, 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().
|
static |
Generate bound constraint
We generate the row corresponding to the following simple valid inequalities:
\[ \frac{x_1}{u_1} + \ldots + \frac{x_n}{u_n} \leq 1\qquad\mbox{and}\qquad \frac{x_1}{\ell_1} + \ldots + \frac{x_n}{\ell_1} \leq 1, \]
where \(\ell_1, \ldots, \ell_n\) and \(u_1, \ldots, u_n\) are the nonzero and finite lower and upper bounds of the variables \(x_1, \ldots, x_n\). If an upper bound < 0 or a lower bound > 0, the constraint itself is redundant, so the cut is not applied (lower bounds > 0 and upper bounds < 0 are usually detected in presolving or propagation). Infinite bounds and zero are skipped. Thus \(\ell_1, \ldots, \ell_n\) are all negative, which results in the \(\leq\) inequality. In case of the presence of variable upper bounds, the bound inequality can be further strengthened.
Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most interesting.
scip | SCIP pointer |
conshdlr | constraint handler |
conflictgraph | conflict graph |
nodes | conflict graph nodes for bound constraint |
nnodes | number of conflict graph nodes for bound constraint |
rhs | right hand side of bound constraint |
local | in any case produce a local cut (even if local bounds of variables are valid globally) |
global | in any case produce a global cut |
strengthen | whether trying to strengthen bound constraint |
removable | should the inequality be removed from the LP due to aging or cleanup? |
nameext | part of name of bound constraints |
rowlb | output: row for lower bounds (or NULL if not needed) |
rowub | output: row for upper bounds (or NULL if not needed) |
Definition at line 6324 of file cons_sos1.c.
References assert(), 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(), TRUE, var, and vars.
Referenced by generateBoundInequalityFromSOS1Cons(), and 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(), assert(), bound, cutoff, FALSE, generateBoundInequalityFromSOS1Nodes(), i, 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(), sol, TRUE, and var.
|
static |
separate bound inequalities from conflict graph
scip | SCIP pointer |
conshdlr | constraint handler |
conshdlrdata | constraint handler data |
sol | LP solution to be separated (or NULL) |
maxboundcuts | maximal number of bound cuts separated per separation round (-1: no limit) |
ngen | pointer to store number of cuts generated |
cutoff | pointer whether a cutoff occurred |
Definition at line 6749 of file cons_sos1.c.
References assert(), cutoff, TCLIQUE_Data::cutoff, FALSE, TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), sol, TCLIQUE_Data::sol, tcliqueMaxClique(), and updateWeightsTCliquegraph().
Referenced by separateSOS1().
|
static |
Generate a bound constraint from the variables of an SOS1 constraint (see generateBoundInequalityFromSOS1Nodes() for more information)
scip | SCIP pointer |
conshdlr | constraint handler |
cons | SOS1 constraint |
local | in any case produce a local cut (even if local bounds of variables are valid globally) |
global | in any case produce a global cut |
strengthen | whether trying to strengthen bound constraint |
removable | should the inequality be removed from the LP due to aging or cleanup? |
rowlb | output: row for lower bounds (or NULL if not needed) |
rowub | output: row for upper bounds (or NULL if not needed) |
Definition at line 6823 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, generateBoundInequalityFromSOS1Nodes(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varGetNodeSOS1().
Referenced by initsepaBoundInequalityFromSOS1Cons().
|
static |
initialize or separate bound inequalities from SOS1 constraints
scip | SCIP pointer |
conshdlr | constraint handler |
conshdlrdata | constraint handler data |
conss | SOS1 constraints |
nconss | number of SOS1 constraints |
sol | LP solution to be separated (or NULL) |
solvedinitlp | TRUE if initial LP relaxation at a node is solved |
maxboundcuts | maximal number of bound cuts separated per separation round (-1: no limit) |
ngen | pointer to store number of cuts generated (or NULL) |
cutoff | pointer to store whether a cutoff occurred |
Definition at line 6886 of file cons_sos1.c.
References assert(), c, cutoff, FALSE, generateBoundInequalityFromSOS1Cons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMsg, SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIProwIsInLP(), sol, and TRUE.
Referenced by SCIP_DECL_CONSINITLP(), and separateSOS1().
|
static |
separate implied bound cuts
scip | SCIP pointer |
conshdlr | constraint handler |
conshdlrdata | constraint handler data |
sol | LP solution to be separated (or NULL) |
maxcuts | maximal number of implied bound cuts separated per separation round (-1: no limit) |
ngen | pointer to store number of cuts generated |
cutoff | pointer whether a cutoff occurred |
Definition at line 7000 of file cons_sos1.c.
References assert(), cutoff, FALSE, i, 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(), sol, TRUE, and var.
Referenced by separateSOS1().
|
static |
separates SOS1 constraints for arbitrary solutions
scip | SCIP pointer |
conshdlr | constraint handler |
sol | solution to be separated (or NULL) |
nconss | number of constraints |
conss | SOS1 constraints |
result | result |
Definition at line 7225 of file cons_sos1.c.
References assert(), cutoff, depth, initsepaBoundInequalityFromSOS1Cons(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPgetDepth(), SCIPisStopped(), sepaBoundInequalitiesFromGraph(), sepaImplBoundCutsSOS1(), sol, and TRUE.
Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
|
static |
gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem
scip | SCIP pointer |
sol | primal solution or NULL for current LP solution |
conflictgraph | conflict graph |
nsos1vars | number of SOS1 variables |
indicatorzero | vector that indicates which variables are currently fixed to zero |
weights | pointer to store weights determining the order of the variables (length = nsos1vars) |
Definition at line 7346 of file cons_sos1.c.
References assert(), i, MIN, NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPsumepsilon(), sol, and var.
Referenced by maxWeightIndSetHeuristic().
|
static |
scip | SCIP pointer |
conshdlr | SOS1 constraint handler |
conflictgraph | conflict graph |
node | node of the conflict graph |
mark | indicator vector of processed nodes |
indset | indicator vector of current independent |
cnt | pointer to store number of marked nodes |
cutoff | pointer to store whether operation is infeasible |
Definition at line 7417 of file cons_sos1.c.
References assert(), cutoff, FALSE, markNeighborsMWISHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_NEGATED, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetAggrConstant(), SCIPvarGetAggrVar(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetNodeSOS1(), SCIPvarGetStatus(), TRUE, and var.
Referenced by markNeighborsMWISHeuristic(), and maxWeightIndSetHeuristic().
|
static |
calls greedy algorithm for the maximum weighted independent set problem (MWIS)
We compute a feasible solution to
\[ \begin{array}{ll} \min\limits_{z} & {x^*}^T z \\ & z_i + z_j \leq 1, \qquad (i,j)\in E \\ & z_i \in \{0,1\}, \qquad\quad i\in V \end{array} \]
by the algorithm GGWMIN of Shuichi Sakai, Mitsunori Togasaki and Koichi Yamazaki in "A note on greedy algorithms for the maximum weighted independent set problem", Discrete Applied Mathematics. Here \(x^*\) denotes the current LP relaxation solution. Note that the solution of the MWIS is the indicator vector of an independent set.
scip | SCIP pointer |
sol | primal solution or NULL for current LP solution |
conshdlr | SOS1 constraint handler |
conflictgraph | conflict graph |
nsos1vars | number of SOS1 variables |
indicatorzero | vector that indicates which variables are currently fixed to zero |
indset | pointer to store indicator vector of an independent set |
Definition at line 7558 of file cons_sos1.c.
References assert(), cutoff, FALSE, getVectorOfWeights(), i, markNeighborsMWISHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownRealInt(), sol, and TRUE.
Referenced by 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
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 assert(), c, 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(), sol, TRUE, and var.
Referenced by SCIPmakeSOS1sFeasible().
|
static |
based on solution values of the variables, fixes variables of the SOS1 constraints to zero to turn these constraints feasible
if the SOS1 constraints overlap, the method makeSOS1constraintsFeasible() may result in better primal solutions
scip | SCIP pointer |
conshdlr | SOS1 constraint handler |
sol | solution |
changed | pointer to store whether the solution has been changed |
allroundable | pointer to store whether all variables are roundable |
Definition at line 7794 of file cons_sos1.c.
References assert(), c, FALSE, NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPgetSolVal(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), sol, TRUE, var, and vars.
Referenced by SCIPmakeSOS1sFeasible().
|
static |
determine a diving variables and boundchanges of diving variables by analyzing the conflict graph
if the SOS1 constraints do not overlap, the method getDiveBdChgsSOS1constraints() may be faster
scip | SCIP pointer |
conshdlr | SOS1 constraint handler |
diveset | diving settings |
sol | solution |
success | pointer to store |
Definition at line 7929 of file cons_sos1.c.
References assert(), bound, diveset, DIVINGCUTOFFVALUE, FALSE, isViolatedSOS1(), MIN, nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), NULL, REALABS, roundup, 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(), sol, TRUE, and var.
Referenced by SCIP_DECL_CONSGETDIVEBDCHGS().
|
static |
determine a diving variables and boundchanges of diving variables by analyzing the SOS1 constraints
if the SOS1 constraints overlap, the method getDiveBdChgsSOS1conflictgraph() may produce better results (e.g., due to more diving candidates)
scip | SCIP pointer |
conshdlr | SOS1 constraint handler |
diveset | diving settings |
sol | solution |
success | pointer to store |
Definition at line 8070 of file cons_sos1.c.
References assert(), bound, c, diveset, DIVINGCUTOFFVALUE, FALSE, MIN, NULL, nvars, REALABS, roundup, 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(), sol, TRUE, var, and vars.
Referenced by SCIP_DECL_CONSGETDIVEBDCHGS().
|
static |
check whether \(x_1\) is a bound variable of \(x_0\); i.e., \(x_0 \leq c\cdot x_1\) or \(x_0 \geq d\cdot x_1\) for positive values \(c, d\). If true, then add this information to the node data of the conflict graph.
scip | SCIP pointer |
conshdlrdata | SOS1 constraint handler data |
var0 | first variable |
var1 | second variable |
val0 | first coefficient |
val1 | second coefficient |
Definition at line 8251 of file cons_sos1.c.
References assert(), nodedata, NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1().
Referenced by checkLinearConssVarboundSOS1().
|
static |
pass connected component \(C\) of the conflict graph and check whether all the variables correspond to a unique variable upper bound variable \(z\), i.e., \(x_i \leq u_i z\) for every \(i\in C\).
scip | SCIP pointer |
conflictgraph | conflict graph |
node | current node of connected component |
boundvar | bound variable of connected component |
checklb | whether to check lower bound variable (else upper bound variable) |
processed | states for each variable whether it has been processed |
concomp | current connected component |
nconcomp | pointer to store number of elements of connected component |
unique | pointer to store whether bound variable is unique |
Definition at line 8327 of file cons_sos1.c.
References assert(), FALSE, nodedata, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE.
Referenced by checkConComponentsVarbound(), and passConComponentVarbound().
|
static |
for each connected component \(C\) of the conflict graph check whether all the variables correspond to a unique variable upper bound variable \(z\) (e.g., for the upper bound case this means that \(x_i \leq u_i z\) for every \(i\in C\)).
scip | SCIP pointer |
conflictgraph | conflict graph |
nsos1vars | number of SOS1 variables |
checklb | whether to check lower bound variable (else check upper bound variable) |
Definition at line 8400 of file cons_sos1.c.
References assert(), FALSE, nodedata, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, and TRUE.
Referenced by computeNodeDataSOS1().
|
static |
check all linear constraints for variable bound constraints of the form \(c\cdot z \leq x \leq d\cdot z\), where x
is some SOS1 variable and z
is some arbitrary variable (not necessarily binary)
scip | SCIP pointer |
conshdlrdata | SOS1 constraint handler data |
linconss | linear constraints |
nlinconss | number of linear constraints |
Definition at line 8489 of file cons_sos1.c.
References assert(), c, detectVarboundSOS1(), NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasZero(), varIsSOS1(), and vars.
Referenced by computeNodeDataSOS1().
|
static |
switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap
scip | SCIP pointer |
conshdlrdata | SOS1 constraint handler data |
conflictgraph | conflict graph |
conss | SOS1 constraints |
nconss | number of SOS1 constraints |
Definition at line 8562 of file cons_sos1.c.
References assert(), c, FALSE, i, NULL, nvars, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, varGetNodeSOS1(), and vars.
Referenced by SCIP_DECL_CONSINITSOL().
|
static |
sets node data of conflict graph nodes
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().
|
static |
initialize conflictgraph and create hashmap for SOS1 variables
scip | SCIP pointer |
conshdlrdata | constraint handler data |
conss | SOS1 constraints |
nconss | number of SOS1 constraints |
Definition at line 8680 of file cons_sos1.c.
References assert(), c, FALSE, i, nodedata, NULL, nvars, 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(), TRUE, var, and vars.
Referenced by SCIP_DECL_CONSINITSOL(), and SCIP_DECL_CONSPRESOL().
|
static |
free conflict graph, nodedata and hashmap
scip | SCIP pointer |
conshdlrdata | constraint handler data |
Definition at line 8875 of file cons_sos1.c.
References assert(), nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphSetNodeData(), SCIPfreeBlockMemory, and SCIPhashmapFree().
Referenced by SCIP_DECL_CONSEXITSOL(), and SCIP_DECL_CONSPRESOL().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 8921 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrSOS1(), TRUE, and valid.
|
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 assert(), CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.
|
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 assert(), checkSwitchNonoverlappingSOS1Methods(), computeNodeDataSOS1(), CONSHDLR_NAME, initConflictgraph(), initTCliquegraph(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPcreateDigraph().
|
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 assert(), c, CONSHDLR_NAME, freeConflictgraph(), freeImplGraphSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPdigraphFree(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPreleaseRow(), and tcliqueFree().
|
static |
frees specific constraint data
Definition at line 9085 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPdropVarEvent(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseRow().
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 9139 of file cons_sos1.c.
References assert(), 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().
|
static |
presolving method of constraint handler
Definition at line 9233 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, freeConflictgraph(), i, initConflictgraph(), NULL, presolRoundConssSOS1(), presolRoundVarsSOS1(), result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPfreeBufferArrayNull.
|
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 assert(), CONSHDLR_NAME, FALSE, initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().
|
static |
separation method of constraint handler for LP solutions
Definition at line 9377 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, NULL, result, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), and separateSOS1().
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 9393 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, NULL, result, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), separateSOS1(), and sol.
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 9409 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, enforceSOS1(), NULL, result, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 9425 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, enforceSOS1(), NULL, result, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), and sol.
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 9441 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, enforceSOS1(), NULL, result, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
|
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 assert(), c, CONSHDLR_NAME, NULL, result, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasZero(), SCIPprintCons(), SCIPresetConsAge(), SCIPupdateSolConsViolation(), SCIPvarGetName(), and sol.
|
static |
domain propagation method of constraint handler
Definition at line 9532 of file cons_sos1.c.
References assert(), c, CONSHDLR_NAME, cutoff, FALSE, initImplGraphSOS1(), NULL, propConsSOS1(), propVariableNonzero(), result, 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(), var, and varGetNodeSOS1().
|
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 assert(), CONSHDLR_NAME, FALSE, NULL, nvars, result, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPnodeGetVarSOS1(), and var.
|
static |
variable rounding lock method of constraint handler
Let lb and ub be the lower and upper bounds of a variable. Preprocessing usually makes sure that lb <= 0 <= ub.
Definition at line 9754 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, NULL, nvars, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), var, and vars.
|
static |
constraint display method of constraint handler
Definition at line 9800 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), and SCIPwriteVarName().
|
static |
constraint copying method of constraint handler
Definition at line 9830 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, NULL, nvars, propagate, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsSOS1(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetVarCopy(), TRUE, and valid.
|
static |
constraint parsing method of constraint handler
Definition at line 9894 of file cons_sos1.c.
References assert(), CONSHDLR_NAME, FALSE, NULL, propagate, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarSOS1(), SCIPconshdlrGetName(), SCIPcreateConsSOS1(), SCIPerrorMessage, SCIPparseVarName(), SCIPreleaseCons(), SCIPskipSpace(), TRUE, and var.
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 9984 of file cons_sos1.c.
References assert(), BMScopyMemoryArray, FALSE, NULL, nvars, SCIP_OKAY, SCIPconsGetData(), TRUE, and vars.
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 10007 of file cons_sos1.c.
References assert(), NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.
|
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 assert(), 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(), TRUE, and var.
|
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 assert(), CONSHDLR_NAME, diveset, FALSE, getDiveBdChgsSOS1conflictgraph(), getDiveBdChgsSOS1constraints(), NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPerrorMessage, and sol.
|
static |
constraint handler method which returns the permutation symmetry detection graph of a constraint
Definition at line 10190 of file cons_sos1.c.
References assert(), FALSE, i, NULL, nvars, 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.
|
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 assert(), FALSE, i, NULL, nvars, 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.