Detailed Description

nonlinear handler for second order cone constraints

Author: Benjamin Mueller; Felipe Serrano; Fabian Wegscheider

This is a nonlinear handler for second order cone constraints of the form

\[\sqrt{\sum_{i=1}^{n} (v_i^T x + \beta_i)^2} \leq v_{n+1}^T x + \beta_{n+1}.\]

Note that \(v_i\), for \(i \leq n\), could be 0, thus allowing a positive constant term inside the root.

Definition in file nlhdlr_soc.c.

#include <string.h>
#include "scip/nlhdlr_soc.h"
#include "scip/cons_nonlinear.h"
#include "scip/expr_pow.h"
#include "scip/expr_sum.h"
#include "scip/expr_var.h"
#include "scip/debug.h"
#include "scip/pub_nlhdlr.h"
#include "scip/nlpi_ipopt.h"

Go to the source code of this file.

Macros
#define	NLHDLR_NAME "soc"

#define	NLHDLR_DESC "nonlinear handler for second-order cone structures"

#define	NLHDLR_DETECTPRIORITY 100

#define	NLHDLR_ENFOPRIORITY 100

#define	DEFAULT_MINCUTEFFICACY 1e-5

#define	DEFAULT_COMPEIGENVALUES TRUE

#define	nlhdlrInitSoc NULL

#define	nlhdlrExitSoc NULL

Functions
static SCIP_RETCODE	createDisaggrVars (SCIP scip, SCIP_EXPR expr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)

static SCIP_RETCODE	freeDisaggrVars (SCIP scip, SCIP_NLHDLREXPRDATA nlhdlrexprdata)

static SCIP_RETCODE	createDisaggrRow (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_EXPR expr, SCIP_NLHDLREXPRDATA nlhdlrexprdata)

static SCIP_RETCODE	createNlhdlrExprData (SCIP scip, SCIP_EXPR vars, SCIP_Real offsets, SCIP_Real transcoefs, int transcoefsidx, int termbegins, int nvars, int nterms, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)

static SCIP_RETCODE	freeNlhdlrExprData (SCIP scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)

static SCIP_Real	evalSingleTerm (SCIP scip, SCIP_NLHDLREXPRDATA nlhdlrexprdata, SCIP_SOL *sol, int k)

static SCIP_RETCODE	generateCutSolSOC (SCIP scip, SCIP_EXPR expr, SCIP_CONS cons, SCIP_SOL sol, SCIP_NLHDLREXPRDATA nlhdlrexprdata, SCIP_Real mincutviolation, SCIP_Real rhsval, SCIP_ROW *cut)

static SCIP_RETCODE	generateCutSolDisagg (SCIP scip, SCIP_EXPR expr, SCIP_CONS cons, SCIP_SOL sol, SCIP_NLHDLREXPRDATA nlhdlrexprdata, int disaggidx, SCIP_Real mincutviolation, SCIP_Real rhsval, SCIP_ROW *cut)

static SCIP_RETCODE	checkAndCollectQuadratic (SCIP scip, SCIP_EXPR quadexpr, SCIP_HASHMAP expr2idx, SCIP_EXPR occurringexprs, int nexprs, SCIP_Bool *success)

static void	buildQuadExprMatrix (SCIP scip, SCIP_EXPR quadexpr, SCIP_HASHMAP expr2idx, int nexprs, SCIP_Real quadmatrix, SCIP_Real *linvector)

static SCIP_RETCODE	tryFillNlhdlrExprDataQuad (SCIP scip, SCIP_EXPR occurringexprs, SCIP_Real eigvecmatrix, SCIP_Real eigvals, SCIP_Real bp, int nvars, int termbegins, SCIP_Real transcoefs, int transcoefsidx, SCIP_Real offsets, SCIP_Real lhsconstant, int nterms, SCIP_Bool *success)

static SCIP_RETCODE	detectSocNorm (SCIP scip, SCIP_EXPR expr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool success)

static SCIP_RETCODE	detectSocQuadraticSimple (SCIP scip, SCIP_EXPR expr, SCIP_Real conslhs, SCIP_Real consrhs, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool enforcebelow, SCIP_Bool *success)

