Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

separator for cuts generated by Reformulation-Linearization-Technique (RLT)

Author
Fabian Wegscheider
Ksenia Bestuzheva

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 42 of file sepa_rlt.c.

Referenced by SCIPincludeSepaRlt().

◆ SEPA_DESC

#define SEPA_DESC   "reformulation-linearization-technique separator"

Definition at line 43 of file sepa_rlt.c.

Referenced by SCIPincludeSepaRlt().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   10

priority for separation

Definition at line 44 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 45 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 46 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 49 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 50 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 52 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 53 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 54 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 55 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 56 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 57 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 58 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 59 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 60 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 61 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 62 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 63 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 64 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 66 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 69 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 70 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 71 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 72 of file sepa_rlt.c.

Referenced by SCIPincludeSepaRlt().

◆ DEFAULT_GOODMAXPARALL

#define DEFAULT_GOODMAXPARALL   0.1

maximum parallelism for good cuts

Definition at line 73 of file sepa_rlt.c.

Referenced by SCIPincludeSepaRlt().

◆ DEFAULT_MAXPARALL

#define DEFAULT_MAXPARALL   0.1

maximum parallelism for non-good cuts

Definition at line 74 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 76 of file sepa_rlt.c.

Referenced by addRltTerm(), computeRltCut(), and separateMcCormickImplicit().

Typedef Documentation

◆ HASHDATA

typedef struct HashData HASHDATA

Definition at line 90 of file sepa_rlt.c.

◆ ADJACENTVARDATA

Definition at line 101 of file sepa_rlt.c.

◆ RLT_SIMPLEROW

typedef struct RLT_SimpleRow RLT_SIMPLEROW

Definition at line 160 of file sepa_rlt.c.

Function Documentation

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashdataKeyEqConss  )
static

returns TRUE iff both keys are equal

two variable pairs/triples are equal if the variables are equal

Definition at line 171 of file sepa_rlt.c.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashdataKeyValConss  )
static

returns the hash value of the key

Definition at line 203 of file sepa_rlt.c.

◆ addAdjacentVars()

static SCIP_RETCODE addAdjacentVars ( SCIP scip,
SCIP_HASHMAP adjvarmap,
SCIP_VAR **  vars 
)
static

store a pair of adjacent variables

Parameters
scipSCIP data structure
adjvarmaphashmap mapping variables to their ADJACENTVARDATAs
varsvariable pair to be stored

Definition at line 234 of file sepa_rlt.c.

References AdjacentVarData::adjacentvars, FALSE, getAdjacentVars(), AdjacentVarData::nadjacentvars, NULL, AdjacentVarData::sadjacentvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBlockMemory, SCIPensureBlockMemoryArray, SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPsortedvecFindPtr(), and SCIPvarGetIndex().

Referenced by addProductVars(), and fillRelationTables().

◆ getAdjacentVars()

static SCIP_VAR** getAdjacentVars ( SCIP_HASHMAP adjvarmap,
SCIP_VAR var,
int *  nadjacentvars 
)
static

returns the array of adjacent variables for a given variable

Parameters
adjvarmaphashmap mapping variables to their ADJACENTVARDATAs
varvariable
nadjacentvarsbuffer to store the number of variables in the returned array

Definition at line 302 of file sepa_rlt.c.

References AdjacentVarData::adjacentvars, clearVarAdjacency(), AdjacentVarData::nadjacentvars, NULL, SCIPhashmapGetImage(), and SCIPvarGetIndex().

Referenced by addAdjacentVars(), detectHiddenProducts(), and markRowsXj().

◆ clearVarAdjacency()

static void clearVarAdjacency ( SCIP scip,
SCIP_HASHMAP adjvarmap 
)
static

frees all ADJACENTVARDATAs stored in a hashmap

Parameters
scipSCIP data structure
adjvarmaphashmap mapping variables to their ADJACENTVARDATAs

Definition at line 325 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 SCIP_RETCODE freeSepaData ( SCIP scip,
SCIP_SEPADATA sepadata 
)
static

