# SCIP

Solving Constraint Integer Programs

cons_sos1.c File Reference

## Detailed Description

constraint handler for SOS type 1 constraints

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

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

The order of the variables is determined as follows:

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

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

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

Definition in file cons_sos1.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/cons_setppc.h"
#include "scip/cons_sos1.h"
#include "scip/pub_cons.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_datastructures.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "tclique/tclique.h"
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

## Data Structures

struct  TCLIQUE_Data

## 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_MAXEXTENSIONS   1

#define DEFAULT_MAXTIGHTENBDS   5

#define DEFAULT_PERFIMPLANALYSIS   FALSE

#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_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 EVENTHDLR_EVENT_TYPE   (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

#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_SOL *sol, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int branchvertex, int *fixingsnode1, int *nfixingsnode1, int *fixingsnode2, int *nfixingsnode2)

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

static SCIP_RETCODE performStrongbranchSOS1 (SCIP *scip, SCIP_DIGRAPH *conflictgraph, int *fixingsexec, int nfixingsexec, int *fixingsop, int nfixingsop, int inititer, SCIP_Bool fixnonzero, int *domainfixings, int *ndomainfixings, SCIP_Bool *infeasible, SCIP_Real *objval, SCIP_Bool *lperror)

static SCIP_RETCODE getBranchingDecisionStrongbranchSOS1 (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars, SCIP_Real lpobjval, SCIP_Bool bipbranch, int nstrongrounds, SCIP_Bool *verticesarefixed, int *fixingsnode1, int *fixingsnode2, int *vertexbestprior, SCIP_Real *bestobjval1, SCIP_Real *bestobjval2, SCIP_RESULT *result)

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

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

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

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

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

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

static SCIP_RETCODE initTCliquegraph (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars)

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

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

static SCIP_RETCODE generateBoundInequalityFromSOS1Nodes (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int *nodes, int nnodes, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool global, SCIP_Bool strengthen, SCIP_Bool removable, const char *nameext, SCIP_ROW **rowlb, SCIP_ROW **rowub)

static TCLIQUE_NEWSOL (tcliqueNewsolClique)

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

static SCIP_RETCODE generateBoundInequalityFromSOS1Cons (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool local, SCIP_Bool global, SCIP_Bool strengthen, SCIP_Bool removable, SCIP_ROW **rowlb, SCIP_ROW **rowub)

static SCIP_RETCODE initsepaBoundInequalityFromSOS1Cons (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool solvedinitlp, int maxboundcuts, int *ngen, SCIP_Bool *cutoff)

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

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

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

static SCIP_RETCODE markNeighborsMWISHeuristic (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int node, SCIP_Bool *mark, SCIP_Bool *indset, int *cnt, SCIP_Bool *cutoff)

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

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

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

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

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

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

static SCIP_RETCODE passConComponentVarbound (SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_VAR *boundvar, SCIP_Bool checklb, SCIP_Bool *processed, int *concomp, int *nconcomp, SCIP_Bool *unique)

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

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

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

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

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

static SCIP_RETCODE freeConflictgraph (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)

static SCIP_DECL_CONSHDLRCOPY (conshdlrCopySOS1)

static SCIP_DECL_CONSFREE (consFreeSOS1)

static SCIP_DECL_CONSINITSOL (consInitsolSOS1)

static SCIP_DECL_CONSEXITSOL (consExitsolSOS1)

static SCIP_DECL_CONSDELETE (consDeleteSOS1)

static SCIP_DECL_CONSTRANS (consTransSOS1)

static SCIP_DECL_CONSPRESOL (consPresolSOS1)

static SCIP_DECL_CONSINITLP (consInitlpSOS1)

static SCIP_DECL_CONSSEPALP (consSepalpSOS1)

static SCIP_DECL_CONSSEPASOL (consSepasolSOS1)

static SCIP_DECL_CONSENFOLP (consEnfolpSOS1)

static SCIP_DECL_CONSENFORELAX (consEnforelaxSOS1)

static SCIP_DECL_CONSENFOPS (consEnfopsSOS1)

static SCIP_DECL_CONSCHECK (consCheckSOS1)

static SCIP_DECL_CONSPROP (consPropSOS1)

static SCIP_DECL_CONSRESPROP (consRespropSOS1)

static SCIP_DECL_CONSLOCK (consLockSOS1)

static SCIP_DECL_CONSPRINT (consPrintSOS1)

static SCIP_DECL_CONSCOPY (consCopySOS1)

static SCIP_DECL_CONSPARSE (consParseSOS1)

static SCIP_DECL_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)

## ◆ CONSHDLR_NAME

 #define CONSHDLR_NAME   "SOS1"

Definition at line 112 of file cons_sos1.c.

## ◆ CONSHDLR_DESC

 #define CONSHDLR_DESC   "SOS1 constraint handler"

Definition at line 113 of file cons_sos1.c.

## ◆ CONSHDLR_SEPAPRIORITY

 #define CONSHDLR_SEPAPRIORITY   1000

priority of the constraint handler for separation

Definition at line 114 of file cons_sos1.c.

## ◆ CONSHDLR_ENFOPRIORITY

 #define CONSHDLR_ENFOPRIORITY   100

priority of the constraint handler for constraint enforcing

Definition at line 115 of file cons_sos1.c.

## ◆ CONSHDLR_CHECKPRIORITY

 #define CONSHDLR_CHECKPRIORITY   -10

priority of the constraint handler for checking feasibility

Definition at line 116 of file cons_sos1.c.

## ◆ CONSHDLR_SEPAFREQ

 #define CONSHDLR_SEPAFREQ   10

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

Definition at line 117 of file cons_sos1.c.

## ◆ CONSHDLR_PROPFREQ

 #define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 118 of file cons_sos1.c.

## ◆ CONSHDLR_EAGERFREQ

 #define CONSHDLR_EAGERFREQ   100

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

Definition at line 119 of file cons_sos1.c.

## ◆ CONSHDLR_MAXPREROUNDS

 #define CONSHDLR_MAXPREROUNDS   -1

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

