SCIP
Solving Constraint Integer Programs
presol_qpkktref.c File Reference
Detailed Description
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 handle the quadratic term variables of the quadratic constraint like in the method presolveAddKKTQuadQuadraticTerms()
- we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms()
- we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms()
- we handle linear constraints in the method presolveAddKKTLinearConss()
- we handle aggregated variables in the method presolveAddKKTAggregatedVars()
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) |
Macro Definition Documentation
◆ PRESOL_NAME
| #define PRESOL_NAME "qpkktref" |
Definition at line 113 of file presol_qpkktref.c.
Referenced by SCIPincludePresolQPKKTref().
◆ PRESOL_DESC
| #define PRESOL_DESC "adds KKT conditions to (mixed-binary) quadratic programs" |
Definition at line 114 of file presol_qpkktref.c.
Referenced by SCIPincludePresolQPKKTref().
◆ PRESOL_PRIORITY
| #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.
Referenced by SCIPincludePresolQPKKTref().
◆ PRESOL_MAXROUNDS
| #define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 118 of file presol_qpkktref.c.
Referenced by SCIPincludePresolQPKKTref().
◆ PRESOL_TIMING
| #define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 121 of file presol_qpkktref.c.
Referenced by SCIPincludePresolQPKKTref().
Function Documentation
◆ createKKTComplementarityLinear()
|
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\)
- Parameters
-
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 148 of file presol_qpkktref.c.
References createKKTComplementarityBounds(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPaddVarSOS1(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicSOS1(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPisInfinity(), SCIPreleaseCons(), SCIPreleaseVar(), and SCIPsnprintf().
Referenced by presolveAddKKTLinearCons().
◆ createKKTComplementarityBounds()
|
static |
create complementarity constraints of KKT conditions associated to bounds of variables
- for an upper bound constraint \(x_i \leq u_i\), create the complementarity constraint \(\mu_i \cdot s_i = 0\), where \(s_i = u_i - x_i\) and \(\mu_i\) is the dual variable of the upper bound constraint
- for a lower bound constraint \(x_i \geq l_i\), create the complementarity constraint \(\lambda_i \cdot w_i = 0\), where \(w_i = x_i - l_i\) and \(\lambda_i\) is the dual variable of the lower bound constraint
- Parameters
-
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 232 of file presol_qpkktref.c.
References createKKTComplementarityBinary(), NULL, 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(), and SCIPvarGetUbGlobal().
Referenced by createKKTComplementarityLinear(), and createKKTDualCons().
◆ createKKTComplementarityBinary()
|
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
- Parameters
-
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 326 of file presol_qpkktref.c.
References createKKTDualCons(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPaddVarSOS1(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicSOS1(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), and SCIPvarGetName().
Referenced by createKKTComplementarityBounds(), and createKKTDualCons().
◆ createKKTDualCons()
|
static |
create/get dual constraint of KKT conditions associated to primal variable
if variable does not already exist in hashmap then
- create dual constraint for variable
- create a dual variable \(\mu_i\) for the upper bound constraint \(x_i \leq u_i\)
- create a dual variable \(\lambda_i\) for the lower bound constraint \(x_i \geq l_i\)
- create the complementarity constraint \(\mu_i \cdot s_i = 0\), where \(s_i = u_i - x_i\)
- create the complementarity constraint \(\lambda_i \cdot w_i = 0\), where \(w_i = x_i - l_i\)
- add objective coefficients of dual variables
- the treatment of binary variables needs special care see the documentation of createKKTComplementarityBinary()
if variable exists in hasmap then the dual constraint associated to the variable has already been created and is returned
- Parameters
-
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 428 of file presol_qpkktref.c.
References createKKTComplementarityBinary(), createKKTComplementarityBounds(), FALSE, NULL, presolveAddKKTLinearCons(), 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(), and TRUE.
Referenced by createKKTComplementarityBinary(), presolveAddKKTLinearCons(), presolveAddKKTQuadBilinearTerms(), presolveAddKKTQuadLinearTerms(), and presolveAddKKTQuadQuadraticTerms().
◆ presolveAddKKTLinearCons()
|
static |
handle (a single) linear constraint for quadratic constraint update
- create the dual constraints (i.e., the two rows of \(Q x + c + A^T \mu = 0\)) associated to the variables of the linear constraint, if not done already
- create the dual variables and the complementarity constraints for the lower and upper bound constraints of the variables of the linear constraint, if not done already
- create the dual variable \(\mu_i\) associated to this linear constraint
- create the complementarity constraint \(\mu_i \cdot (Ax - b)_i = 0\) associated to this linear constraint
- add objective coefficients of dual variables
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.
- Parameters
-
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 581 of file presol_qpkktref.c.
References createKKTComplementarityLinear(), createKKTDualCons(), FALSE, NULL, presolveAddKKTLinearConss(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddVar(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPreleaseVar(), SCIPsnprintf(), and TRUE.
Referenced by createKKTDualCons(), presolveAddKKTAggregatedVars(), presolveAddKKTKnapsackConss(), presolveAddKKTLinearConss(), presolveAddKKTLogicorConss(), presolveAddKKTSetppcConss(), and presolveAddKKTVarboundConss().
◆ presolveAddKKTLinearConss()
|
static |
handle linear constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
- Parameters
-
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 698 of file presol_qpkktref.c.
References NULL, presolveAddKKTKnapsackConss(), presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPdelCons(), SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), and SCIPisFeasEQ().
Referenced by presolveAddKKTLinearCons().
◆ presolveAddKKTKnapsackConss()
|
static |
handle knapsack constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
- Parameters
-
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 767 of file presol_qpkktref.c.
References NULL, presolveAddKKTLinearCons(), presolveAddKKTSetppcConss(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack(), SCIPgetWeightsKnapsack(), and SCIPinfinity().
Referenced by presolveAddKKTLinearConss().
◆ presolveAddKKTSetppcConss()
|
static |
handle set packing constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
- Parameters
-
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 847 of file presol_qpkktref.c.
References NULL, presolveAddKKTLinearCons(), presolveAddKKTVarboundConss(), 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(), and SCIPinfinity().
Referenced by presolveAddKKTKnapsackConss().
◆ presolveAddKKTVarboundConss()
|
static |
handle varbound constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
- Parameters
-
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 953 of file presol_qpkktref.c.
References NULL, presolveAddKKTLinearCons(), presolveAddKKTLogicorConss(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), and SCIPisFeasEQ().
Referenced by presolveAddKKTSetppcConss().
◆ presolveAddKKTLogicorConss()
|
static |
handle logicor constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation
- Parameters
-
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 1041 of file presol_qpkktref.c.
References NULL, presolveAddKKTAggregatedVars(), presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNVarsLogicor(), SCIPgetVarsLogicor(), and SCIPinfinity().
Referenced by presolveAddKKTVarboundConss().
◆ presolveAddKKTAggregatedVars()
|
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
- Parameters
-
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 1124 of file presol_qpkktref.c.
References NULL, presolveAddKKTLinearCons(), presolveAddKKTQuadBilinearTerms(), 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(), and SCIPvarGetUbGlobal().
Referenced by presolveAddKKTLogicorConss().
◆ presolveAddKKTQuadBilinearTerms()
|
static |
handle bilinear terms of quadratic constraint for quadratic constraint update
For the two variables of each bilinear term
- create the dual constraints (i.e., the two rows of \(Q x + c + A^T \mu = 0\)) associated to these variables, if not done already
- create the dual variables and the complementarity constraints for the lower and upper bound constraints of the two variables of the bilinear term, if not done already
- add the coefficient \(Q_{ij}\) of the bilinear term to the dual constraint
for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
- Parameters
-
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 1283 of file presol_qpkktref.c.
References createKKTDualCons(), NULL, presolveAddKKTQuadQuadraticTerms(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisFeasZero(), and SCIPswapPointers().
Referenced by presolveAddKKTAggregatedVars().
◆ presolveAddKKTQuadQuadraticTerms()
|
static |
handle quadratic terms of quadratic constraint for quadratic constraint update
For each quadratic term variable
- create the dual constraint (i.e., a row of \(Q x + c + A^T \mu = 0\)) associated to this variable, if not done already
- create the dual variables and the complementarity constraints for the lower and upper bound constraints of this variable, if not done already
- add the coefficient \(Q_{ii}\) of this variable to the dual constraint
for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
- Parameters
-
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 1361 of file presol_qpkktref.c.
References createKKTDualCons(), NULL, presolveAddKKTQuadLinearTerms(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetVarExprVar(), SCIPisExprVar(), and SCIPisFeasZero().
Referenced by presolveAddKKTQuadBilinearTerms().
◆ presolveAddKKTQuadLinearTerms()
|
static |
handle linear terms of quadratic constraint for quadratic constraint update
For each linear term variable
- create the dual constraint (i.e., a row of \(Q x + c + A^T \mu = 0\)) associated to this variable, if not done already
- create the dual variables and the complementarity constraints for the lower and upper bound constraints of this variable, if not done already
- add the right hand side \(-c_i\) to the dual constraint
- add \(c_i\) to the objective constraint \(1/2 ( c^T x + b^T \mu) = t\), where t is the objective variable
for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
- Parameters
-
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 1425 of file presol_qpkktref.c.
References checkConsQuadraticProblem(), createKKTDualCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetLhsLinear(), SCIPgetRhsLinear(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisExprVar(), and SCIPisFeasZero().
Referenced by presolveAddKKTQuadQuadraticTerms().
◆ checkConsQuadraticProblem()
|
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
- there is a single quadratic constraint that can be written as \(x^T Q x + c^T x + d \leq z\)
- all other constraints are linear
- all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
- z is the only variable in the objective and doesn't appear in any other constraint
- Parameters
-
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 1549 of file presol_qpkktref.c.
References FALSE, NULL, REALABS, SCIP_CALL, SCIP_DECL_PRESOLCOPY(), 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 presolveAddKKTQuadLinearTerms().
◆ SCIP_DECL_PRESOLCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1793 of file presol_qpkktref.c.
Referenced by checkConsQuadraticProblem().
◆ SCIP_DECL_PRESOLFREE()
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1808 of file presol_qpkktref.c.
◆ SCIP_DECL_PRESOLEXEC()
|
static |
execution method of presolver
Definition at line 1825 of file presol_qpkktref.c.