qpkktref presolver
This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic program
\[ \begin{array}{ll} \min & x^T Q x + c^T x + d \\ & A x \leq b, \\ & x \in \{0, 1\}^{p} \times R^{n-p}. \end{array} \]
We first check if the structure of the program is like (QP), see the documentation of the function checkConsQuadraticProblem().
If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT conditions. For a continuous QPs the KKT conditions have the form
\[ \begin{array}{ll} Q x + c + A^T \mu = 0,\\ Ax \leq b,\\ \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\ \mu \geq 0. \end{array} \]
where \(\mu\) are the Lagrangian variables. Each of the complementarity constraints \(\mu_i \cdot (Ax - b)_i = 0\) is enforced via an SOS1 constraint for \(\mu_i\) and an additional slack variable \(s_i = (Ax - b)_i\).
For mixed-binary QPs, the KKT-like conditions are
\[ \begin{array}{ll} Q x + c + A^T \mu + I_J \lambda = 0,\\ Ax \leq b,\\ x_j \in \{0,1\} & j \in J,\\ (1 - x_j) \cdot z_j = 0 & j \in J,\\ x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\ \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\ \mu \geq 0, \end{array} \]
where \(J = \{1,\dots, p\}\), \(\mu\) and \(\lambda\) are the Lagrangian variables, and \(I_J\) is the submatrix of the \(n\times n\) identity matrix with columns indexed by \(J\). For the derivation of the KKT-like conditions, see
Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,
Tobias Fischer, PhD Thesis (2016)
Algorithmically:
we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.
Definition in file presol_qpkktref.c.
#include "blockmemshell/memory.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_knapsack.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/cons_sos1.h"
#include "scip/cons_varbound.h"
#include "scip/presol_qpkktref.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_presol.h"
#include "scip/scip_prob.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | PRESOL_NAME "qpkktref" |
#define | PRESOL_DESC "adds KKT conditions to (mixed-binary) quadratic programs" |
#define | PRESOL_PRIORITY -1 |
#define | PRESOL_MAXROUNDS 0 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */ |
Functions | |
static SCIP_RETCODE | createKKTComplementarityLinear (SCIP *scip, const char *namepart, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_VAR *dualvar, SCIP_Bool takelhs, int *naddconss) |
static SCIP_RETCODE | createKKTComplementarityBounds (SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualvar, SCIP_Bool takelb, int *naddconss) |
static SCIP_RETCODE | createKKTComplementarityBinary (SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualbin1, SCIP_VAR *dualbin2, int *naddconss) |
static SCIP_RETCODE | createKKTDualCons (SCIP *scip, SCIP_CONS *objcons, SCIP_VAR *var, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, SCIP_CONS **dualcons, int *naddconss) |
static SCIP_RETCODE | presolveAddKKTLinearCons (SCIP *scip, SCIP_CONS *objcons, const char *namepart, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
static SCIP_RETCODE | presolveAddKKTLinearConss (SCIP *scip, SCIP_CONS *objcons, SCIP_CONS **savelinconss, int nlinconss, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss) |
static SCIP_RETCODE | presolveAddKKTKnapsackConss (SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss) |
static SCIP_RETCODE | presolveAddKKTSetppcConss (SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss) |
static SCIP_RETCODE | presolveAddKKTVarboundConss (SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss) |
static SCIP_RETCODE | presolveAddKKTLogicorConss (SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss) |
static SCIP_RETCODE | presolveAddKKTAggregatedVars (SCIP *scip, SCIP_CONS *objcons, SCIP_VAR **agrvars, int nagrvars, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
static SCIP_RETCODE | presolveAddKKTQuadBilinearTerms (SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
static SCIP_RETCODE | presolveAddKKTQuadQuadraticTerms (SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
static SCIP_RETCODE | presolveAddKKTQuadLinearTerms (SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_VAR *objvar, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
static SCIP_RETCODE | checkConsQuadraticProblem (SCIP *scip, SCIP_CONS *cons, SCIP_EXPR *quadexpr, SCIP_Bool allowbinary, SCIP_VAR **objvar, SCIP_Real *scale, SCIP_Real *objrhs, SCIP_Bool *isqp) |
static | SCIP_DECL_PRESOLCOPY (presolCopyQPKKTref) |
static | SCIP_DECL_PRESOLFREE (presolFreeQPKKTref) |
static | SCIP_DECL_PRESOLEXEC (presolExecQPKKTref) |
SCIP_RETCODE | SCIPincludePresolQPKKTref (SCIP *scip) |
#define PRESOL_NAME "qpkktref" |
Definition at line 113 of file presol_qpkktref.c.
#define PRESOL_DESC "adds KKT conditions to (mixed-binary) quadratic programs" |
Definition at line 114 of file presol_qpkktref.c.
#define PRESOL_PRIORITY -1 |
priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators
Definition at line 115 of file presol_qpkktref.c.
#define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 117 of file presol_qpkktref.c.
#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 119 of file presol_qpkktref.c.
|
static |
for a linear constraint \(a^T x \leq b\), create the complementarity constraint \(\mu \cdot s = 0\), where \(s = b - a^T x\) and \(\mu\) is the dual variable associated to the constraint \(a^T x \leq b\)
scip | SCIP pointer |
namepart | name of linear constraint |
vars | variables of linear constraint |
vals | coefficients of variables in linear constraint |
lhs | left hand side of linear constraint |
rhs | right hand side of linear constraint |
nvars | number of variables of linear constraint |
dualvar | dual variable associated to linear constraint |
takelhs | whether to consider the lhs or the rhs of the constraint |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 146 of file presol_qpkktref.c.
References assert(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPaddVarSOS1(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicSOS1(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPisInfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), and vars.
Referenced by presolveAddKKTLinearCons().
|
static |
create complementarity constraints of KKT conditions associated to bounds of variables
scip | SCIP pointer |
var | variable |
dualvar | dual variable associated to bound of variable |
takelb | whether to consider the lower or upper bound of variable |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 230 of file presol_qpkktref.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPaddVarSOS1(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicSOS1(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), and var.
Referenced by createKKTDualCons().
|
static |
create the complementarity constraints of the KKT-like conditions associated to a binary variable \(x_i\); these are \((1 - x_i) \cdot z_i = 0\) and \(x_i \cdot (z_i - \lambda_i) = 0\), where \(z_i\) and \(\lambda_i\) are dual variables
scip | SCIP pointer |
var | variable |
dualbin1 | first dual variable associated to binary variable |
dualbin2 | second dual variable associated to binary variable |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 324 of file presol_qpkktref.c.
References assert(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPaddVarSOS1(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicSOS1(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetName(), and var.
Referenced by createKKTDualCons().
|
static |
create/get dual constraint of KKT conditions associated to primal variable
if variable does not already exist in hashmap then
if variable exists in hasmap then the dual constraint associated to the variable has already been created and is returned
scip | SCIP pointer |
objcons | objective constraint |
var | variable |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
dualcons | dual constraint associated to variable |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 426 of file presol_qpkktref.c.
References assert(), createKKTComplementarityBinary(), createKKTComplementarityBounds(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddVar(), SCIPcreateConsBasicLinear(), SCIPcreateVarBasic(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPinfinity(), SCIPisInfinity(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), TRUE, and var.
Referenced by presolveAddKKTLinearCons(), presolveAddKKTQuadBilinearTerms(), presolveAddKKTQuadLinearTerms(), and presolveAddKKTQuadQuadraticTerms().
|
static |
handle (a single) linear constraint for quadratic constraint update
for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
for step 4 see the documentation of the function createKKTComplementarityLinear() for further information.
scip | SCIP pointer |
objcons | objective constraint |
namepart | name of linear constraint |
vars | variables of linear constraint |
vals | coefficients of variables in linear constraint |
lhs | left hand side of linear constraint |
rhs | right hand side of linear constraint |
nvars | number of variables of linear constraint |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 579 of file presol_qpkktref.c.
References assert(), createKKTComplementarityLinear(), createKKTDualCons(), FALSE, i, NULL, nvars, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddVar(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPreleaseVar(), SCIPsnprintf(), TRUE, var, and vars.
Referenced by presolveAddKKTAggregatedVars(), presolveAddKKTKnapsackConss(), presolveAddKKTLinearConss(), presolveAddKKTLogicorConss(), presolveAddKKTSetppcConss(), and presolveAddKKTVarboundConss().
|
static |
handle linear constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
scip | SCIP pointer |
objcons | objective constraint |
savelinconss | copy of array with linear constraints |
nlinconss | number of linear constraints |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
ndelconss | buffer to increase with number of deleted constraints |
Definition at line 696 of file presol_qpkktref.c.
References assert(), c, NULL, nvars, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPdelCons(), SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisFeasEQ(), and vars.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle knapsack constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
scip | SCIP pointer |
objcons | objective constraint |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
ndelconss | buffer to increase with number of deleted constraints |
Definition at line 765 of file presol_qpkktref.c.
References assert(), c, NULL, nvars, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack(), SCIPgetWeightsKnapsack(), SCIPinfinity(), and vars.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle set packing constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
scip | SCIP pointer |
objcons | objective constraint |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
ndelconss | buffer to increase with number of deleted constraints |
Definition at line 845 of file presol_qpkktref.c.
References assert(), c, NULL, nvars, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPinfinity(), and vars.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle varbound constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
scip | SCIP pointer |
objcons | objective constraint |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
ndelconss | buffer to increase with number of deleted constraints |
Definition at line 951 of file presol_qpkktref.c.
References assert(), c, NULL, nvars, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPisFeasEQ(), and vars.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle logicor constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
scip | SCIP pointer |
objcons | objective constraint |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
ndelconss | buffer to increase with number of deleted constraints |
Definition at line 1039 of file presol_qpkktref.c.
References assert(), c, NULL, nvars, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNVarsLogicor(), SCIPgetVarsLogicor(), SCIPinfinity(), and vars.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle aggregated variables for quadratic constraint update
we apply the function presolveAddKKTLinearCons() to the aggregation constraint, see the documentation of this function for further information
scip | SCIP pointer |
objcons | objective constraint |
agrvars | aggregated variables |
nagrvars | number of aggregated variables |
varhash | hash map from variable to index of linear constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 1122 of file presol_qpkktref.c.
References assert(), NULL, nvars, presolveAddKKTLinearCons(), scalars, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArrayNull, SCIPisFeasEQ(), SCIPisFeasZero(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetLbGlobal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetName(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), var, and vars.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle bilinear terms of quadratic constraint for quadratic constraint update
For the two variables of each bilinear term
for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
scip | SCIP pointer |
objcons | objective constraint |
quadexpr | quadratic expression |
varhash | hash map from variable to index of linear constraint |
scale | scale factor of quadratic constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 1281 of file presol_qpkktref.c.
References assert(), createKKTDualCons(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisFeasZero(), and SCIPswapPointers().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle quadratic terms of quadratic constraint for quadratic constraint update
For each quadratic term variable
for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
scip | SCIP pointer |
objcons | objective constraint |
quadexpr | quadratic expression |
varhash | hash map from variable to index of linear constraint |
scale | scale factor of quadratic constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 1359 of file presol_qpkktref.c.
References assert(), createKKTDualCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetVarExprVar(), SCIPisExprVar(), and SCIPisFeasZero().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
handle linear terms of quadratic constraint for quadratic constraint update
For each linear term variable
for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
scip | SCIP pointer |
objcons | objective constraint |
quadexpr | quadratic expression |
varhash | hash map from variable to index of linear constraint |
objvar | variable of objective function |
scale | scale factor of quadratic constraint |
dualconss | array with dual constraints |
ndualconss | pointer to store number of dual constraints |
naddconss | buffer to increase with number of created additional constraints |
Definition at line 1423 of file presol_qpkktref.c.
References assert(), createKKTDualCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetLhsLinear(), SCIPgetRhsLinear(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisExprVar(), SCIPisFeasZero(), and var.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
checks for a given constraint whether it is the objective function of a (mixed-binary) quadratic program
\[ \begin{array}{ll} \min & z \\ s.t. & x^T Q x + c^T x + d <= z \\ & A x \leq b, \\ & x \in \{0, 1\}^{p} \times R^{n-p}, \end{array} \]
which is equivalent to
\[ \begin{array}{ll} \min & x^T Q x + c^T x + d \\ s.t. & A x \leq b, \\ & x \in \{0, 1\}^{p} \times R^{n-p}. \end{array} \]
We check whether
scip | SCIP data structure |
cons | nonlinear constraint |
quadexpr | quadratic expression |
allowbinary | if TRUE then allow binary variables in the problem, if FALSE then all variables have to be continuous |
objvar | pointer to store the objective variable z |
scale | pointer to store the value by which we have to scale the quadratic constraint such that the objective variable z has coefficient -1 |
objrhs | pointer to store the right hand side -d of the objective constraint |
isqp | pointer to store whether the problem is a (mixed-binary) QP |
Definition at line 1547 of file presol_qpkktref.c.
References assert(), FALSE, NULL, obj, REALABS, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetNConss(), SCIPexprGetQuadraticData(), SCIPfindConshdlr(), SCIPgetLhsNonlinear(), SCIPgetLinvarMayIncreaseNonlinear(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNIntVars(), SCIPgetNObjVars(), SCIPgetRhsNonlinear(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbOriginal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetOrigvarSum(), SCIPvarGetUbOriginal(), and TRUE.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1791 of file presol_qpkktref.c.
References assert(), NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolQPKKTref(), and SCIPpresolGetName().
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1806 of file presol_qpkktref.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
|
static |
execution method of presolver
Definition at line 1823 of file presol_qpkktref.c.
References assert(), checkConsQuadraticProblem(), FALSE, i, NULL, nvars, presolveAddKKTAggregatedVars(), presolveAddKKTKnapsackConss(), presolveAddKKTLinearConss(), presolveAddKKTLogicorConss(), presolveAddKKTQuadBilinearTerms(), presolveAddKKTQuadLinearTerms(), presolveAddKKTQuadQuadraticTerms(), presolveAddKKTSetppcConss(), presolveAddKKTVarboundConss(), SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPallocBufferArray, SCIPblkmem(), SCIPcheckQuadraticNonlinear(), SCIPcomputeExprQuadraticCurvature(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateConsBasicLinear(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetConsNVars(), SCIPgetConsVars(), SCIPgetExprNonlinear(), SCIPgetFixedVars(), SCIPgetNBinVars(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPpresolGetData(), SCIPreleaseCons(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), TRUE, and vars.