Detailed Description

constraint handler for SOS type 1 constraints

Author: Tobias Fischer; Marc Pfetsch

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

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

The order of the variables is determined as follows:

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

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

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

Definition in file cons_sos1.c.

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

Go to the source code of this file.

Data Structures
struct	TCLIQUE_Data

Macros
#define	CONSHDLR_NAME "SOS1"

#define	CONSHDLR_DESC "SOS1 constraint handler"

#define	CONSHDLR_SEPAPRIORITY 1000

#define	CONSHDLR_ENFOPRIORITY 100

#define	CONSHDLR_CHECKPRIORITY -10

#define	CONSHDLR_SEPAFREQ 10

#define	CONSHDLR_PROPFREQ 1

#define	CONSHDLR_EAGERFREQ 100

#define	CONSHDLR_MAXPREROUNDS -1

#define	CONSHDLR_DELAYSEPA FALSE

#define	CONSHDLR_DELAYPROP FALSE

#define	CONSHDLR_NEEDSCONS TRUE

#define	CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

#define	CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM

#define	DEFAULT_MAXSOSADJACENCY 10000

#define	DEFAULT_MAXEXTENSIONS 1

#define	DEFAULT_MAXTIGHTENBDS 5

#define	DEFAULT_PERFIMPLANALYSIS 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_ADDCOMPS FALSE

#define	DEFAULT_MAXADDCOMPS -1

#define	DEFAULT_ADDCOMPSDEPTH 30

#define	DEFAULT_ADDCOMPSFEAS -0.6

#define	DEFAULT_ADDBDSFEAS 1.0

#define	DEFAULT_ADDEXTENDEDBDS TRUE

#define	DEFAULT_NSTRONGROUNDS 0

#define	DEFAULT_NSTRONGITER 10000

#define	DEFAULT_BOUNDCUTSFROMSOS1 FALSE

#define	DEFAULT_BOUNDCUTSFROMGRAPH TRUE

#define	DEFAULT_AUTOCUTSFROMSOS1 TRUE

#define	DEFAULT_BOUNDCUTSFREQ 10

#define	DEFAULT_BOUNDCUTSDEPTH 40

#define	DEFAULT_MAXBOUNDCUTS 50

#define	DEFAULT_MAXBOUNDCUTSROOT 150

#define	DEFAULT_STRTHENBOUNDCUTS TRUE

#define	DEFAULT_IMPLCUTSFREQ 0

#define	DEFAULT_IMPLCUTSDEPTH 40

#define	DEFAULT_MAXIMPLCUTS 50

#define	DEFAULT_MAXIMPLCUTSROOT 150

#define	EVENTHDLR_NAME "SOS1"

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

#define	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_CONSGETVARS (consGetVarsSOS1)

static	SCIP_DECL_CONSGETNVARS (consGetNVarsSOS1)

static	SCIP_DECL_EVENTEXEC (eventExecSOS1)

static	SCIP_DECL_CONSGETDIVEBDCHGS (consGetDiveBdChgsSOS1)

static	SCIP_DECL_CONSGETPERMSYMGRAPH (consGetPermsymGraphSOS1)

static	SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH (consGetSignedPermsymGraphSOS1)

SCIP_RETCODE	SCIPincludeConshdlrSOS1 (SCIP *scip)

SCIP_RETCODE	SCIPcreateConsSOS1 (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR *vars, SCIP_Real weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)

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

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

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

int	SCIPgetNVarsSOS1 (SCIP scip, SCIP_CONS cons)

SCIP_VAR **	SCIPgetVarsSOS1 (SCIP scip, SCIP_CONS cons)

SCIP_Real *	SCIPgetWeightsSOS1 (SCIP scip, SCIP_CONS cons)

SCIP_DIGRAPH *	SCIPgetConflictgraphSOS1 (SCIP_CONSHDLR *conshdlr)

int	SCIPgetNSOS1Vars (SCIP_CONSHDLR *conshdlr)

SCIP_Bool	SCIPvarIsSOS1 (SCIP_CONSHDLR conshdlr, SCIP_VAR var)

int	SCIPvarGetNodeSOS1 (SCIP_CONSHDLR conshdlr, SCIP_VAR var)

