Detailed Description
nonlinear handler for second order cone constraints
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 |
helper method to create variables for the cone disaggregation
- Parameters
-
scip SCIP data structure expr expression nlhdlrexprdata nonlinear 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 |
helper method to free variables for the cone disaggregation
- Parameters
-
scip SCIP data structure nlhdlrexprdata nonlinear 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 |
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 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 |
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 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 |
helper method to free nonlinear handler expression data
- Parameters
-
scip SCIP data structure nlhdlrexprdata pointer 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 |
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 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 |
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 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 |
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 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 |
checks if an expression is quadratic and collects all occurring expressions
- Precondition
expr2idx
andoccurringexprs
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 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 |
- 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 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 |
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 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 |
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, thenconst
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 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 |
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 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 |
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 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 |
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)
- \((\sum_i \text{coef}_i \text{expr}_i^2) - \text{coef}_k \text{expr}_k^2 \leq \text{RHS}\) or
- \((\sum_i - \text{coef}_i \text{expr}_i^2) + \text{coef}_k \text{expr}_k^2 \geq \text{LHS}\) or
- \((\sum_i \text{coef}_i \text{expr}_i^2) - \text{coef}_k \text{expr}_k \text{expr}_l \leq \text{RHS}\) or
- \((\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 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 |
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 |
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 |
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()
|
static |
callback to detect structure in expression tree
Definition at line 2299 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 |
auxiliary evaluation callback of nonlinear handler
Definition at line 2346 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 |
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 |
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()
|
static |
nonlinear handler separation callback
Definition at line 2546 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.