free separator data

Parameters
scipSCIP data structure
sepadataseparation data

Definition at line 355 of file sepa_rlt.c.

References clearVarAdjacency(), FALSE, getOriginalRows(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseVar().

Referenced by clearVarAdjacency().

◆ getOriginalRows()

static SCIP_RETCODE getOriginalRows ( SCIP scip,
SCIP_ROW ***  rows,
int *  nrows 
)
static

creates and returns rows of original linear constraints

Parameters
scipSCIP data structure
rowsbuffer to store the rows
nrowsbuffer to store the number of linear rows

Definition at line 399 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 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

fills an array of rows suitable for RLT cut generation

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
prob_rowsproblem rows
rowsan array to be filled with suitable rows
nrowsbuffer to store the number of suitable rows
row_to_poshashmap linking row indices to positions in rows
allowlocalare local rows allowed?

Definition at line 436 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 SCIP_RETCODE ensureVarsSize ( SCIP scip,
SCIP_SEPADATA sepadata,
int  n 
)
static

make sure that the arrays in sepadata are large enough to store information on n variables

Parameters
scipSCIP data structure
sepadataseparator data
nnumber of variables that we need to store

Definition at line 505 of file sepa_rlt.c.

References addProductVars(), SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by addProductVars(), and storeSuitableRows().

◆ addProductVars()

static SCIP_RETCODE addProductVars ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_VAR x,
SCIP_VAR y,
SCIP_HASHMAP varmap,
int  nlocks 
)
static

saves variables x and y to separator data and stores information about their connection

variables must be captured separately

Parameters
scipSCIP data structure
sepadataseparator data
xx variable
yy variable
varmaphashmap linking var index to position
nlocksnumber of locks

Definition at line 535 of file sepa_rlt.c.

References addAdjacentVars(), ensureVarsSize(), extractProducts(), 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 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

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
scipSCIP data structure
sepadataseparator data
vars_xwy3 variables involved in the inequalities in the order x,w,y
coefs1coefficients of the first inequality (always implied, i.e. has x)
coefs2coefficients of the second inequality (can be unconditional)
d1side of the first inequality
d2side of the second inequality
sidetype1side type (lhs or rls) in the first inequality
sidetype2side type (lhs or rhs) in the second inequality
varmapvariable map
fthe first relation is an implication x == f

Definition at line 651 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 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

convert an implied bound: binvar = binvalimplvar ≤/≥ implbnd into a big-M constraint

Parameters
scipSCIP data structure
vars_xwyvariables in order x,w,y
binvarposposition of binvar in vars_xwy
implvarposposition of implvar in vars_xwy
bndtypetype of implied bound
binvalvalue of binvar which implies the bound
implbndvalue of the implied bound
coefscoefficients of the big-M constraint
sideside of the big-M constraint

Definition at line 798 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 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

extract products from a relation given by coefs1, vars, side1 and sidetype1 and implied bounds of the form binvar = !fimplvar ≥/≤ implbnd

Parameters
scipSCIP data structure
sepadataseparator data
coefs1coefficients of the first linear relation
vars_xwyvariables in the order x, w, y
side1side of the first relation
sidetype1is the left or right hand side given for the first relation?
binvarposposition of the indicator variable in the vars_xwy array
implvarposposition of the variable that is bounded
varmapvariable map
fthe value of x that activates the first relation

Definition at line 846 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 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

extract products from a relation given by coefs1, vars_xwy, side1 and sidetype1 and cliques containing vars_xwy[varpos1] and vars_xwy[varpos2]

Parameters
scipSCIP data structure
sepadataseparator data
coefs1coefficients of the first linear relation
vars_xwyvariables of the first relation in the order x, w, y
side1side of the first relation
sidetype1is the left or right hand side given for the first relation?
varpos1position of the first variable in the vars_xwy array
varpos2position of the second variable in the vars_xwy array
varmapvariable map
fthe value of x that activates the first relation

