Detailed Description
nonlinear handler to handle quadratic expressions
Some definitions:
- a
BILINEXPRTERM
is a product of two expressions - a
QUADEXPRTERM
stores an expressionexpr
that is known to appear in a nonlinear, quadratic term, that isexpr^2
orexpr*other_expr
. It stores itssqrcoef
(that can be 0), its linear coef and all the bilinear expression terms in which expr appears.
Definition in file nlhdlr_quadratic.c.
#include <string.h>
#include "scip/cons_nonlinear.h"
#include "scip/pub_nlhdlr.h"
#include "scip/nlhdlr_quadratic.h"
#include "scip/expr_pow.h"
#include "scip/expr_sum.h"
#include "scip/expr_var.h"
#include "scip/expr_product.h"
#include "scip/pub_misc_rowprep.h"
Go to the source code of this file.
Data Structures | |
struct | Rays |
Macros | |
#define | INTERLOG(x) |
#define | NLHDLR_NAME "quadratic" |
#define | NLHDLR_DESC "handler for quadratic expressions" |
#define | NLHDLR_DETECTPRIORITY 1 |
#define | NLHDLR_ENFOPRIORITY 100 |
#define | TABLE_NAME_QUADRATIC "nlhdlr_quadratic" |
#define | TABLE_DESC_QUADRATIC "quadratic nlhdlr statistics table" |
#define | TABLE_POSITION_QUADRATIC 14700 |
#define | TABLE_EARLIEST_STAGE_QUADRATIC SCIP_STAGE_TRANSFORMED |
#define | INTERCUTS_MINVIOL 1e-4 |
#define | DEFAULT_USEINTERCUTS FALSE |
#define | DEFAULT_USESTRENGTH FALSE |
#define | DEFAULT_USEBOUNDS FALSE |
#define | BINSEARCH_MAXITERS 120 |
#define | DEFAULT_NCUTSROOT 20 |
#define | DEFAULT_NCUTS 2 |
Typedefs | |
typedef struct Rays | RAYS |
Functions | |
static | SCIP_DECL_TABLEOUTPUT (tableOutputQuadratic) |
static SCIP_RETCODE | addColToCut (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real cutcoef, SCIP_COL *col) |
static SCIP_RETCODE | addRowToCut (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real cutcoef, SCIP_ROW *row, SCIP_Bool *success) |
static SCIP_RETCODE | constructBasicVars2TableauRowMap (SCIP *scip, int *map) |
static int | countBasicVars (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_Bool *nozerostat) |
static SCIP_RETCODE | storeDenseTableauRow (SCIP *scip, SCIP_COL *col, int *basicvarpos2tableaurow, int nbasiccol, int raylength, SCIP_Real *binvrow, SCIP_Real *binvarow, SCIP_Real *tableaurows) |
static SCIP_RETCODE | storeDenseTableauRowsByColumns (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, int raylength, SCIP_VAR *auxvar, SCIP_Real *tableaurows, int *rayentry2conspos) |
static SCIP_RETCODE | createRays (SCIP *scip, RAYS **rays) |
static SCIP_RETCODE | createBoundRays (SCIP *scip, RAYS **rays, int size) |
static void | freeRays (SCIP *scip, RAYS **rays) |
static SCIP_RETCODE | insertRayEntry (SCIP *scip, RAYS *rays, SCIP_Real coef, int coefidx, int coefpos) |
static void | constructLPPos2ConsPosMap (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, int *map) |
static SCIP_RETCODE | insertRayEntries (SCIP *scip, RAYS *rays, SCIP_Real *densetableaucols, int *rayentry2conspos, int raylength, int nray, int conspos, SCIP_Real factor, int *nnonz, SCIP_Bool *success) |
static SCIP_RETCODE | createAndStoreSparseRays (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, RAYS **raysptr, SCIP_Bool *success) |
static SCIP_RETCODE | intercutsComputeCommonQuantities (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_Real sidefactor, SCIP_SOL *sol, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real *wzlp, SCIP_Real *kappa) |
static SCIP_Real | computeEigenvecDotRay (SCIP_Real *eigenvec, int nquadvars, SCIP_Real *raycoefs, int *rayidx, int raynnonz) |
static SCIP_Real | computeWRayLinear (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Real *raycoefs, int *rayidx, int raynnonz) |
static SCIP_RETCODE | computeRestrictionToRay (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *raycoefs, int *rayidx, int raynnonz, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Real *coefscondition, SCIP_Bool *success) |
static SCIP_Real | evalPhiAtRay (SCIP_Real t, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e) |
static SCIP_Real | isCase4a (SCIP_Real tsol, SCIP_Real *coefs4a, SCIP_Real *coefscondition) |
static void | doBinarySearch (SCIP *scip, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Real *sol) |
static SCIP_Real | computeRoot (SCIP *scip, SCIP_Real *coefs) |
static SCIP_Real | computeIntersectionPoint (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_Bool iscase4, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Real *coefscondition) |
static SCIP_Bool | areCoefsNumericsGood (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Bool iscase4) |
static SCIP_RETCODE | computeIntercut (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP *rowprep, SCIP_Real *interpoints, SCIP_SOL *sol, SCIP_Bool *success) |
static void | combineRays (SCIP_Real *raycoefs1, int *rayidx1, int raynnonz1, SCIP_Real *raycoefs2, int *rayidx2, int raynnonz2, SCIP_Real *newraycoefs, int *newrayidx, int *newraynnonz, SCIP_Real coef1, SCIP_Real coef2) |
static SCIP_Bool | raysAreDependent (SCIP *scip, SCIP_Real *raycoefs1, int *rayidx1, int raynnonz1, SCIP_Real *raycoefs2, int *rayidx2, int raynnonz2, SCIP_Real *coef) |
static SCIP_RETCODE | rayInRecessionCone (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, int j, int i, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real alpha, SCIP_Bool *inreccone, SCIP_Bool *success) |
static SCIP_RETCODE | findRho (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, int idx, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real *interpoints, SCIP_Real *rho, SCIP_Bool *success) |
static SCIP_RETCODE | computeStrengthenedIntercut (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *strengthsuccess) |
static SCIP_RETCODE | setVarToNearestBound (SCIP *scip, SCIP_SOL *sol, SCIP_SOL *vertex, SCIP_VAR *var, SCIP_Real *factor, SCIP_Bool *success) |
static SCIP_RETCODE | findVertexAndGetRays (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_SOL *vertex, SCIP_VAR *auxvar, RAYS **raysptr, SCIP_Bool *success) |
static SCIP_Bool | isQuadConsViolated (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_SOL *sol, SCIP_Real sidefactor) |
static SCIP_RETCODE | generateIntercut (SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool overestimate, SCIP_Bool *success) |
static SCIP_Bool | isPropagable (SCIP_EXPR *qexpr) |
static SCIP_Bool | isPropagableTerm (SCIP_EXPR *qexpr, int idx) |
static SCIP_RETCODE | propagateBoundsQuadExpr (SCIP *scip, SCIP_EXPR *expr, SCIP_Real sqrcoef, SCIP_INTERVAL b, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions) |
static SCIP_RETCODE | propagateBoundsLinExpr (SCIP *scip, SCIP_EXPR *expr, SCIP_Real b, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions) |
static SCIP_Real | computeMaxBoundaryForBilinearProp (SCIP_Real a, SCIP_Real c, SCIP_Real x1, SCIP_Real x2) |
static SCIP_Real | computeMaxForBilinearProp (SCIP_Real a, SCIP_Real c, SCIP_INTERVAL dom) |
static void | computeRangeForBilinearProp (SCIP_INTERVAL exprdom, SCIP_Real coef, SCIP_INTERVAL rhs, SCIP_INTERVAL *range) |
static SCIP_RETCODE | reversePropagateLinearExpr (SCIP *scip, SCIP_EXPR **linexprs, int nlinexprs, SCIP_Real *lincoefs, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions) |
static | SCIP_DECL_NLHDLRFREEEXPRDATA (nlhdlrFreeexprdataQuadratic) |
static | SCIP_DECL_NLHDLRDETECT (nlhdlrDetectQuadratic) |
static | SCIP_DECL_NLHDLREVALAUX (nlhdlrEvalauxQuadratic) |
static | SCIP_DECL_NLHDLRENFO (nlhdlrEnfoQuadratic) |
static | SCIP_DECL_NLHDLRINTEVAL (nlhdlrIntevalQuadratic) |
static | SCIP_DECL_NLHDLRREVERSEPROP (nlhdlrReversepropQuadratic) |
static | SCIP_DECL_NLHDLRFREEHDLRDATA (nlhdlrFreehdlrdataQuadratic) |
static | SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrQuadratic) |
SCIP_RETCODE | SCIPincludeNlhdlrQuadratic (SCIP *scip) |
Macro Definition Documentation
◆ INTERLOG
#define INTERLOG | ( | x | ) |
Definition at line 51 of file nlhdlr_quadratic.c.
Referenced by areCoefsNumericsGood(), computeIntercut(), computeRestrictionToRay(), computeStrengthenedIntercut(), generateIntercut(), and SCIP_DECL_NLHDLRENFO().
◆ NLHDLR_NAME
#define NLHDLR_NAME "quadratic" |
Definition at line 66 of file nlhdlr_quadratic.c.
Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_TABLEOUTPUT(), and SCIPincludeNlhdlrQuadratic().
◆ NLHDLR_DESC
#define NLHDLR_DESC "handler for quadratic expressions" |
Definition at line 67 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ NLHDLR_DETECTPRIORITY
#define NLHDLR_DETECTPRIORITY 1 |
Definition at line 68 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ NLHDLR_ENFOPRIORITY
#define NLHDLR_ENFOPRIORITY 100 |
Definition at line 69 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ TABLE_NAME_QUADRATIC
#define TABLE_NAME_QUADRATIC "nlhdlr_quadratic" |
Definition at line 72 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ TABLE_DESC_QUADRATIC
#define TABLE_DESC_QUADRATIC "quadratic nlhdlr statistics table" |
Definition at line 73 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ TABLE_POSITION_QUADRATIC
#define TABLE_POSITION_QUADRATIC 14700 |
the position of the statistics table
Definition at line 74 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ TABLE_EARLIEST_STAGE_QUADRATIC
#define TABLE_EARLIEST_STAGE_QUADRATIC SCIP_STAGE_TRANSFORMED |
output of the statistics table is only printed from this stage onwards
Definition at line 75 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ INTERCUTS_MINVIOL
#define INTERCUTS_MINVIOL 1e-4 |
Definition at line 78 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ DEFAULT_USEINTERCUTS
#define DEFAULT_USEINTERCUTS FALSE |
Definition at line 79 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ DEFAULT_USESTRENGTH
#define DEFAULT_USESTRENGTH FALSE |
Definition at line 80 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ DEFAULT_USEBOUNDS
#define DEFAULT_USEBOUNDS FALSE |
Definition at line 81 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ BINSEARCH_MAXITERS
#define BINSEARCH_MAXITERS 120 |
Definition at line 82 of file nlhdlr_quadratic.c.
Referenced by doBinarySearch(), and findRho().
◆ DEFAULT_NCUTSROOT
#define DEFAULT_NCUTSROOT 20 |
Definition at line 83 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
◆ DEFAULT_NCUTS
#define DEFAULT_NCUTS 2 |
Definition at line 84 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
Typedef Documentation
◆ RAYS
Definition at line 165 of file nlhdlr_quadratic.c.
Function Documentation
◆ SCIP_DECL_TABLEOUTPUT()
|
static |
output method of statistics table to output file stream 'file'
Definition at line 174 of file nlhdlr_quadratic.c.
References NLHDLR_NAME, NULL, SCIP_OKAY, SCIPfindConshdlr(), SCIPfindNlhdlrNonlinear(), SCIPinfoMessage(), and SCIPnlhdlrGetData().
◆ addColToCut()
|
static |
adds cutcoef * (col - col*) to rowprep
- Parameters
-
scip SCIP data structure rowprep rowprep to store intersection cut sol solution to separate cutcoef cut coefficient col column to add to rowprep
Definition at line 214 of file nlhdlr_quadratic.c.
References NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIPaddRowprepTerm(), SCIPcolGetBasisStatus(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPgetSolVal(), SCIPinfoMessage(), SCIProwprepAddConstant(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().
Referenced by computeIntercut(), and computeStrengthenedIntercut().
◆ addRowToCut()
|
static |
adds cutcoef * (slack - slack*) to rowprep
row is lhs ≤ <coefs, vars> + constant ≤ rhs, thus slack is defined by slack + <coefs.vars> + constant = side
If row (slack) is at upper, it means that <coefs,vars*> + constant = rhs, and so slack* = side - rhs –> slack - slack* = rhs - <coefs, vars> - constant.
If row (slack) is at lower, then <coefs,vars*> + constant = lhs, and so slack* = side - lhs –> slack - slack* = lhs - <coefs, vars> - constant.
- Parameters
-
scip SCIP data structure rowprep rowprep to store intersection cut cutcoef cut coefficient row row, whose slack we are ading to rowprep success if the row is nonbasic enough
Definition at line 249 of file nlhdlr_quadratic.c.
References FALSE, NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPcolGetVar(), SCIPgetRowActivity(), SCIPinfoMessage(), SCIPisFeasEQ(), SCIPisInfinity(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), and SCIProwprepAddConstant().
Referenced by computeIntercut(), and computeStrengthenedIntercut().
◆ constructBasicVars2TableauRowMap()
|
static |
constructs map between lp position of a basic variable and its row in the tableau
- Parameters
-
scip SCIP data structure map buffer to store the map
Definition at line 310 of file nlhdlr_quadratic.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetLPBasisInd(), and SCIPgetNLPRows().
Referenced by storeDenseTableauRowsByColumns().
◆ countBasicVars()
|
static |
counts the number of basic variables in the quadratic expr
- Parameters
-
nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) nozerostat whether there is no variable with basis status zero
Definition at line 336 of file nlhdlr_quadratic.c.
References FALSE, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_ZERO, SCIPcolGetBasisStatus(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPvarGetCol(), and TRUE.
Referenced by createAndStoreSparseRays().
◆ storeDenseTableauRow()
|
static |
stores the row of the tableau where col
is basic
In general, we will have
basicvar1 = tableaurow var1 basicvar2 = tableaurow var2 ... basicvarn = tableaurow varn
However, we want to store the the tableau row by columns. Thus, we need to know which of the basic vars col
is.
Note we only store the entries of the nonbasic variables
- Parameters
-
scip SCIP data structure col basic columns to store its tableau row basicvarpos2tableaurow map between basic var and its tableau row nbasiccol which basic var this is raylength the length of a ray (the total number of basic vars) binvrow buffer to store row of Binv binvarow buffer to store row of Binv A tableaurows pointer to store the tableau rows
Definition at line 415 of file nlhdlr_quadratic.c.
References NULL, SCIP_BASESTAT_BASIC, SCIP_CALL, SCIP_OKAY, SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), and SCIProwGetBasisStatus().
Referenced by storeDenseTableauRowsByColumns().
◆ storeDenseTableauRowsByColumns()
|
static |
stores the rows of the tableau corresponding to the basic variables in the quadratic expression
Also return a map storing to which var the entry of a ray corresponds, i.e., if the tableau is
basicvar_1 = ray1_1 nonbasicvar_1 + ... basicvar_2 = ray1_2 nonbasicvar_1 + ... ... basicvar_n = ray1_n nonbasicvar_1 + ...
The map maps k to the position of basicvar_k in the variables of the constraint assuming the variables are sorted as [quadratic vars, linear vars, auxvar].
- Parameters
-
scip SCIP data structure nlhdlrexprdata nlhdlr expression data raylength length of a ray of the tableau auxvar aux var of expr or NULL if not needed (e.g. separating real cons) tableaurows buffer to store the tableau rows rayentry2conspos buffer to store the map
Definition at line 482 of file nlhdlr_quadratic.c.
References constructBasicVars2TableauRowMap(), NULL, SCIP_BASESTAT_BASIC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetExprAuxVarNonlinear(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPinfoMessage(), SCIPvarGetCol(), and storeDenseTableauRow().
Referenced by createAndStoreSparseRays().
◆ createRays()
|
static |
initializes rays data structure
- Parameters
-
scip SCIP data structure rays rays data structure
Definition at line 582 of file nlhdlr_quadratic.c.
References BMSclearMemory, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPgetNLPCols(), and SCIPgetNLPRows().
Referenced by createAndStoreSparseRays().
◆ createBoundRays()
|
static |
initializes rays data structure for bound rays
- Parameters
-
scip SCIP data structure rays rays data structure size number of rays to allocate
Definition at line 605 of file nlhdlr_quadratic.c.
References BMSclearMemory, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by findVertexAndGetRays().
◆ freeRays()
frees rays data structure
- Parameters
-
scip SCIP data structure rays rays data structure
Definition at line 629 of file nlhdlr_quadratic.c.
References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by createAndStoreSparseRays(), and generateIntercut().
◆ insertRayEntry()
|
static |
inserts entry to rays data structure; checks and resizes if more space is needed
- Parameters
-
scip SCIP data structure rays rays data structure coef coefficient to insert coefidx index of coefficient (conspos of var it corresponds to) coefpos where to insert coefficient
Definition at line 647 of file nlhdlr_quadratic.c.
References Rays::rays, Rays::raysidx, Rays::rayssize, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.
Referenced by insertRayEntries().
◆ constructLPPos2ConsPosMap()
|
static |
constructs map between the lppos of a variables and its position in the constraint assuming the constraint variables are sorted as [quad vars, lin vars, aux var (if it exists)]
If a variable doesn't appear in the constraint, then its position is -1.
- Parameters
-
nlhdlrexprdata nlhdlr expression data auxvar aux var of the expr map buffer to store the mapping
Definition at line 679 of file nlhdlr_quadratic.c.
References NULL, SCIPcolGetLPPos(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), and SCIPvarGetCol().
Referenced by createAndStoreSparseRays().
◆ insertRayEntries()
|
static |
inserts entries of factor * nray-th column of densetableaucols into rays data structure
- Parameters
-
scip SCIP data structure rays rays data structure densetableaucols column of the tableau in dense format rayentry2conspos map between rayentry and conspos of associated var raylength length of a tableau column nray which tableau column to insert conspos conspos of ray's nonbasic var in the cons; -1 if not in the cons factor factor to multiply each tableau col nnonz position to start adding the ray in rays and buffer to store nnonz success we can't separate if there is a nonzero ray with basis status ZERO
Definition at line 722 of file nlhdlr_quadratic.c.
References FALSE, insertRayEntry(), Rays::nrays, NULL, Rays::rays, Rays::raysbegin, Rays::raysidx, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfoMessage(), SCIPisZero(), and TRUE.
Referenced by createAndStoreSparseRays().
◆ createAndStoreSparseRays()
|
static |
stores rays in sparse form
The first rays correspond to the nonbasic variables and the last rays to the nonbasic slack variables.
More details: The LP tableau is of the form
basicvar_1 = ray1_1 nonbasicvar_1 + ... + raym_1 nonbasicvar_m basicvar_2 = ray1_2 nonbasicvar_1 + ... + raym_2 nonbasicvar_m ... basicvar_n = ray1_n nonbasicvar_1 + ... + raym_n nonbasicvar_m nonbasicvar_1 = 1.0 nonbasicvar_1 + ... + 0.0 nonbasicvar_m ... nonbasicvar_m = 0.0 nonbasicvar_1 + ... + 1.0 nonbasicvar_m
so rayk = (rayk_1, ... rayk_n, e_k) We store the entries of the rays associated to the variables present in the quadratic expr. We do not store zero rays.
Also, we store the rays as if every nonbasic variable was at lower (so that all rays moves to infinity) Since the tableau is:
basicvar + Binv L (nonbasic_lower - lb) + Binv U (nonbasic_upper - ub) = basicvar_sol
then:
basicvar = basicvar_sol - Binv L (nonbasic_lower - lb) + Binv U (ub - nonbasic_upper)
and so the entries of the rays associated with the basic variables are: rays_basicvars = [-BinvL, BinvU].
So we flip the sign of the rays associated to nonbasic vars at lower. In constrast, the nonbasic part of the ray has a 1.0 for nonbasic at lower and a -1.0 for nonbasic at upper, i.e. nonbasic_lower = lb + 1.0(nonbasic_lower - lb) and nonbasic_upper = ub - 1.0(ub - nonbasic_upper)
- Parameters
-
scip SCIP data structure nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) raysptr buffer to store rays datastructure success we can't separate if there is a var with basis status ZERO
Definition at line 846 of file nlhdlr_quadratic.c.
References constructLPPos2ConsPosMap(), countBasicVars(), createRays(), freeRays(), insertRayEntries(), Rays::lpposray, Rays::nrays, NULL, Rays::rays, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPinfoMessage(), SCIProwGetBasisStatus(), SCIProwGetLPPos(), SCIPvarGetName(), storeDenseTableauRowsByColumns(), and TRUE.
Referenced by generateIntercut().
◆ intercutsComputeCommonQuantities()
|
static |
compute quantities for intersection cuts
Assume the quadratic is stored as
\[ q(z) = z_q^T Q z_q + b_q^T z_q + b_l z_l + c - z_a \]
where:
- \(z_q\) are the quadratic vars
- \(z_l\) are the linear vars
- \(z_a\) is the aux var if it exists
We can rewrite it as
\[ \Vert x(z)\Vert^2 - \Vert y\Vert^2 + w(z) + \kappa \leq 0. \]
To do this transformation and later to compute the actual cut we need to compute and store some quantities. Let
- \(I_0\), \(I_+\), and \(I_-\) be the index set of zero, positive, and negative eigenvalues, respectively
- \(v_i\) be the i-th eigenvector of \(Q\)
- \(zlp\) be the lp value of the variables \(z\)
The quantities we need are:
- \(vb_i = v_i^T b\) for \(i \in I_+ \cup I_-\)
- \(vzlp_i = v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
- \(\kappa = c - 1/4 \sum_{i \in I_+ \cup I_-} (v_i^T b_q)^2 / eigval_i\)
- \(w(z) = (\sum_{i \in I_0} v_i^T b_q v_i^T) z_q + b_l^T z_l - z_a\)
- \(w(zlp)\)
- Returns
- \(\kappa\) and the vector \(\sum_{i \in I_0} v_i^T b_q v_i^T\)
- Note
- if the constraint is q(z) ≤ rhs, then the constant when writing the constraint as quad ≤ 0 is c - rhs.
-
if the quadratic constraint we are separating is q(z) ≥ lhs, then we multiply by -1. In practice, what changes is
- the sign of the eigenvalues
- the sign of \(b_q\) and \(b_l\)
- the sign of the coefficient of the auxvar (if it exists)
- the constant of the quadratic written as quad ≤ 0 is lhs - c
- The eigenvectors do not change sign!
- Parameters
-
scip SCIP data structure nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise sol solution to separate vb buffer to store \(v_i^T b\) for \(i \in I_+ \cup I_-\) vzlp buffer to store \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\) wcoefs buffer to store the coefs of quad vars of w wzlp pointer to store the value of w at zlp kappa pointer to store the value of kappa
Definition at line 1045 of file nlhdlr_quadratic.c.
References BMSclearMemoryArray, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPgetSolVal(), SCIPinfoMessage(), and SCIPisZero().
Referenced by generateIntercut().
◆ computeEigenvecDotRay()
|
static |
computes eigenvec^T ray
- Parameters
-
eigenvec eigenvector nquadvars number of quadratic vars (length of eigenvec) raycoefs coefficients of ray rayidx index of consvar the ray coef is associated to raynnonz length of raycoefs and rayidx
Definition at line 1160 of file nlhdlr_quadratic.c.
References SCIP_Real.
Referenced by computeRestrictionToRay().
◆ computeWRayLinear()
|
static |
computes linear part of evaluation of w(ray): \(b_l^T ray_l - ray_a\)
- Note
- we can know whether the auxiliary variable appears by the entries of the ray
- Parameters
-
nlhdlrexprdata nlhdlr expression data sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise raycoefs coefficients of ray rayidx ray coef[i] affects var at pos rayidx[i] in consvar raynnonz length of raycoefs and rayidx
Definition at line 1189 of file nlhdlr_quadratic.c.
References NULL, SCIP_Real, and SCIPexprGetQuadraticData().
Referenced by computeRestrictionToRay().
◆ computeRestrictionToRay()
|
static |
calculate coefficients of restriction of the function to given ray.
The restriction of the function representing the maximal S-free set to zlp + t * ray has the form SQRT(A t^2 + B t + C) - (D t + E) for cases 1, 2, and 3. For case 4 it is a piecewise defined function and each piece is of the aforementioned form.
This function computes the coefficients A, B, C, D, E for the given ray. In case 4, it computes the coefficients for both pieces, in addition to coefficients needed to evaluate the condition in the piecewise definition of the function.
The parameter iscase4 tells the function if it is case 4 or not.
- Parameters
-
scip SCIP data structure nlhdlrexprdata nlhdlr expression data sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 raycoefs coefficients of ray rayidx index of consvar the ray coef is associated to raynnonz length of raycoefs and rayidx vb array containing \(v_i^T b\) for \(i \in I_+ \cup I_-\) vzlp array containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\) wcoefs coefficients of w for the qud vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa coefs1234a buffer to store A, B, C, D, and E of cases 1, 2, 3, or 4a coefs4b buffer to store A, B, C, D, and E of case 4b (or NULL if not needed) coefscondition buffer to store data to evaluate condition to decide case 4a or 4b success did we successfully compute the coefficients?
Definition at line 1255 of file nlhdlr_quadratic.c.
References a, b, computeEigenvecDotRay(), computeWRayLinear(), FALSE, INTERLOG, MAX, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPinfoMessage(), SCIPisZero(), and TRUE.
Referenced by computeIntercut(), and rayInRecessionCone().
◆ evalPhiAtRay()
|
static |
returns phi(zlp + t * ray) = SQRT(A t^2 + B t + C) - (D t + E)
- Parameters
-
t argument of phi restricted to ray a value of A b value of B c value of C d value of D e value of E
Definition at line 1492 of file nlhdlr_quadratic.c.
References QUAD, QUAD_ASSIGN, QUAD_SCALE, QUAD_TO_DBL, SCIP_Real, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSqrtQ, SCIPquadprecSquareD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.
Referenced by computeIntersectionPoint(), computeRoot(), and doBinarySearch().
◆ isCase4a()
|
static |
checks whether case 4a applies
The condition for being in case 4a is
\[ -\lambda_{r+1} \Vert \hat y(zlp + tsol\, ray)\Vert + \hat y_{s+1}(zlp + tsol\, ray) \leq 0\]
This reduces to
\[ -num(\hat x_{r+1}(zlp)) \sqrt{A t^2 + B t + C} / E + w(ray) \cdot t + num(\hat y_{s+1}(zlp)) \leq 0\]
where num is the numerator.
- Parameters
-
tsol t in the above formula coefs4a coefficients A, B, C, D, and E of case 4a coefscondition extra coefficients needed for the evaluation of the condition: \(num(\hat x_{r+1}(zlp)) / E\); \(w(ray)\); \(num(\hat y_{s+1}(zlp))\)
Definition at line 1556 of file nlhdlr_quadratic.c.
Referenced by computeIntersectionPoint().
◆ doBinarySearch()
|
static |
helper function of computeRoot: we want phi to be ≤ 0
- Parameters
-
scip SCIP data structure a value of A b value of B c value of C d value of D e value of E sol buffer to store solution; also gives initial point
Definition at line 1569 of file nlhdlr_quadratic.c.
References BINSEARCH_MAXITERS, evalPhiAtRay(), SCIP_Real, SCIPisFeasEQ(), and SCIPisFeasZero().
Referenced by computeRoot().
◆ computeRoot()
finds smallest positive root phi by finding the smallest positive root of (A - D^2) t^2 + (B - 2 D*E) t + (C - E^2) = 0
However, we are conservative and want a solution such that phi is negative, but close to 0. Thus, we correct the result with a binary search.
- Parameters
-
scip SCIP data structure coefs value of A
Definition at line 1614 of file nlhdlr_quadratic.c.
References a, b, doBinarySearch(), evalPhiAtRay(), SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), and SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar().
Referenced by computeIntersectionPoint().
◆ computeIntersectionPoint()
|
static |
The maximal S-free set is \(\gamma(z) \leq 0\); we find the intersection point of the ray ray
starting from zlp with the boundary of the S-free set. That is, we find \(t \geq 0\) such that \(\gamma(zlp + t \cdot \text{ray}) = 0\).
In cases 1,2, and 3, gamma is of the form
\[ \gamma(zlp + t \cdot \text{ray}) = \sqrt{A t^2 + B t + C} - (D t + E) \]
In the case 4 gamma is of the form
\[ \gamma(zlp + t \cdot \text{ray}) = \begin{cases} \sqrt{A t^2 + B t + C} - (D t + E), & \text{if some condition holds}, \\ \sqrt{A' t^2 + B' t + C'} - (D' t + E'), & \text{otherwise.} \end{cases} \]
It can be shown (given the special properties of \(\gamma\)) that the smallest positive root of each function of the form \(\sqrt{a t^2 + b t + c} - (d t + e)\) is the same as the smallest positive root of the quadratic equation:
\begin{align} & \sqrt{a t^2 + b t + c} - (d t + e)) (\sqrt{a t^2 + b t + c} + (d t + e)) = 0 \\ \Leftrightarrow & (a - d^2) t^2 + (b - 2 d\,e) t + (c - e^2) = 0 \end{align}
So, in cases 1, 2, and 3, this function just returns the solution of the above equation. In case 4, it first solves the equation assuming we are in the first piece. If there is no solution, then the second piece can't have a solution (first piece ≥ second piece for all t) Then we check if the solution satisfies the condition. If it doesn't then we solve the equation for the second piece. If it has a solution, then it has to be the solution.
- Parameters
-
scip SCIP data structure nlhdlrdata nlhdlr data iscase4 whether we are in case 4 or not coefs1234a values of A, B, C, D, and E of cases 1, 2, 3, or 4a coefs4b values of A, B, C, D, and E of case 4b coefscondition values needed to evaluate condition of case 4
Definition at line 1714 of file nlhdlr_quadratic.c.
References computeRoot(), evalPhiAtRay(), isCase4a(), MAX, NULL, SCIP_Real, SCIPinfoMessage(), and SCIPisInfinity().
Referenced by computeIntercut(), and rayInRecessionCone().
◆ areCoefsNumericsGood()
|
static |
checks if numerics of the coefficients are not too bad
- Parameters
-
scip SCIP data structure nlhdlrdata nlhdlr data coefs1234a coefficients for case 1-3 and 4a coefs4b coefficients for case 4b iscase4 whether we are in case 4
Definition at line 1781 of file nlhdlr_quadratic.c.
References FALSE, INTERLOG, REALABS, SCIP_Real, SCIPinfinity(), SCIPisHugeValue(), and TRUE.
Referenced by computeIntercut().
◆ computeIntercut()
|
static |
computes intersection cut cuts off sol (because solution sol violates the quadratic constraint cons) and stores it in rowprep. Here, we don't use any strengthening.
- Parameters
-
scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing \(v_i^T b\) for \(i \in I_+ \cup I_-\) vzlp array containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\) wcoefs coefficients of w for the qud vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa rowprep rowprep for the generated cut interpoints array to store intersection points for all rays or NULL if nothing needs to be stored sol solution we want to separate success if a cut candidate could be computed
Definition at line 1857 of file nlhdlr_quadratic.c.
References addColToCut(), addRowToCut(), areCoefsNumericsGood(), computeIntersectionPoint(), computeRestrictionToRay(), INTERLOG, Rays::lpposray, Rays::nrays, NULL, Rays::rays, Rays::raysbegin, Rays::raysidx, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetBasisStatus(), SCIPgetLPCols(), SCIPgetLPRows(), SCIPinfoMessage(), SCIPisInfinity(), and SCIProwGetBasisStatus().
Referenced by computeStrengthenedIntercut(), and generateIntercut().
◆ combineRays()
|
static |
combine ray 1 and 2 to obtain new ray coef1 * ray1 - coef2 * ray2 in sparse format
- Parameters
-
raycoefs1 coefficients of ray 1 rayidx1 index of consvar of the ray 1 coef is associated to raynnonz1 length of raycoefs1 and rayidx1 raycoefs2 coefficients of ray 2 rayidx2 index of consvar of the ray 2 coef is associated to raynnonz2 length of raycoefs2 and rayidx2 newraycoefs coefficients of combined ray newrayidx index of consvar of the combined ray coef is associated to newraynnonz pointer to length of newraycoefs and newrayidx coef1 coef of ray 1 coef2 coef of ray 2
Definition at line 1961 of file nlhdlr_quadratic.c.
Referenced by rayInRecessionCone().
◆ raysAreDependent()
|
static |
checks if two rays are linearly dependent
- Parameters
-
scip SCIP data structure raycoefs1 coefficients of ray 1 rayidx1 index of consvar of the ray 1 coef is associated to raynnonz1 length of raycoefs1 and rayidx1 raycoefs2 coefficients of ray 2 rayidx2 index of consvar of the ray 2 coef is associated to raynnonz2 length of raycoefs2 and rayidx2 coef pointer to store coef (s.t. r1 = coef * r2) in case rays are dependent
Definition at line 2018 of file nlhdlr_quadratic.c.
References FALSE, SCIPisEQ(), SCIPisZero(), and TRUE.
Referenced by findRho().
◆ rayInRecessionCone()
|
static |
checks if the ray alpha * ray_i + (1 - alpha) * ray_j is in the recession cone of the S-free set. To do so, we check if phi restricted to the ray has a positive root.
- Parameters
-
scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays j index of current ray in recession cone i index of current ray not in recession cone sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing \(v_i^T b\) for \(i \in I_+ \cup I_-\) vzlp array containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\) wcoefs coefficients of w for the quad vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa alpha coef for combining the two rays inreccone pointer to store whether the ray is in the recession cone or not success Did numerical troubles occur?
Definition at line 2067 of file nlhdlr_quadratic.c.
References combineRays(), computeIntersectionPoint(), computeRestrictionToRay(), FALSE, Rays::rays, Rays::raysbegin, Rays::raysidx, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and TRUE.
Referenced by findRho().
◆ findRho()
|
static |
finds the smallest negative steplength for the current ray r_idx such that the combination of r_idx with all rays not in the recession cone is in the recession cone
- Parameters
-
scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays idx index of current ray we want to find rho for sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing \(v_i^T b\) for \(i \in I_+ \cup I_-\) vzlp array containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\) wcoefs coefficients of w for the quad vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa interpoints array to store intersection points for all rays or NULL if nothing needs to be stored rho pointer to store the optimal rho success could we successfully find the right rho?
Definition at line 2136 of file nlhdlr_quadratic.c.
References BINSEARCH_MAXITERS, FALSE, Rays::nrays, rayInRecessionCone(), Rays::rays, raysAreDependent(), Rays::raysbegin, Rays::raysidx, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), and SCIPisZero().
Referenced by computeStrengthenedIntercut().
◆ computeStrengthenedIntercut()
|
static |
computes intersection cut using negative edge extension to strengthen rays that do not intersect (i.e., rays in the recession cone)
- Parameters
-
scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing \(v_i^T b\) for \(i \in I_+ \cup I_-\) vzlp array containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\) wcoefs coefficients of w for the qud vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa rowprep rowprep for the generated cut sol solution to separate success if a cut candidate could be computed strengthsuccess if strengthening was successfully applied
Definition at line 2255 of file nlhdlr_quadratic.c.
References addColToCut(), addRowToCut(), computeIntercut(), FALSE, findRho(), INTERLOG, Rays::lpposray, Rays::nrays, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIPisInfinity(), SCIPisZero(), SCIProwGetBasisStatus(), and TRUE.
Referenced by generateIntercut().
◆ setVarToNearestBound()
|
static |
sets variable in solution "vertex" to its nearest bound
- Parameters
-
scip SCIP data structure sol solution to separate vertex new solution to separate var var we want to find nearest bound to factor is vertex for current var at lower or upper? success TRUE if no variable is bounded
Definition at line 2371 of file nlhdlr_quadratic.c.
References bound, FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisInfinity(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by findVertexAndGetRays().
◆ findVertexAndGetRays()
|
static |
This function finds vertex (w.r.t. bounds of variables appearing in the quadratic) that is closest to the current solution we want to separate.
Furthermore, we store the rays corresponding to the unit vectors, i.e.,
- if \(x_i\) is at its lower bound in vertex –> \(r_i = e_i\)
- if \(x_i\) is at its upper bound in vertex –> \(r_i = -e_i\)
- Parameters
-
scip SCIP data structure nlhdlrexprdata nlhdlr expression data sol solution to separate vertex new 'vertex' (w.r.t. bounds) solution to separate auxvar aux var of expr or NULL if not needed (e.g. separating real cons) raysptr pointer to new bound rays success TRUE if no variable is unbounded
Definition at line 2416 of file nlhdlr_quadratic.c.
References createBoundRays(), Rays::lpposray, Rays::nrays, NULL, Rays::rays, Rays::raysbegin, Rays::raysidx, Rays::rayssize, SCIP_CALL, SCIP_OKAY, SCIPcolGetLPPos(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPvarGetCol(), setVarToNearestBound(), and TRUE.
Referenced by generateIntercut().
◆ isQuadConsViolated()
|
static |
checks if the quadratic constraint is violated by sol
- Parameters
-
scip SCIP data structure nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) sol solution to check feasibility for sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
Definition at line 2499 of file nlhdlr_quadratic.c.
References FALSE, NULL, SCIP_Real, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPgetSolVal(), and TRUE.
Referenced by generateIntercut().
◆ generateIntercut()
|
static |
generates intersection cut that cuts off sol (which violates the quadratic constraint cons)
- Parameters
-
scip SCIP data structure expr expr nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data cons violated constraint that contains expr sol solution to separate rowprep rowprep for the generated cut overestimate TRUE if viol cons is q(z) ≥ lhs; FALSE if q(z) ≤ rhs success whether separation was successfull or not
Definition at line 2583 of file nlhdlr_quadratic.c.
References computeIntercut(), computeStrengthenedIntercut(), createAndStoreSparseRays(), FALSE, findVertexAndGetRays(), freeRays(), intercutsComputeCommonQuantities(), INTERLOG, isQuadConsViolated(), NULL, Rays::rays, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIPallocBufferArray, SCIPcreateSol(), SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetExprAuxVarNonlinear(), SCIPinfoMessage(), SCIPprintExpr(), SCIProwprepAddSide(), SCIProwprepGetSide(), SCIProwprepSetSidetype(), and TRUE.
Referenced by SCIP_DECL_NLHDLRENFO().
◆ isPropagable()
returns whether a quadratic form is "propagable"
It is propagable, if a variable (aka child expr) appears at least twice, which is the case if at least two of the following hold:
- it appears as a linear term (coef*expr)
- it appears as a square term (coef*expr^2)
- it appears in a bilinear term
- it appears in another bilinear term
- Parameters
-
qexpr quadratic representation data
Definition at line 2749 of file nlhdlr_quadratic.c.
References FALSE, NULL, SCIP_Real, SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), and TRUE.
Referenced by SCIP_DECL_NLHDLRDETECT().
◆ isPropagableTerm()
returns whether a quadratic term is "propagable"
A term is propagable, if its variable (aka child expr) appears at least twice, which is the case if at least two of the following hold:
- it appears as a linear term (coef*expr)
- it appears as a square term (coef*expr^2)
- it appears in a bilinear term
- it appears in another bilinear term
- Parameters
-
qexpr quadratic representation data idx index of quadratic term to consider
Definition at line 2782 of file nlhdlr_quadratic.c.
References NULL, SCIP_Real, and SCIPexprGetQuadraticQuadTerm().
Referenced by SCIP_DECL_NLHDLRDETECT(), SCIP_DECL_NLHDLRINTEVAL(), and SCIP_DECL_NLHDLRREVERSEPROP().
◆ propagateBoundsQuadExpr()
|
static |
solves a quadratic equation \( a\, \text{expr}^2 + b\, \text{expr} \in \text{rhs} \) (with \(b\) an interval) and reduces bounds on expr
or deduces infeasibility if possible
- Parameters
-
scip SCIP data structure expr expression for which to solve sqrcoef square coefficient b interval acting as linear coefficient rhs interval acting as rhs infeasible buffer to store if propagation produced infeasibility nreductions buffer to store the number of interval reductions
Definition at line 2800 of file nlhdlr_quadratic.c.
References a, SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPgetExprBoundsNonlinear(), SCIPinfoMessage(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalSet(), SCIPintervalSolveUnivariateQuadExpression(), SCIPprintExpr(), SCIPtightenExprIntervalNonlinear(), SCIP_Interval::sup, and TRUE.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
◆ propagateBoundsLinExpr()
|
static |
solves a linear equation \( b\, \text{expr} \in \text{rhs} \) (with \(b\) a scalar) and reduces bounds on expr
or deduces infeasibility if possible
- Parameters
-
scip SCIP data structure expr expression for which to solve b linear coefficient rhs interval acting as rhs infeasible buffer to store if propagation produced infeasibility nreductions buffer to store the number of interval reductions
Definition at line 2851 of file nlhdlr_quadratic.c.
References SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPinfoMessage(), SCIPintervalDivScalar(), SCIPprintExpr(), SCIPtightenExprIntervalNonlinear(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
◆ computeMaxBoundaryForBilinearProp()
|
static |
returns max of a/x - c*x for x in {x1, x2} with x1, x2 > 0
- Parameters
-
a coefficient a c coefficient c x1 coefficient x1 > 0 x2 coefficient x2 > 0
Definition at line 2887 of file nlhdlr_quadratic.c.
References MAX, SCIP_Real, SCIPintervalGetRoundingMode(), SCIPintervalNegateReal(), SCIPintervalSetRoundingMode(), and SCIPintervalSetRoundingModeUpwards().
Referenced by computeMaxForBilinearProp().
◆ computeMaxForBilinearProp()
|
static |
returns max of a/x - c*x for x in dom; it assumes that dom is contained in (0, +inf)
- Parameters
-
a coefficient a c coefficient c dom domain of x
Definition at line 2915 of file nlhdlr_quadratic.c.
References computeMaxBoundaryForBilinearProp(), SCIP_Interval::inf, MAX, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalDivScalar(), SCIPintervalGetRoundingMode(), SCIPintervalNegateReal(), SCIPintervalSet(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSquareRoot(), SCIPnextafter(), and SCIP_Interval::sup.
Referenced by computeRangeForBilinearProp().
◆ computeRangeForBilinearProp()
|
static |
computes the range of rhs/x - coef * x for x in exprdom; this is used for the propagation of bilinear terms
If 0 is in the exprdom, we set range to \(\mathbb{R}\) (even though this is not quite correct, it is correct for the intended use of the function). TODO: maybe check before calling it whether 0 is in the domain and then just avoid calling it
If rhs is [A,B] and x > 0, then we want the min of A/x - coef*x and max of B/x - coef*x for x in [exprdom]. If rhs is [A,B] and x < 0, then we want the min of B/x - coef*x and max of A/x - coef*x for x in [exprdom]. However, this is the same as min of -B/x + coef*x and max of -A/x + coef*x for x in -[exprdom]. Thus, we can always reduce to x > 0 by multiplying [exprdom], rhs, and coef by -1.
- Parameters
-
exprdom expression for which to solve coef expression for which to solve rhs rhs used for computation range storage for the resulting range
Definition at line 2982 of file nlhdlr_quadratic.c.
References computeMaxForBilinearProp(), SCIP_Interval::inf, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalMulScalar(), SCIPintervalSetBounds(), SCIPintervalSetEntire(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
◆ reversePropagateLinearExpr()
|
static |
reverse propagates coef_i expr_i + constant in rhs
- Parameters
-
scip SCIP data structure linexprs linear expressions nlinexprs number of linear expressions lincoefs coefficients of linear expressions constant constant rhs rhs infeasible buffer to store whether an exps' bounds were propagated to an empty interval nreductions buffer to store the number of interval reductions of all exprs
Definition at line 3017 of file nlhdlr_quadratic.c.
References SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPallocBufferArray, SCIPexprGetActivity(), SCIPfreeBufferArray, SCIPintervalPropagateWeightedSum(), and SCIPtightenExprIntervalNonlinear().
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
◆ SCIP_DECL_NLHDLRFREEEXPRDATA()
|
static |
callback to free expression specific data
Definition at line 3067 of file nlhdlr_quadratic.c.
References NULL, SCIP_OKAY, SCIPexprGetQuadraticData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
◆ SCIP_DECL_NLHDLRDETECT()
|
static |
callback to detect structure in expression tree
A term is quadratic if
- it is a product expression of two expressions, or
- it is power expression of an expression with exponent 2.0.
We define a propagable quadratic expression as a quadratic expression whose termwise propagation does not yield the best propagation. In other words, is a quadratic expression that suffers from the dependency problem.
Specifically, a propagable quadratic expression is a sum expression such that there is at least one expr that appears at least twice (because of simplification, this means it appears in a quadratic terms and somewhere else). For example: \(x^2 + y^2\) is not a propagable quadratic expression; \(x^2 + x\) is a propagable quadratic expression; \(x^2 + x y\) is also a propagable quadratic expression
Furthermore, we distinguish between propagable and non-propagable terms. A term is propagable if any of the expressions involved in it appear somewhere else. For example, \(xy + z^2 + z\) is a propagable quadratic, the term \(xy\) is non-propagable, and \(z^2\) is propagable. For propagation, non-propagable terms are handled as if they were linear terms, that is, we do not use the activity of \(x\) and \(y\) to compute the activity of \(xy\) but rather we use directly the activity of \(xy\). Similarly, we do not backward propagate to \(x\) and \(y\) (the product expr handler will do this), but we backward propagate to \(x*y\). More technically, we register \(xy\) for its activity usage, rather than \(x\) and \(y\).
For propagation, we store the quadratic in our data structure in the following way: We count how often a variable appears. Then, a bilinear product expr_i * expr_j is stored as expr_i * expr_j if # expr_i appears > # expr_j appears. When # expr_i appears = # expr_j appears, it then it will be stored as expr_i * expr_j if and only if expr_i < expr_j, where '<' is the expression order (see Ordering Rules in scip_expr.h). Heuristically, this should be useful for propagation. The intuition is that by factoring out the variable that appears most often we should be able to take care of the dependency problem better.
Simple convex quadratics like \(x^2 + y^2\) are ignored since the default nlhdlr will take care of them.
- Note
- The expression needs to be simplified (in particular, it is assumed to be sorted).
- Common subexpressions are also assumed to have been identified, the hashing will fail otherwise!
Sorted implies that:
- expr < expr^2: bases are the same, but exponent 1 < 2
- expr < expr * other_expr: u*v < w holds if and only if v < w (OR8), but here w = u < v, since expr comes before other_expr in the product
- expr < other_expr * expr: u*v < w holds if and only if v < w (OR8), but here v = w
Thus, if we see somebody twice, it is a propagable quadratic.
It also implies that
- expr^2 < expr * other_expr
- other_expr * expr < expr^2
It also implies that x^-2 < x^-1, but since, so far, we do not interpret x^-2 as (x^-1)^2, it is not a problem.
Definition at line 3132 of file nlhdlr_quadratic.c.
References FALSE, isPropagable(), isPropagableTerm(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_UNKNOWN, SCIP_INTERVAL_INFINITY, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_NLHDLR_METHOD_ALL, SCIP_NLHDLR_METHOD_NONE, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIP_STAGE_PRESOLVING, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemory, SCIPcheckExprQuadratic(), SCIPcomputeExprQuadraticCurvature(), SCIPdebugMsg, SCIPexprAreQuadraticExprsVariables(), SCIPexprGetActivity(), SCIPexprGetNChildren(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPexprSetCurvature(), SCIPgetStage(), SCIPgetSubscipDepth(), SCIPinfoMessage(), SCIPintervalIsEntire(), SCIPisExprSum(), SCIPnlhdlrGetData(), SCIPprintExpr(), SCIPprintExprQuadratic(), SCIPregisterExprUsageNonlinear(), and TRUE.
◆ SCIP_DECL_NLHDLREVALAUX()
|
static |
nonlinear handler auxiliary evaluation callback
Definition at line 3405 of file nlhdlr_quadratic.c.
References NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetEvalValue(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), and SCIPgetSolVal().
◆ SCIP_DECL_NLHDLRENFO()
|
static |
nonlinear handler enforcement callback
Definition at line 3470 of file nlhdlr_quadratic.c.
References FALSE, generateIntercut(), INTERLOG, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_SIDETYPE_LEFT, SCIPaddRow(), SCIPcleanupRowprep(), SCIPcreateRowprep(), SCIPdebugMsg, SCIPexprGetQuadraticData(), SCIPfeastol(), SCIPfreeRowprep(), SCIPgetCurrentNode(), SCIPgetCutEfficacy(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPgetNVars(), SCIPgetRhsNonlinear(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowprepRowCons(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPisLPSolBasic(), SCIPmergeRowprepTerms(), SCIPnlhdlrGetData(), SCIPnodeGetDepth(), SCIPnodeGetNumber(), SCIPprintCons(), SCIPprintExpr(), SCIPprintRow(), SCIPprintTransSol(), SCIPreleaseRow(), SCIProwprepGetName(), SCIProwprepGetNVars(), SCIPsnprintf(), SCIPvarGetName(), and TRUE.
◆ SCIP_DECL_NLHDLRINTEVAL()
|
static |
nonlinear handler forward propagation callback
This method should solve the problem
max/min quad expression over box constraints
However, this problem is difficult so we are satisfied with a proxy. Interval arithmetic suffices when no variable appears twice, however this is seldom the case, so we try to take care of the dependency problem to some extent: Let \(P_l = \{i : \text{expr}_l \text{expr}_i \,\text{is a bilinear expr}\}\).
- partition the quadratic expression as sum of quadratic functions \(\sum_l q_l\) where \(q_l = a_l \text{expr}_l^2 + c_l \text{expr}_l + \sum_{i \in P_l} b_{il} \text{expr}_i \text{expr}_l\)
- build interval quadratic functions, i.e., \(a x^2 + b x\) where \(b\) is an interval, i.e., \(a_l \text{expr}_l^2 + [\sum_{i \in P_l} b_{il} \text{expr}_i + c_l] \text{expr}_l\)
- compute \(\min/\max \{ a x^2 + b x : x \in [x] \}\) for each interval quadratic, i.e., \(\min/\max a_l \text{expr}_l^2 + \text{expr}_l [\sum_{i \in P_l} b_{il} \text{expr}_i + c_l] : \text{expr}_l \in [\text{expr}_l]\)
Notes:
- The \(l\)-th quadratic expr (expressions that appear quadratically) is associated with \(q_l\).
nlhdlrdata->quadactivities[l]
is the activity of \(q_l\) as computed in the description above.- The \(q_l\) of a quadratic term might be empty, in which case
nlhdlrdata->quadactivities[l]
is [0,0].
For example, consider \(x^2 + xy\). There are two quadratic expressions, \(x\) and \(y\). The \(q\) associated to \(x\) is \(x^2 + xy\), while the \(q\) associated to \(y\) is empty. Thus,nlhdlrdata->quadactivities[1]
is [0,0] in this case. The logic is to avoid considering the term \(xy\) twice.
- Note
- The order matters! If \(\text{expr}_i\, \text{expr}_l\) is a term in the quadratic, then \(i\) is not in \(P_l\)
Definition at line 3717 of file nlhdlr_quadratic.c.
References b, SCIP_Interval::inf, isPropagableTerm(), NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPexprGetActivity(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfindConshdlr(), SCIPgetCurBoundsTagNonlinear(), SCIPinfoMessage(), SCIPintervalAdd(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalMulScalar(), SCIPintervalQuadUpperBound(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSetEmpty(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPprintExpr(), and SCIP_Interval::sup.
◆ SCIP_DECL_NLHDLRREVERSEPROP()
|
static |
nonlinear handler reverse propagation callback
- Note
- the implemented technique is a proxy for solving the problem min/max{ x_i : quad expr in [quad expr] } and as such can be improved.
Definition at line 3979 of file nlhdlr_quadratic.c.
References b, computeRangeForBilinearProp(), SCIP_Interval::inf, isPropagableTerm(), NULL, propagateBoundsLinExpr(), propagateBoundsQuadExpr(), reversePropagateLinearExpr(), SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPexprGetActivityTag(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetExprBoundsNonlinear(), SCIPintervalAdd(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalIsEntire(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPintervalSub(), SCIPisSumRelEQ(), SCIPswapReals(), SCIP_Interval::sup, and TRUE.
◆ SCIP_DECL_NLHDLRFREEHDLRDATA()
|
static |
callback to free data of handler
Definition at line 4293 of file nlhdlr_quadratic.c.
References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
◆ SCIP_DECL_NLHDLRCOPYHDLR()
|
static |
nonlinear handler copy callback
Definition at line 4304 of file nlhdlr_quadratic.c.
References NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrQuadratic(), and SCIPnlhdlrGetName().