Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

qpkktref presolver

Author
Tobias Fischer

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)
 

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 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

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
scipSCIP pointer
namepartname of linear constraint
varsvariables of linear constraint
valscoefficients of variables in linear constraint
lhsleft hand side of linear constraint
rhsright hand side of linear constraint
nvarsnumber of variables of linear constraint
dualvardual variable associated to linear constraint
takelhswhether to consider the lhs or the rhs of the constraint
naddconssbuffer 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 SCIP_RETCODE createKKTComplementarityBounds ( SCIP scip,
SCIP_VAR var,
SCIP_VAR dualvar,
SCIP_Bool  takelb,
int *  naddconss 
)
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
scipSCIP pointer
varvariable
dualvardual variable associated to bound of variable
takelbwhether to consider the lower or upper bound of variable
naddconssbuffer 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 SCIP_RETCODE createKKTComplementarityBinary ( SCIP scip,
SCIP_VAR var,
SCIP_VAR dualbin1,
SCIP_VAR dualbin2,
int *  naddconss 
)
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
scipSCIP pointer
varvariable
dualbin1first dual variable associated to binary variable
dualbin2second dual variable associated to binary variable
naddconssbuffer 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 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

create/get dual constraint of KKT conditions associated to primal variable

if variable does not already exist in hashmap then

  1. create dual constraint for variable
  2. create a dual variable \(\mu_i\) for the upper bound constraint \(x_i \leq u_i\)
  3. create a dual variable \(\lambda_i\) for the lower bound constraint \(x_i \geq l_i\)
  4. create the complementarity constraint \(\mu_i \cdot s_i = 0\), where \(s_i = u_i - x_i\)
  5. create the complementarity constraint \(\lambda_i \cdot w_i = 0\), where \(w_i = x_i - l_i\)
  6. add objective coefficients of dual variables
  7. 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
scipSCIP pointer
objconsobjective constraint
varvariable
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
dualconsdual constraint associated to variable
naddconssbuffer 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 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

handle (a single) linear constraint for quadratic constraint update

  1. 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
  2. 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
  3. create the dual variable \(\mu_i\) associated to this linear constraint
  4. create the complementarity constraint \(\mu_i \cdot (Ax - b)_i = 0\) associated to this linear constraint
  5. 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
scipSCIP pointer
objconsobjective constraint
namepartname of linear constraint
varsvariables of linear constraint
valscoefficients of variables in linear constraint
lhsleft hand side of linear constraint
rhsright hand side of linear constraint
nvarsnumber of variables of linear constraint
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer 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 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

handle linear constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation

Parameters
scipSCIP pointer
objconsobjective constraint
savelinconsscopy of array with linear constraints
nlinconssnumber of linear constraints
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer to increase with number of created additional constraints
ndelconssbuffer 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 SCIP_RETCODE presolveAddKKTKnapsackConss ( SCIP scip,
SCIP_CONS objcons,
SCIP_HASHMAP varhash,
SCIP_CONS **  dualconss,
int *  ndualconss,
int *  naddconss,
int *  ndelconss 
)
static

handle knapsack constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation

Parameters
scipSCIP pointer
objconsobjective constraint
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer to increase with number of created additional constraints
ndelconssbuffer 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 SCIP_RETCODE presolveAddKKTSetppcConss ( SCIP scip,
SCIP_CONS objcons,
SCIP_HASHMAP varhash,
SCIP_CONS **  dualconss,
int *  ndualconss,
int *  naddconss,
int *  ndelconss 
)
static

handle set packing constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation

Parameters
scipSCIP pointer
objconsobjective constraint
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer to increase with number of created additional constraints
ndelconssbuffer 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 SCIP_RETCODE presolveAddKKTVarboundConss ( SCIP scip,
SCIP_CONS objcons,
SCIP_HASHMAP varhash,
SCIP_CONS **  dualconss,
int *  ndualconss,
int *  naddconss,
int *  ndelconss 
)
static

handle varbound constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation

Parameters
scipSCIP pointer
objconsobjective constraint
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer to increase with number of created additional constraints
ndelconssbuffer 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 SCIP_RETCODE presolveAddKKTLogicorConss ( SCIP scip,
SCIP_CONS objcons,
SCIP_HASHMAP varhash,
SCIP_CONS **  dualconss,
int *  ndualconss,
int *  naddconss,
int *  ndelconss 
)
static

handle logicor constraints for quadratic constraint update, see the documentation of the function presolveAddKKTLinearCons() for an explanation

Parameters
scipSCIP pointer
objconsobjective constraint
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer to increase with number of created additional constraints
ndelconssbuffer 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 SCIP_RETCODE presolveAddKKTAggregatedVars ( SCIP scip,
SCIP_CONS objcons,
SCIP_VAR **  agrvars,
int  nagrvars,
SCIP_HASHMAP varhash,
SCIP_CONS **  dualconss,
int *  ndualconss,
int *  naddconss 
)
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
scipSCIP pointer
objconsobjective constraint
agrvarsaggregated variables
nagrvarsnumber of aggregated variables
varhashhash map from variable to index of linear constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer 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 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

handle bilinear terms of quadratic constraint for quadratic constraint update

For the two variables of each bilinear term

  1. 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
  2. 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
  3. 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
scipSCIP pointer
objconsobjective constraint
quadexprquadratic expression
varhashhash map from variable to index of linear constraint
scalescale factor of quadratic constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer 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 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

handle quadratic terms of quadratic constraint for quadratic constraint update

For each quadratic term variable

  1. create the dual constraint (i.e., a row of \(Q x + c + A^T \mu = 0\)) associated to this variable, if not done already
  2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this variable, if not done already
  3. 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
scipSCIP pointer
objconsobjective constraint
quadexprquadratic expression
varhashhash map from variable to index of linear constraint
scalescale factor of quadratic constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer 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 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

handle linear terms of quadratic constraint for quadratic constraint update

For each linear term variable

  1. create the dual constraint (i.e., a row of \(Q x + c + A^T \mu = 0\)) associated to this variable, if not done already
  2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this variable, if not done already
  3. add the right hand side \(-c_i\) to the dual constraint
  4. 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
scipSCIP pointer
objconsobjective constraint
quadexprquadratic expression
varhashhash map from variable to index of linear constraint
objvarvariable of objective function
scalescale factor of quadratic constraint
dualconssarray with dual constraints
ndualconsspointer to store number of dual constraints
naddconssbuffer 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 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

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

  1. there is a single quadratic constraint that can be written as \(x^T Q x + c^T x + d \leq z\)
  2. all other constraints are linear
  3. all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
  4. z is the only variable in the objective and doesn't appear in any other constraint
Parameters
scipSCIP data structure
consnonlinear constraint
quadexprquadratic expression
allowbinaryif TRUE then allow binary variables in the problem, if FALSE then all variables have to be continuous
objvarpointer to store the objective variable z
scalepointer to store the value by which we have to scale the quadratic constraint such that the objective variable z has coefficient -1
objrhspointer to store the right hand side -d of the objective constraint
isqppointer 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 SCIP_DECL_PRESOLCOPY ( presolCopyQPKKTref  )
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 SCIP_DECL_PRESOLFREE ( presolFreeQPKKTref  )
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 SCIP_DECL_PRESOLEXEC ( presolExecQPKKTref  )
static

execution method of presolver

Definition at line 1825 of file presol_qpkktref.c.