Definition at line 122 of file cons_sos1.c.

## ◆ CONSHDLR_DELAYSEPA

 #define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 123 of file cons_sos1.c.

## ◆ CONSHDLR_DELAYPROP

 #define CONSHDLR_DELAYPROP   FALSE

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

Definition at line 124 of file cons_sos1.c.

## ◆ CONSHDLR_NEEDSCONS

 #define CONSHDLR_NEEDSCONS   TRUE

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

Definition at line 125 of file cons_sos1.c.

## ◆ CONSHDLR_PROP_TIMING

 #define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 126 of file cons_sos1.c.

## ◆ CONSHDLR_PRESOLTIMING

 #define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM

Definition at line 127 of file cons_sos1.c.

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

Definition at line 130 of file cons_sos1.c.

## ◆ DEFAULT_MAXEXTENSIONS

 #define DEFAULT_MAXEXTENSIONS   1

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

Definition at line 135 of file cons_sos1.c.

## ◆ DEFAULT_MAXTIGHTENBDS

 #define DEFAULT_MAXTIGHTENBDS   5

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

Definition at line 136 of file cons_sos1.c.

## ◆ DEFAULT_PERFIMPLANALYSIS

 #define DEFAULT_PERFIMPLANALYSIS   FALSE

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

Definition at line 137 of file cons_sos1.c.

## ◆ DEFAULT_DEPTHIMPLANALYSIS

 #define DEFAULT_DEPTHIMPLANALYSIS   -1

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

Definition at line 138 of file cons_sos1.c.

## ◆ DEFAULT_CONFLICTPROP

 #define DEFAULT_CONFLICTPROP   TRUE

whether to use conflict graph propagation

Definition at line 141 of file cons_sos1.c.

## ◆ DEFAULT_IMPLPROP

 #define DEFAULT_IMPLPROP   TRUE

whether to use implication graph propagation

Definition at line 142 of file cons_sos1.c.

## ◆ DEFAULT_SOSCONSPROP

 #define DEFAULT_SOSCONSPROP   FALSE

whether to use SOS1 constraint propagation

Definition at line 143 of file cons_sos1.c.

## ◆ DEFAULT_BRANCHSTRATEGIES

 #define DEFAULT_BRANCHSTRATEGIES   "nbs"

possible branching strategies (see parameter DEFAULT_BRANCHINGRULE)

Definition at line 146 of file cons_sos1.c.

## ◆ DEFAULT_BRANCHINGRULE

 #define DEFAULT_BRANCHINGRULE   'n'

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

Definition at line 147 of file cons_sos1.c.

## ◆ DEFAULT_AUTOSOS1BRANCH

 #define DEFAULT_AUTOSOS1BRANCH   TRUE

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

Definition at line 150 of file cons_sos1.c.

## ◆ DEFAULT_FIXNONZERO

 #define DEFAULT_FIXNONZERO   FALSE

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

Definition at line 151 of file cons_sos1.c.

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

Definition at line 154 of file cons_sos1.c.

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

Definition at line 157 of file cons_sos1.c.

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

Definition at line 158 of file cons_sos1.c.

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

Definition at line 159 of file cons_sos1.c.

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

Definition at line 160 of file cons_sos1.c.

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

Definition at line 161 of file cons_sos1.c.

## ◆ DEFAULT_NSTRONGROUNDS

 #define DEFAULT_NSTRONGROUNDS   0

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

Definition at line 164 of file cons_sos1.c.

## ◆ DEFAULT_NSTRONGITER

 #define DEFAULT_NSTRONGITER   10000

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

Definition at line 167 of file cons_sos1.c.

## ◆ DEFAULT_BOUNDCUTSFROMSOS1

 #define DEFAULT_BOUNDCUTSFROMSOS1   FALSE

if TRUE separate bound inequalities from SOS1 constraints

Definition at line 170 of file cons_sos1.c.

## ◆ DEFAULT_BOUNDCUTSFROMGRAPH

 #define DEFAULT_BOUNDCUTSFROMGRAPH   TRUE

if TRUE separate bound inequalities from the conflict graph

Definition at line 171 of file cons_sos1.c.

## ◆ DEFAULT_AUTOCUTSFROMSOS1

 #define DEFAULT_AUTOCUTSFROMSOS1   TRUE

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

Definition at line 172 of file cons_sos1.c.

## ◆ DEFAULT_BOUNDCUTSFREQ

 #define DEFAULT_BOUNDCUTSFREQ   10

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

Definition at line 173 of file cons_sos1.c.

## ◆ DEFAULT_BOUNDCUTSDEPTH

 #define DEFAULT_BOUNDCUTSDEPTH   40

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

Definition at line 174 of file cons_sos1.c.

## ◆ DEFAULT_MAXBOUNDCUTS

 #define DEFAULT_MAXBOUNDCUTS   50

maximal number of bound cuts separated per branching node

Definition at line 175 of file cons_sos1.c.

## ◆ DEFAULT_MAXBOUNDCUTSROOT

 #define DEFAULT_MAXBOUNDCUTSROOT   150

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

Definition at line 176 of file cons_sos1.c.

## ◆ DEFAULT_STRTHENBOUNDCUTS

 #define DEFAULT_STRTHENBOUNDCUTS   TRUE

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

Definition at line 177 of file cons_sos1.c.

## ◆ DEFAULT_IMPLCUTSFREQ

 #define DEFAULT_IMPLCUTSFREQ   0

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

Definition at line 178 of file cons_sos1.c.

## ◆ DEFAULT_IMPLCUTSDEPTH

 #define DEFAULT_IMPLCUTSDEPTH   40

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

Definition at line 179 of file cons_sos1.c.

## ◆ DEFAULT_MAXIMPLCUTS

 #define DEFAULT_MAXIMPLCUTS   50

maximal number of implied bound cuts separated per branching node

Definition at line 180 of file cons_sos1.c.

