Scippy

SCIP

Solving Constraint Integer Programs

cons_sos1.c File Reference

Detailed Description

constraint handler for SOS type 1 constraints

Author
Tobias Fischer
Marc Pfetsch

A specially ordered set of type 1 (SOS1) is a sequence of variables such that at most one variable is nonzero. The special case of two variables arises, for instance, from equilibrium or complementary conditions like $x \cdot y = 0$. Note that it is in principle allowed that a variables appears twice, but it then can be fixed to 0.

This implementation of this constraint handler is based on classical ideas, see e.g.
"Special Facilities in General Mathematical Programming System for Non-Convex Problems Using Ordered Sets of Variables"
E. Beale and J. Tomlin, Proc. 5th IFORS Conference, 447-454 (1970)

The order of the variables is determined as follows:

  • If the constraint is created with SCIPcreateConsSOS1() and weights are given, the weights determine the order (decreasing weights). Additional variables can be added with SCIPaddVarSOS1(), which adds a variable with given weight.
  • If an empty constraint is created and then variables are added with SCIPaddVarSOS1(), weights are needed and stored.
  • All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are added with SCIPappendVarSOS1().

The validity of the SOS1 constraints can be enforced by different branching rules:

  • If classical SOS branching is used, branching is performed on only one SOS1 constraint. Depending on the parameters, there are two ways to choose this branching constraint. Either the constraint with the most number of nonzeros or the one with the largest nonzero-variable weight. The later version allows the user to specify an order for the branching importance of the constraints. Constraint branching can also be turned off.
  • Another way is to branch on the neighborhood of a single variable i, i.e., in one branch $x_i$ is fixed to zero and in the other its neighbors from the conflict graph.
  • If bipartite branching is used, then we branch using complete bipartite subgraphs of the conflict graph, i.e., in one branch fix the variables from the first bipartite partition and the variables from the second bipartite partition in the other.
  • In addition to variable domain fixings, it is sometimes also possible to add new SOS1 constraints to the branching nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.

Definition in file cons_sos1.c.

#include <assert.h>
#include "scip/cons_sos1.h"
#include "scip/cons_linear.h"
#include "scip/cons_setppc.h"
#include "scip/pub_misc.h"
#include "scip/misc.h"
#include "scip/struct_misc.h"
#include "tclique/tclique.h"
#include <string.h>
#include <ctype.h>

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "SOS1"
 
#define CONSHDLR_DESC   "SOS1 constraint handler"
 
#define CONSHDLR_SEPAPRIORITY   1000
 
#define CONSHDLR_ENFOPRIORITY   100
 
#define CONSHDLR_CHECKPRIORITY   -10
 
#define CONSHDLR_SEPAFREQ   10
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM
 
#define DEFAULT_MAXSOSADJACENCY   10000
 
#define DEFAULT_MAXEXTENSIONS   1
 
#define DEFAULT_MAXTIGHTENBDS   5
 
#define DEFAULT_PERFIMPLANALYSIS   TRUE
 
#define DEFAULT_DEPTHIMPLANALYSIS   -1
 
#define DEFAULT_CONFLICTPROP   TRUE
 
#define DEFAULT_IMPLPROP   TRUE
 
#define DEFAULT_SOSCONSPROP   FALSE
 
#define DEFAULT_BRANCHSTRATEGIES   "nbs"
 
#define DEFAULT_BRANCHINGRULE   'n'
 
#define DEFAULT_AUTOSOS1BRANCH   TRUE
 
#define DEFAULT_FIXNONZERO   FALSE
 
#define DEFAULT_ADDCOMPS   FALSE
 
#define DEFAULT_MAXADDCOMPS   -1
 
#define DEFAULT_ADDCOMPSDEPTH   30
 
#define DEFAULT_ADDCOMPSFEAS   -0.6
 
#define DEFAULT_ADDBDSFEAS   1.0
 
#define DEFAULT_ADDEXTENDEDBDS   TRUE
 
#define DEFAULT_NSTRONGROUNDS   0
 
#define DEFAULT_NSTRONGITER   10000
 
#define DEFAULT_BOUNDCUTSFROMSOS1   FALSE
 
#define DEFAULT_BOUNDCUTSFROMGRAPH   TRUE
 
#define DEFAULT_AUTOCUTSFROMSOS1   TRUE
 
#define DEFAULT_BOUNDCUTSFREQ   10
 
#define DEFAULT_BOUNDCUTSDEPTH   40
 
#define DEFAULT_MAXBOUNDCUTS   50
 
#define DEFAULT_MAXBOUNDCUTSROOT   150
 
#define DEFAULT_STRTHENBOUNDCUTS   TRUE
 
#define DEFAULT_IMPLCUTSFREQ   0
 
#define DEFAULT_IMPLCUTSDEPTH   40
 
#define DEFAULT_MAXIMPLCUTS   50
 
#define DEFAULT_MAXIMPLCUTSROOT   150
 
#define EVENTHDLR_NAME   "SOS1"
 
#define EVENTHDLR_DESC   "bound change event handler for SOS1 constraints"
 
#define DIVINGCUTOFFVALUE   1e6
 

Typedefs

typedef struct SCIP_NodeData SCIP_NODEDATA
 
typedef struct SCIP_SuccData SCIP_SUCCDATA
 

Functions

static SCIP_Bool isConnectedSOS1 (SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *conflictgraph, int vertex1, int vertex2)
 
static SCIP_Bool isViolatedSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_SOL *sol)
 
static SCIP_Real nodeGetSolvalBinaryBigMSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
 
static SCIP_Real nodeGetSolvalVarboundLbSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
 
static SCIP_Real nodeGetSolvalVarboundUbSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
 
static SCIP_Bool varIsSOS1 (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
 
static int varGetNodeSOS1 (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
 
static SCIP_RETCODE fixVariableZeroNode (SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible)
 
static SCIP_RETCODE fixVariableZero (SCIP *scip, SCIP_VAR *var, SCIP_Bool *infeasible, SCIP_Bool *tightened)
 
static SCIP_RETCODE inferVariableZero (SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened, SCIP_Bool *success)
 
static SCIP_RETCODE lockVariableSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE unlockVariableSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE consdataEnsurevarsSizeSOS1 (SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveWeights)
 
static SCIP_RETCODE handleNewVariableSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Bool transformed)
 
static SCIP_RETCODE addVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Real weight)
 
static SCIP_RETCODE appendVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
 
static SCIP_RETCODE deleteVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE extensionOperatorSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *vertexcliquegraph, int nsos1vars, int nconss, SCIP_CONS *cons, SCIP_VAR **vars, SCIP_Real *weights, SCIP_Bool firstcall, SCIP_Bool usebacktrack, int **cliques, int *ncliques, int *cliquesizes, int *newclique, int *workingset, int nworkingset, int nexts, int pos, int *maxextensions, int *naddconss, SCIP_Bool *success)
 
static SCIP_RETCODE genConflictgraphLinearCons (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraphlin, SCIP_DIGRAPH *conflictgraphorig, SCIP_VAR **linvars, int nlinvars, int *posinlinvars)
 
static SCIP_RETCODE cliqueGetCommonSuccessorsSOS1 (SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int *clique, SCIP_VAR **vars, int nvars, int *comsucc, int *ncomsucc)
 
static SCIP_RETCODE getSOS1Implications (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR **vars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, int node)
 
static SCIP_RETCODE presolRoundConsSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *substituted, SCIP_Bool *cutoff, SCIP_Bool *success, int *ndelconss, int *nupgdconss, int *nfixedvars, int *nremovedvars)
 
static SCIP_RETCODE presolRoundConssSOS1 (SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, SCIP_CONS **conss, int nconss, int nsos1vars, int *naddconss, int *ndelconss, int *nupgdconss, int *nfixedvars, int *nremovedvars, SCIP_RESULT *result)
 
static SCIP_RETCODE performImplicationGraphAnalysis (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **totalvars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool **adjacencymatrix, int givennode, int nonznode, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Bool *implnodes, int *naddconss, int *probingdepth, SCIP_Bool *infeasible)
 
static SCIP_Bool isImpliedZero (SCIP_DIGRAPH *conflictgraph, SCIP_Bool *implnodes, int node)
 
static SCIP_RETCODE updateArcData (SCIP *scip, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_VAR **totalvars, SCIP_VAR *varv, SCIP_VAR *varw, SCIP_Real lb, SCIP_Real ub, SCIP_Real newbound, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible)
 
static SCIP_RETCODE updateImplicationGraphSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, SCIP_VAR **totalvars, int **cliquecovers, int *cliquecoversizes, int *varincover, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_Real *bounds, SCIP_VAR *var, SCIP_Real bound, SCIP_Real boundnonzero, int ninftynonzero, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible)
 
static SCIP_RETCODE computeVarsCoverSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraphroot, SCIP_DIGRAPH *conflictgraphlin, SCIP_VAR **linvars, SCIP_Bool *coveredvars, int *clique, int *cliquesize, int v, SCIP_Bool considersolvals)
 
static SCIP_RETCODE tightenVarsBoundsSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool **adjacencymatrix, SCIP_VAR **totalvars, int ntotalvars, int nsos1vars, int *nchgbds, SCIP_Bool *implupdate, SCIP_Bool *cutoff)
 
static SCIP_RETCODE presolRoundVarsSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, int nsos1vars, int *nfixedvars, int *nchgbds, int *naddconss, SCIP_RESULT *result)
 
static SCIP_RETCODE propConsSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *ngen)
 
static SCIP_RETCODE propVariableNonzero (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *implgraph, SCIP_CONS *cons, int node, SCIP_Bool implprop, SCIP_Bool *cutoff, int *ngen)
 
static SCIP_RETCODE initImplGraphSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars, int maxrounds, int *nchgbds, SCIP_Bool *cutoff, SCIP_Bool *success)
 
static SCIP_RETCODE freeImplGraphSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_RETCODE getCoverVertices (SCIP_DIGRAPH *conflictgraph, SCIP_Bool *verticesarefixed, int vertex, int *neightocover, int nneightocover, int *coververtices, int *ncoververtices)
 
static SCIP_RETCODE getBranchingVerticesSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_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, 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, 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, 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, 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_RESULT *result)
 