static SCIP_RETCODE	detectSocQuadraticComplex (SCIP scip, SCIP_EXPR expr, SCIP_Real conslhs, SCIP_Real consrhs, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool enforcebelow, SCIP_Bool *success)

static SCIP_RETCODE	detectSOC (SCIP scip, SCIP_NLHDLRDATA nlhdlrdata, SCIP_EXPR expr, SCIP_Real conslhs, SCIP_Real consrhs, SCIP_NLHDLREXPRDATA nlhdlrexprdata, SCIP_Bool enforcebelow, SCIP_Bool *success)

static	SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrSoc)

static	SCIP_DECL_NLHDLRFREEHDLRDATA (nlhdlrFreehdlrdataSoc)

static	SCIP_DECL_NLHDLRFREEEXPRDATA (nlhdlrFreeExprDataSoc)

static	SCIP_DECL_NLHDLRDETECT (nlhdlrDetectSoc)

static	SCIP_DECL_NLHDLREVALAUX (nlhdlrEvalauxSoc)

static	SCIP_DECL_NLHDLRINITSEPA (nlhdlrInitSepaSoc)

static	SCIP_DECL_NLHDLREXITSEPA (nlhdlrExitSepaSoc)

static	SCIP_DECL_NLHDLRENFO (nlhdlrEnfoSoc)

SCIP_RETCODE	SCIPincludeNlhdlrSoc (SCIP *scip)

SCIP_RETCODE	SCIPisSOCNonlinear (SCIP scip, SCIP_CONS cons, SCIP_Bool compeigenvalues, SCIP_Bool success, SCIP_SIDETYPE sidetype, SCIP_VAR *vars, SCIP_Real offsets, SCIP_Real transcoefs, int transcoefsidx, int *termbegins, int nvars, int *nterms)

void	SCIPfreeSOCArraysNonlinear (SCIP scip, SCIP_VAR vars, SCIP_Real offsets, SCIP_Real transcoefs, int transcoefsidx, int **termbegins, int nvars, int nterms)

Macro Definition Documentation

◆ NLHDLR_NAME

#define NLHDLR_NAME "soc"

Definition at line 47 of file nlhdlr_soc.c.

Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), and SCIPincludeNlhdlrSoc().

◆ NLHDLR_DESC

#define NLHDLR_DESC "nonlinear handler for second-order cone structures"

Definition at line 48 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ NLHDLR_DETECTPRIORITY

#define NLHDLR_DETECTPRIORITY 100

priority of the nonlinear handler for detection

Definition at line 49 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ NLHDLR_ENFOPRIORITY

#define NLHDLR_ENFOPRIORITY 100

priority of the nonlinear handler for enforcement

Definition at line 50 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ DEFAULT_MINCUTEFFICACY

#define DEFAULT_MINCUTEFFICACY 1e-5

default value for parameter mincutefficacy

Definition at line 51 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ DEFAULT_COMPEIGENVALUES

#define DEFAULT_COMPEIGENVALUES TRUE

default value for parameter compeigenvalues

Definition at line 52 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ nlhdlrInitSoc

#define nlhdlrInitSoc NULL

callback to be called in initialization

Definition at line 2269 of file nlhdlr_soc.c.

Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA(), and SCIPincludeNlhdlrSoc().

◆ nlhdlrExitSoc

#define nlhdlrExitSoc NULL

callback to be called in deinitialization

Definition at line 2284 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

Function Documentation

◆ createDisaggrVars()

static SCIP_RETCODE createDisaggrVars	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata
	)

static

helper method to create variables for the cone disaggregation

Parameters

scip	SCIP data structure
expr	expression
nlhdlrexprdata	nonlinear handler expression data

Definition at line 205 of file nlhdlr_soc.c.

References NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPaddVar(), SCIPaddVarLocksType(), SCIPallocBlockMemoryArray, SCIPcreateVarBasic(), SCIPinfinity(), SCIPsnprintf(), and SCIPvarMarkRelaxationOnly().

Referenced by SCIP_DECL_NLHDLRINITSEPA().