## ◆ DEFAULT_MAXIMPLCUTSROOT

 #define DEFAULT_MAXIMPLCUTSROOT   150

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

Definition at line 181 of file cons_sos1.c.

## ◆ EVENTHDLR_NAME

 #define EVENTHDLR_NAME   "SOS1"

Definition at line 184 of file cons_sos1.c.

## ◆ EVENTHDLR_DESC

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

Definition at line 185 of file cons_sos1.c.

## ◆ EVENTHDLR_EVENT_TYPE

 #define EVENTHDLR_EVENT_TYPE   (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

Definition at line 187 of file cons_sos1.c.

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

## ◆ DIVINGCUTOFFVALUE

 #define DIVINGCUTOFFVALUE   1e6

Definition at line 190 of file cons_sos1.c.

Referenced by getDiveBdChgsSOS1conflictgraph(), and getDiveBdChgsSOS1constraints().

## ◆ SCIP_NODEDATA

 typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 220 of file cons_sos1.c.

## ◆ SCIP_SUCCDATA

 typedef struct SCIP_SuccData SCIP_SUCCDATA

Definition at line 229 of file cons_sos1.c.

## ◆ isConnectedSOS1()

 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
 adjacencymatrix adjacency matrix of conflict graph (lower half) (or NULL if an adjacencymatrix is not at hand) conflictgraph conflict graph (or NULL if an adjacencymatrix is at hand) vertex1 first vertex vertex2 second vertex

Definition at line 327 of file cons_sos1.c.

## ◆ isViolatedSOS1()

 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
 scip SCIP data structure conflictgraph conflict graph (or NULL if an adjacencymatrix is at hand) node node of variable in the conflict graph sol solution, or NULL to use current node's solution

Definition at line 387 of file cons_sos1.c.

Referenced by getDiveBdChgsSOS1conflictgraph(), and isConnectedSOS1().

## ◆ nodeGetSolvalBinaryBigMSOS1()

 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
 scip SCIP pointer conflictgraph conflict graph sol primal solution, or NULL for current LP/pseudo solution node node of the conflict graph

Definition at line 432 of file cons_sos1.c.

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

## ◆ nodeGetSolvalVarboundLbSOS1()

 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
 scip SCIP pointer conflictgraph conflict graph sol primal solution, or NULL for current LP/pseudo solution node node of the conflict graph

Definition at line 482 of file cons_sos1.c.

## ◆ nodeGetSolvalVarboundUbSOS1()

 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
 scip SCIP pointer conflictgraph conflict graph sol primal solution, or NULL for current LP/pseudo solution node node of the conflict graph

Definition at line 509 of file cons_sos1.c.

## ◆ varIsSOS1()

 static SCIP_Bool varIsSOS1 ( SCIP_CONSHDLRDATA * conshdlrdata, SCIP_VAR * var )
static

returns whether variable is part of the SOS1 conflict graph

Parameters
 conshdlrdata SOS1 constraint handler var variable

Definition at line 536 of file cons_sos1.c.

Referenced by checkLinearConssVarboundSOS1(), and nodeGetSolvalVarboundUbSOS1().

## ◆ varGetNodeSOS1()

 static int varGetNodeSOS1 ( SCIP_CONSHDLRDATA * conshdlrdata, SCIP_VAR * var )
static

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

Parameters
 conshdlrdata SOS1 constraint handler var variable

Definition at line 553 of file cons_sos1.c.

## ◆ fixVariableZeroNode()

 static SCIP_RETCODE fixVariableZeroNode ( SCIP * scip, SCIP_VAR * var, SCIP_NODE * node, SCIP_Bool * infeasible )
static

fix variable in given node to 0 or add constraint if variable is multi-aggregated

Parameters
 scip SCIP pointer var variable to be fixed to 0 node node infeasible if fixing is infeasible

Definition at line 574 of file cons_sos1.c.

## ◆ fixVariableZero()

 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
 scip SCIP pointer var variable to be fixed to 0 infeasible if fixing is infeasible tightened if fixing was performed

Definition at line 629 of file cons_sos1.c.

Referenced by fixVariableZeroNode(), and presolRoundConsSOS1().

## ◆ inferVariableZero()

 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
 scip SCIP pointer var variable to be fixed to 0 cons constraint inferinfo info for reverse prop. infeasible if fixing is infeasible tightened if fixing was performed success whether fixing was successful, i.e., variable is not multi-aggregated

Definition at line 703 of file cons_sos1.c.

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

## ◆ lockVariableSOS1()

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

Parameters
 scip SCIP data structure cons constraint var variable

Definition at line 746 of file cons_sos1.c.

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

## ◆ unlockVariableSOS1()

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

remove lock on variable

Parameters
 scip SCIP data structure cons constraint var variable

Definition at line 766 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
 scip SCIP data structure consdata constraint data num minimum number of entries to store reserveWeights whether the weights array is handled

Definition at line 786 of file cons_sos1.c.

## ◆ handleNewVariableSOS1()

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

handle new variable

Parameters
 scip SCIP data structure cons constraint consdata constraint data conshdlrdata constraint handler data var variable transformed whether original variable was transformed

Definition at line 814 of file cons_sos1.c.

 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
 scip SCIP data structure cons constraint conshdlrdata constraint handler data var variable to add to the constraint weight weight to determine position

Definition at line 949 of file cons_sos1.c.

## ◆ appendVarSOS1()

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

appends a variable to an SOS1 constraint

Parameters
 scip SCIP data structure cons constraint conshdlrdata constraint handler data var variable to add to the constraint

Definition at line 1019 of file cons_sos1.c.

## ◆ deleteVarSOS1()

 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
 scip SCIP data structure cons constraint consdata constraint data eventhdlr corresponding event handler pos position of variable in array

Definition at line 1077 of file cons_sos1.c.

Referenced by appendVarSOS1(), and presolRoundConsSOS1().