SCIP_VAR *	SCIPnodeGetVarSOS1 (SCIP_DIGRAPH *conflictgraph, int node)

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

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "SOS1"

Definition at line 120 of file cons_sos1.c.

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "SOS1 constraint handler"

Definition at line 121 of file cons_sos1.c.

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY 1000

priority of the constraint handler for separation

Definition at line 122 of file cons_sos1.c.

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY 100

priority of the constraint handler for constraint enforcing

Definition at line 123 of file cons_sos1.c.

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY -10

priority of the constraint handler for checking feasibility

Definition at line 124 of file cons_sos1.c.

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ 10

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

Definition at line 125 of file cons_sos1.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 126 of file cons_sos1.c.

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ 100

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

Definition at line 128 of file cons_sos1.c.

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS -1

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

Definition at line 129 of file cons_sos1.c.

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 130 of file cons_sos1.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 131 of file cons_sos1.c.

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 132 of file cons_sos1.c.

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 133 of file cons_sos1.c.

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM

Definition at line 134 of file cons_sos1.c.

◆ DEFAULT_MAXSOSADJACENCY

#define DEFAULT_MAXSOSADJACENCY 10000

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

Definition at line 138 of file cons_sos1.c.

◆ DEFAULT_MAXEXTENSIONS

#define DEFAULT_MAXEXTENSIONS 1

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

Definition at line 141 of file cons_sos1.c.

◆ DEFAULT_MAXTIGHTENBDS

#define DEFAULT_MAXTIGHTENBDS 5

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

Definition at line 142 of file cons_sos1.c.

◆ DEFAULT_PERFIMPLANALYSIS

#define DEFAULT_PERFIMPLANALYSIS FALSE

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

Definition at line 143 of file cons_sos1.c.

◆ DEFAULT_DEPTHIMPLANALYSIS

#define DEFAULT_DEPTHIMPLANALYSIS -1

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

Definition at line 144 of file cons_sos1.c.

◆ DEFAULT_CONFLICTPROP

#define DEFAULT_CONFLICTPROP TRUE

whether to use conflict graph propagation

Definition at line 147 of file cons_sos1.c.

◆ DEFAULT_IMPLPROP

#define DEFAULT_IMPLPROP TRUE

whether to use implication graph propagation

Definition at line 148 of file cons_sos1.c.

◆ DEFAULT_SOSCONSPROP

#define DEFAULT_SOSCONSPROP FALSE

whether to use SOS1 constraint propagation

Definition at line 149 of file cons_sos1.c.

◆ DEFAULT_BRANCHSTRATEGIES

#define DEFAULT_BRANCHSTRATEGIES "nbs"

possible branching strategies (see parameter DEFAULT_BRANCHINGRULE)

Definition at line 152 of file cons_sos1.c.

◆ DEFAULT_BRANCHINGRULE

#define DEFAULT_BRANCHINGRULE 'n'

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

Definition at line 154 of file cons_sos1.c.

◆ DEFAULT_AUTOSOS1BRANCH

#define DEFAULT_AUTOSOS1BRANCH TRUE

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

Definition at line 155 of file cons_sos1.c.

◆ DEFAULT_FIXNONZERO

#define DEFAULT_FIXNONZERO FALSE

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

Definition at line 157 of file cons_sos1.c.

◆ DEFAULT_ADDCOMPS

#define DEFAULT_ADDCOMPS FALSE

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

Definition at line 159 of file cons_sos1.c.

◆ DEFAULT_MAXADDCOMPS

#define DEFAULT_MAXADDCOMPS -1

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

Definition at line 160 of file cons_sos1.c.

◆ DEFAULT_ADDCOMPSDEPTH

#define DEFAULT_ADDCOMPSDEPTH 30

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

Definition at line 161 of file cons_sos1.c.

◆ DEFAULT_ADDCOMPSFEAS

#define DEFAULT_ADDCOMPSFEAS -0.6

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

Definition at line 162 of file cons_sos1.c.

◆ DEFAULT_ADDBDSFEAS

#define DEFAULT_ADDBDSFEAS 1.0

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

Definition at line 163 of file cons_sos1.c.

