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/lapack_calls.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 void	updateVarVals (SCIP scip, SCIP_NLHDLREXPRDATA nlhdlrexprdata, SCIP_SOL *sol, SCIP_Bool roundtinyfrac)

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

static SCIP_RETCODE	generateCutSolSOC (SCIP scip, SCIP_ROWPREP rowprep, SCIP_EXPR expr, SCIP_CONS cons, SCIP_NLHDLREXPRDATA nlhdlrexprdata, SCIP_Real mincutviolation, SCIP_Real rhsval)

static SCIP_RETCODE	generateCutSolDisagg (SCIP scip, SCIP_ROWPREP rowprep, SCIP_EXPR expr, SCIP_CONS cons, SCIP_NLHDLREXPRDATA nlhdlrexprdata, int disaggidx, SCIP_Real mincutviolation, SCIP_Real rhsval)

static SCIP_RETCODE	addCut (SCIP scip, SCIP_NLHDLRDATA nlhdlrdata, SCIP_ROWPREP rowprep, SCIP_SOL sol, SCIP_CONS cons, SCIP_Bool allowweakcuts, SCIP_RESULT result)

static SCIP_RETCODE	addCutPool (SCIP scip, SCIP_NLHDLRDATA nlhdlrdata, SCIP_ROWPREP rowprep, SCIP_SOL sol, SCIP_CONS *cons)

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)

static	SCIP_DECL_NLHDLRSOLLINEARIZE (nlhdlrSollinearizeSoc)

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 56 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 57 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ NLHDLR_DETECTPRIORITY

#define NLHDLR_DETECTPRIORITY 100

priority of the nonlinear handler for detection

Definition at line 58 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ NLHDLR_ENFOPRIORITY

#define NLHDLR_ENFOPRIORITY 100

priority of the nonlinear handler for enforcement

Definition at line 59 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ DEFAULT_MINCUTEFFICACY

#define DEFAULT_MINCUTEFFICACY 1e-5

default value for parameter mincutefficacy

Definition at line 60 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ DEFAULT_COMPEIGENVALUES

#define DEFAULT_COMPEIGENVALUES TRUE

default value for parameter compeigenvalues

Definition at line 61 of file nlhdlr_soc.c.

Referenced by SCIPincludeNlhdlrSoc().

◆ nlhdlrInitSoc

#define nlhdlrInitSoc NULL

callback to be called in initialization

Definition at line 2419 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 2434 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 216 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 251 of file nlhdlr_soc.c.

References NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPfreeBlockMemoryArray, 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 282 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 335 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 384 of file nlhdlr_soc.c.

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

Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA(), and SCIPisSOCNonlinear().

◆ updateVarVals()

static void updateVarVals	(	SCIP *	scip,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata,
		SCIP_SOL *	sol,
		SCIP_Bool	roundtinyfrac
	)

static

set varvalrs in nlhdlrexprdata to values from given SCIP solution

Parameters

scip	SCIP data structure
nlhdlrexprdata	nonlinear handler expression data
sol	SCIP solution
roundtinyfrac	whether values close to integers should be rounded

Definition at line 412 of file nlhdlr_soc.c.

References NULL, SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), SCIPisIntegral(), and SCIPround().

Referenced by SCIP_DECL_NLHDLRENFO(), SCIP_DECL_NLHDLREVALAUX(), and SCIP_DECL_NLHDLRSOLLINEARIZE().

◆ evalSingleTerm()