## ◆ extensionOperatorSOS1()

 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
 scip SCIP pointer conshdlrdata constraint handler data adjacencymatrix adjacencymatrix of the conflict graph (only lower half filled) vertexcliquegraph graph that contains the information which cliques contain a given vertex vertices of variables = 0, ..., nsos1vars-1; vertices of cliques = nsos1vars, ..., nsos1vars+ncliques-1 nsos1vars number of SOS1 variables nconss number of SOS1 constraints cons constraint to be extended vars variables of extended clique weights weights of extended clique firstcall whether this is the first call of extension operator usebacktrack whether backtracking is needed for the computation cliques all cliques found so far ncliques number of clique found so far cliquesizes number of variables of current clique newclique clique we want to extended workingset set of vertices that already served as extension and set of candidates that probably will lead to an extension nworkingset length of array workingset nexts number of vertices that already served as extension pos position of potential candidate maxextensions maximal number of extensions naddconss number of added constraints success pointer to store if at least one new clique was found

Definition at line 1116 of file cons_sos1.c.

Referenced by deleteVarSOS1(), and presolRoundConssSOS1().

## ◆ genConflictgraphLinearCons()

 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
 conshdlrdata constraint handler data conflictgraphlin conflict graph of linear constraint (nodes: 1, ..., nlinvars) conflictgraphorig original conflict graph (nodes: 1, ..., nsos1vars) linvars linear variables in linear constraint nlinvars number of linear variables in linear constraint posinlinvars posinlinvars[i] = position (index) of SOS1 variable i in linear constraint, posinlinvars[i]= -1 if i is not a SOS1 variable or not a variable of the linear constraint

Definition at line 1377 of file cons_sos1.c.

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
 conshdlrdata constraint handler data conflictgraph conflict graph clique current clique vars clique variables nvars number of clique variables comsucc pointer to store common successors of clique vertices (size = nvars) ncomsucc pointer to store number common successors of clique vertices

Definition at line 1430 of file cons_sos1.c.

Referenced by genConflictgraphLinearCons(), and presolRoundConssSOS1().

## ◆ getSOS1Implications()

 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
 scip SCIP pointer conshdlrdata constraint handler data vars problem and SOS1 variables implgraph implication graph (j is successor of i if and only if $$x_i\not = 0 \Rightarrow x_j\not = 0$$) implhash hash map from variable to node in implication graph implnodes implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero node node of the implication graph

Definition at line 1531 of file cons_sos1.c.

## ◆ presolRoundConsSOS1()

 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
 scip SCIP pointer cons constraint consdata constraint data eventhdlr event handler substituted whether a variable was substituted cutoff whether a cutoff happened success whether we performed a successful reduction ndelconss number of deleted constraints nupgdconss number of upgraded constraints nfixedvars number of fixed variables nremovedvars number of variables removed

Definition at line 1597 of file cons_sos1.c.

Referenced by getSOS1Implications(), and presolRoundConssSOS1().

## ◆ 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
 scip SCIP pointer eventhdlr event handler conshdlrdata constraint handler data conflictgraph conflict graph adjacencymatrix adjacency matrix of conflict graph (or NULL) conss SOS1 constraints nconss number of SOS1 constraints nsos1vars number of SOS1 variables naddconss number of added constraints ndelconss number of deleted constraints nupgdconss number of upgraded constraints nfixedvars number of fixed variables nremovedvars number of variables removed result result

Definition at line 1823 of file cons_sos1.c.

Referenced by presolRoundConsSOS1().

## ◆ performImplicationGraphAnalysis()

 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
 scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph totalvars problem and SOS1 variables implgraph implication graph (j is successor of i if and only if $$x_i\not = 0 \Rightarrow x_j\not = 0$$) implhash hash map from variable to node in implication graph adjacencymatrix adjacencymatrix of the conflict graph (only lower half filled) givennode node of the conflict graph nonznode node of the conflict graph that is implied to be nonzero if given node is nonzero impllbs current lower variable bounds if given node is nonzero (update possible) implubs current upper variable bounds if given node is nonzero (update possible) implnodes indicates which variables are currently implied to be nonzero if given node is nonzero (update possible) naddconss pointer to store number of added SOS1 constraints probingdepth pointer to store current probing depth infeasible pointer to store whether the subproblem gets infeasible if variable to 'nonznode' is nonzero

Definition at line 2095 of file cons_sos1.c.

## ◆ isImpliedZero()

 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
 conflictgraph conflict graph implnodes implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero node node of the conflict graph (or -1)

Definition at line 2253 of file cons_sos1.c.

## ◆ updateArcData()

 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
 scip SCIP pointer implgraph implication graph implhash hash map from variable to node in implication graph totalvars problem and SOS1 variables varv variable that is assumed to be nonzero varw implication variable lb old lower bound of $$x_w$$ ub old upper bound of $$x_w$$ newbound new bound of $$x_w$$ lower whether to consider lower bound implication (otherwise upper bound) nchgbds pointer to store number of changed bounds update pointer to store whether implication graph has been updated infeasible pointer to store whether an infeasibility has been detected

Definition at line 2282 of file cons_sos1.c.

Referenced by updateImplicationGraphSOS1().

## ◆ 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

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

Parameters
 scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph adjacencymatrix adjacency matrix of conflict graph (lower half) implgraph implication graph (j is successor of i if and only if $$x_i\not = 0 \Rightarrow x_j\not = 0$$) implhash hash map from variable to node in implication graph implnodes implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero totalvars problem and SOS1 variables cliquecovers clique covers of linear constraint cliquecoversizes size of clique covers varincover array with varincover[i] = cover of SOS1 index i vars variables to be checked coefs coefficients of variables in linear constraint nvars number of variables to be checked bounds bounds of variables var variable that is assumed to be nonzero bound bound of variable boundnonzero bound of variable if it is known to be nonzero if infinity values are not summarized ninftynonzero number of times infinity/-infinity has to be summarized to boundnonzero lower TRUE if lower bounds are consideres; FALSE for upper bounds nchgbds pointer to store number of changed bounds update pointer to store whether implication graph has been updated infeasible pointer to store whether an infeasibility has been detected