◆ freeDisaggrVars()

static SCIP_RETCODE freeDisaggrVars	(	SCIP *	scip,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata
	)

static

helper method to free variables for the cone disaggregation

Parameters

scip	SCIP data structure
nlhdlrexprdata	nonlinear handler expression data

Definition at line 239 of file nlhdlr_soc.c.

References NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().

Referenced by freeNlhdlrExprData().

◆ createDisaggrRow()

static SCIP_RETCODE createDisaggrRow	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_EXPR *	expr,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata
	)

static

helper method to create the disaggregation row \(\text{disvars}_i \leq v_{n+1}^T x + \beta_{n+1}\)

Parameters

scip	SCIP data structure
conshdlr	nonlinear constraint handler
expr	expression
nlhdlrexprdata	nonlinear handler expression data

Definition at line 269 of file nlhdlr_soc.c.

References FALSE, nterms, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcreateEmptyRowConshdlr(), SCIPgetExprAuxVarNonlinear(), SCIPinfinity(), SCIPsnprintf(), and TRUE.

Referenced by SCIP_DECL_NLHDLRINITSEPA().

◆ createNlhdlrExprData()

static SCIP_RETCODE createNlhdlrExprData	(	SCIP *	scip,
		SCIP_EXPR **	vars,
		SCIP_Real *	offsets,
		SCIP_Real *	transcoefs,
		int *	transcoefsidx,
		int *	termbegins,
		int	nvars,
		int	nterms,
		SCIP_NLHDLREXPRDATA **	nlhdlrexprdata
	)

static

helper method to create nonlinear handler expression data

Parameters

scip	SCIP data structure
vars	expressions which variables appear on both sides ( \(x\))
offsets	offsets of bot sides ( \(beta_i\))
transcoefs	non-zeroes of linear transformation vectors ( \(v_i\))
transcoefsidx	mapping of transformation coefficients to variable indices in vars
termbegins	starting indices of transcoefs for each term
nvars	total number of variables appearing
nterms	number of summands in the SQRT, +1 for RHS
nlhdlrexprdata	pointer to store nonlinear handler expression data

Definition at line 322 of file nlhdlr_soc.c.

References nterms, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory(), SCIPdebugMsg, and SCIPduplicateBlockMemoryArray.

Referenced by detectSocNorm(), detectSocQuadraticComplex(), and detectSocQuadraticSimple().

◆ freeNlhdlrExprData()

static SCIP_RETCODE freeNlhdlrExprData	(	SCIP *	scip,
		SCIP_NLHDLREXPRDATA **	nlhdlrexprdata
	)

static

helper method to free nonlinear handler expression data

Parameters

scip	SCIP data structure
nlhdlrexprdata	pointer to free nonlinear handler expression data

Definition at line 368 of file nlhdlr_soc.c.

References freeDisaggrVars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA(), and SCIPisSOCNonlinear().

◆ evalSingleTerm()

static SCIP_Real evalSingleTerm	(	SCIP *	scip,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata,
		SCIP_SOL *	sol,
		int	k
	)

static

evaluate a single term of the form \(v_i^T x + \beta_i\)

Parameters

scip	SCIP data structure
nlhdlrexprdata	nonlinear handler expression data
sol	solution
k	term to be evaluated

Definition at line 395 of file nlhdlr_soc.c.

References nterms, NULL, SCIP_Real, SCIPgetExprAuxVarNonlinear(), and SCIPgetSolVal().

Referenced by generateCutSolDisagg(), generateCutSolSOC(), SCIP_DECL_NLHDLRENFO(), and SCIP_DECL_NLHDLREVALAUX().

◆ generateCutSolSOC()

static SCIP_RETCODE generateCutSolSOC	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata,
		SCIP_Real	mincutviolation,
		SCIP_Real	rhsval,
		SCIP_ROW **	cut
	)

static

computes gradient cut for a 2D or 3D SOC

A 3D SOC looks like

\[ \sqrt{ (v_1^T x + \beta_1)^2 + (v_2^T x + \beta_2)^2 } \leq v_3^T x + \beta_3 \]

