|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cons_sos1.c
Go to the documentation of this file.
22 * variable is nonzero. The special case of two variables arises, for instance, from equilibrium or
38 * - If an empty constraint is created and then variables are added with SCIPaddVarSOS1(), weights
41 * - All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are
64 * @todo Possibly allow to generate local cuts via strengthened local cuts (would need to modified coefficients of rows).
66 * @todo Check whether we can avoid turning off multi-aggregation (it is sometimes possible to fix a multi-aggregated
70 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
89 #define CONSHDLR_ENFOPRIORITY 100 /**< priority of the constraint handler for constraint enforcing */
90 #define CONSHDLR_CHECKPRIORITY -10 /**< priority of the constraint handler for checking feasibility */
91 #define CONSHDLR_SEPAFREQ 10 /**< frequency for separating cuts; zero means to separate only in the root node */
92 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
93 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
95 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
96 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
97 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
98 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
103 #define DEFAULT_MAXSOSADJACENCY 10000 /**< do not create an adjacency matrix if number of SOS1 variables is larger than predefined value
107 #define DEFAULT_MAXEXTENSIONS 1 /**< maximal number of extensions that will be computed for each SOS1 constraint */
108 #define DEFAULT_MAXTIGHTENBDS 5 /**< maximal number of bound tightening rounds per presolving round (-1: no limit) */
109 #define DEFAULT_UPDATECONFLPRESOL FALSE /**< if TRUE then update conflict graph during presolving procedure */
117 #define DEFAULT_NEIGHBRANCH TRUE /**< if TRUE turn neighborhood branching method on (note: an automatic switching to SOS1 branching is possible) */
118 #define DEFAULT_BIPBRANCH FALSE /**< if TRUE turn bipartite branching method on (note: an automatic switching to SOS1 branching is possible) */
120 #define DEFAULT_AUTOSOS1BRANCH TRUE /**< if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap */
121 #define DEFAULT_FIXNONZERO FALSE /**< if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the
123 #define DEFAULT_ADDCOMPS FALSE /**< if TRUE then add complementarity constraints to the branching nodes (can be used in combination with
125 #define DEFAULT_MAXADDCOMPS -1 /**< maximal number of complementarity constraints added per branching node (-1: no limit) */
126 #define DEFAULT_ADDCOMPSDEPTH 30 /**< only add complementarity constraints to branching nodes for predefined depth (-1: no limit) */
127 #define DEFAULT_ADDCOMPSFEAS -0.6 /**< minimal feasibility value for complementarity constraints in order to be added to the branching node */
128 #define DEFAULT_ADDBDSFEAS 1.0 /**< minimal feasibility value for bound inequalities in order to be added to the branching node */
129 #define DEFAULT_ADDEXTENDEDBDS TRUE /**< should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities */
132 #define DEFAULT_NSTRONGROUNDS 0 /**< maximal number of strong branching rounds to perform for each node (-1: auto)
134 #define DEFAULT_NSTRONGITER 10000 /**< maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) */
137 #define DEFAULT_BOUNDCUTSFROMSOS1 FALSE /**< if TRUE separate bound inequalities from SOS1 constraints */
138 #define DEFAULT_BOUNDCUTSFROMGRAPH TRUE /**< if TRUE separate bound inequalities from the conflict graph */
139 #define DEFAULT_AUTOCUTSFROMSOS1 TRUE /**< if TRUE then automatically switch to separating from SOS1 constraints if the SOS1 constraints do not overlap */
140 #define DEFAULT_BOUNDCUTSFREQ 10 /**< frequency for separating bound cuts; zero means to separate only in the root node */
142 #define DEFAULT_MAXBOUNDCUTS 50 /**< maximal number of bound cuts separated per branching node */
143 #define DEFAULT_MAXBOUNDCUTSROOT 150 /**< maximal number of bound cuts separated per iteration in the root node */
144 #define DEFAULT_STRTHENBOUNDCUTS TRUE /**< if TRUE then bound cuts are strengthened in case bound variables are available */
145 #define DEFAULT_IMPLCUTSFREQ 0 /**< frequency for separating implied bound cuts; zero means to separate only in the root node */
146 #define DEFAULT_IMPLCUTSDEPTH 40 /**< node depth of separating implied bound cuts (-1: no limit) */
147 #define DEFAULT_MAXIMPLCUTS 50 /**< maximal number of implied bound cuts separated per branching node */
148 #define DEFAULT_MAXIMPLCUTSROOT 150 /**< maximal number of implied bound cuts separated per iteration in the root node */
160 {
176 SCIP_VAR* lbboundvar; /**< bound variable @p z from constraint \f$x \geq \mu \cdot z\f$ (or NULL if not existent) */
177 SCIP_VAR* ubboundvar; /**< bound variable @p z from constraint \f$x \leq \mu \cdot z\f$ (or NULL if not existent) */
178 SCIP_Real lbboundcoef; /**< value \f$\mu\f$ from constraint \f$x \geq \mu z \f$ (0.0 if not existent) */
179 SCIP_Real ubboundcoef; /**< value \f$\mu\f$ from constraint \f$x \leq \mu z \f$ (0.0 if not existent) */
180 SCIP_Bool lbboundcomp; /**< TRUE if the nodes from the connected component of the conflict graph the given node belongs to
182 SCIP_Bool ubboundcomp; /**< TRUE if the nodes from the connected component of the conflict graph the given node belongs to
190 {
199 {
208 int maxboundcuts; /**< maximal number of clique cuts separated per separation round (-1: no limit) */
209 SCIP_Bool strthenboundcuts; /**< if TRUE then bound cuts are strengthened in case bound variables are available */
210 };
219 SCIP_Bool isconflocal; /**< if TRUE then local conflicts are present and conflict graph has to be updated for each node */
223 int maxsosadjacency; /**< do not create an adjacency matrix in if number of SOS1 variables is larger than predefined
226 SCIP_DIGRAPH* implgraph; /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
238 int maxextensions; /**< maximal number of extensions that will be computed for each SOS1 constraint */
239 int maxtightenbds; /**< maximal number of bound tightening rounds per presolving round (-1: no limit) */
240 SCIP_Bool updateconflpresol; /**< if TRUE then update conflict graph during presolving procedure */
246 SCIP_Bool neighbranch; /**< if TRUE turn neighborhood branching method on (note: an automatic switching to SOS1 branching is possible) */
247 SCIP_Bool bipbranch; /**< if TRUE turn bipartite branching method on (note: an automatic switching to SOS1 branching is possible) */
249 SCIP_Bool autosos1branch; /**< if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap */
250 SCIP_Bool fixnonzero; /**< if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the
252 SCIP_Bool addcomps; /**< if TRUE then add complementarity constraints to the branching nodes additionally to domain fixings
254 int maxaddcomps; /**< maximal number of complementarity cons. and cor. bound ineq. added per branching node (-1: no limit) */
255 int addcompsdepth; /**< only add complementarity constraints to branching nodes for predefined depth (-1: no limit) */
256 SCIP_Real addcompsfeas; /**< minimal feasibility value for complementarity constraints in order to be added to the branching node */
257 SCIP_Real addbdsfeas; /**< minimal feasibility value for bound inequalities in order to be added to the branching node */
258 SCIP_Bool addextendedbds; /**< should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities */
261 SCIP_Bool branchweight; /**< Branch on SOS cons. with highest nonzero-variable weight for branching - needs branchnonzeros to be false */
264 int nstrongrounds; /**< maximal number of strong branching rounds to perform for each node (-1: auto)
266 int nstrongiter; /**< maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) */
269 SCIP_Bool boundcutsfromgraph; /**< if TRUE separate bound inequalities from the conflict graph */
270 SCIP_Bool autocutsfromsos1; /**< if TRUE then automatically switch to separating SOS1 constraints if the SOS1 constraints do not overlap */
271 SCIP_Bool switchcutsfromsos1; /**< whether to switch to separate bound inequalities from SOS1 constraints */
272 int boundcutsfreq; /**< frequency for separating bound cuts; zero means to separate only in the root node */
275 int maxboundcutsroot; /**< maximal number of bound cuts separated per iteration in the root node */
277 SCIP_Bool strthenboundcuts; /**< if TRUE then bound cuts are strengthened in case bound variables are available */
278 int implcutsfreq; /**< frequency for separating implied bound cuts; zero means to separate only in the root node */
281 int maximplcutsroot; /**< maximal number of implied bound cuts separated per iteration in the root node */
293 SCIP_Bool** adjacencymatrix, /**< adjacency matrix of conflict graph (lower half) (or NULL if an adjacencymatrix is not at hand) */
297 )
350 /** checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable */
357 )
370 /* check whether variable is nonzero w.r.t. sol and the bounds have not been fixed to zero by propagation */
371 if ( ! SCIPisFeasZero(scip, solval) && ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) )
386 if ( ! SCIPisFeasZero(scip, solval) && ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) )
395 /** returns solution value of imaginary binary big-M variable of a given node from the conflict graph */
402 )
445 /** gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph */
452 )
472 /** gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph */
479 )
544 )
548 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
562 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
564 SCIPdebugMessage("creating constraint to force multi-aggregated variable <%s> to 0.\n", SCIPvarGetName(var));
566 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "branch", 1, &var, &val, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
586 * Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
590 * we can express the fixing \f$x = 0\f$ by fixing all \f$x_i\f$ to 0 if \f$c = 0\f$ and the lower bounds of \f$x_i\f$
591 * are nonnegative if \f$\alpha_i > 0\f$ or the upper bounds are nonpositive if \f$\alpha_i < 0\f$.
599 )
631 if ( (SCIPisPositive(scip, aggrvals[i]) && SCIPisNegative(scip, SCIPvarGetLbLocal(aggrvars[i]))) ||
675 SCIP_Bool* success /**< whether fixing was successful, i.e., variable is not multi-aggregated */
683 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
716 {
722 SCIP_CALL( SCIPlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)), SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var))) );
735 {
741 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)), SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var))) );
754 )
806 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
817 if ( consdata->rowub != NULL && ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) && ! SCIPisZero(scip, SCIPvarGetUbGlobal(var)) )
823 if ( consdata->rowlb != NULL && ! SCIPisInfinity(scip, SCIPvarGetLbGlobal(var)) && ! SCIPisZero(scip, SCIPvarGetLbGlobal(var)) )
840 /* variable does not appear in the conflict graph: switch to SOS1 branching rule, which does not make use of a conflict graph
842 SCIPdebugMessage("Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
847 /* if the constraint is local, then there is no need to act, since local constraints are handled by the local conflict graph in the
885 SCIPdebugMessage("Added new conflict graph arc from variable %s to variable %s.\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]));
886 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, node), SCIPdigraphGetNSuccessors(conflictgraph, node));
891 SCIPdebugMessage("Added new conflict graph arc from variable %s to variable %s.\n", SCIPvarGetName(vars[v]), SCIPvarGetName(var));
892 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, nodev), SCIPdigraphGetNSuccessors(conflictgraph, nodev));
897 /* variable does not appear in the conflict graph: switch to SOS1 branching rule, which does not make use of a conflict graph
899 SCIPdebugMessage("Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
934 SCIPerrorMessage("cannot add variable to SOS1 constraint <%s> that does not contain weights.\n", SCIPconsGetName(cons));
987 )
1044 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); /*lint !e740*/
1064 * Algorithm 457: Finding all Cliques of an Undirected Graph, Bron & Kerbosch, Commun. ACM, 1973
1070 SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of the conflict graph (only lower half filled) */
1071 SCIP_DIGRAPH* vertexcliquegraph, /**< graph that contains the information which cliques contain a given vertex
1072 * vertices of variables = 0, ..., nsos1vars-1; vertices of cliques = nsos1vars, ..., nsos1vars+ncliques-1*/
1084 int* workingset, /**< set of vertices that already served as extension and set of candidates that probably will lead to an extension */
1149 if ( vertex != workingset[j] && ! isConnectedSOS1(adjacencymatrix, NULL, vertex, workingset[j]) )
1178 /* If fixed point is initially chosen from candidates then number of disconnections will be preincreased by one. */
1220 SCIP_CALL( SCIPallocBufferArray(scip, &(cliques[*ncliques]), cliquesizes[*ncliques]) );/*lint !e866*/
1231 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "extsos1_%"SCIP_LONGINT_FORMAT, conshdlrdata->cntextsos1, conshdlrdata->cntextsos1);
1245 /* add arc from clique vertex to clique (needed in presolRoundConssSOS1() to delete redundand cliques) */
1255 cliquesizes[*ncliques] = cliquesizes[*ncliques-1]; /* cliquesizes[*ncliques] = size of newclique */
1272 SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights, FALSE, usebacktrack,
1273 cliques, ncliques, cliquesizes, newclique, workingsetnew, nworkingsetnew, nextsnew, pos, maxextensions, naddconss, success) );
1291 SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights, FALSE, usebacktrack,
1292 cliques, ncliques, cliquesizes, newclique, workingset, nworkingset, nextsnew, pos, maxextensions, naddconss, success) );
1331 SCIP_DIGRAPH* conflictgraphlin, /**< conflict graph of linear constraint (nodes: 1, ..., nlinvars) */
1335 int* posinlinvars /**< posinlinvars[i] = position (index) of SOS1 variable i in linear constraint,
1336 * posinlinvars[i]= -1 if @p i is not a SOS1 variable or not a variable of the linear constraint */
1351 for (v = 1; v < nlinvars; ++v) /* we start with v = 1, since "indexinlinvars < v" (see below) is never fulfilled for v = 0 */
1477 /** get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero */
1483 SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
1485 SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
1521 if ( sos1node >= 0 && ! implnodes[sos1node] && ( SCIPisFeasPositive(scip, data->lbimpl) || SCIPisFeasNegative(scip, data->ubimpl) ) )
1525 SCIP_CALL( getSOS1Implications(scip, conshdlrdata, vars, implgraph, implhash, implnodes, succnode) );
1610 SCIPdebugMessage("substituted variable <%s> by <%s>.\n", SCIPvarGetName(vars[j]), SCIPvarGetName(var));
1611 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[j], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); /*lint !e740*/
1612 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) ); /*lint !e740*/
1628 SCIPdebugMessage("variable <%s> appears twice in constraint, fixing it to 0.\n", SCIPvarGetName(vars[j]));
1672 SCIPdebugMessage("Deleting SOS1 constraint <%s> with < 2 variables.\n", SCIPconsGetName(cons));
1685 SCIPdebugMessage("The problem is infeasible: more than one variable has bounds that keep it from being 0.\n");
1712 SCIPdebugMessage("Deleting redundant SOS1 constraint <%s> with one variable.\n", SCIPconsGetName(cons));
1720 /* note: there is no need to update consdata->nfixednonzeros, since the constraint is deleted as soon nfixednonzeros > 0. */
1729 SCIP_CALL( SCIPcreateConsSetpack(scip, &setpackcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars,
1730 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons),
1731 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons),
1736 SCIPdebugMessage("Upgrading SOS1 constraint <%s> to set packing constraint.\n", SCIPconsGetName(cons));
1870 SCIP_CALL( presolRoundConsSOS1(scip, cons, consdata, eventhdlr, &substituted, &cutoff, &success, ndelconss, nupgdconss, nfixedvars, nremovedvars) );
1953 SCIP_CALL( SCIPcomputeArraysIntersection(comsucc, ncomsucc, succ, nsucc, comsucc, &ncomsucc) );
1973 SCIP_CALL( cliqueGetCommonSuccessorsSOS1(conshdlrdata, conflictgraph, newclique, vars, nvars, comsucc, &ncomsucc) );
1978 SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, consvars, consweights,
1979 TRUE, (maxextensions <= 1) ? FALSE : TRUE, cliques, &ncliques, cliquesizes, newclique, comsucc, ncomsucc, 0, -1, &maxextensions,
2038 SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
2040 SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to a given node i in the implication graph is implied to be nonzero */
2041 SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of the conflict graph (only lower half filled) */
2043 int nonznode, /**< node of the conflict graph that is implied to be nonzero if given node is nonzero */
2086 (void) SCIPsnprintf(namesos, SCIP_MAXSTRLEN, "presolved_sos1_%s_%s", SCIPvarGetName(var1), SCIPvarGetName(var2) );
2087 SCIP_CALL( SCIPcreateConsSOS1(scip, &soscons, namesos, 0, NULL, NULL, TRUE, TRUE, TRUE, FALSE, TRUE,
2106 assert( nonznode == (int) (size_t) SCIPhashmapGetImage(implhash, SCIPnodeGetVarSOS1(conflictgraph, nonznode)) );
2120 if ( varGetNodeSOS1(conshdlrdata, totalvars[succnode]) >= 0 && ! implnodes[succnode] && ( SCIPisFeasPositive(scip, data->lbimpl) || SCIPisFeasNegative(scip, data->ubimpl) ) )
2122 /* by construction: nodes of SOS1 variables are equal for conflict graph and implication graph */
2123 assert( succnode == (int) (size_t) SCIPhashmapGetImage(implhash, SCIPnodeGetVarSOS1(conflictgraph, succnode)) );
2125 SCIP_CALL( updateConflictGraphSOS1(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, implnodes, adjacencymatrix, givennode, succnode, naddconss) );
2133 /** returns whether node is implied to be zero; this information is taken from the input array 'implnodes' */
2137 SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2140 {
2195 if ( ( lower && SCIPisFeasLT(scip, ub, newbound) ) || ( ! lower && SCIPisFeasGT(scip, lb, newbound) ) )
2208 SCIPdebugMessage("fixed variable %s from lb = %f and ub = %f to 0.0 \n", SCIPvarGetName(varv), lb, ub);
2214 indv = (int) (size_t) SCIPhashmapGetImage(implhash, varv); /* get index of x_v in implication graph */
2220 /* search for nodew in existing successors. If this is the case then check whether the lower implication bound may be updated ... */
2233 SCIPdebugMessage("updated to implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2239 SCIPdebugMessage("updated to implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2245 /* ..., otherwise if there does not exist an arc between indv and indw already, then create one and add implication */
2254 SCIPdebugMessage("add implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2260 SCIPdebugMessage("add implication %s != 0 -> %s <= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2272 * Assume the variable from the input is nonzero. If this implies that some other variable is also nonzero, then
2281 SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
2283 SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2294 SCIP_Real boundnonzero, /**< bound of variable if it is known to be nonzero if infinity values are not summarized */
2295 int ninftynonzero, /**< number of times infinity/-infinity has to be summarized to boundnonzero */
2308 nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
2310 /* if nodev is an index of an SOS1 variable and at least one lower bound of a variable that is not x_v is infinity */
2326 /* variable should not be fixed to be already zero (note x_v is fixed to be nonzero by assumption) */
2327 if ( nodew < 0 || ( nodev != nodew && ! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodew) && ! isImpliedZero(conflictgraph, implnodes, nodew) ) )
2336 /* boundnonzero is the bound of x_v if x_v is nonzero we use this information to get a bound of x_w if x_v is
2348 nodecliq = varGetNodeSOS1(conshdlrdata, vars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
2350 /* if nodecliq is not a member of an SOS1 constraint or the variable corresponding to nodecliq is not implied to be zero if x_v != 0 */
2351 if ( nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
2397 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, TRUE, nchgbds, update) );
2401 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, FALSE, nchgbds, update) );
2408 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, FALSE, nchgbds, update) );
2412 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, TRUE, nchgbds, update) );
2425 * For a given vertex @p v search for a clique of the conflict graph induced by the variables of a linear constraint that
2432 SCIP_DIGRAPH* conflictgraphroot, /**< conflict graph of the root node (nodes: 1, ..., @p nsos1vars) */
2433 SCIP_DIGRAPH* conflictgraphlin, /**< conflict graph of linear constraint (nodes: 1, ..., @p nlinvars) */
2435 SCIP_Bool* coveredvars, /**< states which variables of the linear constraint are currently covered by a clique */
2439 SCIP_Bool considersolvals /**< TRUE if largest auxiliary bigM values of variables should be prefered */
2491 /* search for the extension with the largest absolute value of its LP relaxation solution value */
2545 SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \f$ implies a new lower/upper bound for \f$ x_j\f$) */
2552 SCIP_Bool* implupdate, /**< pointer to store whether the implication graph has been updated in this function call */
2560 SCIP_Bool* implnodes = NULL; /* implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2561 SCIP_Bool* coveredvars = NULL; /* coveredvars[i] = TRUE if variable with index i is covered by the clique cover */
2562 int* varindincons = NULL; /* varindincons[i] = position of SOS1 index i in linear constraint (-1 if x_i is not involved in linear constraint) */
2564 SCIP_VAR** trafolinvars = NULL; /* variables of transformed linear constraints without (multi)aggregated variables */
2572 SCIP_VAR** sos1linvars = NULL; /* variables that are not contained in linear constraint, but are in conflict with a variable from the linear constraint */
2641 SCIP_CALL( SCIPgetProbvarLinearSum(scip, trafolinvars, trafolinvals, &ntrafolinvars, noriglinvars, &constant, &requiredsize, TRUE) );
2647 SCIP_CALL( SCIPgetProbvarLinearSum(scip, trafolinvars, trafolinvals, &ntrafolinvars, requiredsize, &constant, &requiredsize, TRUE) );
2771 SCIP_CALL( genConflictgraphLinearCons(conshdlrdata, conflictgraphlin, conflictgraph, trafolinvars, ntrafolinvars, varindincons) );
2789 SCIP_CALL( SCIPallocBufferArray(scip, &(cliquecovers[ncliquecovers]), ntrafolinvars) ); /*lint !e866*/
2790 SCIP_CALL( computeVarsCoverSOS1(scip, conflictgraph, conflictgraphlin, trafolinvars, coveredvars, cliquecovers[ncliquecovers], &(cliquecoversizes[ncliquecovers]), v, FALSE) );
2798 /* compute variables that are not contained in transformed linear constraint, but are in conflict with a variable from the transformed linear constraint */
2821 /* if variable is not a member of linear constraint and not already listed in the array sos1linvars */
2835 /* sort each cliquecover array in ascending order of the lower bounds of a_i * x_i; fill vector varincover */
2888 nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
2894 SCIP_CALL( getSOS1Implications(scip, conshdlrdata, totalvars, implgraph, implhash, implnodes, (int) (size_t) SCIPhashmapGetImage(implhash, var)) );
2929 nodecliq = varGetNodeSOS1(conshdlrdata, trafolinvars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
2934 /* if nodev or nodecliq are not a member of an SOS1 constraint or the variable corresponding to nodecliq is not implied to be zero if x_v != 0 */
2935 if ( nodev < 0 || nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
2977 SCIPdebugMessage("changed lower bound of variable %s from %f to %f \n", SCIPvarGetName(var), lb, newbound);
2998 SCIPdebugMessage("changed upper bound of variable %s from %f to %f \n", SCIPvarGetName(var), ub, newbound);
3005 SCIP_CALL( updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3006 trafolinvars, trafolinvals, ntrafolinvars, trafoubs, var, trafoubv, newboundnonzero, ninftynonzero, TRUE, nchgbds, &update) );
3028 /* sort each cliquecover array in ascending order of the lower bounds of a_i * x_i; fill vector varincover */
3041 /* for every variable that is in transformed constraint or every variable that is in conflict with some variable from trans. cons.:
3079 nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
3082 /* determine incidence vector of implication variables (i.e., which SOS1 variables are nonzero if x_v is nonzero) */
3085 SCIP_CALL( getSOS1Implications(scip, conshdlrdata, totalvars, implgraph, implhash, implnodes, (int) (size_t) SCIPhashmapGetImage(implhash, var)) );
3116 /* determine maximum without index v and if x_v is nonzero (note that trafolbs is sorted non-increasingly) */
3122 nodecliq = varGetNodeSOS1(conshdlrdata, trafolinvars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
3127 /* if nodev or nodecliq are not a member of an SOS1 constraint or the variable corresponding to nodecliq is not implied to be zero if x_v != 0 */
3128 if ( nodev < 0 || nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
3174 SCIPdebugMessage("changed upper bound of variable %s from %f to %f \n", SCIPvarGetName(var), ub, newbound);
3195 SCIPdebugMessage("changed lower bound of variable %s from %f to %f \n", SCIPvarGetName(var), lb, newbound);
3202 SCIP_CALL( updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3203 trafolinvars, trafolinvals, ntrafolinvars, trafolbs, var, trafolbv, newboundnonzero, ninftynonzero, FALSE, nchgbds, &update) );
3304 for (j = 0; (j < conshdlrdata->maxtightenbds || conshdlrdata->maxtightenbds == -1 ) && ! cutoff; ++j)
3312 SCIP_CALL( tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, implgraph, implhash, adjacencymatrix, totalvars, ntotalvars, nsos1vars, nchgbds, &implupdate, &cutoff) );
3342 SCIP_CALL( updateConflictGraphSOS1(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, implnodes, adjacencymatrix, i, i, naddconss) );
3420 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) )
3428 SCIPdebugMessage("variable <%s> is fixed nonzero, fixing other variables to 0.\n", SCIPvarGetName(vars[firstFixedNonzero]));
3435 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
3446 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
3447 assert( ! infeasible ); /* there should be no variables after firstFixedNonzero that are fixed to be nonzero */
3499 assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(SCIPnodeGetVarSOS1(conflictgraph, node))) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(SCIPnodeGetVarSOS1(conflictgraph, node))) );
3521 SCIP_CALL( inferVariableZero(scip, succvar, cons, inferinfo, &infeasible, &tightened, &success) );
3574 SCIP_CALL( SCIPinferVarLbCons(scip, var, succdata->lbimpl, cons, inferinfo, FALSE, &infeasible, &tightened) );
3590 SCIP_CALL( SCIPinferVarUbCons(scip, var, succdata->ubimpl, cons, inferinfo, FALSE, &infeasible, &tightened) );
3646 /* we do not create the adjacency matrix of the conflict graph if the number of SOS1 variables is larger than a predefined value */
3650 SCIPdebugMessage("Implication graph was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
3670 * Note: For separation of implied bound cuts it is important that SOS1 variables are enumerated first
3752 SCIP_CALL( tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->implgraph, implhash, adjacencymatrix, implvars, nimplnodes, nsos1vars, nchgbds, &implupdate, cutoff) );
3829 /** get the vertices whose neighbor set covers a subset of the neighbor set of a given other vertex.
3836 SCIP_Bool* verticesarefixed, /**< array that indicates which variables are currently fixed to zero */
3838 int* neightocover, /**< neighbors of given vertex to be covered (or NULL if all neighbors shall be covered) */
3839 int nneightocover, /**< number of entries of neightocover (or 0 if all neighbors shall be covered )*/
3840 int* coververtices, /**< array to store the vertices whose neighbor set covers the neighbor set of the given vertex */
3931 assert( *ncoververtices <= 1 || coververtices[*ncoververtices - 1] > coververtices[*ncoververtices - 2] );
3944 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
3949 int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the second node */
3953 SCIP_Bool takeallsucc; /* whether to set fixingsnode1 = neighbors of 'branchvertex' in the conflict graph */
3981 /* get all the neighbors of the variable with index 'branchvertex' whose solution value is nonzero */
3984 if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, SCIPnodeGetVarSOS1(conflictgraph, succ[j]))) )
3991 /* if one of the sets fixingsnode1 or fixingsnode2 contains only one variable with a nonzero LP value we perform standard neighborhood branching */
3994 /* get the vertices whose neighbor set cover the selected subset of the neighbors of the given branching vertex */
3995 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
3997 /* determine the intersection of the neighbors of branchvertex with the intersection of all the neighbors of fixingsnode2 */
3998 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode2, *nfixingsnode2, fixingsnode1, nfixingsnode1) );
4007 /* we decide whether to use all successors if one partition of complete bipartite subgraph has only one node */
4037 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4041 /* use neighborhood branching, i.e, for the second node only the branching vertex can be fixed */
4051 /** gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision */
4058 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4060 int* fixingsnode1, /**< vertices of variables that will be fixed to zero for the first node (size = nsos1vars) */
4061 int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the second node (size = nsos1vars) */
4062 SCIP_Real* branchpriors, /**< pointer to store branching priorities (size = nsos1vars) or NULL if not needed */
4063 int* vertexbestprior, /**< pointer to store vertex with the best branching priority or NULL if not needed */
4093 if ( nsucc == 0 || SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, SCIPnodeGetVarSOS1(conflictgraph, i))) || verticesarefixed[i] )
4102 SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, verticesarefixed, bipbranch, i, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4157 int* fixingsexec, /**< vertices of variables to be fixed to zero for this strong branching execution */
4158 int nfixingsexec, /**< number of vertices of variables to be fixed to zero for this strong branching execution */
4159 int* fixingsop, /**< vertices of variables to be fixed to zero for the opposite strong branching execution */
4160 int nfixingsop, /**< number of vertices of variables to be fixed to zero for the opposite strong branching execution */
4162 SCIP_Bool fixnonzero, /**< shall opposite variable (if positive in sign) fixed to the feasibility tolerance
4164 int* domainfixings, /**< vertices that can be used to reduce the domain (should have size equal to number of variables) */
4165 int* ndomainfixings, /**< pointer to store number of vertices that can be used to reduce the domain, could be filled by earlier calls */
4167 SCIP_Real* objval, /**< pointer to store objective value of LP with fixed variables (SCIP_INVALID if reddomain = TRUE or lperror = TRUE) */
4168 SCIP_Bool* lperror /**< pointer to store whether an unresolved LP error or a strange solution status occurred */
4227 if ( SCIPisFeasGT(scip, SCIPvarGetLbLocal(var), 0.0) || SCIPisFeasLT(scip, SCIPvarGetUbLocal(var), 0.0) )
4265 else if ( solstat == SCIP_LPSOLSTAT_OPTIMAL || solstat == SCIP_LPSOLSTAT_TIMELIMIT || solstat == SCIP_LPSOLSTAT_ITERLIMIT )
4290 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4291 int* fixingsnode1, /**< pointer to store vertices of variables that will be fixed to zero for the first node (size = nsos1vars) */
4292 int* fixingsnode2, /**< pointer to store vertices of variables that will be fixed to zero for the second node (size = nsos1vars) */
4294 SCIP_Real* bestobjval1, /**< pointer to store LP objective for left child node of branching decision with best priority */
4295 SCIP_Real* bestobjval2, /**< pointer to store LP objective for right child node of branching decision with best priority */
4330 SCIP_CALL( getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, nsos1vars, verticesarefixed,
4400 /* if variable with index 'vertex' does not violate any complementarity in its neighborhood for the current LP relaxation solution */
4412 SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, verticesarefixed, bipbranch, testvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4415 SCIP_CALL( performStrongbranchSOS1(scip, conflictgraph, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2,
4416 inititer, conshdlrdata->fixnonzero, domainfixings, &ndomainfixings, &infeasible1, &objval1, &lperror) );
4421 SCIP_CALL( performStrongbranchSOS1(scip, conflictgraph, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1,
4446 score = MAX( REALABS( objval1 - lpobjval ), SCIPfeastol(scip) ) * MAX( REALABS( objval2 - lpobjval ), SCIPfeastol(scip) );/*lint !e666*/
4472 SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, domainfixings[i]), node, &infeasible) );
4491 /** for two given vertices @p v1 and @p v2 search for a clique in the conflict graph that contains these vertices. From
4501 SCIP_Bool extend, /**< should @p v1 and @p v2 be greedily extended to a clique of larger size */
4616 else /* search for the extension with the largest absolute value of its LP relaxation solution value */
4719 * @note In this function the conflict graph is updated to the conflict graph of the considered child branching node.
4727 SCIP_DIGRAPH* localconflicts, /**< local conflicts (updates to local conflicts of child node) */
4729 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zerox */
4730 int* fixingsnode1, /**< vertices of variables that will be fixed to zero for the branching node in the input of this function */
4732 int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the other branching node */
4735 SCIP_Bool onlyviolsos1 /**< should only SOS1 constraints be added that are violated by the LP solution */
4756 int* coverarray; /* vertices, not in fixingsnode1 that cover all the vertices in array fixingsnode22 */
4781 assert( nfixingsnode1 <= 1 || (fixingsnode1[nfixingsnode1 - 1] > fixingsnode1[nfixingsnode1 - 2]) ); /* test: vertices are sorted */
4788 assert( nfixingsnode2 <= 1 || (fixingsnode2[nfixingsnode2 - 1] > fixingsnode2[nfixingsnode2 - 2]) ); /* test: vertices are sorted */
4792 /* compute the set of vertices that have a neighbor in the set fixingsnode2, but are not in the set fixingsnode1 or fixingsnode2 and are not already fixed */
4837 /* compute first partition of fixingsnode2 that is the intersection of the neighbors of 'vertex1' with the set fixingsnode2 */
4847 assert( nfixingsnode21 == 1 || (fixingsnode21[nfixingsnode21 - 1] > fixingsnode21[nfixingsnode21 - 2]) ); /* test: successor vertices are sorted */
4862 SCIP_CALL( SCIPcomputeArraysSetminus(fixingsnode2, nfixingsnode2, fixingsnode21, nfixingsnode21, fixingsnode22, &nfixingsnode22) );
4865 /* compute cover set (that are all the vertices not in fixingsnode1 and fixingsnode21, whose neighborhood covers all the vertices of fixingsnode22) */
4866 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, -1, fixingsnode22, nfixingsnode22, coverarray, &ncoverarray) );
4867 SCIP_CALL( SCIPcomputeArraysSetminus(coverarray, ncoverarray, fixingsnode1, nfixingsnode1, coverarray, &ncoverarray) );
4868 SCIP_CALL( SCIPcomputeArraysSetminus(coverarray, ncoverarray, fixingsnode21, nfixingsnode21, coverarray, &ncoverarray) );
4933 SCIPsortInt(SCIPdigraphGetSuccessors(localconflicts, vertex1), SCIPdigraphGetNSuccessors(localconflicts, vertex1));
4934 SCIPsortInt(SCIPdigraphGetSuccessors(localconflicts, vertex2), SCIPdigraphGetNSuccessors(localconflicts, vertex2));
4935 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, vertex1), SCIPdigraphGetNSuccessors(conflictgraph, vertex1));
4936 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, vertex2), SCIPdigraphGetNSuccessors(conflictgraph, vertex2));
4938 /* mark conflictgraph as not local such that the new arcs are deleted after currents node processing */
5006 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sos1_branchnode_%i_no_%i", SCIPnodeGetNumber(node), *naddedconss);
5007 SCIP_CALL( SCIPcreateConsSOS1(scip, &conssos1, name, 0, NULL, NULL, TRUE, TRUE, TRUE, FALSE, TRUE,
5026 /* possibly create linear constraint of the form x_i/u_i + x_j/u_j <= t if a bound variable t with x_i <= u_i * t and x_j <= u_j * t exists.
5027 * Otherwise try to create a constraint of the form x_i/u_i + x_j/u_j <= 1. Try the same for the lower bounds. */
5028 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "boundcons_branchnode_%i_no_%i", SCIPnodeGetNumber(node), *naddedconss);
5032 SCIP_CALL( SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -SCIPinfinity(scip), 0.0, TRUE, FALSE, TRUE, FALSE, FALSE,
5036 SCIP_CALL( getBoundConsFromVertices(scip, conflictgraph, vertex1, vertex2, boundvar1, conshdlrdata->addextendedbds, conssos1, &feas) );
5041 SCIP_CALL( SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -SCIPinfinity(scip), 1.0, TRUE, FALSE, TRUE, FALSE, FALSE,
5045 SCIP_CALL( getBoundConsFromVertices(scip, conflictgraph, vertex1, vertex2, NULL, conshdlrdata->addextendedbds, conssos1, &feas) );
5088 SCIP_DIGRAPH* localconflicts, /**< local conflicts that should be removed from conflict graph */
5091 {
5125 * - Branch on the neighborhood of a single variable @p i, i.e., in one branch \f$x_i\f$ is fixed to zero and in the
5128 * - Branch on complete bipartite subgraphs of the conflict graph, i.e., in one branch fix the variables from the first
5131 * - In addition to variable domain fixings, it is sometimes also possible to add new SOS1 constraints to the branching
5132 * nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.
5134 * We make use of different selection rules that define on which system of SOS1 variables to branch next:
5138 * - Strong branching: Here, the LP-relaxation is partially solved for each branching decision among a candidate list.
5207 /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
5214 SCIPdebugMessage("propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen);
5264 if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
5274 if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
5301 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, j), SCIPdigraphGetNSuccessors(conflictgraph, j));
5335 nstrongrounds = MAX(10, (int)SCIPfloor(scip, pow(log((SCIP_Real)nsos1vars), 1.0)));/*lint !e666*/
5337 nstrongrounds = MAX(5, (int)SCIPfloor(scip, pow(log((SCIP_Real)nsos1vars), 0.7)));/*lint !e666*/
5358 SCIP_CALL( getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, nsos1vars, verticesarefixed, bipbranch, fixingsnode1, fixingsnode2, NULL, &branchvertex, &relsolfeas) );
5386 SCIP_CALL( getBranchingDecisionStrongbranchSOS1(scip, conshdlrdata, conflictgraph, nsos1vars, lpobjval, bipbranch, nstrongrounds, verticesarefixed,
5412 SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, verticesarefixed, bipbranch, branchvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
5459 SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode1[j]), node1, &infeasible) );
5484 SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode2[j]), node2, &infeasible) );
5490 if ( conshdlrdata->addcomps && ( conshdlrdata->addcompsdepth == -1 || conshdlrdata->addcompsdepth >= SCIPgetDepth(scip) ) )
5497 SCIP_CALL( addBranchingComplementaritiesSOS1(scip, node1, conshdlrdata, conflictgraph, conshdlrdata->localconflicts,
5498 nsos1vars, verticesarefixed, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2, &naddedconss, TRUE) );
5503 SCIP_CALL( addBranchingComplementaritiesSOS1(scip, node2, conshdlrdata, conflictgraph, conshdlrdata->localconflicts,
5504 nsos1vars, verticesarefixed, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1, &naddedconss, TRUE) );
5549 * Depending on the parameters (@c branchnonzeros, @c branchweight) there are three ways to choose
5555 * <TR><TD>@c false </TD><TD> @c true </TD><TD>maximal weight corresponding to nonzero variable</TD></TR>
5559 * @c branchnonzeros = @c false, @c branchweight = @c true allows the user to specify an order for
5618 /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
5624 SCIPdebugMessage("propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen);
5684 SCIPdebugMessage("Branching on constraint <%s> (weight: %f).\n", SCIPconsGetName(branchCons), maxWeight);
5695 assert( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, vars[0])) && ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, vars[1])) );
5700 SCIP_CALL( SCIPcreateChild(scip, &node1, SCIPcalcNodeselPriority(scip, vars[0], SCIP_BRANCHDIR_DOWNWARDS, 0.0), SCIPcalcChildEstimate(scip, vars[0], 0.0) ) );
5704 SCIP_CALL( SCIPcreateChild(scip, &node2, SCIPcalcNodeselPriority(scip, vars[1], SCIP_BRANCHDIR_DOWNWARDS, 0.0), SCIPcalcChildEstimate(scip, vars[1], 0.0) ) );
5743 /* branch on variable ind: either all variables up to ind or all variables after ind are zero */
5986 * where \f$\ell_1, \ldots, \ell_n\f$ and \f$u_1, \ldots, u_n\f$ are the nonzero and finite lower and upper bounds of
5987 * the variables \f$x_1, \ldots, x_n\f$. If an upper bound < 0 or a lower bound > 0, the constraint itself is
5988 * redundant, so the cut is not applied (lower bounds > 0 and upper bounds < 0 are usually detected in presolving or
5989 * propagation). Infinite bounds and zero are skipped. Thus \f$\ell_1, \ldots, \ell_n\f$ are all negative, which
5990 * results in the \f$\leq\f$ inequality. In case of the presence of variable upper bounds, the bound inequality can
5993 * Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as
5994 * above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most
6005 SCIP_Bool local, /**< in any case produce a local cut (even if local bounds of variables are valid globally) */
6008 SCIP_Bool removable, /**< should the inequality be removed from the LP due to aging or cleanup? */
6039 /* Loop through all variables. We check whether all bound variables (if existent) are equal; if this is the
6097 /* should not apply the cut if a variable is fixed to be negative -> constraint is redundant */
6121 SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowub, conshdlr, name, -SCIPinfinity(scip), 0.0, localubs, FALSE, removable) );
6129 SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowub, conshdlr, name, -SCIPinfinity(scip), rhs, localubs, FALSE, removable) );
6144 /* loop through all variables. We check whether all bound variables (if existent) are equal; if this is the
6205 /* should not apply the cut if a variable is fixed to be positive -> constraint is redundant */
6229 SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowlb, conshdlr, name, -SCIPinfinity(scip), 0.0, locallbs, FALSE, TRUE) );
6237 SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowlb, conshdlr, name, -SCIPinfinity(scip), rhs, locallbs, FALSE, TRUE) );
6264 /* we don't accept the solution as new incumbent, because we want to find many violated clique inequalities */
6331 if ( generateBoundInequalityFromSOS1Nodes(scip, tcliquedata->conshdlr, tcliquedata->conflictgraph,
6332 cliquenodes, ncliquenodes, 1.0, FALSE, FALSE, tcliquedata->strthenboundcuts, FALSE, nameext, &rowlb, &rowub) != SCIP_OKAY )
6371 /* if we found more than half the cuts we are allowed to generate, we accept the clique as new incumbent,
6396 int maxboundcuts, /**< maximal number of bound cuts separated per separation round (-1: no limit) */
6409 int maxzeroextensions = 1000; /* maximal number of zero-valued variables extending the clique (-1: no limit) */
6410 int backtrackfreq = 1000; /* frequency for premature backtracking up to tree level 1 (0: no backtracking) */
6436 SCIP_CALL( updateWeightsTCliquegraph(scip, conshdlrdata, tcliquedata, conflictgraph, sol, nsos1vars) );
6463 /** Generate a bound constraint from the variables of an SOS1 constraint (see generateBoundInequalityFromSOS1Nodes() for more information) */
6469 SCIP_Bool local, /**< in any case produce a local cut (even if local bounds of variables are valid globally) */
6472 SCIP_Bool removable, /**< should the inequality be removed from the LP due to aging or cleanup? */
6505 if ( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(consdata->vars[j])) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(consdata->vars[j])) )
6515 SCIP_CALL( generateBoundInequalityFromSOS1Nodes(scip, conshdlr, conshdlrdata->conflictgraph, nodes, cnt, 1.0, local, global,
6536 int maxboundcuts, /**< maximal number of bound cuts separated per separation round (-1: no limit) */
6561 SCIPdebugMessage("Separating inequalities for SOS1 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
6563 SCIPdebugMessage("Checking for initial rows for SOS1 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
6568 SCIP_CALL( generateBoundInequalityFromSOS1Cons(scip, conshdlr, conss[c], FALSE, TRUE, TRUE, FALSE, &consdata->rowlb, &consdata->rowub) );
6573 if ( row != NULL && ! SCIProwIsInLP(row) && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, row) ) )
6575 assert( SCIPisInfinity(scip, -SCIProwGetLhs(row)) && ( SCIPisEQ(scip, SCIProwGetRhs(row), 1.0) || SCIPisEQ(scip, SCIProwGetRhs(row), 0.0) ) );
6590 if ( row != NULL && ! SCIProwIsInLP(row) && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, row) ) )
6592 assert( SCIPisInfinity(scip, -SCIProwGetLhs(row)) && ( SCIPisEQ(scip, SCIProwGetRhs(row), 1.0) || SCIPisEQ(scip, SCIProwGetRhs(row), 0.0) ) );
6625 int maxcuts, /**< maximal number of implied bound cuts separated per separation round (-1: no limit) */
6655 SCIP_CALL( initImplGraphSOS1(scip, conshdlrdata, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, cutoff, &success) );
6775 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &cut, conshdlr, "", -SCIPinfinity(scip), lhsrhs, FALSE, FALSE, TRUE) );
6784 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &cut, conshdlr, "", lhsrhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
6810 SCIPdebugMessage("added cut for implication %s != 0 -> %s >= %f \n", SCIPvarGetName(var), SCIPvarGetName(succvar), succdata->lbimpl);
6812 SCIPdebugMessage("added cut for implication %s != 0 -> %s <= %f \n", SCIPvarGetName(var), SCIPvarGetName(succvar), succdata->ubimpl);
6874 if ( conshdlrdata->boundcutsfreq >= 0 && ( (conshdlrdata->boundcutsfreq == 0 && depth == 0) || (conshdlrdata->boundcutsfreq > 0 && depth % conshdlrdata->boundcutsfreq == 0)) )
6892 SCIP_CALL( initsepaBoundInequalityFromSOS1Cons(scip, conshdlr, conshdlrdata, conss, nconss, sol, TRUE, maxboundcuts, &ngen, &cutoff) );
6904 SCIP_CALL( sepaBoundInequalitiesFromGraph(scip, conshdlr, conshdlrdata, sol, maxboundcuts, &ngen, &cutoff) );
6921 if ( conshdlrdata->implcutsfreq >= 0 && ( (conshdlrdata->implcutsfreq == 0 && depth == 0) || (conshdlrdata->implcutsfreq > 0 && depth % conshdlrdata->implcutsfreq == 0)) )
6936 SCIP_CALL( sepaImplBoundCutsSOS1(scip, conshdlr, conshdlrdata, sol, maximplcuts, &ngen, &cutoff) );
6956 /** gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem */
6963 SCIP_Bool* indicatorzero, /**< vector that indicates which variables are currently fixed to zero */
6964 SCIP_Real* weights /**< pointer to store weights determining the order of the variables (length = nsos1vars) */
7017 weights[i] = ( val + SCIPsumepsilon(scip) ) / ( sum * (SCIP_Real)nviols + SCIPsumepsilon(scip) );
7115 SCIP_CALL( markNeighborsMWISHeuristic(scip, conshdlr, conflictgraph, aggrnode, mark, indset, cnt, cutoff) );
7161 * by the algorithm GGWMIN of Shuichi Sakai, Mitsunori Togasaki and Koichi Yamazaki in "A note on greedy algorithms for the
7162 * maximum weighted independent set problem", Discrete Applied Mathematics. Here \f$x^*\f$ denotes the current LP
7163 * relaxation solution. Note that the solution of the MWIS is the indicator vector of an independent set.
7172 SCIP_Bool* indicatorzero, /**< vector that indicates which variables are currently fixed to zero */
7246 SCIP_CALL( markNeighborsMWISHeuristic(scip, conshdlr, conflictgraph, ind, mark, indset, &k, &cutoff) );
7264 /** check whether \f$x_1\f$ is a bound variable of \f$x_0\f$; i.e., \f$x_0 \leq c\cdot x_1\f$ or \f$x_0 \geq d\cdot x_1\f$
7265 * for positive values \f$c, d\f$. If true, then add this information to the node data of the conflict graph.
7311 SCIPdebugMessage("detected variable bound constraint %s >= %f %s.\n", SCIPvarGetName(var0), val, SCIPvarGetName(var1));
7329 SCIPdebugMessage("detected variable bound constraint %s <= %f %s.\n", SCIPvarGetName(var0), val, SCIPvarGetName(var1));
7338 /** pass connected component \f$C\f$ of the conflict graph and check whether all the variables correspond to a unique variable upper bound variable \f$z\f$,
7404 SCIP_CALL( passConComponentVarbound(scip, conflictgraph, succ[s], boundvar, checklb, processed, concomp, nconcomp, unique) );
7411 /** for each connected component \f$C\f$ of the conflict graph check whether all the variables correspond to a unique variable upper bound variable \f$z\f$
7412 * (e.g., for the upper bound case this means that \f$x_i \leq u_i z\f$ for every \f$i\in C\f$).
7421 SCIP_Bool checklb /**< whether to check lower bound variable (else check upper bound variable) */
7422 )
7471 SCIP_CALL( passConComponentVarbound(scip, conflictgraph, succ[s], boundvar, checklb, processed, concomp, &nconcomp, &unique) );
7489 SCIPdebugMessage("Found a connected component of size <%i> with unique bound variable.\n", nconcomp);
7502 /** check all linear constraints for variable bound constraints of the form \f$c\cdot z \leq x \leq d\cdot z\f$, where @p x is some SOS1
7511 )
7577 /** switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap */
7614 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(vars[i])) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[i])) )
7626 assert( node >= 0 || ( SCIPisFeasZero(scip, SCIPvarGetLbLocal(vars[i])) && SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[i]))) );
7650 SCIPdebugMessage("Switched to separating bound cuts from SOS1 constraints (and not from the conflict graph), since the SOS1 constraints do not overlap\n");
7665 {
7686 /* for each connected component of the conflict graph check whether all the variables correspond to a unique variable
7688 SCIP_CALL( checkConComponentsVarbound(scip, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, TRUE) );
7689 SCIP_CALL( checkConComponentsVarbound(scip, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, FALSE) );
7702 )
7704 SCIP_Bool* nodecreated; /* nodecreated[i] = TRUE if a node in the conflict graph is already created for index i
7751 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
7811 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
7823 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, var, (void*) (size_t) cntsos) );/*lint !e571*/
7851 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
7861 SCIP_CALL( SCIPdigraphAddArcSafe(conshdlrdata->conflictgraph, nodeorig[indi], nodeorig[indj], NULL) );
7862 SCIP_CALL( SCIPdigraphAddArcSafe(conshdlrdata->conflictgraph, nodeorig[indj], nodeorig[indi], NULL) );
7945 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
7964 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
7994 SCIP_CALL( checkSwitchNonoverlappingSOS1Methods(scip, conshdlrdata, conshdlrdata->conflictgraph, conss, nconss) );
7998 SCIP_CALL( initTCliquegraph(scip, conshdlr, conshdlrdata, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars) );
8006 /* initialize stack of variables fixed to nonzero (memory may be already allocated in consTransSOS1()) */
8010 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->fixnonzerovars, conshdlrdata->maxnfixnonzerovars) );
8018 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
8072 SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->fixnonzerovars, conshdlrdata->maxnfixnonzerovars); /*lint !e737*/
8112 SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[j], SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlr,
8174 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->fixnonzerovars, conshdlrdata->maxnfixnonzerovars) );
8190 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, sourcedata->weights, consdata->nvars) );
8201 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(consdata->vars[j])) )
8217 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[j], SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlr,
8224 SCIPdebugMessage("constraint <%s> has %d variables fixed to be nonzero.\n", SCIPconsGetName(*targetcons),
8261 if( nconss > 0 && ( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 ) )
8289 /* we do not create the adjacency matrix of the conflict graph if the number of SOS1 variables is larger than a predefined value */
8322 SCIPdebugMessage("Adjacency matrix was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
8326 SCIP_CALL( presolRoundConssSOS1(scip, eventhdlr, conshdlrdata, conflictgraph, adjacencymatrix, conss, nconss, nsos1vars, naddconss, ndelconss, nupgdconss, nfixedvars, &nremovedvars, result) );
8333 SCIP_CALL( presolRoundVarsSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, nsos1vars, nchgbds, naddconss, result) );
8347 SCIPdebugMessage("presolving fixed %d variables, removed %d variables, deleted %d constraints, and upgraded %d constraints.\n",
8348 *nfixedvars - oldnfixedvars, nremovedvars, *ndelconss - oldndelconss, *nupgdconss - oldnupgdconss);
8354 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
8371 SCIP_CALL( initsepaBoundInequalityFromSOS1Cons(scip, conshdlr, conshdlrdata, conss, nconss, NULL, FALSE, -1, NULL, &cutoff) );
8441 SCIPerrorMessage("Incompatible parameter setting: nonzero fixing is not compatible with bipartite or sos1 branching.\n");
8496 SCIPerrorMessage("Incompatible parameter setting: nonzero fixing is not compatible with bipartite or sos1 branching.\n");
8633 SCIP_CALL( initImplGraphSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, &cutoff, &success) );
8682 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
8686 SCIP_CALL( propVariableNonzero(scip, conflictgraph, implgraph, conss[0], node, conshdlrdata->implprop, &cutoff, &ngen) );
8751 SCIPdebugMessage("Propagation resolution method of SOS1 constraint <%s>.\n", SCIPconsGetName(cons));
8935 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) );
8972 SCIP_CALL( SCIPcreateConsSOS1(scip, cons, name, 0, NULL, NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
8987 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error: expected weight at input: %s\n", s);
8998 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error during parsing of the weight: %s\n", s);
9040 /** constraint method of constraint handler which returns the number of variables (if possible) */
9099 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <= SCIPgetNTotalVars(scip) );
9121 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <= SCIPgetNTotalVars(scip) );
9151 SCIPdebugMessage("changed bound of variable <%s> from %f to %f (nfixednonzeros: %d).\n", SCIPvarGetName(SCIPeventGetVar(event)),
9158 /** constraint handler method to determine a diving variable by assigning a variable and two values for diving */
9189 /* check whether the variable violates an SOS1 constraint together with at least one other variable */
9228 SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_SOS1VARIABLE, var, solval, fracval, &score, &roundup) );
9268 /* if the diving score voted for fixing the best variable to 0.0, we add this as the preferred bound change;
9271 assert( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(bestvar)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(bestvar)) );
9272 SCIP_CALL( SCIPaddDiveBoundChange(scip, bestvar, SCIP_BRANCHDIR_FIXED, 0.0, !bestvarfixneigh) );
9280 if ( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var)) )
9322 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecSOS1, NULL) );
9346 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSOS1, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
9348 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSOS1, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
9350 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSOS1, consSepasolSOS1, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
9357 "do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit)",
9388 "if TRUE turn neighborhood branching method on (note: an automatic switching to SOS1 branching is possible)",
9392 "if TRUE turn bipartite branching method on (note: an automatic switching to SOS1 branching is possible)",
9404 "if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance",
9408 "if TRUE then add complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching)",
9416 "minimal feasibility value for complementarity constraints in order to be added to the branching node",
9417 &conshdlrdata->addcompsfeas, TRUE, DEFAULT_ADDCOMPSFEAS, -SCIP_REAL_MAX, SCIP_REAL_MAX, NULL, NULL) );
9421 &conshdlrdata->addbdsfeas, TRUE, DEFAULT_ADDBDSFEAS, -SCIP_REAL_MAX, SCIP_REAL_MAX, NULL, NULL) );
9424 "should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities",
9436 "Branch on SOS cons. with highest nonzero-variable weight for branching (needs branchnonzeros = false)?",
9445 "maximal number of strong branching rounds to perform for each node (-1: auto); only available for neighborhood and bipartite branching",
9449 "maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit)",
9462 "if TRUE then automatically switch to separating initial SOS1 constraints if the SOS1 constraints do not overlap",
9507 * We set the constraint to not be modifable. If the weights are non NULL, the variables are ordered according to these
9510 * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
9518 SCIP_Real* weights, /**< weights determining the variable order, or NULL if natural order should be used */
9534 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
9536 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
9597 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
9601 /* replace original variables by transformed variables in transformed constraint, add locks, and catch events */
9619 SCIP_CALL( handleNewVariableSOS1(scip, *cons, consdata, conshdlrdata, consdata->vars[v], transformed) );
9626 /** creates and captures a SOS1 constraint with all constraint flags set to their default values.
9631 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
9639 SCIP_Real* weights /**< weights determining the variable order, or NULL if natural order should be used */
9642 SCIP_CALL( SCIPcreateConsSOS1( scip, cons, name, nvars, vars, weights, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
9654 )
9663 SCIPdebugMessage("adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var), SCIPconsGetName(cons), weight);
9688 {
9696 SCIPdebugMessage("appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons));
9917 /** based on solution values of the variables, fixes variables to zero to turn all SOS1 constraints feasible */
9923 SCIP_Bool* success /**< pointer to store whether SOS1 constraints have been turned feasible and
9965 assert( ! SCIPvarMayRoundUp(var) || ! SCIPisFeasPositive(scip, SCIPgetSolVal(scip, sol, var)) );
9966 assert( ! SCIPvarMayRoundDown(var) || ! SCIPisFeasNegative(scip, SCIPgetSolVal(scip, sol, var)) );
9990 SCIP_CALL( maxWeightIndSetHeuristic(scip, sol, conshdlr, conflictgraph, nsos1vars, indicatorzero, indset) );
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed) Definition: scip.c:22764 void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len) SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var) Definition: var.c:16759 SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff) Definition: scip.c:32398 void ** SCIPdigraphGetSuccessorsData(SCIP_DIGRAPH *digraph, int node) Definition: misc.c:5978 SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type) Definition: scip.c:15939 SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred) Definition: scip.c:32649 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) Definition: cons_sos1.c:1550 static SCIP_RETCODE genConflictgraphLinearCons(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraphlin, SCIP_DIGRAPH *conflictgraphorig, SCIP_VAR **linvars, int nlinvars, int *posinlinvars) Definition: cons_sos1.c:1334 Definition: type_result.h:33 SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name) Definition: scip.c:5847 Definition: type_result.h:37 SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans))) Definition: scip.c:5557 static SCIP_RETCODE fixVariableZero(SCIP *scip, SCIP_VAR *var, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: cons_sos1.c:599 static SCIP_RETCODE enforceConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_RESULT *result) Definition: cons_sos1.c:5147 SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success) Definition: cons_sos1.c:9923 static SCIP_RETCODE detectVarboundSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var0, SCIP_VAR *var1, SCIP_Real val0, SCIP_Real val1) Definition: cons_sos1.c:7273 Definition: type_lp.h:39 static SCIP_RETCODE getBranchingVerticesSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int branchvertex, int *fixingsnode1, int *nfixingsnode1, int *fixingsnode2, int *nfixingsnode2) Definition: cons_sos1.c:3946 SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples) Definition: scip.c:17456 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) Definition: cons_sos1.c:3478 Definition: struct_scip.h:53 TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph) Definition: tclique_graph.c:175 Definition: type_prob.h:38 TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight) Definition: tclique_graph.c:330 SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41528 SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop))) Definition: scip.c:5603 SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy) Definition: scip.c:30487 SCIP_Real * SCIPgetWeightsSOS1(SCIP *scip, SCIP_CONS *cons) Definition: cons_sos1.c:9771 SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa) Definition: scip.c:5215 static SCIP_RETCODE inferVariableZero(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened, SCIP_Bool *success) Definition: cons_sos1.c:673 static SCIP_RETCODE cliqueGetCommonSuccessorsSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int *clique, SCIP_VAR **vars, int nvars, int *comsucc, int *ncomsucc) Definition: cons_sos1.c:1387 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) Definition: cons_sos1.c:4159 Definition: type_result.h:49 static SCIP_RETCODE updateConflictGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **totalvars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, SCIP_Bool **adjacencymatrix, int givennode, int nonznode, int *naddconss) Definition: cons_sos1.c:2038 SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr) Definition: cons.c:4262 int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node) Definition: misc.c:5960 static SCIP_RETCODE getSOS1Implications(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR **vars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, int node) Definition: cons_sos1.c:1484 SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy))) Definition: scip.c:5303 SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut) Definition: scip.c:30469 Definition: struct_var.h:196 SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val) Definition: scip.c:34453 static SCIP_RETCODE propConsSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *ngen) Definition: cons_sos1.c:3380 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) Definition: cons_sos1.c:1072 static SCIP_Bool isImpliedZero(SCIP_DIGRAPH *conflictgraph, SCIP_Bool *implnodes, int node) Definition: cons_sos1.c:2140 SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant) Definition: scip.c:17512 SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars))) Definition: scip.c:5787 SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_setppc.c:8952 static SCIP_Real nodeGetSolvalBinaryBigMSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node) Definition: cons_sos1.c:402 SCIP_RETCODE SCIPappendVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_sos1.c:9688 SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound) Definition: scip.c:32162 static SCIP_RETCODE deleteVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos) Definition: cons_sos1.c:1033 SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize) Definition: misc.c:2052 static SCIP_Real nodeGetSolvalVarboundLbSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node) Definition: cons_sos1.c:452 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) Definition: cons_sos1.c:7349 SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata) Definition: scip.c:7747 miscellaneous datastructures int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_linear.c:16905 static SCIP_Real nodeGetSolvalVarboundUbSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node) Definition: cons_sos1.c:479 SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse))) Definition: scip.c:5764 static SCIP_RETCODE maxWeightIndSetHeuristic(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *indicatorzero, SCIP_Bool *indset) Definition: cons_sos1.c:7171 SCIP_RETCODE SCIPcomputeArraysIntersection(int *array1, int narray1, int *array2, int narray2, int *intersectarray, int *nintersectarray) Definition: misc.c:7968 static SCIP_RETCODE separateSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, SCIP_RESULT *result) Definition: cons_sos1.c:6842 void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len) SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals) Definition: scip.c:27875 static SCIP_RETCODE resetConflictgraphSOS1(SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, int nsos1vars) Definition: cons_sos1.c:5091 SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after) Definition: var.c:15695 SCIP_Longint SCIPgetNDualResolveLPIterations(SCIP *scip) Definition: scip.c:37323 SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var) Definition: scip.c:34593 Definition: type_result.h:40 static SCIP_RETCODE initConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss) Definition: cons_sos1.c:7702 tclique user interface static SCIP_RETCODE getBoundConsFromVertices(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int v1, int v2, SCIP_VAR *boundvar, SCIP_Bool extend, SCIP_CONS *cons, SCIP_Real *feas) Definition: cons_sos1.c:4500 void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len) void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2111 SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip) Definition: scip.c:37395 SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file) Definition: scip.c:26224 SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible) Definition: scip.c:30577 Constraint handler for the set partitioning / packing / covering constraints . Definition: type_lp.h:37 static SCIP_RETCODE getBranchingPrioritiesSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int *fixingsnode1, int *fixingsnode2, SCIP_Real *branchpriors, int *vertexbestprior, SCIP_Bool *relsolfeas) Definition: cons_sos1.c:4058 static SCIP_RETCODE getVectorOfWeights(SCIP *scip, SCIP_SOL *sol, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *indicatorzero, SCIP_Real *weights) Definition: cons_sos1.c:6963 Definition: struct_tree.h:122 SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree))) Definition: scip.c:5328 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) Definition: cons_sos1.c:2281 SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20638 SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound) Definition: scip.c:12400 Definition: struct_sol.h:50 SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3516 SCIP_Bool SCIPvarIsSOS1(SCIP_CONSHDLR *conshdlr, SCIP_VAR *var) Definition: cons_sos1.c:9843 SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2154 SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3542 SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr) Definition: scip.c:16242 SCIP_RETCODE SCIPdigraphCreate(SCIP_DIGRAPH **digraph, int nnodes) Definition: misc.c:5591 SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr) Definition: cons.c:3921 SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos) Definition: scip.c:36232 static SCIP_RETCODE enforceConssSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_RESULT *result) Definition: cons_sos1.c:5570 SCIP_RETCODE SCIPcreateConsBasicSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights) Definition: cons_sos1.c:9638 Definition: struct_misc.h:101 Definition: cons_sos1.c:203 SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success) Definition: scip.c:1750 SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar) Definition: scip.c:17159 TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2) Definition: tclique_graph.c:370 Definition: type_result.h:35 SCIP_RETCODE SCIPdigraphSetNSuccessors(SCIP_DIGRAPH *digraph, int node, int nsuccessors) Definition: misc.c:5871 Definition: struct_cons.h:36 #define SCIPfreeBlockMemoryArrayNull(scip, ptr, num) Definition: scip.h:20403 SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19592 SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue) Definition: scip.c:33261 SCIP_VAR * SCIPnodeGetVarSOS1(SCIP_DIGRAPH *conflictgraph, int node) Definition: cons_sos1.c:9898 Definition: struct_cons.h:116 Definition: type_retcode.h:42 void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight) Definition: tclique_graph.c:352 void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node) Definition: misc.c:5897 static SCIP_RETCODE updateWeightsTCliquegraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, TCLIQUE_DATA *tcliquedata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars) Definition: cons_sos1.c:5869 Definition: type_retcode.h:48 SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after) Definition: var.c:15787 SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming) Definition: scip.c:5496 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) Definition: cons_sos1.c:6470 Definition: type_result.h:36 void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node) Definition: misc.c:5913 static SCIP_RETCODE sepaBoundInequalitiesFromGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_SOL *sol, int maxboundcuts, int *ngen, SCIP_Bool *cutoff) Definition: cons_sos1.c:6396 SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41515 Definition: type_history.h:36 static SCIP_RETCODE fixVariableZeroNode(SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible) Definition: cons_sos1.c:544 SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_linear.c:16842 #define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum) Definition: scip.h:20391 Definition: type_var.h:44 internal miscellaneous methods Definition: type_retcode.h:33 void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status) Definition: tclique_branch.c:1000 static SCIP_RETCODE appendVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var) Definition: cons_sos1.c:987 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) Definition: cons_sos1.c:2546 SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming) Definition: scip.c:5261 SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata) Definition: scip.c:5161 static SCIP_RETCODE computeNodeDataSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nsos1vars) Definition: cons_sos1.c:7665 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) Definition: cons_sos1.c:6533 Definition: type_result.h:42 SCIP_RETCODE SCIPgetDivesetScore(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup) Definition: scip.c:32511 SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41554 SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data) Definition: misc.c:5809 SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode) Definition: scip.c:11966 Definition: type_lp.h:34 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) Definition: cons_sos1.c:2169 SCIP_RETCODE SCIPcomputeArraysSetminus(int *array1, int narray1, int *array2, int narray2, int *setminusarray, int *nsetminusarray) Definition: misc.c:8024 SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var) Definition: scip.c:23106 static SCIP_RETCODE checkConComponentsVarbound(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool checklb) Definition: cons_sos1.c:7422 SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20259 public data structures and miscellaneous methods SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data) Definition: misc.c:5837 int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node) Definition: misc.c:5945 static SCIP_RETCODE freeImplGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata) Definition: cons_sos1.c:3784 SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: scip.c:24759 SCIP_Bool SCIPdivesetSupportsType(SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype) Definition: heur.c:562 SCIP_RETCODE SCIPsetConshdlrGetDiveBdChgs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETDIVEBDCHGS((*consgetdivebdchgs))) Definition: scip.c:5833 Definition: type_message.h:43 Definition: type_var.h:46 SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row) Definition: scip.c:27798 SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx) Definition: scip.c:24356 Definition: struct_lp.h:189 SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var) Definition: scip.c:17412 static SCIP_RETCODE addVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Real weight) Definition: cons_sos1.c:917 SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var) Definition: var.c:16792 SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval) Definition: scip.c:32025 Definition: type_var.h:45 SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp))) Definition: scip.c:5580 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) Definition: cons_sos1.c:9517 SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var) Definition: var.c:16747 Constraint handler for linear constraints in their most general form, . static SCIP_RETCODE initImplGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars, int maxrounds, int *nchgbds, SCIP_Bool *cutoff, SCIP_Bool *success) Definition: cons_sos1.c:3620 static SCIP_RETCODE initTCliquegraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars) Definition: cons_sos1.c:5800 static SCIP_RETCODE addBoundCutSepa(SCIP *scip, TCLIQUE_DATA *tcliquedata, SCIP_ROW *rowlb, SCIP_ROW *rowub, SCIP_Bool *success, SCIP_Bool *cutoff) Definition: cons_sos1.c:5929 void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...) Definition: scip.c:1270 static SCIP_RETCODE addBranchingComplementaritiesSOS1(SCIP *scip, SCIP_NODE *node, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, int nsos1vars, SCIP_Bool *verticesarefixed, int *fixingsnode1, int nfixingsnode1, int *fixingsnode2, int nfixingsnode2, int *naddedconss, SCIP_Bool onlyviolsos1) Definition: cons_sos1.c:4727 SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound) Definition: scip.c:19964 SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val) Definition: cons_linear.c:16573 SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20535 SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos) Definition: scip.c:36278 SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete))) Definition: scip.c:5534 Definition: type_history.h:34 SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol))) Definition: scip.c:5400 SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr) Definition: cons_sos1.c:9799 SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint))) Definition: scip.c:5741 SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row) Definition: scip.c:27821 void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...) Definition: scip.c:1253 SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_linear.c:16236 static SCIP_RETCODE checkSwitchNonoverlappingSOS1Methods(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_CONS **conss, int nconss) Definition: cons_sos1.c:7584 #define SCIPduplicateBufferArray(scip, ptr, source, num) Definition: scip.h:20422 SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol))) Definition: scip.c:5424 const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr) Definition: event.c:278 static SCIP_RETCODE getBranchingDecisionStrongbranchSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Real lpobjval, SCIP_Bool bipbranch, int nstrongrounds, SCIP_Bool *verticesarefixed, int *fixingsnode1, int *fixingsnode2, int *vertexbestprior, SCIP_Real *bestobjval1, SCIP_Real *bestobjval2, SCIP_RESULT *result) Definition: cons_sos1.c:4287 SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound) Definition: scip.c:31962 static SCIP_RETCODE branchCons(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result) Definition: cons_disjunction.c:208 SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19519 SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound) Definition: scip.c:19997 static SCIP_RETCODE lockVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_sos1.c:716 static SCIP_RETCODE sepaImplBoundCutsSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_SOL *sol, int maxcuts, int *ngen, SCIP_Bool *cutoff) Definition: cons_sos1.c:6625 SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound) Definition: scip.c:31928 SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20365 SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable) Definition: scip.c:27587 constraint handler for SOS type 1 constraints SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file) Definition: scip.c:28321 #define SCIPduplicateBlockMemoryArray(scip, ptr, source, num) Definition: scip.h:20397 static SCIP_RETCODE getCoverVertices(SCIP_DIGRAPH *conflictgraph, SCIP_Bool *verticesarefixed, int vertex, int *neightocover, int nneightocover, int *coververtices, int *ncoververtices) Definition: cons_sos1.c:3839 SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_linear.c:16818 void SCIPsortInt(int *intarray, int len) static SCIP_RETCODE freeConflictgraph(SCIP_CONSHDLRDATA *conshdlrdata) Definition: cons_sos1.c:7897 Definition: type_retcode.h:45 void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len) Definition: type_lp.h:35 static SCIP_RETCODE presolRoundVarsSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, int nsos1vars, int *nchgbds, int *naddconss, SCIP_RESULT *result) Definition: cons_sos1.c:3246 static SCIP_RETCODE checkLinearConssVarboundSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **linconss, int nlinconss) Definition: cons_sos1.c:7511 SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup) Definition: scip.c:19465 static SCIP_RETCODE handleNewVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Bool transformed) Definition: cons_sos1.c:782 static SCIP_RETCODE consdataEnsurevarsSizeSOS1(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveWeights) Definition: cons_sos1.c:754 static SCIP_RETCODE unlockVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_sos1.c:735 static SCIP_Bool varIsSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var) Definition: cons_sos1.c:506 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) Definition: cons_sos1.c:1774 Definition: type_result.h:45 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) Definition: cons_sos1.c:7034 SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate) Definition: scip.c:33311 Definition: type_lp.h:38 SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_linear.c:16929 SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx) Definition: scip.c:24423 Definition: type_retcode.h:35 SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image) Definition: misc.c:2089 Definition: type_retcode.h:43 SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight) Definition: cons_sos1.c:9654 SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue) Definition: scip.c:33288 SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3598 static SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsSOS1) Definition: cons_sos1.c:9165 SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars))) Definition: scip.c:5810 SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val) Definition: scip.c:27851 Definition: struct_misc.h:171 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) Definition: cons_sos1.c:6003 Definition: type_set.h:36 static int varGetNodeSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var) Definition: cons_sos1.c:523 SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons) Definition: cons_linear.c:16953 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) Definition: cons_sos1.c:2435 static SCIP_Bool isConnectedSOS1(SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *conflictgraph, int vertex1, int vertex2) Definition: cons_sos1.c:297 Definition: type_result.h:39 Definition: struct_event.h:185 static SCIP_Bool isViolatedSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_SOL *sol) Definition: cons_sos1.c:357 int SCIPvarGetNodeSOS1(SCIP_CONSHDLR *conshdlr, SCIP_VAR *var) Definition: cons_sos1.c:9867 |