static SCIP_RETCODE enforceConssSOS1 (SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, 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_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_CONSENFOPS (consEnfopsSOS1)
 
static SCIP_DECL_CONSCHECK (consCheckSOS1)
 
static SCIP_DECL_CONSPROP (consPropSOS1)
 
static SCIP_DECL_CONSRESPROP (consRespropSOS1)
 
static SCIP_DECL_CONSLOCK (consLockSOS1)
 
static SCIP_DECL_CONSPRINT (consPrintSOS1)
 
static SCIP_DECL_CONSCOPY (consCopySOS1)
 
static SCIP_DECL_CONSPARSE (consParseSOS1)
 
static SCIP_DECL_CONSGETVARS (consGetVarsSOS1)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsSOS1)
 
static SCIP_DECL_EVENTEXEC (eventExecSOS1)
 
static SCIP_DECL_CONSGETDIVEBDCHGS (consGetDiveBdChgsSOS1)
 
SCIP_RETCODE SCIPincludeConshdlrSOS1 (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsSOS1 (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicSOS1 (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
 
SCIP_RETCODE SCIPaddVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
 
SCIP_RETCODE SCIPappendVarSOS1 (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
int SCIPgetNVarsSOS1 (SCIP *scip, SCIP_CONS *cons)
 
SCIP_VAR ** SCIPgetVarsSOS1 (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RealSCIPgetWeightsSOS1 (SCIP *scip, SCIP_CONS *cons)
 
SCIP_DIGRAPHSCIPgetConflictgraphSOS1 (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_VARSCIPnodeGetVarSOS1 (SCIP_DIGRAPH *conflictgraph, int node)
 
SCIP_RETCODE SCIPmakeSOS1sFeasible (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
 

Macro Definition Documentation

#define CONSHDLR_NAME   "SOS1"
#define CONSHDLR_DESC   "SOS1 constraint handler"

Definition at line 87 of file cons_sos1.c.

#define CONSHDLR_SEPAPRIORITY   1000

priority of the constraint handler for separation

Definition at line 88 of file cons_sos1.c.

#define CONSHDLR_ENFOPRIORITY   100

priority of the constraint handler for constraint enforcing

Definition at line 89 of file cons_sos1.c.

#define CONSHDLR_CHECKPRIORITY   -10

priority of the constraint handler for checking feasibility

Definition at line 90 of file cons_sos1.c.

#define CONSHDLR_SEPAFREQ   10

frequency for separating cuts; zero means to separate only in the root node

Definition at line 91 of file cons_sos1.c.

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 92 of file cons_sos1.c.

#define CONSHDLR_EAGERFREQ   100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 93 of file cons_sos1.c.

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 96 of file cons_sos1.c.

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 97 of file cons_sos1.c.

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 98 of file cons_sos1.c.

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 99 of file cons_sos1.c.

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 100 of file cons_sos1.c.

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM

Definition at line 101 of file cons_sos1.c.

#define DEFAULT_MAXSOSADJACENCY   10000

do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit)

Definition at line 104 of file cons_sos1.c.

#define DEFAULT_MAXEXTENSIONS   1

maximal number of extensions that will be computed for each SOS1 constraint

Definition at line 109 of file cons_sos1.c.

#define DEFAULT_MAXTIGHTENBDS   5

maximal number of bound tightening rounds per presolving round (-1: no limit)

Definition at line 110 of file cons_sos1.c.

#define DEFAULT_PERFIMPLANALYSIS   TRUE

if TRUE then perform implication graph analysis (might add additional SOS1 constraints)

Definition at line 111 of file cons_sos1.c.

#define DEFAULT_DEPTHIMPLANALYSIS   -1

number of recursive calls of implication graph analysis (-1: no limit)

Definition at line 112 of file cons_sos1.c.

#define DEFAULT_CONFLICTPROP   TRUE

whether to use conflict graph propagation

Definition at line 115 of file cons_sos1.c.

#define DEFAULT_IMPLPROP   TRUE

whether to use implication graph propagation

Definition at line 116 of file cons_sos1.c.

#define DEFAULT_SOSCONSPROP   FALSE

whether to use SOS1 constraint propagation

Definition at line 117 of file cons_sos1.c.

#define DEFAULT_BRANCHSTRATEGIES   "nbs"

possible branching strategies (see parameter DEFAULT_BRANCHINGRULE)

Definition at line 120 of file cons_sos1.c.

#define DEFAULT_BRANCHINGRULE   'n'

which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique) (note: in some cases an automatic switching to SOS1 branching is possible)

Definition at line 121 of file cons_sos1.c.

#define DEFAULT_AUTOSOS1BRANCH   TRUE

if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap

Definition at line 124 of file cons_sos1.c.

#define DEFAULT_FIXNONZERO   FALSE

if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance

Definition at line 125 of file cons_sos1.c.

#define DEFAULT_ADDCOMPS   FALSE

if TRUE then add complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching)

Definition at line 128 of file cons_sos1.c.

#define DEFAULT_MAXADDCOMPS   -1

maximal number of complementarity constraints added per branching node (-1: no limit)

Definition at line 131 of file cons_sos1.c.

#define DEFAULT_ADDCOMPSDEPTH   30

only add complementarity constraints to branching nodes for predefined depth (-1: no limit)

Definition at line 132 of file cons_sos1.c.

#define DEFAULT_ADDCOMPSFEAS   -0.6

minimal feasibility value for complementarity constraints in order to be added to the branching node

Definition at line 133 of file cons_sos1.c.

#define DEFAULT_ADDBDSFEAS   1.0

minimal feasibility value for bound inequalities in order to be added to the branching node

Definition at line 134 of file cons_sos1.c.

#define DEFAULT_ADDEXTENDEDBDS   TRUE

should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities

Definition at line 135 of file cons_sos1.c.

#define DEFAULT_NSTRONGROUNDS   0

maximal number of strong branching rounds to perform for each node (-1: auto) (only available for neighborhood and bipartite branching)

Definition at line 138 of file cons_sos1.c.

#define DEFAULT_NSTRONGITER   10000

maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit)

Definition at line 141 of file cons_sos1.c.

#define DEFAULT_BOUNDCUTSFROMSOS1   FALSE

if TRUE separate bound inequalities from SOS1 constraints

Definition at line 144 of file cons_sos1.c.

#define DEFAULT_BOUNDCUTSFROMGRAPH   TRUE

if TRUE separate bound inequalities from the conflict graph

Definition at line 145 of file cons_sos1.c.

#define DEFAULT_AUTOCUTSFROMSOS1   TRUE

if TRUE then automatically switch to separating from SOS1 constraints if the SOS1 constraints do not overlap

Definition at line 146 of file cons_sos1.c.

#define DEFAULT_BOUNDCUTSFREQ   10

frequency for separating bound cuts; zero means to separate only in the root node

Definition at line 147 of file cons_sos1.c.

#define DEFAULT_BOUNDCUTSDEPTH   40

node depth of separating bound cuts (-1: no limit)

Definition at line 148 of file cons_sos1.c.

#define DEFAULT_MAXBOUNDCUTS   50

maximal number of bound cuts separated per branching node

Definition at line 149 of file cons_sos1.c.

#define DEFAULT_MAXBOUNDCUTSROOT   150

maximal number of bound cuts separated per iteration in the root node

Definition at line 150 of file cons_sos1.c.

#define DEFAULT_STRTHENBOUNDCUTS   TRUE

if TRUE then bound cuts are strengthened in case bound variables are available

Definition at line 151 of file cons_sos1.c.

#define DEFAULT_IMPLCUTSFREQ   0

frequency for separating implied bound cuts; zero means to separate only in the root node

Definition at line 152 of file cons_sos1.c.

#define DEFAULT_IMPLCUTSDEPTH   40

node depth of separating implied bound cuts (-1: no limit)

Definition at line 153 of file cons_sos1.c.

#define DEFAULT_MAXIMPLCUTS   50

maximal number of implied bound cuts separated per branching node

Definition at line 154 of file cons_sos1.c.

#define DEFAULT_MAXIMPLCUTSROOT   150

maximal number of implied bound cuts separated per iteration in the root node

Definition at line 155 of file cons_sos1.c.

#define EVENTHDLR_NAME   "SOS1"

Definition at line 158 of file cons_sos1.c.

#define EVENTHDLR_DESC   "bound change event handler for SOS1 constraints"

Definition at line 159 of file cons_sos1.c.

#define DIVINGCUTOFFVALUE   1e6

Definition at line 162 of file cons_sos1.c.

Referenced by getDiveBdChgsSOS1conflictgraph(), and getDiveBdChgsSOS1constraints().

Typedef Documentation

typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 192 of file cons_sos1.c.

typedef struct SCIP_SuccData SCIP_SUCCDATA

Definition at line 201 of file cons_sos1.c.

Function Documentation

static SCIP_Bool isConnectedSOS1 ( SCIP_Bool **  adjacencymatrix,
SCIP_DIGRAPH conflictgraph,
int  vertex1,
int  vertex2 
)
static

returns whether two vertices are adjacent in the conflict graph

Parameters
adjacencymatrixadjacency matrix of conflict graph (lower half) (or NULL if an adjacencymatrix is not at hand)
conflictgraphconflict graph (or NULL if an adjacencymatrix is at hand)
vertex1first vertex
vertex2second vertex

Definition at line 299 of file cons_sos1.c.

References FALSE, isViolatedSOS1(), NULL, SCIP_Bool, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPsortInt(), SCIPswapInts(), and TRUE.

Referenced by addBranchingComplementaritiesSOS1(), computeVarsCoverSOS1(), enforceConflictgraph(), extensionOperatorSOS1(), getBoundConsFromVertices(), performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().

static SCIP_Bool isViolatedSOS1 ( SCIP scip,
SCIP_DIGRAPH conflictgraph,
int  node,
SCIP_SOL sol 
)
static

checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable

Parameters
scipSCIP data structure
conflictgraphconflict graph (or NULL if an adjacencymatrix is at hand)
nodenode of variable in the conflict graph
solsolution, or NULL to use current node's solution

Definition at line 359 of file cons_sos1.c.

References FALSE, nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by getDiveBdChgsSOS1conflictgraph(), and isConnectedSOS1().

static SCIP_Real nodeGetSolvalBinaryBigMSOS1 ( SCIP scip,
SCIP_DIGRAPH conflictgraph,
SCIP_SOL sol,
int  node 
)
static

returns solution value of imaginary binary big-M variable of a given node from the conflict graph

Parameters
scipSCIP pointer
conflictgraphconflict graph
solprimal solution, or NULL for current LP/pseudo solution
nodenode of the conflict graph

Definition at line 404 of file cons_sos1.c.

References nodeGetSolvalVarboundLbSOS1(), NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by computeVarsCoverSOS1(), getBoundConsFromVertices(), and isViolatedSOS1().

static SCIP_Real nodeGetSolvalVarboundLbSOS1 ( SCIP scip,
SCIP_DIGRAPH conflictgraph,
SCIP_SOL sol,
int  node 
)
static

gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph

Parameters
scipSCIP pointer
conflictgraphconflict graph
solprimal solution, or NULL for current LP/pseudo solution
nodenode of the conflict graph

Definition at line 454 of file cons_sos1.c.

References nodeGetSolvalVarboundUbSOS1(), NULL, SCIP_Real, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetLbLocal().

Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalBinaryBigMSOS1(), and updateWeightsTCliquegraph().

static SCIP_Real nodeGetSolvalVarboundUbSOS1 ( SCIP scip,
SCIP_DIGRAPH conflictgraph,
SCIP_SOL sol,
int  node 
)
static

gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph

Parameters
scipSCIP pointer
conflictgraphconflict graph
solprimal solution, or NULL for current LP/pseudo solution
nodenode of the conflict graph

Definition at line 481 of file cons_sos1.c.

References NULL, SCIP_Bool, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), SCIPvarGetUbLocal(), and varIsSOS1().

Referenced by getDiveBdChgsSOS1conflictgraph(), nodeGetSolvalVarboundLbSOS1(), and updateWeightsTCliquegraph().

static SCIP_Bool varIsSOS1 ( SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR var 
)
static

returns whether variable is part of the SOS1 conflict graph

Parameters
conshdlrdataSOS1 constraint handler
varvariable

Definition at line 508 of file cons_sos1.c.

Referenced by checkLinearConssVarboundSOS1(), and nodeGetSolvalVarboundUbSOS1().

static int varGetNodeSOS1 ( SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR var 
)
static
static SCIP_RETCODE fixVariableZeroNode ( SCIP scip,
SCIP_VAR var,
SCIP_NODE node,
SCIP_Bool infeasible 
)
static
static SCIP_RETCODE fixVariableZero ( SCIP scip,
SCIP_VAR var,
SCIP_Bool infeasible,
SCIP_Bool tightened 
)
static

try to fix variable to 0

Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation

\[ x = \sum_{i=1}^n \alpha_i x_i + c, \]

we can express the fixing $x = 0$ by fixing all $x_i$ to 0 if $c = 0$ and the lower bounds of $x_i$ are nonnegative if $\alpha_i > 0$ or the upper bounds are nonpositive if $\alpha_i < 0$.

Parameters
scipSCIP pointer
varvariable to be fixed to 0
infeasibleif fixing is infeasible
tightenedif fixing was performed

Definition at line 601 of file cons_sos1.c.

References FALSE, inferVariableZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPfixVar(), SCIPflattenVarAggregationGraph(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

Referenced by fixVariableZeroNode(), and presolRoundConsSOS1().

static SCIP_RETCODE inferVariableZero ( SCIP scip,
SCIP_VAR var,
SCIP_CONS cons,
int  inferinfo,
SCIP_Bool infeasible,
SCIP_Bool tightened,
SCIP_Bool success 
)
static

fix variable in local node to 0, and return whether the operation was feasible

Note
We do not add a linear constraint if the variable is multi-aggregated as in fixVariableZeroNode(), since this would be too time consuming.
Parameters
scipSCIP pointer
varvariable to be fixed to 0
consconstraint
inferinfoinfo for reverse prop.
infeasibleif fixing is infeasible
tightenedif fixing was performed
successwhether fixing was successful, i.e., variable is not multi-aggregated

Definition at line 675 of file cons_sos1.c.

References FALSE, lockVariableSOS1(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

Referenced by fixVariableZero(), propConsSOS1(), and propVariableNonzero().

static SCIP_RETCODE lockVariableSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var 
)
static

add lock on variable

Parameters
scipSCIP data structure
consconstraint
varvariable

Definition at line 718 of file cons_sos1.c.

Referenced by handleNewVariableSOS1(), inferVariableZero(), and presolRoundConsSOS1().

static SCIP_RETCODE unlockVariableSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var 
)
static

remove lock on variable

Parameters
scipSCIP data structure
consconstraint
varvariable

Definition at line 737 of file cons_sos1.c.

Referenced by deleteVarSOS1(), and presolRoundConsSOS1().

static SCIP_RETCODE consdataEnsurevarsSizeSOS1 ( SCIP scip,
SCIP_CONSDATA consdata,
int  num,
SCIP_Bool  reserveWeights 
)
static

ensures that the vars and weights array can store at least num entries

Parameters
scipSCIP data structure
consdataconstraint data
numminimum number of entries to store
reserveWeightswhether the weights array is handled

Definition at line 756 of file cons_sos1.c.

References handleNewVariableSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by addVarSOS1(), and appendVarSOS1().

static SCIP_RETCODE handleNewVariableSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR var,
SCIP_Bool  transformed 
)
static
static SCIP_RETCODE addVarSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR var,
SCIP_Real  weight 
)
static