Let \(f(x)\) be the left-hand-side. The partial derivatives of \(f\) are given by

\[ \frac{\delta f}{\delta x_j} = \frac{(v_1)_j(v_1^T x + \beta_1) + (v_2)_j (v_2^T x + \beta_2)}{f(x)} \]

and the gradient cut is then \(f(x^*) + \nabla f(x^*)(x - x^*) \leq v_3^T x + \beta_3\).

A 2D SOC is

\[ |v_1^T x + \beta_1| \leq v_2^T x + \beta_2 \]

but we build the cut using the same procedure as for 3D.

Parameters

scip	SCIP data structure
expr	expression
cons	the constraint that expr is part of
sol	solution to separate or NULL for the LP solution
nlhdlrexprdata	nonlinear handler expression data
mincutviolation	minimal required cut violation
rhsval	value of last term at sol
cut	pointer to store a cut

Definition at line 441 of file nlhdlr_soc.c.

References evalSingleTerm(), FALSE, nterms, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_RIGHT, SCIPaddRowprepTerm(), SCIPcleanupRowprep2(), SCIPcreateRowprep(), SCIPdebugMsg, SCIPensureRowprepSize(), SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetNLPs(), SCIPgetRowprepRowCons(), SCIPgetRowprepViolation(), SCIPgetSolVal(), SCIPinfinity(), SCIProwprepAddSide(), SCIProwprepGetName(), and SCIPsnprintf().

Referenced by SCIP_DECL_NLHDLRENFO().

◆ generateCutSolDisagg()

static SCIP_RETCODE generateCutSolDisagg	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata,
		int	disaggidx,
		SCIP_Real	mincutviolation,
		SCIP_Real	rhsval,
		SCIP_ROW **	cut
	)

static

helper method to compute and add a gradient cut for the k-th cone disaggregation

After the SOC constraint \(\sqrt{\sum_{i = 0}^{n-1} (v_i^T x + \beta_i)^2} \leq v_n^T x + \beta_n\) has been disaggregated into the row \(\sum_{i = 0}^{n-1} y_i \leq v_n^T x + \beta_n\) and the smaller SOC constraints

\[ (v_i^T x + \beta_i)^2 \leq (v_n^T x + \beta_n) y_i \text{ for } i \in \{0, \ldots, n -1\}, \]

we want to separate one of the small rotated cones. We first transform it into standard form:

\[ \sqrt{4(v_i^T x + \beta_i)^2 + (v_n^T x + \beta_n - y_i)^2} - v_n^T x - \beta_n - y_i \leq 0. \]

Let \(f(x,y)\) be the left-hand-side. We now compute the gradient by

\begin{align*} \frac{\delta f}{\delta x_j} &= \frac{(v_i)_j(4v_i^T x + 4\beta_i) + (v_n)_j(v_n^T x + \beta_n - y_i)}{\sqrt{4(v_i^T x + \beta_i)^2 + (v_n^T x + \beta_n - y_i)^2}} - (v_n)_j \\ \frac{\delta f}{\delta y_i} &= \frac{y_i - v_n^T x -\beta_n}{\sqrt{4(v_i^T x + \beta_i)^2 + (v_n^T x + \beta_n - y_i)^2}} - 1 \end{align*}

and the gradient cut is then \(f(x^*, y^*) + \nabla f(x^*,y^*)((x,y) - (x^*, y^*)) \leq 0\).

Parameters

scip	SCIP data structure
expr	expression
cons	the constraint that expr is part of
sol	solution to separate or NULL for the LP solution
nlhdlrexprdata	nonlinear handler expression data
disaggidx	index of disaggregation to separate
mincutviolation	minimal required cut violation
rhsval	value of the rhs term
cut	pointer to store a cut

Definition at line 577 of file nlhdlr_soc.c.

References evalSingleTerm(), FALSE, nterms, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_RIGHT, SCIPaddRowprepTerm(), SCIPcleanupRowprep2(), SCIPcreateRowprep(), SCIPdebugMsg, SCIPensureRowprepSize(), SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetNLPs(), SCIPgetRowprepRowCons(), SCIPgetRowprepViolation(), SCIPgetSolVal(), SCIPinfinity(), SCIPisZero(), SCIProwprepAddSide(), SCIProwprepGetName(), and SCIPsnprintf().