◆ DEFAULT_ADDEXTENDEDBDS

#define DEFAULT_ADDEXTENDEDBDS TRUE

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

Definition at line 164 of file cons_sos1.c.

◆ DEFAULT_NSTRONGROUNDS

#define DEFAULT_NSTRONGROUNDS 0

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

Definition at line 168 of file cons_sos1.c.

◆ DEFAULT_NSTRONGITER

#define DEFAULT_NSTRONGITER 10000

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

Definition at line 169 of file cons_sos1.c.

◆ DEFAULT_BOUNDCUTSFROMSOS1

#define DEFAULT_BOUNDCUTSFROMSOS1 FALSE

if TRUE separate bound inequalities from SOS1 constraints

Definition at line 172 of file cons_sos1.c.

◆ DEFAULT_BOUNDCUTSFROMGRAPH

#define DEFAULT_BOUNDCUTSFROMGRAPH TRUE

if TRUE separate bound inequalities from the conflict graph

Definition at line 173 of file cons_sos1.c.

◆ DEFAULT_AUTOCUTSFROMSOS1

#define DEFAULT_AUTOCUTSFROMSOS1 TRUE

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

Definition at line 174 of file cons_sos1.c.

◆ DEFAULT_BOUNDCUTSFREQ

#define DEFAULT_BOUNDCUTSFREQ 10

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

Definition at line 175 of file cons_sos1.c.

◆ DEFAULT_BOUNDCUTSDEPTH

#define DEFAULT_BOUNDCUTSDEPTH 40

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

Definition at line 176 of file cons_sos1.c.

◆ DEFAULT_MAXBOUNDCUTS

#define DEFAULT_MAXBOUNDCUTS 50

maximal number of bound cuts separated per branching node

Definition at line 177 of file cons_sos1.c.

◆ DEFAULT_MAXBOUNDCUTSROOT

#define DEFAULT_MAXBOUNDCUTSROOT 150

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

Definition at line 178 of file cons_sos1.c.

◆ DEFAULT_STRTHENBOUNDCUTS

#define DEFAULT_STRTHENBOUNDCUTS TRUE

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

Definition at line 179 of file cons_sos1.c.

◆ DEFAULT_IMPLCUTSFREQ

#define DEFAULT_IMPLCUTSFREQ 0

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

Definition at line 180 of file cons_sos1.c.

◆ DEFAULT_IMPLCUTSDEPTH

#define DEFAULT_IMPLCUTSDEPTH 40

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

Definition at line 181 of file cons_sos1.c.

◆ DEFAULT_MAXIMPLCUTS

#define DEFAULT_MAXIMPLCUTS 50

maximal number of implied bound cuts separated per branching node

Definition at line 182 of file cons_sos1.c.

◆ DEFAULT_MAXIMPLCUTSROOT

#define DEFAULT_MAXIMPLCUTSROOT 150

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

Definition at line 183 of file cons_sos1.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "SOS1"

Definition at line 186 of file cons_sos1.c.

◆ EVENTHDLR_DESC

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

Definition at line 187 of file cons_sos1.c.

◆ EVENTHDLR_EVENT_TYPE

#define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

Definition at line 189 of file cons_sos1.c.

◆ DIVINGCUTOFFVALUE

#define DIVINGCUTOFFVALUE 1e6

Definition at line 192 of file cons_sos1.c.

Typedef Documentation

◆ SCIP_NODEDATA

typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 222 of file cons_sos1.c.

◆ SCIP_SUCCDATA

typedef struct SCIP_SuccData SCIP_SUCCDATA

Definition at line 231 of file cons_sos1.c.

Function Documentation

◆ isConnectedSOS1()

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

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

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

◆ isViolatedSOS1()

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

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

Referenced by getDiveBdChgsSOS1conflictgraph().

◆ nodeGetSolvalBinaryBigMSOS1()

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

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

Referenced by computeVarsCoverSOS1(), and getBoundConsFromVertices().

◆ nodeGetSolvalVarboundLbSOS1()

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

References nodedata, NULL, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetLbLocal().

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

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

References nodedata, NULL, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPgetSolVal(), and SCIPvarGetUbLocal().

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

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