adds a variable to an SOS1 constraint, at position given by weight - ascending order

Parameters
scipSCIP data structure
consconstraint
conshdlrdataconstraint handler data
varvariable to add to the constraint
weightweight to determine position

Definition at line 919 of file cons_sos1.c.

References appendVarSOS1(), consdataEnsurevarsSizeSOS1(), handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.

Referenced by addBranchingComplementaritiesSOS1(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), and SCIPaddVarSOS1().

static SCIP_RETCODE appendVarSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR var 
)
static

appends a variable to an SOS1 constraint

Parameters
scipSCIP data structure
consconstraint
conshdlrdataconstraint handler data
varvariable to add to the constraint

Definition at line 989 of file cons_sos1.c.

References consdataEnsurevarsSizeSOS1(), deleteVarSOS1(), FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPgetTransformedVar(), and SCIPvarIsTransformed().

Referenced by addVarSOS1().

static SCIP_RETCODE deleteVarSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

deletes a variable of an SOS1 constraint

Parameters
scipSCIP data structure
consconstraint
consdataconstraint data
eventhdlrcorresponding event handler
posposition of variable in array

Definition at line 1035 of file cons_sos1.c.

References extensionOperatorSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1().

Referenced by appendVarSOS1(), and presolRoundConsSOS1().

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

extends a given clique of the conflict graph

Implementation of the Bron-Kerbosch Algorithm from the paper: Algorithm 457: Finding all Cliques of an Undirected Graph, Bron & Kerbosch, Commun. ACM, 1973

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
adjacencymatrixadjacencymatrix of the conflict graph (only lower half filled)
vertexcliquegraphgraph that contains the information which cliques contain a given vertex vertices of variables = 0, ..., nsos1vars-1; vertices of cliques = nsos1vars, ..., nsos1vars+ncliques-1
nsos1varsnumber of SOS1 variables
nconssnumber of SOS1 constraints
consconstraint to be extended
varsvariables of extended clique
weightsweights of extended clique
firstcallwhether this is the first call of extension operator
usebacktrackwhether backtracking is needed for the computation
cliquesall cliques found so far
ncliquesnumber of clique found so far
cliquesizesnumber of variables of current clique
newcliqueclique we want to extended
workingsetset of vertices that already served as extension and set of candidates that probably will lead to an extension
nworkingsetlength of array workingset
nextsnumber of vertices that already served as extension
posposition of potential candidate
maxextensionsmaximal number of extensions
naddconssnumber of added constraints
successpointer to store if at least one new clique was found

Definition at line 1074 of file cons_sos1.c.

References FALSE, genConflictgraphLinearCons(), isConnectedSOS1(), MAX, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), and TRUE.

Referenced by deleteVarSOS1(), and presolRoundConssSOS1().

static SCIP_RETCODE genConflictgraphLinearCons ( SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH conflictgraphlin,
SCIP_DIGRAPH conflictgraphorig,
SCIP_VAR **  linvars,
int  nlinvars,
int *  posinlinvars 
)
static

generates conflict graph that is induced by the variables of a linear constraint

Parameters
conshdlrdataconstraint handler data
conflictgraphlinconflict graph of linear constraint (nodes: 1, ..., nlinvars)
conflictgraphorigoriginal conflict graph (nodes: 1, ..., nsos1vars)
linvarslinear variables in linear constraint
nlinvarsnumber of linear variables in linear constraint
posinlinvarsposinlinvars[i] = position (index) of SOS1 variable i in linear constraint, posinlinvars[i]= -1 if i is not a SOS1 variable or not a variable of the linear constraint

Definition at line 1336 of file cons_sos1.c.

References cliqueGetCommonSuccessorsSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().

Referenced by extensionOperatorSOS1(), and tightenVarsBoundsSOS1().

static SCIP_RETCODE cliqueGetCommonSuccessorsSOS1 ( SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH conflictgraph,
int *  clique,
SCIP_VAR **  vars,
int  nvars,
int *  comsucc,
int *  ncomsucc 
)
static

determine the common successors of the vertices from the considered clique

Parameters
conshdlrdataconstraint handler data
conflictgraphconflict graph
cliquecurrent clique
varsclique variables
nvarsnumber of clique variables
comsuccpointer to store common successors of clique vertices (size = nvars)
ncomsuccpointer to store number common successors of clique vertices

Definition at line 1389 of file cons_sos1.c.

References getSOS1Implications(), NULL, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and varGetNodeSOS1().

Referenced by genConflictgraphLinearCons(), and presolRoundConssSOS1().

static SCIP_RETCODE getSOS1Implications ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR **  vars,
SCIP_DIGRAPH implgraph,
SCIP_HASHMAP implhash,
SCIP_Bool implnodes,
int  node 
)
static

get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
varsproblem and SOS1 variables
implgraphimplication graph (j is successor of i if and only if $ x_i\not = 0 \Rightarrow x_j\not = 0$)
implhashhash map from variable to node in implication graph
implnodesimplnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero
nodenode of the implication graph

Definition at line 1486 of file cons_sos1.c.

References NULL, presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, and varGetNodeSOS1().

Referenced by cliqueGetCommonSuccessorsSOS1(), and tightenVarsBoundsSOS1().

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

perform one presolving round for a single SOS1 constraint

We perform the following presolving steps.

  • If the bounds of some variable force it to be nonzero, we can fix all other variables to zero and remove the SOS1 constraints that contain it.
  • If a variable is fixed to zero, we can remove the variable.
  • If a variable appears twice, it can be fixed to 0.
  • We substitute appregated variables.