Referenced by SCIP_DECL_NLHDLRENFO().

◆ checkAndCollectQuadratic()

static SCIP_RETCODE checkAndCollectQuadratic	(	SCIP *	scip,
		SCIP_EXPR *	quadexpr,
		SCIP_HASHMAP *	expr2idx,
		SCIP_EXPR **	occurringexprs,
		int *	nexprs,
		SCIP_Bool *	success
	)

static

checks if an expression is quadratic and collects all occurring expressions

Precondition: expr2idx and occurringexprs need to be initialized with capacity 2 * nchildren

Note: We assume that a linear term always appears before its corresponding quadratic term in quadexpr; this should be ensured by canonicalize

Parameters

scip	SCIP data structure
quadexpr	candidate for a quadratic expression
expr2idx	hashmap to store expressions
occurringexprs	array to store expressions
nexprs	buffer to store number of expressions
success	buffer to store whether the check was successful

Definition at line 725 of file nlhdlr_soc.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetExponentExprPow(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapInsertInt(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprVar(), SCIPvarIsBinary(), and TRUE.

Referenced by detectSocQuadraticComplex().

◆ buildQuadExprMatrix()

static void buildQuadExprMatrix	(	SCIP *	scip,
		SCIP_EXPR *	quadexpr,
		SCIP_HASHMAP *	expr2idx,
		int	nexprs,
		SCIP_Real *	quadmatrix,
		SCIP_Real *	linvector
	)

static

Parameters

scip	SCIP data structure
quadexpr	the quadratic expression
expr2idx	hashmap mapping the occurring expressions to their index
nexprs	number of occurring expressions
quadmatrix	pointer to store (the lower-left triangle of) the quadratic matrix
linvector	pointer to store the linear vector

Definition at line 840 of file nlhdlr_soc.c.

References MAX, NULL, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetExponentExprPow(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprVar(), and SCIPvarIsBinary().

Referenced by detectSocQuadraticComplex().

◆ tryFillNlhdlrExprDataQuad()

static SCIP_RETCODE tryFillNlhdlrExprDataQuad	(	SCIP *	scip,
		SCIP_EXPR **	occurringexprs,
		SCIP_Real *	eigvecmatrix,
		SCIP_Real *	eigvals,
		SCIP_Real *	bp,
		int	nvars,
		int *	termbegins,
		SCIP_Real *	transcoefs,
		int *	transcoefsidx,
		SCIP_Real *	offsets,
		SCIP_Real *	lhsconstant,
		int *	nterms,
		SCIP_Bool *	success
	)

static

tries to fill the nlhdlrexprdata for a potential quadratic SOC expression

We say "try" because the expression might still turn out not to be a SOC at this point.

Parameters

scip	SCIP data structure
occurringexprs	array of all occurring expressions (nvars many)
eigvecmatrix	array containing the Eigenvectors
eigvals	array containing the Eigenvalues
bp	product of linear vector b * P (eigvecmatrix^t)
nvars	number of variables
termbegins	pointer to store the termbegins
transcoefs	pointer to store the transcoefs
transcoefsidx	pointer to store the transcoefsidx
offsets	pointer to store the offsets
lhsconstant	pointer to store the lhsconstant
nterms	pointer to store the total number of terms
success	whether the expression is indeed a SOC

Definition at line 921 of file nlhdlr_soc.c.

References FALSE, SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisZero(), SCIPswapReals(), SCIP_Interval::sup, and TRUE.

Referenced by detectSocQuadraticComplex().

◆ detectSocNorm()

static SCIP_RETCODE detectSocNorm	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_NLHDLREXPRDATA **	nlhdlrexprdata,
		SCIP_Bool *	success
	)

static

detects if expr ≤ auxvar is of the form SQRT(sum_i coef_i (expr_i + shift_i)^2 + const) ≤ auxvar

Note: if a user inputs the above expression with const = -epsilon, then const is going to be set to 0.

Parameters

scip	SCIP data structure
expr	expression
nlhdlrexprdata	pointer to store nonlinear handler expression data
success	pointer to store whether SOC structure has been detected

Definition at line 1148 of file nlhdlr_soc.c.

References createNlhdlrExprData(), FALSE, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExponentExprPow(), SCIPgetExprNLocksPosNonlinear(), SCIPgetVarExprVar(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetGetNElements(), SCIPhashsetInsert(), SCIPhashsetRemove(), SCIPinfoMessage(), SCIPisExprPower(), SCIPisExprSum(), SCIPisExprVar(), SCIPisNegative(), SCIPisZero(), SCIPprintExpr(), SCIPregisterExprUsageNonlinear(), SCIPvarIsBinary(), and TRUE.

Referenced by detectSOC().

◆ detectSocQuadraticSimple()

static SCIP_RETCODE detectSocQuadraticSimple	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_Real	conslhs,
		SCIP_Real	consrhs,
		SCIP_NLHDLREXPRDATA **	nlhdlrexprdata,
		SCIP_Bool *	enforcebelow,
		SCIP_Bool *	success
	)

static

helper method to detect c + sum_i coef_i expr_i^2 - coef_k expr_k^2 ≤ 0 and c + sum_i coef_i expr_i^2 - coef_k expr_k expr_l ≤ 0

binary linear variables are interpreted as quadratic terms

Parameters

scip	SCIP data structure
expr	expression
conslhs	lhs of the constraint that the expression defines (or SCIP_INVALID)
consrhs	rhs of the constraint that the expression defines (or SCIP_INVALID)
nlhdlrexprdata	pointer to store nonlinear handler expression data
enforcebelow	pointer to store whether we enforce <= (TRUE) or >= (FALSE); only valid when success is TRUE
success	pointer to store whether SOC structure has been detected

Definition at line 1432 of file nlhdlr_soc.c.

References createNlhdlrExprData(), FALSE, SCIP_Interval::inf, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfreeBufferArrayNull, SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExponentExprPow(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisExprVar(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPprintExpr(), SCIPregisterExprUsageNonlinear(), SCIPvarIsBinary(), SCIP_Interval::sup, and TRUE.

Referenced by detectSOC().

◆ detectSocQuadraticComplex()

static SCIP_RETCODE detectSocQuadraticComplex	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_Real	conslhs,
		SCIP_Real	consrhs,
		SCIP_NLHDLREXPRDATA **	nlhdlrexprdata,
		SCIP_Bool *	enforcebelow,
		SCIP_Bool *	success
	)

static

detects complex quadratic expressions that can be represented as SOC constraints

These are quadratic expressions with either exactly one positive or exactly one negative eigenvalue, in addition to some extra conditions. One needs to write the quadratic as sum eigval_i (eigvec_i . x)^2 + c ≤ -eigval_k (eigvec_k . x)^2, where eigval_k is the negative eigenvalue, and c must be positive and (eigvec_k . x) must not change sign. This is described in more details in Mahajan, Ashutosh & Munson, Todd, Exploiting Second-Order Cone Structure for Global Optimization, 2010.

The eigen-decomposition is computed using Lapack. Binary linear variables are interpreted as quadratic terms.

Parameters

scip	SCIP data structure
expr	expression
conslhs	lhs of the constraint that the expression defines (or SCIP_INVALID)
consrhs	rhs of the constraint that the expression defines (or SCIP_INVALID)
nlhdlrexprdata	pointer to store nonlinear handler expression data
enforcebelow	pointer to store whether we enforce <= (TRUE) or >= (FALSE); only valid when success is TRUE
success	pointer to store whether SOC structure has been detected

Definition at line 1900 of file nlhdlr_soc.c.

References buildQuadExprMatrix(), checkAndCollectQuadratic(), createNlhdlrExprData(), FALSE, SCIP_Interval::inf, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPcallLapackDsyevIpopt(), SCIPdebugMsg, SCIPdismantleExpr(), SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetConstantExprSum(), SCIPgetExprNLocksNegNonlinear(), SCIPgetExprNLocksPosNonlinear(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetNElements(), SCIPinfoMessage(), SCIPisExprSum(), SCIPisIpoptAvailableIpopt(), SCIPisZero(), SCIPprintExpr(), SCIPregisterExprUsageNonlinear(), SCIPverbMessage(), SCIP_Interval::sup, TRUE, and tryFillNlhdlrExprDataQuad().

Referenced by detectSOC().

◆ detectSOC()

static SCIP_RETCODE detectSOC	(	SCIP *	scip,
		SCIP_NLHDLRDATA *	nlhdlrdata,
		SCIP_EXPR *	expr,
		SCIP_Real	conslhs,
		SCIP_Real	consrhs,
		SCIP_NLHDLREXPRDATA **	nlhdlrexprdata,
		SCIP_Bool *	enforcebelow,
		SCIP_Bool *	success
	)

static

helper method to detect SOC structures

The detection runs in 3 steps:

check if expression is a norm of the form \(\sqrt{\sum_i (\text{sqrcoef}_i\, \text{expr}_i^2 + \text{lincoef}_i\, \text{expr}_i) + c}\) which can be transformed to the form \(\sqrt{\sum_i (\text{coef}_i \text{expr}_i + \text{const}_i)^2 + c^*}\) with \(c^* \geq 0\).
-> this results in the SOC expr ≤ auxvar(expr)

TODO we should generalize and check for sqrt(positive-semidefinite-quadratic)
check if expression represents a quadratic function of one of the following forms (all coefs > 0)
1. \((\sum_i \text{coef}_i \text{expr}_i^2) - \text{coef}_k \text{expr}_k^2 \leq \text{RHS}\) or
2. \((\sum_i - \text{coef}_i \text{expr}_i^2) + \text{coef}_k \text{expr}_k^2 \geq \text{LHS}\) or
3. \((\sum_i \text{coef}_i \text{expr}_i^2) - \text{coef}_k \text{expr}_k \text{expr}_l \leq \text{RHS}\) or
4. \((\sum_i - \text{coef}_i \text{expr}_i^2) + \text{coef}_k \text{expr}_k \text{expr}_l \geq \text{LHS}\),
where RHS ≥ 0 or LHS ≤ 0, respectively. For LHS and RHS we use the constraint sides if it is a root expr and the bounds of the auxiliary variable otherwise. The last two cases are called hyperbolic or rotated second order cone.
-> this results in the SOC \(\sqrt{(\sum_i \text{coef}_i \text{expr}_i^2) - \text{RHS}} \leq \sqrt{\text{coef}_k} \text{expr}_k\) or \(\sqrt{4(\sum_i \text{coef}_i \text{expr}_i^2) - 4\text{RHS} + (\text{expr}_k - \text{expr}_l)^2)} \leq \text{expr}_k + \text{expr}_l\). (analogously for the LHS cases)
check if expression represents a quadratic inequality of the form \(f(x) = x^TAx + b^Tx + c \leq 0\) such that \(f(x)\) has exactly one negative eigenvalue plus some extra conditions, see detectSocQuadraticComplex().

Note that step 3 is only performed if parameter compeigenvalues is set to TRUE.

Parameters

scip	SCIP data structure
nlhdlrdata	nonlinear handler data
expr	expression
conslhs	lhs of the constraint that the expression defines (or SCIP_INVALID)
consrhs	rhs of the constraint that the expression defines (or SCIP_INVALID)
nlhdlrexprdata	pointer to store nonlinear handler expression data
enforcebelow	pointer to store whether we enforce <= (TRUE) or >= (FALSE); only valid when success is TRUE
success	pointer to store whether SOC structure has been detected

Definition at line 2174 of file nlhdlr_soc.c.

References detectSocNorm(), detectSocQuadraticComplex(), detectSocQuadraticSimple(), FALSE, NULL, SCIP_CALL, SCIP_INVALID, and SCIP_OKAY.

Referenced by SCIP_DECL_NLHDLRDETECT(), and SCIPisSOCNonlinear().

◆ SCIP_DECL_NLHDLRCOPYHDLR()

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrSoc )

static

nonlinear handler copy callback

Definition at line 2224 of file nlhdlr_soc.c.

References NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrSoc(), and SCIPnlhdlrGetName().

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrFreehdlrdataSoc )

static

callback to free data of handler

Definition at line 2237 of file nlhdlr_soc.c.

References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

static SCIP_DECL_NLHDLRFREEEXPRDATA ( nlhdlrFreeExprDataSoc )

static

callback to free expression specific data

Definition at line 2248 of file nlhdlr_soc.c.

References freeNlhdlrExprData(), nlhdlrInitSoc, NULL, SCIP_CALL, SCIP_DECL_NLHDLRINIT, SCIP_OKAY, SCIPABORT, and SCIPerrorMessage.

◆ SCIP_DECL_NLHDLRDETECT()

static SCIP_DECL_NLHDLRDETECT ( nlhdlrDetectSoc )

static

callback to detect structure in expression tree

Definition at line 2290 of file nlhdlr_soc.c.

References detectSOC(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_Real, SCIPgetExponentExprPow(), SCIPgetExprNAuxvarUsesNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPisExprPower(), and SCIPnlhdlrGetData().

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalauxSoc )

static

auxiliary evaluation callback of nonlinear handler

Definition at line 2337 of file nlhdlr_soc.c.

References evalSingleTerm(), NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExponentExprPow(), SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), SCIPisExprPower(), SCIPisExprProduct(), and SCIPisExprSum().

