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

◆ PRESOL_DESC

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

Definition at line 114 of file presol_qpkktref.c.

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY -1

priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators

Definition at line 116 of file presol_qpkktref.c.

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

◆ PRESOL_TIMING

#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */

Definition at line 119 of file presol_qpkktref.c.

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

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

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

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

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

References createKKTComplementarityBinary(), createKKTComplementarityBounds(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddVar(), SCIPcreateConsBasicLinear(), SCIPcreateVarBasic(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPinfinity(), SCIPisInfinity(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and TRUE.

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

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

References createKKTComplementarityLinear(), createKKTDualCons(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddVar(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPreleaseVar(), SCIPsnprintf(), and TRUE.

Referenced by 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 696 of file presol_qpkktref.c.

References NULL, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPdelCons(), SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), and SCIPisFeasEQ().

Referenced by SCIP_DECL_PRESOLEXEC().

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

References NULL, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack(), SCIPgetWeightsKnapsack(), and SCIPinfinity().

Referenced by SCIP_DECL_PRESOLEXEC().

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

References NULL, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), and SCIPinfinity().

Referenced by SCIP_DECL_PRESOLEXEC().

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

References NULL, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), and SCIPisFeasEQ().

Referenced by SCIP_DECL_PRESOLEXEC().

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

References NULL, presolveAddKKTLinearCons(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdelCons(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNVarsLogicor(), SCIPgetVarsLogicor(), and SCIPinfinity().

Referenced by SCIP_DECL_PRESOLEXEC().

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

References NULL, presolveAddKKTLinearCons(), scalars, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArrayNull, SCIPisFeasEQ(), SCIPisFeasZero(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetLbGlobal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetName(), SCIPvarGetNegationConstant(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), and SCIPvarGetUbGlobal().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ 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

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

References createKKTDualCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisFeasZero(), and SCIPswapPointers().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ 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

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

References createKKTDualCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetVarExprVar(), SCIPisExprVar(), and SCIPisFeasZero().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ 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

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

References createKKTDualCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetLhsLinear(), SCIPgetRhsLinear(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisExprVar(), and SCIPisFeasZero().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ 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

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

References FALSE, NULL, REALABS, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetNConss(), SCIPexprGetQuadraticData(), SCIPfindConshdlr(), SCIPgetLhsNonlinear(), SCIPgetLinvarMayIncreaseNonlinear(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNIntVars(), SCIPgetNObjVars(), SCIPgetRhsNonlinear(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbOriginal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetOrigvarSum(), SCIPvarGetUbOriginal(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyQPKKTref )

static

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

Definition at line 1791 of file presol_qpkktref.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolQPKKTref(), and SCIPpresolGetName().

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeQPKKTref )

static

destructor of presolver to free user data (called when SCIP is exiting)

Definition at line 1806 of file presol_qpkktref.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().

◆ SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecQPKKTref )

static

execution method of presolver

Definition at line 1823 of file presol_qpkktref.c.

References checkConsQuadraticProblem(), FALSE, NULL, presolveAddKKTAggregatedVars(), presolveAddKKTKnapsackConss(), presolveAddKKTLinearConss(), presolveAddKKTLogicorConss(), presolveAddKKTQuadBilinearTerms(), presolveAddKKTQuadLinearTerms(), presolveAddKKTQuadQuadraticTerms(), presolveAddKKTSetppcConss(), presolveAddKKTVarboundConss(), SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPallocBufferArray, SCIPblkmem(), SCIPcheckQuadraticNonlinear(), SCIPcomputeExprQuadraticCurvature(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateConsBasicLinear(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetConsNVars(), SCIPgetConsVars(), SCIPgetExprNonlinear(), SCIPgetFixedVars(), SCIPgetNBinVars(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPpresolGetData(), SCIPreleaseCons(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PRESOL_NAME

◆ PRESOL_DESC

◆ PRESOL_PRIORITY

◆ PRESOL_MAXROUNDS

◆ PRESOL_TIMING

Function Documentation

◆ createKKTComplementarityLinear()

◆ createKKTComplementarityBounds()

◆ createKKTComplementarityBinary()

◆ createKKTDualCons()

◆ presolveAddKKTLinearCons()

◆ presolveAddKKTLinearConss()

◆ presolveAddKKTKnapsackConss()

◆ presolveAddKKTSetppcConss()

◆ presolveAddKKTVarboundConss()

◆ presolveAddKKTLogicorConss()

◆ presolveAddKKTAggregatedVars()

◆ presolveAddKKTQuadBilinearTerms()

◆ presolveAddKKTQuadQuadraticTerms()

◆ presolveAddKKTQuadLinearTerms()

◆ checkConsQuadraticProblem()

◆ SCIP_DECL_PRESOLCOPY()

◆ SCIP_DECL_PRESOLFREE()

◆ SCIP_DECL_PRESOLEXEC()