Parameters
scipSCIP pointer
consconstraint
consdataconstraint data
eventhdlrevent handler
substitutedwhether a variable was substituted
cutoffwhether a cutoff happened
successwhether we performed a successful reduction
ndelconssnumber of deleted constraints
nupgdconssnumber of upgraded constraints
nfixedvarsnumber of fixed variables
nremovedvarsnumber of variables removed

Definition at line 1552 of file cons_sos1.c.

References deleteVarSOS1(), FALSE, fixVariableZero(), lockVariableSOS1(), NULL, presolRoundConssSOS1(), SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcatchVarEvent(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMessage, SCIPdelCons(), SCIPdropVarEvent(), SCIPfindConshdlr(), SCIPfixVar(), SCIPgetProbvarSum(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, and unlockVariableSOS1().

Referenced by getSOS1Implications(), and presolRoundConssSOS1().

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

perform one presolving round for all SOS1 constraints

We perform the following presolving steps.

  • If the bounds of some variable force it to be nonzero, we can fix all other variables to zero and remove the SOS1 constraints that contain it.
  • If a variable is fixed to zero, we can remove the variable.
  • If a variable appears twice, it can be fixed to 0.
  • We substitute appregated variables.
  • Remove redundant SOS1 constraints

If the adjacency matrix of the conflict graph is present, then we perform the following additional presolving steps

  • Search for larger SOS1 constraints in the conflict graph
Parameters
scipSCIP pointer
eventhdlrevent handler
conshdlrdataconstraint handler data
conflictgraphconflict graph
adjacencymatrixadjacency matrix of conflict graph (or NULL)
conssSOS1 constraints
nconssnumber of SOS1 constraints
nsos1varsnumber of SOS1 variables
naddconssnumber of added constraints
ndelconssnumber of deleted constraints
nupgdconssnumber of upgraded constraints
nfixedvarsnumber of fixed variables
nremovedvarsnumber of variables removed
resultresult

Definition at line 1776 of file cons_sos1.c.

References cliqueGetCommonSuccessorsSOS1(), extensionOperatorSOS1(), FALSE, MAX, NULL, performImplicationGraphAnalysis(), presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPcomputeArraysIntersection(), SCIPconsGetData(), SCIPconsIsModifiable(), SCIPdelCons(), SCIPdigraphAddArcSafe(), SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownIntInt(), SCIPsortInt(), TRUE, and varGetNodeSOS1().

Referenced by presolRoundConsSOS1().

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

performs implication graph analysis

Tentatively fixes a variable to nonzeero and extracts consequences from it:

  • adds (possibly new) complementarity constraints to the problem if variables are implied to be zero
  • returns that the subproblem is infeasible if the domain of a variable turns out to be empty
Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conflictgraphconflict graph
totalvarsproblem and SOS1 variables
implgraphimplication graph (j is successor of i if and only if $ x_i\not = 0 \Rightarrow x_j\not = 0$)
implhashhash map from variable to node in implication graph
adjacencymatrixadjacencymatrix of the conflict graph (only lower half filled)
givennodenode of the conflict graph
nonznodenode of the conflict graph that is implied to be nonzero if given node is nonzero
impllbscurrent lower variable bounds if given node is nonzero (update possible)
implubscurrent upper variable bounds if given node is nonzero (update possible)
implnodesindicates which variables are currently implied to be nonzero if given node is nonzero (update possible)
naddconsspointer to store number of added SOS1 constraints
probingdepthpointer to store current probing depth
infeasiblepointer to store whether the subproblem gets infeasible if variable to 'nonznode' is nonzero

Definition at line 2045 of file cons_sos1.c.

References addVarSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSOS1(), SCIPdigraphAddArcSafe(), SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImage(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), SCIPvarGetName(), TRUE, and varGetNodeSOS1().

Referenced by presolRoundConssSOS1(), and presolRoundVarsSOS1().

static SCIP_Bool isImpliedZero ( SCIP_DIGRAPH conflictgraph,
SCIP_Bool implnodes,
int  node 
)
static

returns whether node is implied to be zero; this information is taken from the input array 'implnodes'

Parameters
conflictgraphconflict graph
implnodesimplnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero
nodenode of the conflict graph (or -1)

Definition at line 2202 of file cons_sos1.c.

Referenced by performImplicationGraphAnalysis(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().

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

updates arc data of implication graph

Parameters
scipSCIP pointer
implgraphimplication graph
implhashhash map from variable to node in implication graph
totalvarsproblem and SOS1 variables
varvvariable that is assumed to be nonzero
varwimplication variable
lbold lower bound of $x_w$
ubold upper bound of $x_w$
newboundnew bound of $x_w$
lowerwhether to consider lower bound implication (otherwise upper bound)
nchgbdspointer to store number of changed bounds
updatepointer to store whether implication graph has been updated
infeasiblepointer to store whether an infeasibility has been detected

Definition at line 2231 of file cons_sos1.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPceil(), SCIPdebugMessage, SCIPdigraphAddArc(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfloor(), SCIPhashmapGetImage(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), SCIPvarIsIntegral(), TRUE, and updateImplicationGraphSOS1().

Referenced by updateImplicationGraphSOS1().

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

updates implication graph

Assume the variable from the input is nonzero. If this implies that some other variable is also nonzero, then store this information in an implication graph

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conflictgraphconflict graph
adjacencymatrixadjacency matrix of conflict graph (lower half)
implgraphimplication graph (j is successor of i if and only if $ x_i\not = 0 \Rightarrow x_j\not = 0$)
implhashhash map from variable to node in implication graph
implnodesimplnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero
totalvarsproblem and SOS1 variables
cliquecoversclique covers of linear constraint
cliquecoversizessize of clique covers
varincoverarray with varincover[i] = cover of SOS1 index i
varsvariables to be checked
coefscoefficients of variables in linear constraint
nvarsnumber of variables to be checked
boundsbounds of variables
varvariable that is assumed to be nonzero
boundbound of variable
boundnonzerobound of variable if it is known to be nonzero if infinity values are not summarized
ninftynonzeronumber of times infinity/-infinity has to be summarized to boundnonzero
lowerTRUE if lower bounds are consideres; FALSE for upper bounds
nchgbdspointer to store number of changed bounds
updatepointer to store whether implication graph has been updated
infeasiblepointer to store whether an infeasibility has been detected

Definition at line 2357 of file cons_sos1.c.

References computeVarsCoverSOS1(), FALSE, isConnectedSOS1(), isImpliedZero(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, updateArcData(), and varGetNodeSOS1().

Referenced by tightenVarsBoundsSOS1(), and updateArcData().

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

search new disjoint clique that covers given node

For a given vertex v search for a clique of the conflict graph induced by the variables of a linear constraint that

  • covers v and
  • has an an empty intersection with already computed clique cover.
Parameters
scipSCIP pointer
conflictgraphrootconflict graph of the root node (nodes: 1, ..., nsos1vars)
conflictgraphlinconflict graph of linear constraint (nodes: 1, ..., nlinvars)
linvarsvariables in linear constraint
coveredvarsstates which variables of the linear constraint are currently covered by a clique
cliquearray to store new clique in cover
cliquesizepointer to store the size of clique
vposition of variable in linear constraint that should be covered
considersolvalsTRUE if largest auxiliary bigM values of variables should be prefered

Definition at line 2513 of file cons_sos1.c.

References isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasLT(), tightenVarsBoundsSOS1(), and TRUE.

Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().

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

try to tighten upper and lower bounds for variables

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conflictgraphconflict graph
implgraphimplication graph (j is successor of i if and only if $ x_i\not = 0 $ implies a new lower/upper bound for $ x_j$)
implhashhash map from variable to node in implication graph
adjacencymatrixadjacencymatrix of conflict graph
totalvarsproblem and SOS1 vars
ntotalvarsnumber of problem and SOS1 variables
nsos1varsnumber of SOS1 variables
nchgbdspointer to store number of changed bounds
implupdatepointer to store whether the implication graph has been updated in this function call
cutoffpointer to store if current nodes LP is infeasible

Definition at line 2624 of file cons_sos1.c.

References computeVarsCoverSOS1(), FALSE, genConflictgraphLinearCons(), getSOS1Implications(), isConnectedSOS1(), isImpliedZero(), MAX, MIN, NULL, presolRoundVarsSOS1(), REALABS, scalars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPallocBufferArray, SCIPceil(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdebugMessage, SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfloor(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetProbvarLinearSum(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPreallocBufferArray, SCIPsortDownRealInt(), SCIPsortRealInt(), SCIPswapPointers(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetName(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, updateImplicationGraphSOS1(), and varGetNodeSOS1().

Referenced by computeVarsCoverSOS1(), initImplGraphSOS1(), and presolRoundVarsSOS1().

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

perform one presolving round for variables

We perform the following presolving steps:

  • Tighten the bounds of the variables
  • Update conflict graph based on bound implications of the variables
Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conflictgraphconflict graph
adjacencymatrixadjacencymatrix of conflict graph
nsos1varsnumber of SOS1 variables
nfixedvarspointer to store number of fixed variables
nchgbdspointer to store number of changed bounds
naddconsspointer to store number of addded constraints
resultresult

Definition at line 3332 of file cons_sos1.c.

References FALSE, performImplicationGraphAnalysis(), propConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMessage, SCIPdigraphCreate(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfixVar(), SCIPfreeBufferArrayNull, SCIPfreeMemory, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenVarsBoundsSOS1(), and TRUE.

Referenced by tightenVarsBoundsSOS1().

static SCIP_RETCODE propConsSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_Bool cutoff,
int *  ngen 
)
static

propagate variables of SOS1 constraint

Parameters
scipSCIP pointer
consconstraint
consdataconstraint data
cutoffwhether a cutoff happened
ngennumber of domain changes

Definition at line 3506 of file cons_sos1.c.

References FALSE, inferVariableZero(), NULL, propVariableNonzero(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsIsModifiable(), SCIPdebugMessage, SCIPdelConsLocal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by enforceConflictgraph(), enforceConssSOS1(), and presolRoundVarsSOS1().

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

propagate a variable that is known to be nonzero

Parameters
scipSCIP pointer
conflictgraphconflict graph
implgraphimplication graph
conssome arbitrary SOS1 constraint
nodeconflict graph node of variable that is known to be nonzero
implpropwhether implication graph propagation shall be applied
cutoffwhether a cutoff happened
ngennumber of domain changes

Definition at line 3604 of file cons_sos1.c.

References FALSE, inferVariableZero(), initImplGraphSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propConsSOS1().

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

initialize implication graph

j is successor of i if and only if $ x_i\not = 0 \Rightarrow x_j\not = 0$

Note
By construction the implication graph is globally valid.
Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conflictgraphconflict graph
nsos1varsnumber of SOS1 variables
maxroundsmaximal number of propagation rounds for generating implications
nchgbdspointer to store number of bound changes
cutoffpointer to store whether a cutoff occurred
successwhether initialization was successful

Definition at line 3746 of file cons_sos1.c.

References FALSE, freeImplGraphSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemory, SCIPblkmem(), SCIPdebugMessage, SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPnodeGetVarSOS1(), tightenVarsBoundsSOS1(), and TRUE.

Referenced by propVariableNonzero(), and sepaImplBoundCutsSOS1().

static SCIP_RETCODE freeImplGraphSOS1 ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

deinitialize implication graph

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data

Definition at line 3913 of file cons_sos1.c.

Referenced by initImplGraphSOS1().

static SCIP_RETCODE getCoverVertices ( SCIP_DIGRAPH conflictgraph,
SCIP_Bool verticesarefixed,
int  vertex,
int *  neightocover,
int  nneightocover,
int *  coververtices,
int *  ncoververtices 
)
static

get the vertices whose neighbor set covers a subset of the neighbor set of a given other vertex.

This function can be used to compute sets of variables to branch on.

Parameters
conflictgraphconflict graph
verticesarefixedarray that indicates which variables are currently fixed to zero
vertexvertex (-1 if not needed)
neightocoverneighbors of given vertex to be covered (or NULL if all neighbors shall be covered)
nneightocovernumber of entries of neightocover (or 0 if all neighbors shall be covered )
coververticesarray to store the vertices whose neighbor set covers the neighbor set of the given vertex
ncoververticespointer to store size of coververtices

Definition at line 3972 of file cons_sos1.c.

References getBranchingVerticesSOS1(), NULL, SCIP_Bool, SCIP_OKAY, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().

Referenced by addBranchingComplementaritiesSOS1(), and getBranchingVerticesSOS1().

static SCIP_RETCODE getBranchingVerticesSOS1 ( SCIP scip,
SCIP_DIGRAPH conflictgraph,
SCIP_Bool verticesarefixed,
SCIP_Bool  bipbranch,
int  branchvertex,
int *  fixingsnode1,
int *  nfixingsnode1,
int *  fixingsnode2,
int *  nfixingsnode2 
)
static

get vertices of variables that will be fixed to zero for each node

Parameters
scipSCIP pointer
conflictgraphconflict graph
verticesarefixedvector that indicates which variables are currently fixed to zero
bipbranchTRUE if bipartite branching method should be used
branchvertexbranching vertex
fixingsnode1vertices of variables that will be fixed to zero for the first node
nfixingsnode1pointer to store number of fixed variables for the first node
fixingsnode2vertices of variables that will be fixed to zero for the second node
nfixingsnode2pointer to store number of fixed variables for the second node

Definition at line 4079 of file cons_sos1.c.

References FALSE, getBranchingPrioritiesSOS1(), getCoverVertices(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and TRUE.

Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), and getCoverVertices().

static SCIP_RETCODE getBranchingPrioritiesSOS1 ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH conflictgraph,
int  nsos1vars,
SCIP_Bool verticesarefixed,
SCIP_Bool  bipbranch,
int *  fixingsnode1,
int *  fixingsnode2,
SCIP_Real branchpriors,
int *  vertexbestprior,
SCIP_Bool relsolfeas 
)
static

gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conflictgraphconflict graph
nsos1varsnumber of SOS1 variables
verticesarefixedvector that indicates which variables are currently fixed to zero
bipbranchTRUE if bipartite branching method should be used
fixingsnode1vertices of variables that will be fixed to zero for the first node (size = nsos1vars)
fixingsnode2vertices of variables that will be fixed to zero for the second node (size = nsos1vars)
branchpriorspointer to store branching priorities (size = nsos1vars) or NULL if not needed
vertexbestpriorpointer to store vertex with the best branching priority or NULL if not needed
relsolfeaspointer to store if LP relaxation solution is feasible

Definition at line 4191 of file cons_sos1.c.

References FALSE, getBranchingVerticesSOS1(), NULL, performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), and TRUE.

Referenced by enforceConflictgraph(), getBranchingDecisionStrongbranchSOS1(), and getBranchingVerticesSOS1().

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

performs strong branching with given domain fixings

Parameters
scipSCIP pointer
conflictgraphconflict graph
fixingsexecvertices of variables to be fixed to zero for this strong branching execution
nfixingsexecnumber of vertices of variables to be fixed to zero for this strong branching execution
fixingsopvertices of variables to be fixed to zero for the opposite strong branching execution
nfixingsopnumber of vertices of variables to be fixed to zero for the opposite strong branching execution
inititermaximal number of LP iterations to perform
fixnonzeroshall opposite variable (if positive in sign) fixed to the feasibility tolerance (only possible if nfixingsop = 1)
domainfixingsvertices that can be used to reduce the domain (should have size equal to number of variables)
ndomainfixingspointer to store number of vertices that can be used to reduce the domain, could be filled by earlier calls
infeasiblepointer to store whether branch is infeasible
objvalpointer to store objective value of LP with fixed variables (SCIP_INVALID if reddomain = TRUE or lperror = TRUE)
lperrorpointer to store whether an unresolved LP error or a strange solution status occurred

Definition at line 4292 of file cons_sos1.c.

References FALSE, getBranchingDecisionStrongbranchSOS1(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPendProbing(), SCIPfeastol(), SCIPfixVarProbing(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPpropagateProbing(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.

Referenced by getBranchingDecisionStrongbranchSOS1(), and getBranchingPrioritiesSOS1().

static SCIP_RETCODE getBranchingDecisionStrongbranchSOS1 ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH conflictgraph,
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

apply strong branching to determine the vertex for the next branching decision

Parameters
scipSCIP pointer
conshdlrdataSOS1 constraint handler data
conflictgraphconflict graph
nsos1varsnumber of SOS1 variables
lpobjvalcurrent LP relaxation solution
bipbranchTRUE if bipartite branching method should be used
nstrongroundsnumber of strong branching rounds
verticesarefixedvector that indicates which variables are currently fixed to zero
fixingsnode1pointer to store vertices of variables that will be fixed to zero for the first node (size = nsos1vars)
fixingsnode2pointer to store vertices of variables that will be fixed to zero for the second node (size = nsos1vars)
vertexbestpriorpointer to store vertex with the best strong branching priority
bestobjval1pointer to store LP objective for left child node of branching decision with best priority
bestobjval2pointer to store LP objective for right child node of branching decision with best priority
resultpointer to store result of strong branching

Definition at line 4434 of file cons_sos1.c.

References FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), MAX, MIN, NULL, performStrongbranchSOS1(), REALABS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPallocBufferArray, SCIPdebugMessage, SCIPfeastol(), SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPgetLPObjval(), SCIPgetNDualResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNNodeInitLPIterations(), SCIPgetNNodeInitLPs(), SCIPgetNNodes(), SCIPinfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), and SCIPsortDownRealInt().

Referenced by enforceConflictgraph(), and performStrongbranchSOS1().

static SCIP_RETCODE getBoundConsFromVertices ( SCIP scip,
SCIP_DIGRAPH conflictgraph,
int  v1,
int  v2,
SCIP_VAR boundvar,
SCIP_Bool  extend,
SCIP_CONS cons,
SCIP_Real feas 
)
static

for two given vertices v1 and v2 search for a clique in the conflict graph that contains these vertices. From this clique, we create a bound constraint.

Parameters
scipSCIP pointer
conflictgraphconflict graph
v1first vertex that shall be contained in bound constraint
v2second vertex that shall be contained in bound constraint
boundvarbound variable of v1 and v2 (or NULL if not existent)
extendshould v1 and v2 be greedily extended to a clique of larger size
consbound constraint
feasfeasibility value of bound constraint

Definition at line 4647 of file cons_sos1.c.

References addBranchingComplementaritiesSOS1(), FALSE, isConnectedSOS1(), nodeGetSolvalBinaryBigMSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPallocBufferArray, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by addBranchingComplementaritiesSOS1(), and getBranchingDecisionStrongbranchSOS1().

static SCIP_RETCODE addBranchingComplementaritiesSOS1 ( SCIP scip,
SCIP_NODE node,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH conflictgraph,
SCIP_DIGRAPH localconflicts,
int  nsos1vars,
SCIP_Bool verticesarefixed,
int *  fixingsnode1,
int  nfixingsnode1,
int *  fixingsnode2,
int  nfixingsnode2,
int *  naddedconss,
SCIP_Bool  onlyviolsos1 
)
static

tries to add feasible complementarity constraints to a given child branching node.

Note
In this function the conflict graph is updated to the conflict graph of the considered child branching node.
Parameters
scipSCIP pointer
nodebranching node
conshdlrdataconstraint handler data
conflictgraphconflict graph of the current node
localconflictslocal conflicts (updates to local conflicts of child node)
nsos1varsnumber of SOS1 variables
verticesarefixedvector that indicates which variables are currently fixed to zerox
fixingsnode1vertices of variables that will be fixed to zero for the branching node in the input of this function
nfixingsnode1number of entries of array nfixingsnode1
fixingsnode2vertices of variables that will be fixed to zero for the other branching node
nfixingsnode2number of entries of array nfixingsnode2
naddedconsspointer to store the number of added SOS1 constraints
onlyviolsos1should only SOS1 constraints be added that are violated by the LP solution

Definition at line 4874 of file cons_sos1.c.

References addVarSOS1(), FALSE, fixVariableZeroNode(), getBoundConsFromVertices(), getCoverVertices(), isConnectedSOS1(), NULL, resetConflictgraphSOS1(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPcomputeArraysSetminus(), SCIPcreateConsLinear(), SCIPcreateConsSOS1(), SCIPdigraphAddArc(), SCIPdigraphCreate(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisGT(), SCIPisInfinity(), SCIPnodeGetNumber(), SCIPnodeGetVarSOS1(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortInt(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by enforceConflictgraph(), and getBoundConsFromVertices().

static SCIP_RETCODE resetConflictgraphSOS1 ( SCIP_DIGRAPH conflictgraph,
SCIP_DIGRAPH localconflicts,
int  nsos1vars 
)
static

resets local conflict graph to the conflict graph of the root node

Parameters
conflictgraphconflict graph of root node
localconflictslocal conflicts that should be removed from conflict graph
nsos1varsnumber of SOS1 variables

Definition at line 5238 of file cons_sos1.c.

References enforceConflictgraph(), SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminus(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors().

Referenced by addBranchingComplementaritiesSOS1(), and enforceConflictgraph().

static SCIP_RETCODE enforceConflictgraph ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONSHDLR conshdlr,
int  nconss,
SCIP_CONS **  conss,
SCIP_RESULT result 
)
static

Conflict graph enforcement method

The conflict graph can be enforced by different branching rules:

  • Branch on the neighborhood of a single variable i, i.e., in one branch $x_i$ is fixed to zero and in the other its neighbors from the conflict graph.
  • Branch on complete bipartite subgraphs of the conflict graph, i.e., in one branch fix the variables from the first bipartite partition and the variables from the second bipartite partition in the other.
  • In addition to variable domain fixings, it is sometimes also possible to add new SOS1 constraints to the branching nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.

We make use of different selection rules that define on which system of SOS1 variables to branch next:

  • Most infeasible branching: Branch on the system of SOS1 variables with largest violation.
  • Strong branching: Here, the LP-relaxation is partially solved for each branching decision among a candidate list. Then the decision with best progress is chosen.
Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conshdlrconstraint handler
nconssnumber of constraints
conssSOS1 constraints
resultresult

Definition at line 5294 of file cons_sos1.c.

References addBranchingComplementaritiesSOS1(), enforceConssSOS1(), FALSE, fixVariableZeroNode(), getBranchingDecisionStrongbranchSOS1(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), isConnectedSOS1(), log(), MAX, MIN, NULL, pow(), propConsSOS1(), resetConflictgraphSOS1(), SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VARSTATUS_MULTAGGR, SCIPallocBufferArray, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMessage, SCIPdigraphAddArcSafe(), SCIPdigraphCreate(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPerrorMessage, SCIPfeastol(), SCIPfloor(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPinfinity(), SCIPisFeasZero(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPsortInt(), SCIPupdateNodeLowerbound(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), TRUE, and varGetNodeSOS1().

Referenced by resetConflictgraphSOS1().

static SCIP_RETCODE enforceConssSOS1 ( SCIP scip,
SCIP_CONSHDLR conshdlr,
int  nconss,
SCIP_CONS **  conss,
SCIP_RESULT result 
)
static

SOS1 branching enforcement method

We check whether the current solution is feasible, i.e., contains at most one nonzero variable. If not, we branch along the lines indicated by Beale and Tomlin:

We first compute $W = \sum_{j=1}^n |x_i|$ and $w = \sum_{j=1}^n j\, |x_i|$. Then we search for the index $k$ that satisfies

\[ k \leq \frac{w}{W} < k+1. \]

The branches are then

\[ x_1 = 0, \ldots, x_k = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0. \]

If the constraint contains two variables, the branching of course simplifies.

Depending on the parameters (branchnonzeros, branchweight) there are three ways to choose the branching constraint.

branchnonzeros branchweight constraint chosen
true ? most number of nonzeros
false true maximal weight corresponding to nonzero variable
false true largest sum of variable values

branchnonzeros = false, branchweight = true allows the user to specify an order for the branching importance of the constraints (setting the weights accordingly).

Constraint branching can also be turned off using parameter branchsos.

Parameters
scipSCIP pointer
conshdlrconstraint handler
nconssnumber of constraints
conssindicator constraints
resultresult

Definition at line 5747 of file cons_sos1.c.

References branchCons(), fixVariableZeroNode(), initTCliquegraph(), NULL, propConsSOS1(), REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIP_REAL_MAX, SCIP_REDUCEDDOM, SCIPcalcChildEstimate(), SCIPcalcNodeselPriority(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMessage, SCIPerrorMessage, SCIPfloor(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetName(), and SCIPvarIsBinary().

Referenced by enforceConflictgraph().

static SCIP_RETCODE initTCliquegraph ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH conflictgraph,
int  nsos1vars 
)
static
static SCIP_RETCODE updateWeightsTCliquegraph ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
TCLIQUE_DATA tcliquedata,
SCIP_DIGRAPH conflictgraph,
SCIP_SOL sol,
int  nsos1vars 
)
static

update weights of tclique graph

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
tcliquedatatclique data
conflictgraphconflict graph
solLP solution to be separated (or NULL)
nsos1varsnumber of SOS1 variables

Definition at line 6063 of file cons_sos1.c.

References addBoundCutSepa(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), REALABS, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tcliqueChangeWeight().

Referenced by initTCliquegraph(), and sepaBoundInequalitiesFromGraph().

static SCIP_RETCODE addBoundCutSepa ( SCIP scip,
TCLIQUE_DATA tcliquedata,
SCIP_ROW rowlb,
SCIP_ROW rowub,
SCIP_Bool success,
SCIP_Bool cutoff 
)
static

adds bound cut(s) to separation storage

Parameters
scipSCIP pointer
tcliquedataclique data
rowlbrow for lower bounds (or NULL)
rowubrow for upper bounds (or NULL)
successpointer to store if bound cut was added
cutoffpointer to store if a cutoff occurred

Definition at line 6123 of file cons_sos1.c.

References FALSE, generateBoundInequalityFromSOS1Nodes(), TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPdebug, SCIPisCutEfficacious(), SCIPprintRow(), SCIProwIsInLP(), and TRUE.

Referenced by updateWeightsTCliquegraph().

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

Generate bound constraint

We generate the row corresponding to the following simple valid inequalities:

\[ \frac{x_1}{u_1} + \ldots + \frac{x_n}{u_n} \leq 1\qquad\mbox{and}\qquad \frac{x_1}{\ell_1} + \ldots + \frac{x_n}{\ell_1} \leq 1, \]

where $\ell_1, \ldots, \ell_n$ and $u_1, \ldots, u_n$ are the nonzero and finite lower and upper bounds of the variables $x_1, \ldots, x_n$. If an upper bound < 0 or a lower bound > 0, the constraint itself is redundant, so the cut is not applied (lower bounds > 0 and upper bounds < 0 are usually detected in presolving or propagation). Infinite bounds and zero are skipped. Thus $\ell_1, \ldots, \ell_n$ are all negative, which results in the $\leq$ inequality. In case of the presence of variable upper bounds, the bound inequality can be further strengthened.

Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most interesting.

Parameters
scipSCIP pointer
conshdlrconstraint handler
conflictgraphconflict graph
nodesconflict graph nodes for bound constraint
nnodesnumber of conflict graph nodes for bound constraint
rhsright hand side of bound constraint
localin any case produce a local cut (even if local bounds of variables are valid globally)
globalin any case produce a global cut
strengthenwhether trying to strengthen bound constraint
removableshould the inequality be removed from the LP due to aging or cleanup?
nameextpart of name of bound constraints
rowlboutput: row for lower bounds (or NULL if not needed)
rowuboutput: row for upper bounds (or NULL if not needed)

Definition at line 6197 of file cons_sos1.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowCons(), SCIPdebug, SCIPdigraphGetNodeData(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPprintRow(), SCIPsnprintf(), SCIPvarCompare(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TCLIQUE_NEWSOL(), and TRUE.

Referenced by addBoundCutSepa(), and generateBoundInequalityFromSOS1Cons().

static TCLIQUE_NEWSOL ( tcliqueNewsolClique  )
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 6489 of file cons_sos1.c.

Referenced by generateBoundInequalityFromSOS1Nodes().

static SCIP_RETCODE sepaBoundInequalitiesFromGraph ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_SOL sol,
int  maxboundcuts,
int *  ngen,
SCIP_Bool cutoff 
)
static

separate bound inequalities from conflict graph

Parameters
scipSCIP pointer
conshdlrconstraint handler
conshdlrdataconstraint handler data
solLP solution to be separated (or NULL)
maxboundcutsmaximal number of bound cuts separated per separation round (-1: no limit)
ngenpointer to store number of cuts generated
cutoffpointer whether a cutoff occurred

Definition at line 6624 of file cons_sos1.c.

References TCLIQUE_Data::cutoff, FALSE, generateBoundInequalityFromSOS1Cons(), TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), TCLIQUE_Data::sol, tcliqueMaxClique(), and updateWeightsTCliquegraph().

Referenced by separateSOS1().

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

Generate a bound constraint from the variables of an SOS1 constraint (see generateBoundInequalityFromSOS1Nodes() for more information)

Parameters
scipSCIP pointer
conshdlrconstraint handler
consSOS1 constraint
localin any case produce a local cut (even if local bounds of variables are valid globally)
globalin any case produce a global cut
strengthenwhether trying to strengthen bound constraint
removableshould the inequality be removed from the LP due to aging or cleanup?
rowlboutput: row for lower bounds (or NULL if not needed)
rowuboutput: row for upper bounds (or NULL if not needed)

Definition at line 6698 of file cons_sos1.c.

References CONSHDLR_NAME, generateBoundInequalityFromSOS1Nodes(), initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varGetNodeSOS1().

Referenced by initsepaBoundInequalityFromSOS1Cons(), and sepaBoundInequalitiesFromGraph().

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

initialize or separate bound inequalities from SOS1 constraints

Parameters
scipSCIP pointer
conshdlrconstraint handler
conshdlrdataconstraint handler data
conssSOS1 constraints
nconssnumber of SOS1 constraints
solLP solution to be separated (or NULL)
solvedinitlpTRUE if initial LP relaxation at a node is solved
maxboundcutsmaximal number of bound cuts separated per separation round (-1: no limit)
ngenpointer to store number of cuts generated (or NULL)
cutoffpointer to store whether a cutoff occurred

Definition at line 6761 of file cons_sos1.c.

References FALSE, generateBoundInequalityFromSOS1Cons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMessage, SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIProwIsInLP(), sepaImplBoundCutsSOS1(), and TRUE.

Referenced by generateBoundInequalityFromSOS1Cons(), and separateSOS1().

static SCIP_RETCODE sepaImplBoundCutsSOS1 ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_SOL sol,
int  maxcuts,
int *  ngen,
SCIP_Bool cutoff 
)
static

separate implied bound cuts

Parameters
scipSCIP pointer
conshdlrconstraint handler
conshdlrdataconstraint handler data
solLP solution to be separated (or NULL)
maxcutsmaximal number of implied bound cuts separated per separation round (-1: no limit)
ngenpointer to store number of cuts generated
cutoffpointer whether a cutoff occurred

Definition at line 6871 of file cons_sos1.c.

References FALSE, initImplGraphSOS1(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPdebugMessage, SCIPdigraphGetNArcs(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPflushRowExtensions(), SCIPgetDepth(), SCIPgetSolVal(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasZero(), SCIPisInfinity(), SCIPprintRow(), SCIPreleaseRow(), SCIProwIsInLP(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), separateSOS1(), and TRUE.

Referenced by initsepaBoundInequalityFromSOS1Cons(), and separateSOS1().

static SCIP_RETCODE separateSOS1 ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
int  nconss,
SCIP_CONS **  conss,
SCIP_RESULT result 
)
static

separates SOS1 constraints for arbitrary solutions

Parameters
scipSCIP pointer
conshdlrconstraint handler
solsolution to be separated (or NULL)
nconssnumber of constraints
conssSOS1 constraints
resultresult

Definition at line 7088 of file cons_sos1.c.

References getVectorOfWeights(), initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMessage, SCIPgetDepth(), SCIPisStopped(), sepaBoundInequalitiesFromGraph(), sepaImplBoundCutsSOS1(), and TRUE.

Referenced by sepaImplBoundCutsSOS1().

static SCIP_RETCODE getVectorOfWeights ( SCIP scip,
SCIP_SOL sol,
SCIP_DIGRAPH conflictgraph,
int  nsos1vars,
SCIP_Bool indicatorzero,
SCIP_Real weights 
)
static

gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem

Parameters
scipSCIP pointer
solprimal solution or NULL for current LP solution
conflictgraphconflict graph
nsos1varsnumber of SOS1 variables
indicatorzerovector that indicates which variables are currently fixed to zero
weightspointer to store weights determining the order of the variables (length = nsos1vars)

Definition at line 7209 of file cons_sos1.c.

References markNeighborsMWISHeuristic(), MIN, NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPgetSolVal(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), and SCIPsumepsilon().

Referenced by maxWeightIndSetHeuristic(), and separateSOS1().

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
Parameters
scipSCIP pointer
conshdlrSOS1 constraint handler
conflictgraphconflict graph
nodenode of the conflict graph
markindicator vector of processed nodes
indsetindicator vector of current independent
cntpointer to store number of marked nodes
cutoffpointer to store whether operation is infeasible

Definition at line 7280 of file cons_sos1.c.

References FALSE, maxWeightIndSetHeuristic(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_NEGATED, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPvarGetAggrConstant(), SCIPvarGetAggrVar(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetNodeSOS1(), SCIPvarGetStatus(), and TRUE.

Referenced by getVectorOfWeights(), and maxWeightIndSetHeuristic().

static SCIP_RETCODE maxWeightIndSetHeuristic ( SCIP scip,
SCIP_SOL sol,
SCIP_CONSHDLR conshdlr,
SCIP_DIGRAPH conflictgraph,
int  nsos1vars,
SCIP_Bool indicatorzero,
SCIP_Bool indset 
)
static

calls greedy algorithm for the maximum weighted independent set problem (MWIS)

We compute a feasible solution to

\[ \begin{array}{ll} \min\limits_{z} & {x^*}^T z \\ & z_i + z_j \leq 1, \qquad (i,j)\in E \\ & z_i \in \{0,1\}, \qquad\quad i\in V \end{array} \]

by the algorithm GGWMIN of Shuichi Sakai, Mitsunori Togasaki and Koichi Yamazaki in "A note on greedy algorithms for the maximum weighted independent set problem", Discrete Applied Mathematics. Here $x^*$ denotes the current LP relaxation solution. Note that the solution of the MWIS is the indicator vector of an independent set.

Parameters
scipSCIP pointer
solprimal solution or NULL for current LP solution
conshdlrSOS1 constraint handler
conflictgraphconflict graph
nsos1varsnumber of SOS1 variables
indicatorzerovector that indicates which variables are currently fixed to zero
indsetpointer to store indicator vector of an independent set

Definition at line 7421 of file cons_sos1.c.

References FALSE, getVectorOfWeights(), makeSOS1conflictgraphFeasible(), markNeighborsMWISHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdigraphGetNSuccessors(), SCIPfreeBufferArrayNull, SCIPsortDownRealInt(), and TRUE.

Referenced by makeSOS1conflictgraphFeasible(), and markNeighborsMWISHeuristic().

static SCIP_RETCODE makeSOS1conflictgraphFeasible ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
SCIP_Bool changed,
SCIP_Bool allroundable 
)
static

based on solution values of the variables, fixes variables of the conflict graph to zero to turn all SOS1 constraints feasible

if the SOS1 constraints do not overlap, the method makeSOS1constraintsFeasible() may be faster

Parameters
scipSCIP pointer
conshdlrSOS1 constraint handler
solsolution
changedpointer to store whether the solution has been changed
allroundablepointer to store whether all variables are roundable

Definition at line 7527 of file cons_sos1.c.

References FALSE, makeSOS1constraintsFeasible(), maxWeightIndSetHeuristic(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfreeBufferArray, SCIPgetConflictgraphSOS1(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPnodeGetVarSOS1(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.

Referenced by maxWeightIndSetHeuristic(), and SCIPmakeSOS1sFeasible().

static SCIP_RETCODE makeSOS1constraintsFeasible ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
SCIP_Bool changed,
SCIP_Bool allroundable 
)
static

based on solution values of the variables, fixes variables of the SOS1 constraints to zero to turn these constraints feasible

if the SOS1 constraints overlap, the method makeSOS1constraintsFeasible() may result in better primal solutions

Parameters
scipSCIP pointer
conshdlrSOS1 constraint handler
solsolution
changedpointer to store whether the solution has been changed
allroundablepointer to store whether all variables are roundable

Definition at line 7656 of file cons_sos1.c.

References FALSE, getDiveBdChgsSOS1conflictgraph(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPgetSolVal(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.

Referenced by makeSOS1conflictgraphFeasible(), and SCIPmakeSOS1sFeasible().

static SCIP_RETCODE getDiveBdChgsSOS1conflictgraph ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_DIVESET diveset,
SCIP_SOL sol,
SCIP_Bool success 
)
static
static SCIP_RETCODE getDiveBdChgsSOS1constraints ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_DIVESET diveset,
SCIP_SOL sol,
SCIP_Bool success 
)
static

determine a diving variables and boundchanges of diving variables by analyzing the SOS1 constraints

if the SOS1 constraints overlap, the method getDiveBdChgsSOS1conflictgraph() may produce better results (e.g., due to more diving candidates)

Parameters
scipSCIP pointer
conshdlrSOS1 constraint handler
divesetdiving settings
solsolution
successpointer to store

Definition at line 7930 of file cons_sos1.c.

References detectVarboundSOS1(), DIVINGCUTOFFVALUE, FALSE, MIN, NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdivesetSupportsType(), SCIPgetDivesetScore(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisPositive(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by getDiveBdChgsSOS1conflictgraph().

static SCIP_RETCODE detectVarboundSOS1 ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR var0,
SCIP_VAR var1,
SCIP_Real  val0,
SCIP_Real  val1 
)
static

check whether $x_1$ is a bound variable of $x_0$; i.e., $x_0 \leq c\cdot x_1$ or $x_0 \geq d\cdot x_1$ for positive values $c, d$. If true, then add this information to the node data of the conflict graph.

Parameters
scipSCIP pointer
conshdlrdataSOS1 constraint handler data
var0first variable
var1second variable
val0first coefficient
val1second coefficient

Definition at line 8108 of file cons_sos1.c.

References NULL, passConComponentVarbound(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1().

Referenced by checkLinearConssVarboundSOS1(), and getDiveBdChgsSOS1constraints().

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

pass connected component $C$ of the conflict graph and check whether all the variables correspond to a unique variable upper bound variable $z$, i.e., $x_i \leq u_i z$ for every $i\in C$.

Note
if the bound variable is unique, then bound inequalities can be strengthened.
Parameters
scipSCIP pointer
conflictgraphconflict graph
nodecurrent node of connected component
boundvarbound variable of connected component
checklbwhether to check lower bound variable (else upper bound variable)
processedstates for each variable whether it has been processed
concompcurrent connected component
nconcomppointer to store number of elements of connected component
uniquepointer to store whether bound variable is unique

Definition at line 8184 of file cons_sos1.c.

References checkConComponentsVarbound(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE.

Referenced by checkConComponentsVarbound(), and detectVarboundSOS1().

static SCIP_RETCODE checkConComponentsVarbound ( SCIP scip,
SCIP_DIGRAPH conflictgraph,
int  nsos1vars,
SCIP_Bool  checklb 
)
static

for each connected component $C$ of the conflict graph check whether all the variables correspond to a unique variable upper bound variable $z$ (e.g., for the upper bound case this means that $x_i \leq u_i z$ for every $i\in C$).

Note
if the bound variable is unique, then bound inequalities can be strengthened.
Parameters
scipSCIP pointer
conflictgraphconflict graph
nsos1varsnumber of SOS1 variables
checklbwhether to check lower bound variable (else check upper bound variable)

Definition at line 8257 of file cons_sos1.c.

References checkLinearConssVarboundSOS1(), FALSE, NULL, passConComponentVarbound(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArray, and TRUE.

Referenced by passConComponentVarbound().

static SCIP_RETCODE checkLinearConssVarboundSOS1 ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS **  linconss,
int  nlinconss 
)
static

check all linear constraints for variable bound constraints of the form $c\cdot z \leq x \leq d\cdot z$, where x is some SOS1 variable and z is some arbitrary variable (not necessarily binary)

Parameters
scipSCIP pointer
conshdlrdataSOS1 constraint handler data
linconsslinear constraints
nlinconssnumber of linear constraints

Definition at line 8346 of file cons_sos1.c.

References checkSwitchNonoverlappingSOS1Methods(), detectVarboundSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasZero(), and varIsSOS1().

Referenced by checkConComponentsVarbound().

static SCIP_RETCODE checkSwitchNonoverlappingSOS1Methods ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH conflictgraph,
SCIP_CONS **  conss,
int  nconss 
)
static

switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap

Parameters
scipSCIP pointer
conshdlrdataSOS1 constraint handler data
conflictgraphconflict graph
conssSOS1 constraints
nconssnumber of SOS1 constraints

Definition at line 8419 of file cons_sos1.c.

References computeNodeDataSOS1(), FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPdebugMessage, SCIPdigraphGetNSuccessors(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().

Referenced by checkLinearConssVarboundSOS1().

static SCIP_RETCODE computeNodeDataSOS1 ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
int  nsos1vars 
)
static

sets node data of conflict graph nodes

Parameters
scipSCIP pointer
conshdlrdataSOS1 constraint handler data
nsos1varsnumber of SOS1 variables

Definition at line 8500 of file cons_sos1.c.

Referenced by checkSwitchNonoverlappingSOS1Methods().

static SCIP_RETCODE initConflictgraph ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS **  conss,
int  nconss 
)
static
static SCIP_RETCODE freeConflictgraph ( SCIP_CONSHDLRDATA conshdlrdata)
static

free conflict graph, nodedata and hashmap

Parameters
conshdlrdataconstraint handler data

Definition at line 8732 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphSetNodeData(), SCIPfreeMemory, and SCIPhashmapFree().

Referenced by initConflictgraph().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySOS1  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 8777 of file cons_sos1.c.

Referenced by freeConflictgraph().

static SCIP_DECL_CONSFREE ( consFreeSOS1  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 8794 of file cons_sos1.c.

static SCIP_DECL_CONSINITSOL ( consInitsolSOS1  )
static

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

Definition at line 8813 of file cons_sos1.c.

static SCIP_DECL_CONSEXITSOL ( consExitsolSOS1  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 8866 of file cons_sos1.c.

static SCIP_DECL_CONSDELETE ( consDeleteSOS1  )
static

frees specific constraint data

Definition at line 8938 of file cons_sos1.c.

static SCIP_DECL_CONSTRANS ( consTransSOS1  )
static

transforms constraint data into data belonging to the transformed problem

Definition at line 8992 of file cons_sos1.c.

static SCIP_DECL_CONSPRESOL ( consPresolSOS1  )
static

presolving method of constraint handler

Definition at line 9084 of file cons_sos1.c.

static SCIP_DECL_CONSINITLP ( consInitlpSOS1  )
static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 9207 of file cons_sos1.c.

static SCIP_DECL_CONSSEPALP ( consSepalpSOS1  )
static

separation method of constraint handler for LP solutions

Definition at line 9232 of file cons_sos1.c.

static SCIP_DECL_CONSSEPASOL ( consSepasolSOS1  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 9248 of file cons_sos1.c.

static SCIP_DECL_CONSENFOLP ( consEnfolpSOS1  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 9264 of file cons_sos1.c.

static SCIP_DECL_CONSENFOPS ( consEnfopsSOS1  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 9319 of file cons_sos1.c.

static SCIP_DECL_CONSCHECK ( consCheckSOS1  )
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 9377 of file cons_sos1.c.

static SCIP_DECL_CONSPROP ( consPropSOS1  )
static

domain propagation method of constraint handler

Definition at line 9445 of file cons_sos1.c.

static SCIP_DECL_CONSRESPROP ( consRespropSOS1  )
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 9590 of file cons_sos1.c.

static SCIP_DECL_CONSLOCK ( consLockSOS1  )
static

variable rounding lock method of constraint handler

Let lb and ub be the lower and upper bounds of a variable. Preprocessing usually makes sure that lb <= 0 <= ub.

  • If lb < 0 then rounding down may violate the constraint.
  • If ub > 0 then rounding up may violated the constraint.
  • If lb > 0 or ub < 0 then the constraint is infeasible and we do not have to deal with it here.
  • If lb == 0 then rounding down does not violate the constraint.
  • If ub == 0 then rounding up does not violate the constraint.

Definition at line 9666 of file cons_sos1.c.

static SCIP_DECL_CONSPRINT ( consPrintSOS1  )
static

constraint display method of constraint handler

Definition at line 9710 of file cons_sos1.c.

static SCIP_DECL_CONSCOPY ( consCopySOS1  )
static

constraint copying method of constraint handler

Definition at line 9740 of file cons_sos1.c.

static SCIP_DECL_CONSPARSE ( consParseSOS1  )
static

constraint parsing method of constraint handler

Definition at line 9806 of file cons_sos1.c.

static SCIP_DECL_CONSGETVARS ( consGetVarsSOS1  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 9870 of file cons_sos1.c.

References BMScopyMemoryArray, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSOS1  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 9893 of file cons_sos1.c.

Referenced by SCIP_DECL_CONSGETVARS().

static SCIP_DECL_EVENTEXEC ( eventExecSOS1  )
static

exec the event handler

We update the number of variables fixed to be nonzero

Definition at line 9914 of file cons_sos1.c.

static SCIP_DECL_CONSGETDIVEBDCHGS ( consGetDiveBdChgsSOS1  )
static

constraint handler method to determine a diving variable by assigning a variable and two values for diving

Definition at line 10011 of file cons_sos1.c.

SCIP_RETCODE SCIPincludeConshdlrSOS1 ( SCIP scip)

creates the handler for SOS1 constraints and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 10052 of file cons_sos1.c.

Referenced by SCIPincludeDefaultPlugins().

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 
)

creates and captures a SOS1 constraint

We set the constraint to not be modifable. If the weights are non NULL, the variables are ordered according to these weights (in ascending order).

Note
The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
weightsweights determining the variable order, or NULL if natural order should be used
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 10266 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, handleNewVariableSOS1(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STAGE_TRANSFORMED, SCIPallocBlockMemory, SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPcreateCons(), SCIPcreateConsBasicSOS1(), SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfindConshdlr(), SCIPgetStage(), SCIPgetTransformedVar(), SCIPmarkDoNotMultaggrVar(), SCIPsortRealPtr(), and SCIPvarIsTransformed().

Referenced by addBranchingComplementaritiesSOS1(), extensionOperatorSOS1(), performImplicationGraphAnalysis(), readSOS(), readSos(), readSOScons(), and SCIPcreateConsBasicSOS1().

SCIP_RETCODE SCIPcreateConsBasicSOS1 ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real weights 
)

creates and captures a SOS1 constraint with all constraint flags set to their default values.

Warning
Do NOT set the constraint to be modifiable manually, because this might lead to wrong results as the variable array will not be resorted
Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
weightsweights determining the variable order, or NULL if natural order should be used

Definition at line 10387 of file cons_sos1.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarSOS1(), SCIPcreateConsSOS1(), and TRUE.

Referenced by SCIPcreateConsSOS1().

SCIP_RETCODE SCIPaddVarSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_Real  weight 
)

adds variable to SOS1 constraint, the position is determined by the given weight

Parameters
scipSCIP data structure
consconstraint
varvariable to add to the constraint
weightweight determining position of variable

Definition at line 10403 of file cons_sos1.c.

References addVarSOS1(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPappendVarSOS1(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPerrorMessage, and SCIPvarGetName().

Referenced by readSOS(), readSos(), readSOScons(), and SCIPcreateConsBasicSOS1().

SCIP_RETCODE SCIPappendVarSOS1 ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var 
)

appends variable to SOS1 constraint

Parameters
scipSCIP data structure
consconstraint
varvariable to add to the constraint

Definition at line 10437 of file cons_sos1.c.

Referenced by SCIPaddVarSOS1().

int SCIPgetNVarsSOS1 ( SCIP scip,
SCIP_CONS cons 
)

gets number of variables in SOS1 constraint

Parameters
scipSCIP data structure
consconstraint

Definition at line 10470 of file cons_sos1.c.

Referenced by SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp().

SCIP_VAR** SCIPgetVarsSOS1 ( SCIP scip,
SCIP_CONS cons 
)

gets array of variables in SOS1 constraint

Parameters
scipSCIP data structure
consconstraint data

Definition at line 10495 of file cons_sos1.c.

Referenced by SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp().

SCIP_Real* SCIPgetWeightsSOS1 ( SCIP scip,
SCIP_CONS cons 
)

gets array of weights in SOS1 constraint (or NULL if not existent)

Parameters
scipSCIP data structure
consconstraint data

Definition at line 10520 of file cons_sos1.c.

Referenced by SCIP_DECL_READERWRITE(), and SCIPwriteLp().

SCIP_DIGRAPH* SCIPgetConflictgraphSOS1 ( SCIP_CONSHDLR conshdlr)

gets conflict graph of SOS1 constraints (or NULL if not existent)

Note
The conflict graph is globally valid; local changes are not taken into account.
Parameters
conshdlrSOS1 constraint handler

Definition at line 10548 of file cons_sos1.c.

Referenced by getDiveBdChgsSOS1conflictgraph(), makeSOS1conflictgraphFeasible(), SCIP_DECL_SEPAEXECLP(), and sepaBoundInequalitiesFromGraph().

int SCIPgetNSOS1Vars ( SCIP_CONSHDLR conshdlr)

gets number of problem variables that are part of the SOS1 conflict graph

Parameters
conshdlrSOS1 constraint handler

Definition at line 10570 of file cons_sos1.c.

Referenced by getDiveBdChgsSOS1conflictgraph(), makeSOS1conflictgraphFeasible(), SCIP_DECL_SEPAEXECLP(), SCIPperformGenericDivingAlgorithm(), and sepaBoundInequalitiesFromGraph().

SCIP_Bool SCIPvarIsSOS1 ( SCIP_CONSHDLR conshdlr,
SCIP_VAR var 
)

returns whether variable is part of the SOS1 conflict graph

Parameters
conshdlrconstraint handler
varvariable

Definition at line 10592 of file cons_sos1.c.

int SCIPvarGetNodeSOS1 ( SCIP_CONSHDLR conshdlr,
SCIP_VAR var 
)

returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph

Parameters
conshdlrSOS1 constraint handler
varvariable

Definition at line 10616 of file cons_sos1.c.

Referenced by markNeighborsMWISHeuristic().

SCIP_RETCODE SCIPmakeSOS1sFeasible ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
SCIP_Bool changed,
SCIP_Bool success 
)

based on solution values of the variables, fixes variables to zero to turn all SOS1 constraints feasible

Parameters
scipSCIP pointer
conshdlrSOS1 constraint handler
solsolution
changedpointer to store whether the solution has been changed
successpointer to store whether SOS1 constraints have been turned feasible and solution was good enough

Definition at line 10672 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, makeSOS1conflictgraphFeasible(), makeSOS1constraintsFeasible(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrGetNConss(), SCIPerrorMessage, SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPgetUpperbound(), SCIPisLT(), and TRUE.

Referenced by SCIPperformGenericDivingAlgorithm().