Detailed Description

minor separator with intersection cuts

Author: Felipe Serrano; Antonia Chmiela

Let X be the matrix of auxiliary variables added for bilinear terms, X_{ij} = x_ix_j. The separator enforces quadratic constraints det(2x2 minor of X) = 0 via intersection cuts.

Definition in file sepa_interminor.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_interminor.h"
#include "scip/expr.h"
#include "scip/expr_var.h"
#include "scip/expr_pow.h"
#include "scip/expr_product.h"
#include "scip/nlpi_ipopt.h"
#include "scip/cons_nonlinear.h"

Go to the source code of this file.

Data Structures
struct	rowdata

Macros
#define	SEPA_NAME "interminor"

#define	SEPA_DESC "intersection cuts separator to ensure that 2x2 minors of X (= xx') have determinant 0"

#define	SEPA_PRIORITY 0

#define	SEPA_FREQ -1

#define	SEPA_MAXBOUNDDIST 1.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	DEFAULT_MINCUTVIOL 1e-4

#define	DEFAULT_RANDSEED 157

#define	DEFAULT_MAXROUNDS 10

#define	DEFAULT_MAXROUNDSROOT -1

#define	BINSEARCH_MAXITERS 120

#define	DEFAULT_USESTRENGTHENING FALSE

#define	DEFAULT_USEBOUNDS FALSE

Functions
static SCIP_RETCODE	sepadataAddMinor (SCIP scip, SCIP_SEPADATA sepadata, SCIP_VAR auxvarxik, SCIP_VAR auxvarxil, SCIP_VAR auxvarxjk, SCIP_VAR auxvarxjl, SCIP_Bool isauxvarxikdiag, SCIP_Bool isauxvarxildiag, SCIP_Bool isauxvarxjkdiag, SCIP_Bool isauxvarxjldiag)

static SCIP_RETCODE	sepadataClear (SCIP scip, SCIP_SEPADATA sepadata)

static SCIP_RETCODE	getMinorVars (SCIP_SEPADATA sepadata, int idx, SCIP_VAR auxvarxik, SCIP_VAR auxvarxil, SCIP_VAR auxvarxjk, SCIP_VAR auxvarxjl, SCIP_Bool isauxvarxikdiag, SCIP_Bool isauxvarxildiag, SCIP_Bool isauxvarxjkdiag, SCIP_Bool *isauxvarxjldiag)

static SCIP_RETCODE	insertIndex (SCIP scip, SCIP_HASHMAP rowmap, SCIP_VAR row, SCIP_VAR col, SCIP_VAR auxvar, int rowindices, int *nrows)

static SCIP_RETCODE	detectMinors (SCIP scip, SCIP_SEPADATA sepadata)

static SCIP_RETCODE	constructBasicVars2TableauRowMap (SCIP scip, int map)

static SCIP_RETCODE	computeRestrictionToRay (SCIP scip, SCIP_Real ray, SCIP_VAR *vars, SCIP_Real coefs, SCIP_Real coefs4b, SCIP_Real coefscondition, SCIP_Bool usebounds, SCIP_Real ad, SCIP_Bool success)

static SCIP_Real	evalPhiAtRay (SCIP *scip, SCIP_Real t, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)

static void	doBinarySearch (SCIP scip, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Real sol)

static SCIP_Real	isCase4a (SCIP_Real tsol, SCIP_Real coefs, SCIP_Real coefscondition)

static SCIP_Real	computeRoot (SCIP scip, SCIP_Real coefs)

static SCIP_Real	computeIntersectionPoint (SCIP scip, SCIP_Bool usebounds, SCIP_Real coefs, SCIP_Real coefs4b, SCIP_Real coefscondition)

static SCIP_RETCODE	addColToCut (SCIP scip, SCIP_ROWPREP rowprep, SCIP_Real cutcoef, SCIP_COL *col)

static SCIP_RETCODE	addRowToCut (SCIP scip, SCIP_ROWPREP rowprep, SCIP_Real cutcoef, SCIP_ROW row, SCIP_Bool success)

static SCIP_RETCODE	getTableauRows (SCIP scip, SCIP_VAR vars, int basicvarpos2tableaurow, SCIP_HASHMAP tableau, SCIP_Real tableaurows, SCIP_Bool success)

