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/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 |
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) |
#define NLHDLR_NAME "soc" |
Definition at line 56 of file nlhdlr_soc.c.
#define NLHDLR_DESC "nonlinear handler for second-order cone structures" |
Definition at line 57 of file nlhdlr_soc.c.
#define NLHDLR_DETECTPRIORITY 100 |
priority of the nonlinear handler for detection
Definition at line 58 of file nlhdlr_soc.c.
#define NLHDLR_ENFOPRIORITY 100 |
priority of the nonlinear handler for enforcement
Definition at line 59 of file nlhdlr_soc.c.
#define DEFAULT_MINCUTEFFICACY 1e-5 |
default value for parameter mincutefficacy
Definition at line 60 of file nlhdlr_soc.c.
Referenced by SCIPincludeNlhdlrSoc().
#define DEFAULT_COMPEIGENVALUES TRUE |
default value for parameter compeigenvalues
Definition at line 61 of file nlhdlr_soc.c.
Referenced by SCIPincludeNlhdlrSoc().
|
static |
helper method to create variables for the cone disaggregation
scip | SCIP data structure |
expr | expression |
nlhdlrexprdata | nonlinear handler expression data |
Definition at line 216 of file nlhdlr_soc.c.
References assert(), i, 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().
|
static |
helper method to free variables for the cone disaggregation
scip | SCIP data structure |
nlhdlrexprdata | nonlinear handler expression data |
Definition at line 251 of file nlhdlr_soc.c.
References assert(), i, NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().
Referenced by freeNlhdlrExprData().
|
static |
helper method to create the disaggregation row \(\text{disvars}_i \leq v_{n+1}^T x + \beta_{n+1}\)
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 assert(), FALSE, i, nterms, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcreateEmptyRowConshdlr(), SCIPgetExprAuxVarNonlinear(), SCIPinfinity(), SCIPsnprintf(), TRUE, and var.
Referenced by SCIP_DECL_NLHDLRINITSEPA().
|
static |
helper method to create nonlinear handler expression data
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 assert(), nterms, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, and vars.
Referenced by detectSocNorm(), detectSocQuadraticComplex(), and detectSocQuadraticSimple().
|
static |
helper method to free nonlinear handler expression data
scip | SCIP data structure |
nlhdlrexprdata | pointer to free nonlinear handler expression data |
Definition at line 384 of file nlhdlr_soc.c.
References assert(), freeDisaggrVars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPfreeBlockMemoryArrayNull.
Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA(), and SCIPisSOCNonlinear().
|
static |
set varvalrs in nlhdlrexprdata to values from given SCIP solution
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 assert(), i, NULL, SCIP_Bool, SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), SCIPisIntegral(), SCIPround(), and sol.
Referenced by SCIP_DECL_NLHDLRENFO(), SCIP_DECL_NLHDLREVALAUX(), and SCIP_DECL_NLHDLRSOLLINEARIZE().
|
static |
evaluate a single term of the form \(v_i^T x + \beta_i\)
scip | SCIP data structure |
nlhdlrexprdata | nonlinear handler expression data |
k | term to be evaluated |
Definition at line 444 of file nlhdlr_soc.c.
References assert(), i, nterms, NULL, result, and SCIP_Real.
Referenced by generateCutSolDisagg(), generateCutSolSOC(), SCIP_DECL_NLHDLRENFO(), SCIP_DECL_NLHDLREVALAUX(), SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRSOLLINEARIZE().
|
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.
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 assert(), evalSingleTerm(), FALSE, i, 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, TRUE, and vars.
Referenced by SCIP_DECL_NLHDLRENFO(), SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRSOLLINEARIZE().
|
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\).
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 assert(), evalSingleTerm(), FALSE, i, 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 vars.
Referenced by SCIP_DECL_NLHDLRENFO(), SCIP_DECL_NLHDLRINITSEPA(), and SCIP_DECL_NLHDLRSOLLINEARIZE().
|
static |
given a rowprep, does a number of cleanup and checks and, if successful, generate a cut to be added to the sepastorage
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 assert(), FALSE, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPcleanupRowprep2(), SCIPdebugMsg, SCIPgetCutEfficacy(), SCIPgetHugeValue(), SCIPgetLPFeastol(), SCIPgetRowprepRowCons(), SCIPgetRowprepViolation(), SCIPisCutApplicable(), SCIPmarkRowNotRemovableLocal(), SCIPreleaseRow(), and sol.
Referenced by SCIP_DECL_NLHDLRENFO().
|
static |
given a rowprep, does a number of cleanup and checks and, if successful, generate a cut to be added to the cutpool
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 assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddPoolCut(), SCIPcleanupRowprep2(), SCIPgetHugeValue(), SCIPgetRowprepRowCons(), SCIPreleaseRow(), SCIProwprepGetNVars(), SCIProwprepIsLocal(), and sol.
Referenced by SCIP_DECL_NLHDLRSOLLINEARIZE().
|
static |
checks if an expression is quadratic and collects all occurring expressions
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 assert(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetExponentExprPow(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapInsertInt(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprVar(), SCIPvarIsBinary(), and TRUE.
Referenced by detectSocQuadraticComplex().
|
static |
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 assert(), i, MAX, MIN, NULL, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetExponentExprPow(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprVar(), and SCIPvarIsBinary().
Referenced by detectSocQuadraticComplex().
|
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.
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 assert(), FALSE, i, SCIP_Interval::inf, nterms, NULL, nvars, SCIP_Bool, 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().
|
static |
detects if expr ≤ auxvar is of the form sqrt(sum_i coef_i (expr_i + shift_i)^2 + const) ≤ auxvar
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 assert(), createNlhdlrExprData(), FALSE, i, nterms, NULL, nvars, 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, TRUE, and vars.
Referenced by detectSOC().
|
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
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 assert(), createNlhdlrExprData(), FALSE, i, SCIP_Interval::inf, nterms, NULL, nvars, 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, TRUE, and vars.
Referenced by detectSOC().
|
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.
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 assert(), buildQuadExprMatrix(), checkAndCollectQuadratic(), createNlhdlrExprData(), FALSE, i, SCIP_Interval::inf, nterms, NULL, nvars, 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().
|
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)
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)
Note that step 3 is only performed if parameter compeigenvalues is set to TRUE.
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 assert(), detectSocNorm(), detectSocQuadraticComplex(), detectSocQuadraticSimple(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, and SCIP_Real.
Referenced by SCIP_DECL_NLHDLRDETECT(), and SCIPisSOCNonlinear().
|
static |
nonlinear handler copy callback
Definition at line 2374 of file nlhdlr_soc.c.
References assert(), NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrSoc(), and SCIPnlhdlrGetName().
|
static |
callback to free data of handler
Definition at line 2387 of file nlhdlr_soc.c.
References assert(), NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
|
static |
callback to free expression specific data
Definition at line 2398 of file nlhdlr_soc.c.
References assert(), freeNlhdlrExprData(), NULL, SCIP_CALL, and SCIP_OKAY.
|
static |
callback to detect structure in expression tree
Definition at line 2409 of file nlhdlr_soc.c.
References assert(), 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().
|
static |
auxiliary evaluation callback of nonlinear handler
Definition at line 2456 of file nlhdlr_soc.c.
References assert(), evalSingleTerm(), FALSE, i, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExponentExprPow(), SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), sol, SQR, and updateVarVals().
|
static |
separation deinitialization method of a nonlinear handler (called during CONSINITLP)
Definition at line 2550 of file nlhdlr_soc.c.
References assert(), BMSclearMemoryArray, c, createDisaggrRow(), createDisaggrVars(), evalSingleTerm(), FALSE, generateCutSolDisagg(), generateCutSolSOC(), i, 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.
|
static |
separation deinitialization method of a nonlinear handler (called during CONSEXITSOL)
Definition at line 2952 of file nlhdlr_soc.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPreleaseRow().
|
static |
nonlinear handler separation callback
Definition at line 2970 of file nlhdlr_soc.c.
References addCut(), assert(), evalSingleTerm(), generateCutSolDisagg(), generateCutSolSOC(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPdebugMsg, SCIPfreeRowprep(), SCIPgetLPFeastol(), SCIPgetRowSolFeasibility(), SCIPnlhdlrGetData(), SCIProwIsInLP(), sol, TRUE, and updateVarVals().
|
static |
Definition at line 3058 of file nlhdlr_soc.c.
References addCutPool(), assert(), evalSingleTerm(), generateCutSolDisagg(), generateCutSolSOC(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeRowprep(), SCIPinfinity(), SCIPnlhdlrGetData(), sol, TRUE, and updateVarVals().