separator for cuts generated by Reformulation-Linearization-Technique (RLT)
Definition in file sepa_rlt.c.
#include <assert.h>
#include <string.h>
#include "scip/sepa_rlt.h"
#include "scip/cons_nonlinear.h"
#include "scip/pub_lp.h"
#include "scip/expr_pow.h"
#include "scip/nlhdlr_bilinear.h"
#include "scip/cutsel_hybrid.h"
Go to the source code of this file.
Data Structures | |
struct | HashData |
struct | AdjacentVarData |
struct | RLT_SimpleRow |
Macros | |
#define | SEPA_NAME "rlt" |
#define | SEPA_DESC "reformulation-linearization-technique separator" |
#define | SEPA_PRIORITY 10 |
#define | SEPA_FREQ 0 |
#define | SEPA_MAXBOUNDDIST 1.0 |
#define | SEPA_USESSUBSCIP FALSE |
#define | SEPA_DELAY FALSE |
#define | DEFAULT_MAXUNKNOWNTERMS 0 |
#define | DEFAULT_MAXUSEDVARS 100 |
#define | DEFAULT_MAXNCUTS -1 |
#define | DEFAULT_MAXROUNDS 1 |
#define | DEFAULT_MAXROUNDSROOT 10 |
#define | DEFAULT_ONLYEQROWS FALSE |
#define | DEFAULT_ONLYCONTROWS FALSE |
#define | DEFAULT_ONLYORIGINAL TRUE |
#define | DEFAULT_USEINSUBSCIP FALSE |
#define | DEFAULT_USEPROJECTION FALSE |
#define | DEFAULT_DETECTHIDDEN FALSE |
#define | DEFAULT_HIDDENRLT FALSE |
#define | DEFAULT_ADDTOPOOL TRUE |
#define | DEFAULT_GOODSCORE 1.0 |
#define | DEFAULT_BADSCORE 0.5 |
#define | DEFAULT_OBJPARALWEIGHT 0.0 |
#define | DEFAULT_EFFICACYWEIGHT 1.0 |
#define | DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 |
#define | DEFAULT_GOODMAXPARALL 0.1 |
#define | DEFAULT_MAXPARALL 0.1 |
#define | MAXVARBOUND 1e+5 |
#define SEPA_NAME "rlt" |
Definition at line 51 of file sepa_rlt.c.
#define SEPA_DESC "reformulation-linearization-technique separator" |
Definition at line 52 of file sepa_rlt.c.
#define SEPA_PRIORITY 10 |
priority for separation
Definition at line 53 of file sepa_rlt.c.
#define SEPA_FREQ 0 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 54 of file sepa_rlt.c.
#define SEPA_MAXBOUNDDIST 1.0 |
maximal relative distance from the current node's dual bound to primal bound compared to best node's dual bound for applying separation.
Definition at line 55 of file sepa_rlt.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 57 of file sepa_rlt.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 58 of file sepa_rlt.c.
#define DEFAULT_MAXUNKNOWNTERMS 0 |
maximum number of unknown bilinear terms a row can have to be used
Definition at line 60 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_MAXUSEDVARS 100 |
maximum number of variables that will be used to compute rlt cuts
Definition at line 61 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_MAXNCUTS -1 |
maximum number of cuts that will be added per round
Definition at line 62 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_MAXROUNDS 1 |
maximum number of separation rounds per node (-1: unlimited)
Definition at line 63 of file sepa_rlt.c.
#define DEFAULT_MAXROUNDSROOT 10 |
maximum number of separation rounds in the root node (-1: unlimited)
Definition at line 64 of file sepa_rlt.c.
#define DEFAULT_ONLYEQROWS FALSE |
whether only equality rows should be used for rlt cuts
Definition at line 65 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_ONLYCONTROWS FALSE |
whether only continuous rows should be used for rlt cuts
Definition at line 66 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_ONLYORIGINAL TRUE |
whether only original variables and rows should be used for rlt cuts
Definition at line 67 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_USEINSUBSCIP FALSE |
whether the separator should also be used in sub-scips
Definition at line 68 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_USEPROJECTION FALSE |
whether the separator should first check projected rows
Definition at line 69 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_DETECTHIDDEN FALSE |
whether implicit products should be detected and separated by McCormick
Definition at line 70 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_HIDDENRLT FALSE |
whether RLT cuts should be added for hidden products
Definition at line 71 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_ADDTOPOOL TRUE |
whether globally valid RLT cuts are added to the global cut pool
Definition at line 72 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
#define DEFAULT_GOODSCORE 1.0 |
threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied
Definition at line 74 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt(), and SCIPincludeSepaZerohalf().
#define DEFAULT_BADSCORE 0.5 |
threshold for score of cut relative to best score to be discarded
Definition at line 76 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt(), and SCIPincludeSepaZerohalf().
#define DEFAULT_OBJPARALWEIGHT 0.0 |
weight of objective parallelism in cut score calculation
Definition at line 77 of file sepa_rlt.c.
#define DEFAULT_EFFICACYWEIGHT 1.0 |
weight of efficacy in cut score calculation
Definition at line 78 of file sepa_rlt.c.
#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 |
weight of directed cutoff distance in cut score calculation
Definition at line 79 of file sepa_rlt.c.
#define DEFAULT_GOODMAXPARALL 0.1 |
maximum parallelism for good cuts
Definition at line 80 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt(), and SCIPincludeSepaZerohalf().
#define DEFAULT_MAXPARALL 0.1 |
maximum parallelism for non-good cuts
Definition at line 81 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt(), and SCIPincludeSepaZerohalf().
#define MAXVARBOUND 1e+5 |
maximum allowed variable bound for computing an RLT-cut
Definition at line 83 of file sepa_rlt.c.
Referenced by addRltTerm(), computeRltCut(), and separateMcCormickImplicit().
typedef struct AdjacentVarData ADJACENTVARDATA |
Definition at line 108 of file sepa_rlt.c.
typedef struct RLT_SimpleRow RLT_SIMPLEROW |
Definition at line 167 of file sepa_rlt.c.
|
static |
returns TRUE iff both keys are equal
two variable pairs/triples are equal if the variables are equal
Definition at line 178 of file sepa_rlt.c.
References assert(), FALSE, HashData::firstrow, HashData::nvars, SCIPvarCompare(), TRUE, and HashData::vars.
|
static |
returns the hash value of the key
Definition at line 210 of file sepa_rlt.c.
References assert(), MAX, MAX3, MIN, MIN3, NULL, HashData::nvars, SCIPhashFour, SCIPvarGetIndex(), and HashData::vars.
|
static |
store a pair of adjacent variables
scip | SCIP data structure |
adjvarmap | hashmap mapping variables to their ADJACENTVARDATAs |
vars | variable pair to be stored |
Definition at line 241 of file sepa_rlt.c.
References AdjacentVarData::adjacentvars, assert(), i, AdjacentVarData::nadjacentvars, NULL, AdjacentVarData::sadjacentvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemory, SCIPensureBlockMemoryArray, SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPsortedvecFindPtr(), SCIPvarGetIndex(), and vars.
Referenced by addProductVars(), and fillRelationTables().
|
static |
returns the array of adjacent variables for a given variable
adjvarmap | hashmap mapping variables to their ADJACENTVARDATAs |
var | variable |
nadjacentvars | buffer to store the number of variables in the returned array |
Definition at line 315 of file sepa_rlt.c.
References AdjacentVarData::adjacentvars, assert(), AdjacentVarData::nadjacentvars, NULL, SCIPhashmapGetImage(), SCIPvarGetIndex(), and var.
Referenced by detectHiddenProducts(), and markRowsXj().
|
static |
frees all ADJACENTVARDATAs stored in a hashmap
scip | SCIP data structure |
adjvarmap | hashmap mapping variables to their ADJACENTVARDATAs |
Definition at line 338 of file sepa_rlt.c.
References AdjacentVarData::adjacentvars, assert(), i, NULL, AdjacentVarData::sadjacentvars, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPhashmapEntryGetImage(), SCIPhashmapGetEntry(), and SCIPhashmapGetNEntries().
Referenced by detectHiddenProducts(), and freeSepaData().
|
static |
free separator data
scip | SCIP data structure |
sepadata | separation data |
Definition at line 368 of file sepa_rlt.c.
References assert(), clearVarAdjacency(), FALSE, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPhashmapFree(), SCIPreleaseVar(), and sepadata.
Referenced by SCIP_DECL_SEPAEXITSOL().
|
static |
creates and returns rows of original linear constraints
scip | SCIP data structure |
rows | buffer to store the rows |
nrows | buffer to store the number of linear rows |
Definition at line 412 of file sepa_rlt.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetRow(), SCIPgetConss(), and SCIPgetNConss().
Referenced by detectHiddenProducts(), and SCIP_DECL_SEPAEXECLP().
|
static |
fills an array of rows suitable for RLT cut generation
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
prob_rows | problem rows |
rows | an array to be filled with suitable rows |
nrows | buffer to store the number of suitable rows |
row_to_pos | hashmap linking row indices to positions in rows |
allowlocal | are local rows allowed? |
Definition at line 449 of file sepa_rlt.c.
References FALSE, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcolIsIntegral(), SCIPhashmapSetImageInt(), SCIPisEQ(), SCIProwGetCols(), SCIProwGetIndex(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetOriginSepa(), SCIProwGetRhs(), SCIProwIsLocal(), sepadata, and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
make sure that the arrays in sepadata are large enough to store information on n variables
scip | SCIP data structure |
sepadata | separator data |
n | number of variables that we need to store |
Definition at line 518 of file sepa_rlt.c.
References assert(), SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, and sepadata.
Referenced by addProductVars().
|
static |
saves variables x and y to separator data and stores information about their connection
variables must be captured separately
scip | SCIP data structure |
sepadata | separator data |
x | x variable |
y | y variable |
varmap | hashmap linking var index to position |
nlocks | number of locks |
Definition at line 548 of file sepa_rlt.c.
References addAdjacentVars(), assert(), ensureVarsSize(), MIN, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPvarGetIndex(), sepadata, vars, x, and y.
Referenced by createSepaData(), and extractProducts().
|
static |
extract a bilinear product from two linear relations, if possible
First, the two given rows are brought to the form:
\[ a_1x + b_1w + c_1y \leq/\geq d_1,\\ a_2x + b_2w + c_2y \leq/\geq d_2, \]
where \( a_1a_2 \leq 0 \) and the first implied relation is enabled when \( x = 1 \) and the second when \( x = 0 \), and \( b_1, b_2 > 0 \), the product relation can be written as:
\[ \frac{b_1b_2w + (b_2(a_1 - d_1) + b_1d_2)x + b_1c_2y - b_1d_2}{b_1c_2 - c_1b_2} \leq/\geq xy. \]
The inequality sign in the product relation is similar to that in the given linear relations if \( b_1c_2 - c_1b_2 > 0 \) and opposite if \( b_1c_2 - c_1b_2 > 0 \).
To obtain this formula, the given relations are first multiplied by scaling factors \( \alpha \) and \( \beta \), which is necessary in order for the solution to always exist, and written as implications:
\begin{align} x = 1 & ~\Rightarrow~ \alpha b_1w + \alpha c_1y \leq/\geq \alpha(d_1 - a_1), \\ x = 0 & ~\Rightarrow~ \beta b_2w + \beta c_2y \leq/\geq \beta d_2. \end{align}
Then a linear system is solved which ensures that the coefficients of the two implications of the product relation are equal to the corresponding coefficients in the linear relations. If the product relation is written as:
\[ Ax + Bw + Cy + D \leq/\geq xy, \]
then the system is
\[ B = \alpha b_1, ~C - 1 = \alpha c_1, ~D+A = \alpha(a_1-d_1),\\ B = \beta b_2, ~C = \beta c_2, ~D = -\beta d_2. \]
scip | SCIP data structure |
sepadata | separator data |
vars_xwy | 3 variables involved in the inequalities in the order x,w,y |
coefs1 | coefficients of the first inequality (always implied, i.e. has x) |
coefs2 | coefficients of the second inequality (can be unconditional) |
d1 | side of the first inequality |
d2 | side of the second inequality |
sidetype1 | side type (lhs or rls) in the first inequality |
sidetype2 | side type (lhs or rhs) in the second inequality |
varmap | variable map |
f | the first relation is an implication x == f |
Definition at line 664 of file sepa_rlt.c.
References addProductVars(), assert(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPinsertBilinearTermImplicitNonlinear(), SCIPisRelEQ(), SCIPswapReals(), SCIPvarGetName(), SCIPvarGetType(), sepadata, w, x, and y.
Referenced by detectHiddenProducts(), detectProductsClique(), detectProductsImplbnd(), and detectProductsUnconditional().
|
static |
convert an implied bound: binvar = binval ⇒ implvar ≤/≥ implbnd into a big-M constraint
scip | SCIP data structure |
vars_xwy | variables in order x,w,y |
binvarpos | position of binvar in vars_xwy |
implvarpos | position of implvar in vars_xwy |
bndtype | type of implied bound |
binval | value of binvar which implies the bound |
implbnd | value of the implied bound |
coefs | coefficients of the big-M constraint |
side | side of the big-M constraint |
Definition at line 811 of file sepa_rlt.c.
References assert(), RLT_SimpleRow::coefs, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_Real, SCIPdebugMsg, SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by detectHiddenProducts(), and detectProductsImplbnd().
|
static |
extract products from a relation given by coefs1, vars, side1 and sidetype1 and implied bounds of the form binvar = !f ⇒ implvar ≥/≤ implbnd
scip | SCIP data structure |
sepadata | separator data |
coefs1 | coefficients of the first linear relation |
vars_xwy | variables in the order x, w, y |
side1 | side of the first relation |
sidetype1 | is the left or right hand side given for the first relation? |
binvarpos | position of the indicator variable in the vars_xwy array |
implvarpos | position of the variable that is bounded |
varmap | variable map |
f | the value of x that activates the first relation |
Definition at line 859 of file sepa_rlt.c.
References assert(), extractProducts(), i, implBndToBigM(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIP_VARTYPE_BINARY, SCIPvarGetImplicVarBounds(), SCIPvarGetType(), and sepadata.
Referenced by detectHiddenProducts().
|
static |
extract products from a relation given by coefs1, vars_xwy, side1 and sidetype1 and cliques containing vars_xwy[varpos1] and vars_xwy[varpos2]
scip | SCIP data structure |
sepadata | separator data |
coefs1 | coefficients of the first linear relation |
vars_xwy | variables of the first relation in the order x, w, y |
side1 | side of the first relation |
sidetype1 | is the left or right hand side given for the first relation? |
varpos1 | position of the first variable in the vars_xwy array |
varpos2 | position of the second variable in the vars_xwy array |
varmap | variable map |
f | the value of x that activates the first relation |
Definition at line 925 of file sepa_rlt.c.
References assert(), extractProducts(), FALSE, i, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_RIGHT, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPvarGetName(), SCIPvarGetType(), SCIPvarsHaveCommonClique(), sepadata, and TRUE.
Referenced by detectHiddenProducts().
|
static |
extract products from a relation given by coefs1, vars, side1 and sidetype1 and unconditional relations (inequalities with 2 nonzeros) containing vars[varpos1] and vars[varpos2]
scip | SCIP data structure |
sepadata | separator data |
rows | problem rows |
row_list | linked list of rows corresponding to 2 or 3 var sets |
hashtable | hashtable storing unconditional relations |
coefs1 | coefficients of the first linear relation |
vars_xwy | variables of the first relation in the order x, w, y |
side1 | side of the first relation |
sidetype1 | is the left or right hand side given for the first relation? |
varpos1 | position of the first unconditional variable in the vars_xwy array |
varpos2 | position of the second unconditional variable in the vars_xwy array |
varmap | variable map |
f | the value of x that activates the first relation |
Definition at line 998 of file sepa_rlt.c.
References assert(), extractProducts(), HashData::firstrow, NULL, HashData::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPcolGetVar(), SCIPdebugMsg, SCIPhashtableRetrieve(), SCIPisInfinity(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetIndex(), sepadata, and HashData::vars.
Referenced by detectHiddenProducts().
|
static |
finds and stores implied relations (x = f ⇒ ay + bw ≤ c, f can be 0 or 1) and 2-variable relations
Fills the following:
scip | SCIP data structure |
prob_rows | linear rows of the problem |
nrows | number of rows |
hashtable2 | hashtable to store 2-variable relations |
hashtable3 | hashtable to store implied relations |
vars_in_2rels | connections between variables that appear in 2-variable relations |
row_list | linked lists of row positions for each 2 or 3 variable set |
Definition at line 1102 of file sepa_rlt.c.
References addAdjacentVars(), assert(), HashData::firstrow, HashData::nrows, NULL, HashData::nvars, r, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPallocBuffer, SCIPcolGetVar(), SCIPdebugMsg, SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIProwGetCols(), SCIProwGetName(), SCIProwGetNNonz(), SCIPvarGetType(), and HashData::vars.
Referenced by detectHiddenProducts().
|
static |
detect bilinear products encoded in linear constraints
scip | SCIP data structure |
sepadata | separation data |
varmap | variable map |
Definition at line 1230 of file sepa_rlt.c.
References assert(), clearVarAdjacency(), detectProductsClique(), detectProductsImplbnd(), detectProductsUnconditional(), extractProducts(), fillRelationTables(), HashData::firstrow, getAdjacentVars(), getOriginalRows(), i, implBndToBigM(), MIN, NULL, nvars, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPblkmem(), SCIPcolGetVar(), SCIPdebugMsg, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableGetEntry(), SCIPhashtableGetNEntries(), SCIPisInfinity(), SCIPisZero(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNImpls(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), sepadata, and HashData::vars.
Referenced by createSepaData().
|
static |
helper method to create separation data
scip | SCIP data structure |
sepadata | separation data |
Definition at line 1594 of file sepa_rlt.c.
References addProductVars(), assert(), SCIP_ConsNonlinear_BilinTerm::aux, detectHiddenProducts(), SCIP_ConsNonlinear_BilinTerm::exprs, i, MIN, SCIP_ConsNonlinear_BilinTerm::nauxexprs, NULL, nvars, SCIP_ConsNonlinear_Auxexpr::overestimate, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcaptureVar(), SCIPgetBilinTermsNonlinear(), SCIPgetNBilinTermsNonlinear(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPselectDownIntPtr(), SCIPstatisticMessage, SCIPvarIsRelaxationOnly(), sepadata, TRUE, SCIP_ConsNonlinear_Auxexpr::underestimate, SCIP_ConsNonlinear_BilinTerm::var, x, and y.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
get the positions of the most violated auxiliary under- and overestimators for each product
-1 means no relation with given product is violated
scip | SCIP data structure |
sepadata | separator data |
sol | solution at which to evaluate the expressions |
bestunderestimators | array of indices of best underestimators for each term |
bestoverestimators | array of indices of best overestimators for each term |
Definition at line 1729 of file sepa_rlt.c.
References assert(), SCIP_ConsNonlinear_BilinTerm::exprs, i, SCIP_ConsNonlinear_BilinTerm::nauxexprs, NULL, SCIP_ConsNonlinear_Auxexpr::overestimate, SCIP_Real, SCIPevalBilinAuxExprNonlinear(), SCIPgetBilinTermsNonlinear(), SCIPgetNBilinTermsNonlinear(), SCIPgetSolVal(), SCIPisFeasGT(), sepadata, sol, SCIP_ConsNonlinear_Auxexpr::underestimate, x, and y.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
tests if a row contains too many unknown bilinear terms w.r.t. the parameters
sepadata | separation data |
row | the row to be tested |
var | the variable that is to be multiplied with row |
currentnunknown | buffer to store number of unknown terms in current row if acceptable |
acceptable | buffer to store the result |
Definition at line 1786 of file sepa_rlt.c.
References assert(), SCIP_ConsNonlinear_BilinTerm::aux, i, SCIP_ConsNonlinear_BilinTerm::nauxexprs, NULL, SCIP_Bool, SCIP_OKAY, SCIPcolGetVar(), SCIPgetBilinTermIdxNonlinear(), SCIPgetBilinTermsNonlinear(), SCIProwGetCols(), SCIProwGetNNonz(), sepadata, SCIP_ConsNonlinear_BilinTerm::var, and var.
Referenced by separateRltCuts().
|
static |
adds coefficients and constant of an auxiliary expression
the variables the pointers are pointing to must already be initialized
var1 | first product variable |
var2 | second product variable |
auxexpr | auxiliary expression to be added |
coef | coefficient of the auxiliary expression |
coefaux | pointer to add the coefficient of the auxiliary variable |
coef1 | pointer to add the coefficient of the first variable |
coef2 | pointer to add the coefficient of the second variable |
cst | pointer to add the constant |
Definition at line 1832 of file sepa_rlt.c.
References assert(), SCIP_ConsNonlinear_Auxexpr::auxvar, SCIP_ConsNonlinear_Auxexpr::coefs, RLT_SimpleRow::cst, SCIP_ConsNonlinear_Auxexpr::cst, NULL, SCIP_Real, and SCIPvarCompare().
Referenced by addRltTerm(), and separateMcCormickImplicit().
|
static |
add a linear term coef*colvar multiplied by a bound factor (var - lb(var)) or (ub(var) - var)
adds the linear term with colvar to cut and updates coefvar and cst
scip | SCIP data structure |
sepadata | separator data |
sol | the point to be separated (can be NULL) |
bestunderest | positions of most violated underestimators for each product term |
bestoverest | positions of most violated overestimators for each product term |
cut | cut to which the term is to be added |
var | multiplier variable |
colvar | row variable to be multiplied |
coef | coefficient of the bilinear term |
uselb | whether we multiply with (var - lb) or (ub - var) |
uselhs | whether to create a cut for the lhs or rhs |
local | whether local or global cuts should be computed |
computeEqCut | whether conditions are fulfilled to compute equality cuts |
coefvar | coefficient of var |
cst | buffer to store the constant part of the cut |
success | buffer to store whether cut was updated successfully |
Definition at line 1873 of file sepa_rlt.c.
References addAuxexprCoefs(), assert(), SCIP_ConsNonlinear_BilinTerm::aux, SCIP_ConsNonlinear_Auxexpr::auxvar, c, RLT_SimpleRow::cst, SCIP_ConsNonlinear_BilinTerm::exprs, FALSE, MAX, MAXVARBOUND, MIN, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddBilinMcCormick(), SCIPaddSquareLinearization(), SCIPaddSquareSecant(), SCIPaddVarToRow(), SCIPcliqueHasVar(), SCIPdebugMsg, SCIPgetBilinTermIdxNonlinear(), SCIPgetBilinTermsNonlinear(), SCIPgetSolVal(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetCliques(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), sepadata, sol, TRUE, SCIP_ConsNonlinear_BilinTerm::var, and var.
Referenced by computeRltCut().
|
static |
creates the RLT cut formed by multiplying a given row with (x - lb) or (ub - x)
In detail:
scip | SCIP data structure |
sepa | separator |
sepadata | separation data |
cut | buffer to store the cut |
row | the row that is used for the rlt cut (NULL if using projected row) |
projrow | projected row that is used for the rlt cut (NULL if using row) |
sol | the point to be separated (can be NULL) |
bestunderest | positions of most violated underestimators for each product term |
bestoverest | positions of most violated overestimators for each product term |
var | the variable that is used for the rlt cuts |
success | buffer to store whether cut was created successfully |
uselb | whether we multiply with (var - lb) or (ub - var) |
uselhs | whether to create a cut for the lhs or rhs |
local | whether local or global cuts should be computed |
computeEqCut | whether conditions are fulfilled to compute equality cuts |
useprojrow | whether to use projected row instead of normal row |
Definition at line 2113 of file sepa_rlt.c.
References addRltTerm(), assert(), RLT_SimpleRow::coefs, RLT_SimpleRow::cst, FALSE, i, RLT_SimpleRow::lhs, MAXVARBOUND, RLT_SimpleRow::name, RLT_SimpleRow::nnonz, NULL, REALABS, RLT_SimpleRow::rhs, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetDepth(), SCIPgetNLPs(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), sepadata, sol, TRUE, var, and RLT_SimpleRow::vars.
Referenced by separateRltCuts().
|
static |
store a row projected by fixing all variables that are at bound at sol; the result is a simplified row
scip | SCIP data structure |
simplerow | pointer to the simplified row |
row | row to be projected |
sol | the point to be separated (can be NULL) |
local | whether local bounds should be checked |
Definition at line 2258 of file sepa_rlt.c.
References assert(), RLT_SimpleRow::coefs, RLT_SimpleRow::cst, i, RLT_SimpleRow::lhs, RLT_SimpleRow::name, RLT_SimpleRow::nnonz, NULL, RLT_SimpleRow::rhs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), SCIPcolGetVar(), SCIPduplicateBlockMemoryArray, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPreallocBufferArray, SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), RLT_SimpleRow::size, sol, var, and RLT_SimpleRow::vars.
Referenced by createProjRows().
|
static |
free the projected row
scip | SCIP data structure |
simplerow | simplified row to be freed |
Definition at line 2322 of file sepa_rlt.c.
References assert(), RLT_SimpleRow::coefs, RLT_SimpleRow::name, NULL, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, RLT_SimpleRow::size, and RLT_SimpleRow::vars.
Referenced by freeProjRows().
|
static |
creates the projected problem
All variables that are at their bounds at the current solution are added to left and/or right hand sides as constant values.
scip | SCIP data structure |
rows | problem rows |
nrows | number of rows |
sol | the point to be separated (can be NULL) |
projrows | the projected rows to be filled |
local | are local cuts allowed? |
allcst | buffer to store whether all projected rows have only constants |
Definition at line 2346 of file sepa_rlt.c.
References assert(), createProjRow(), FALSE, i, RLT_SimpleRow::nnonz, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, sol, and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
frees the projected rows
scip | SCIP data structure |
projrows | the projected LP |
nrows | number of rows in projrows |
Definition at line 2430 of file sepa_rlt.c.
References freeProjRow(), i, and SCIPfreeBufferArray.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
mark a row for rlt cut selection
depending on the sign of the coefficient and violation, set or update mark which cut is required:
ridx | row index |
a | coefficient of x in the row |
violatedbelow | whether the relation auxexpr <= xy is violated |
violatedabove | whether the relation xy <= auxexpr is violated |
row_idcs | sparse array with indices of marked rows |
row_marks | sparse array to store the marks |
nmarked | number of marked rows |
Definition at line 2452 of file sepa_rlt.c.
References a, assert(), i, SCIP_Bool, SCIP_Real, and SCIPsortedvecFindInt().
Referenced by markRowsXj().
|
static |
mark all rows that should be multiplied by xj
scip | SCIP data structure |
sepadata | separator data |
conshdlr | nonlinear constraint handler |
sol | point to be separated (can be NULL) |
j | index of the multiplier variable in sepadata |
local | are local cuts allowed? |
row_to_pos | hashmap linking row indices to positions in array |
bestunderest | positions of most violated underestimators for each product term |
bestoverest | positions of most violated overestimators for each product term |
row_marks | sparse array storing the row marks |
row_idcs | sparse array storing the marked row positions |
nmarked | number of marked rows |
Definition at line 2499 of file sepa_rlt.c.
References a, addRowMark(), assert(), SCIP_ConsNonlinear_BilinTerm::existing, SCIP_ConsNonlinear_BilinTerm::exprs, FALSE, getAdjacentVars(), i, NULL, r, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPevalBilinAuxExprNonlinear(), SCIPgetBilinTermIdxNonlinear(), SCIPgetBilinTermsNonlinear(), SCIPgetNBilinTermsNonlinear(), SCIPgetSolVal(), SCIPhashmapExists(), SCIPisFeasEQ(), SCIPisFeasPositive(), SCIProwGetIndex(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), sepadata, sol, TRUE, SCIP_ConsNonlinear_BilinTerm::var, x, and y.
Referenced by separateRltCuts().
|
static |
adds McCormick inequalities for implicit products
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
sol | the point to be separated (can be NULL) |
bestunderestimators | indices of auxiliary underestimators with largest violation in sol |
bestoverestimators | indices of auxiliary overestimators with largest violation in sol |
result | pointer to store the result |
Definition at line 2666 of file sepa_rlt.c.
References addAuxexprCoefs(), assert(), SCIP_ConsNonlinear_BilinTerm::aux, SCIP_ConsNonlinear_Auxexpr::auxvar, cutoff, SCIP_ConsNonlinear_BilinTerm::exprs, FALSE, i, SCIP_Interval::inf, MAX, MAXVARBOUND, MIN, RLT_SimpleRow::name, NULL, SCIP_ConsNonlinear_Auxexpr::overestimate, REALABS, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddBilinMcCormick(), SCIPaddRow(), SCIPaddVarToRow(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPevalBilinAuxExprNonlinear(), SCIPgetBilinTermsNonlinear(), SCIPgetNBilinTermsNonlinear(), SCIPgetNLPs(), SCIPgetRowFeasibility(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPreleaseRow(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), sepadata, sol, SCIP_Interval::sup, TRUE, SCIP_ConsNonlinear_Auxexpr::underestimate, x, and y.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
builds and adds the RLT cuts
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
conshdlr | nonlinear constraint handler |
sol | the point to be separated (can be NULL) |
row_to_pos | hashmap linking row indices to positions in array |
projrows | projected rows |
rows | problem rows |
nrows | number of problem rows |
allowlocal | are local cuts allowed? |
bestunderestimators | indices of auxiliary underestimators with largest violation in sol |
bestoverestimators | indices of auxiliary overestimators with largest violation in sol |
result | buffer to store whether separation was successful |
Definition at line 2823 of file sepa_rlt.c.
References assert(), computeRltCut(), FALSE, i, isAcceptableRow(), markRowsXj(), RLT_SimpleRow::nnonz, NULL, r, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddRow(), SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeCleanBufferArray, SCIPgetRowFeasibility(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisEQ(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPprintRow(), SCIPreallocBufferArray, SCIPreleaseRow(), SCIProwGetIndex(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPselectCutsHybrid(), SCIPvarGetName(), sepadata, sol, and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 3069 of file sepa_rlt.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaRlt(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 3083 of file sepa_rlt.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadata.
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 3102 of file sepa_rlt.c.
References assert(), freeSepaData(), NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), SCIPsepaGetName(), SEPA_NAME, and sepadata.
|
static |
LP solution separation method of separator
Definition at line 3121 of file sepa_rlt.c.
References assert(), createProjRows(), createSepaData(), depth, FALSE, freeProjRows(), getBestEstimators(), getOriginalRows(), ncalls, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNBilinTermsNonlinear(), SCIPgetSubscipDepth(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPinProbing(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SEPA_NAME, sepadata, separateMcCormickImplicit(), separateRltCuts(), and storeSuitableRows().