static SCIP_RETCODE	addCols (SCIP scip, SCIP_VAR vars, SCIP_Real tableaurows, SCIP_ROWPREP rowprep, SCIP_Real rays, int nrays, int rayslppos, SCIP_Real interpoints, SCIP_Bool usebounds, SCIP_Real ad, SCIP_Bool success)

static SCIP_RETCODE	addRows (SCIP scip, SCIP_VAR vars, SCIP_Real tableaurows, SCIP_ROWPREP rowprep, SCIP_Real rays, int nrays, int rayslppos, SCIP_Real interpoints, SCIP_Bool usebounds, SCIP_Real ad, SCIP_Bool success)

static SCIP_Bool	raysAreDependent (SCIP scip, SCIP_Real ray1, SCIP_Real ray2, SCIP_Real coef)

static SCIP_RETCODE	findRho (SCIP scip, SCIP_Real rays, int nrays, int idx, SCIP_Real interpoints, SCIP_VAR vars, SCIP_Real rho, SCIP_Bool usebounds, SCIP_Real ad, SCIP_Bool success)

static SCIP_RETCODE	computeNegCutcoefs (SCIP scip, SCIP_VAR vars, SCIP_Real rays, int nrays, int rayslppos, SCIP_Real interpoints, SCIP_ROWPREP rowprep, SCIP_Bool usebounds, SCIP_Real ad, SCIP_Bool *success)

static SCIP_RETCODE	separateDeterminant (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, SCIP_VAR xik, SCIP_VAR xil, SCIP_VAR xjk, SCIP_VAR xjl, SCIP_Bool isxikdiag, SCIP_Bool isxildiag, SCIP_Bool isxjkdiag, SCIP_Bool isxjldiag, int basicvarpos2tableaurow, SCIP_HASHMAP tableau, SCIP_RESULT result)

static SCIP_RETCODE	separatePoint (SCIP scip, SCIP_SEPA sepa, SCIP_RESULT *result)

static	SCIP_DECL_SEPACOPY (sepaCopyMinor)

static	SCIP_DECL_SEPAFREE (sepaFreeMinor)

static	SCIP_DECL_SEPAINIT (sepaInitMinor)

static	SCIP_DECL_SEPAEXIT (sepaExitMinor)

static	SCIP_DECL_SEPAINITSOL (sepaInitsolMinor)

static	SCIP_DECL_SEPAEXITSOL (sepaExitsolMinor)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpMinor)

SCIP_RETCODE	SCIPincludeSepaInterminor (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "interminor"

Definition at line 50 of file sepa_interminor.c.

◆ SEPA_DESC

#define SEPA_DESC "intersection cuts separator to ensure that 2x2 minors of X (= xx') have determinant 0"

Definition at line 51 of file sepa_interminor.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 0

Definition at line 52 of file sepa_interminor.c.

◆ SEPA_FREQ

#define SEPA_FREQ -1

Definition at line 53 of file sepa_interminor.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 54 of file sepa_interminor.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 55 of file sepa_interminor.c.

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 56 of file sepa_interminor.c.

◆ DEFAULT_MINCUTVIOL

#define DEFAULT_MINCUTVIOL 1e-4

default minimum required violation of a cut

Definition at line 58 of file sepa_interminor.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 157

default random seed

Definition at line 59 of file sepa_interminor.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 10

maximal number of separation rounds per node (-1: unlimited)

Definition at line 60 of file sepa_interminor.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT -1

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 61 of file sepa_interminor.c.

◆ BINSEARCH_MAXITERS

#define BINSEARCH_MAXITERS 120

default iteration limit for binary search

Definition at line 62 of file sepa_interminor.c.

◆ DEFAULT_USESTRENGTHENING

#define DEFAULT_USESTRENGTHENING FALSE

default for using strengthend intersection cuts to separate

Definition at line 63 of file sepa_interminor.c.

◆ DEFAULT_USEBOUNDS

#define DEFAULT_USEBOUNDS FALSE

default for using nonnegativity bounds when separating

Definition at line 64 of file sepa_interminor.c.

Function Documentation

◆ sepadataAddMinor()

static SCIP_RETCODE sepadataAddMinor	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR *	auxvarxik,
		SCIP_VAR *	auxvarxil,
		SCIP_VAR *	auxvarxjk,
		SCIP_VAR *	auxvarxjl,
		SCIP_Bool	isauxvarxikdiag,
		SCIP_Bool	isauxvarxildiag,
		SCIP_Bool	isauxvarxjkdiag,
		SCIP_Bool	isauxvarxjldiag
	)

