cons_sos1.c
Go to the documentation of this file.
32 * variable is nonzero. The special case of two variables arises, for instance, from equilibrium or
48 * - If an empty constraint is created and then variables are added with SCIPaddVarSOS1(), weights
51 * - All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are
74 * @todo Possibly allow to generate local cuts via strengthened local cuts (would need to modified coefficients of rows).
76 * @todo Check whether we can avoid turning off multi-aggregation (it is sometimes possible to fix a multi-aggregated
80 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
123 #define CONSHDLR_ENFOPRIORITY 100 /**< priority of the constraint handler for constraint enforcing */
124 #define CONSHDLR_CHECKPRIORITY -10 /**< priority of the constraint handler for checking feasibility */
125 #define CONSHDLR_SEPAFREQ 10 /**< frequency for separating cuts; zero means to separate only in the root node */
126 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
127 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
129 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
130 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
131 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
132 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
137 #define DEFAULT_MAXSOSADJACENCY 10000 /**< do not create an adjacency matrix if number of SOS1 variables is larger than predefined value
141 #define DEFAULT_MAXEXTENSIONS 1 /**< maximal number of extensions that will be computed for each SOS1 constraint */
142 #define DEFAULT_MAXTIGHTENBDS 5 /**< maximal number of bound tightening rounds per presolving round (-1: no limit) */
143 #define DEFAULT_PERFIMPLANALYSIS FALSE /**< if TRUE then perform implication graph analysis (might add additional SOS1 constraints) */
144 #define DEFAULT_DEPTHIMPLANALYSIS -1 /**< number of recursive calls of implication graph analysis (-1: no limit) */
152 #define DEFAULT_BRANCHSTRATEGIES "nbs" /**< possible branching strategies (see parameter DEFAULT_BRANCHINGRULE) */
153 #define DEFAULT_BRANCHINGRULE 'n' /**< which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique)
155 #define DEFAULT_AUTOSOS1BRANCH TRUE /**< if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap */
156 #define DEFAULT_FIXNONZERO FALSE /**< if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the
158 #define DEFAULT_ADDCOMPS FALSE /**< if TRUE then add complementarity constraints to the branching nodes (can be used in combination with
160 #define DEFAULT_MAXADDCOMPS -1 /**< maximal number of complementarity constraints added per branching node (-1: no limit) */
161 #define DEFAULT_ADDCOMPSDEPTH 30 /**< only add complementarity constraints to branching nodes for predefined depth (-1: no limit) */
162 #define DEFAULT_ADDCOMPSFEAS -0.6 /**< minimal feasibility value for complementarity constraints in order to be added to the branching node */
163 #define DEFAULT_ADDBDSFEAS 1.0 /**< minimal feasibility value for bound inequalities in order to be added to the branching node */
164 #define DEFAULT_ADDEXTENDEDBDS TRUE /**< should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities */
167 #define DEFAULT_NSTRONGROUNDS 0 /**< maximal number of strong branching rounds to perform for each node (-1: auto)
169 #define DEFAULT_NSTRONGITER 10000 /**< maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) */
172 #define DEFAULT_BOUNDCUTSFROMSOS1 FALSE /**< if TRUE separate bound inequalities from SOS1 constraints */
173 #define DEFAULT_BOUNDCUTSFROMGRAPH TRUE /**< if TRUE separate bound inequalities from the conflict graph */
174 #define DEFAULT_AUTOCUTSFROMSOS1 TRUE /**< if TRUE then automatically switch to separating from SOS1 constraints if the SOS1 constraints do not overlap */
175 #define DEFAULT_BOUNDCUTSFREQ 10 /**< frequency for separating bound cuts; zero means to separate only in the root node */
177 #define DEFAULT_MAXBOUNDCUTS 50 /**< maximal number of bound cuts separated per branching node */
178 #define DEFAULT_MAXBOUNDCUTSROOT 150 /**< maximal number of bound cuts separated per iteration in the root node */
179 #define DEFAULT_STRTHENBOUNDCUTS TRUE /**< if TRUE then bound cuts are strengthened in case bound variables are available */
180 #define DEFAULT_IMPLCUTSFREQ 0 /**< frequency for separating implied bound cuts; zero means to separate only in the root node */
181 #define DEFAULT_IMPLCUTSDEPTH 40 /**< node depth of separating implied bound cuts (-1: no limit) */
182 #define DEFAULT_MAXIMPLCUTS 50 /**< maximal number of implied bound cuts separated per branching node */
183 #define DEFAULT_MAXIMPLCUTSROOT 150 /**< maximal number of implied bound cuts separated per iteration in the root node */
213 SCIP_VAR* lbboundvar; /**< bound variable @p z from constraint \f$x \geq \mu \cdot z\f$ (or NULL if not existent) */
214 SCIP_VAR* ubboundvar; /**< bound variable @p z from constraint \f$x \leq \mu \cdot z\f$ (or NULL if not existent) */
215 SCIP_Real lbboundcoef; /**< value \f$\mu\f$ from constraint \f$x \geq \mu z \f$ (0.0 if not existent) */
216 SCIP_Real ubboundcoef; /**< value \f$\mu\f$ from constraint \f$x \leq \mu z \f$ (0.0 if not existent) */
217 SCIP_Bool lbboundcomp; /**< TRUE if the nodes from the connected component of the conflict graph the given node belongs to
219 SCIP_Bool ubboundcomp; /**< TRUE if the nodes from the connected component of the conflict graph the given node belongs to
245 int maxboundcuts; /**< maximal number of clique cuts separated per separation round (-1: no limit) */
246 SCIP_Bool strthenboundcuts; /**< if TRUE then bound cuts are strengthened in case bound variables are available */
247 };
252 {
256 SCIP_Bool isconflocal; /**< if TRUE then local conflicts are present and conflict graph has to be updated for each node */
260 int maxsosadjacency; /**< do not create an adjacency matrix if number of SOS1 variables is larger than predefined
263 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$) */
275 int maxextensions; /**< maximal number of extensions that will be computed for each SOS1 constraint */
276 int maxtightenbds; /**< maximal number of bound tightening rounds per presolving round (-1: no limit) */
277 SCIP_Bool perfimplanalysis; /**< if TRUE then perform implication graph analysis (might add additional SOS1 constraints) */
278 int depthimplanalysis; /**< number of recursive calls of implication graph analysis (-1: no limit) */
284 char branchingrule; /**< which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique)
286 SCIP_Bool autosos1branch; /**< if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap */
287 SCIP_Bool fixnonzero; /**< if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the
289 SCIP_Bool addcomps; /**< if TRUE then add complementarity constraints to the branching nodes additionally to domain fixings
291 int maxaddcomps; /**< maximal number of complementarity cons. and cor. bound ineq. added per branching node (-1: no limit) */
292 int addcompsdepth; /**< only add complementarity constraints to branching nodes for predefined depth (-1: no limit) */
293 SCIP_Real addcompsfeas; /**< minimal feasibility value for complementarity constraints in order to be added to the branching node */
294 SCIP_Real addbdsfeas; /**< minimal feasibility value for bound inequalities in order to be added to the branching node */
295 SCIP_Bool addextendedbds; /**< should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities */
296 SCIP_Bool branchsos; /**< Branch on SOS condition in enforcing? This value can only be set to false if all SOS1 variables are binary */
298 SCIP_Bool branchweight; /**< Branch on SOS cons. with highest nonzero-variable weight for branching - needs branchnonzeros to be false */
301 int nstrongrounds; /**< maximal number of strong branching rounds to perform for each node (-1: auto)
303 int nstrongiter; /**< maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) */
306 SCIP_Bool boundcutsfromgraph; /**< if TRUE separate bound inequalities from the conflict graph */
307 SCIP_Bool autocutsfromsos1; /**< if TRUE then automatically switch to separating SOS1 constraints if the SOS1 constraints do not overlap */
308 SCIP_Bool switchcutsfromsos1; /**< whether to switch to separate bound inequalities from SOS1 constraints */
309 int boundcutsfreq; /**< frequency for separating bound cuts; zero means to separate only in the root node */
312 int maxboundcutsroot; /**< maximal number of bound cuts separated per iteration in the root node */
314 SCIP_Bool strthenboundcuts; /**< if TRUE then bound cuts are strengthened in case bound variables are available */
315 int implcutsfreq; /**< frequency for separating implied bound cuts; zero means to separate only in the root node */
318 int maximplcutsroot; /**< maximal number of implied bound cuts separated per iteration in the root node */
330 SCIP_Bool** adjacencymatrix, /**< adjacency matrix of conflict graph (lower half) (or NULL if an adjacencymatrix is not at hand) */
335 {
387 /** checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable */
395 {
407 /* check whether variable is nonzero w.r.t. sol and the bounds have not been fixed to zero by propagation */
408 if ( ! SCIPisFeasZero(scip, solval) && ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) )
423 if ( ! SCIPisFeasZero(scip, solval) && ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) )
432 /** returns solution value of imaginary binary big-M variable of a given node from the conflict graph */
440 {
482 /** gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph */
490 {
509 /** gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph */
517 {
582 {
585 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
599 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
601 SCIPdebugMsg(scip, "creating constraint to force multi-aggregated variable <%s> to 0.\n", SCIPvarGetName(var));
603 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "branch", 1, &var, &val, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
623 * Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
627 * 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$
628 * are nonnegative if \f$\alpha_i > 0\f$ or the upper bounds are nonpositive if \f$\alpha_i < 0\f$.
637 {
668 if ( (SCIPisPositive(scip, aggrvals[i]) && SCIPisNegative(scip, SCIPvarGetLbLocal(aggrvars[i]))) ||
712 SCIP_Bool* success /**< whether fixing was successful, i.e., variable is not multi-aggregated */
720 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
779 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)),
794 {
845 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
856 if ( consdata->rowub != NULL && ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) && ! SCIPisZero(scip, SCIPvarGetUbGlobal(var)) )
862 if ( consdata->rowlb != NULL && ! SCIPisInfinity(scip, SCIPvarGetLbGlobal(var)) && ! SCIPisZero(scip, SCIPvarGetLbGlobal(var)) )
879 /* variable does not appear in the conflict graph: switch to SOS1 branching rule, which does not make use of a conflict graph
881 SCIPdebugMsg(scip, "Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
886 /* if the constraint is local, then there is no need to act, since local constraints are handled by the local conflict graph in the
924 SCIPdebugMsg(scip, "Added new conflict graph arc from variable %s to variable %s.\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]));
925 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, node), SCIPdigraphGetNSuccessors(conflictgraph, node));
930 SCIPdebugMsg(scip, "Added new conflict graph arc from variable %s to variable %s.\n", SCIPvarGetName(vars[v]), SCIPvarGetName(var));
931 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, nodev), SCIPdigraphGetNSuccessors(conflictgraph, nodev));
936 /* variable does not appear in the conflict graph: switch to SOS1 branching rule, which does not make use of a conflict graph
938 SCIPdebugMsg(scip, "Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
957 )
973 SCIPerrorMessage("cannot add variable to SOS1 constraint <%s> that does not contain weights.\n", SCIPconsGetName(cons));
1027 {
1085 )
1095 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); /*lint !e740*/
1115 * Algorithm 457: Finding all Cliques of an Undirected Graph, Bron & Kerbosch, Commun. ACM, 1973
1121 SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of the conflict graph (only lower half filled) */
1122 SCIP_DIGRAPH* vertexcliquegraph, /**< graph that contains the information which cliques contain a given vertex
1123 * vertices of variables = 0, ..., nsos1vars-1; vertices of cliques = nsos1vars, ..., nsos1vars+ncliques-1*/
1135 int* workingset, /**< set of vertices that already served as extension and set of candidates that probably will lead to an extension */
1199 if ( vertex != workingset[j] && ! isConnectedSOS1(adjacencymatrix, NULL, vertex, workingset[j]) )
1228 /* If fixed point is initially chosen from candidates then number of disconnections will be preincreased by one. */
1270 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(cliques[*ncliques]), cliquesizes[*ncliques]) );/*lint !e866*/
1295 /* add arc from clique vertex to clique (needed in presolRoundConssSOS1() to delete redundand cliques) */
1305 cliquesizes[*ncliques] = cliquesizes[*ncliques-1]; /* cliquesizes[*ncliques] = size of newclique */
1322 SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights, FALSE, usebacktrack,
1323 cliques, ncliques, cliquesizes, newclique, workingsetnew, nworkingsetnew, nextsnew, pos, maxextensions, naddconss, success) );
1341 SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights, FALSE, usebacktrack,
1342 cliques, ncliques, cliquesizes, newclique, workingset, nworkingset, nextsnew, pos, maxextensions, naddconss, success) );
1381 SCIP_DIGRAPH* conflictgraphlin, /**< conflict graph of linear constraint (nodes: 1, ..., nlinvars) */
1385 int* posinlinvars /**< posinlinvars[i] = position (index) of SOS1 variable i in linear constraint,
1386 * posinlinvars[i]= -1 if @p i is not a SOS1 variable or not a variable of the linear constraint */
1401 for (v = 1; v < nlinvars; ++v) /* we start with v = 1, since "indexinlinvars < v" (see below) is never fulfilled for v = 0 */
1531 /** get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero */
1537 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$) */
1539 SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
1575 if ( sos1node >= 0 && ! implnodes[sos1node] && ( SCIPisFeasPositive(scip, data->lbimpl) || SCIPisFeasNegative(scip, data->ubimpl) ) )
1579 SCIP_CALL( getSOS1Implications(scip, conshdlrdata, vars, implgraph, implhash, implnodes, succnode) );
1664 SCIPdebugMsg(scip, "substituted variable <%s> by <%s>.\n", SCIPvarGetName(vars[j]), SCIPvarGetName(var));
1665 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[j], EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); /*lint !e740*/
1666 SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) ); /*lint !e740*/
1682 SCIPdebugMsg(scip, "variable <%s> appears twice in constraint, fixing it to 0.\n", SCIPvarGetName(vars[j]));
1726 SCIPdebugMsg(scip, "Deleting SOS1 constraint <%s> with < 2 variables.\n", SCIPconsGetName(cons));
1739 SCIPdebugMsg(scip, "The problem is infeasible: more than one variable has bounds that keep it from being 0.\n");
1766 SCIPdebugMsg(scip, "Deleting redundant SOS1 constraint <%s> with one variable.\n", SCIPconsGetName(cons));
1774 /* note: there is no need to update consdata->nfixednonzeros, since the constraint is deleted as soon nfixednonzeros > 0. */
1783 SCIP_CALL( SCIPcreateConsSetpack(scip, &setpackcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars,
1784 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons),
1785 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons),
1790 SCIPdebugMsg(scip, "Upgrading SOS1 constraint <%s> to set packing constraint.\n", SCIPconsGetName(cons));
1880 /* Use block memory for cliques, because sizes might be quite different and allocation interfers with workingset. */
1928 SCIP_CALL( presolRoundConsSOS1(scip, cons, consdata, eventhdlr, &substituted, &cutoff, &success, ndelconss, nupgdconss, nfixedvars, nremovedvars) );
2031 SCIP_CALL( cliqueGetCommonSuccessorsSOS1(conshdlrdata, conflictgraph, newclique, vars, nvars, comsucc, &ncomsucc) );
2036 SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, consvars, consweights,
2037 TRUE, (maxextensions <= 1) ? FALSE : TRUE, cliques, &ncliques, cliquesizes, newclique, comsucc, ncomsucc, 0, -1, &maxextensions,
2093 * - adds (possibly new) complementarity constraints to the problem if variables are implied to be zero
2094 * - returns that the subproblem is infeasible if the domain of a variable turns out to be empty
2102 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$) */
2104 SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of the conflict graph (only lower half filled) */
2106 int nonznode, /**< node of the conflict graph that is implied to be nonzero if given node is nonzero */
2107 SCIP_Real* impllbs, /**< current lower variable bounds if given node is nonzero (update possible) */
2108 SCIP_Real* implubs, /**< current upper variable bounds if given node is nonzero (update possible) */
2109 SCIP_Bool* implnodes, /**< indicates which variables are currently implied to be nonzero if given node is nonzero (update possible) */
2112 SCIP_Bool* infeasible /**< pointer to store whether the subproblem gets infeasible if variable to 'nonznode' is nonzero */
2124 if ( conshdlrdata->depthimplanalysis >= 0 && *probingdepth >= conshdlrdata->depthimplanalysis )
2132 /* loop through neighbors of 'nonznode' in the conflict graph; these variables are implied to be zero */
2137 /* if the current variable domain of the successor node does not contain the value zero then return that the problem is infeasible
2138 * else if 'succnode' is not already complementary to 'givennode' then add a new complementarity constraint */
2139 if ( givennode == succnode || SCIPisFeasPositive(scip, impllbs[succnode]) || SCIPisFeasNegative(scip, implubs[succnode]) )
2160 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, givennode), SCIPdigraphGetNSuccessors(conflictgraph, givennode));
2161 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, succnode), SCIPdigraphGetNSuccessors(conflictgraph, succnode));
2174 (void) SCIPsnprintf(namesos, SCIP_MAXSTRLEN, "presolved_sos1_%s_%s", SCIPvarGetName(var1), SCIPvarGetName(var2) );
2175 SCIP_CALL( SCIPcreateConsSOS1(scip, &soscons, namesos, 0, NULL, NULL, TRUE, TRUE, TRUE, FALSE, TRUE,
2192 /* by construction: nodes of SOS1 variables are equal for conflict graph and implication graph */
2193 assert( nonznode == SCIPhashmapGetImageInt(implhash, SCIPnodeGetVarSOS1(conflictgraph, nonznode)) );
2213 /* if node is SOS1 and implied to be nonzero for the first time, then this recursively may imply further bound changes */
2214 if ( varGetNodeSOS1(conshdlrdata, totalvars[succnode]) >= 0 && ! implnodes[succnode] && SCIPisFeasPositive(scip, data->lbimpl) )
2216 /* by construction: nodes of SOS1 variables are equal for conflict graph and implication graph */
2217 assert( succnode == SCIPhashmapGetImageInt(implhash, SCIPnodeGetVarSOS1(conflictgraph, succnode)) );
2219 SCIP_CALL( performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2233 /* if node is SOS1 and implied to be nonzero for the first time, then this recursively may imply further bound changes */
2234 if ( varGetNodeSOS1(conshdlrdata, totalvars[succnode]) >= 0 && ! implnodes[succnode] && SCIPisFeasNegative(scip, data->ubimpl) )
2236 /* by construction: nodes of SOS1 variables are equal for conflict graph and implication graph */
2237 assert( succnode == SCIPhashmapGetImageInt(implhash, SCIPnodeGetVarSOS1(conflictgraph, succnode)) );
2239 SCIP_CALL( performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2253 /** returns whether node is implied to be zero; this information is taken from the input array 'implnodes' */
2257 SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2316 if ( ( lower && SCIPisFeasLT(scip, ub, newbound) ) || ( ! lower && SCIPisFeasGT(scip, lb, newbound) ) )
2328 SCIPdebugMsg(scip, "detected infeasibility while trying to fix variable <%s> to zero\n", SCIPvarGetName(varv));
2334 SCIPdebugMsg(scip, "fixed variable %s from lb = %f and ub = %f to 0.0 \n", SCIPvarGetName(varv), lb, ub);
2346 /* search for nodew in existing successors. If this is the case then check whether the lower implication bound may be updated ... */
2363 SCIPdebugMsg(scip, "updated to implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2373 SCIPdebugMsg(scip, "updated to implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2379 /* ..., otherwise if there does not exist an arc between indv and indw already, then create one and add implication */
2388 SCIPdebugMsg(scip, "add implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2394 SCIPdebugMsg(scip, "add implication %s != 0 -> %s <= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2406 * Assume the variable from the input is nonzero. If this implies that some other variable is also nonzero, then
2415 SCIP_DIGRAPH* implgraph, /**< implication graph (\f$j\f$ is successor of \f$i\f$ if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
2417 SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2428 SCIP_Real boundnonzero, /**< bound of variable if it is known to be nonzero if infinity values are not summarized */
2429 int ninftynonzero, /**< number of times infinity/-infinity has to be summarized to boundnonzero */
2444 nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
2446 /* 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 */
2462 /* variable should not be fixed to be already zero (note x_v is fixed to be nonzero by assumption) */
2463 if ( nodew < 0 || ( nodev != nodew && ! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodew) && ! isImpliedZero(conflictgraph, implnodes, nodew) ) )
2472 /* 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
2484 nodecliq = varGetNodeSOS1(conshdlrdata, vars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
2486 /* 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 */
2487 if ( nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
2491 if ( !SCIPisInfinity(scip, REALABS(bounds[w])) && !SCIPisInfinity(scip, REALABS(implbound + bounds[w])) )
2499 if ( SCIPisInfinity(scip, REALABS(bounds[indcliq])) || SCIPisInfinity(scip, REALABS(implbound - bounds[indcliq])) )
2539 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, TRUE, nchgbds, update, infeasible) );
2543 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, FALSE, nchgbds, update, infeasible) );
2550 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, FALSE, nchgbds, update, infeasible) );
2554 SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, TRUE, nchgbds, update, infeasible) );
2567 * For a given vertex v search for a clique of the conflict graph induced by the variables of a linear constraint that
2574 SCIP_DIGRAPH* conflictgraphroot, /**< conflict graph of the root node (nodes: 1, ..., nsos1vars) */
2575 SCIP_DIGRAPH* conflictgraphlin, /**< conflict graph of linear constraint (nodes: 1, ..., nlinvars) */
2577 SCIP_Bool* coveredvars, /**< states which variables of the linear constraint are currently covered by a clique */
2581 SCIP_Bool considersolvals /**< TRUE if largest auxiliary bigM values of variables should be prefered */
2633 /* search for the extension with the largest absolute value of its LP relaxation solution value */
2687 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$) */
2694 SCIP_Bool* implupdate, /**< pointer to store whether the implication graph has been updated in this function call */
2702 SCIP_Bool* implnodes = NULL; /* implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2703 SCIP_Bool* coveredvars = NULL; /* coveredvars[i] = TRUE if variable with index i is covered by the clique cover */
2704 int* varindincons = NULL; /* varindincons[i] = position of SOS1 index i in linear constraint (-1 if x_i is not involved in linear constraint) */
2706 SCIP_VAR** trafolinvars = NULL; /* variables of transformed linear constraints without (multi)aggregated variables */
2714 SCIP_VAR** sos1linvars = NULL; /* variables that are not contained in linear constraint, but are in conflict with a variable from the linear constraint */
2808 SCIP_CALL( SCIPgetProbvarLinearSum(scip, trafolinvars, trafolinvals, &ntrafolinvars, ntrafolinvars, &constant, &requiredsize, TRUE) );
2814 SCIP_CALL( SCIPgetProbvarLinearSum(scip, trafolinvars, trafolinvals, &ntrafolinvars, requiredsize, &constant, &requiredsize, TRUE) );
2851 if ( SCIPisInfinity(scip, REALABS(lb)) || SCIPisInfinity(scip, REALABS(lb * trafolinvals[v])) )
2856 if ( SCIPisInfinity(scip, REALABS(ub)) || SCIPisInfinity(scip, REALABS(ub * trafolinvals[v])) )
2879 SCIP_CALL( genConflictgraphLinearCons(conshdlrdata, conflictgraphlin, conflictgraph, trafolinvars, ntrafolinvars, varindincons) );
2897 SCIP_CALL( SCIPallocBufferArray(scip, &(cliquecovers[ncliquecovers]), ntrafolinvars) ); /*lint !e866*/
2898 SCIP_CALL( computeVarsCoverSOS1(scip, conflictgraph, conflictgraphlin, trafolinvars, coveredvars, cliquecovers[ncliquecovers], &(cliquecoversizes[ncliquecovers]), v, FALSE) );
2906 /* compute variables that are not contained in transformed linear constraint, but are in conflict with a variable from the transformed linear constraint */
2929 /* if variable is not a member of linear constraint and not already listed in the array sos1linvars */
2942 /* sort each cliquecover array in ascending order of the lower bounds of a_i * x_i; fill vector varincover */
2995 nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
3001 SCIP_CALL( getSOS1Implications(scip, conshdlrdata, totalvars, implgraph, implhash, implnodes, SCIPhashmapGetImageInt(implhash, var)) );
3014 /* determine maximum without index v (note that the array 'cliquecovers' is sorted by the values of trafoub in non-increasing order) */
3017 if ( SCIPisInfinity(scip, trafoubs[indcliq]) || SCIPisInfinity(scip, REALABS(newboundnores - trafoubs[indcliq])) )
3025 if ( SCIPisInfinity(scip, trafoubs[cliquecovers[i][1]]) || SCIPisInfinity(scip, REALABS(newboundnores - trafoubs[cliquecovers[i][1]])) )
3031 /* determine maximum without index v and if x_v is nonzero (note that the array 'cliquecovers' is sorted by the values of trafoub in non-increasing order) */
3037 nodecliq = varGetNodeSOS1(conshdlrdata, trafolinvars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
3042 /* 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 */
3043 if ( nodev < 0 || nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
3045 if ( SCIPisInfinity(scip, trafoubs[indcliq]) || SCIPisInfinity(scip, REALABS(newboundnonzero - trafoubs[indcliq])) )
3049 break; /* break since we are only interested in the maximum upper bound among the variables in the clique cover;
3050 * the variables in the clique cover form an SOS1 constraint, thus only one of them can be nonzero */
3092 SCIPdebugMsg(scip, "changed lower bound of variable %s from %f to %f \n", SCIPvarGetName(var), lb, newbound);
3113 SCIPdebugMsg(scip, "changed upper bound of variable %s from %f to %f \n", SCIPvarGetName(var), ub, newbound);
3120 SCIP_CALL( updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3121 trafolinvars, trafolinvals, ntrafolinvars, trafoubs, var, trafoubv, newboundnonzero, ninftynonzero, TRUE, nchgbds, &update, &infeasible) );
3144 /* sort each cliquecover array in ascending order of the lower bounds of a_i * x_i; fill vector varincover */
3157 /* for every variable that is in transformed constraint or every variable that is in conflict with some variable from trans. cons.:
3195 nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
3198 /* determine incidence vector of implication variables (i.e., which SOS1 variables are nonzero if x_v is nonzero) */
3201 SCIP_CALL( getSOS1Implications(scip, conshdlrdata, totalvars, implgraph, implhash, implnodes, SCIPhashmapGetImageInt(implhash, var)) );
3214 /* determine minimum without index v (note that the array 'cliquecovers' is sorted by the values of trafolb in increasing order) */
3218 if ( SCIPisInfinity(scip, -trafolbs[indcliq]) || SCIPisInfinity(scip, REALABS(newboundnores - trafolbs[indcliq])) )
3226 if ( SCIPisInfinity(scip, -trafolbs[cliquecovers[i][1]]) || SCIPisInfinity(scip, REALABS(newboundnores - trafolbs[cliquecovers[i][1]])) )
3232 /* determine minimum without index v and if x_v is nonzero (note that the array 'cliquecovers' is sorted by the values of trafolb in increasing order) */
3238 nodecliq = varGetNodeSOS1(conshdlrdata, trafolinvars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
3243 /* 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 */
3244 if ( nodev < 0 || nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
3247 if ( SCIPisInfinity(scip, -trafolbs[indcliq]) || SCIPisInfinity(scip, REALABS(newboundnonzero - trafolbs[indcliq])) )
3251 break; /* break since we are only interested in the minimum lower bound among the variables in the clique cover;
3252 * the variables in the clique cover form an SOS1 constraint, thus only one of them can be nonzero */
3295 SCIPdebugMsg(scip, "changed upper bound of variable %s from %f to %f \n", SCIPvarGetName(var), ub, newbound);
3316 SCIPdebugMsg(scip, "changed lower bound of variable %s from %f to %f \n", SCIPvarGetName(var), lb, newbound);
3323 SCIP_CALL( updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3324 trafolinvars, trafolinvals, ntrafolinvars, trafolbs, var, trafolbv, newboundnonzero, ninftynonzero, FALSE, nchgbds, &update, &infeasible) );
3426 for (j = 0; (j < conshdlrdata->maxtightenbds || conshdlrdata->maxtightenbds == -1 ) && ! cutoff; ++j)
3434 SCIP_CALL( tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, implgraph, implhash, adjacencymatrix, totalvars, ntotalvars, nsos1vars, nchgbds, &implupdate, &cutoff) );
3478 SCIP_CALL( performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, i, i, impllbs, implubs, implnodes, naddconss, &probingdepth, &infeasible) );
3488 SCIPvarGetName(totalvars[i]), SCIPvarGetLbLocal(totalvars[i]), SCIPvarGetUbLocal(totalvars[i]));
3544 )
3583 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) )
3591 SCIPdebugMsg(scip, "variable <%s> is fixed nonzero, fixing other variables to 0.\n", SCIPvarGetName(vars[firstFixedNonzero]));
3598 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
3609 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
3610 assert( ! infeasible ); /* there should be no variables after firstFixedNonzero that are fixed to be nonzero */
3662 assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(SCIPnodeGetVarSOS1(conflictgraph, node))) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(SCIPnodeGetVarSOS1(conflictgraph, node))) );
3684 SCIP_CALL( inferVariableZero(scip, succvar, cons, inferinfo, &infeasible, &tightened, &success) );
3738 SCIP_CALL( SCIPinferVarLbCons(scip, var, succdata->lbimpl, cons, inferinfo, FALSE, &infeasible, &tightened) );
3754 SCIP_CALL( SCIPinferVarUbCons(scip, var, succdata->ubimpl, cons, inferinfo, FALSE, &infeasible, &tightened) );
3811 /* we do not create the adjacency matrix of the conflict graph if the number of SOS1 variables is larger than a predefined value */
3815 SCIPdebugMsg(scip, "Implication graph was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
3835 * Note: For separation of implied bound cuts it is important that SOS1 variables are enumerated first
3917 SCIP_CALL( tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->implgraph, implhash, adjacencymatrix, implvars, nimplnodes, nsos1vars, nchgbds, &implupdate, cutoff) );
4004 /** get the vertices whose neighbor set covers a subset of the neighbor set of a given other vertex.
4011 SCIP_Bool* verticesarefixed, /**< array that indicates which variables are currently fixed to zero */
4013 int* neightocover, /**< neighbors of given vertex to be covered (or NULL if all neighbors shall be covered) */
4014 int nneightocover, /**< number of entries of neightocover (or 0 if all neighbors shall be covered )*/
4015 int* coververtices, /**< array to store the vertices whose neighbor set covers the neighbor set of the given vertex */
4106 assert( *ncoververtices <= 1 || coververtices[*ncoververtices - 1] > coververtices[*ncoververtices - 2] );
4120 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4125 int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the second node */
4129 SCIP_Bool takeallsucc; /* whether to set fixingsnode1 = neighbors of 'branchvertex' in the conflict graph */
4157 /* get all the neighbors of the variable with index 'branchvertex' whose solution value is nonzero */
4160 if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, succ[j]))) )
4167 /* if one of the sets fixingsnode1 or fixingsnode2 contains only one variable with a nonzero LP value we perform standard neighborhood branching */
4170 /* get the vertices whose neighbor set cover the selected subset of the neighbors of the given branching vertex */
4171 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4173 /* determine the intersection of the neighbors of branchvertex with the intersection of all the neighbors of fixingsnode2 */
4174 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode2, *nfixingsnode2, fixingsnode1, nfixingsnode1) );
4183 /* we decide whether to use all successors if one partition of complete bipartite subgraph has only one node */
4213 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4217 /* use neighborhood branching, i.e, for the second node only the branching vertex can be fixed */
4227 /** gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision */
4235 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4237 int* fixingsnode1, /**< vertices of variables that will be fixed to zero for the first node (size = nsos1vars) */
4238 int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the second node (size = nsos1vars) */
4239 SCIP_Real* branchpriors, /**< pointer to store branching priorities (size = nsos1vars) or NULL if not needed */
4240 int* vertexbestprior, /**< pointer to store vertex with the best branching priority or NULL if not needed */
4272 if ( nsucc == 0 || SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, i))) || verticesarefixed[i] )
4283 SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, i, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4336 int* fixingsexec, /**< vertices of variables to be fixed to zero for this strong branching execution */
4337 int nfixingsexec, /**< number of vertices of variables to be fixed to zero for this strong branching execution */
4338 int* fixingsop, /**< vertices of variables to be fixed to zero for the opposite strong branching execution */
4339 int nfixingsop, /**< number of vertices of variables to be fixed to zero for the opposite strong branching execution */
4341 SCIP_Bool fixnonzero, /**< shall opposite variable (if positive in sign) fixed to the feasibility tolerance
4343 int* domainfixings, /**< vertices that can be used to reduce the domain (should have size equal to number of variables) */
4344 int* ndomainfixings, /**< pointer to store number of vertices that can be used to reduce the domain, could be filled by earlier calls */
4346 SCIP_Real* objval, /**< pointer to store objective value of LP with fixed variables (SCIP_INVALID if reddomain = TRUE or lperror = TRUE) */
4347 SCIP_Bool* lperror /**< pointer to store whether an unresolved LP error or a strange solution status occurred */
4401 /* fix variable to some negative number with small absolute value or to -1.0 if variable is integral */
4420 if ( SCIPisFeasGT(scip, SCIPvarGetLbLocal(var), 0.0) || SCIPisFeasLT(scip, SCIPvarGetUbLocal(var), 0.0) )
4458 else if ( solstat == SCIP_LPSOLSTAT_OPTIMAL || solstat == SCIP_LPSOLSTAT_TIMELIMIT || solstat == SCIP_LPSOLSTAT_ITERLIMIT )
4484 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4485 int* fixingsnode1, /**< pointer to store vertices of variables that will be fixed to zero for the first node (size = nsos1vars) */
4486 int* fixingsnode2, /**< pointer to store vertices of variables that will be fixed to zero for the second node (size = nsos1vars) */
4488 SCIP_Real* bestobjval1, /**< pointer to store LP objective for left child node of branching decision with best priority */
4489 SCIP_Real* bestobjval2, /**< pointer to store LP objective for right child node of branching decision with best priority */
4524 SCIP_CALL( getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, verticesarefixed,
4596 /* if variable with index 'vertex' does not violate any complementarity in its neighborhood for the current LP relaxation solution */
4608 SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, testvertex,
4612 SCIP_CALL( performStrongbranchSOS1(scip, conflictgraph, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2,
4613 inititer, conshdlrdata->fixnonzero, domainfixings, &ndomainfixings, &infeasible1, &objval1, &lperror) );
4618 SCIP_CALL( performStrongbranchSOS1(scip, conflictgraph, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1,
4643 score = MAX( REALABS(objval1 - lpobjval), SCIPfeastol(scip) ) * MAX( REALABS(objval2 - lpobjval), SCIPfeastol(scip) );/*lint !e666*/
4669 SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, domainfixings[i]), node, &infeasible) );
4688 /** for two given vertices @p v1 and @p v2 search for a clique in the conflict graph that contains these vertices. From
4699 SCIP_Bool extend, /**< should @p v1 and @p v2 be greedily extended to a clique of larger size */
4814 else /* search for the extension with the largest absolute value of its LP relaxation solution value */
4917 * @note In this function the conflict graph is updated to the conflict graph of the considered child branching node.
4925 SCIP_DIGRAPH* localconflicts, /**< local conflicts (updates to local conflicts of child node) */
4928 SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zerox */
4929 int* fixingsnode1, /**< vertices of variables that will be fixed to zero for the branching node in the input of this function */
4931 int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the other branching node */
4934 SCIP_Bool onlyviolsos1 /**< should only SOS1 constraints be added that are violated by the LP solution */
4955 int* coverarray; /* vertices, not in fixingsnode1 that cover all the vertices in array fixingsnode22 */
4980 assert( nfixingsnode1 <= 1 || (fixingsnode1[nfixingsnode1 - 1] > fixingsnode1[nfixingsnode1 - 2]) ); /* test: vertices are sorted */
4987 assert( nfixingsnode2 <= 1 || (fixingsnode2[nfixingsnode2 - 1] > fixingsnode2[nfixingsnode2 - 2]) ); /* test: vertices are sorted */
4991 /* 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 */
5036 /* compute first partition of fixingsnode2 that is the intersection of the neighbors of 'vertex1' with the set fixingsnode2 */
5046 assert( nfixingsnode21 == 1 || (fixingsnode21[nfixingsnode21 - 1] > fixingsnode21[nfixingsnode21 - 2]) ); /* test: successor vertices are sorted */
5061 SCIPcomputeArraysSetminusInt(fixingsnode2, nfixingsnode2, fixingsnode21, nfixingsnode21, fixingsnode22, &nfixingsnode22);
5064 /* compute cover set (that are all the vertices not in fixingsnode1 and fixingsnode21, whose neighborhood covers all the vertices of fixingsnode22) */
5065 SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, -1, fixingsnode22, nfixingsnode22, coverarray, &ncoverarray) );
5066 SCIPcomputeArraysSetminusInt(coverarray, ncoverarray, fixingsnode1, nfixingsnode1, coverarray, &ncoverarray);
5067 SCIPcomputeArraysSetminusInt(coverarray, ncoverarray, fixingsnode21, nfixingsnode21, coverarray, &ncoverarray);
5132 SCIPsortInt(SCIPdigraphGetSuccessors(localconflicts, vertex1), SCIPdigraphGetNSuccessors(localconflicts, vertex1));
5133 SCIPsortInt(SCIPdigraphGetSuccessors(localconflicts, vertex2), SCIPdigraphGetNSuccessors(localconflicts, vertex2));
5134 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, vertex1), SCIPdigraphGetNSuccessors(conflictgraph, vertex1));
5135 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, vertex2), SCIPdigraphGetNSuccessors(conflictgraph, vertex2));
5137 /* mark conflictgraph as not local such that the new arcs are deleted after currents node processing */
5205 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sos1_branchnode_%" SCIP_LONGINT_FORMAT "_no_%i", SCIPnodeGetNumber(node), *naddedconss);
5206 SCIP_CALL( SCIPcreateConsSOS1(scip, &conssos1, name, 0, NULL, NULL, TRUE, TRUE, TRUE, FALSE, TRUE,
5224 /* 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.
5225 * 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. */
5226 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "boundcons_branchnode_%" SCIP_LONGINT_FORMAT "_no_%i", SCIPnodeGetNumber(node), *naddedconss);
5230 SCIP_CALL( SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -SCIPinfinity(scip), 0.0, TRUE, FALSE, TRUE, FALSE, FALSE,
5234 SCIP_CALL( getBoundConsFromVertices(scip, conflictgraph, sol, vertex1, vertex2, boundvar1, conshdlrdata->addextendedbds, conssos1, &feas) );
5239 SCIP_CALL( SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -SCIPinfinity(scip), 1.0, TRUE, FALSE, TRUE, FALSE, FALSE,
5243 SCIP_CALL( getBoundConsFromVertices(scip, conflictgraph, sol, vertex1, vertex2, NULL, conshdlrdata->addextendedbds, conssos1, &feas) );
5286 SCIP_DIGRAPH* localconflicts, /**< local conflicts that should be removed from conflict graph */
5323 * - 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
5326 * - Branch on complete bipartite subgraphs of the conflict graph, i.e., in one branch fix the variables from the first
5329 * - In addition to variable domain fixings, it is sometimes also possible to add new SOS1 constraints to the branching
5330 * nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.
5332 * We make use of different selection rules that define on which system of SOS1 variables to branch next:
5336 * - Strong branching: Here, the LP-relaxation is partially solved for each branching decision among a candidate list.
5413 /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
5419 SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen);
5457 if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
5467 if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
5496 SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, j), SCIPdigraphGetNSuccessors(conflictgraph, j));
5541 nstrongrounds = MAX(10, (int)SCIPfloor(scip, pow(log((SCIP_Real)nsos1vars), 1.0)));/*lint !e666*/
5543 nstrongrounds = MAX(5, (int)SCIPfloor(scip, pow(log((SCIP_Real)nsos1vars), 0.7)));/*lint !e666*/
5562 SCIP_CALL( getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, verticesarefixed,
5591 SCIP_CALL( getBranchingDecisionStrongbranchSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, lpobjval,
5592 bipbranch, nstrongrounds, verticesarefixed, fixingsnode1, fixingsnode2, &branchvertex, &bestobjval1,
5636 SCIPerrorMessage("Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5646 SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, branchvertex,
5694 /* fix variable to some negative number with small absolute value to -1.0 if variable is integral */
5699 /* fix variable to some negative number with small absolute value to -1.0 if variable is integral */
5709 SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode1[j]), node1, &infeasible) );
5732 SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode2[j]), node2, &infeasible) );
5737 if ( conshdlrdata->addcomps && ( conshdlrdata->addcompsdepth == -1 || conshdlrdata->addcompsdepth >= SCIPgetDepth(scip) ) )
5744 SCIP_CALL( addBranchingComplementaritiesSOS1(scip, node1, conshdlrdata, conflictgraph, conshdlrdata->localconflicts, sol,
5745 nsos1vars, verticesarefixed, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2, &naddedconss, TRUE) );
5750 SCIP_CALL( addBranchingComplementaritiesSOS1(scip, node2, conshdlrdata, conflictgraph, conshdlrdata->localconflicts, sol,
5751 nsos1vars, verticesarefixed, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1, &naddedconss, TRUE) );
5796 * Depending on the parameters (@c branchnonzeros, @c branchweight) there are three ways to choose
5802 * <TR><TD>@c false </TD><TD> @c true </TD><TD>maximal weight corresponding to nonzero variable</TD></TR>
5806 * @c branchnonzeros = @c false, @c branchweight = @c true allows the user to specify an order for
5866 /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
5872 SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen);
5943 SCIPerrorMessage("Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5949 SCIPdebugMsg(scip, "Branching on constraint <%s> (weight: %f).\n", SCIPconsGetName(branchCons), maxWeight);
5960 assert( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[0])) && ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[1])) );
5965 SCIP_CALL( SCIPcreateChild(scip, &node1, SCIPcalcNodeselPriority(scip, vars[0], SCIP_BRANCHDIR_DOWNWARDS, 0.0), SCIPcalcChildEstimate(scip, vars[0], 0.0) ) );
5969 SCIP_CALL( SCIPcreateChild(scip, &node2, SCIPcalcNodeselPriority(scip, vars[1], SCIP_BRANCHDIR_DOWNWARDS, 0.0), SCIPcalcChildEstimate(scip, vars[1], 0.0) ) );
6010 /* branch on variable ind: either all variables up to ind or all variables after ind are zero */
6018 objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0);
6036 objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0);
6084 if ( conshdlrdata->fixnonzero && ( conshdlrdata->branchingrule == 'b' || conshdlrdata->branchingrule == 's' ) )
6086 SCIPerrorMessage("Incompatible parameter setting: nonzero fixing is not compatible with bipartite or sos1 branching.\n");
6127 )
6312 * 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
6313 * the variables \f$x_1, \ldots, x_n\f$. If an upper bound < 0 or a lower bound > 0, the constraint itself is
6314 * redundant, so the cut is not applied (lower bounds > 0 and upper bounds < 0 are usually detected in presolving or
6315 * propagation). Infinite bounds and zero are skipped. Thus \f$\ell_1, \ldots, \ell_n\f$ are all negative, which
6316 * results in the \f$\leq\f$ inequality. In case of the presence of variable upper bounds, the bound inequality can
6319 * Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as
6320 * above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most
6331 SCIP_Bool local, /**< in any case produce a local cut (even if local bounds of variables are valid globally) */
6334 SCIP_Bool removable, /**< should the inequality be removed from the LP due to aging or cleanup? */
6365 /* Loop through all variables. We check whether all bound variables (if existent) are equal; if this is the
6423 /* should not apply the cut if a variable is fixed to be negative -> constraint is redundant */
6464 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, rowub, conshdlr, name, -SCIPinfinity(scip), 0.0, localubs, FALSE, removable) );
6472 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, rowub, conshdlr, name, -SCIPinfinity(scip), rhs, localubs, FALSE, removable) );
6486 /* loop through all variables. We check whether all bound variables (if existent) are equal; if this is the
6546 /* should not apply the cut if a variable is fixed to be positive -> constraint is redundant */
6587 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, rowlb, conshdlr, name, -SCIPinfinity(scip), 0.0, locallbs, FALSE, TRUE) );
6595 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, rowlb, conshdlr, name, -SCIPinfinity(scip), rhs, locallbs, FALSE, TRUE) );
6622 /* we don't accept the solution as new incumbent, because we want to find many violated clique inequalities */
6689 if ( generateBoundInequalityFromSOS1Nodes(scip, tcliquedata->conshdlr, tcliquedata->conflictgraph,
6690 cliquenodes, ncliquenodes, 1.0, FALSE, FALSE, tcliquedata->strthenboundcuts, FALSE, nameext, &rowlb, &rowub) != SCIP_OKAY )
6729 /* if we found more than half the cuts we are allowed to generate, we accept the clique as new incumbent,
6754 int maxboundcuts, /**< maximal number of bound cuts separated per separation round (-1: no limit) */
6767 int maxzeroextensions = 1000; /* maximal number of zero-valued variables extending the clique (-1: no limit) */
6768 int backtrackfreq = 1000; /* frequency for premature backtracking up to tree level 1 (0: no backtracking) */
6794 SCIP_CALL( updateWeightsTCliquegraph(scip, conshdlrdata, tcliquedata, conflictgraph, sol, nsos1vars) );
6821 /** Generate a bound constraint from the variables of an SOS1 constraint (see generateBoundInequalityFromSOS1Nodes() for more information) */
6827 SCIP_Bool local, /**< in any case produce a local cut (even if local bounds of variables are valid globally) */
6830 SCIP_Bool removable, /**< should the inequality be removed from the LP due to aging or cleanup? */
6863 if ( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(consdata->vars[j])) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(consdata->vars[j])) )
6873 SCIP_CALL( generateBoundInequalityFromSOS1Nodes(scip, conshdlr, conshdlrdata->conflictgraph, nodes, cnt, 1.0, local, global,
6894 int maxboundcuts, /**< maximal number of bound cuts separated per separation round (-1: no limit) */
6922 SCIPdebugMsg(scip, "Separating inequalities for SOS1 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
6926 SCIPdebugMsg(scip, "Checking for initial rows for SOS1 constraint <%s>.\n", SCIPconsGetName(conss[c]) );
6929 /* in case that the SOS1 constraint is local, we always generate new rows - the former rows might be invalid;
6933 SCIP_CALL( generateBoundInequalityFromSOS1Cons(scip, conshdlr, conss[c], TRUE, FALSE, TRUE, FALSE, &rowlb, &rowub) );
6940 SCIP_CALL( generateBoundInequalityFromSOS1Cons(scip, conshdlr, conss[c], FALSE, TRUE, TRUE, FALSE,
6949 if ( rowub != NULL && ! SCIProwIsInLP(rowub) && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, rowub) ) )
6961 if ( ! (*cutoff) && rowlb != NULL && ! SCIProwIsInLP(rowlb) && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, rowlb) ) )
7005 int maxcuts, /**< maximal number of implied bound cuts separated per separation round (-1: no limit) */
7039 SCIP_CALL( initImplGraphSOS1(scip, conshdlrdata, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, cutoff, &success) );
7159 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &cut, conshdlr, "", -SCIPinfinity(scip), lhsrhs, FALSE, FALSE, TRUE) );
7168 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &cut, conshdlr, "", lhsrhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
7195 SCIPdebugMsg(scip, "added cut for implication %s != 0 -> %s >= %f \n", SCIPvarGetName(var), SCIPvarGetName(succvar), succdata->lbimpl);
7199 SCIPdebugMsg(scip, "added cut for implication %s != 0 -> %s <= %f \n", SCIPvarGetName(var), SCIPvarGetName(succvar), succdata->ubimpl);
7262 ( (conshdlrdata->boundcutsfreq == 0 && depth == 0) || (conshdlrdata->boundcutsfreq > 0 && depth % conshdlrdata->boundcutsfreq == 0)) )
7280 SCIP_CALL( initsepaBoundInequalityFromSOS1Cons(scip, conshdlr, conshdlrdata, conss, nconss, sol, TRUE, maxboundcuts, &ngen, &cutoff) );
7292 SCIP_CALL( sepaBoundInequalitiesFromGraph(scip, conshdlr, conshdlrdata, sol, maxboundcuts, &ngen, &cutoff) );
7309 ( (conshdlrdata->implcutsfreq == 0 && depth == 0) || (conshdlrdata->implcutsfreq > 0 && depth % conshdlrdata->implcutsfreq == 0)) )
7324 SCIP_CALL( sepaImplBoundCutsSOS1(scip, conshdlr, conshdlrdata, sol, maximplcuts, &ngen, &cutoff) );
7344 /** gets weights determining an order of the variables in a heuristic for the maximum weighted independent set problem */
7351 SCIP_Bool* indicatorzero, /**< vector that indicates which variables are currently fixed to zero */
7352 SCIP_Real* weights /**< pointer to store weights determining the order of the variables (length = nsos1vars) */
7405 weights[i] = ( val + SCIPsumepsilon(scip) ) / ( sum * (SCIP_Real)nviols + SCIPsumepsilon(scip) );
7507 SCIP_CALL( markNeighborsMWISHeuristic(scip, conshdlr, conflictgraph, aggrnode, mark, indset, cnt, cutoff) );
7553 * by the algorithm GGWMIN of Shuichi Sakai, Mitsunori Togasaki and Koichi Yamazaki in "A note on greedy algorithms for the
7554 * maximum weighted independent set problem", Discrete Applied Mathematics. Here \f$x^*\f$ denotes the current LP
7555 * relaxation solution. Note that the solution of the MWIS is the indicator vector of an independent set.
7564 SCIP_Bool* indicatorzero, /**< vector that indicates which variables are currently fixed to zero */
7622 SCIP_CALL( markNeighborsMWISHeuristic(scip, conshdlr, conflictgraph, i, mark, indset, &k, &cutoff) );
7643 SCIP_CALL( markNeighborsMWISHeuristic(scip, conshdlr, conflictgraph, ind, mark, indset, &k, &cutoff) );
7659 /** based on solution values of the variables, fixes variables of the conflict graph to zero to turn all SOS1 constraints feasible
7661 * if the SOS1 constraints do not overlap, the method makeSOS1constraintsFeasible() may be faster
7670 )
7728 else if ( SCIPisFeasPositive(scip, lb) || SCIPisFeasNegative(scip, ub) ) /* if variable is fixed to be nonzero */
7742 SCIP_CALL( maxWeightIndSetHeuristic(scip, sol, conshdlr, conflictgraph, nsos1vars, indicatorzero, indset) );
7789 /** based on solution values of the variables, fixes variables of the SOS1 constraints to zero to turn these constraints feasible
7791 * if the SOS1 constraints overlap, the method makeSOS1constraintsFeasible() may result in better primal solutions
7800 )
7862 /* it is possible that the bounds were proagated to zero although the current solution value is nonzero
7869 else if ( SCIPisFeasPositive(scip, lb) || SCIPisFeasNegative(scip, ub) ) /* if variable is fixed to be nonzero */
7876 else if ( ! varisfixed && SCIPisFeasGT(scip, REALABS(SCIPgetSolVal(scip, sol, var)), REALABS(maxval)) ) /* search for variable with maximum solution value */
7924 /** determine a diving variables and boundchanges of diving variables by analyzing the conflict graph
7926 * if the SOS1 constraints do not overlap, the method getDiveBdChgsSOS1constraints() may be faster
7935 )
7961 /* check whether the variable violates an SOS1 constraint together with at least one other variable */
8000 SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_SOS1VARIABLE, var, solval, fracval,
8041 /* if the diving score voted for fixing the best variable to 0.0, we add this as the preferred bound change;
8044 assert( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(bestvar)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(bestvar)) );
8045 SCIP_CALL( SCIPaddDiveBoundChange(scip, bestvar, SCIP_BRANCHDIR_FIXED, 0.0, !bestvarfixneigh) );
8053 if ( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var)) )
8064 /** determine a diving variables and boundchanges of diving variables by analyzing the SOS1 constraints
8066 * if the SOS1 constraints overlap, the method getDiveBdChgsSOS1conflictgraph() may produce better results (e.g., due to more
8076 )
8119 /* check whether variable is nonzero w.r.t. sol and the bounds have not been fixed to zero by propagation */
8121 && (!SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || !SCIPisFeasZero(scip, SCIPvarGetUbLocal(var))) )
8139 SCIP_Bool fixcomp; /* whether to fix the complementary variables of the candidate in the SOS1 constraint to zero */
8146 /* check whether variable is nonzero w.r.t. sol and the bounds have not been fixed to zero by propagation */
8147 if ( ! SCIPisFeasZero(scip, solval) && ( ! SCIPisFeasZero(scip, lb) || ! SCIPisFeasZero(scip, ub) ) )
8176 SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_SOS1VARIABLE, var, solval, fracval,
8185 /* we always fix the complementary variables of the candidate in the SOS1 constraint to zero */
8221 /* if the diving score voted for fixing the best variable to 0.0, we add this as the preferred bound change;
8222 * otherwise, fixing the complementary variables of the candidate in the SOS1 constraint to 0.0 is the preferred bound change.
8224 assert( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(bestvar)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(bestvar)) );
8226 SCIP_CALL( SCIPaddDiveBoundChange(scip, bestvar, SCIP_BRANCHDIR_FIXED, 0.0, !bestvarfixcomp) );
8234 if ( var != bestvar && ( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var)) ) )
8247 /** 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$
8248 * for positive values \f$c, d\f$. If true, then add this information to the node data of the conflict graph.
8294 SCIPdebugMsg(scip, "detected variable bound constraint %s >= %f %s.\n", SCIPvarGetName(var0), val, SCIPvarGetName(var1));
8312 SCIPdebugMsg(scip, "detected variable bound constraint %s <= %f %s.\n", SCIPvarGetName(var0), val, SCIPvarGetName(var1));
8321 /** 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$,
8387 SCIP_CALL( passConComponentVarbound(scip, conflictgraph, succ[s], boundvar, checklb, processed, concomp, nconcomp, unique) );
8394 /** 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$
8395 * (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$).
8404 SCIP_Bool checklb /**< whether to check lower bound variable (else check upper bound variable) */
8406 {
8454 SCIP_CALL( passConComponentVarbound(scip, conflictgraph, succ[s], boundvar, checklb, processed, concomp, &nconcomp, &unique) );
8472 SCIPdebugMsg(scip, "Found a connected component of size <%i> with unique bound variable.\n", nconcomp);
8485 /** 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
8495 {
8560 /** switch to SOS1 branching and separating bound iniqualities from SOS1 constraints if the SOS1 constraints do not overlap */
8568 )
8597 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(vars[i])) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[i])) )
8609 assert( node >= 0 || ( SCIPisFeasZero(scip, SCIPvarGetLbLocal(vars[i])) && SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[i]))) );
8633 SCIPdebugMsg(scip, "Switched to separating bound cuts from SOS1 constraints (and not from the conflict graph), since the SOS1 constraints do not overlap\n");
8669 /* for each connected component of the conflict graph check whether all the variables correspond to a unique variable
8671 SCIP_CALL( checkConComponentsVarbound(scip, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, TRUE) );
8672 SCIP_CALL( checkConComponentsVarbound(scip, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, FALSE) );
8686 {
8687 SCIP_Bool* nodecreated; /* nodecreated[i] = TRUE if a node in the conflict graph is already created for index i
8734 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
8794 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
8834 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
8844 SCIP_CALL( SCIPdigraphAddArcSafe(conshdlrdata->conflictgraph, nodeorig[indi], nodeorig[indj], NULL) );
8845 SCIP_CALL( SCIPdigraphAddArcSafe(conshdlrdata->conflictgraph, nodeorig[indj], nodeorig[indi], NULL) );
8936 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
8949 /* free stack of variables fixed to nonzero (usually already freed in consExitsolSOS1 unless instance was solved during presolving) */
8950 SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->fixnonzerovars, conshdlrdata->maxnfixnonzerovars); /*lint !e737*/
8958 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
8987 SCIP_CALL( checkSwitchNonoverlappingSOS1Methods(scip, conshdlrdata, conshdlrdata->conflictgraph, conss, nconss) );
8991 SCIP_CALL( initTCliquegraph(scip, conshdlr, conshdlrdata, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars) );
8999 /* initialize stack of variables fixed to nonzero (memory may be already allocated in consTransSOS1()) */
9003 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->fixnonzerovars, conshdlrdata->maxnfixnonzerovars) );
9011 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
9066 SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->fixnonzerovars, conshdlrdata->maxnfixnonzerovars); /*lint !e737*/
9108 SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[j], EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr,
9170 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->fixnonzerovars, conshdlrdata->maxnfixnonzerovars) );
9188 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, sourcedata->weights, consdata->nvars) );
9199 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(consdata->vars[j])) )
9215 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[j], EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr,
9222 SCIPdebugMsg(scip, "constraint <%s> has %d variables fixed to be nonzero.\n", SCIPconsGetName(*targetcons),
9257 if( nconss > 0 && ( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 ) )
9285 /* we do not create the adjacency matrix of the conflict graph if the number of SOS1 variables is larger than a predefined value */
9318 SCIPdebugMsg(scip, "Adjacency matrix was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
9322 SCIP_CALL( presolRoundConssSOS1(scip, eventhdlr, conshdlrdata, conflictgraph, adjacencymatrix, conss, nconss, nsos1vars, naddconss, ndelconss, nupgdconss, nfixedvars, &nremovedvars, result) );
9329 SCIP_CALL( presolRoundVarsSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, nsos1vars, nfixedvars, nchgbds, naddconss, result) );
9343 SCIPdebug( SCIPdebugMsg(scip, "presolving fixed %d variables, changed %d bounds, removed %d variables, deleted %d constraints, and upgraded %d constraints.\n",
9344 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds, nremovedvars, *ndelconss - oldndelconss, *nupgdconss - oldnupgdconss); )
9350 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
9368 SCIP_CALL( initsepaBoundInequalityFromSOS1Cons(scip, conshdlr, conshdlrdata, conss, nconss, NULL, FALSE, -1, NULL, infeasible) );
9571 SCIP_CALL( initImplGraphSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, &cutoff, &success) );
9620 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
9624 SCIP_CALL( propVariableNonzero(scip, conflictgraph, implgraph, conss[0], node, conshdlrdata->implprop, &cutoff, &ngen) );
9690 SCIPdebugMsg(scip, "Propagation resolution method of SOS1 constraint <%s>.\n", SCIPconsGetName(cons));
9865 SCIP_CALL( SCIPduplicateBufferArray(sourcescip, &targetweights, sourceconsdata->weights, nvars) );
9874 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) );
9911 SCIP_CALL( SCIPcreateConsSOS1(scip, cons, name, 0, NULL, NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
10005 /** constraint method of constraint handler which returns the number of variables (if possible) */
10065 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <= SCIPgetNTotalVars(scip) );
10087 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <= SCIPgetNTotalVars(scip) );
10141 SCIPdebugMsg(scip, "changed bound of variable <%s> from %f to %f (nfixednonzeros: %d).\n", SCIPvarGetName(SCIPeventGetVar(event)),
10148 /** constraint handler method to determine a diving variable by assigning a variable and two values for diving */
10172 /* if the SOS1 constraints do not overlap, we apply a faster method getDiveBdChgsSOS1constraints() that does not make use of the conflict graph;
10173 * for overlapping SOS1 constraints we apply the method getDiveBdChgsSOS1conflictgraph(), which then may produce better results (e.g. due to more
10188 /** constraint handler method which returns the permutation symmetry detection graph of a constraint */
10238 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/
10240 SCIP_CALL( SCIPaddSymgraphVarAggregation(scip, graph, nodeidx, locvars, locvals, nlocvars, constant) );
10254 /** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
10295 /* use SYM_SYMTYPE_PERM here to NOT center variable domains at 0, as the latter might not preserve
10305 if ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(locvars[0])) == SCIPisInfinity(scip, SCIPvarGetUbGlobal(locvars[0]))
10328 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &sumnodeidx) ); /*lint !e641*/
10390 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecSOS1, NULL) );
10414 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSOS1, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
10416 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSOS1, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
10418 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSOS1, consSepasolSOS1, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
10422 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphSOS1) );
10428 "do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit)",
10446 &conshdlrdata->depthimplanalysis, TRUE, DEFAULT_DEPTHIMPLANALYSIS, -1, INT_MAX, NULL, NULL) );
10463 "which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique) (note: in some cases an automatic switching to SOS1 branching is possible)",
10464 &conshdlrdata->branchingrule, TRUE, DEFAULT_BRANCHINGRULE, DEFAULT_BRANCHSTRATEGIES, NULL, NULL) );
10471 "if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance",
10475 "if TRUE then add complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching)",
10483 "minimal feasibility value for complementarity constraints in order to be added to the branching node",
10484 &conshdlrdata->addcompsfeas, TRUE, DEFAULT_ADDCOMPSFEAS, -SCIP_REAL_MAX, SCIP_REAL_MAX, NULL, NULL) );
10487 "minimal feasibility value for bound inequalities in order to be added to the branching node",
10488 &conshdlrdata->addbdsfeas, TRUE, DEFAULT_ADDBDSFEAS, -SCIP_REAL_MAX, SCIP_REAL_MAX, NULL, NULL) );
10491 "should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities",
10495 "Use SOS1 branching in enforcing (otherwise leave decision to branching rules)? This value can only be set to false if all SOS1 variables are binary",
10503 "Branch on SOS cons. with highest nonzero-variable weight for branching (needs branchnonzeros = false)?",
10507 "only add complementarity constraints to branching nodes for predefined depth (-1: no limit)",
10512 "maximal number of strong branching rounds to perform for each node (-1: auto); only available for neighborhood and bipartite branching",
10516 "maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit)",
10529 "if TRUE then automatically switch to separating initial SOS1 constraints if the SOS1 constraints do not overlap",
10534 &conshdlrdata->boundcutsfreq, TRUE, DEFAULT_BOUNDCUTSFREQ, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
10554 &conshdlrdata->implcutsfreq, TRUE, DEFAULT_IMPLCUTSFREQ, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
10574 * We set the constraint to not be modifable. If the weights are non NULL, the variables are ordered according to these
10577 * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
10585 SCIP_Real* weights, /**< weights determining the variable order, or NULL if natural order should be used */
10601 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
10603 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
10664 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
10668 /* replace original variables by transformed variables in transformed constraint, add locks, and catch events */
10686 SCIP_CALL( handleNewVariableSOS1(scip, *cons, consdata, conshdlrdata, consdata->vars[v], transformed) );
10693 /** creates and captures a SOS1 constraint with all constraint flags set to their default values.
10698 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
10706 SCIP_Real* weights /**< weights determining the variable order, or NULL if natural order should be used */
10709 SCIP_CALL( SCIPcreateConsSOS1( scip, cons, name, nvars, vars, weights, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
10722 {
10730 SCIPdebugMsg(scip, "adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var), SCIPconsGetName(cons), weight);
10763 SCIPdebugMsg(scip, "appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons));
10928 /** returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph */
10984 /** based on solution values of the variables, fixes variables to zero to turn all SOS1 constraints feasible */
10990 SCIP_Bool* success /**< pointer to store whether SOS1 constraints have been turned feasible and
11023 /* if the SOS1 constraints do not overlap, we apply a faster method makeSOS1constraintsFeasible() that does not make use of the conflict graph;
11024 * for overlapping SOS1 constraints we apply the method makeSOS1conflictgraphFeasible(), which then may produce better feasible solutions */
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void ** SCIPdigraphGetSuccessorsData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7837
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:1605
static SCIP_RETCODE genConflictgraphLinearCons(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraphlin, SCIP_DIGRAPH *conflictgraphorig, SCIP_VAR **linvars, int nlinvars, int *posinlinvars)
Definition: cons_sos1.c:1385
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1692
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
Definition: type_result.h:42
static SCIP_RETCODE enforceConssSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_sos1.c:5818
Definition: type_result.h:46
static SCIP_RETCODE fixVariableZero(SCIP *scip, SCIP_VAR *var, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: cons_sos1.c:637
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5202
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2127
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
public methods for SCIP parameter handling
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:8257
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17871
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
public methods for branch and bound tree
Definition: type_lp.h:48
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:3642
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
Definition: struct_scip.h:69
static SCIP_RETCODE getDiveBdChgsSOS1constraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success)
Definition: cons_sos1.c:8076
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1991
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
Definition: tclique_graph.c:185
static SCIP_DECL_CONSENFORELAX(consEnforelaxSOS1)
Definition: cons_sos1.c:9431
SCIP_VAR ** SCIPgetVarsSOS1(SCIP *scip, SCIP_CONS *cons)
Definition: cons_sos1.c:10814
Definition: type_prob.h:47
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:340
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3546
static SCIP_RETCODE getDiveBdChgsSOS1conflictgraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success)
Definition: cons_sos1.c:7935
public methods for conflict handler plugins and conflict analysis
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:711
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
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:1438
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:4339
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1813
Definition: type_result.h:58
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
void SCIPcomputeArraysSetminusInt(int *array1, int narray1, int *array2, int narray2, int *setminusarray, int *nsetminusarray)
Definition: misc.c:10689
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
SCIP_Real * SCIPgetWeightsSOS1(SCIP *scip, SCIP_CONS *cons)
Definition: cons_sos1.c:10839
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:1539
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4845
static SCIP_RETCODE makeSOS1constraintsFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *allroundable)
Definition: cons_sos1.c:7800
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
Definition: struct_var.h:207
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1438
static SCIP_RETCODE propConsSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *ngen)
Definition: cons_sos1.c:3544
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:533
SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
Definition: cons_sos1.c:10991
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:1124
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
static SCIP_Bool isImpliedZero(SCIP_DIGRAPH *conflictgraph, SCIP_Bool *implnodes, int node)
Definition: cons_sos1.c:2261
static SCIP_RETCODE updateArcData(SCIP *scip, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_VAR **totalvars, SCIP_VAR *varv, SCIP_VAR *varw, SCIP_Real lb, SCIP_Real ub, SCIP_Real newbound, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible)
Definition: cons_sos1.c:2290
int SCIPgetSymgraphVarnodeidx(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
Definition: symmetry_graph.c:512
static SCIP_Real nodeGetSolvalBinaryBigMSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
Definition: cons_sos1.c:440
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4595
static SCIP_RETCODE deleteVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_sos1.c:1085
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
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_cons.c:181
static SCIP_Real nodeGetSolvalVarboundLbSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
Definition: cons_sos1.c:490
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:8333
static SCIP_Real nodeGetSolvalVarboundUbSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
Definition: cons_sos1.c:517
SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var)
Definition: var.c:17916
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:419
SCIP_RETCODE SCIPincludeConshdlrSOS1(SCIP *scip)
Definition: cons_sos1.c:10368
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
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:7564
static SCIP_RETCODE separateSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, SCIP_RESULT *result)
Definition: cons_sos1.c:7231
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
public methods for problem variables
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: scip_probing.c:1264
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5319
static SCIP_RETCODE resetConflictgraphSOS1(SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, int nsos1vars)
Definition: cons_sos1.c:5290
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_cons.c:235
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
Definition: type_result.h:49
static SCIP_RETCODE initConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss)
Definition: cons_sos1.c:8686
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4889
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
tclique user interface
SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
Definition: scip_branch.c:971
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_RETCODE SCIPaddSymgraphVarAggregation(SCIP *scip, SYM_GRAPH *graph, int rootidx, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real constant)
Definition: symmetry_graph.c:294
Definition: type_lp.h:46
public methods for SCIP variables
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
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_param.c:83
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18573
static SCIP_RETCODE getVectorOfWeights(SCIP *scip, SCIP_SOL *sol, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *indicatorzero, SCIP_Real *weights)
Definition: cons_sos1.c:7352
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18304
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
Definition: struct_tree.h:141
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_cons.c:998
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip_datastructures.c:617
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:352
public methods for numerical tolerances
public methods for querying solving statistics
Definition: struct_sol.h:73
SCIP_Longint SCIPgetNDualResolveLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:731
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4258
public methods for the branch-and-bound tree
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
Definition: struct_misc.h:137
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
public methods for managing constraints
Definition: cons_sos1.c:241
SCIP_RETCODE SCIPsetConshdlrGetDiveBdChgs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETDIVEBDCHGS((*consgetdivebdchgs)))
Definition: scip_cons.c:877
methods for dealing with symmetry detection graphs
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
int SCIPvarGetNodeSOS1(SCIP_CONSHDLR *conshdlr, SCIP_VAR *var)
Definition: cons_sos1.c:10935
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
Definition: tclique_graph.c:380
Definition: type_result.h:44
SCIP_RETCODE SCIPdigraphSetNSuccessors(SCIP_DIGRAPH *digraph, int node, int nsuccessors)
Definition: misc.c:7730
Definition: struct_cons.h:46
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
Definition: struct_cons.h:126
Definition: type_retcode.h:51
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3474
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
Definition: cons_sos1.c:10722
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:362
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:418
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETPERMSYMGRAPH((*consgetpermsymgraph)))
Definition: scip_cons.c:900
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7756
static SCIP_RETCODE updateWeightsTCliquegraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, TCLIQUE_DATA *tcliquedata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars)
Definition: cons_sos1.c:6196
Definition: type_retcode.h:57
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1793
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:6829
Definition: type_result.h:45
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
Definition: misc.c:7772
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4436
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:6755
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8714
Definition: type_history.h:45
void SCIPcomputeArraysIntersectionInt(int *array1, int narray1, int *array2, int narray2, int *intersectarray, int *nintersectarray)
Definition: misc.c:10559
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
static SCIP_RETCODE fixVariableZeroNode(SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible)
Definition: cons_sos1.c:582
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4219
Definition: type_var.h:53
structs for symmetry computations
Definition: type_symmetry.h:61
Definition: type_retcode.h:42
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:1010
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
public methods for problem copies
static SCIP_RETCODE appendVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
Definition: cons_sos1.c:1027
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:2689
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:820
static SCIP_RETCODE computeNodeDataSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nsos1vars)
Definition: cons_sos1.c:8649
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_var.c:1737
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
Definition: var.c:17883
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:6892
Definition: type_result.h:51
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7662
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10867
SCIP_Bool SCIPdivesetSupportsType(SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype)
Definition: heur.c:753
int SCIPgetSymgraphNegatedVarnodeidx(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
Definition: symmetry_graph.c:532
Definition: type_lp.h:43
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3323
SCIP_Bool SCIPvarIsSOS1(SCIP_CONSHDLR *conshdlr, SCIP_VAR *var)
Definition: cons_sos1.c:10911
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:9417
SCIP_RETCODE SCIPappendVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_sos1.c:10756
static SCIP_RETCODE checkConComponentsVarbound(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool checklb)
Definition: cons_sos1.c:8406
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7693
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7804
static SCIP_RETCODE freeImplGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons_sos1.c:3956
static SCIP_RETCODE getBranchingDecisionStrongbranchSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars, SCIP_Real lpobjval, SCIP_Bool bipbranch, int nstrongrounds, SCIP_Bool *verticesarefixed, int *fixingsnode1, int *fixingsnode2, int *vertexbestprior, SCIP_Real *bestobjval1, SCIP_Real *bestobjval2, SCIP_RESULT *result)
Definition: cons_sos1.c:4481
static SCIP_RETCODE enforceConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_sos1.c:5346
Definition: struct_heur.h:67
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip_prob.c:3757
Definition: type_var.h:55
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2537
Definition: struct_lp.h:201
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphSOS1)
Definition: cons_sos1.c:10262
static SCIP_RETCODE freeConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons_sos1.c:8881
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphSOS1)
Definition: cons_sos1.c:10196
public methods for LP management
static SCIP_RETCODE addVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Real weight)
Definition: cons_sos1.c:957
public methods for cuts and aggregation rows
static SCIP_RETCODE getBranchingVerticesSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int branchvertex, int *fixingsnode1, int *nfixingsnode1, int *fixingsnode2, int *nfixingsnode2)
Definition: cons_sos1.c:4122
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:920
SCIP_VAR * SCIPnodeGetVarSOS1(SCIP_DIGRAPH *conflictgraph, int node)
Definition: cons_sos1.c:10966
Definition: type_var.h:54
SCIP_Longint SCIPgetNDualResolveLPs(SCIP *scip)
Definition: scip_solvingstats.c:711
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8275
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4350
static SCIP_RETCODE performImplicationGraphAnalysis(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **totalvars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool **adjacencymatrix, int givennode, int nonznode, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Bool *implnodes, int *naddconss, int *probingdepth, SCIP_Bool *infeasible)
Definition: cons_sos1.c:2103
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_RETCODE SCIPaddSymgraphOpnode(SCIP *scip, SYM_GRAPH *graph, int op, int *nodeidx)
Definition: symmetry_graph.c:382
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:3785
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_var.c:5500
static SCIP_RETCODE initTCliquegraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars)
Definition: cons_sos1.c:6127
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:6256
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:947
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH((*consgetsignedpermsymgraph)))
Definition: scip_cons.c:924
SCIP_RETCODE SCIPcreateConsBasicSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
Definition: cons_sos1.c:10706
public methods for the LP relaxation, rows and columns
methods for sorting joint arrays of various types
Definition: type_history.h:43
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:17952
public methods for branching rule plugins and branching
static SCIP_RETCODE getBoundConsFromVertices(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int v1, int v2, SCIP_VAR *boundvar, SCIP_Bool extend, SCIP_CONS *cons, SCIP_Real *feas)
Definition: cons_sos1.c:4698
public methods for managing events
SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:821
general public methods
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
static SCIP_RETCODE addBranchingComplementaritiesSOS1(SCIP *scip, SCIP_NODE *node, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, SCIP_SOL *sol, int nsos1vars, SCIP_Bool *verticesarefixed, int *fixingsnode1, int nfixingsnode1, int *fixingsnode2, int nfixingsnode2, int *naddedconss, SCIP_Bool onlyviolsos1)
Definition: cons_sos1.c:4926
static SCIP_RETCODE makeSOS1conflictgraphFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *allroundable)
Definition: cons_sos1.c:7670
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:167
public methods for solutions
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_copy.c:711
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18660
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_var.c:5614
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
static SCIP_RETCODE checkSwitchNonoverlappingSOS1Methods(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_CONS **conss, int nconss)
Definition: cons_sos1.c:8568
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
public methods for message output
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:129
static SCIP_RETCODE branchCons(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result)
Definition: cons_disjunction.c:231
Definition: type_var.h:97
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:857
SCIP_RETCODE SCIPaddSymgraphConsnode(SCIP *scip, SYM_GRAPH *graph, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, int *nodeidx)
Definition: symmetry_graph.c:464
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
Definition: symmetry_graph.c:1697
static SCIP_RETCODE lockVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_sos1.c:754
SCIP_RETCODE SCIPaddSymgraphValnode(SCIP *scip, SYM_GRAPH *graph, SCIP_Real val, int *nodeidx)
Definition: symmetry_graph.c:423
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:7006
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1727
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
constraint handler for SOS type 1 constraints
public methods for message handling
static SCIP_RETCODE updateImplicationGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, SCIP_VAR **totalvars, int **cliquecovers, int *cliquecoversizes, int *varincover, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_Real *bounds, SCIP_VAR *var, SCIP_Real bound, SCIP_Real boundnonzero, int ninftynonzero, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible)
Definition: cons_sos1.c:2416
public methods for data structures
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
static SCIP_RETCODE getCoverVertices(SCIP_DIGRAPH *conflictgraph, SCIP_Bool *verticesarefixed, int vertex, int *neightocover, int nneightocover, int *coververtices, int *ncoververtices)
Definition: cons_sos1.c:4015
void SCIPsortInt(int *intarray, int len)
static SCIP_RETCODE presolRoundVarsSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, int nsos1vars, int *nfixedvars, int *nchgbds, int *naddconss, SCIP_RESULT *result)
Definition: cons_sos1.c:3370
Definition: type_retcode.h:54
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_RETCODE SCIPaddSymgraphEdge(SCIP *scip, SYM_GRAPH *graph, int first, int second, SCIP_Bool hasval, SCIP_Real val)
Definition: symmetry_graph.c:634
Definition: type_lp.h:44
static SCIP_RETCODE checkLinearConssVarboundSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **linconss, int nlinconss)
Definition: cons_sos1.c:8495
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:822
static SCIP_RETCODE consdataEnsurevarsSizeSOS1(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveWeights)
Definition: cons_sos1.c:794
static SCIP_RETCODE unlockVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_sos1.c:774
static SCIP_Bool varIsSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
Definition: cons_sos1.c:544
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:1831
Definition: type_result.h:54
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18684
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:10585
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:7423
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
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_probing.c:1120
Definition: type_lp.h:47
static SCIP_RETCODE getBranchingPrioritiesSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int *fixingsnode1, int *fixingsnode2, SCIP_Real *branchpriors, int *vertexbestprior, SCIP_Bool *relsolfeas)
Definition: cons_sos1.c:4235
Definition: type_retcode.h:44
public methods for primal heuristics
Definition: type_retcode.h:52
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(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_lp.c:1391
Definition: objbenders.h:43
static SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsSOS1)
Definition: cons_sos1.c:10156
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:230
public methods for global and local (sub)problems
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
Definition: struct_misc.h:219
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:6330
static SCIP_RETCODE enforceSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_sos1.c:6064
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18636
Definition: type_set.h:47
Definition: type_symmetry.h:83
static int varGetNodeSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
Definition: cons_sos1.c:561
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18549
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_param.c:139
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:2578
static SCIP_Bool isConnectedSOS1(SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *conflictgraph, int vertex1, int vertex2)
Definition: cons_sos1.c:335
Definition: type_result.h:48
Definition: struct_event.h:204
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_param.c:57
static SCIP_Bool isViolatedSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_SOL *sol)
Definition: cons_sos1.c:395
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
memory allocation routines