static SCIP_Real evalSingleTerm	(	SCIP *	scip,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata,
		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
k	term to be evaluated

Definition at line 444 of file nlhdlr_soc.c.

References nterms, NULL, and SCIP_Real.

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

◆ generateCutSolSOC()

static SCIP_RETCODE generateCutSolSOC	(	SCIP *	scip,
		SCIP_ROWPREP **	rowprep,
		SCIP_EXPR *	expr,
		SCIP_CONS *	cons,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata,
		SCIP_Real	mincutviolation,
		SCIP_Real	rhsval
	)

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

If \(\beta_1 = \beta_2 = 0\), then the constant on the left-hand-side of the cut becomes zero:

\[ f(x^*) - (\frac{(v_1)_j v_1^T x^* + (v_2)_j v_2^T x^*}{f(x^*)})_j^T x^* = f(x^*) - \frac{1}{f(x^*)} \sum_j ((v_1)_j x_j^* v_1^T x^* + (v_2)_j x_j^* v_2^T x^*) = f(x^*) - \frac{1}{f(x^*)} ((v_1^T x^*)^2 + (v_2^T x^*)^2) = f(x^*) - \frac{1}{f(x^*)} f(x^*)^2 = 0 \]

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
rowprep	buffer to store rowprep with cut data
expr	expression
cons	the constraint that expr is part of
nlhdlrexprdata	nonlinear handler expression data
mincutviolation	minimal required cut violation
rhsval	value of last term at sol

Definition at line 494 of file nlhdlr_soc.c.

References evalSingleTerm(), FALSE, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_RIGHT, SCIPaddRowprepTerm(), SCIPcreateRowprep(), SCIPdebugMsg, SCIPensureRowprepSize(), SCIPgetExprAuxVarNonlinear(), SCIPgetNLPs(), SCIPisZero(), SCIProwprepAddSide(), SCIProwprepGetName(), SCIPsnprintf(), SQR, and TRUE.

Referenced by SCIP_DECL_NLHDLRENFO(), SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRSOLLINEARIZE().

◆ generateCutSolDisagg()

static SCIP_RETCODE generateCutSolDisagg	(	SCIP *	scip,
		SCIP_ROWPREP **	rowprep,
		SCIP_EXPR *	expr,
		SCIP_CONS *	cons,
		SCIP_NLHDLREXPRDATA *	nlhdlrexprdata,
		int	disaggidx,
		SCIP_Real	mincutviolation,
		SCIP_Real	rhsval
	)

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

As in generateCutSolSOC(), the cut constant is zero if \(\beta_i = \beta_n = 0\).

Parameters

scip	SCIP data structure
rowprep	buffer to store rowprep with cut data
expr	expression
cons	the constraint that expr is part of
nlhdlrexprdata	nonlinear handler expression data
disaggidx	index of disaggregation to separate
mincutviolation	minimal required cut violation
rhsval	value of the rhs term

Definition at line 627 of file nlhdlr_soc.c.

References evalSingleTerm(), FALSE, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_RIGHT, SCIPaddRowprepTerm(), SCIPcreateRowprep(), SCIPdebugMsg, SCIPensureRowprepSize(), SCIPgetExprAuxVarNonlinear(), SCIPgetNLPs(), SCIPisZero(), SCIProwprepAddSide(), SCIProwprepGetName(), SCIPsnprintf(), and SQR.

Referenced by SCIP_DECL_NLHDLRENFO(), SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRSOLLINEARIZE().

◆ addCut()

static SCIP_RETCODE addCut	(	SCIP *	scip,
		SCIP_NLHDLRDATA *	nlhdlrdata,
		SCIP_ROWPREP *	rowprep,
		SCIP_SOL *	sol,
		SCIP_CONS *	cons,
		SCIP_Bool	allowweakcuts,
		SCIP_RESULT *	result
	)

static

given a rowprep, does a number of cleanup and checks and, if successful, generate a cut to be added to the sepastorage

Parameters

scip	SCIP data structure
nlhdlrdata	nonlinear handler data
rowprep	rowprep from which to generate row and add as cut
sol	solution to be separated
cons	constraint for which cut is generated, or NULL
allowweakcuts	whether weak cuts are allowed
result	result pointer to update (set to SCIP_CUTOFF or SCIP_SEPARATED if cut is added)

Definition at line 763 of file nlhdlr_soc.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPcleanupRowprep2(), SCIPdebugMsg, SCIPgetCutEfficacy(), SCIPgetHugeValue(), SCIPgetLPFeastol(), SCIPgetRowprepRowCons(), SCIPgetRowprepViolation(), SCIPisCutApplicable(), SCIPmarkRowNotRemovableLocal(), and SCIPreleaseRow().

Referenced by SCIP_DECL_NLHDLRENFO().

◆ addCutPool()

static SCIP_RETCODE addCutPool	(	SCIP *	scip,
		SCIP_NLHDLRDATA *	nlhdlrdata,
		SCIP_ROWPREP *	rowprep,
		SCIP_SOL *	sol,
		SCIP_CONS *	cons
	)

static

given a rowprep, does a number of cleanup and checks and, if successful, generate a cut to be added to the cutpool

Parameters

scip	SCIP data structure
nlhdlrdata	nonlinear handler data
rowprep	rowprep from which to generate row and add as cut
sol	solution to be separated
cons	constraint for which cut is generated, or NULL

Definition at line 831 of file nlhdlr_soc.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddPoolCut(), SCIPcleanupRowprep2(), SCIPgetHugeValue(), SCIPgetRowprepRowCons(), SCIPreleaseRow(), SCIProwprepGetNVars(), and SCIProwprepIsLocal().

Referenced by SCIP_DECL_NLHDLRSOLLINEARIZE().

◆ 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 875 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 990 of file nlhdlr_soc.c.

References MAX, MIN, 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 1071 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 1298 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(), SQR, 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 1582 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 2050 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(), SCIPbuffer(), SCIPdebugMsg, SCIPdismantleExpr(), SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetConstantExprSum(), SCIPgetExprNLocksNegNonlinear(), SCIPgetExprNLocksPosNonlinear(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetNElements(), SCIPinfoMessage(), SCIPisExprSum(), SCIPisZero(), SCIPlapackComputeEigenvalues(), SCIPlapackIsAvailable(), 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 2324 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 2374 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 2387 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 2398 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 2440 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 2487 of file nlhdlr_soc.c.

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

◆ SCIP_DECL_NLHDLRINITSEPA()

static SCIP_DECL_NLHDLRINITSEPA ( nlhdlrInitSepaSoc )

static

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

Definition at line 2581 of file nlhdlr_soc.c.

References BMSclearMemoryArray, createDisaggrRow(), createDisaggrVars(), evalSingleTerm(), FALSE, generateCutSolDisagg(), generateCutSolSOC(), nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPallocBlockMemoryArray, SCIPcleanupRowprep2(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugMsg, SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetHugeValue(), SCIPgetRowprepRowCons(), SCIPinfinity(), SCIPisEQ(), SCIPisZero(), SCIPreleaseRow(), SCIPsortedvecFindInt(), SCIPvarGetName(), and SQR.

◆ SCIP_DECL_NLHDLREXITSEPA()

static SCIP_DECL_NLHDLREXITSEPA ( nlhdlrExitSepaSoc )

static

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

Definition at line 2983 of file nlhdlr_soc.c.

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

◆ SCIP_DECL_NLHDLRENFO()

static SCIP_DECL_NLHDLRENFO ( nlhdlrEnfoSoc )

static

nonlinear handler separation callback

Definition at line 3001 of file nlhdlr_soc.c.

References addCut(), evalSingleTerm(), generateCutSolDisagg(), generateCutSolSOC(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPdebugMsg, SCIPfreeRowprep(), SCIPgetLPFeastol(), SCIPgetRowSolFeasibility(), SCIPnlhdlrGetData(), SCIProwIsInLP(), TRUE, and updateVarVals().

◆ SCIP_DECL_NLHDLRSOLLINEARIZE()

static SCIP_DECL_NLHDLRSOLLINEARIZE ( nlhdlrSollinearizeSoc )

static

Definition at line 3089 of file nlhdlr_soc.c.

References addCutPool(), evalSingleTerm(), generateCutSolDisagg(), generateCutSolSOC(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeRowprep(), SCIPinfinity(), SCIPnlhdlrGetData(), TRUE, and updateVarVals().

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

◆ updateVarVals()

◆ evalSingleTerm()

◆ generateCutSolSOC()

◆ generateCutSolDisagg()

◆ addCut()

◆ addCutPool()

◆ 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()

◆ SCIP_DECL_NLHDLRSOLLINEARIZE()