presol_qpkktref.c File Reference

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 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 104 of file presol_qpkktref.c.

Referenced by SCIPincludePresolQPKKTref().

PRESOL_DESC

#define PRESOL_DESC   "adds KKT conditions to (mixed-binary) quadratic programs"

Definition at line 105 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 106 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 109 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 112 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

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

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

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

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

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

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

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

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

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

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

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 1115 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_BILINTERM *  bilinterms, int  nbilinterms, 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

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

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

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

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

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

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 t\)
2. all other constraints are linear
3. all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
4. 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 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 1528 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 SCIP_DECL_PRESOLCOPY ( presolCopyQPKKTref  )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 1750 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 1765 of file presol_qpkktref.c.

SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecQPKKTref  )

static

execution method of presolver

Definition at line 1782 of file presol_qpkktref.c.