static

helper method to store a 2x2 minor in the separation data

Parameters

scip	SCIP data structure
sepadata	separator data
auxvarxik	auxiliary variable X_ik = x_i * x_k
auxvarxil	auxiliary variable X_il = x_i * x_l
auxvarxjk	auxiliary variable X_jk = x_j * x_k
auxvarxjl	auxiliary variable X_jl = x_j * x_l
isauxvarxikdiag	is X_ik diagonal? (i.e. i = k)
isauxvarxildiag	is X_il diagonal? (i.e. i = l)
isauxvarxjkdiag	is X_jk diagonal? (i.e. j = k)
isauxvarxjldiag	is X_jl diagonal? (i.e. j = l)

Definition at line 102 of file sepa_interminor.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPdebugMsg, SCIPreallocBlockMemoryArray, and SCIPvarGetName().

Referenced by detectMinors().

◆ sepadataClear()

static SCIP_RETCODE sepadataClear	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

static

helper method to clear separation data

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 159 of file sepa_interminor.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().

Referenced by SCIP_DECL_SEPAEXITSOL().

◆ getMinorVars()

static SCIP_RETCODE getMinorVars	(	SCIP_SEPADATA *	sepadata,
		int	idx,
		SCIP_VAR **	auxvarxik,
		SCIP_VAR **	auxvarxil,
		SCIP_VAR **	auxvarxjk,
		SCIP_VAR **	auxvarxjl,
		SCIP_Bool *	isauxvarxikdiag,
		SCIP_Bool *	isauxvarxildiag,
		SCIP_Bool *	isauxvarxjkdiag,
		SCIP_Bool *	isauxvarxjldiag
	)

static

helper method to get the variables associated to a minor

Parameters

sepadata	separator data
idx	index of the stored minor
auxvarxik	auxiliary variable X_ik = x_i * x_k
auxvarxil	auxiliary variable X_il = x_i * x_l
auxvarxjk	auxiliary variable X_jk = x_j * x_k
auxvarxjl	auxiliary variable X_jl = x_j * x_l
isauxvarxikdiag	is X_ik diagonal? (i.e. i = k)
isauxvarxildiag	is X_il diagonal? (i.e. i = l)
isauxvarxjkdiag	is X_jk diagonal? (i.e. j = k)
isauxvarxjldiag	is X_jl diagonal? (i.e. j = l)

Definition at line 190 of file sepa_interminor.c.

References NULL, and SCIP_OKAY.

Referenced by separatePoint().

◆ insertIndex()

static SCIP_RETCODE insertIndex	(	SCIP *	scip,
		SCIP_HASHMAP *	rowmap,
		SCIP_VAR *	row,
		SCIP_VAR *	col,
		SCIP_VAR *	auxvar,
		int *	rowindices,
		int *	nrows
	)

static

adds a new entry (i.e., auxvar) of in (row, col) of matrix M.

we have a matrix, M, indexed by the variables M(xi, xk) is the auxiliary variable of xi * xk if it exists We store, for each row of the matrix, the indices of the nonzero column entries (assoc with the given row) and the auxiliary variable for xi * xk The nonzero column entries are stored as an array (struct rowdata) So we have a hashmap mapping each variable (row of the matrix) with its array representing the nonzero entries of the row.

Parameters

scip	SCIP data structure
rowmap	hashmap of the rows of the matrix
row	variable corresponding to row of new entry
col	variable corresponding to column of new entry
auxvar	auxvar to insert into the matrix
rowindices	array of indices of all variables corresponding to a row
nrows	number of rows

Definition at line 231 of file sepa_interminor.c.

