Detailed Description
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 |
Typedefs | |
typedef struct HashData | HASHDATA |
typedef struct AdjacentVarData | ADJACENTVARDATA |
typedef struct RLT_SimpleRow | RLT_SIMPLEROW |
Functions | |
static | SCIP_DECL_HASHKEYEQ (hashdataKeyEqConss) |
static | SCIP_DECL_HASHKEYVAL (hashdataKeyValConss) |
static SCIP_RETCODE | addAdjacentVars (SCIP *scip, SCIP_HASHMAP *adjvarmap, SCIP_VAR **vars) |
static SCIP_VAR ** | getAdjacentVars (SCIP_HASHMAP *adjvarmap, SCIP_VAR *var, int *nadjacentvars) |
static void | clearVarAdjacency (SCIP *scip, SCIP_HASHMAP *adjvarmap) |
static SCIP_RETCODE | freeSepaData (SCIP *scip, SCIP_SEPADATA *sepadata) |
static SCIP_RETCODE | getOriginalRows (SCIP *scip, SCIP_ROW ***rows, int *nrows) |
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) |
static SCIP_RETCODE | ensureVarsSize (SCIP *scip, SCIP_SEPADATA *sepadata, int n) |
static SCIP_RETCODE | addProductVars (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR *x, SCIP_VAR *y, SCIP_HASHMAP *varmap, int nlocks) |
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) |
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) |
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) |
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) |
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) |
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) |
static SCIP_RETCODE | detectHiddenProducts (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_HASHMAP *varmap) |
static SCIP_RETCODE | createSepaData (SCIP *scip, SCIP_SEPADATA *sepadata) |
static void | getBestEstimators (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators) |
static SCIP_RETCODE | isAcceptableRow (SCIP_SEPADATA *sepadata, SCIP_ROW *row, SCIP_VAR *var, int *currentnunknown, SCIP_Bool *acceptable) |
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) |
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) |
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) |
static SCIP_RETCODE | createProjRow (SCIP *scip, RLT_SIMPLEROW *simplerow, SCIP_ROW *row, SCIP_SOL *sol, SCIP_Bool local) |
static void | freeProjRow (SCIP *scip, RLT_SIMPLEROW *simplerow) |
static SCIP_RETCODE | createProjRows (SCIP *scip, SCIP_ROW **rows, int nrows, SCIP_SOL *sol, RLT_SIMPLEROW **projrows, SCIP_Bool local, SCIP_Bool *allcst) |
static void | freeProjRows (SCIP *scip, RLT_SIMPLEROW **projrows, int nrows) |
static void | addRowMark (int ridx, SCIP_Real a, SCIP_Bool violatedbelow, SCIP_Bool violatedabove, int *row_idcs, unsigned int *row_marks, int *nmarked) |
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) |
static SCIP_RETCODE | separateMcCormickImplicit (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators, SCIP_RESULT *result) |
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) |
static | SCIP_DECL_SEPACOPY (sepaCopyRlt) |
static | SCIP_DECL_SEPAFREE (sepaFreeRlt) |
static | SCIP_DECL_SEPAEXITSOL (sepaExitsolRlt) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpRlt) |
SCIP_RETCODE | SCIPincludeSepaRlt (SCIP *scip) |
Macro Definition Documentation
◆ SEPA_NAME
#define SEPA_NAME "rlt" |
Definition at line 51 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ SEPA_DESC
#define SEPA_DESC "reformulation-linearization-technique separator" |
Definition at line 52 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ SEPA_PRIORITY
#define SEPA_PRIORITY 10 |
priority for separation
Definition at line 53 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ SEPA_FREQ
#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.
Referenced by SCIPincludeSepaRlt().
◆ SEPA_MAXBOUNDDIST
#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.
Referenced by SCIPincludeSepaRlt().
◆ SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 58 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ SEPA_DELAY
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 59 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_MAXUNKNOWNTERMS
#define DEFAULT_MAXUNKNOWNTERMS 0 |
maximum number of unknown bilinear terms a row can have to be used
Definition at line 61 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_MAXUSEDVARS
#define DEFAULT_MAXUSEDVARS 100 |
maximum number of variables that will be used to compute rlt cuts
Definition at line 62 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_MAXNCUTS
#define DEFAULT_MAXNCUTS -1 |
maximum number of cuts that will be added per round
Definition at line 63 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS 1 |
maximum number of separation rounds per node (-1: unlimited)
Definition at line 64 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT 10 |
maximum number of separation rounds in the root node (-1: unlimited)
Definition at line 65 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_ONLYEQROWS
#define DEFAULT_ONLYEQROWS FALSE |
whether only equality rows should be used for rlt cuts
Definition at line 66 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_ONLYCONTROWS
#define DEFAULT_ONLYCONTROWS FALSE |
whether only continuous rows should be used for rlt cuts
Definition at line 67 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_ONLYORIGINAL
#define DEFAULT_ONLYORIGINAL TRUE |
whether only original variables and rows should be used for rlt cuts
Definition at line 68 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_USEINSUBSCIP
#define DEFAULT_USEINSUBSCIP FALSE |
whether the separator should also be used in sub-scips
Definition at line 69 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_USEPROJECTION
#define DEFAULT_USEPROJECTION FALSE |
whether the separator should first check projected rows
Definition at line 70 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_DETECTHIDDEN
#define DEFAULT_DETECTHIDDEN FALSE |
whether implicit products should be detected and separated by McCormick
Definition at line 71 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_HIDDENRLT
#define DEFAULT_HIDDENRLT FALSE |
whether RLT cuts should be added for hidden products
Definition at line 72 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_ADDTOPOOL
#define DEFAULT_ADDTOPOOL TRUE |
whether globally valid RLT cuts are added to the global cut pool
Definition at line 73 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_GOODSCORE
#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 75 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_BADSCORE
#define DEFAULT_BADSCORE 0.5 |
threshold for score of cut relative to best score to be discarded
Definition at line 78 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_OBJPARALWEIGHT
#define DEFAULT_OBJPARALWEIGHT 0.0 |
weight of objective parallelism in cut score calculation
Definition at line 79 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_EFFICACYWEIGHT
#define DEFAULT_EFFICACYWEIGHT 1.0 |
weight of efficacy in cut score calculation
Definition at line 80 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_DIRCUTOFFDISTWEIGHT
#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 |
weight of directed cutoff distance in cut score calculation
Definition at line 81 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_GOODMAXPARALL
#define DEFAULT_GOODMAXPARALL 0.1 |
maximum parallelism for good cuts
Definition at line 82 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ DEFAULT_MAXPARALL
#define DEFAULT_MAXPARALL 0.1 |
maximum parallelism for non-good cuts
Definition at line 83 of file sepa_rlt.c.
Referenced by SCIPincludeSepaRlt().
◆ MAXVARBOUND
#define MAXVARBOUND 1e+5 |
maximum allowed variable bound for computing an RLT-cut
Definition at line 85 of file sepa_rlt.c.
Referenced by addRltTerm(), computeRltCut(), and separateMcCormickImplicit().
Typedef Documentation
◆ HASHDATA
Definition at line 99 of file sepa_rlt.c.
◆ ADJACENTVARDATA
typedef struct AdjacentVarData ADJACENTVARDATA |
Definition at line 110 of file sepa_rlt.c.
◆ RLT_SIMPLEROW
typedef struct RLT_SimpleRow RLT_SIMPLEROW |
Definition at line 169 of file sepa_rlt.c.
Function Documentation
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff both keys are equal
two variable pairs/triples are equal if the variables are equal
Definition at line 180 of file sepa_rlt.c.
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns the hash value of the key
Definition at line 212 of file sepa_rlt.c.
◆ addAdjacentVars()
|
static |
store a pair of adjacent variables
- Parameters
-
scip SCIP data structure adjvarmap hashmap mapping variables to their ADJACENTVARDATAs vars variable pair to be stored
Definition at line 243 of file sepa_rlt.c.
References AdjacentVarData::adjacentvars, getAdjacentVars(), AdjacentVarData::nadjacentvars, NULL, AdjacentVarData::sadjacentvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemory, SCIPensureBlockMemoryArray, SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPsortedvecFindPtr(), and SCIPvarGetIndex().
Referenced by addProductVars(), and fillRelationTables().
◆ getAdjacentVars()
|
static |
returns the array of adjacent variables for a given variable
- Parameters
-
adjvarmap hashmap mapping variables to their ADJACENTVARDATAs var variable nadjacentvars buffer to store the number of variables in the returned array
Definition at line 317 of file sepa_rlt.c.
References AdjacentVarData::adjacentvars, clearVarAdjacency(), AdjacentVarData::nadjacentvars, NULL, SCIPhashmapGetImage(), and SCIPvarGetIndex().
Referenced by addAdjacentVars(), detectHiddenProducts(), and markRowsXj().
◆ clearVarAdjacency()
|
static |
frees all ADJACENTVARDATAs stored in a hashmap
- Parameters
-
scip SCIP data structure adjvarmap hashmap mapping variables to their ADJACENTVARDATAs
Definition at line 340 of file sepa_rlt.c.
References AdjacentVarData::adjacentvars, freeSepaData(), NULL, AdjacentVarData::sadjacentvars, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPhashmapEntryGetImage(), SCIPhashmapGetEntry(), and SCIPhashmapGetNEntries().
Referenced by detectHiddenProducts(), freeSepaData(), and getAdjacentVars().
◆ freeSepaData()
|
static |
free separator data
- Parameters
-
scip SCIP data structure sepadata separation data
Definition at line 370 of file sepa_rlt.c.
References clearVarAdjacency(), FALSE, getOriginalRows(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseVar().
Referenced by clearVarAdjacency().
◆ getOriginalRows()
|
static |
creates and returns rows of original linear constraints
- Parameters
-
scip SCIP data structure rows buffer to store the rows nrows buffer to store the number of linear rows
Definition at line 414 of file sepa_rlt.c.
References HashData::nrows, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetRow(), SCIPgetConss(), SCIPgetNConss(), and storeSuitableRows().
Referenced by detectHiddenProducts(), and freeSepaData().
◆ storeSuitableRows()
|
static |
fills an array of rows suitable for RLT cut generation
- Parameters
-
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 451 of file sepa_rlt.c.
References ensureVarsSize(), FALSE, HashData::nrows, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcolIsIntegral(), SCIPhashmapSetImageInt(), SCIPisEQ(), SCIProwGetCols(), SCIProwGetIndex(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetOriginSepa(), SCIProwGetRhs(), SCIProwIsLocal(), and TRUE.
Referenced by getOriginalRows().
◆ ensureVarsSize()
|
static |
make sure that the arrays in sepadata are large enough to store information on n variables
- Parameters
-
scip SCIP data structure sepadata separator data n number of variables that we need to store
Definition at line 520 of file sepa_rlt.c.
References addProductVars(), SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addProductVars(), and storeSuitableRows().
◆ addProductVars()
|
static |
saves variables x and y to separator data and stores information about their connection
variables must be captured separately
- Parameters
-
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 550 of file sepa_rlt.c.
References addAdjacentVars(), ensureVarsSize(), extractProducts(), MIN, NULL, HashData::nvars, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPvarGetIndex(), HashData::vars, x, and y.
Referenced by createSepaData(), ensureVarsSize(), and extractProducts().
◆ 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. \]
- Parameters
-
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 666 of file sepa_rlt.c.
References addProductVars(), implBndToBigM(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPinsertBilinearTermImplicitNonlinear(), SCIPisRelEQ(), SCIPswapReals(), SCIPvarGetName(), SCIPvarGetType(), w, x, and y.
Referenced by addProductVars(), detectHiddenProducts(), detectProductsClique(), detectProductsImplbnd(), and detectProductsUnconditional().
◆ implBndToBigM()
|
static |
convert an implied bound: binvar
= binval
⇒ implvar
≤/≥ implbnd
into a big-M constraint
- Parameters
-
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 813 of file sepa_rlt.c.
References RLT_SimpleRow::coefs, detectProductsImplbnd(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_Real, SCIPdebugMsg, SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by detectHiddenProducts(), detectProductsImplbnd(), and extractProducts().
◆ detectProductsImplbnd()
|
static |
extract products from a relation given by coefs1, vars, side1 and sidetype1 and implied bounds of the form binvar
= !f
⇒ implvar
≥/≤ implbnd
- Parameters
-
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 861 of file sepa_rlt.c.
References detectProductsClique(), extractProducts(), 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(), and SCIPvarGetType().
Referenced by detectHiddenProducts(), and implBndToBigM().
◆ detectProductsClique()
|
static |
extract products from a relation given by coefs1
, vars_xwy
, side1
and sidetype1
and cliques containing vars_xwy[varpos1]
and vars_xwy[varpos2]
- Parameters
-
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 927 of file sepa_rlt.c.
References detectProductsUnconditional(), extractProducts(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_RIGHT, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPvarGetName(), SCIPvarGetType(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by detectHiddenProducts(), and detectProductsImplbnd().
◆ detectProductsUnconditional()
|
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]
- Parameters
-
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 1000 of file sepa_rlt.c.
References extractProducts(), fillRelationTables(), HashData::firstrow, NULL, HashData::nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPcolGetVar(), SCIPdebugMsg, SCIPhashtableRetrieve(), SCIPisInfinity(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetIndex(), and HashData::vars.
Referenced by detectHiddenProducts(), and detectProductsClique().
◆ fillRelationTables()
|
static |
finds and stores implied relations (x = f ⇒ ay + bw ≤ c, f can be 0 or 1) and 2-variable relations
Fills the following:
- An array of variables that participate in two variable relations; for each such variable, ADJACENTVARDATA containing an array of variables that participate in two variable relations together with it; and a hashmap mapping variables to ADJACENTVARDATAs.
- Hashtables storing hashdata objects with the two or three variables and the position of the first row in the
prob_rows
array, which in combination with the linked list (described below) will allow access to all rows that depend only on the corresponding variables. - Linked lists of row indices. Each list corresponds to a pair or triple of variables and contains positions of rows which depend only on those variables. All lists are stored in
row_list
, an array of lengthnrows
, which is possible because each row belongs to at most one list. The array indices ofrow_list
represent the positions of rows inprob_rows
, and a value in therow_list
array represents the next index in the list (-1 if there is no next list element). The first index of each list is stored in one of the hashdata objects as firstrow.
- Parameters
-
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 1104 of file sepa_rlt.c.
References addAdjacentVars(), detectHiddenProducts(), 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(), and detectProductsUnconditional().
◆ detectHiddenProducts()
|
static |
detect bilinear products encoded in linear constraints
- Parameters
-
scip SCIP data structure sepadata separation data varmap variable map
Definition at line 1232 of file sepa_rlt.c.
References clearVarAdjacency(), createSepaData(), detectProductsClique(), detectProductsImplbnd(), detectProductsUnconditional(), extractProducts(), fillRelationTables(), HashData::firstrow, getAdjacentVars(), getOriginalRows(), implBndToBigM(), MIN, HashData::nrows, NULL, HashData::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(), and HashData::vars.
Referenced by createSepaData(), and fillRelationTables().
◆ createSepaData()
|
static |
helper method to create separation data
- Parameters
-
scip SCIP data structure sepadata separation data
Definition at line 1596 of file sepa_rlt.c.
References addProductVars(), SCIP_ConsNonlinear_BilinTerm::aux, detectHiddenProducts(), SCIP_ConsNonlinear_BilinTerm::exprs, getBestEstimators(), MIN, SCIP_ConsNonlinear_BilinTerm::nauxexprs, NULL, HashData::nvars, SCIP_ConsNonlinear_Auxexpr::overestimate, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcaptureVar(), SCIPgetBilinTermsNonlinear(), SCIPgetNBilinTermsNonlinear(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPselectDownIntPtr(), SCIPstatisticMessage, SCIPvarIsRelaxationOnly(), TRUE, SCIP_ConsNonlinear_Auxexpr::underestimate, and SCIP_ConsNonlinear_BilinTerm::var.
Referenced by detectHiddenProducts().
◆ getBestEstimators()
|
static |
get the positions of the most violated auxiliary under- and overestimators for each product
-1 means no relation with given product is violated
- Parameters
-
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 1731 of file sepa_rlt.c.
References SCIP_ConsNonlinear_BilinTerm::exprs, isAcceptableRow(), SCIP_ConsNonlinear_BilinTerm::nauxexprs, NULL, SCIP_ConsNonlinear_Auxexpr::overestimate, SCIP_Real, SCIPevalBilinAuxExprNonlinear(), SCIPgetBilinTermsNonlinear(), SCIPgetNBilinTermsNonlinear(), SCIPgetSolVal(), SCIPisFeasGT(), and SCIP_ConsNonlinear_Auxexpr::underestimate.
Referenced by createSepaData().
◆ isAcceptableRow()
|
static |
tests if a row contains too many unknown bilinear terms w.r.t. the parameters
- 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 1788 of file sepa_rlt.c.
References addAuxexprCoefs(), SCIP_ConsNonlinear_BilinTerm::aux, SCIP_ConsNonlinear_BilinTerm::nauxexprs, NULL, SCIP_OKAY, SCIPcolGetVar(), SCIPgetBilinTermIdxNonlinear(), SCIPgetBilinTermsNonlinear(), SCIProwGetCols(), SCIProwGetNNonz(), and SCIP_ConsNonlinear_BilinTerm::var.
Referenced by getBestEstimators(), and separateRltCuts().
◆ addAuxexprCoefs()
|
static |
adds coefficients and constant of an auxiliary expression
the variables the pointers are pointing to must already be initialized
- Parameters
-
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 1834 of file sepa_rlt.c.
References addRltTerm(), SCIP_ConsNonlinear_Auxexpr::auxvar, SCIP_ConsNonlinear_Auxexpr::coefs, SCIP_ConsNonlinear_Auxexpr::cst, RLT_SimpleRow::cst, NULL, and SCIPvarCompare().
Referenced by addRltTerm(), isAcceptableRow(), and separateMcCormickImplicit().
◆ addRltTerm()
|
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
- Parameters
-
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 1875 of file sepa_rlt.c.
References addAuxexprCoefs(), SCIP_ConsNonlinear_BilinTerm::aux, SCIP_ConsNonlinear_Auxexpr::auxvar, computeRltCut(), 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(), TRUE, and SCIP_ConsNonlinear_BilinTerm::var.
Referenced by addAuxexprCoefs(), and computeRltCut().
◆ computeRltCut()
|
static |
creates the RLT cut formed by multiplying a given row with (x - lb) or (ub - x)
In detail:
- The row is multiplied either with (x - lb(x)) or with (ub(x) - x), depending on parameter
uselb
, or by x if this is an equality cut - The (inequality) cut is computed either for lhs or rhs, depending on parameter
uselhs
. - Terms for which no auxiliary variable and no clique relation exists are replaced by either McCormick, secants, or gradient linearization cuts.
- Parameters
-
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 2115 of file sepa_rlt.c.
References addRltTerm(), RLT_SimpleRow::coefs, createProjRow(), RLT_SimpleRow::cst, FALSE, RLT_SimpleRow::lhs, MAXVARBOUND, RLT_SimpleRow::name, RLT_SimpleRow::nnonz, NULL, REALABS, RLT_SimpleRow::rhs, 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(), TRUE, and RLT_SimpleRow::vars.
Referenced by addRltTerm(), and separateRltCuts().
◆ createProjRow()
|
static |
store a row projected by fixing all variables that are at bound at sol; the result is a simplified row
- Parameters
-
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 2260 of file sepa_rlt.c.
References RLT_SimpleRow::coefs, RLT_SimpleRow::cst, freeProjRow(), RLT_SimpleRow::lhs, RLT_SimpleRow::name, RLT_SimpleRow::nnonz, NULL, RLT_SimpleRow::rhs, 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, and RLT_SimpleRow::vars.
Referenced by computeRltCut(), and createProjRows().
◆ freeProjRow()
|
static |
free the projected row
- Parameters
-
scip SCIP data structure simplerow simplified row to be freed
Definition at line 2324 of file sepa_rlt.c.
References RLT_SimpleRow::coefs, createProjRows(), RLT_SimpleRow::name, NULL, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, RLT_SimpleRow::size, and RLT_SimpleRow::vars.
Referenced by createProjRow(), and freeProjRows().
◆ createProjRows()
|
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.
- Parameters
-
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 2348 of file sepa_rlt.c.
References RLT_SimpleRow::coefs, createProjRow(), RLT_SimpleRow::cst, FALSE, freeProjRows(), RLT_SimpleRow::lhs, RLT_SimpleRow::nnonz, HashData::nrows, NULL, REALABS, RLT_SimpleRow::rhs, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPinfoMessage(), SCIPisInfinity(), SCIPvarGetName(), and TRUE.
Referenced by freeProjRow().
◆ freeProjRows()
|
static |
frees the projected rows
- Parameters
-
scip SCIP data structure projrows the projected LP nrows number of rows in projrows
Definition at line 2432 of file sepa_rlt.c.
References addRowMark(), freeProjRow(), HashData::nrows, and SCIPfreeBufferArray.
Referenced by createProjRows().
◆ addRowMark()
|
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:
- 1 - cuts for axy < aw case,
- 2 - cuts for axy > aw case,
- 3 - cuts for both cases
- Parameters
-
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 2454 of file sepa_rlt.c.
References a, markRowsXj(), SCIP_Bool, and SCIPsortedvecFindInt().
Referenced by freeProjRows(), and markRowsXj().
◆ markRowsXj()
|
static |
mark all rows that should be multiplied by xj
- Parameters
-
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 2501 of file sepa_rlt.c.
References a, addRowMark(), SCIP_ConsNonlinear_BilinTerm::existing, SCIP_ConsNonlinear_BilinTerm::exprs, FALSE, getAdjacentVars(), 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(), separateMcCormickImplicit(), TRUE, and SCIP_ConsNonlinear_BilinTerm::var.
Referenced by addRowMark(), and separateRltCuts().
◆ separateMcCormickImplicit()
|
static |
adds McCormick inequalities for implicit products
- Parameters
-
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 2668 of file sepa_rlt.c.
References addAuxexprCoefs(), SCIP_ConsNonlinear_BilinTerm::aux, SCIP_ConsNonlinear_Auxexpr::auxvar, SCIP_ConsNonlinear_BilinTerm::exprs, FALSE, SCIP_Interval::inf, MAX, MAXVARBOUND, MIN, RLT_SimpleRow::name, NULL, SCIP_ConsNonlinear_Auxexpr::overestimate, REALABS, 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(), separateRltCuts(), SCIP_Interval::sup, TRUE, and SCIP_ConsNonlinear_Auxexpr::underestimate.
Referenced by markRowsXj().
◆ separateRltCuts()
|
static |
builds and adds the RLT cuts
- Parameters
-
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 2825 of file sepa_rlt.c.
References computeRltCut(), FALSE, isAcceptableRow(), markRowsXj(), RLT_SimpleRow::nnonz, HashData::nrows, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_SEPACOPY(), 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(), and TRUE.
Referenced by separateMcCormickImplicit().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 3071 of file sepa_rlt.c.
Referenced by separateRltCuts().
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 3085 of file sepa_rlt.c.
◆ SCIP_DECL_SEPAEXITSOL()
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 3104 of file sepa_rlt.c.
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 3123 of file sepa_rlt.c.