Definition at line 2408 of file cons_sos1.c.

Referenced by tightenVarsBoundsSOS1(), and updateArcData().

## ◆ computeVarsCoverSOS1()

 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
 scip SCIP pointer conflictgraphroot conflict graph of the root node (nodes: 1, ..., nsos1vars) conflictgraphlin conflict graph of linear constraint (nodes: 1, ..., nlinvars) linvars variables in linear constraint coveredvars states which variables of the linear constraint are currently covered by a clique clique array to store new clique in cover cliquesize pointer to store the size of clique v position of variable in linear constraint that should be covered considersolvals TRUE if largest auxiliary bigM values of variables should be prefered

Definition at line 2570 of file cons_sos1.c.

Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().

## ◆ tightenVarsBoundsSOS1()

 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
 scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph implgraph implication graph (j is successor of i if and only if $$x_i\not = 0$$ implies a new lower/upper bound for $$x_j$$) implhash hash map from variable to node in implication graph adjacencymatrix adjacencymatrix of conflict graph totalvars problem and SOS1 vars ntotalvars number of problem and SOS1 variables nsos1vars number of SOS1 variables nchgbds pointer to store number of changed bounds implupdate pointer to store whether the implication graph has been updated in this function call cutoff pointer to store if current nodes LP is infeasible

Definition at line 2681 of file cons_sos1.c.

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
 scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph adjacencymatrix adjacencymatrix of conflict graph nsos1vars number of SOS1 variables nfixedvars pointer to store number of fixed variables nchgbds pointer to store number of changed bounds naddconss pointer to store number of addded constraints result result

Definition at line 3362 of file cons_sos1.c.

Referenced by tightenVarsBoundsSOS1().

## ◆ propConsSOS1()

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

propagate variables of SOS1 constraint

Parameters
 scip SCIP pointer cons constraint consdata constraint data cutoff whether a cutoff happened ngen number of domain changes

Definition at line 3536 of file cons_sos1.c.

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

## ◆ propVariableNonzero()

 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
 scip SCIP pointer conflictgraph conflict graph implgraph implication graph cons some arbitrary SOS1 constraint node conflict graph node of variable that is known to be nonzero implprop whether implication graph propagation shall be applied cutoff whether a cutoff happened ngen number of domain changes

Definition at line 3634 of file cons_sos1.c.

Referenced by propConsSOS1().

## ◆ initImplGraphSOS1()

 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
 scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph nsos1vars number of SOS1 variables maxrounds maximal number of propagation rounds for generating implications nchgbds pointer to store number of bound changes cutoff pointer to store whether a cutoff occurred success whether initialization was successful

Definition at line 3777 of file cons_sos1.c.

Referenced by propVariableNonzero(), and sepaImplBoundCutsSOS1().

## ◆ freeImplGraphSOS1()

 static SCIP_RETCODE freeImplGraphSOS1 ( SCIP * scip, SCIP_CONSHDLRDATA * conshdlrdata )
static

deinitialize implication graph

Parameters
 scip SCIP pointer conshdlrdata constraint handler data

Definition at line 3948 of file cons_sos1.c.

Referenced by initImplGraphSOS1().

## ◆ getCoverVertices()

 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
 conflictgraph conflict graph verticesarefixed array that indicates which variables are currently fixed to zero vertex vertex (-1 if not needed) neightocover neighbors of given vertex to be covered (or NULL if all neighbors shall be covered) nneightocover number of entries of neightocover (or 0 if all neighbors shall be covered ) coververtices array to store the vertices whose neighbor set covers the neighbor set of the given vertex ncoververtices pointer to store size of coververtices

Definition at line 4007 of file cons_sos1.c.

## ◆ getBranchingVerticesSOS1()

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

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

Parameters
 scip SCIP pointer conflictgraph conflict graph sol solution to be enforced (NULL for LP solution) verticesarefixed vector that indicates which variables are currently fixed to zero bipbranch TRUE if bipartite branching method should be used branchvertex branching vertex fixingsnode1 vertices of variables that will be fixed to zero for the first node nfixingsnode1 pointer to store number of fixed variables for the first node fixingsnode2 vertices of variables that will be fixed to zero for the second node nfixingsnode2 pointer to store number of fixed variables for the second node

Definition at line 4114 of file cons_sos1.c.

## ◆ getBranchingPrioritiesSOS1()

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

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

Parameters
 scip SCIP pointer conshdlrdata constraint handler data conflictgraph conflict graph sol solution to be enforced (NULL for LP solution) nsos1vars number of SOS1 variables verticesarefixed vector that indicates which variables are currently fixed to zero bipbranch TRUE if bipartite branching method should be used fixingsnode1 vertices of variables that will be fixed to zero for the first node (size = nsos1vars) fixingsnode2 vertices of variables that will be fixed to zero for the second node (size = nsos1vars) branchpriors pointer to store branching priorities (size = nsos1vars) or NULL if not needed vertexbestprior pointer to store vertex with the best branching priority or NULL if not needed relsolfeas pointer to store if LP relaxation solution is feasible

Definition at line 4227 of file cons_sos1.c.

## ◆ performStrongbranchSOS1()

 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
 scip SCIP pointer conflictgraph conflict graph fixingsexec vertices of variables to be fixed to zero for this strong branching execution nfixingsexec number of vertices of variables to be fixed to zero for this strong branching execution fixingsop vertices of variables to be fixed to zero for the opposite strong branching execution nfixingsop number of vertices of variables to be fixed to zero for the opposite strong branching execution inititer maximal number of LP iterations to perform fixnonzero shall opposite variable (if positive in sign) fixed to the feasibility tolerance (only possible if nfixingsop = 1) domainfixings vertices that can be used to reduce the domain (should have size equal to number of variables) ndomainfixings pointer to store number of vertices that can be used to reduce the domain, could be filled by earlier calls infeasible pointer to store whether branch is infeasible objval pointer to store objective value of LP with fixed variables (SCIP_INVALID if reddomain = TRUE or lperror = TRUE) lperror pointer to store whether an unresolved LP error or a strange solution status occurred

