# SCIP

Solving Constraint Integer Programs

presol_qpkktref.c File Reference

## Detailed Description

qpkktref presolver

This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic program

$\begin{array}{ll} \min & x^T Q x + c^T x + d \\ & A x \leq b, \\ & x \in \{0, 1\}^{p} \times R^{n-p}. \end{array}$

We first check if the structure of the program is like (QP), see the documentation of the function checkConsQuadraticProblem().

If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT conditions. For a continuous QPs the KKT conditions have the form

$\begin{array}{ll} Q x + c + A^T \mu = 0,\\ Ax \leq b,\\ \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\ \mu \geq 0. \end{array}$

where $$\mu$$ are the Lagrangian variables. Each of the complementarity constraints $$\mu_i \cdot (Ax - b)_i = 0$$ is enforced via an SOS1 constraint for $$\mu_i$$ and an additional slack variable $$s_i = (Ax - b)_i$$.

For mixed-binary QPs, the KKT-like conditions are

$\begin{array}{ll} Q x + c + A^T \mu + I_J \lambda = 0,\\ Ax \leq b,\\ x_j \in \{0,1\} & j \in J,\\ (1 - x_j) \cdot z_j = 0 & j \in J,\\ x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\ \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\ \mu \geq 0, \end{array}$

where $$J = \{1,\dots, p\}$$, $$\mu$$ and $$\lambda$$ are the Lagrangian variables, and $$I_J$$ is the submatrix of the $$n\times n$$ identity matrix with columns indexed by $$J$$. For the derivation of the KKT-like conditions, see

Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,
Tobias Fischer, PhD Thesis (2016)

Algorithmically:

we 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_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 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)

## ◆ PRESOL_NAME

 #define PRESOL_NAME   "qpkktref"

Definition at line 104 of file presol_qpkktref.c.

Referenced by SCIPincludePresolQPKKTref().

## ◆ PRESOL_DESC

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().

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

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

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.

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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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

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.

static

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.

 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

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

Definition at line 1407 of file presol_qpkktref.c.

 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.

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

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