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

typedef struct AdjacentVarData 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

scip	SCIP data structure
adjvarmap	hashmap mapping variables to their ADJACENTVARDATAs
vars	variable 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

adjvarmap	hashmap mapping variables to their ADJACENTVARDATAs
var	variable
nadjacentvars	buffer 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

scip	SCIP data structure
adjvarmap	hashmap 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

scip	SCIP data structure
sepadata	separation 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

scip	SCIP data structure
rows	buffer to store the rows
nrows	buffer 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

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 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

scip	SCIP data structure
sepadata	separator data
n	number 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

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 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

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 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 = 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 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 = !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 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

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 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

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 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

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 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

detect bilinear products encoded in linear constraints

Parameters

scip	SCIP data structure
sepadata	separation data
varmap	variable map

Definition at line 1217 of file sepa_rlt.c.

References clearVarAdjacency(), createSepaData(), detectProductsClique(), detectProductsImplbnd(), detectProductsUnconditional(), extractProducts(), fillRelationTables(), HashData::firstrow, getAdjacentVars(), getOriginalRows(), implBndToBigM(), 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 SCIP_RETCODE createSepaData	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

static

helper method to create separation data

Parameters

scip	SCIP data structure
sepadata	separation data

Definition at line 1581 of file sepa_rlt.c.

References addProductVars(), SCIP_ConsNonlinear_BilinTerm::aux, detectHiddenProducts(), SCIP_ConsNonlinear_BilinTerm::exprs, getBestEstimators(), 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 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

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 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

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 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

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 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

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 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

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 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

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 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

scip	SCIP data structure
simplerow	simplified 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

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 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

scip	SCIP data structure
projrows	the projected LP
nrows	number 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

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 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

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 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

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 2650 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, RLT_SimpleRow::name, NULL, SCIP_ConsNonlinear_Auxexpr::overestimate, REALABS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, 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 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

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 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.

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MAXUNKNOWNTERMS

◆ DEFAULT_MAXUSEDVARS

◆ DEFAULT_MAXNCUTS

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_ONLYEQROWS

◆ DEFAULT_ONLYCONTROWS

◆ DEFAULT_ONLYORIGINAL

◆ DEFAULT_USEINSUBSCIP

◆ DEFAULT_USEPROJECTION

◆ DEFAULT_DETECTHIDDEN

◆ DEFAULT_HIDDENRLT

◆ DEFAULT_ADDTOPOOL

◆ DEFAULT_GOODSCORE

◆ DEFAULT_BADSCORE

◆ DEFAULT_OBJPARALWEIGHT

◆ DEFAULT_EFFICACYWEIGHT

◆ DEFAULT_DIRCUTOFFDISTWEIGHT

◆ DEFAULT_GOODMAXPARALL

◆ DEFAULT_MAXPARALL

◆ MAXVARBOUND

Typedef Documentation

◆ HASHDATA

◆ ADJACENTVARDATA

◆ RLT_SIMPLEROW

Function Documentation

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ addAdjacentVars()

◆ getAdjacentVars()

◆ clearVarAdjacency()

◆ freeSepaData()

◆ getOriginalRows()

◆ storeSuitableRows()

◆ ensureVarsSize()

◆ addProductVars()

◆ extractProducts()

◆ implBndToBigM()

◆ detectProductsImplbnd()

◆ detectProductsClique()

◆ detectProductsUnconditional()

◆ fillRelationTables()

◆ detectHiddenProducts()

◆ createSepaData()

◆ getBestEstimators()

◆ isAcceptableRow()

◆ addAuxexprCoefs()

◆ addRltTerm()

◆ computeRltCut()

◆ createProjRow()

◆ freeProjRow()

◆ createProjRows()

◆ freeProjRows()

◆ addRowMark()

◆ markRowsXj()

◆ separateMcCormickImplicit()

◆ separateRltCuts()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()