Definition at line 4331 of file cons_sos1.c.

Referenced by getBranchingDecisionStrongbranchSOS1(), and getBranchingPrioritiesSOS1().

## ◆ getBranchingDecisionStrongbranchSOS1()

 static SCIP_RETCODE getBranchingDecisionStrongbranchSOS1 ( SCIP * scip, SCIP_CONSHDLRDATA * conshdlrdata, SCIP_DIGRAPH * conflictgraph, SCIP_SOL * sol, int nsos1vars, SCIP_Real lpobjval, SCIP_Bool bipbranch, int nstrongrounds, SCIP_Bool * verticesarefixed, int * fixingsnode1, int * fixingsnode2, int * vertexbestprior, SCIP_Real * bestobjval1, SCIP_Real * bestobjval2, SCIP_RESULT * result )
static

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

Parameters
 scip SCIP pointer conshdlrdata SOS1 constraint handler data conflictgraph conflict graph sol solution to be enforced (NULL for LP solution) nsos1vars number of SOS1 variables lpobjval current LP relaxation solution bipbranch TRUE if bipartite branching method should be used nstrongrounds number of strong branching rounds verticesarefixed vector that indicates which variables are currently fixed to zero fixingsnode1 pointer to store vertices of variables that will be fixed to zero for the first node (size = nsos1vars) fixingsnode2 pointer to store vertices of variables that will be fixed to zero for the second node (size = nsos1vars) vertexbestprior pointer to store vertex with the best strong branching priority bestobjval1 pointer to store LP objective for left child node of branching decision with best priority bestobjval2 pointer to store LP objective for right child node of branching decision with best priority result pointer to store result of strong branching

Definition at line 4473 of file cons_sos1.c.

Referenced by enforceConflictgraph(), and performStrongbranchSOS1().

## ◆ getBoundConsFromVertices()

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

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

Parameters
 scip SCIP pointer conflictgraph conflict graph sol solution to be enforced (NULL for LP solution) v1 first vertex that shall be contained in bound constraint v2 second vertex that shall be contained in bound constraint boundvar bound variable of v1 and v2 (or NULL if not existent) extend should v1 and v2 be greedily extended to a clique of larger size cons bound constraint feas feasibility value of bound constraint

Definition at line 4690 of file cons_sos1.c.

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

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

Note
In this function the conflict graph is updated to the conflict graph of the considered child branching node.
Parameters
 scip SCIP pointer node branching node conshdlrdata constraint handler data conflictgraph conflict graph of the current node localconflicts local conflicts (updates to local conflicts of child node) sol solution to be enforced (NULL for LP solution) nsos1vars number of SOS1 variables verticesarefixed vector that indicates which variables are currently fixed to zerox fixingsnode1 vertices of variables that will be fixed to zero for the branching node in the input of this function nfixingsnode1 number of entries of array nfixingsnode1 fixingsnode2 vertices of variables that will be fixed to zero for the other branching node nfixingsnode2 number of entries of array nfixingsnode2 naddedconss pointer to store the number of added SOS1 constraints onlyviolsos1 should only SOS1 constraints be added that are violated by the LP solution

Definition at line 4918 of file cons_sos1.c.

Referenced by enforceConflictgraph(), and getBoundConsFromVertices().

## ◆ resetConflictgraphSOS1()

 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
 conflictgraph conflict graph of root node localconflicts local conflicts that should be removed from conflict graph nsos1vars number of SOS1 variables

Definition at line 5282 of file cons_sos1.c.