References FALSE, NULL, SCIPhashmapExists(), and TRUE.

Referenced by checkLinearConssVarboundSOS1(), and SCIPvarIsSOS1().

◆ varGetNodeSOS1()

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

static

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

Parameters

conshdlrdata	SOS1 constraint handler
var	variable

Definition at line 555 of file cons_sos1.c.

References NULL, SCIPhashmapExists(), and SCIPhashmapGetImageInt().

Referenced by checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), detectVarboundSOS1(), enforceConflictgraph(), genConflictgraphLinearCons(), generateBoundInequalityFromSOS1Cons(), getSOS1Implications(), handleNewVariableSOS1(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), SCIP_DECL_CONSPROP(), SCIPvarGetNodeSOS1(), tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().

◆ fixVariableZeroNode()

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

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddConsNode(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.

Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), enforceConssSOS1(), and getBranchingDecisionStrongbranchSOS1().

◆ fixVariableZero()

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

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

Referenced by presolRoundConsSOS1().

◆ inferVariableZero()

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

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

Referenced by propConsSOS1(), and propVariableNonzero().

◆ lockVariableSOS1()

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

static

add lock on variable

Parameters

scip	SCIP data structure
cons	constraint
var	variable

Definition at line 748 of file cons_sos1.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by handleNewVariableSOS1(), and presolRoundConsSOS1().

◆ unlockVariableSOS1()

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by deleteVarSOS1(), and presolRoundConsSOS1().

◆ consdataEnsurevarsSizeSOS1()

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

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

Referenced by addVarSOS1(), and appendVarSOS1().

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

References EVENTHDLR_EVENT_TYPE, lockVariableSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarToRow(), SCIPcatchVarEvent(), SCIPdebugMsg, SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisZero(), SCIPmarkDoNotMultaggrVar(), SCIPsortInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varGetNodeSOS1().

Referenced by addVarSOS1(), appendVarSOS1(), and SCIPcreateConsSOS1().

◆ addVarSOS1()

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

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

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

◆ appendVarSOS1()

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

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

Referenced by SCIPappendVarSOS1().

◆ deleteVarSOS1()

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

References EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdropVarEvent(), and unlockVariableSOS1().

Referenced by 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 1118 of file cons_sos1.c.

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

Referenced by extensionOperatorSOS1(), and presolRoundConssSOS1().

◆ genConflictgraphLinearCons()

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

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

Referenced by tightenVarsBoundsSOS1().

◆ cliqueGetCommonSuccessorsSOS1()

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

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

Referenced by 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 1533 of file cons_sos1.c.