◆ SCIP_DECL_NLHDLRINITSEPA()

static SCIP_DECL_NLHDLRINITSEPA ( nlhdlrInitSepaSoc )

static

separation deinitialization method of a nonlinear handler (called during CONSINITLP)

Definition at line 2429 of file nlhdlr_soc.c.

References createDisaggrRow(), createDisaggrVars(), nterms, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPgetVarExprVar(), and SCIPisZero().

◆ SCIP_DECL_NLHDLREXITSEPA()

static SCIP_DECL_NLHDLREXITSEPA ( nlhdlrExitSepaSoc )

static

separation deinitialization method of a nonlinear handler (called during CONSEXITSOL)

Definition at line 2521 of file nlhdlr_soc.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPreleaseRow().

◆ SCIP_DECL_NLHDLRENFO()

static SCIP_DECL_NLHDLRENFO ( nlhdlrEnfoSoc )

static

nonlinear handler separation callback

Definition at line 2537 of file nlhdlr_soc.c.

References evalSingleTerm(), FALSE, generateCutSolDisagg(), generateCutSolSOC(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPdebugMsg, SCIPgetCutEfficacy(), SCIPgetLPFeastol(), SCIPgetRowSolFeasibility(), SCIPisCutApplicable(), SCIPmarkRowNotRemovableLocal(), SCIPnlhdlrGetData(), SCIPreleaseRow(), SCIProwIsInLP(), and TRUE.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ NLHDLR_NAME

◆ NLHDLR_DESC

◆ NLHDLR_DETECTPRIORITY

◆ NLHDLR_ENFOPRIORITY

◆ DEFAULT_MINCUTEFFICACY

◆ DEFAULT_COMPEIGENVALUES

◆ nlhdlrInitSoc

◆ nlhdlrExitSoc

Function Documentation

◆ createDisaggrVars()

◆ freeDisaggrVars()

◆ createDisaggrRow()

◆ createNlhdlrExprData()

◆ freeNlhdlrExprData()

◆ evalSingleTerm()

◆ generateCutSolSOC()

◆ generateCutSolDisagg()

◆ checkAndCollectQuadratic()

◆ buildQuadExprMatrix()

◆ tryFillNlhdlrExprDataQuad()

◆ detectSocNorm()

◆ detectSocQuadraticSimple()

◆ detectSocQuadraticComplex()

◆ detectSOC()

◆ SCIP_DECL_NLHDLRCOPYHDLR()

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

◆ SCIP_DECL_NLHDLRDETECT()

◆ SCIP_DECL_NLHDLREVALAUX()

◆ SCIP_DECL_NLHDLRINITSEPA()

◆ SCIP_DECL_NLHDLREXITSEPA()

◆ SCIP_DECL_NLHDLRENFO()