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 */
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 */
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 */
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),
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);
2106 * - The row is multiplied either with (x - lb(x)) or with (ub(x) - x), depending on parameter `uselb`, or by x if
2109 * - Terms for which no auxiliary variable and no clique relation exists are replaced by either McCormick, secants,
2182 SCIPdebugMsg(scip, "cut generation for %srow <%s>, %s, and variable <%s> with its %s %g not possible\n",
2205 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "rlt_%scut_%s_%s_%s_%s_%" SCIP_LONGINT_FORMAT, useprojrow ? "proj" : "", rowname,
2207 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, cut, sepa, cutname, -SCIPinfinity(scip), SCIPinfinity(scip),
2208 SCIPgetDepth(scip) > 0 && local, FALSE, FALSE) ); /* TODO SCIPgetDepth() should be replaced by depth that is passed on to the SEPAEXEC calls (?) */
2212 /* iterate over all variables in the row and add the corresponding terms coef*colvar*(bound factor) to the cuts */
2256/** store a row projected by fixing all variables that are at bound at sol; the result is a simplified row */
2446 * depending on the sign of the coefficient and violation, set or update mark which cut is required:
2544 if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, valj) || SCIPisFeasEQ(scip, vub, valj)) )
2547 SCIPdebugMsg(scip, "Rejected multiplier <%s> in [%g,%g] because it is at bound (current value %g)\n", SCIPvarGetName(xj), vlb, vub, valj);
2568 if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, vali) || SCIPisFeasEQ(scip, vub, vali)) )
2584 { /* no violated implicit underestimation relations -> either use auxvar or set violatedbelow to FALSE */
2588 violatedbelow = SCIPisFeasPositive(scip, SCIPgetSolVal(scip, sol, terms[idx].aux.var) - valj * vali);
2601 assert(SCIPisFeasPositive(scip, SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2607 { /* no violated implicit overestimation relations -> either use auxvar or set violatedabove to FALSE */
2611 violatedabove = SCIPisFeasPositive(scip, valj * vali - SCIPgetSolVal(scip, sol, terms[idx].aux.var));
2624 assert(SCIPisFeasPositive(scip, valj * vali - SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2632 SCIPdebugMsg(scip, "the product for vars <%s> and <%s> is not violated\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2642 SCIPdebugMsg(scip, "marking rows for xj = <%s>, xi = <%s>\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2650 continue; /* if row index is not in row_to_pos, it means that storeSuitableRows decided to ignore this row */
2671 int* bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2672 int* bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2751 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "mccormick_%sestimate_implicit_%s*%s_%" SCIP_LONGINT_FORMAT,
2755 SCIP_CALL(SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), SCIPinfinity(scip), TRUE,
2767 /* add McCormick terms: ask for an underestimator if relation is xy <= auxexpr, and vice versa */
2768 SCIPaddBilinMcCormick(scip, 1.0, bndx.inf, bndx.sup, refpointx, bndy.inf, bndy.sup, refpointy, !underestimate,
2798 SCIPdebugMsg(scip, "\nMcCormick cut for hidden product <%s>*<%s> was created successfully, but is not violated",
2834 int* bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2835 int* bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2859 assert(!sepadata->detecthidden || (bestunderestimators != NULL && bestoverestimators != NULL));
2870 for( j = 0; j < sepadata->nbilinvars && (sepadata->maxusedvars < 0 || j < sepadata->maxusedvars); ++j )
2875 SCIP_CALL( markRowsXj(scip, sepadata, conshdlr, sol, j, allowlocal, row_to_pos, bestunderestimators,
2898 SCIPdebugMsg(scip, "rejected row <%s> for variable <%s> (introduces too many new products)\n", SCIProwGetName(row), SCIPvarGetName(xj));
2903 SCIPdebugMsg(scip, "accepted row <%s> for variable <%s>\n", SCIProwGetName(rows[r]), SCIPvarGetName(xj));
2909 /* 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)
2910 * 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
2936 SCIPdebugMsg(scip, "row <%s>, uselb = %u, uselhs = %u\n", SCIProwGetName(row), uselb[k], uselhs[k]);
2945 SCIP_CALL( computeRltCut(scip, sepa, sepadata, &cut, NULL, &(projrows[pos]), sol, bestunderestimators,
2955 SCIPdebugMsg(scip, "projected cut is not violated, feasibility = %g\n", SCIPgetRowFeasibility(scip, cut));
2964 /* if we don't use projection or if the projected cut was generated successfully and is violated,
2974 success = SCIPisFeasNegative(scip, SCIPgetRowFeasibility(scip, cut)) || (sepadata->addtopool &&
2978 /* if the cut was created successfully and is violated or (if addtopool == TRUE) globally valid,
2995 SCIPdebugMsg(scip, "the generation of the cut failed or cut not violated and not added to cutpool\n");
3009 /* if cuts were found, we apply an additional filtering procedure, which is similar to sepastore */
3017 SCIP_CALL( SCIPselectCutsHybrid(scip, cuts, NULL, NULL, sepadata->goodscore, sepadata->badscore, sepadata->goodmaxparall,
3018 sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight,
3100/** solving process deinitialization method of separator (called before branch and bound process data is freed) */
3165 /* if this is called for the first time, create the sepadata and start the initial separation round */
3209 SCIP_CALL( storeSuitableRows(scip, sepa, sepadata, prob_rows, rows, &nrows, row_to_pos, allowlocal) );
3249 /* if we detect implicit products, a term might have more than one estimator in each direction;
3257 SCIP_CALL( separateMcCormickImplicit(scip, sepa, sepadata, NULL, bestunderestimators, bestoverestimators,
3262 SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3271 SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3312 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
3378 "whether RLT cuts (TRUE) or only McCormick inequalities (FALSE) should be added for hidden products",
3388 "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied",
constraint handler for nonlinear constraints specified by algebraic expressions
hybrid cut selector
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:3253
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:3321
power and signed power expression handlers
SCIP_Real SCIPevalBilinAuxExprNonlinear(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_CONSNONLINEAR_AUXEXPR *auxexpr, SCIP_SOL *sol)
Definition: cons_nonlinear.c:13436
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:13492
int SCIPgetBilinTermIdxNonlinear(SCIP_CONSHDLR *conshdlr, SCIP_VAR *x, SCIP_VAR *y)
Definition: cons_nonlinear.c:13363
SCIP_CONSNONLINEAR_BILINTERM * SCIPgetBilinTermsNonlinear(SCIP_CONSHDLR *conshdlr)
Definition: cons_nonlinear.c:13344
int SCIPgetNBilinTermsNonlinear(SCIP_CONSHDLR *conshdlr)
Definition: cons_nonlinear.c:13325
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:438
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2777
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition: misc.c:2785
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:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
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
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_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_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
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2124
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
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 SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1607
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
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:231
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:1156
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:857
void SCIPvarGetImplicVarBounds(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_Real *lb, SCIP_Real *ub)
Definition: var.c:11146
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18373
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18402
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11475
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18388
void SCIPselectDownIntPtr(int *intarray, void **ptrarray, int k, int len)
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
SCIP_Bool SCIPcliqueHasVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1141
Definition: objbenders.h:44
bilinear nonlinear handler
public methods for LP management
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:664
static SCIP_RETCODE isAcceptableRow(SCIP_SEPADATA *sepadata, SCIP_ROW *row, SCIP_VAR *var, int *currentnunknown, SCIP_Bool *acceptable)
Definition: sepa_rlt.c:1786
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:2666
static SCIP_VAR ** getAdjacentVars(SCIP_HASHMAP *adjvarmap, SCIP_VAR *var, int *nadjacentvars)
Definition: sepa_rlt.c:315
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:925
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:811
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:2823
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:1873
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:859
static SCIP_RETCODE getOriginalRows(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: sepa_rlt.c:412
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:1102
static SCIP_RETCODE createProjRow(SCIP *scip, RLT_SIMPLEROW *simplerow, SCIP_ROW *row, SCIP_SOL *sol, SCIP_Bool local)
Definition: sepa_rlt.c:2258
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:2346
static SCIP_RETCODE detectHiddenProducts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_HASHMAP *varmap)
Definition: sepa_rlt.c:1230
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:2499
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:1832
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:2113
static SCIP_RETCODE createSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:1594
static void clearVarAdjacency(SCIP *scip, SCIP_HASHMAP *adjvarmap)
Definition: sepa_rlt.c:338
static SCIP_RETCODE freeSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:368
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:449
static SCIP_RETCODE addProductVars(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR *x, SCIP_VAR *y, SCIP_HASHMAP *varmap, int nlocks)
Definition: sepa_rlt.c:548
static SCIP_RETCODE addAdjacentVars(SCIP *scip, SCIP_HASHMAP *adjvarmap, SCIP_VAR **vars)
Definition: sepa_rlt.c:241
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:998
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:2452
static void freeProjRows(SCIP *scip, RLT_SIMPLEROW **projrows, int nrows)
Definition: sepa_rlt.c:2430
static SCIP_RETCODE ensureVarsSize(SCIP *scip, SCIP_SEPADATA *sepadata, int n)
Definition: sepa_rlt.c:518
static void getBestEstimators(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators)
Definition: sepa_rlt.c:1729
reformulation-linearization technique separator
Definition: sepa_rlt.c:103
Definition: presol_gateextraction.c:106
Definition: sepa_rlt.c:157
Definition: struct_implics.h:76
Definition: struct_lp.h:136
Definition: cons_nonlinear.h:58
Definition: cons_nonlinear.h:79
SCIP_CONSNONLINEAR_AUXEXPR ** exprs
Definition: cons_nonlinear.h:84
union SCIP_ConsNonlinear_BilinTerm::@4 aux
Definition: struct_cons.h:47
Definition: struct_cons.h:127
Definition: struct_misc.h:131
Definition: struct_misc.h:138
Definition: struct_misc.h:90
Definition: intervalarith.h:54
Definition: struct_lp.h:202
Definition: struct_sepa.h:47
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70