References rowdata::auxvars, rowdata::nvals, rowdata::rowidx, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreallocBufferArray, SCIPvarGetName(), SCIPvarGetProbindex(), rowdata::vals, and rowdata::valssize.

Referenced by detectMinors().

◆ detectMinors()

static SCIP_RETCODE detectMinors	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

static

method to detect and store principal minors

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 295 of file sepa_interminor.c.

References rowdata::auxvars, FALSE, insertIndex(), NULL, rowdata::nvals, rowdata::rowidx, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcomputeArraysIntersectionInt(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeExpriter(), SCIPgetExponentExprPow(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprNonlinear(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetTotalTime(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPisExprPower(), SCIPisExprProduct(), SCIPsortInt(), SCIPstatisticMessage, sepadataAddMinor(), TRUE, and rowdata::vals.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ constructBasicVars2TableauRowMap()

static SCIP_RETCODE constructBasicVars2TableauRowMap	(	SCIP *	scip,
		int *	map
	)

static

constructs map between lp position of a basic variable and its row in the tableau

Parameters

scip	SCIP data structure
map	buffer to store the map

Definition at line 510 of file sepa_interminor.c.

References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetLPBasisInd(), and SCIPgetNLPRows().

Referenced by separatePoint().

◆ computeRestrictionToRay()

static SCIP_RETCODE computeRestrictionToRay	(	SCIP *	scip,
		SCIP_Real *	ray,
		SCIP_VAR **	vars,
		SCIP_Real *	coefs,
		SCIP_Real *	coefs4b,
		SCIP_Real *	coefscondition,
		SCIP_Bool	usebounds,
		SCIP_Real *	ad,
		SCIP_Bool *	success
	)

static

The restriction of the function representing the maximal S-free set to zlp + t * ray has the form sqrt(A t^2 + B t + C) - (D t + E). This function computes the coefficients A, B, C, D, E for the given ray.

Parameters

scip	SCIP data structure
ray	coefficients of ray
vars	variables
coefs	buffer to store A, B, C, D, and E of cases 1, 2, 3, or 4a
coefs4b	buffer to store A, B, C, D, and E of case 4b
coefscondition	buffer to store coefs for checking whether we are in case 4a or 4b
usebounds	TRUE if we want to separate non-negative bound
ad	coefs a and d for the hyperplane aTx + dTy <= 0
success	FALSE if we need to abort generation because of numerics

Definition at line 539 of file sepa_interminor.c.

References a, ABS, b, FALSE, NULL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPinfoMessage(), SCIPisHugeValue(), SCIPvarGetLPSol(), SQR, and TRUE.

Referenced by addCols(), addRows(), and findRho().

◆ evalPhiAtRay()

static SCIP_Real evalPhiAtRay	(	SCIP *	scip,
		SCIP_Real	t,
		SCIP_Real	a,
		SCIP_Real	b,
		SCIP_Real	c,
		SCIP_Real	d,
		SCIP_Real	e
	)

static

returns phi(zlp + t * ray) = sqrt(A t^2 + B t + C) - (D t + E)

Parameters

scip	SCIP data structure
t	argument of phi restricted to ray
a	value of A
b	value of B
c	value of C
d	value of D
e	value of E

Definition at line 700 of file sepa_interminor.c.

References a, b, QUAD, QUAD_ASSIGN, QUAD_SCALE, QUAD_TO_DBL, SCIP_Real, SCIPisInfinity(), SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSqrtQ, SCIPquadprecSquareD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.

Referenced by computeRoot(), and doBinarySearch().

◆ doBinarySearch()

static void doBinarySearch	(	SCIP *	scip,
		SCIP_Real	a,
		SCIP_Real	b,
		SCIP_Real	c,
		SCIP_Real	d,
		SCIP_Real	e,
		SCIP_Real *	sol
	)

static

helper function of computeRoot: we want phi to be <= 0

Parameters

scip	SCIP data structure
a	value of A
b	value of B
c	value of C
d	value of D
e	value of E
sol	buffer to store solution; also gives initial point

Definition at line 757 of file sepa_interminor.c.

References a, b, BINSEARCH_MAXITERS, evalPhiAtRay(), SCIP_Real, SCIPisFeasEQ(), and SCIPisFeasZero().

Referenced by computeRoot().

◆ isCase4a()

static SCIP_Real isCase4a	(	SCIP_Real	tsol,
		SCIP_Real *	coefs,
		SCIP_Real *	coefscondition
	)

static

checks if we are in case 4a, i.e., if (num(xhat_{r+1}(zlp)) / E) * sqrt(A * tsol^2 + B * tsol + C) + w(ray) * tsol + num(yhat_{s+1}(zlp)) <= 0

Parameters

tsol	t in the above formula
coefs	coefficients A, B, C, D, and E of case 4a
coefscondition	extra coefficients needed for the evaluation of the condition: num(xhat_{r+1}(zlp)) / E; w(ray); num(yhat_{s+1}(zlp))

Definition at line 799 of file sepa_interminor.c.

References SQR.

Referenced by computeIntersectionPoint().

◆ computeRoot()

static SCIP_Real computeRoot	(	SCIP *	scip,
		SCIP_Real *	coefs
	)

static

finds smallest positive root phi by finding the smallest positive root of (A - D^2) t^2 + (B - 2 D*E) t + (C - E^2) = 0

However, we are conservative and want a solution such that phi is negative, but close to 0; thus we correct the result with a binary search

Parameters

scip	SCIP data structure
coefs	value of A

Definition at line 817 of file sepa_interminor.c.

References a, b, doBinarySearch(), evalPhiAtRay(), SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), and SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar().

Referenced by computeIntersectionPoint().

◆ computeIntersectionPoint()

static SCIP_Real computeIntersectionPoint	(	SCIP *	scip,
		SCIP_Bool	usebounds,
		SCIP_Real *	coefs,
		SCIP_Real *	coefs4b,
		SCIP_Real *	coefscondition
	)

static

The maximal S-free set is gamma(z) <= 0; we find the intersection point of the ray ray starting from zlp with the boundary of the S-free set. That is, we find t >= 0 such that gamma(zlp + t * ray) = 0.

In cases 1,2, and 3, gamma is of the form gamma(zlp + t * ray) = sqrt(A t^2 + B t + C) - (D t + E)

In the case 4 gamma is of the form gamma(zlp + t * ray) = sqrt(A t^2 + B t + C) - (D t + E) if some condition holds sqrt(A' t^2 + B' t + C') - (D' t + E') otherwise

It can be shown (given the special properties of gamma) that the smallest positive root of each function of the form sqrt(a t^2 + b t + c) - (d t + e) is the same as the smallest positive root of the quadratic equation: (sqrt(a t^2 + b t + c) - (d t + e)) * (sqrt(a t^2 + b t + c) + (d t + e)) = 0 <==> (a - d^2) t^2 + (b - 2 d*e) t + (c - e^2) = 0

So, in cases 1, 2, and 3, this function just returns the solution of the above equation. In case 4, it first solves the equation assuming we are in the first piece. If there is no solution, then the second piece can't have a solution (first piece >= second piece for all t) Then we check if the solution satisfies the condition. If it doesn't then we solve the equation for the second piece. If it has a solution, then it has to be the solution.

Parameters

scip	SCIP data structure
usebounds	whether we are in case 4 or not
coefs	values of A, B, C, D, and E of cases 1, 2, 3, or 4a
coefs4b	values of A, B, C, D, and E of case 4b
coefscondition	values needed to evaluate condition of case 4

Definition at line 904 of file sepa_interminor.c.

References computeRoot(), isCase4a(), MAX, NULL, SCIP_Real, and SCIPisInfinity().

Referenced by addCols(), addRows(), and findRho().

◆ addColToCut()

static SCIP_RETCODE addColToCut	(	SCIP *	scip,
		SCIP_ROWPREP *	rowprep,
		SCIP_Real	cutcoef,
		SCIP_COL *	col
	)

static

adds cutcoef * (col - col*) to rowprep

Parameters

scip	SCIP data structure
rowprep	rowprep to store intersection cut
cutcoef	cut coefficient
col	column to add to rowprep

Definition at line 953 of file sepa_interminor.c.

References NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIPaddRowprepTerm(), SCIPcolGetBasisStatus(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPinfoMessage(), SCIProwprepAddConstant(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by addCols(), and computeNegCutcoefs().

◆ addRowToCut()

static SCIP_RETCODE addRowToCut	(	SCIP *	scip,
		SCIP_ROWPREP *	rowprep,
		SCIP_Real	cutcoef,
		SCIP_ROW *	row,
		SCIP_Bool *	success
	)

static

adds cutcoef * (slack - slack*) to rowprep

row is lhs <= <coefs, vars> + constant <= rhs, thus slack is defined by slack + <coefs, vars> + constant = side If row (slack) is at upper, it means that <coefs,vars*> + constant = rhs, and so slack* = side - rhs --> slack - slack* = rhs - <coefs, vars> - constant. If row (slack) is at lower, then <coefs,vars*> + constant = lhs, and so slack* = side - lhs --> slack - slack* = lhs - <coefs, vars> - constant.

Parameters

scip	SCIP data structure
rowprep	rowprep to store intersection cut
cutcoef	cut coefficient
row	row, whose slack we are adding to rowprep
success	buffer to store whether the row is nonbasic enough

Definition at line 985 of file sepa_interminor.c.

References FALSE, NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPcolGetVar(), SCIPgetRowActivity(), SCIPinfoMessage(), SCIPisFeasEQ(), SCIPisInfinity(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), and SCIProwprepAddConstant().

Referenced by addRows(), and computeNegCutcoefs().

◆ getTableauRows()

static SCIP_RETCODE getTableauRows	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int *	basicvarpos2tableaurow,
		SCIP_HASHMAP *	tableau,
		SCIP_Real **	tableaurows,
		SCIP_Bool *	success
	)

static

get the tableau rows of the variables in vars

Parameters

scip	SCIP data structure
vars	variables in the minor
basicvarpos2tableaurow	map between basic var and its tableau row
tableau	map between var an its tableau row
tableaurows	buffer to store tableau row
success	set to TRUE if no variable had basisstat = ZERO

Definition at line 1046 of file sepa_interminor.c.

References FALSE, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_ZERO, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPvarGetCol(), and TRUE.

Referenced by separateDeterminant().

◆ addCols()

static SCIP_RETCODE addCols	(	SCIP *	scip,
		SCIP_VAR **	vars,
		SCIP_Real **	tableaurows,
		SCIP_ROWPREP *	rowprep,
		SCIP_Real *	rays,
		int *	nrays,
		int *	rayslppos,
		SCIP_Real *	interpoints,
		SCIP_Bool	usebounds,
		SCIP_Real *	ad,
		SCIP_Bool *	success
	)

static

computes the cut coefs of the non-basic (non-slack) variables (correspond to cols) and adds them to the intersection cut

Parameters

scip	SCIP data structure
vars	variables
tableaurows	tableau rows corresponding to the variables in vars
rowprep	store cut
rays	buffer to store rays
nrays	pointer to store number of nonzero rays
rayslppos	buffer to store lppos of nonzero rays
interpoints	buffer to store intersection points or NULL if not needed
usebounds	TRUE if we want to separate non-negative bound
ad	coefs a and d for the hyperplane aTx + dTy <= 0
success	pointer to store whether the generation of cutcoefs was successful

Definition at line 1110 of file sepa_interminor.c.

References addColToCut(), computeIntersectionPoint(), computeRestrictionToRay(), FALSE, NULL, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetBasisStatus(), SCIPgetLPCols(), SCIPgetNLPCols(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetCol(), and TRUE.

Referenced by separateDeterminant().

◆ addRows()

static SCIP_RETCODE addRows	(	SCIP *	scip,
		SCIP_VAR **	vars,
		SCIP_Real **	tableaurows,
		SCIP_ROWPREP *	rowprep,
		SCIP_Real *	rays,
		int *	nrays,
		int *	rayslppos,
		SCIP_Real *	interpoints,
		SCIP_Bool	usebounds,
		SCIP_Real *	ad,
		SCIP_Bool *	success
	)

static

computes the cut coefs of the non-basic slack variables (correspond to rows) and adds them to the intersection cut

Parameters

scip	SCIP data structure
vars	variables
tableaurows	tableau rows corresponding to the variables in vars
rowprep	store cut
rays	buffer to store rays
nrays	pointer to store number of nonzero rays
rayslppos	buffer to store lppos of nonzero rays
interpoints	buffer to store intersection points or NULL if not needed
usebounds	TRUE if we want to separate non-negative bound
ad	coefs a and d for the hyperplane aTx + dTy <= 0
success	pointer to store whether the generation of cutcoefs was successful

Definition at line 1216 of file sepa_interminor.c.

References addRowToCut(), computeIntersectionPoint(), computeRestrictionToRay(), FALSE, NULL, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisInfinity(), SCIPisZero(), SCIProwGetBasisStatus(), and TRUE.

Referenced by separateDeterminant().

◆ raysAreDependent()

static SCIP_Bool raysAreDependent	(	SCIP *	scip,
		SCIP_Real *	ray1,
		SCIP_Real *	ray2,
		SCIP_Real *	coef
	)

static

Parameters

scip	SCIP data structure
ray1	coefficients of ray 1
ray2	coefficients of ray 2
coef	pointer to store coef (s.t. r1 = coef * r2) in case rays are dependent

Definition at line 1326 of file sepa_interminor.c.

References FALSE, SCIPisFeasEQ(), SCIPisZero(), and TRUE.

Referenced by findRho().

◆ findRho()

static SCIP_RETCODE findRho	(	SCIP *	scip,
		SCIP_Real *	rays,
		int	nrays,
		int	idx,
		SCIP_Real *	interpoints,
		SCIP_VAR **	vars,
		SCIP_Real *	rho,
		SCIP_Bool	usebounds,
		SCIP_Real *	ad,
		SCIP_Bool *	success
	)

static

finds the smallest negative steplength for the current ray r_idx such that the combination of r_idx with all rays not in the recession cone is in the recession cone

Parameters

scip	SCIP data structure
rays	rays
nrays	number of nonzero rays
idx	index of current ray we want to find rho for
interpoints	intersection points of nonzero rays
vars	variables
rho	pointer to store the optimal rho
usebounds	TRUE if we want to separate non-negative bound
ad	coefs a and d for the hyperplane aTx + dTy <= 0
success	TRUE if computation of rho was successful

Definition at line 1363 of file sepa_interminor.c.

References BINSEARCH_MAXITERS, computeIntersectionPoint(), computeRestrictionToRay(), raysAreDependent(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by computeNegCutcoefs().

◆ computeNegCutcoefs()

static SCIP_RETCODE computeNegCutcoefs	(	SCIP *	scip,
		SCIP_VAR **	vars,
		SCIP_Real *	rays,
		int	nrays,
		int *	rayslppos,
		SCIP_Real *	interpoints,
		SCIP_ROWPREP *	rowprep,
		SCIP_Bool	usebounds,
		SCIP_Real *	ad,
		SCIP_Bool *	success
	)

static

computes negative steplengths for the rays that are in the recession cone of the S-free set, i.e., which have an infinite intersection point.

Parameters

scip	SCIP data structure
vars	variables
rays	rays
nrays	number of nonzero rays
rayslppos	lppos of nonzero rays
interpoints	intersection points
rowprep	rowprep for the generated cut
usebounds	TRUE if we want to separate non-negative bound
ad	coefs a and d for the hyperplane aTx + dTy <= 0
success	if a cut candidate could be computed

Definition at line 1467 of file sepa_interminor.c.

References addColToCut(), addRowToCut(), findRho(), SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetBasisStatus(), SCIPgetLPCols(), SCIPgetLPRows(), SCIPisInfinity(), SCIProwGetBasisStatus(), and TRUE.

Referenced by separateDeterminant().

◆ separateDeterminant()

static SCIP_RETCODE separateDeterminant	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR *	xik,
		SCIP_VAR *	xil,
		SCIP_VAR *	xjk,
		SCIP_VAR *	xjl,
		SCIP_Bool *	isxikdiag,
		SCIP_Bool *	isxildiag,
		SCIP_Bool *	isxjkdiag,
		SCIP_Bool *	isxjldiag,
		int *	basicvarpos2tableaurow,
		SCIP_HASHMAP *	tableau,
		SCIP_RESULT *	result
	)

static

separates cuts for stored principal minors

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
xik	variable X_ik = x_i * x_k
xil	variable X_il = x_i * x_l
xjk	variable X_jk = x_j * x_k
xjl	variable X_jl = x_j * x_l
isxikdiag	is X_ik diagonal? (i.e. i = k)
isxildiag	is X_il diagonal? (i.e. i = l)
isxjkdiag	is X_jk diagonal? (i.e. j = k)
isxjldiag	is X_jl diagonal? (i.e. j = l)
basicvarpos2tableaurow	map from basic var to its tableau row
tableau	map from var to its tableau row
result	pointer to store the result of the separation call

Definition at line 1538 of file sepa_interminor.c.

References addCols(), addRows(), computeNegCutcoefs(), FALSE, getTableauRows(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_SIDETYPE_LEFT, SCIPaddRow(), SCIPallocBufferArray, SCIPcleanupRowprep(), SCIPcreateRowprep(), SCIPfreeBuffer, SCIPfreeRowprep(), SCIPgetCutEfficacy(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPgetRowprepRowSepa(), SCIPisFeasNegative(), SCIPmergeRowprepTerms(), SCIPreleaseRow(), SCIProwprepAddSide(), SCIPvarGetLPSol(), and TRUE.

Referenced by separatePoint().

◆ separatePoint()

static SCIP_RETCODE separatePoint	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_RESULT *	result
	)

static

separates cuts for stored principal minors

Parameters

scip	SCIP data structure
sepa	separator
result	pointer to store the result of the separation call

Definition at line 1682 of file sepa_interminor.c.

References constructBasicVars2TableauRowMap(), getMinorVars(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNLPCols(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapEntryGetImage(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetNEntries(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPsepaGetData(), SCIPvarGetLPSol(), and separateDeterminant().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyMinor )

static

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

Definition at line 1795 of file sepa_interminor.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaInterminor(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeMinor )

static

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

Definition at line 1810 of file sepa_interminor.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), and SCIPsepaSetData().

◆ SCIP_DECL_SEPAINIT()

static SCIP_DECL_SEPAINIT ( sepaInitMinor )

static

initialization method of separator (called after problem was transformed)

Definition at line 1830 of file sepa_interminor.c.

References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), and TRUE.

◆ SCIP_DECL_SEPAEXIT()

static SCIP_DECL_SEPAEXIT ( sepaExitMinor )

static

deinitialization method of separator (called before transformed problem is freed)

Definition at line 1848 of file sepa_interminor.c.

References NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPAINITSOL()

static SCIP_DECL_SEPAINITSOL ( sepaInitsolMinor )

static

solving process initialization method of separator (called when branch and bound process is about to begin)

Definition at line 1866 of file sepa_interminor.c.

References SCIP_OKAY.

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolMinor )

static

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

Definition at line 1874 of file sepa_interminor.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), and sepadataClear().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpMinor )

static

LP solution separation method of separator

Definition at line 1890 of file sepa_interminor.c.

References detectMinors(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetDepth(), SCIPisIpoptAvailableIpopt(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), and separatePoint().

SCIP

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MINCUTVIOL

◆ DEFAULT_RANDSEED

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ BINSEARCH_MAXITERS

◆ DEFAULT_USESTRENGTHENING

◆ DEFAULT_USEBOUNDS

Function Documentation

◆ sepadataAddMinor()

◆ sepadataClear()

◆ getMinorVars()

◆ insertIndex()

◆ detectMinors()

◆ constructBasicVars2TableauRowMap()

◆ computeRestrictionToRay()

◆ evalPhiAtRay()

◆ doBinarySearch()

◆ isCase4a()

◆ computeRoot()

◆ computeIntersectionPoint()

◆ addColToCut()

◆ addRowToCut()

◆ getTableauRows()

◆ addCols()

◆ addRows()

◆ raysAreDependent()

◆ findRho()

◆ computeNegCutcoefs()

◆ separateDeterminant()

◆ separatePoint()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAINIT()

◆ SCIP_DECL_SEPAEXIT()

◆ SCIP_DECL_SEPAINITSOL()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()