Definition at line 912 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 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

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
scipSCIP data structure
sepadataseparator data
rowsproblem rows
row_listlinked list of rows corresponding to 2 or 3 var sets
hashtablehashtable storing unconditional relations
coefs1coefficients of the first linear relation
vars_xwyvariables of the first relation in the order x, w, y
side1side of the first relation
sidetype1is the left or right hand side given for the first relation?
varpos1position of the first unconditional variable in the vars_xwy array
varpos2position of the second unconditional variable in the vars_xwy array
varmapvariable map
fthe value of x that activates the first relation

Definition at line 985 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 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

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 length nrows, which is possible because each row belongs to at most one list. The array indices of row_list represent the positions of 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 list element). The first index of each list is stored in one of the hashdata objects as firstrow.
Parameters
scipSCIP data structure
prob_rowslinear rows of the problem
nrowsnumber of rows
hashtable2hashtable to store 2-variable relations
hashtable3hashtable to store implied relations
vars_in_2relsconnections between variables that appear in 2-variable relations
row_listlinked lists of row positions for each 2 or 3 variable set

Definition at line 1089 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 SCIP_RETCODE detectHiddenProducts ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_HASHMAP varmap 
)
static

◆ createSepaData()

◆ getBestEstimators()

static void getBestEstimators ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_SOL sol,
int *  bestunderestimators,
int *  bestoverestimators 
)
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
scipSCIP data structure
sepadataseparator data
solsolution at which to evaluate the expressions
bestunderestimatorsarray of indices of best underestimators for each term
bestoverestimatorsarray of indices of best overestimators for each term

Definition at line 1714 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 SCIP_RETCODE isAcceptableRow ( SCIP_SEPADATA sepadata,
SCIP_ROW row,
SCIP_VAR var,
int *  currentnunknown,
SCIP_Bool acceptable 
)
static

tests if a row contains too many unknown bilinear terms w.r.t. the parameters

Parameters
sepadataseparation data
rowthe row to be tested
varthe variable that is to be multiplied with row
currentnunknownbuffer to store number of unknown terms in current row if acceptable
acceptablebuffer to store the result

Definition at line 1771 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 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

adds coefficients and constant of an auxiliary expression

the variables the pointers are pointing to must already be initialized

Parameters
var1first product variable
var2second product variable
auxexprauxiliary expression to be added
coefcoefficient of the auxiliary expression
coefauxpointer to add the coefficient of the auxiliary variable
coef1pointer to add the coefficient of the first variable
coef2pointer to add the coefficient of the second variable
cstpointer to add the constant

Definition at line 1817 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 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

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
scipSCIP data structure
sepadataseparator data
solthe point to be separated (can be NULL)
bestunderestpositions of most violated underestimators for each product term
bestoverestpositions of most violated overestimators for each product term
cutcut to which the term is to be added
varmultiplier variable
colvarrow variable to be multiplied
coefcoefficient of the bilinear term
uselbwhether we multiply with (var - lb) or (ub - var)
uselhswhether to create a cut for the lhs or rhs
localwhether local or global cuts should be computed
computeEqCutwhether conditions are fulfilled to compute equality cuts
coefvarcoefficient of var
cstbuffer to store the constant part of the cut
successbuffer to store whether cut was updated successfully

Definition at line 1858 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, 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 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

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
scipSCIP data structure
sepaseparator
sepadataseparation data
cutbuffer to store the cut
rowthe row that is used for the rlt cut (NULL if using projected row)
projrowprojected row that is used for the rlt cut (NULL if using row)
solthe point to be separated (can be NULL)
bestunderestpositions of most violated underestimators for each product term
bestoverestpositions of most violated overestimators for each product term
varthe variable that is used for the rlt cuts
successbuffer to store whether cut was created successfully
uselbwhether we multiply with (var - lb) or (ub - var)
uselhswhether to create a cut for the lhs or rhs
localwhether local or global cuts should be computed
computeEqCutwhether conditions are fulfilled to compute equality cuts
useprojrowwhether to use projected row instead of normal row