## ◆ enforceConflictgraph()

 static SCIP_RETCODE enforceConflictgraph ( SCIP * scip, SCIP_CONSHDLRDATA * conshdlrdata, SCIP_CONSHDLR * conshdlr, int nconss, SCIP_CONS ** conss, SCIP_SOL * sol, 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
 scip SCIP pointer conshdlrdata constraint handler data conshdlr constraint handler nconss number of constraints conss SOS1 constraints sol solution to be enforced (NULL for LP solution) result result

Definition at line 5338 of file cons_sos1.c.

Referenced by enforceSOS1(), and resetConflictgraphSOS1().

## ◆ enforceConssSOS1()

 static SCIP_RETCODE enforceConssSOS1 ( SCIP * scip, SCIP_CONSHDLR * conshdlr, int nconss, SCIP_CONS ** conss, SCIP_SOL * sol, 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
 scip SCIP pointer conshdlr constraint handler nconss number of constraints conss indicator constraints sol solution to be enforced (NULL for LP solution) result result

Definition at line 5810 of file cons_sos1.c.

Referenced by enforceConflictgraph(), and enforceSOS1().

## ◆ enforceSOS1()

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

constraint enforcing method of constraint handler

Parameters
 scip SCIP pointer conshdlr constraint handler nconss number of constraints conss indicator constraints sol solution to be enforced (NULL for LP solution) result result

Definition at line 6054 of file cons_sos1.c.

Referenced by enforceConssSOS1().

## ◆ initTCliquegraph()

 static SCIP_RETCODE initTCliquegraph ( SCIP * scip, SCIP_CONSHDLR * conshdlr, SCIP_CONSHDLRDATA * conshdlrdata, SCIP_DIGRAPH * conflictgraph, int nsos1vars )
static

initialitze tclique graph and create clique data

Parameters
 scip SCIP pointer conshdlr constraint handler conshdlrdata constraint handler data conflictgraph conflict graph nsos1vars number of SOS1 variables

Definition at line 6117 of file cons_sos1.c.

Referenced by enforceSOS1().

## ◆ updateWeightsTCliquegraph()

 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
 scip SCIP pointer conshdlrdata constraint handler data tcliquedata tclique data conflictgraph conflict graph sol LP solution to be separated (or NULL) nsos1vars number of SOS1 variables

Definition at line 6186 of file cons_sos1.c.

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
 scip SCIP pointer tcliquedata clique data rowlb row for lower bounds (or NULL) rowub row for upper bounds (or NULL) success pointer to store if bound cut was added cutoff pointer to store if a cutoff occurred

Definition at line 6246 of file cons_sos1.c.

Referenced by updateWeightsTCliquegraph().

## ◆ generateBoundInequalityFromSOS1Nodes()

 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
 scip SCIP pointer conshdlr constraint handler conflictgraph conflict graph nodes conflict graph nodes for bound constraint nnodes number of conflict graph nodes for bound constraint rhs right hand side of bound constraint local in any case produce a local cut (even if local bounds of variables are valid globally) global in any case produce a global cut strengthen whether trying to strengthen bound constraint removable should the inequality be removed from the LP due to aging or cleanup? nameext part of name of bound constraints rowlb output: row for lower bounds (or NULL if not needed) rowub output: row for upper bounds (or NULL if not needed)

Definition at line 6320 of file cons_sos1.c.

## ◆ TCLIQUE_NEWSOL()

 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 6610 of file cons_sos1.c.

Referenced by generateBoundInequalityFromSOS1Nodes().

## ◆ sepaBoundInequalitiesFromGraph()

 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
 scip SCIP pointer conshdlr constraint handler conshdlrdata constraint handler data sol LP solution to be separated (or NULL) maxboundcuts maximal number of bound cuts separated per separation round (-1: no limit) ngen pointer to store number of cuts generated cutoff pointer whether a cutoff occurred

Definition at line 6745 of file cons_sos1.c.

Referenced by separateSOS1().

## ◆ generateBoundInequalityFromSOS1Cons()

 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
 scip SCIP pointer conshdlr constraint handler cons SOS1 constraint local in any case produce a local cut (even if local bounds of variables are valid globally) global in any case produce a global cut strengthen whether trying to strengthen bound constraint removable should the inequality be removed from the LP due to aging or cleanup? rowlb output: row for lower bounds (or NULL if not needed) rowub output: row for upper bounds (or NULL if not needed)

Definition at line 6819 of file cons_sos1.c.

Referenced by initsepaBoundInequalityFromSOS1Cons(), and sepaBoundInequalitiesFromGraph().

## ◆ initsepaBoundInequalityFromSOS1Cons()

 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
 scip SCIP pointer conshdlr constraint handler conshdlrdata constraint handler data conss SOS1 constraints nconss number of SOS1 constraints sol LP solution to be separated (or NULL) solvedinitlp TRUE if initial LP relaxation at a node is solved maxboundcuts maximal number of bound cuts separated per separation round (-1: no limit) ngen pointer to store number of cuts generated (or NULL) cutoff pointer to store whether a cutoff occurred

Definition at line 6882 of file cons_sos1.c.

Referenced by generateBoundInequalityFromSOS1Cons(), and separateSOS1().

## ◆ sepaImplBoundCutsSOS1()

 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
 scip SCIP pointer conshdlr constraint handler conshdlrdata constraint handler data sol LP solution to be separated (or NULL) maxcuts maximal number of implied bound cuts separated per separation round (-1: no limit) ngen pointer to store number of cuts generated cutoff pointer whether a cutoff occurred

Definition at line 6996 of file cons_sos1.c.

Referenced by initsepaBoundInequalityFromSOS1Cons(), and separateSOS1().

## ◆ 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
 scip SCIP pointer conshdlr constraint handler sol solution to be separated (or NULL) nconss number of constraints conss SOS1 constraints result result

Definition at line 7221 of file cons_sos1.c.

Referenced by sepaImplBoundCutsSOS1().

## ◆ getVectorOfWeights()

 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
 scip SCIP pointer sol primal solution or NULL for current LP solution conflictgraph conflict graph nsos1vars number of SOS1 variables indicatorzero vector that indicates which variables are currently fixed to zero weights pointer to store weights determining the order of the variables (length = nsos1vars)

Definition at line 7342 of file cons_sos1.c.

Referenced by maxWeightIndSetHeuristic(), and separateSOS1().

## ◆ markNeighborsMWISHeuristic()

 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
 scip SCIP pointer conshdlr SOS1 constraint handler conflictgraph conflict graph node node of the conflict graph mark indicator vector of processed nodes indset indicator vector of current independent cnt pointer to store number of marked nodes cutoff pointer to store whether operation is infeasible

Definition at line 7413 of file cons_sos1.c.

Referenced by getVectorOfWeights(), and maxWeightIndSetHeuristic().

## ◆ 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
 scip SCIP pointer sol primal solution or NULL for current LP solution conshdlr SOS1 constraint handler conflictgraph conflict graph nsos1vars number of SOS1 variables indicatorzero vector that indicates which variables are currently fixed to zero indset pointer to store indicator vector of an independent set

Definition at line 7554 of file cons_sos1.c.

Referenced by makeSOS1conflictgraphFeasible(), and markNeighborsMWISHeuristic().

## ◆ makeSOS1conflictgraphFeasible()

 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
 scip SCIP pointer conshdlr SOS1 constraint handler sol solution changed pointer to store whether the solution has been changed allroundable pointer to store whether all variables are roundable

Definition at line 7660 of file cons_sos1.c.

Referenced by maxWeightIndSetHeuristic(), and SCIPmakeSOS1sFeasible().

## ◆ makeSOS1constraintsFeasible()

 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
 scip SCIP pointer conshdlr SOS1 constraint handler sol solution changed pointer to store whether the solution has been changed allroundable pointer to store whether all variables are roundable

Definition at line 7790 of file cons_sos1.c.

Referenced by makeSOS1conflictgraphFeasible(), and SCIPmakeSOS1sFeasible().

## ◆ getDiveBdChgsSOS1conflictgraph()

 static SCIP_RETCODE getDiveBdChgsSOS1conflictgraph ( 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 conflict graph

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

Parameters
 scip SCIP pointer conshdlr SOS1 constraint handler diveset diving settings sol solution success pointer to store

Definition at line 7925 of file cons_sos1.c.

Referenced by makeSOS1constraintsFeasible().

## ◆ getDiveBdChgsSOS1constraints()

 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
 scip SCIP pointer conshdlr SOS1 constraint handler diveset diving settings sol solution success pointer to store

Definition at line 8066 of file cons_sos1.c.

Referenced by getDiveBdChgsSOS1conflictgraph().

## ◆ detectVarboundSOS1()

 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
 scip SCIP pointer conshdlrdata SOS1 constraint handler data var0 first variable var1 second variable val0 first coefficient val1 second coefficient

Definition at line 8247 of file cons_sos1.c.

Referenced by checkLinearConssVarboundSOS1(), and getDiveBdChgsSOS1constraints().

## ◆ passConComponentVarbound()

 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
 scip SCIP pointer conflictgraph conflict graph node current node of connected component boundvar bound variable of connected component checklb whether to check lower bound variable (else upper bound variable) processed states for each variable whether it has been processed concomp current connected component nconcomp pointer to store number of elements of connected component unique pointer to store whether bound variable is unique

Definition at line 8323 of file cons_sos1.c.

Referenced by checkConComponentsVarbound(), and detectVarboundSOS1().

## ◆ checkConComponentsVarbound()

 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
 scip SCIP pointer conflictgraph conflict graph nsos1vars number of SOS1 variables checklb whether to check lower bound variable (else check upper bound variable)

Definition at line 8396 of file cons_sos1.c.

Referenced by passConComponentVarbound().

## ◆ checkLinearConssVarboundSOS1()

 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
 scip SCIP pointer conshdlrdata SOS1 constraint handler data linconss linear constraints nlinconss number of linear constraints

Definition at line 8485 of file cons_sos1.c.

Referenced by checkConComponentsVarbound().

## ◆ checkSwitchNonoverlappingSOS1Methods()

 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
 scip SCIP pointer conshdlrdata SOS1 constraint handler data conflictgraph conflict graph conss SOS1 constraints nconss number of SOS1 constraints

Definition at line 8558 of file cons_sos1.c.

Referenced by checkLinearConssVarboundSOS1().

## ◆ computeNodeDataSOS1()

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

sets node data of conflict graph nodes

Parameters
 scip SCIP pointer conshdlrdata SOS1 constraint handler data nsos1vars number of SOS1 variables

Definition at line 8639 of file cons_sos1.c.

Referenced by checkSwitchNonoverlappingSOS1Methods().

## ◆ initConflictgraph()

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

initialize conflictgraph and create hashmap for SOS1 variables

Parameters
 scip SCIP pointer conshdlrdata constraint handler data conss SOS1 constraints nconss number of SOS1 constraints

Definition at line 8676 of file cons_sos1.c.

## ◆ freeConflictgraph()

 static SCIP_RETCODE freeConflictgraph ( SCIP * scip, SCIP_CONSHDLRDATA * conshdlrdata )
static

free conflict graph, nodedata and hashmap

Parameters
 scip SCIP pointer conshdlrdata constraint handler data

Definition at line 8871 of file cons_sos1.c.

Referenced by initConflictgraph().

## ◆ SCIP_DECL_CONSHDLRCOPY()

 static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySOS1 )
static

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

Definition at line 8917 of file cons_sos1.c.

Referenced by freeConflictgraph().

## ◆ SCIP_DECL_CONSFREE()

 static SCIP_DECL_CONSFREE ( consFreeSOS1 )
static

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

Definition at line 8934 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSINITSOL()

 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 8956 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSEXITSOL()

 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 9009 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSDELETE()

 static SCIP_DECL_CONSDELETE ( consDeleteSOS1 )
static

frees specific constraint data

Definition at line 9081 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSTRANS()

 static SCIP_DECL_CONSTRANS ( consTransSOS1 )
static

transforms constraint data into data belonging to the transformed problem

Definition at line 9135 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSPRESOL()

 static SCIP_DECL_CONSPRESOL ( consPresolSOS1 )
static

presolving method of constraint handler

Definition at line 9229 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSINITLP()

 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 9348 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSSEPALP()

 static SCIP_DECL_CONSSEPALP ( consSepalpSOS1 )
static

separation method of constraint handler for LP solutions

Definition at line 9373 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSSEPASOL()

 static SCIP_DECL_CONSSEPASOL ( consSepasolSOS1 )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 9389 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSENFOLP()

 static SCIP_DECL_CONSENFOLP ( consEnfolpSOS1 )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 9405 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSENFORELAX()

 static SCIP_DECL_CONSENFORELAX ( consEnforelaxSOS1 )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 9421 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSENFOPS()

 static SCIP_DECL_CONSENFOPS ( consEnfopsSOS1 )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 9437 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSCHECK()

 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 9456 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSPROP()

 static SCIP_DECL_CONSPROP ( consPropSOS1 )
static

domain propagation method of constraint handler

Definition at line 9528 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSRESPROP()

 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 9674 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSLOCK()

 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 9750 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSPRINT()

 static SCIP_DECL_CONSPRINT ( consPrintSOS1 )
static

constraint display method of constraint handler

Definition at line 9796 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSCOPY()

 static SCIP_DECL_CONSCOPY ( consCopySOS1 )
static

constraint copying method of constraint handler

Definition at line 9826 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSPARSE()

 static SCIP_DECL_CONSPARSE ( consParseSOS1 )
static

constraint parsing method of constraint handler

Definition at line 9890 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSGETVARS()

static

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

Definition at line 9954 of file cons_sos1.c.

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

## ◆ SCIP_DECL_CONSGETNVARS()

static

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

Definition at line 9977 of file cons_sos1.c.

Referenced by SCIP_DECL_CONSGETVARS().

## ◆ SCIP_DECL_EVENTEXEC()

 static SCIP_DECL_EVENTEXEC ( eventExecSOS1 )
static

exec the event handler

We update the number of variables fixed to be nonzero

Definition at line 9998 of file cons_sos1.c.

## ◆ SCIP_DECL_CONSGETDIVEBDCHGS()

 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 10120 of file cons_sos1.c.