SCIP
Solving Constraint Integer Programs
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_knapsack.h"#include "scip/cons_linear.h"#include "scip/cons_logicor.h"#include "scip/cons_quadratic.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 -1 |
| #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_BILINTERM *bilinterms, int nbilinterms, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
| static SCIP_RETCODE | presolveAddKKTQuadQuadraticTerms (SCIP *scip, SCIP_CONS *objcons, SCIP_QUADVARTERM *quadterms, int nquadterms, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
| static SCIP_RETCODE | presolveAddKKTQuadLinearTerms (SCIP *scip, SCIP_CONS *objcons, SCIP_VAR **lintermvars, SCIP_Real *lintermcoefs, int nlintermvars, SCIP_QUADVARTERM *quadterms, int nquadterms, SCIP_HASHMAP *varhash, SCIP_VAR *objvar, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss) |
| static SCIP_RETCODE | checkConsQuadraticProblem (SCIP *scip, SCIP_CONSHDLR *quadconshdlr, SCIP_CONS *cons, 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 103 of file presol_qpkktref.c.
Referenced by SCIPincludePresolQPKKTref().
◆ PRESOL_DESC
| #define PRESOL_DESC "adds KKT conditions to (mixed-binary) quadratic programs" |
Definition at line 104 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 105 of file presol_qpkktref.c.
Referenced by SCIPincludePresolQPKKTref().
◆ PRESOL_MAXROUNDS
| #define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 108 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 111 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 138 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 222 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 316 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 418 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 571 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 688 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 757 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 837 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 943 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 1031 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 1114 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 bilinterms bilinear terms of quadratic constraint nbilinterms number of bilinear terms of quadratic constraint 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 1273 of file presol_qpkktref.c.
References createKKTDualCons(), NULL, presolveAddKKTQuadQuadraticTerms(), SCIP_CALL, SCIP_OKAY, SCIPaddCoefLinear(), SCIPisFeasZero(), SCIP_BilinTerm::var1, and SCIP_BilinTerm::var2.
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 quadterms quadratic terms of quadratic constraint nquadterms number of quadratic terms of quadratic constraint 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 1347 of file presol_qpkktref.c.
References createKKTDualCons(), NULL, presolveAddKKTQuadLinearTerms(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPisFeasZero(), and SCIP_QuadVarTerm::var.
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 lintermvars linear terms of quadratic constraint lintermcoefs coefficients of linear terms of quadratic constraint nlintermvars number of linear terms of quadratic constraints quadterms quadratic terms of quadratic constraint nquadterms number of quadratic terms of quadratic constraint 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 1406 of file presol_qpkktref.c.
References checkConsQuadraticProblem(), createKKTDualCons(), SCIP_QuadVarTerm::lincoef, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPgetLhsLinear(), SCIPgetRhsLinear(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisFeasZero(), and SCIP_QuadVarTerm::var.
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 t\)
- all other constraints are linear
- all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
- t is the only variable in the objective and doesn't appear in any other constraint
- Parameters
-
scip SCIP data structure quadconshdlr constraint handler data structure cons quadratic constraint 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 zscale pointer to store the value by which we have to scale the quadratic constraint such that the objective variable zhas coefficient -1objrhs pointer to store the right hand side -dof the objective constraintisqp pointer to store whether the problem is a (mixed-binary) QP
Definition at line 1527 of file presol_qpkktref.c.
References FALSE, NULL, REALABS, SCIP_CALL, SCIP_DECL_PRESOLCOPY(), SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPgetCoefsLinearVarsQuadratic(), SCIPgetLhsQuadratic(), SCIPgetLinearVarsQuadratic(), SCIPgetLinvarMayDecreaseQuadratic(), SCIPgetLinvarMayIncreaseQuadratic(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNIntVars(), SCIPgetNLinearVarsQuadratic(), SCIPgetNObjVars(), SCIPgetRhsQuadratic(), 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 1749 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 1764 of file presol_qpkktref.c.
◆ SCIP_DECL_PRESOLEXEC()
|
static |
execution method of presolver
Definition at line 1781 of file presol_qpkktref.c.