Definition at line 2097 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_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 SCIP_RETCODE createProjRow ( SCIP scip,
RLT_SIMPLEROW simplerow,
SCIP_ROW row,
SCIP_SOL sol,
SCIP_Bool  local 
)
static

store a row projected by fixing all variables that are at bound at sol; the result is a simplified row

Parameters
scipSCIP data structure
simplerowpointer to the simplified row
rowrow to be projected
solthe point to be separated (can be NULL)
localwhether local bounds should be checked

Definition at line 2242 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 void freeProjRow ( SCIP scip,
RLT_SIMPLEROW simplerow 
)
static

free the projected row

Parameters
scipSCIP data structure
simplerowsimplified row to be freed

Definition at line 2306 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 SCIP_RETCODE createProjRows ( SCIP scip,
SCIP_ROW **  rows,
int  nrows,
SCIP_SOL sol,
RLT_SIMPLEROW **  projrows,
SCIP_Bool  local,
SCIP_Bool allcst 
)
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
scipSCIP data structure
rowsproblem rows
nrowsnumber of rows
solthe point to be separated (can be NULL)
projrowsthe projected rows to be filled
localare local cuts allowed?
allcstbuffer to store whether all projected rows have only constants

Definition at line 2330 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 void freeProjRows ( SCIP scip,
RLT_SIMPLEROW **  projrows,
int  nrows 
)
static

frees the projected rows

Parameters
scipSCIP data structure
projrowsthe projected LP
nrowsnumber of rows in projrows

Definition at line 2414 of file sepa_rlt.c.

References addRowMark(), freeProjRow(), HashData::nrows, and SCIPfreeBufferArray.

Referenced by createProjRows().

◆ addRowMark()

static void addRowMark ( int  ridx,
SCIP_Real  a,
SCIP_Bool  violatedbelow,
SCIP_Bool  violatedabove,
int *  row_idcs,
unsigned int *  row_marks,
int *  nmarked 
)
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
ridxrow index
acoefficient of x in the row
violatedbelowwhether the relation auxexpr <= xy is violated
violatedabovewhether the relation xy <= auxexpr is violated
row_idcssparse array with indices of marked rows
row_markssparse array to store the marks
nmarkednumber of marked rows

Definition at line 2436 of file sepa_rlt.c.

References a, markRowsXj(), SCIP_Bool, and SCIPsortedvecFindInt().

Referenced by freeProjRows(), and markRowsXj().

◆ markRowsXj()

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

mark all rows that should be multiplied by xj

Parameters
scipSCIP data structure
sepadataseparator data
conshdlrnonlinear constraint handler
solpoint to be separated (can be NULL)
jindex of the multiplier variable in sepadata
localare local cuts allowed?
row_to_poshashmap linking row indices to positions in array
bestunderestpositions of most violated underestimators for each product term
bestoverestpositions of most violated overestimators for each product term
row_markssparse array storing the row marks
row_idcssparse array storing the marked row positions
nmarkednumber of marked rows

Definition at line 2483 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 SCIP_RETCODE separateMcCormickImplicit ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
SCIP_SOL sol,
int *  bestunderestimators,
int *  bestoverestimators,
SCIP_RESULT result 
)
static

◆ separateRltCuts()

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

builds and adds the RLT cuts

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
conshdlrnonlinear constraint handler
solthe point to be separated (can be NULL)
row_to_poshashmap linking row indices to positions in array
projrowsprojected rows
rowsproblem rows
nrowsnumber of problem rows
allowlocalare local cuts allowed?
bestunderestimatorsindices of auxiliary underestimators with largest violation in sol
bestoverestimatorsindices of auxiliary overestimators with largest violation in sol
resultbuffer to store whether separation was successful

Definition at line 2807 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 SCIP_DECL_SEPACOPY ( sepaCopyRlt  )
static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 3053 of file sepa_rlt.c.

Referenced by separateRltCuts().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeRlt  )
static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 3067 of file sepa_rlt.c.

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolRlt  )
static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 3086 of file sepa_rlt.c.

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpRlt  )
static

LP solution separation method of separator

Definition at line 3105 of file sepa_rlt.c.