nonlinear handler to handle quadratic expressions
Some definitions:
Definition in file nlhdlr_quadratic.c.
#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_USEMONOIDAL TRUE |
#define | DEFAULT_USEMINREP TRUE |
#define | DEFAULT_USEBOUNDS FALSE |
#define | BINSEARCH_MAXITERS 120 |
#define | DEFAULT_NCUTSROOT 20 |
#define | DEFAULT_NCUTS 2 |
#define INTERLOG | ( | x | ) |
Definition at line 52 of file nlhdlr_quadratic.c.
Referenced by areCoefsNumericsGood(), computeIntercut(), computeRestrictionToLine(), computeRestrictionToRay(), computeStrengthenedIntercut(), generateIntercut(), and SCIP_DECL_NLHDLRENFO().
#define NLHDLR_NAME "quadratic" |
Definition at line 65 of file nlhdlr_quadratic.c.
#define NLHDLR_DESC "handler for quadratic expressions" |
Definition at line 66 of file nlhdlr_quadratic.c.
#define NLHDLR_DETECTPRIORITY 1 |
Definition at line 67 of file nlhdlr_quadratic.c.
#define NLHDLR_ENFOPRIORITY 100 |
Definition at line 68 of file nlhdlr_quadratic.c.
#define TABLE_NAME_QUADRATIC "nlhdlr_quadratic" |
Definition at line 71 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define TABLE_DESC_QUADRATIC "quadratic nlhdlr statistics table" |
Definition at line 72 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define TABLE_POSITION_QUADRATIC 14700 |
the position of the statistics table
Definition at line 73 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define TABLE_EARLIEST_STAGE_QUADRATIC SCIP_STAGE_TRANSFORMED |
output of the statistics table is only printed from this stage onwards
Definition at line 74 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define INTERCUTS_MINVIOL 1e-4 |
Definition at line 77 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define DEFAULT_USEINTERCUTS FALSE |
Definition at line 78 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define DEFAULT_USESTRENGTH FALSE |
Definition at line 79 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define DEFAULT_USEMONOIDAL TRUE |
Definition at line 80 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define DEFAULT_USEMINREP TRUE |
Definition at line 81 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define DEFAULT_USEBOUNDS FALSE |
Definition at line 82 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic(), and SCIPincludeSepaInterminor().
#define BINSEARCH_MAXITERS 120 |
Definition at line 83 of file nlhdlr_quadratic.c.
Referenced by doBinarySearch(), doBinarySearch(), findMonoidalQuadRoot(), findRho(), and findRho().
#define DEFAULT_NCUTSROOT 20 |
Definition at line 84 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
#define DEFAULT_NCUTS 2 |
Definition at line 85 of file nlhdlr_quadratic.c.
Referenced by SCIPincludeNlhdlrQuadratic().
Definition at line 175 of file nlhdlr_quadratic.c.
|
static |
output method of statistics table to output file stream 'file'
Definition at line 184 of file nlhdlr_quadratic.c.
References assert(), NLHDLR_NAME, NULL, SCIP_OKAY, SCIPfindConshdlr(), SCIPfindNlhdlrNonlinear(), SCIPinfoMessage(), and SCIPnlhdlrGetData().
|
static |
adds cutcoef * (col - col*) to rowprep
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 227 of file nlhdlr_quadratic.c.
References assert(), NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPcolGetBasisStatus(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPgetSolVal(), SCIPinfoMessage(), SCIProwprepAddConstant(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and sol.
Referenced by computeIntercut(), and computeStrengthenedIntercut().
|
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.
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 262 of file nlhdlr_quadratic.c.
References assert(), FALSE, i, NULL, SCIP_BASESTAT_LOWER, SCIP_Bool, 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().
|
static |
constructs map between lp position of a basic variable and its row in the tableau
scip | SCIP data structure |
map | buffer to store the map |
Definition at line 323 of file nlhdlr_quadratic.c.
References i, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetLPBasisInd(), and SCIPgetNLPRows().
Referenced by storeDenseTableauRowsByColumns().
|
static |
counts the number of basic variables in the quadratic expr
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 349 of file nlhdlr_quadratic.c.
References FALSE, i, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIPcolGetBasisStatus(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPvarGetCol(), and TRUE.
Referenced by createAndStoreSparseRays().
|
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
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 428 of file nlhdlr_quadratic.c.
References assert(), i, NULL, SCIP_BASESTAT_BASIC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), and SCIProwGetBasisStatus().
Referenced by 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].
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 495 of file nlhdlr_quadratic.c.
References assert(), constructBasicVars2TableauRowMap(), i, 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().
|
static |
initializes rays data structure
scip | SCIP data structure |
rays | rays data structure |
Definition at line 595 of file nlhdlr_quadratic.c.
References BMSclearMemory, Rays::rays, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPgetNLPCols(), and SCIPgetNLPRows().
Referenced by createAndStoreSparseRays().
|
static |
initializes rays data structure for bound rays
scip | SCIP data structure |
rays | rays data structure |
size | number of rays to allocate |
Definition at line 618 of file nlhdlr_quadratic.c.
References BMSclearMemory, Rays::rays, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by findVertexAndGetRays().
frees rays data structure
scip | SCIP data structure |
rays | rays data structure |
Definition at line 642 of file nlhdlr_quadratic.c.
References NULL, Rays::rays, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by createAndStoreSparseRays(), and generateIntercut().
|
static |
inserts entry to rays data structure; checks and resizes if more space is needed
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 660 of file nlhdlr_quadratic.c.
References Rays::rays, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.
Referenced by insertRayEntries().
|
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.
nlhdlrexprdata | nlhdlr expression data |
auxvar | aux var of the expr |
map | buffer to store the mapping |
Definition at line 692 of file nlhdlr_quadratic.c.
References i, NULL, SCIPcolGetLPPos(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), and SCIPvarGetCol().
Referenced by createAndStoreSparseRays().
|
static |
inserts entries of factor * nray-th column of densetableaucols into rays data structure
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 735 of file nlhdlr_quadratic.c.
References assert(), FALSE, i, insertRayEntry(), NULL, Rays::rays, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfoMessage(), SCIPisZero(), and TRUE.
Referenced by 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)
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 859 of file nlhdlr_quadratic.c.
References assert(), constructLPPos2ConsPosMap(), countBasicVars(), createRays(), freeRays(), i, insertRayEntries(), NULL, Rays::rays, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, 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().
|
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:
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
The quantities we need are:
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 1058 of file nlhdlr_quadratic.c.
References assert(), BMSclearMemoryArray, i, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPisZero(), sol, and SQR.
Referenced by generateIntercut().
|
static |
computes eigenvec^T ray
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 1177 of file nlhdlr_quadratic.c.
Referenced by computeRestrictionToRay().
|
static |
computes linear part of evaluation of w(ray): \(b_l^T ray_l - ray_a\)
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 1206 of file nlhdlr_quadratic.c.
References i, NULL, SCIP_Real, and SCIPexprGetQuadraticData().
Referenced by computeRestrictionToRay().
|
static |
computes the dot product of v_i and the current ray as well as of v_i and the apex where v_i is the i-th eigenvalue
nlhdlrexprdata | nlhdlr expression data |
apex | array containing the apex of the S-free set in the original space |
raycoefs | coefficients of ray |
rayidx | index of consvar the ray coef is associated to |
raynnonz | length of raycoefs and rayidx |
vapex | array to store \(v_i^T apex\) |
vray | array to store \(v_i^T ray\) |
Definition at line 1263 of file nlhdlr_quadratic.c.
References i, NULL, SCIP_Real, and SCIPexprGetQuadraticData().
Referenced by computeMonoidalStrengthCoef(), and computeRestrictionToLine().
|
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.
scip | SCIP data structure |
nlhdlrexprdata | nlhdlr expression data |
sidefactor | 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise |
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_-\) |
kappa | value of kappa |
apex | apex of C |
coefs2 | buffer to store A, B, C, D, and E of case 2 |
success | did we successfully compute the coefficients? |
Definition at line 1331 of file nlhdlr_quadratic.c.
References a, assert(), b, BMSclearMemoryArray, c, computeVApexAndVRay(), FALSE, i, INTERLOG, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPinfoMessage(), SCIPisZero(), SQR, and TRUE.
Referenced by computeIntercut().
|
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.
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 1464 of file nlhdlr_quadratic.c.
References a, assert(), b, BMSclearMemoryArray, c, computeEigenvecDotRay(), computeWRayLinear(), FALSE, i, INTERLOG, MAX, MIN, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPinfoMessage(), SCIPisZero(), SQR, and TRUE.
Referenced by computeIntercut(), and rayInRecessionCone().
|
static |
returns phi(zlp + t * ray) = sqrt(A t^2 + B t + C) - (D t + E)
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 1701 of file nlhdlr_quadratic.c.
References a, assert(), b, c, QUAD, QUAD_ASSIGN, QUAD_SCALE, QUAD_TO_DBL, SCIP_Real, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSqrtQ, SCIPquadprecSquareD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.
Referenced by computeIntersectionPoint(), computeRoot(), and doBinarySearch().
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.
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 1765 of file nlhdlr_quadratic.c.
References SCIP_Real, and SQR.
Referenced by computeIntersectionPoint().
|
static |
helper function of computeRoot: we want phi to be ≤ 0
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 1778 of file nlhdlr_quadratic.c.
References a, b, BINSEARCH_MAXITERS, c, evalPhiAtRay(), i, SCIP_Real, SCIPisFeasEQ(), SCIPisFeasZero(), and sol.
Referenced by 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.
scip | SCIP data structure |
coefs | value of A |
Definition at line 1823 of file nlhdlr_quadratic.c.
References a, b, c, doBinarySearch(), evalPhiAtRay(), result, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(), and sol.
Referenced by computeIntercut(), and 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.
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 1923 of file nlhdlr_quadratic.c.
References assert(), computeRoot(), evalPhiAtRay(), isCase4a(), MAX, NULL, SCIP_Bool, SCIP_Real, SCIPinfoMessage(), and SCIPisInfinity().
Referenced by computeIntercut(), and rayInRecessionCone().
|
static |
checks if numerics of the coefficients are not too bad
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 1990 of file nlhdlr_quadratic.c.
References ABS, assert(), FALSE, INTERLOG, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisHugeValue(), and TRUE.
Referenced by computeIntercut().
|
static |
computes the coefficients a, b, c defining the quadratic function defining set S restricted to the line theta * apex.
The solution to the monoidal strengthening problem is then given by the smallest root of the function a * theta^2 + b * theta + c
scip | SCIP data structure |
nlhdlrexprdata | nlhdlr expression data |
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_-\) |
vapex | array containing \(v_i^T apex\) |
vray | array containing \(v_i^T ray\) |
kappa | value of kappa |
sidefactor | 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise |
a | pointer to store quadratic coefficient |
b | pointer to store linear coefficient |
c | pointer to store constant |
Definition at line 2071 of file nlhdlr_quadratic.c.
References a, b, c, i, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPisZero(), and SQR.
Referenced by computeMonoidalStrengthCoef().
|
static |
check if ray was in strip by checking if the point in the monoid corresponding to the cutcoef we just found is "on the wrong side" of the hyperplane -(a - lambda^Ta lambda)^T x
nlhdlrexprdata | nlhdlr expression data |
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_-\) |
vapex | array containing \(v_i^T apex\) |
vray | array containing \(v_i^T ray\) |
kappa | value of kappa |
sidefactor | 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise |
cutcoef | optimal solution of the monoidal quadratic |
Definition at line 2121 of file nlhdlr_quadratic.c.
References assert(), i, NULL, SCIP_Bool, SCIP_Real, SCIPexprGetQuadraticData(), and SQR.
Referenced by computeMonoidalStrengthCoef().
computes the smallest root of the quadratic function a*x^2 + b*x + c with a > 0 and b^2 - 4ac >= 0. We use binary search between -inf and minimum at -b/2a.
scip | SCIP data structure |
a | quadratic coefficient |
b | linear coefficient |
c | constant |
Definition at line 2172 of file nlhdlr_quadratic.c.
References a, ABS, assert(), b, BINSEARCH_MAXITERS, c, result, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(), SCIPisInfinity(), SCIPisZero(), sol, and SQR.
Referenced by computeMonoidalStrengthCoef().
|
static |
computes the apex of the S-free set (if it exists)
nlhdlrexprdata | nlhdlr expression data |
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_-\) |
kappa | value of kappa |
sidefactor | 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise |
apex | array to store apex |
success | TRUE if computation of apex was successful |
Definition at line 2261 of file nlhdlr_quadratic.c.
References assert(), FALSE, i, NULL, SCIP_Bool, SCIP_Real, SCIPexprGetQuadraticData(), SQR, and TRUE.
Referenced by computeIntercut().
|
static |
for a given ray, computes the cut coefficient using monoidal strengthening (if possible)
scip | SCIP data structure |
nlhdlrexprdata | nlhdlr expression data |
lppos | lp pos of current ray |
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 |
kappa | value of kappa |
apex | array containing the apex of the S-free set in the original space |
sidefactor | 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise |
cutcoef | pointer to store cut coef |
success | TRUE if monoidal strengthening could be applied |
Definition at line 2327 of file nlhdlr_quadratic.c.
References a, assert(), b, c, computeMonoidalQuadCoefs(), computeVApexAndVRay(), FALSE, findMonoidalQuadRoot(), isRayInStrip(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPcolGetVar(), SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIProwIsIntegral(), SCIPvarGetType(), SQR, and TRUE.
Referenced by computeIntercut().
|
static |
sparsify intersection cut by replacing non-basic variables with their bounds if their coefficient allows it
scip | SCIP data structure |
rowprep | rowprep for the generated cut |
Definition at line 2402 of file nlhdlr_quadratic.c.
References i, NULL, nvars, SCIP_Real, SCIPgetSolVal(), SCIPisZero(), SCIProwprepAddSide(), SCIProwprepGetCoefs(), SCIProwprepGetNVars(), SCIProwprepGetVars(), SCIProwprepSetCoef(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and var.
Referenced by SCIP_DECL_NLHDLRENFO().
|
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.
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 2455 of file nlhdlr_quadratic.c.
References addColToCut(), addRowToCut(), areCoefsNumericsGood(), assert(), computeApex(), computeIntersectionPoint(), computeMonoidalStrengthCoef(), computeRestrictionToLine(), computeRestrictionToRay(), computeRoot(), FALSE, i, INTERLOG, NULL, Rays::rays, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPexprGetQuadraticData(), SCIPfreeBufferArrayNull, SCIPgetLPCols(), SCIPgetLPRows(), SCIPinfinity(), SCIPinfoMessage(), SCIPisInfinity(), SCIProwGetBasisStatus(), sol, and TRUE.
Referenced by computeStrengthenedIntercut(), and generateIntercut().
|
static |
combine ray 1 and 2 to obtain new ray coef1 * ray1 - coef2 * ray2 in sparse format
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 2682 of file nlhdlr_quadratic.c.
References SCIP_Real.
Referenced by rayInRecessionCone().
|
static |
checks if two rays are linearly dependent
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 2739 of file nlhdlr_quadratic.c.
References FALSE, i, SCIP_Bool, SCIP_Real, SCIPisEQ(), SCIPisZero(), and TRUE.
Referenced by findRho().
|
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.
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 2788 of file nlhdlr_quadratic.c.
References alpha, combineRays(), computeIntersectionPoint(), computeRestrictionToRay(), FALSE, i, Rays::rays, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and TRUE.
Referenced by 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
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 2857 of file nlhdlr_quadratic.c.
References alpha, BINSEARCH_MAXITERS, FALSE, i, rayInRecessionCone(), Rays::rays, raysAreDependent(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), and SCIPisZero().
Referenced by computeStrengthenedIntercut().
|
static |
computes intersection cut using negative edge extension to strengthen rays that do not intersect (i.e., rays in the recession cone)
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 2976 of file nlhdlr_quadratic.c.
References addColToCut(), addRowToCut(), assert(), computeIntercut(), FALSE, findRho(), i, INTERLOG, Rays::rays, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIPisInfinity(), SCIPisZero(), SCIProwGetBasisStatus(), sol, and TRUE.
Referenced by generateIntercut().
|
static |
sets variable in solution "vertex" to its nearest bound
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 3092 of file nlhdlr_quadratic.c.
References bound, FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisInfinity(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sol, TRUE, and var.
Referenced by 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.,
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 3137 of file nlhdlr_quadratic.c.
References createBoundRays(), i, NULL, Rays::rays, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcolGetLPPos(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPvarGetCol(), setVarToNearestBound(), sol, and TRUE.
Referenced by generateIntercut().
|
static |
checks if the quadratic constraint is violated by sol
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 3220 of file nlhdlr_quadratic.c.
References FALSE, i, NULL, SCIP_Bool, SCIP_Real, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPgetSolVal(), sol, SQR, and TRUE.
Referenced by generateIntercut().
|
static |
generates intersection cut that cuts off sol (which violates the quadratic constraint cons)
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 3304 of file nlhdlr_quadratic.c.
References assert(), computeIntercut(), computeStrengthenedIntercut(), createAndStoreSparseRays(), FALSE, findVertexAndGetRays(), freeRays(), i, 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(), sol, and TRUE.
Referenced by SCIP_DECL_NLHDLRENFO().
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:
qexpr | quadratic representation data |
Definition at line 3471 of file nlhdlr_quadratic.c.
References FALSE, i, NULL, SCIP_Bool, SCIP_Real, SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), and TRUE.
Referenced by SCIP_DECL_NLHDLRDETECT().
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:
qexpr | quadratic representation data |
idx | index of quadratic term to consider |
Definition at line 3504 of file nlhdlr_quadratic.c.
References NULL, SCIP_Bool, SCIP_Real, and SCIPexprGetQuadraticQuadTerm().
Referenced by SCIP_DECL_NLHDLRDETECT(), SCIP_DECL_NLHDLRINTEVAL(), and SCIP_DECL_NLHDLRREVERSEPROP().
|
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
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 3522 of file nlhdlr_quadratic.c.
References a, assert(), b, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPgetExprBoundsNonlinear(), SCIPinfoMessage(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalSet(), SCIPintervalSolveUnivariateQuadExpression(), SCIPprintExpr(), SCIPtightenExprIntervalNonlinear(), SCIP_Interval::sup, and TRUE.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
|
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
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 3573 of file nlhdlr_quadratic.c.
References assert(), b, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPinfoMessage(), SCIPintervalDivScalar(), SCIPprintExpr(), SCIPtightenExprIntervalNonlinear(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
|
static |
returns max of a/x - c*x for x in {x1, x2} with x1, x2 > 0
a | coefficient a |
c | coefficient c |
x1 | coefficient x1 > 0 |
x2 | coefficient x2 > 0 |
Definition at line 3609 of file nlhdlr_quadratic.c.
References a, assert(), c, MAX, SCIP_Real, SCIPintervalGetRoundingMode(), SCIPintervalNegateReal(), SCIPintervalSetRoundingMode(), and SCIPintervalSetRoundingModeUpwards().
Referenced by computeMaxForBilinearProp().
|
static |
returns max of a/x - c*x for x in dom; it assumes that dom is contained in (0, +inf)
a | coefficient a |
c | coefficient c |
dom | domain of x |
Definition at line 3637 of file nlhdlr_quadratic.c.
References a, assert(), c, 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().
|
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.
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 3704 of file nlhdlr_quadratic.c.
References assert(), computeMaxForBilinearProp(), SCIP_Interval::inf, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalMulScalar(), SCIPintervalSetBounds(), SCIPintervalSetEntire(), and SCIP_Interval::sup.
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
|
static |
reverse propagates coef_i expr_i + constant in rhs
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 3739 of file nlhdlr_quadratic.c.
References i, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprGetActivity(), SCIPfreeBufferArray, SCIPintervalPropagateWeightedSum(), and SCIPtightenExprIntervalNonlinear().
Referenced by SCIP_DECL_NLHDLRREVERSEPROP().
|
static |
callback to free expression specific data
Definition at line 3789 of file nlhdlr_quadratic.c.
References assert(), NULL, SCIP_OKAY, SCIPexprGetQuadraticData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
|
static |
callback to detect structure in expression tree
A term is quadratic if
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.
Sorted implies that:
Thus, if we see somebody twice, it is a propagable quadratic.
It also implies that
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 3854 of file nlhdlr_quadratic.c.
References assert(), FALSE, i, 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.
|
static |
nonlinear handler auxiliary evaluation callback
Definition at line 4127 of file nlhdlr_quadratic.c.
References assert(), i, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetEvalValue(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), and sol.
|
static |
nonlinear handler enforcement callback
Definition at line 4192 of file nlhdlr_quadratic.c.
References ABS, assert(), depth, FALSE, generateIntercut(), INTERLOG, MAX, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Longint, SCIP_LONGINT_FORMAT, 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(), sol, sparsifyIntercut(), and TRUE.
|
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}\}\).
Notes:
Definition at line 4448 of file nlhdlr_quadratic.c.
References assert(), b, i, 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.
|
static |
nonlinear handler reverse propagation callback
Definition at line 4710 of file nlhdlr_quadratic.c.
References assert(), b, computeRangeForBilinearProp(), i, 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.
|
static |
callback to free data of handler
Definition at line 5024 of file nlhdlr_quadratic.c.
References assert(), NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
|
static |
nonlinear handler copy callback
Definition at line 5035 of file nlhdlr_quadratic.c.
References assert(), NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrQuadratic(), and SCIPnlhdlrGetName().