References getSOS1Implications(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPhashmapGetImageInt(), SCIPisFeasNegative(), SCIPisFeasPositive(), TRUE, and varGetNodeSOS1().

Referenced by getSOS1Implications(), and tightenVarsBoundsSOS1().

◆ presolRoundConsSOS1()

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

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

Referenced by 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 1824 of file cons_sos1.c.

References cliqueGetCommonSuccessorsSOS1(), extensionOperatorSOS1(), FALSE, MAX, NULL, presolRoundConsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcomputeArraysIntersectionInt(), SCIPconsGetData(), SCIPconsIsModifiable(), SCIPcreateDigraph(), SCIPdelCons(), SCIPdigraphAddArcSafe(), SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArrayNull, SCIPsortDownIntInt(), SCIPsortInt(), TRUE, and varGetNodeSOS1().

Referenced by SCIP_DECL_CONSPRESOL().

◆ performImplicationGraphAnalysis()

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

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

Referenced by performImplicationGraphAnalysis(), and presolRoundVarsSOS1().

◆ isImpliedZero()

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

References FALSE, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and TRUE.

Referenced by tightenVarsBoundsSOS1(), and updateImplicationGraphSOS1().

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

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPceil(), SCIPdebugMsg, SCIPdigraphAddArc(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfloor(), SCIPhashmapGetImageInt(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), SCIPvarIsIntegral(), and TRUE.

Referenced by updateImplicationGraphSOS1().

◆ updateImplicationGraphSOS1()

static SCIP_RETCODE updateImplicationGraphSOS1	(	SCIP *	scip,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_DIGRAPH *	conflictgraph,
		SCIP_Bool **	adjacencymatrix,
		SCIP_DIGRAPH *	implgraph,
		SCIP_HASHMAP *	implhash,
		SCIP_Bool *	implnodes,
		SCIP_VAR **	totalvars,
		int **	cliquecovers,
		int *	cliquecoversizes,
		int *	varincover,
		SCIP_VAR **	vars,
		SCIP_Real *	coefs,
		int	nvars,
		SCIP_Real *	bounds,
		SCIP_VAR *	var,
		SCIP_Real	bound,
		SCIP_Real	boundnonzero,
		int	ninftynonzero,
		SCIP_Bool	lower,
		int *	nchgbds,
		SCIP_Bool *	update,
		SCIP_Bool *	infeasible
	)

static

updates implication graph

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

Parameters

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

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

Referenced by tightenVarsBoundsSOS1().

◆ computeVarsCoverSOS1()

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

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

Referenced by tightenVarsBoundsSOS1().

◆ tightenVarsBoundsSOS1()

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

References computeVarsCoverSOS1(), FALSE, genConflictgraphLinearCons(), getSOS1Implications(), isConnectedSOS1(), isImpliedZero(), MAX, MIN, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPallocBufferArray, SCIPceil(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfloor(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetProbvarLinearSum(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPhashmapGetImageInt(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisZero(), SCIPnodeGetVarSOS1(), SCIPreallocBufferArray, SCIPsortDownRealInt(), SCIPsortRealInt(), SCIPswapReals(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, updateImplicationGraphSOS1(), varGetNodeSOS1(), and w.

Referenced by initImplGraphSOS1(), and presolRoundVarsSOS1().

◆ presolRoundVarsSOS1()

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

References FALSE, performImplicationGraphAnalysis(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPblkmem(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphFree(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfixVar(), SCIPfreeBlockMemory, SCIPfreeBufferArrayNull, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPnodeGetVarSOS1(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenVarsBoundsSOS1(), and TRUE.

Referenced by SCIP_DECL_CONSPRESOL().

◆ propConsSOS1()

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

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

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

◆ propVariableNonzero()

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

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

Referenced by SCIP_DECL_CONSPROP().

◆ initImplGraphSOS1()

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

References FALSE, nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPblkmem(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPnodeGetVarSOS1(), tightenVarsBoundsSOS1(), and TRUE.

Referenced by SCIP_DECL_CONSPROP(), and sepaImplBoundCutsSOS1().

◆ freeImplGraphSOS1()

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

static

deinitialize implication graph

Parameters

scip	SCIP pointer
conshdlrdata	constraint handler data

Definition at line 3949 of file cons_sos1.c.

References nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPdigraphSetNodeData(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_CONSEXITSOL().

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

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

Referenced by addBranchingComplementaritiesSOS1(), and getBranchingVerticesSOS1().

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

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

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

◆ getBranchingPrioritiesSOS1()

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

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

Referenced by enforceConflictgraph(), and getBranchingDecisionStrongbranchSOS1().

◆ performStrongbranchSOS1()

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

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

Referenced by getBranchingDecisionStrongbranchSOS1().

◆ getBranchingDecisionStrongbranchSOS1()

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

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

Referenced by enforceConflictgraph().

◆ getBoundConsFromVertices()

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

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

Referenced by addBranchingComplementaritiesSOS1().

◆ addBranchingComplementaritiesSOS1()

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

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

Referenced by enforceConflictgraph().

◆ resetConflictgraphSOS1()

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

References SCIP_CALL, SCIP_OKAY, SCIPcomputeArraysSetminusInt(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPdigraphSetNSuccessors().

Referenced by enforceConflictgraph().

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

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

Referenced by enforceSOS1().

◆ enforceConssSOS1()

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

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

Referenced by enforceSOS1().

◆ enforceSOS1()

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

References enforceConflictgraph(), enforceConssSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIPconshdlrGetData(), and SCIPerrorMessage.

Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().

◆ initTCliquegraph()

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

References TCLIQUE_Data::conflictgraph, TCLIQUE_Data::conshdlr, TCLIQUE_Data::maxboundcuts, TCLIQUE_Data::nboundcuts, TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, TCLIQUE_Data::scip, SCIP_CALL, SCIP_NOMEMORY, SCIP_OKAY, SCIPallocBlockMemory, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPnodeGetVarSOS1(), SCIPvarIsActive(), TCLIQUE_Data::sol, TCLIQUE_Data::strthenboundcuts, tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), and tcliqueFlush().

Referenced by SCIP_DECL_CONSINITSOL().

◆ updateWeightsTCliquegraph()

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

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

Referenced by sepaBoundInequalitiesFromGraph().

◆ addBoundCutSepa()

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

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

Referenced by TCLIQUE_NEWSOL().

◆ generateBoundInequalityFromSOS1Nodes()

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

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

Referenced by generateBoundInequalityFromSOS1Cons(), and TCLIQUE_NEWSOL().

◆ TCLIQUE_NEWSOL()

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

References addBoundCutSepa(), bound, FALSE, generateBoundInequalityFromSOS1Nodes(), MAX, nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), NULL, REALABS, SCIP_Bool, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPdebugMsg, SCIPerrorMessage, SCIPgetSolVal(), SCIPisEfficacious(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPnodeGetVarSOS1(), SCIPreleaseRow(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

◆ sepaBoundInequalitiesFromGraph()

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

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

Referenced by separateSOS1().

◆ generateBoundInequalityFromSOS1Cons()

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

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

Referenced by initsepaBoundInequalityFromSOS1Cons().

◆ initsepaBoundInequalityFromSOS1Cons()

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

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

Referenced by SCIP_DECL_CONSINITLP(), and separateSOS1().

◆ sepaImplBoundCutsSOS1()

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

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

Referenced by separateSOS1().

◆ separateSOS1()

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

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

Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ getVectorOfWeights()

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

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

Referenced by maxWeightIndSetHeuristic().

◆ markNeighborsMWISHeuristic()

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

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

Referenced by markNeighborsMWISHeuristic(), and maxWeightIndSetHeuristic().

◆ maxWeightIndSetHeuristic()

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

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

Referenced by makeSOS1conflictgraphFeasible().

◆ makeSOS1conflictgraphFeasible()

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

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

Referenced by SCIPmakeSOS1sFeasible().

◆ makeSOS1constraintsFeasible()

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

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

Referenced by SCIPmakeSOS1sFeasible().

◆ getDiveBdChgsSOS1conflictgraph()

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

References bound, DIVINGCUTOFFVALUE, FALSE, isViolatedSOS1(), MIN, nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), NULL, REALABS, SCIP_Bool, SCIP_BRANCHDIR_FIXED, SCIP_CALL, SCIP_DIVETYPE_SOS1VARIABLE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdivesetSupportsType(), SCIPgetConflictgraphSOS1(), SCIPgetDivesetScore(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisPositive(), SCIPnodeGetVarSOS1(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIP_DECL_CONSGETDIVEBDCHGS().

◆ getDiveBdChgsSOS1constraints()

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

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

Referenced by SCIP_DECL_CONSGETDIVEBDCHGS().

◆ detectVarboundSOS1()

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

References nodedata, NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPdigraphGetNodeData(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPvarGetName(), and varGetNodeSOS1().

Referenced by checkLinearConssVarboundSOS1().

◆ passConComponentVarbound()

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

References FALSE, nodedata, NULL, passConComponentVarbound(), SCIP_CALL, SCIP_OKAY, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPvarCompare(), and TRUE.

Referenced by checkConComponentsVarbound(), and passConComponentVarbound().

◆ checkConComponentsVarbound()

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

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

Referenced by computeNodeDataSOS1().

◆ checkLinearConssVarboundSOS1()

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

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

Referenced by computeNodeDataSOS1().

◆ checkSwitchNonoverlappingSOS1Methods()

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

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

Referenced by SCIP_DECL_CONSINITSOL().

◆ computeNodeDataSOS1()

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

References checkConComponentsVarbound(), checkLinearConssVarboundSOS1(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), and TRUE.

Referenced by SCIP_DECL_CONSINITSOL().

◆ initConflictgraph()

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

References FALSE, nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPblkmem(), SCIPconsGetData(), SCIPcreateDigraph(), SCIPdigraphAddArcSafe(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPfreeBufferArray, SCIPgetNTotalVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPisFeasZero(), SCIPsortInt(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIP_DECL_CONSINITSOL(), and SCIP_DECL_CONSPRESOL().

◆ freeConflictgraph()

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

References nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), SCIPdigraphSetNodeData(), SCIPfreeBlockMemory, and SCIPhashmapFree().

Referenced by SCIP_DECL_CONSEXITSOL(), and SCIP_DECL_CONSPRESOL().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySOS1 )

static

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

Definition at line 8920 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrSOS1(), and TRUE.

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

References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.

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

References checkSwitchNonoverlappingSOS1Methods(), computeNodeDataSOS1(), CONSHDLR_NAME, initConflictgraph(), initTCliquegraph(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPcreateDigraph().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolSOS1 )

static

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

Definition at line 9012 of file cons_sos1.c.

References CONSHDLR_NAME, freeConflictgraph(), freeImplGraphSOS1(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPdigraphFree(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPreleaseRow(), and tcliqueFree().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteSOS1 )

static

frees specific constraint data

Definition at line 9084 of file cons_sos1.c.

References CONSHDLR_NAME, EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPdropVarEvent(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseRow().

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransSOS1 )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 9138 of file cons_sos1.c.

References CONSHDLR_NAME, EVENTHDLR_EVENT_TYPE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcatchVarEvent(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetNTotalVars(), SCIPgetTransformedVar(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPsnprintf(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolSOS1 )

static

presolving method of constraint handler

Definition at line 9232 of file cons_sos1.c.

References CONSHDLR_NAME, freeConflictgraph(), initConflictgraph(), NULL, presolRoundConssSOS1(), presolRoundVarsSOS1(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebug, SCIPdebugMsg, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and SCIPfreeBufferArrayNull.

◆ SCIP_DECL_CONSINITLP()

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

References CONSHDLR_NAME, FALSE, initsepaBoundInequalityFromSOS1Cons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpSOS1 )

static

separation method of constraint handler for LP solutions

Definition at line 9376 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), and separateSOS1().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSOS1 )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 9392 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), and separateSOS1().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpSOS1 )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 9408 of file cons_sos1.c.

References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxSOS1 )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 9424 of file cons_sos1.c.

References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsSOS1 )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 9440 of file cons_sos1.c.

References CONSHDLR_NAME, enforceSOS1(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().

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

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasZero(), SCIPprintCons(), SCIPresetConsAge(), SCIPupdateSolConsViolation(), and SCIPvarGetName().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropSOS1 )

static

domain propagation method of constraint handler

Definition at line 9531 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, initImplGraphSOS1(), NULL, propConsSOS1(), propVariableNonzero(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetDepth(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisTransformed(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and varGetNodeSOS1().

◆ SCIP_DECL_CONSRESPROP()

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

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisFeasNegative(), SCIPisFeasPositive(), and SCIPnodeGetVarSOS1().

◆ SCIP_DECL_CONSLOCK()

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

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintSOS1 )

static

constraint display method of constraint handler

Definition at line 9799 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), and SCIPwriteVarName().

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopySOS1 )

static

constraint copying method of constraint handler

Definition at line 9829 of file cons_sos1.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsSOS1(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetVarCopy(), separate(), and TRUE.

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseSOS1 )

static

constraint parsing method of constraint handler

Definition at line 9893 of file cons_sos1.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarSOS1(), SCIPconshdlrGetName(), SCIPcreateConsSOS1(), SCIPerrorMessage, SCIPparseVarName(), SCIPreleaseCons(), SCIPskipSpace(), separate(), and TRUE.

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsSOS1 )

static

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

Definition at line 9983 of file cons_sos1.c.

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

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSOS1 )

static

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

Definition at line 10006 of file cons_sos1.c.

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

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

References EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_EVENTTYPE_LBRELAXED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBRELAXED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPerrorMessage, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPgetNTotalVars(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPlockVarCons(), SCIPunlockVarCons(), SCIPvarGetName(), and TRUE.

◆ SCIP_DECL_CONSGETDIVEBDCHGS()

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

References CONSHDLR_NAME, FALSE, getDiveBdChgsSOS1conflictgraph(), getDiveBdChgsSOS1constraints(), NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPerrorMessage.

◆ SCIP_DECL_CONSGETPERMSYMGRAPH()

static SCIP_DECL_CONSGETPERMSYMGRAPH ( consGetPermsymGraphSOS1 )

static

constraint handler method which returns the permutation symmetry detection graph of a constraint

Definition at line 10189 of file cons_sos1.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphVarAggregation(), SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSymActiveVariables(), SCIPgetSymgraphVarnodeidx(), SCIPgetVarsSOS1(), SCIPisEQ(), SCIPisTransformed(), SCIPisZero(), SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_PERM, and TRUE.

◆ SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH()

static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH ( consGetSignedPermsymGraphSOS1 )

static

constraint handler method which returns the signed permutation symmetry detection graph of a constraint

Definition at line 10255 of file cons_sos1.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSymActiveVariables(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphVarnodeidx(), SCIPgetVarsSOS1(), SCIPisEQ(), SCIPisInfinity(), SCIPisTransformed(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_PERM, and TRUE.

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PROP_TIMING

◆ CONSHDLR_PRESOLTIMING

◆ DEFAULT_MAXSOSADJACENCY

◆ DEFAULT_MAXEXTENSIONS

◆ DEFAULT_MAXTIGHTENBDS

◆ DEFAULT_PERFIMPLANALYSIS

◆ DEFAULT_DEPTHIMPLANALYSIS

◆ DEFAULT_CONFLICTPROP

◆ DEFAULT_IMPLPROP

◆ DEFAULT_SOSCONSPROP

◆ DEFAULT_BRANCHSTRATEGIES

◆ DEFAULT_BRANCHINGRULE

◆ DEFAULT_AUTOSOS1BRANCH

◆ DEFAULT_FIXNONZERO

◆ DEFAULT_ADDCOMPS

◆ DEFAULT_MAXADDCOMPS

◆ DEFAULT_ADDCOMPSDEPTH

◆ DEFAULT_ADDCOMPSFEAS

◆ DEFAULT_ADDBDSFEAS

◆ DEFAULT_ADDEXTENDEDBDS

◆ DEFAULT_NSTRONGROUNDS

◆ DEFAULT_NSTRONGITER

◆ DEFAULT_BOUNDCUTSFROMSOS1

◆ DEFAULT_BOUNDCUTSFROMGRAPH

◆ DEFAULT_AUTOCUTSFROMSOS1

◆ DEFAULT_BOUNDCUTSFREQ

◆ DEFAULT_BOUNDCUTSDEPTH

◆ DEFAULT_MAXBOUNDCUTS

◆ DEFAULT_MAXBOUNDCUTSROOT

◆ DEFAULT_STRTHENBOUNDCUTS

◆ DEFAULT_IMPLCUTSFREQ

◆ DEFAULT_IMPLCUTSDEPTH

◆ DEFAULT_MAXIMPLCUTS

◆ DEFAULT_MAXIMPLCUTSROOT

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ EVENTHDLR_EVENT_TYPE

◆ DIVINGCUTOFFVALUE

Typedef Documentation

◆ SCIP_NODEDATA

◆ SCIP_SUCCDATA

Function Documentation

◆ isConnectedSOS1()

◆ isViolatedSOS1()

◆ nodeGetSolvalBinaryBigMSOS1()

◆ nodeGetSolvalVarboundLbSOS1()

◆ nodeGetSolvalVarboundUbSOS1()

◆ varIsSOS1()

◆ varGetNodeSOS1()

◆ fixVariableZeroNode()

◆ fixVariableZero()

◆ inferVariableZero()

◆ lockVariableSOS1()

◆ unlockVariableSOS1()

◆ consdataEnsurevarsSizeSOS1()

◆ handleNewVariableSOS1()

◆ addVarSOS1()

◆ appendVarSOS1()

◆ deleteVarSOS1()

◆ extensionOperatorSOS1()

◆ genConflictgraphLinearCons()