sepa_rlt.c
Go to the documentation of this file.
31 * @todo implement the possibility to add extra auxiliary variables for RLT (like in DOI 10.1080/10556788.2014.916287)
33 * @todo implement dynamic addition of RLT cuts during branching (see DOI 10.1007/s10898-012-9874-7)
35 * @todo parameter maxusedvars seems arbitrary (too large for small problems; too small for large problems); something more adaptive we can do? (e.g., all variables with priority >= x% of highest prio)
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
54 #define SEPA_FREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
55 #define SEPA_MAXBOUNDDIST 1.0 /**< maximal relative distance from the current node's dual bound to primal bound
58 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
60 #define DEFAULT_MAXUNKNOWNTERMS 0 /**< maximum number of unknown bilinear terms a row can have to be used */
61 #define DEFAULT_MAXUSEDVARS 100 /**< maximum number of variables that will be used to compute rlt cuts */
64 #define DEFAULT_MAXROUNDSROOT 10 /**< maximum number of separation rounds in the root node (-1: unlimited) */
66 #define DEFAULT_ONLYCONTROWS FALSE /**< whether only continuous rows should be used for rlt cuts */
67 #define DEFAULT_ONLYORIGINAL TRUE /**< whether only original variables and rows should be used for rlt cuts */
68 #define DEFAULT_USEINSUBSCIP FALSE /**< whether the separator should also be used in sub-scips */
69 #define DEFAULT_USEPROJECTION FALSE /**< whether the separator should first check projected rows */
70 #define DEFAULT_DETECTHIDDEN FALSE /**< whether implicit products should be detected and separated by McCormick */
72 #define DEFAULT_ADDTOPOOL TRUE /**< whether globally valid RLT cuts are added to the global cut pool */
74 #define DEFAULT_GOODSCORE 1.0 /**< threshold for score of cut relative to best score to be considered good,
76 #define DEFAULT_BADSCORE 0.5 /**< threshold for score of cut relative to best score to be discarded */
77 #define DEFAULT_OBJPARALWEIGHT 0.0 /**< weight of objective parallelism in cut score calculation */
79 #define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in cut score calculation */
96 };
107 };
115 SCIP_Bool isinitialround; /**< indicates that this is the first round and original rows are used */
119 SCIP_HASHMAP* bilinvardatamap; /**< maps each bilinear var to ADJACENTVARDATA containing vars appearing
130 int maxunknownterms; /**< maximum number of unknown bilinear terms a row can have to be used (-1: unlimited) */
131 int maxusedvars; /**< maximum number of variables that will be used to compute rlt cuts (-1: unlimited) */
137 SCIP_Bool onlyoriginal; /**< whether only original rows and variables should be used for rlt cuts */
140 SCIP_Bool detecthidden; /**< whether implicit products should be detected and separated by McCormick */
145 SCIP_Real goodscore; /**< threshold for score of cut relative to best score to be considered good,
150 SCIP_Real dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */
166 };
200 /* if two hashdata objects have the same variables, then either one of them doesn't have a row list yet
203 assert(hashdata1->firstrow == -1 || hashdata2->firstrow == -1 || hashdata1->firstrow == hashdata2->firstrow);
260 adjacentvardata = (ADJACENTVARDATA*) SCIPhashmapGetImage(adjvarmap, (void*)(size_t) SCIPvarGetIndex(vars[v1]));
266 SCIP_CALL( SCIPhashmapInsert(adjvarmap, (void*)(size_t) SCIPvarGetIndex(vars[v1]), adjacentvardata) );
292 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &adjacentvardata->adjacentvars, &adjacentvardata->sadjacentvars,
326 adjacentvardata = (ADJACENTVARDATA*) SCIPhashmapGetImage(adjvarmap, (void*)(size_t) SCIPvarGetIndex(var));
507 SCIP_CALL( SCIPhashmapSetImageInt(row_to_pos, (void*)(size_t)SCIProwGetIndex(prob_rows[r]), new_nrows) ); /*lint !e571 */
516 /** make sure that the arrays in sepadata are large enough to store information on n variables */
535 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->varssorted, sepadata->sbilinvars, newsize) );
536 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->varpriorities, sepadata->sbilinvars, newsize) );
568 /* the number of variables participating in bilinear products cannot exceed twice the number of bilinear terms;
569 * however, if we detect hidden products, the number of terms is yet unknown, so use the number of variables
585 SCIP_CALL( SCIPhashmapInsertInt(varmap, (void*)(size_t) xidx, sepadata->nbilinvars) ); /*lint !e571*/
606 SCIP_CALL( SCIPhashmapInsertInt(varmap, (void*)(size_t) yidx, sepadata->nbilinvars) ); /*lint !e571*/
637 * and the second when \f$ x = 0 \f$, and \f$ b_1, b_2 > 0 \f$, the product relation can be written as:
641 * The inequality sign in the product relation is similar to that in the given linear relations if
644 * To obtain this formula, the given relations are first multiplied by scaling factors \f$ \alpha \f$
645 * and \f$ \beta \f$, which is necessary in order for the solution to always exist, and written as
651 * Then a linear system is solved which ensures that the coefficients of the two implications of the product
694 /* coefficients in given relations: a for x, b for w, c for y; 1 and 2 for 1st and 2nd relation, respectively */
713 SCIPdebugMsg(scip, "Relation 1: <%s> == %u => %g<%s> + %g<%s> %s %g\n", SCIPvarGetName(x), f, b1,
716 SCIPdebugMsg(scip, "Relation 2: <%s> == %d => %g<%s> + %g<%s> %s %g\n", SCIPvarGetName(x), !f, b2,
779 * where the inequality sign in the product relation is similar to that in the given linear relations
787 overestimate = (sidetype1 == SCIP_SIDETYPE_LEFT && mult > 0.0) || (sidetype1 == SCIP_SIDETYPE_RIGHT && mult < 0.0);
800 SCIPdebugMsg(scip, "product: <%s><%s> %s %g<%s> + %g<%s> + %g<%s> + %g\n", SCIPvarGetName(x), SCIPvarGetName(y),
801 overestimate ? "<=" : ">=", A, SCIPvarGetName(x), B, SCIPvarGetName(w), C, SCIPvarGetName(y), D);
804 SCIP_CALL( SCIPinsertBilinearTermImplicitNonlinear(scip, sepadata->conshdlr, x, y, w, A, C, B, D, overestimate) );
809 /** convert an implied bound: `binvar` = `binval` ⇒ `implvar` ≤/≥ `implbnd` into a big-M constraint */
832 globbnd = bndtype == SCIP_BOUNDTYPE_LOWER ? SCIPvarGetLbGlobal(implvar) : SCIPvarGetUbGlobal(implvar);
890 /* loop over binvals; if binvar is x (case binvarpos == 0), then we want to use only implications from
891 * binvar == !f (which is the option complementing the first relation, which is implied from f); if
892 * binvar is not x, this doesn't matter since the implbnd doesn't depend on x, therefore try both !f and f
902 implBndToBigM(scip, vars_xwy, binvarpos, implvarpos, SCIP_BOUNDTYPE_LOWER, binvals[i], impllb, coefs2, &side2);
911 implBndToBigM(scip, vars_xwy, binvarpos, implvarpos, SCIP_BOUNDTYPE_UPPER, binvals[i], implub, coefs2, &side2);
961 /* if var1=TRUE and var2=TRUE are in a clique (binvals[i] == TRUE), the relation var1 + var2 <= 1 is implied
962 * if var1=FALSE and var2=TRUE are in a clique (binvals[i] == FALSE), the relation (1 - var1) + var2 <= 1 is implied
966 SCIPdebugMsg(scip, "vars %s<%s> and <%s> are in a clique\n", binvals[i] ? "" : "!", SCIPvarGetName(var1), SCIPvarGetName(var2));
975 /* if var1=TRUE and var2=FALSE are in the same clique, the relation var1 + (1-var2) <= 1 is implied
976 * if var1=FALSE and var2=FALSE are in the same clique, the relation (1-var1) + (1-var2) <= 1 is implied
980 SCIPdebugMsg(scip, "vars %s<%s> and !<%s> are in a clique\n", binvals[i] ? "" : "!", SCIPvarGetName(var1), SCIPvarGetName(var2));
994 /** extract products from a relation given by `coefs1`, `vars`, `side1` and `sidetype1` and unconditional relations
1083 /** finds and stores implied relations (x = f ⇒ ay + bw ≤ c, f can be 0 or 1) and 2-variable relations
1087 * - An array of variables that participate in two variable relations; for each such variable, ADJACENTVARDATA
1088 * containing an array of variables that participate in two variable relations together with it; and a hashmap
1091 * - Hashtables storing hashdata objects with the two or three variables and the position of the first row in the
1092 * `prob_rows` array, which in combination with the linked list (described below) will allow access to all rows that
1095 * - Linked lists of row indices. Each list corresponds to a pair or triple of variables and contains positions of rows
1096 * which depend only on those variables. All lists are stored in `row_list`, an array of length `nrows`, which is
1097 * possible because each row belongs to at most one list. The array indices of `row_list` represent the positions of
1098 * rows in `prob_rows`, and a value in the `row_list` array represents the next index in the list (-1 if there is no next
1099 * list element). The first index of each list is stored in one of the hashdata objects as firstrow.
1108 SCIP_HASHMAP* vars_in_2rels, /**< connections between variables that appear in 2-variable relations */
1142 SCIPdebugMsg(scip, "ignoring relation <%s> because a var is binary\n", SCIProwGetName(prob_rows[r]));
1175 /* hashdata.vars are two variables participating together in a two variable relation, therefore update
1285 /* fill the data structures that will be used for product detection: hashtables and linked lists allowing to access
1286 * two and three variable relations by the variables; and the hashmap for accessing variables participating in two
1288 SCIP_CALL( fillRelationTables(scip, prob_rows, nrows, hashtable2, hashtable3, vars_in_2rels, row_list) );
1301 /* An implied relation has the form: x == f => l(w,y) <=/>= side (f is 0 or 1, l is a linear function). Given
1302 * a linear relation with three variables, any binary var can be x: we try them all here because this can
1326 /* the order of variables in all rows should be the same, and similar to the order in hashdata->vars,
1333 /* use the side for which the inequality becomes tighter when x == xfixing than when x == !xfixing */
1364 /* look for the second relation: it should be tighter when x == !xfixing than when x == xfixing
1384 /* use the side for which the inequality becomes tighter when x == !xfixing than when x == xfixing */
1442 if( SCIPvarGetType(vars_xwy[1]) == SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[2]) != SCIP_VARTYPE_BINARY )
1445 SCIP_CALL( detectProductsImplbnd(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 1, 2, varmap, xfixing) );
1449 if( SCIPvarGetType(vars_xwy[2]) == SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[1]) != SCIP_VARTYPE_BINARY )
1452 SCIP_CALL( detectProductsImplbnd(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 2, 1, varmap, xfixing) );
1456 if( SCIPvarGetType(vars_xwy[1]) == SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[2]) == SCIP_VARTYPE_BINARY )
1459 SCIP_CALL( detectProductsClique(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 1, 2, varmap, xfixing) );
1463 if( SCIPvarGetType(vars_xwy[1]) != SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[2]) != SCIP_VARTYPE_BINARY )
1466 SCIP_CALL( detectProductsUnconditional(scip, sepadata, prob_rows, row_list, hashtable2, coefs1,
1509 SCIPdebugMsg(scip, "Written as big-M: %g%s + %s %s %g\n", coefs1[0], SCIPvarGetName(vars_xwy[0]),
1514 /* x does not participate in the second relation, so we immediately set its coefficient to 0.0 */
1517 SCIPdebugMsg(scip, "Implic of x = <%s> + implied lb on w = <%s>:\n", SCIPvarGetName(vars_xwy[0]), SCIPvarGetName(vars_xwy[1]));
1533 SCIPdebugMsg(scip, "Implic of x = <%s> + implied ub on w = <%s>:\n", SCIPvarGetName(vars_xwy[0]), SCIPvarGetName(vars_xwy[1]));
1558 SCIP_CALL( detectProductsUnconditional(scip, sepadata, prob_rows, row_list, hashtable2, coefs1,
1622 /* the number of variables participating in bilinear products cannot exceed twice the number of bilinear terms;
1623 * however, if we detect hidden products, the number of terms is yet unknown, so use the number of variables
1645 /* if only original variables should be used, skip products that contain at least one auxiliary variable */
1700 * (same as normal sort, except that entries at positions maxusedvars..nbilinvars may be unsorted at end)
1702 SCIPselectDownIntPtr(sepadata->varpriorities, (void**) sepadata->varssorted, MIN(sepadata->maxusedvars,sepadata->nbilinvars-1),
1724 /** get the positions of the most violated auxiliary under- and overestimators for each product
1765 auxval = SCIPevalBilinAuxExprNonlinear(scip, terms[j].x, terms[j].y, terms[j].aux.exprs[i], sol);
1768 if( terms[j].aux.exprs[i]->underestimate && SCIPisFeasGT(scip, auxval, prodval) && prodviol > viol_below )
1773 if( terms[j].aux.exprs[i]->overestimate && SCIPisFeasGT(scip, prodval, auxval) && -prodviol > viol_above )
1790 int* currentnunknown, /**< buffer to store number of unknown terms in current row if acceptable */
1804 for( i = 0; (i < SCIProwGetNNonz(row)) && (sepadata->maxunknownterms < 0 || *currentnunknown <= sepadata->maxunknownterms); ++i )
1806 idx = SCIPgetBilinTermIdxNonlinear(sepadata->conshdlr, var, SCIPcolGetVar(SCIProwGetCols(row)[i]));
1816 if( sepadata->eqauxexpr[idx] == -1 && !(terms[idx].nauxexprs == 0 && terms[idx].aux.var != NULL) )
1868 /** add a linear term `coef`*`colvar` multiplied by a bound factor (var - lb(var)) or (ub(var) - var)
1925 coefauxvar = 0.0; /* coefficient of the auxiliary variable corresponding to the bilinear term */
1956 /* if the term is implicit and a suitable auxiliary expression for var*colvar exists, add the coefficients
1957 * of the auxiliary expression for coefterm*var*colvar to coefauxvar, coefcolvar, coefvar and cst
1963 addAuxexprCoefs(var, colvar, terms[idx].aux.exprs[auxpos], coefterm, &coefauxvar, coefvar, &coefcolvar, cst);
1975 /* otherwise, use clique information or the McCormick estimator in place of the bilinear term */
1981 SCIP_Real refpointcolvar = MAX(lbcolvar, MIN(ubcolvar, SCIPgetSolVal(scip, sol, colvar))); /*lint !e666*/
1991 SCIPdebugMsg(scip, "auxvar for <%s> and <%s> not found, will linearize the product\n", SCIPvarGetName(colvar), SCIPvarGetName(var));
1994 if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY && SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY )
2011 if( SCIPcliqueHasVar(varcliques[c], colvar, FALSE) ) /* var + (1-colvar) <= 1 => var*colvar = var */
2026 if( SCIPcliqueHasVar(varcliques[c], colvar, TRUE) ) /* (1-var) + colvar <= 1 => var*colvar = colvar */
2033 if( SCIPcliqueHasVar(varcliques[c], colvar, FALSE) ) /* (1-var) + (1-colvar) <= 1 => var*colvar = var + colvar - 1 */
2047 SCIPdebugMsg(scip, "clique for <%s> and <%s> not found or at least one of them is not binary, will use McCormick\n", SCIPvarGetName(colvar), SCIPvarGetName(var));
2055 /* or, if it's a quadratic term, use a secant for overestimation and a gradient for underestimation */
2058 SCIPdebugMsg(scip, "auxvar for <%s>^2 not found, will use gradient and secant estimators\n", SCIPvarGetName(colvar));
2069 /* depending on over-/underestimation and the sign of the column variable, compute secant or tangent */
2073 SCIPaddSquareLinearization(scip, coefterm, refpointvar, SCIPvarIsIntegral(var), coefvar, cst, success);
2105 * - The row is multiplied either with (x - lb(x)) or with (ub(x) - x), depending on parameter `uselb`, or by x if
2108 * - Terms for which no auxiliary variable and no clique relation exists are replaced by either McCormick, secants,
2181 SCIPdebugMsg(scip, "cut generation for %srow <%s>, %s, and variable <%s> with its %s %g not possible\n",
2204 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "rlt_%scut_%s_%s_%s_%s_%" SCIP_LONGINT_FORMAT, useprojrow ? "proj" : "", rowname,
2206 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, cut, sepa, cutname, -SCIPinfinity(scip), SCIPinfinity(scip),
2207 SCIPgetDepth(scip) > 0 && local, FALSE, FALSE) ); /* TODO SCIPgetDepth() should be replaced by depth that is passed on to the SEPAEXEC calls (?) */
2211 /* iterate over all variables in the row and add the corresponding terms coef*colvar*(bound factor) to the cuts */
2255 /** store a row projected by fixing all variables that are at bound at sol; the result is a simplified row */
2445 * depending on the sign of the coefficient and violation, set or update mark which cut is required:
2543 if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, valj) || SCIPisFeasEQ(scip, vub, valj)) )
2546 SCIPdebugMsg(scip, "Rejected multiplier <%s> in [%g,%g] because it is at bound (current value %g)\n", SCIPvarGetName(xj), vlb, vub, valj);
2567 if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, vali) || SCIPisFeasEQ(scip, vub, vali)) )
2583 { /* no violated implicit underestimation relations -> either use auxvar or set violatedbelow to FALSE */
2587 violatedbelow = SCIPisFeasPositive(scip, SCIPgetSolVal(scip, sol, terms[idx].aux.var) - valj * vali);
2600 assert(SCIPisFeasPositive(scip, SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2606 { /* no violated implicit overestimation relations -> either use auxvar or set violatedabove to FALSE */
2610 violatedabove = SCIPisFeasPositive(scip, valj * vali - SCIPgetSolVal(scip, sol, terms[idx].aux.var));
2623 assert(SCIPisFeasPositive(scip, valj * vali - SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2631 SCIPdebugMsg(scip, "the product for vars <%s> and <%s> is not violated\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2641 SCIPdebugMsg(scip, "marking rows for xj = <%s>, xi = <%s>\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2649 continue; /* if row index is not in row_to_pos, it means that storeSuitableRows decided to ignore this row */
2670 int* bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2671 int* bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2750 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "mccormick_%sestimate_implicit_%s*%s_%" SCIP_LONGINT_FORMAT,
2754 SCIP_CALL(SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), SCIPinfinity(scip), TRUE,
2766 /* add McCormick terms: ask for an underestimator if relation is xy <= auxexpr, and vice versa */
2767 SCIPaddBilinMcCormick(scip, 1.0, bndx.inf, bndx.sup, refpointx, bndy.inf, bndy.sup, refpointy, !underestimate,
2797 SCIPdebugMsg(scip, "\nMcCormick cut for hidden product <%s>*<%s> was created successfully, but is not violated",
2833 int* bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2834 int* bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2858 assert(!sepadata->detecthidden || (bestunderestimators != NULL && bestoverestimators != NULL));
2869 for( j = 0; j < sepadata->nbilinvars && (sepadata->maxusedvars < 0 || j < sepadata->maxusedvars); ++j )
2874 SCIP_CALL( markRowsXj(scip, sepadata, conshdlr, sol, j, allowlocal, row_to_pos, bestunderestimators,
2897 SCIPdebugMsg(scip, "rejected row <%s> for variable <%s> (introduces too many new products)\n", SCIProwGetName(row), SCIPvarGetName(xj));
2902 SCIPdebugMsg(scip, "accepted row <%s> for variable <%s>\n", SCIProwGetName(rows[r]), SCIPvarGetName(xj));
2908 /* if all terms are known and it is an equality row, compute equality cut, that is, multiply row with (x-lb) and/or (ub-x) (but see also @todo at top)
2909 * otherwise, multiply row w.r.t. lhs and/or rhs with (x-lb) and/or (ub-x) and estimate product terms that have no aux.var or aux.expr
2935 SCIPdebugMsg(scip, "row <%s>, uselb = %u, uselhs = %u\n", SCIProwGetName(row), uselb[k], uselhs[k]);
2944 SCIP_CALL( computeRltCut(scip, sepa, sepadata, &cut, NULL, &(projrows[pos]), sol, bestunderestimators,
2954 SCIPdebugMsg(scip, "projected cut is not violated, feasibility = %g\n", SCIPgetRowFeasibility(scip, cut));
2963 /* if we don't use projection or if the projected cut was generated successfully and is violated,
2973 success = SCIPisFeasNegative(scip, SCIPgetRowFeasibility(scip, cut)) || (sepadata->addtopool &&
2977 /* if the cut was created successfully and is violated or (if addtopool == TRUE) globally valid,
2994 SCIPdebugMsg(scip, "the generation of the cut failed or cut not violated and not added to cutpool\n");
3008 /* if cuts were found, we apply an additional filtering procedure, which is similar to sepastore */
3016 SCIP_CALL( SCIPselectCutsHybrid(scip, cuts, NULL, NULL, sepadata->goodscore, sepadata->badscore, sepadata->goodmaxparall,
3017 sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight,
3099 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */
3164 /* if this is called for the first time, create the sepadata and start the initial separation round */
3208 SCIP_CALL( storeSuitableRows(scip, sepa, sepadata, prob_rows, rows, &nrows, row_to_pos, allowlocal) );
3248 /* if we detect implicit products, a term might have more than one estimator in each direction;
3256 SCIP_CALL( separateMcCormickImplicit(scip, sepa, sepadata, NULL, bestunderestimators, bestoverestimators,
3261 SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3270 SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3300 )
3311 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
3377 "whether RLT cuts (TRUE) or only McCormick inequalities (FALSE) should be added for hidden products",
3387 "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied",
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
Definition: type_result.h:42
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3520
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11487
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
static SCIP_RETCODE extractProducts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR **vars_xwy, SCIP_Real *coefs1, SCIP_Real *coefs2, SCIP_Real d1, SCIP_Real d2, SCIP_SIDETYPE sidetype1, SCIP_SIDETYPE sidetype2, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:666
Definition: intervalarith.h:53
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition: misc.c:2735
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
Definition: struct_scip.h:68
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3307
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:1156
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2497
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
static SCIP_RETCODE addRltTerm(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderest, int *bestoverest, SCIP_ROW *cut, SCIP_VAR *var, SCIP_VAR *colvar, SCIP_Real coef, SCIP_Bool uselb, SCIP_Bool uselhs, SCIP_Bool local, SCIP_Bool computeEqCut, SCIP_Real *coefvar, SCIP_Real *cst, SCIP_Bool *success)
Definition: sepa_rlt.c:1875
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
static SCIP_VAR ** getAdjacentVars(SCIP_HASHMAP *adjvarmap, SCIP_VAR *var, int *nadjacentvars)
Definition: sepa_rlt.c:317
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1698
hybrid cut selector
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18286
Definition: cons_nonlinear.h:57
static void freeProjRows(SCIP *scip, RLT_SIMPLEROW **projrows, int nrows)
Definition: sepa_rlt.c:2431
Definition: struct_var.h:207
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
SCIP_Bool SCIPcliqueHasVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1141
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3024
int SCIPgetNBilinTermsNonlinear(SCIP_CONSHDLR *conshdlr)
Definition: cons_nonlinear.c:11812
Definition: type_var.h:62
static SCIP_RETCODE addAdjacentVars(SCIP *scip, SCIP_HASHMAP *adjvarmap, SCIP_VAR **vars)
Definition: sepa_rlt.c:243
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3142
int SCIPgetBilinTermIdxNonlinear(SCIP_CONSHDLR *conshdlr, SCIP_VAR *x, SCIP_VAR *y)
Definition: cons_nonlinear.c:11850
static SCIP_RETCODE detectProductsImplbnd(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *coefs1, SCIP_VAR **vars_xwy, SCIP_Real side1, SCIP_SIDETYPE sidetype1, int binvarpos, int implvarpos, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:861
Definition: type_lp.h:64
Definition: type_result.h:49
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3211
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
Definition: struct_sepa.h:46
void SCIPselectDownIntPtr(int *intarray, void **ptrarray, int k, int len)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
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
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2121
bilinear nonlinear handler
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2246
Definition: struct_lp.h:135
Definition: struct_sol.h:73
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3373
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
static SCIP_RETCODE computeRltCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_ROW **cut, SCIP_ROW *row, RLT_SIMPLEROW *projrow, SCIP_SOL *sol, int *bestunderest, int *bestoverest, SCIP_VAR *var, SCIP_Bool *success, SCIP_Bool uselb, SCIP_Bool uselhs, SCIP_Bool local, SCIP_Bool computeEqCut, SCIP_Bool useprojrow)
Definition: sepa_rlt.c:2114
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
Definition: struct_misc.h:137
Definition: type_result.h:44
Definition: struct_cons.h:46
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3499
Definition: struct_cons.h:126
static SCIP_RETCODE addProductVars(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR *x, SCIP_VAR *y, SCIP_HASHMAP *varmap, int nlocks)
Definition: sepa_rlt.c:550
Definition: type_lp.h:56
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
Definition: type_var.h:51
static SCIP_RETCODE detectProductsUnconditional(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **rows, int *row_list, SCIP_HASHTABLE *hashtable, SCIP_Real *coefs1, SCIP_VAR **vars_xwy, SCIP_Real side1, SCIP_SIDETYPE sidetype1, int varpos1, int varpos2, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:1000
power and signed power expression handlers
Definition: type_retcode.h:42
static SCIP_RETCODE storeSuitableRows(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_ROW **prob_rows, SCIP_ROW **rows, int *nrows, SCIP_HASHMAP *row_to_pos, SCIP_Bool allowlocal)
Definition: sepa_rlt.c:451
static void addRowMark(int ridx, SCIP_Real a, SCIP_Bool violatedbelow, SCIP_Bool violatedabove, int *row_idcs, unsigned int *row_marks, int *nmarked)
Definition: sepa_rlt.c:2453
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
union SCIP_ConsNonlinear_BilinTerm::@4 aux
Definition: type_lp.h:43
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
static void getBestEstimators(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators)
Definition: sepa_rlt.c:1731
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18233
static void addAuxexprCoefs(SCIP_VAR *var1, SCIP_VAR *var2, SCIP_CONSNONLINEAR_AUXEXPR *auxexpr, SCIP_Real coef, SCIP_Real *coefaux, SCIP_Real *coef1, SCIP_Real *coef2, SCIP_Real *cst)
Definition: sepa_rlt.c:1834
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:231
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1607
SCIP_CONSNONLINEAR_BILINTERM * SCIPgetBilinTermsNonlinear(SCIP_CONSHDLR *conshdlr)
Definition: cons_nonlinear.c:11831
Definition: presol_gateextraction.c:109
SCIP_RETCODE SCIPselectCutsHybrid(SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_RANDNUMGEN *randnumgen, SCIP_Real goodscorefac, SCIP_Real badscorefac, SCIP_Real goodmaxparall, SCIP_Real maxparall, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)
Definition: cutsel_hybrid.c:442
Definition: struct_misc.h:130
constraint handler for nonlinear constraints specified by algebraic expressions
Definition: struct_lp.h:201
public methods for LP management
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1453
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
void SCIPaddSquareSecant(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real lb, SCIP_Real ub, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
Definition: expr_pow.c:3303
SCIP_Real SCIPevalBilinAuxExprNonlinear(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_CONSNONLINEAR_AUXEXPR *auxexpr, SCIP_SOL *sol)
Definition: cons_nonlinear.c:11923
static SCIP_RETCODE createSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:1596
void SCIPaddBilinMcCormick(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
Definition: nlhdlr_bilinear.c:1762
static SCIP_RETCODE fillRelationTables(SCIP *scip, SCIP_ROW **prob_rows, int nrows, SCIP_HASHTABLE *hashtable2, SCIP_HASHTABLE *hashtable3, SCIP_HASHMAP *vars_in_2rels, int *row_list)
Definition: sepa_rlt.c:1104
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2558
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18247
Definition: cons_nonlinear.h:78
reformulation-linearization technique separator
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18218
static SCIP_RETCODE separateRltCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_HASHMAP *row_to_pos, RLT_SIMPLEROW *projrows, SCIP_ROW **rows, int nrows, SCIP_Bool allowlocal, int *bestunderestimators, int *bestoverestimators, SCIP_RESULT *result)
Definition: sepa_rlt.c:2824
Definition: struct_misc.h:89
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
static SCIP_RETCODE getOriginalRows(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: sepa_rlt.c:414
static SCIP_RETCODE markRowsXj(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int j, SCIP_Bool local, SCIP_HASHMAP *row_to_pos, int *bestunderest, int *bestoverest, unsigned int *row_marks, int *row_idcs, int *nmarked)
Definition: sepa_rlt.c:2500
Definition: type_lp.h:57
static SCIP_RETCODE freeSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:370
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:857
Definition: type_lp.h:65
static SCIP_RETCODE createProjRow(SCIP *scip, RLT_SIMPLEROW *simplerow, SCIP_ROW *row, SCIP_SOL *sol, SCIP_Bool local)
Definition: sepa_rlt.c:2259
Definition: struct_implics.h:75
static SCIP_RETCODE separateMcCormickImplicit(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators, SCIP_RESULT *result)
Definition: sepa_rlt.c:2667
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2209
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2727
static void implBndToBigM(SCIP *scip, SCIP_VAR **vars_xwy, int binvarpos, int implvarpos, SCIP_BOUNDTYPE bndtype, SCIP_Bool binval, SCIP_Real implbnd, SCIP_Real *coefs, SCIP_Real *side)
Definition: sepa_rlt.c:813
static SCIP_RETCODE ensureVarsSize(SCIP *scip, SCIP_SEPADATA *sepadata, int n)
Definition: sepa_rlt.c:520
Definition: sepa_rlt.c:104
SCIP_RETCODE SCIPinsertBilinearTermImplicitNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_VAR *x, SCIP_VAR *y, SCIP_VAR *auxvar, SCIP_Real coefx, SCIP_Real coefy, SCIP_Real coefaux, SCIP_Real cst, SCIP_Bool overestimate)
Definition: cons_nonlinear.c:11979
void SCIPaddSquareLinearization(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
Definition: expr_pow.c:3235
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3106
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
Definition: sepa_rlt.c:158
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3231
Definition: objbenders.h:43
static void clearVarAdjacency(SCIP *scip, SCIP_HASHMAP *adjvarmap)
Definition: sepa_rlt.c:340
static SCIP_RETCODE createProjRows(SCIP *scip, SCIP_ROW **rows, int nrows, SCIP_SOL *sol, RLT_SIMPLEROW **projrows, SCIP_Bool local, SCIP_Bool *allcst)
Definition: sepa_rlt.c:2347
static SCIP_RETCODE detectHiddenProducts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_HASHMAP *varmap)
Definition: sepa_rlt.c:1232
static SCIP_RETCODE isAcceptableRow(SCIP_SEPADATA *sepadata, SCIP_ROW *row, SCIP_VAR *var, int *currentnunknown, SCIP_Bool *acceptable)
Definition: sepa_rlt.c:1788
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
void SCIPvarGetImplicVarBounds(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_Real *lb, SCIP_Real *ub)
Definition: var.c:11155
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
SCIP_CONSNONLINEAR_AUXEXPR ** exprs
Definition: cons_nonlinear.h:84
Definition: type_result.h:48
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_RETCODE detectProductsClique(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *coefs1, SCIP_VAR **vars_xwy, SCIP_Real side1, SCIP_SIDETYPE sidetype1, int varpos1, int varpos2, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:927