Scippy

SCIP

Solving Constraint Integer Programs

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 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 2278 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 2293 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
scipSCIP data structure
exprexpression
nlhdlrexprdatanonlinear handler expression data

Definition at line 214 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
scipSCIP data structure
nlhdlrexprdatanonlinear handler expression data

Definition at line 248 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
scipSCIP data structure
conshdlrnonlinear constraint handler
exprexpression
nlhdlrexprdatanonlinear handler expression data

Definition at line 278 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
scipSCIP data structure
varsexpressions which variables appear on both sides ( \(x\))
offsetsoffsets of bot sides ( \(beta_i\))
transcoefsnon-zeroes of linear transformation vectors ( \(v_i\))
transcoefsidxmapping of transformation coefficients to variable indices in vars
termbeginsstarting indices of transcoefs for each term
nvarstotal number of variables appearing
ntermsnumber of summands in the SQRT, +1 for RHS
nlhdlrexprdatapointer to store nonlinear handler expression data

Definition at line 331 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
scipSCIP data structure
nlhdlrexprdatapointer to free nonlinear handler expression data

Definition at line 377 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
scipSCIP data structure
nlhdlrexprdatanonlinear handler expression data
solsolution
kterm to be evaluated

Definition at line 404 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
scipSCIP data structure
exprexpression
consthe constraint that expr is part of
solsolution to separate or NULL for the LP solution
nlhdlrexprdatanonlinear handler expression data
mincutviolationminimal required cut violation
rhsvalvalue of last term at sol
cutpointer to store a cut

Definition at line 450 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
scipSCIP data structure
exprexpression
consthe constraint that expr is part of
solsolution to separate or NULL for the LP solution
nlhdlrexprdatanonlinear handler expression data
disaggidxindex of disaggregation to separate
mincutviolationminimal required cut violation
rhsvalvalue of the rhs term
cutpointer to store a cut

Definition at line 586 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
scipSCIP data structure
quadexprcandidate for a quadratic expression
expr2idxhashmap to store expressions
occurringexprsarray to store expressions
nexprsbuffer to store number of expressions
successbuffer to store whether the check was successful

Definition at line 734 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
scipSCIP data structure
quadexprthe quadratic expression
expr2idxhashmap mapping the occurring expressions to their index
nexprsnumber of occurring expressions
quadmatrixpointer to store (the lower-left triangle of) the quadratic matrix
linvectorpointer to store the linear vector

Definition at line 849 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
scipSCIP data structure
occurringexprsarray of all occurring expressions (nvars many)
eigvecmatrixarray containing the Eigenvectors
eigvalsarray containing the Eigenvalues
bpproduct of linear vector b * P (eigvecmatrix^t)
nvarsnumber of variables
termbeginspointer to store the termbegins
transcoefspointer to store the transcoefs
transcoefsidxpointer to store the transcoefsidx
offsetspointer to store the offsets
lhsconstantpointer to store the lhsconstant
ntermspointer to store the total number of terms
successwhether the expression is indeed a SOC

Definition at line 930 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
scipSCIP data structure
exprexpression
nlhdlrexprdatapointer to store nonlinear handler expression data
successpointer to store whether SOC structure has been detected

Definition at line 1157 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
scipSCIP data structure
exprexpression
conslhslhs of the constraint that the expression defines (or SCIP_INVALID)
consrhsrhs of the constraint that the expression defines (or SCIP_INVALID)
nlhdlrexprdatapointer to store nonlinear handler expression data
enforcebelowpointer to store whether we enforce <= (TRUE) or >= (FALSE); only valid when success is TRUE
successpointer to store whether SOC structure has been detected

Definition at line 1441 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
scipSCIP data structure
exprexpression
conslhslhs of the constraint that the expression defines (or SCIP_INVALID)
consrhsrhs of the constraint that the expression defines (or SCIP_INVALID)
nlhdlrexprdatapointer to store nonlinear handler expression data
enforcebelowpointer to store whether we enforce <= (TRUE) or >= (FALSE); only valid when success is TRUE
successpointer to store whether SOC structure has been detected

Definition at line 1909 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:

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

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

  3. 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
scipSCIP data structure
nlhdlrdatanonlinear handler data
exprexpression
conslhslhs of the constraint that the expression defines (or SCIP_INVALID)
consrhsrhs of the constraint that the expression defines (or SCIP_INVALID)
nlhdlrexprdatapointer to store nonlinear handler expression data
enforcebelowpointer to store whether we enforce <= (TRUE) or >= (FALSE); only valid when success is TRUE
successpointer to store whether SOC structure has been detected

Definition at line 2183 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 2233 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 2246 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 2257 of file nlhdlr_soc.c.

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

◆ SCIP_DECL_NLHDLRDETECT()

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalauxSoc  )
static

◆ SCIP_DECL_NLHDLRINITSEPA()

static SCIP_DECL_NLHDLRINITSEPA ( nlhdlrInitSepaSoc  )
static

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

Definition at line 2438 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 2530 of file nlhdlr_soc.c.

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

◆ SCIP_DECL_NLHDLRENFO()