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

◆ NLHDLR_DESC

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

Definition at line 57 of file nlhdlr_soc.c.

◆ NLHDLR_DETECTPRIORITY

#define NLHDLR_DETECTPRIORITY   100

priority of the nonlinear handler for detection

Definition at line 58 of file nlhdlr_soc.c.

◆ NLHDLR_ENFOPRIORITY

#define NLHDLR_ENFOPRIORITY   100

priority of the nonlinear handler for enforcement

Definition at line 59 of file nlhdlr_soc.c.

◆ DEFAULT_MINCUTEFFICACY

#define DEFAULT_MINCUTEFFICACY   1e-5

default value for parameter mincutefficacy

Definition at line 60 of file nlhdlr_soc.c.

◆ DEFAULT_COMPEIGENVALUES

#define DEFAULT_COMPEIGENVALUES   TRUE

default value for parameter compeigenvalues

Definition at line 61 of file nlhdlr_soc.c.

◆ nlhdlrInitSoc

#define nlhdlrInitSoc   NULL

callback to be called in initialization

Definition at line 2419 of file nlhdlr_soc.c.

◆ nlhdlrExitSoc

#define nlhdlrExitSoc   NULL

callback to be called in deinitialization

Definition at line 2434 of file nlhdlr_soc.c.

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 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
scipSCIP data structure
nlhdlrexprdatanonlinear 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
scipSCIP data structure
conshdlrnonlinear constraint handler
exprexpression
nlhdlrexprdatanonlinear 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
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 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
scipSCIP data structure
nlhdlrexprdatapointer 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
scipSCIP data structure
nlhdlrexprdatanonlinear handler expression data
solSCIP solution
roundtinyfracwhether 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
scipSCIP data structure
nlhdlrexprdatanonlinear handler expression data
kterm 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
scipSCIP data structure
rowprepbuffer to store rowprep with cut data
exprexpression
consthe constraint that expr is part of
nlhdlrexprdatanonlinear handler expression data
mincutviolationminimal required cut violation
rhsvalvalue 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
scipSCIP data structure
rowprepbuffer to store rowprep with cut data
exprexpression
consthe constraint that expr is part of
nlhdlrexprdatanonlinear handler expression data
disaggidxindex of disaggregation to separate
mincutviolationminimal required cut violation
rhsvalvalue 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
scipSCIP data structure
nlhdlrdatanonlinear handler data
rowpreprowprep from which to generate row and add as cut
solsolution to be separated
consconstraint for which cut is generated, or NULL
allowweakcutswhether weak cuts are allowed
resultresult 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
scipSCIP data structure
nlhdlrdatanonlinear handler data
rowpreprowprep from which to generate row and add as cut
solsolution to be separated
consconstraint 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
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 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
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 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
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 1071 of file nlhdlr_soc.c.

References FALSE, SCIP_Interval::inf, nterms, 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 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
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 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
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 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:

  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 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(), NULL, SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_NLHDLRDETECT()

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalauxSoc  )
static

◆ SCIP_DECL_NLHDLRINITSEPA()

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

◆ SCIP_DECL_NLHDLRSOLLINEARIZE()

static SCIP_DECL_NLHDLRSOLLINEARIZE ( nlhdlrSollinearizeSoc  )
static