Scippy

    SCIP

    Solving Constraint Integer Programs

    presol_qpkktref.c
    Go to the documentation of this file.
    1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    2/* */
    3/* This file is part of the program and library */
    4/* SCIP --- Solving Constraint Integer Programs */
    5/* */
    6/* Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB) */
    7/* */
    8/* Licensed under the Apache License, Version 2.0 (the "License"); */
    9/* you may not use this file except in compliance with the License. */
    10/* You may obtain a copy of the License at */
    11/* */
    12/* http://www.apache.org/licenses/LICENSE-2.0 */
    13/* */
    14/* Unless required by applicable law or agreed to in writing, software */
    15/* distributed under the License is distributed on an "AS IS" BASIS, */
    16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
    17/* See the License for the specific language governing permissions and */
    18/* limitations under the License. */
    19/* */
    20/* You should have received a copy of the Apache-2.0 license */
    21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
    22/* */
    23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    24
    25/**@file presol_qpkktref.c
    26 * @ingroup DEFPLUGINS_PRESOL
    27 * @brief qpkktref presolver
    28 * @author Tobias Fischer
    29 *
    30 * This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic
    31 * program
    32 * \f[
    33 * \begin{array}{ll}
    34 * \min & x^T Q x + c^T x + d \\
    35 * & A x \leq b, \\
    36 * & x \in \{0, 1\}^{p} \times R^{n-p}.
    37 * \end{array}
    38 * \f]
    39 *
    40 * We first check if the structure of the program is like (QP), see the documentation of the function
    41 * checkConsQuadraticProblem().
    42 *
    43 * If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT
    44 * conditions. For a continuous QPs the KKT conditions have the form
    45 * \f[
    46 * \begin{array}{ll}
    47 * Q x + c + A^T \mu = 0,\\
    48 * Ax \leq b,\\
    49 * \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\
    50 * \mu \geq 0.
    51 * \end{array}
    52 * \f]
    53 * where \f$\mu\f$ are the Lagrangian variables. Each of the complementarity constraints \f$\mu_i \cdot (Ax - b)_i = 0\f$
    54 * is enforced via an SOS1 constraint for \f$\mu_i\f$ and an additional slack variable \f$s_i = (Ax - b)_i\f$.
    55 *
    56 * For mixed-binary QPs, the KKT-like conditions are
    57 * \f[
    58 * \begin{array}{ll}
    59 * Q x + c + A^T \mu + I_J \lambda = 0,\\
    60 * Ax \leq b,\\
    61 * x_j \in \{0,1\} & j \in J,\\
    62 * (1 - x_j) \cdot z_j = 0 & j \in J,\\
    63 * x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\
    64 * \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\
    65 * \mu \geq 0,
    66 * \end{array}
    67 * \f]
    68 * where \f$J = \{1,\dots, p\}\f$, \f$\mu\f$ and \f$\lambda\f$ are the Lagrangian variables, and \f$I_J\f$ is the
    69 * submatrix of the \f$n\times n\f$ identity matrix with columns indexed by \f$J\f$. For the derivation of the KKT-like
    70 * conditions, see
    71 *
    72 * Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,@n
    73 * Tobias Fischer, PhD Thesis (2016)
    74 *
    75 * Algorithmically:
    76 *
    77 * - we handle the quadratic term variables of the quadratic constraint like in the method
    78 * presolveAddKKTQuadQuadraticTerms()
    79 * - we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms()
    80 * - we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms()
    81 * - we handle linear constraints in the method presolveAddKKTLinearConss()
    82 * - we handle aggregated variables in the method presolveAddKKTAggregatedVars()
    83 *
    84 * we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.
    85 */
    86
    87/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    88
    89#include "blockmemshell/memory.h"
    90#include "scip/cons_nonlinear.h"
    91#include "scip/cons_knapsack.h"
    92#include "scip/cons_linear.h"
    93#include "scip/cons_logicor.h"
    94#include "scip/cons_setppc.h"
    95#include "scip/cons_sos1.h"
    96#include "scip/cons_varbound.h"
    97#include "scip/presol_qpkktref.h"
    98#include "scip/pub_cons.h"
    99#include "scip/pub_message.h"
    100#include "scip/pub_misc.h"
    101#include "scip/pub_presol.h"
    102#include "scip/pub_var.h"
    103#include "scip/scip_cons.h"
    104#include "scip/scip_mem.h"
    105#include "scip/scip_message.h"
    106#include "scip/scip_numerics.h"
    107#include "scip/scip_param.h"
    108#include "scip/scip_presol.h"
    109#include "scip/scip_prob.h"
    110#include "scip/scip_var.h"
    111#include <string.h>
    112
    113#define PRESOL_NAME "qpkktref"
    114#define PRESOL_DESC "adds KKT conditions to (mixed-binary) quadratic programs"
    115#define PRESOL_PRIORITY -1 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers);
    116 * combined with propagators */
    117#define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no
    118 * limit) */
    119#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
    120
    121
    122/*
    123 * Data structures
    124 */
    125
    126/** presolver data */
    127struct SCIP_PresolData
    128{
    129 SCIP_Bool addkktbinary; /**< if TRUE then allow binary variables for KKT update */
    130 SCIP_Bool updatequadbounded; /**< if TRUE then only apply the update to QPs with bounded variables; if
    131 * the variables are not bounded then a finite optimal solution might not
    132 * exist and the KKT conditions would then be invalid */
    133 SCIP_Bool updatequadindef; /**< if TRUE then apply quadratic constraint update even if the quadratic
    134 * constraint matrix is known to be indefinite */
    135};
    136
    137
    138/*
    139 * Local methods
    140 */
    141
    142/** for a linear constraint \f$a^T x \leq b\f$, create the complementarity constraint \f$\mu \cdot s = 0\f$, where
    143 * \f$s = b - a^T x\f$ and \f$\mu\f$ is the dual variable associated to the constraint \f$a^T x \leq b\f$
    144 */
    145static
    146SCIP_RETCODE createKKTComplementarityLinear(
    147 SCIP* scip, /**< SCIP pointer */
    148 const char* namepart, /**< name of linear constraint */
    149 SCIP_VAR** vars, /**< variables of linear constraint */
    150 SCIP_Real* vals, /**< coefficients of variables in linear constraint */
    151 SCIP_Real lhs, /**< left hand side of linear constraint */
    152 SCIP_Real rhs, /**< right hand side of linear constraint */
    153 int nvars, /**< number of variables of linear constraint */
    154 SCIP_VAR* dualvar, /**< dual variable associated to linear constraint */
    155 SCIP_Bool takelhs, /**< whether to consider the lhs or the rhs of the constraint */
    156 int* naddconss /**< buffer to increase with number of created additional constraints */
    157 )
    158{
    159 char name[SCIP_MAXSTRLEN];
    160 SCIP_CONS* KKTlincons;
    161 SCIP_CONS* sos1cons;
    162 SCIP_VAR* slack;
    163 SCIP_Real slackcoef;
    164 SCIP_Real eqval;
    165
    166 assert( scip != NULL );
    167 assert( namepart != NULL );
    168 assert( vars != NULL );
    169 assert( vals != NULL );
    170 assert( dualvar != NULL );
    171 assert( ! takelhs || ! SCIPisInfinity(scip, -lhs) );
    172 assert( takelhs || ! SCIPisInfinity(scip, rhs) );
    173 assert( naddconss != NULL );
    174
    175 if( takelhs )
    176 {
    177 eqval = lhs;
    178 slackcoef = -1.0;
    179 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_lhs_%s", namepart);
    180 }
    181 else
    182 {
    183 eqval = rhs;
    184 slackcoef = 1.0;
    185 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_rhs_%s", namepart);
    186 }
    187
    188 /* create slack variable */
    189 SCIP_CALL( SCIPcreateVarBasic(scip, &slack, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
    190
    191 /* add skack variable */
    192 SCIP_CALL( SCIPaddVar(scip, slack) );
    193
    194 /* create a new linear constraint */
    195 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTlin_%s_%d", namepart, takelhs);
    196 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &KKTlincons, name, nvars, vars, vals, eqval, eqval) );
    197
    198 /* add slack variable to linear constraint */
    199 SCIP_CALL( SCIPaddCoefLinear(scip, KKTlincons, slack, slackcoef) );
    200
    201 /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
    202 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_lin_%s_%d", namepart, takelhs);
    203 SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons, name, 0, NULL, NULL) );
    204
    205 /* add slack and dual variable to SOS1 constraint */
    206 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, slack, 1.0) );
    207 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, dualvar, 2.0) );
    208
    209 /* add/release constraints */
    210 SCIP_CALL( SCIPaddCons(scip, sos1cons) );
    211 SCIP_CALL( SCIPaddCons(scip, KKTlincons) );
    212 SCIP_CALL( SCIPreleaseCons(scip, &sos1cons) );
    213 SCIP_CALL( SCIPreleaseCons(scip, &KKTlincons) );
    214 *naddconss = *naddconss + 2;
    215
    216 /* release slack variable */
    217 SCIP_CALL( SCIPreleaseVar(scip, &slack) );
    218
    219 return SCIP_OKAY;
    220}
    221
    222/** create complementarity constraints of KKT conditions associated to bounds of variables
    223 * - for an upper bound constraint \f$x_i \leq u_i\f$, create the complementarity constraint \f$\mu_i \cdot s_i = 0\f$,
    224 * where \f$s_i = u_i - x_i\f$ and \f$\mu_i\f$ is the dual variable of the upper bound constraint
    225 * - for a lower bound constraint \f$x_i \geq l_i\f$, create the complementarity constraint \f$\lambda_i \cdot w_i = 0\f$,
    226 * where \f$w_i = x_i - l_i\f$
    227 * and \f$\lambda_i\f$ is the dual variable of the lower bound constraint
    228 */
    229static
    230SCIP_RETCODE createKKTComplementarityBounds(
    231 SCIP* scip, /**< SCIP pointer */
    232 SCIP_VAR* var, /**< variable */
    233 SCIP_VAR* dualvar, /**< dual variable associated to bound of variable */
    234 SCIP_Bool takelb, /**< whether to consider the lower or upper bound of variable */
    235 int* naddconss /**< buffer to increase with number of created additional constraints */
    236 )
    237{
    238 char name[SCIP_MAXSTRLEN];
    239 SCIP_CONS* KKTlincons;
    240 SCIP_CONS* sos1cons;
    241 SCIP_VAR* slack;
    242 SCIP_Real slackcoef;
    243 SCIP_Real eqval;
    244
    245 assert( scip != NULL );
    246 assert( var != NULL );
    247 assert( dualvar != NULL );
    248 assert( ! takelb || ! SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) );
    249 assert( takelb || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
    250 assert( naddconss != NULL );
    251
    252 if( takelb )
    253 {
    254 eqval = SCIPvarGetLbGlobal(var);
    255 slackcoef = -1.0;
    256 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_lb_%s", SCIPvarGetName(var));
    257 }
    258 else
    259 {
    260 eqval = SCIPvarGetUbGlobal(var);
    261 slackcoef = 1.0;
    262 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "slack_ub_%s", SCIPvarGetName(var));
    263 }
    264
    265 /* create complementarity constraint; if bound is nonzero, we additionally need to introduce a slack variable */
    266 if( SCIPisFeasZero(scip, eqval) && SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR )
    267 {
    268 /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
    269 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bound%s_%d", SCIPvarGetName(var), takelb);
    270 SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons, name, 0, NULL, NULL) );
    271
    272 /* add slack and dual variable to SOS1 constraint */
    273 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, var, 1.0) );
    274 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, dualvar, 2.0) );
    275
    276 /* add/release constraint */
    277 SCIP_CALL( SCIPaddCons(scip, sos1cons) );
    278 SCIP_CALL( SCIPreleaseCons(scip, &sos1cons) );
    279 ++(*naddconss);
    280 }
    281 else
    282 {
    283 /* create slack variable */
    284 SCIP_CALL( SCIPcreateVarBasic(scip, &slack, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
    285
    286 /* add skack variable */
    287 SCIP_CALL( SCIPaddVar(scip, slack) );
    288
    289 /* create a new linear constraint */
    290 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKT_bound%s_%d", SCIPvarGetName(var), takelb);
    291 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &KKTlincons, name, 0, NULL, NULL, eqval, eqval) );
    292
    293 /* add slack variable to linear constraint */
    294 SCIP_CALL( SCIPaddCoefLinear(scip, KKTlincons, var, 1.0) );
    295 SCIP_CALL( SCIPaddCoefLinear(scip, KKTlincons, slack, slackcoef) );
    296
    297 /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
    298 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bound%s_%d", SCIPvarGetName(var), takelb);
    299 SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons, name, 0, NULL, NULL) );
    300
    301 /* add slack and dual variable to SOS1 constraint */
    302 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, slack, 1.0) );
    303 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons, dualvar, 2.0) );
    304
    305 /* add/release constraints */
    306 SCIP_CALL( SCIPaddCons(scip, sos1cons) );
    307 SCIP_CALL( SCIPaddCons(scip, KKTlincons) );
    308 SCIP_CALL( SCIPreleaseCons(scip, &sos1cons) );
    309 SCIP_CALL( SCIPreleaseCons(scip, &KKTlincons) );
    310 *naddconss = *naddconss + 2;
    311
    312 /* release slack variable */
    313 SCIP_CALL( SCIPreleaseVar(scip, &slack) );
    314 }
    315
    316 return SCIP_OKAY;
    317}
    318
    319/** create the complementarity constraints of the KKT-like conditions associated to a binary variable \f$x_i\f$;
    320 * these are \f$(1 - x_i) \cdot z_i = 0\f$ and \f$x_i \cdot (z_i - \lambda_i) = 0\f$, where \f$z_i\f$ and
    321 * \f$\lambda_i\f$ are dual variables
    322 */
    323static
    324SCIP_RETCODE createKKTComplementarityBinary(
    325 SCIP* scip, /**< SCIP pointer */
    326 SCIP_VAR* var, /**< variable */
    327 SCIP_VAR* dualbin1, /**< first dual variable associated to binary variable */
    328 SCIP_VAR* dualbin2, /**< second dual variable associated to binary variable */
    329 int* naddconss /**< buffer to increase with number of created additional constraints */
    330 )
    331{
    332 char name[SCIP_MAXSTRLEN];
    333 SCIP_CONS* conslinbin1;
    334 SCIP_CONS* conslinbin2;
    335 SCIP_CONS* sos1cons1;
    336 SCIP_CONS* sos1cons2;
    337 SCIP_VAR* slackbin1;
    338 SCIP_VAR* slackbin2;
    339
    340 assert( scip != NULL );
    341 assert( var != NULL );
    342 assert( dualbin1 != NULL );
    343 assert( dualbin2 != NULL );
    344 assert( naddconss != NULL );
    345
    346 /* create first slack variable associated to binary constraint; domain [-inf, inf] */
    347 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_slackbin1", SCIPvarGetName(var));
    348 SCIP_CALL( SCIPcreateVarBasic(scip, &slackbin1, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
    349 SCIP_VARTYPE_CONTINUOUS) );
    350 SCIP_CALL( SCIPaddVar(scip, slackbin1) );
    351 assert( slackbin1 != NULL );
    352
    353 /* create a new linear constraint: dualbin1 - dualbin2 = slackbin */
    354 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTBinary1_%s", SCIPvarGetName(var));
    355 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &conslinbin1, name, 0, NULL, NULL, 0.0, 0.0) );
    356 SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin1, dualbin1, 1.0) );
    357 SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin1, dualbin2, -1.0) );
    358 SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin1, slackbin1, -1.0) );
    359 SCIP_CALL( SCIPaddCons(scip, conslinbin1) );
    360 SCIP_CALL( SCIPreleaseCons(scip, &conslinbin1) );
    361 ++(*naddconss);
    362
    363 /* create SOS1 (complementarity) constraint involving binary variable and slack variable */
    364 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bin1%s", SCIPvarGetName(var));
    365 SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons1, name, 0, NULL, NULL) );
    366
    367 /* add slack and dual variable to SOS1 constraint */
    368 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons1, var, 1.0) );
    369 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons1, slackbin1, 2.0) );
    370
    371 /* add/release constraint */
    372 SCIP_CALL( SCIPaddCons(scip, sos1cons1) );
    373 SCIP_CALL( SCIPreleaseCons(scip, &sos1cons1) );
    374 ++(*naddconss);
    375
    376 /* release slack variable */
    377 SCIP_CALL( SCIPreleaseVar(scip, &slackbin1) );
    378
    379 /* create second slack variable associated to binary constraint; domain [0, inf] */
    380 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_slackbin2", SCIPvarGetName(var));
    381 SCIP_CALL( SCIPcreateVarBasic(scip, &slackbin2, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
    382 SCIP_CALL( SCIPaddVar(scip, slackbin2) );
    383 assert( slackbin2 != NULL );
    384
    385 /* create a new linear constraint: 1.0 - var = slackbin2 */
    386 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTBinary2_%s", SCIPvarGetName(var));
    387 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &conslinbin2, name, 0, NULL, NULL, 1.0, 1.0) );
    388 SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin2, var, 1.0) );
    389 SCIP_CALL( SCIPaddCoefLinear(scip, conslinbin2, slackbin2, 1.0) );
    390 SCIP_CALL( SCIPaddCons(scip, conslinbin2) );
    391 SCIP_CALL( SCIPreleaseCons(scip, &conslinbin2) );
    392 ++(*naddconss);
    393
    394 /* create SOS1 (complementarity) constraint involving first dual variable and slack variable */
    395 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTsos1_bin2%s", SCIPvarGetName(var));
    396 SCIP_CALL( SCIPcreateConsBasicSOS1(scip, &sos1cons2, name, 0, NULL, NULL) );
    397
    398 /* add slack and dual variable to SOS1 constraint */
    399 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons2, dualbin1, 1.0) );
    400 SCIP_CALL( SCIPaddVarSOS1(scip, sos1cons2, slackbin2, 2.0) );
    401
    402 /* add/release constraint */
    403 SCIP_CALL( SCIPaddCons(scip, sos1cons2) );
    404 SCIP_CALL( SCIPreleaseCons(scip, &sos1cons2) );
    405 ++(*naddconss);
    406
    407 /* release slack variable */
    408 SCIP_CALL( SCIPreleaseVar(scip, &slackbin2) );
    409
    410 return SCIP_OKAY;
    411}
    412
    413/** create/get dual constraint of KKT conditions associated to primal variable @n@n
    414 * if variable does not already exist in hashmap then
    415 * 1. create dual constraint for variable
    416 * 2. create a dual variable \f$\mu_i\f$ for the upper bound constraint \f$x_i \leq u_i\f$
    417 * 3. create a dual variable \f$\lambda_i\f$ for the lower bound constraint \f$x_i \geq l_i\f$
    418 * 4. create the complementarity constraint \f$\mu_i \cdot s_i = 0\f$, where \f$s_i = u_i - x_i\f$
    419 * 5. create the complementarity constraint \f$\lambda_i \cdot w_i = 0\f$, where \f$w_i = x_i - l_i\f$
    420 * 6. add objective coefficients of dual variables
    421 * 7. the treatment of binary variables needs special care see the documentation of createKKTComplementarityBinary()
    422 *
    423 * if variable exists in hasmap then the dual constraint associated to the variable has already been created and is returned
    424 */
    425static
    426SCIP_RETCODE createKKTDualCons(
    427 SCIP* scip, /**< SCIP pointer */
    428 SCIP_CONS* objcons, /**< objective constraint */
    429 SCIP_VAR* var, /**< variable */
    430 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    431 SCIP_CONS** dualconss, /**< array with dual constraints */
    432 int* ndualconss, /**< pointer to store number of dual constraints */
    433 SCIP_CONS** dualcons, /**< dual constraint associated to variable */
    434 int* naddconss /**< buffer to increase with number of created additional constraints */
    435 )
    436{
    437 SCIP_VAR* dualub = NULL; /* dual variable associated to upper bound constraint */
    438 SCIP_VAR* duallb = NULL; /* dual variable associated to lower bound constraint */
    439 SCIP_VAR* dualbin1 = NULL; /* first dual variable associated to binary variable */
    440 SCIP_VAR* dualbin2 = NULL; /* second dual variable associated to binary variable */
    441
    442 assert( scip != NULL );
    443 assert( objcons != NULL );
    444 assert( var != NULL );
    445 assert( varhash != NULL );
    446 assert( dualconss != NULL );
    447 assert( ndualconss != NULL );
    448 assert( naddconss != NULL );
    449
    450 /* if variable exists in hashmap */
    451 if( SCIPhashmapExists(varhash, var) )
    452 {
    453 int ind;
    454 ind = SCIPhashmapGetImageInt(varhash, var);
    455 *dualcons = dualconss[ind];
    456 }
    457 else
    458 {
    459 char name[SCIP_MAXSTRLEN];
    460 SCIP_Real lb;
    461 SCIP_Real ub;
    462
    463 lb = SCIPvarGetLbGlobal(var);
    464 ub = SCIPvarGetUbGlobal(var);
    465
    466 /* create dual variables corresponding to the bounds of the variables; binary variables have to be treated in a
    467 * different way */
    468 if( SCIPvarIsBinary(var) )
    469 {
    470 /* create first dual variable associated to binary constraint; the domain of dualbin is [-inf,inf]; the objective
    471 * coefficient is -0.5 */
    472 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_bin1", SCIPvarGetName(var));
    473 SCIP_CALL( SCIPcreateVarBasic(scip, &dualbin1, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
    474 SCIP_VARTYPE_CONTINUOUS) );
    475 SCIP_CALL( SCIPaddVar(scip, dualbin1) );
    476 assert( dualbin1 != NULL );
    477 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, dualbin1, -0.5) );
    478
    479 /* create second variable associated to binary constraint; the domain of dualbin2 is [-inf,inf]; the objective
    480 * coefficient is zero */
    481 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_bin2", SCIPvarGetName(var));
    482 SCIP_CALL( SCIPcreateVarBasic(scip, &dualbin2, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
    483 SCIP_VARTYPE_CONTINUOUS) );
    484 SCIP_CALL( SCIPaddVar(scip, dualbin2) );
    485 assert( dualbin2 != NULL );
    486 }
    487 else
    488 {
    489 if( ! SCIPisInfinity(scip, -lb) )
    490 {
    491 /* create dual variable associated to lower bound; the domain of duallb is [0,inf] */
    492 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_lb", SCIPvarGetName(var));
    493 SCIP_CALL( SCIPcreateVarBasic(scip, &duallb, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
    494 SCIP_CALL( SCIPaddVar(scip, duallb) );
    495 assert( duallb != NULL );
    496 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallb, 0.5 * lb) );
    497 }
    498
    499 if( ! SCIPisInfinity(scip, ub) )
    500 {
    501 /* create dual variable associated to upper bound; the domain of dualub is [0,inf] */
    502 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_ub", SCIPvarGetName(var));
    503 SCIP_CALL( SCIPcreateVarBasic(scip, &dualub, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
    504 SCIP_CALL( SCIPaddVar(scip, dualub) );
    505 assert( dualub != NULL );
    506 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, dualub, -0.5 * ub) );
    507 }
    508 }
    509
    510 /* add variable in map */
    511 SCIP_CALL( SCIPhashmapInsertInt(varhash, var, (*ndualconss)) );
    512 assert( *ndualconss == SCIPhashmapGetImageInt(varhash, var) );
    513
    514 /* create a new linear constraint */
    515 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "KKTref_%s", SCIPvarGetName(var));
    516 SCIP_CALL( SCIPcreateConsBasicLinear(scip, dualcons, name, 0, NULL, NULL, 0.0, 0.0) );
    517
    518 /* add dual constraint to array for later use */
    519 dualconss[(*ndualconss)++] = *dualcons;
    520
    521 /* add dual variables to dual constraints and create complementarity constraints; binary variables have to be
    522 * treated in a different way */
    523 if( SCIPvarIsBinary(var) )
    524 {
    525 /* add coefficient of second dual variable corresponding to binary variable */
    526 SCIP_CALL( SCIPaddCoefLinear(scip, *dualcons, dualbin2, 1.0) );
    527
    528 /* create complementarity constraints */
    529 SCIP_CALL( createKKTComplementarityBinary(scip, var, dualbin1, dualbin2, naddconss) );
    530
    531 SCIP_CALL( SCIPreleaseVar(scip, &dualbin1) );
    532 SCIP_CALL( SCIPreleaseVar(scip, &dualbin2) );
    533 }
    534 else
    535 {
    536 if( duallb != NULL )
    537 {
    538 /* add dual variable corresponding to lower bound of variable */
    539 SCIP_CALL( SCIPaddCoefLinear(scip, *dualcons, duallb, -1.0) );
    540
    541 /* create complementarity constraint between slack variable of lower bound constraint and dual variable of
    542 * lower bound */
    543 SCIP_CALL( createKKTComplementarityBounds(scip, var, duallb, TRUE, naddconss) );
    544
    545 SCIP_CALL( SCIPreleaseVar(scip, &duallb) );
    546 }
    547
    548 if( dualub != NULL )
    549 {
    550 /* add dual variable corresponding to upper bound of variable */
    551 SCIP_CALL( SCIPaddCoefLinear(scip, *dualcons, dualub, 1.0) );
    552
    553 /* create complementarity constraint between slack variable of upper bound constraint and dual variable of
    554 * upper bound */
    555 SCIP_CALL( createKKTComplementarityBounds(scip, var, dualub, FALSE, naddconss) );
    556
    557 SCIP_CALL( SCIPreleaseVar(scip, &dualub) );
    558 }
    559 }
    560 }
    561 assert( *dualcons != NULL );
    562
    563 return SCIP_OKAY;
    564}
    565
    566/** handle (a single) linear constraint for quadratic constraint update
    567 * 1. create the dual constraints (i.e., the two rows of \f$Q x + c + A^T \mu = 0\f$) associated to the variables of the
    568 * linear constraint, if not done already
    569 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of the
    570 * variables of the linear constraint, if not done already
    571 * 3. create the dual variable \f$\mu_i\f$ associated to this linear constraint
    572 * 4. create the complementarity constraint \f$\mu_i \cdot (Ax - b)_i = 0\f$ associated to this linear constraint
    573 * 5. add objective coefficients of dual variables
    574 *
    575 * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.@n
    576 * for step 4 see the documentation of the function createKKTComplementarityLinear() for further information.
    577 */
    578static
    579SCIP_RETCODE presolveAddKKTLinearCons(
    580 SCIP* scip, /**< SCIP pointer */
    581 SCIP_CONS* objcons, /**< objective constraint */
    582 const char* namepart, /**< name of linear constraint */
    583 SCIP_VAR** vars, /**< variables of linear constraint */
    584 SCIP_Real* vals, /**< coefficients of variables in linear constraint */
    585 SCIP_Real lhs, /**< left hand side of linear constraint */
    586 SCIP_Real rhs, /**< right hand side of linear constraint */
    587 int nvars, /**< number of variables of linear constraint */
    588 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    589 SCIP_CONS** dualconss, /**< array with dual constraints */
    590 int* ndualconss, /**< pointer to store number of dual constraints */
    591 int* naddconss /**< buffer to increase with number of created additional constraints */
    592 )
    593{
    594 int i;
    595
    596 assert( scip != NULL );
    597 assert( objcons != NULL );
    598 assert( namepart != NULL );
    599 assert( varhash != NULL );
    600 assert( dualconss != NULL );
    601 assert( ndualconss != NULL );
    602 assert( vars != NULL );
    603 assert( vals != NULL );
    604 assert( namepart != NULL );
    605 assert( naddconss != NULL );
    606
    607 /* differ between left hand side and right hand side case (i=0 -> lhs; i=1 -> rhs) */
    608 for( i = 0; i < 2; ++i )
    609 {
    610 char name[SCIP_MAXSTRLEN];
    611 SCIP_VAR* duallin = NULL;
    612 int j;
    613
    614 /* skip one iteration if lhs equals rhs */
    615 if( i == 0 && SCIPisFeasEQ(scip, lhs, rhs) )
    616 continue;
    617
    618 /* create dual variable corresponding to linear constraint */
    619 if( i == 0 )
    620 {
    621 assert( ! SCIPisFeasEQ(scip, lhs, rhs) );
    622
    623 if( SCIPisInfinity(scip, -lhs) )
    624 continue;
    625
    626 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_lhs", namepart);
    627 SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
    628 SCIP_CALL( SCIPaddVar(scip, duallin) );
    629 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallin, 0.5 * lhs) );
    630
    631 /* create complementarity constraint between dual variable and slack variable of linear constraint */
    632 SCIP_CALL( createKKTComplementarityLinear(scip, namepart, vars, vals, lhs, rhs, nvars, duallin, TRUE,
    633 naddconss) );
    634 }
    635 else
    636 {
    637 if( SCIPisInfinity(scip, rhs) )
    638 continue;
    639
    640 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dual_%s_rhs", namepart);
    641 if( SCIPisFeasEQ(scip, lhs, rhs) )
    642 {
    643 SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
    644 SCIP_VARTYPE_CONTINUOUS) );
    645 SCIP_CALL( SCIPaddVar(scip, duallin) );
    646 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallin, -0.5 * rhs) );
    647 }
    648 else
    649 {
    650 SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
    651 SCIP_CALL( SCIPaddVar(scip, duallin) );
    652 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, duallin, -0.5 * rhs) );
    653
    654 /* create complementarity constraint between dual variable and slack variable of linear constraint */
    655 SCIP_CALL( createKKTComplementarityLinear(scip, namepart, vars, vals, lhs, rhs, nvars, duallin, FALSE,
    656 naddconss) );
    657 }
    658 }
    659 assert( duallin != NULL );
    660
    661 /* loop through variables of linear constraint */
    662 for( j = 0; j < nvars; ++j )
    663 {
    664 SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
    665 SCIP_VAR* var;
    666
    667 var = vars[j];
    668
    669 /* create/get dual constraint associated to variable;
    670 * if variable does not already exist in hashmap then create dual variables for its bounds */
    671 SCIP_CALL( createKKTDualCons(scip, objcons, var, varhash, dualconss, ndualconss, &dualcons, naddconss) );
    672 assert( dualcons != NULL );
    673
    674 /* add dual variable corresponding to linear constraint */
    675 if( i == 0 )
    676 {
    677 SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, duallin, -vals[j]) );
    678 }
    679 else
    680 {
    681 SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, duallin, vals[j]) );
    682 }
    683 }
    684
    685 /* release dual variable */
    686 SCIP_CALL( SCIPreleaseVar(scip, &duallin) );
    687 }
    688
    689 return SCIP_OKAY;
    690}
    691
    692/** handle linear constraints for quadratic constraint update, see the documentation of the function
    693 * presolveAddKKTLinearCons() for an explanation
    694 */
    695static
    696SCIP_RETCODE presolveAddKKTLinearConss(
    697 SCIP* scip, /**< SCIP pointer */
    698 SCIP_CONS* objcons, /**< objective constraint */
    699 SCIP_CONS** savelinconss, /**< copy of array with linear constraints */
    700 int nlinconss, /**< number of linear constraints */
    701 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    702 SCIP_CONS** dualconss, /**< array with dual constraints */
    703 int* ndualconss, /**< pointer to store number of dual constraints */
    704 int* naddconss, /**< buffer to increase with number of created additional constraints */
    705 int* ndelconss /**< buffer to increase with number of deleted constraints */
    706 )
    707{
    708 int c;
    709
    710 assert( scip != NULL );
    711 assert( objcons != NULL );
    712 assert( varhash != NULL );
    713 assert( dualconss != NULL );
    714 assert( ndualconss != NULL );
    715 assert( naddconss != NULL );
    716 assert( ndelconss != NULL );
    717
    718 /* loop through linear constraints */
    719 for( c = 0; c < nlinconss; ++c )
    720 {
    721 SCIP_CONS* lincons;
    722 SCIP_VAR** vars;
    723 SCIP_Real* vals;
    724 SCIP_Real lhs;
    725 SCIP_Real rhs;
    726 int nvars;
    727
    728 /* get data of constraint */
    729 lincons = savelinconss[c];
    730 assert( lincons != NULL );
    731 lhs = SCIPgetLhsLinear(scip, lincons);
    732 rhs = SCIPgetRhsLinear(scip, lincons);
    733 nvars = SCIPgetNVarsLinear(scip, lincons);
    734 vars = SCIPgetVarsLinear(scip, lincons);
    735 vals = SCIPgetValsLinear(scip, lincons);
    736
    737 /* handle linear constraint for quadratic constraint update */
    738 SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(lincons),
    739 vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
    740 }
    741
    742 /* remove linear constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
    743 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
    744 for( c = nlinconss-1; c >= 0; --c )
    745 {
    746 SCIP_CONS* lincons;
    747
    748 lincons = savelinconss[c];
    749 assert( savelinconss[c] != NULL );
    750
    751 if( ! SCIPisFeasEQ(scip, SCIPgetLhsLinear(scip, lincons), SCIPgetRhsLinear(scip, lincons)) )
    752 {
    753 SCIP_CALL( SCIPdelCons(scip, savelinconss[c]) );
    754 ++(*ndelconss);
    755 }
    756 }
    757
    758 return SCIP_OKAY;
    759}
    760
    761/** handle knapsack constraints for quadratic constraint update, see the documentation of the function
    762 * presolveAddKKTLinearCons() for an explanation
    763 */
    764static
    765SCIP_RETCODE presolveAddKKTKnapsackConss(
    766 SCIP* scip, /**< SCIP pointer */
    767 SCIP_CONS* objcons, /**< objective constraint */
    768 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    769 SCIP_CONS** dualconss, /**< array with dual constraints */
    770 int* ndualconss, /**< pointer to store number of dual constraints */
    771 int* naddconss, /**< buffer to increase with number of created additional constraints */
    772 int* ndelconss /**< buffer to increase with number of deleted constraints */
    773 )
    774{
    775 SCIP_CONSHDLR* conshdlr;
    776 SCIP_CONS** conss;
    777 int nconss;
    778 int c;
    779
    780 assert( scip != NULL );
    781 assert( objcons != NULL );
    782 assert( varhash != NULL );
    783 assert( dualconss != NULL );
    784 assert( ndualconss != NULL );
    785 assert( naddconss != NULL );
    786 assert( ndelconss != NULL );
    787
    788 conshdlr = SCIPfindConshdlr(scip, "knapsack");
    789 if( conshdlr == NULL )
    790 return SCIP_OKAY;
    791
    792 nconss = SCIPconshdlrGetNConss(conshdlr);
    793 conss = SCIPconshdlrGetConss(conshdlr);
    794
    795 /* loop through knapsack constraints */
    796 for( c = 0; c < nconss; ++c )
    797 {
    798 SCIP_CONS* cons;
    799 SCIP_VAR** vars;
    800 SCIP_Longint* weights;
    801 SCIP_Real* vals;
    802 SCIP_Real lhs;
    803 SCIP_Real rhs;
    804 int nvars;
    805 int v;
    806
    807 /* get data of constraint */
    808 cons = conss[c];
    809 assert( cons != NULL );
    810 lhs = -SCIPinfinity(scip);
    811 rhs = (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons);
    812 nvars = SCIPgetNVarsKnapsack(scip, cons);
    813 vars = SCIPgetVarsKnapsack(scip, cons);
    814 weights = SCIPgetWeightsKnapsack(scip, cons);
    815
    816 /* set coefficients of variables */
    817 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
    818 for( v = 0; v < nvars; ++v )
    819 vals[v] = (SCIP_Real) weights[v];
    820
    821 /* handle linear constraint for quadratic constraint update */
    822 SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
    823 vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
    824
    825 /* free buffer array */
    826 SCIPfreeBufferArray(scip, &vals);
    827 }
    828
    829 /* remove knapsack constraints, since they are now redundant; their feasibility is already expressed
    830 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
    831 for( c = nconss-1; c >= 0; --c )
    832 {
    833 assert( conss[c] != NULL );
    834 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
    835 ++(*ndelconss);
    836 }
    837
    838 return SCIP_OKAY;
    839}
    840
    841/** handle set packing constraints for quadratic constraint update, see the documentation of the function
    842 * presolveAddKKTLinearCons() for an explanation
    843 */
    844static
    845SCIP_RETCODE presolveAddKKTSetppcConss(
    846 SCIP* scip, /**< SCIP pointer */
    847 SCIP_CONS* objcons, /**< objective constraint */
    848 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    849 SCIP_CONS** dualconss, /**< array with dual constraints */
    850 int* ndualconss, /**< pointer to store number of dual constraints */
    851 int* naddconss, /**< buffer to increase with number of created additional constraints */
    852 int* ndelconss /**< buffer to increase with number of deleted constraints */
    853 )
    854{
    855 SCIP_CONSHDLR* conshdlr;
    856 SCIP_CONS** conss;
    857 int nconss;
    858 int c;
    859
    860 assert( scip != NULL );
    861 assert( objcons != NULL );
    862 assert( varhash != NULL );
    863 assert( dualconss != NULL );
    864 assert( ndualconss != NULL );
    865 assert( naddconss != NULL );
    866 assert( ndelconss != NULL );
    867
    868 conshdlr = SCIPfindConshdlr(scip, "setppc");
    869 if( conshdlr == NULL )
    870 return SCIP_OKAY;
    871
    872 nconss = SCIPconshdlrGetNConss(conshdlr);
    873 conss = SCIPconshdlrGetConss(conshdlr);
    874
    875 /* loop through linear constraints */
    876 for( c = 0; c < nconss; ++c )
    877 {
    878 SCIP_SETPPCTYPE type;
    879 SCIP_CONS* cons;
    880 SCIP_VAR** vars;
    881 SCIP_Real* vals;
    882 SCIP_Real lhs;
    883 SCIP_Real rhs;
    884 int nvars;
    885 int v;
    886
    887 /* get data of constraint */
    888 cons = conss[c];
    889 assert( cons != NULL );
    890
    891 /* get setppc type */
    892 type = SCIPgetTypeSetppc(scip, cons);
    893 lhs = -SCIPinfinity(scip);
    894 rhs = SCIPinfinity(scip);
    895 switch( type )
    896 {
    897 case SCIP_SETPPCTYPE_PARTITIONING:
    898 lhs = 1.0;
    899 rhs = 1.0;
    900 break;
    901 case SCIP_SETPPCTYPE_PACKING:
    902 rhs = 1.0;
    903 break;
    904 case SCIP_SETPPCTYPE_COVERING:
    905 lhs = 1.0;
    906 break;
    907 default:
    908 SCIPerrorMessage("unknown setppc type\n");
    909 return SCIP_INVALIDDATA;
    910 }
    911
    912 nvars = SCIPgetNVarsSetppc(scip, cons);
    913 vars = SCIPgetVarsSetppc(scip, cons);
    914
    915 /* set coefficients of variables */
    916 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
    917 for( v = 0; v < nvars; ++v )
    918 vals[v] = 1.0;
    919
    920 /* handle linear constraint for quadratic constraint update */
    921 SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
    922 vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
    923
    924 /* free buffer array */
    925 SCIPfreeBufferArray(scip, &vals);
    926 }
    927
    928 /* remove set packing constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
    929 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
    930 for( c = nconss-1; c >= 0; --c )
    931 {
    932 assert( conss[c] != NULL );
    933
    934 if( SCIPgetTypeSetppc(scip, conss[c]) != SCIP_SETPPCTYPE_PARTITIONING )
    935 {
    936 assert( SCIPgetTypeSetppc(scip, conss[c]) == SCIP_SETPPCTYPE_PACKING
    937 || SCIPgetTypeSetppc(scip, conss[c]) == SCIP_SETPPCTYPE_COVERING );
    938
    939 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
    940 ++(*ndelconss);
    941 }
    942 }
    943
    944 return SCIP_OKAY;
    945}
    946
    947/** handle varbound constraints for quadratic constraint update, see the documentation of the function
    948 * presolveAddKKTLinearCons() for an explanation
    949 */
    950static
    951SCIP_RETCODE presolveAddKKTVarboundConss(
    952 SCIP* scip, /**< SCIP pointer */
    953 SCIP_CONS* objcons, /**< objective constraint */
    954 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    955 SCIP_CONS** dualconss, /**< array with dual constraints */
    956 int* ndualconss, /**< pointer to store number of dual constraints */
    957 int* naddconss, /**< buffer to increase with number of created additional constraints */
    958 int* ndelconss /**< buffer to increase with number of deleted constraints */
    959 )
    960{
    961 SCIP_CONSHDLR* conshdlr;
    962 SCIP_CONS** conss;
    963 int nconss;
    964 int c;
    965
    966 assert( scip != NULL );
    967 assert( objcons != NULL );
    968 assert( varhash != NULL );
    969 assert( dualconss != NULL );
    970 assert( ndualconss != NULL );
    971 assert( naddconss != NULL );
    972 assert( ndelconss != NULL );
    973
    974 conshdlr = SCIPfindConshdlr(scip, "varbound");
    975 if( conshdlr == NULL )
    976 return SCIP_OKAY;
    977
    978 nconss = SCIPconshdlrGetNConss(conshdlr);
    979 conss = SCIPconshdlrGetConss(conshdlr);
    980
    981 /* loop through linear constraints */
    982 for( c = 0; c < nconss; ++c )
    983 {
    984 SCIP_CONS* cons;
    985 SCIP_VAR** vars;
    986 SCIP_Real* vals;
    987 SCIP_Real lhs;
    988 SCIP_Real rhs;
    989 int nvars;
    990
    991 /* allocate buffer arrays */
    992 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
    993 SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
    994
    995 /* get data of constraint */
    996 cons = conss[c];
    997 assert( cons != NULL );
    998
    999 lhs = SCIPgetLhsVarbound(scip, cons);
    1000 rhs = SCIPgetRhsVarbound(scip, cons);
    1001 vars[0] = SCIPgetVarVarbound(scip, cons);
    1002 vars[1] = SCIPgetVbdvarVarbound(scip, cons);
    1003 vals[0] = 1.0;
    1004 vals[1] = SCIPgetVbdcoefVarbound(scip, cons);
    1005 nvars = 2;
    1006
    1007 /* handle linear constraint for quadratic constraint update */
    1008 SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
    1009 vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
    1010
    1011 /* free buffer array */
    1012 SCIPfreeBufferArray(scip, &vals);
    1013 SCIPfreeBufferArray(scip, &vars);
    1014 }
    1015
    1016 /* remove varbound constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
    1017 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
    1018 for( c = nconss-1; c >= 0; --c )
    1019 {
    1020 SCIP_CONS* cons;
    1021
    1022 cons = conss[c];
    1023 assert( cons != NULL );
    1024
    1025 if( ! SCIPisFeasEQ(scip, SCIPgetLhsVarbound(scip, cons), SCIPgetRhsVarbound(scip, cons)) )
    1026 {
    1027 SCIP_CALL( SCIPdelCons(scip, cons) );
    1028 ++(*ndelconss);
    1029 }
    1030 }
    1031
    1032 return SCIP_OKAY;
    1033}
    1034
    1035/** handle logicor constraints for quadratic constraint update, see the documentation of the function
    1036 * presolveAddKKTLinearCons() for an explanation
    1037 */
    1038static
    1039SCIP_RETCODE presolveAddKKTLogicorConss(
    1040 SCIP* scip, /**< SCIP pointer */
    1041 SCIP_CONS* objcons, /**< objective constraint */
    1042 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    1043 SCIP_CONS** dualconss, /**< array with dual constraints */
    1044 int* ndualconss, /**< pointer to store number of dual constraints */
    1045 int* naddconss, /**< buffer to increase with number of created additional constraints */
    1046 int* ndelconss /**< buffer to increase with number of deleted constraints */
    1047 )
    1048{
    1049 SCIP_CONSHDLR* conshdlr;
    1050 SCIP_CONS** conss;
    1051 int nconss;
    1052 int c;
    1053
    1054 assert( scip != NULL );
    1055 assert( objcons != NULL );
    1056 assert( varhash != NULL );
    1057 assert( dualconss != NULL );
    1058 assert( ndualconss != NULL );
    1059 assert( naddconss != NULL );
    1060 assert( ndelconss != NULL );
    1061
    1062 conshdlr = SCIPfindConshdlr(scip, "logicor");
    1063 if( conshdlr == NULL )
    1064 return SCIP_OKAY;
    1065
    1066 nconss = SCIPconshdlrGetNConss(conshdlr);
    1067 conss = SCIPconshdlrGetConss(conshdlr);
    1068
    1069 /* loop through linear constraints */
    1070 for( c = 0; c < nconss; ++c )
    1071 {
    1072 SCIP_CONS* cons;
    1073 SCIP_VAR** vars;
    1074 SCIP_Real* vals;
    1075 SCIP_Real lhs;
    1076 SCIP_Real rhs;
    1077 int nvars;
    1078 int v;
    1079
    1080 /* get data of constraint */
    1081 cons = conss[c];
    1082 assert( cons != NULL );
    1083
    1084 /* get setppc type */
    1085 lhs = 1.0;
    1086 rhs = SCIPinfinity(scip);
    1087
    1088 nvars = SCIPgetNVarsLogicor(scip, cons);
    1089 vars = SCIPgetVarsLogicor(scip, cons);
    1090
    1091 /* set coefficients of variables */
    1092 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
    1093 for( v = 0; v < nvars; ++v )
    1094 vals[v] = 1.0;
    1095
    1096 /* handle linear constraint for quadratic constraint update */
    1097 SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPconsGetName(cons),
    1098 vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
    1099
    1100 /* free buffer array */
    1101 SCIPfreeBufferArray(scip, &vals);
    1102 }
    1103
    1104 /* remove logicor constraints, since they are now redundant; their feasibility is already expressed
    1105 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
    1106 for( c = nconss-1; c >= 0; --c )
    1107 {
    1108 assert( conss[c] != NULL );
    1109
    1110 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
    1111 ++(*ndelconss);
    1112 }
    1113
    1114 return SCIP_OKAY;
    1115}
    1116
    1117/** handle aggregated variables for quadratic constraint update @n
    1118 * we apply the function presolveAddKKTLinearCons() to the aggregation constraint, see the documentation of this
    1119 * function for further information
    1120 */
    1121static
    1122SCIP_RETCODE presolveAddKKTAggregatedVars(
    1123 SCIP* scip, /**< SCIP pointer */
    1124 SCIP_CONS* objcons, /**< objective constraint */
    1125 SCIP_VAR** agrvars, /**< aggregated variables */
    1126 int nagrvars, /**< number of aggregated variables */
    1127 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    1128 SCIP_CONS** dualconss, /**< array with dual constraints */
    1129 int* ndualconss, /**< pointer to store number of dual constraints */
    1130 int* naddconss /**< buffer to increase with number of created additional constraints */
    1131 )
    1132{
    1133 int v;
    1134
    1135 assert( scip != NULL );
    1136 assert( objcons != NULL );
    1137 assert( agrvars != NULL );
    1138 assert( varhash != NULL );
    1139 assert( dualconss != NULL );
    1140 assert( ndualconss != NULL );
    1141 assert( naddconss != NULL );
    1142
    1143 /* loop through variables */
    1144 for( v = 0; v < nagrvars; ++v )
    1145 {
    1146 SCIP_VAR* var;
    1147 SCIP_VAR** vars = NULL;
    1148 SCIP_Real* vals = NULL;
    1149 SCIP_Real lhs;
    1150 SCIP_Real rhs;
    1151 int nvars;
    1152
    1153 var = agrvars[v];
    1154
    1155 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED )
    1156 {
    1157 SCIP_Real constant;
    1158
    1159 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
    1160 SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
    1161
    1162 /* get aggregation variable */
    1163 constant = SCIPvarGetAggrConstant(var);
    1164 vars[0] = SCIPvarGetAggrVar(var);
    1165 vals[0] = SCIPvarGetAggrScalar(var);
    1166 vars[1] = var;
    1167 vals[1] = -1.0;
    1168 lhs = -constant;
    1169 rhs = -constant;
    1170 nvars = 2;
    1171 }
    1172 else if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
    1173 {
    1174 SCIP_Real* scalars;
    1175 SCIP_VAR** multvars;
    1176 SCIP_Real constant;
    1177 int nmultvars;
    1178 int nbuffer;
    1179 int j;
    1180
    1181 nmultvars = SCIPvarGetMultaggrNVars(var);
    1182 nbuffer = nmultvars+1;
    1183
    1184 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbuffer) );
    1185 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nbuffer) );
    1186
    1187 /* get aggregation variables */
    1188 multvars = SCIPvarGetMultaggrVars(var);
    1189 scalars = SCIPvarGetMultaggrScalars(var);
    1190 constant = SCIPvarGetMultaggrConstant(var);
    1191
    1192 /* add multi-aggregated variables to array */
    1193 for( j = 0; j < nmultvars; ++j )
    1194 {
    1195 vars[j] = multvars[j];
    1196 vals[j] = scalars[j];
    1197 }
    1198
    1199 /* add new variable to array */
    1200 vars[nmultvars] = var;
    1201 vals[nmultvars] = -1.0;
    1202 lhs = -constant;
    1203 rhs = -constant;
    1204 nvars = nmultvars + 1;
    1205 }
    1206 else if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED )
    1207 {
    1208 SCIP_VAR* negvar;
    1209 SCIP_Real negconst;
    1210
    1211 /* get negation variable and negation offset */
    1212 negvar = SCIPvarGetNegationVar(var);
    1213 negconst = SCIPvarGetNegationConstant(var);
    1214
    1215 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
    1216 SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
    1217
    1218 vars[0] = negvar;
    1219 vars[1] = var;
    1220 vals[0] = 1.0;
    1221 vals[1] = 1.0;
    1222 lhs = negconst;
    1223 rhs = negconst;
    1224 nvars = 2;
    1225 }
    1226 else if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
    1227 {
    1228 SCIP_Real lb;
    1229 SCIP_Real ub;
    1230
    1231 lb = SCIPvarGetLbGlobal(var);
    1232 ub = SCIPvarGetUbGlobal(var);
    1233 assert( SCIPisFeasEQ(scip, lb, ub) );
    1234
    1235 if( SCIPisFeasZero(scip, lb) && SCIPisFeasZero(scip, ub) )
    1236 continue;
    1237 else
    1238 {
    1239 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 1) );
    1240 SCIP_CALL( SCIPallocBufferArray(scip, &vals, 1) );
    1241
    1242 vars[0] = var;
    1243 vals[0] = 1.0;
    1244 lhs = lb;
    1245 rhs = lb;
    1246 nvars = 1;
    1247 }
    1248 }
    1249 else
    1250 {
    1251 SCIPerrorMessage("unexpected variable status\n");
    1252 return SCIP_ERROR;
    1253 }
    1254
    1255 if( nvars > 0 )
    1256 {
    1257 /* handle aggregation constraint for quadratic constraint update */
    1258 SCIP_CALL( presolveAddKKTLinearCons(scip, objcons, SCIPvarGetName(var),
    1259 vars, vals, lhs, rhs, nvars, varhash, dualconss, ndualconss, naddconss) );
    1260 }
    1261
    1262 SCIPfreeBufferArrayNull(scip, &vals);
    1263 SCIPfreeBufferArrayNull(scip, &vars);
    1264 }
    1265
    1266 return SCIP_OKAY;
    1267}
    1268
    1269/** handle bilinear terms of quadratic constraint for quadratic constraint update
    1270 *
    1271 * For the two variables of each bilinear term
    1272 * 1. create the dual constraints (i.e., the two rows of \f$Q x + c + A^T \mu = 0\f$) associated to these variables, if not
    1273 * done already
    1274 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of the two
    1275 * variables of the bilinear term, if not done already
    1276 * 3. add the coefficient \f$Q_{ij}\f$ of the bilinear term to the dual constraint
    1277 *
    1278 * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
    1279 **/
    1280static
    1281SCIP_RETCODE presolveAddKKTQuadBilinearTerms(
    1282 SCIP* scip, /**< SCIP pointer */
    1283 SCIP_CONS* objcons, /**< objective constraint */
    1284 SCIP_EXPR* quadexpr, /**< quadratic expression */
    1285 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    1286 SCIP_Real scale, /**< scale factor of quadratic constraint */
    1287 SCIP_CONS** dualconss, /**< array with dual constraints */
    1288 int* ndualconss, /**< pointer to store number of dual constraints */
    1289 int* naddconss /**< buffer to increase with number of created additional constraints */
    1290 )
    1291{
    1292 int nbilinexprs;
    1293 int j;
    1294
    1295 assert( scip != NULL );
    1296 assert( objcons != NULL );
    1297 assert( quadexpr != NULL );
    1298 assert( varhash != NULL );
    1299 assert( dualconss != NULL );
    1300 assert( ndualconss != NULL );
    1301 assert( naddconss != NULL );
    1302
    1303 /* get the number of bilinear expressions */
    1304 SCIPexprGetQuadraticData(quadexpr, NULL, NULL, NULL, NULL, NULL, &nbilinexprs, NULL, NULL);
    1305
    1306 /* loop through bilinear terms of quadratic constraint */
    1307 for( j = 0; j < nbilinexprs; ++j )
    1308 {
    1309 SCIP_EXPR* expr1;
    1310 SCIP_EXPR* expr2;
    1311 SCIP_VAR* bilvar1;
    1312 SCIP_VAR* bilvar2;
    1313 SCIP_Real coef;
    1314 int i;
    1315
    1316 /* get variables of the bilinear term */
    1317 SCIPexprGetQuadraticBilinTerm(quadexpr, j, &expr1, &expr2, &coef, NULL, NULL);
    1318 assert(expr1 != NULL && SCIPisExprVar(scip, expr1));
    1319 assert(expr2 != NULL && SCIPisExprVar(scip, expr2));
    1320
    1321 bilvar1 = SCIPgetVarExprVar(expr1);
    1322 bilvar2 = SCIPgetVarExprVar(expr2);
    1323 assert(bilvar1 != NULL && bilvar2 != NULL && bilvar1 != bilvar2);
    1324
    1325 /* quadratic matrix has to be symmetric; therefore, split bilinear terms into two parts */
    1326 for( i = 0; i < 2; ++i )
    1327 {
    1328 SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
    1329
    1330 if( i == 1 )
    1331 SCIPswapPointers((void**)&bilvar1, (void**)&bilvar2);
    1332
    1333 /* create/get dual constraint associated to variable 'bilvar1';
    1334 * if variable does not already exist in hashmap then create dual variables for its bounds */
    1335 SCIP_CALL( createKKTDualCons(scip, objcons, bilvar1, varhash, dualconss, ndualconss, &dualcons, naddconss) );
    1336 assert( dualcons != NULL );
    1337
    1338 /* add variable to dual constraint */
    1339 assert( ! SCIPisFeasZero(scip, scale) );
    1340 SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, bilvar2, coef / scale) );
    1341 }
    1342 }
    1343
    1344 return SCIP_OKAY;
    1345}
    1346
    1347/** handle quadratic terms of quadratic constraint for quadratic constraint update
    1348 *
    1349 * For each quadratic term variable
    1350 * 1. create the dual constraint (i.e., a row of \f$Q x + c + A^T \mu = 0\f$) associated to this variable, if not done
    1351 * already
    1352 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
    1353 * variable, if not done already
    1354 * 3. add the coefficient \f$Q_{ii}\f$ of this variable to the dual constraint
    1355 *
    1356 * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
    1357 **/
    1358static
    1359SCIP_RETCODE presolveAddKKTQuadQuadraticTerms(
    1360 SCIP* scip, /**< SCIP pointer */
    1361 SCIP_CONS* objcons, /**< objective constraint */
    1362 SCIP_EXPR* quadexpr, /**< quadratic expression */
    1363 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    1364 SCIP_Real scale, /**< scale factor of quadratic constraint */
    1365 SCIP_CONS** dualconss, /**< array with dual constraints */
    1366 int* ndualconss, /**< pointer to store number of dual constraints */
    1367 int* naddconss /**< buffer to increase with number of created additional constraints */
    1368 )
    1369{
    1370 int nquadexprs;
    1371 int j;
    1372
    1373 assert( scip != NULL );
    1374 assert( objcons != NULL );
    1375 assert( varhash != NULL );
    1376 assert( dualconss != NULL );
    1377 assert( ndualconss != NULL );
    1378 assert( naddconss != NULL );
    1379
    1380 /* get the number of quadratic expressions */
    1381 SCIPexprGetQuadraticData(quadexpr, NULL, NULL, NULL, NULL, &nquadexprs, NULL, NULL, NULL);
    1382
    1383 /* loop through quadratic terms */
    1384 for( j = 0; j < nquadexprs; ++j )
    1385 {
    1386 SCIP_EXPR* expr;
    1387 SCIP_Real sqrcoef;
    1388 SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
    1389 SCIP_VAR* quadvar;
    1390
    1391 /* get variable of the quadratic term */
    1392 SCIPexprGetQuadraticQuadTerm(quadexpr, j, &expr, NULL, &sqrcoef, NULL, NULL, NULL);
    1393 assert(expr != NULL && SCIPisExprVar(scip, expr));
    1394 quadvar = SCIPgetVarExprVar(expr);
    1395 assert(quadvar != NULL);
    1396
    1397 /* create/get dual constraint associated to variable 'bilvar1';
    1398 * if variable does not already exist in hashmap then create dual variables for its bounds */
    1399 SCIP_CALL( createKKTDualCons(scip, objcons, quadvar, varhash, dualconss, ndualconss, &dualcons, naddconss) );
    1400 assert( dualcons != NULL );
    1401
    1402 /* add variable to dual constraint */
    1403 assert( ! SCIPisFeasZero(scip, scale) );
    1404 SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, quadvar, sqrcoef * 2.0 / scale) );
    1405 }
    1406
    1407 return SCIP_OKAY;
    1408}
    1409
    1410/** handle linear terms of quadratic constraint for quadratic constraint update
    1411 *
    1412 * For each linear term variable
    1413 * 1. create the dual constraint (i.e., a row of \f$Q x + c + A^T \mu = 0\f$) associated to this variable, if not done
    1414 * already
    1415 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
    1416 * variable, if not done already
    1417 * 3. add the right hand side \f$-c_i\f$ to the dual constraint
    1418 * 4. add \f$c_i\f$ to the objective constraint \f$1/2 ( c^T x + b^T \mu) = t\f$, where t is the objective variable
    1419 *
    1420 * for steps 1 and 2 see the documentation of createKKTDualCons() for further information.
    1421 **/
    1422static
    1423SCIP_RETCODE presolveAddKKTQuadLinearTerms(
    1424 SCIP* scip, /**< SCIP pointer */
    1425 SCIP_CONS* objcons, /**< objective constraint */
    1426 SCIP_EXPR* quadexpr, /**< quadratic expression */
    1427 SCIP_HASHMAP* varhash, /**< hash map from variable to index of linear constraint */
    1428 SCIP_VAR* objvar, /**< variable of objective function */
    1429 SCIP_Real scale, /**< scale factor of quadratic constraint */
    1430 SCIP_CONS** dualconss, /**< array with dual constraints */
    1431 int* ndualconss, /**< pointer to store number of dual constraints */
    1432 int* naddconss /**< buffer to increase with number of created additional constraints */
    1433 )
    1434{
    1435 SCIP_EXPR** linexprs;
    1436 SCIP_Real* lincoefs;
    1437 int nquadexprs;
    1438 int nlinexprs;
    1439 int j;
    1440
    1441 assert( scip != NULL );
    1442 assert( objcons != NULL );
    1443 assert( varhash != NULL );
    1444 assert( objvar != NULL );
    1445 assert( dualconss != NULL );
    1446 assert( ndualconss != NULL );
    1447 assert( naddconss != NULL );
    1448
    1449 /* get linear and quadratic expression terms */
    1450 SCIPexprGetQuadraticData(quadexpr, NULL, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, NULL, NULL, NULL);
    1451
    1452 /* loop through linear terms */
    1453 for( j = 0; j < nlinexprs; ++j )
    1454 {
    1455 SCIP_VAR* var;
    1456 SCIP_Real coef;
    1457
    1458 assert(linexprs[j] != NULL);
    1459 assert(SCIPisExprVar(scip, linexprs[j]));
    1460
    1461 var = SCIPgetVarExprVar(linexprs[j]);
    1462 assert(var != NULL);
    1463 coef = lincoefs[j];
    1464
    1465 if( var != objvar )
    1466 {
    1467 SCIP_CONS* dualcons = NULL; /* dual constraint associated to variable */
    1468
    1469 /* create/get dual constraint associated to variable;
    1470 * if variable does not already exist in hashmap then create dual variables for its bounds
    1471 */
    1472 SCIP_CALL( createKKTDualCons(scip, objcons, var, varhash, dualconss, ndualconss, &dualcons, naddconss) );
    1473 assert( dualcons != NULL );
    1474
    1475 /* change lhs and rhs of dual constraint */
    1476 assert( ! SCIPisFeasZero(scip, scale) );
    1477 SCIP_CALL( SCIPchgLhsLinear(scip, dualcons, SCIPgetLhsLinear(scip, dualcons) - coef / scale) );
    1478 SCIP_CALL( SCIPchgRhsLinear(scip, dualcons, SCIPgetRhsLinear(scip, dualcons) - coef / scale) );
    1479
    1480 /* add variable to objective constraint */
    1481 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, var, coef / (scale * 2)) );
    1482 }
    1483 }
    1484
    1485 /* loop through linear terms that are part of a quadratic term */
    1486 for( j = 0; j < nquadexprs; ++j )
    1487 {
    1488 SCIP_EXPR* expr;
    1489 SCIP_CONS* dualcons;
    1490 SCIP_Real coef;
    1491 SCIP_VAR* var;
    1492 int ind;
    1493
    1494 SCIPexprGetQuadraticQuadTerm(quadexpr, j, &expr, &coef, NULL, NULL, NULL, NULL);
    1495 assert(expr != NULL);
    1496 assert(SCIPisExprVar(scip, expr));
    1497
    1498 var = SCIPgetVarExprVar(expr);
    1499 assert(var != NULL && var != objvar);
    1500
    1501 /* get dual constraint associated to variable (has already been created in function
    1502 * presolveAddKKTQuadQuadraticTerms()
    1503 */
    1504 assert( SCIPhashmapExists(varhash, var) );
    1505 ind = SCIPhashmapGetImageInt(varhash, var);
    1506 dualcons = dualconss[ind];
    1507 assert( dualcons != NULL );
    1508
    1509 /* change lhs and rhs of dual constraint */
    1510 assert( ! SCIPisFeasZero(scip, scale) );
    1511 SCIP_CALL( SCIPchgLhsLinear(scip, dualcons, SCIPgetLhsLinear(scip, dualcons) -coef / scale) );
    1512 SCIP_CALL( SCIPchgRhsLinear(scip, dualcons, SCIPgetRhsLinear(scip, dualcons) -coef / scale) );
    1513
    1514 /* add variable to objective constraint */
    1515 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, var, coef / (scale * 2.0)) );
    1516 }
    1517
    1518 return SCIP_OKAY;
    1519}
    1520
    1521/** checks for a given constraint whether it is the objective function of a (mixed-binary) quadratic program
    1522 * \f[
    1523 * \begin{array}{ll}
    1524 * \min & z \\
    1525 * s.t. & x^T Q x + c^T x + d <= z \\
    1526 * & A x \leq b, \\
    1527 * & x \in \{0, 1\}^{p} \times R^{n-p},
    1528 * \end{array}
    1529 * \f]
    1530 * which is equivalent to
    1531 * \f[
    1532 * \begin{array}{ll}
    1533 * \min & x^T Q x + c^T x + d \\
    1534 * s.t. & A x \leq b, \\
    1535 * & x \in \{0, 1\}^{p} \times R^{n-p}.
    1536 * \end{array}
    1537 * \f]
    1538 *
    1539 *
    1540 * We check whether
    1541 * 1. there is a single quadratic constraint that can be written as \f$x^T Q x + c^T x + d \leq z\f$
    1542 * 2. all other constraints are linear
    1543 * 3. all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
    1544 * 4. z is the only variable in the objective and doesn't appear in any other constraint
    1545 */
    1546static
    1547SCIP_RETCODE checkConsQuadraticProblem(
    1548 SCIP* scip, /**< SCIP data structure */
    1549 SCIP_CONS* cons, /**< nonlinear constraint */
    1550 SCIP_EXPR* quadexpr, /**< quadratic expression */
    1551 SCIP_Bool allowbinary, /**< if TRUE then allow binary variables in the problem, if FALSE then all
    1552 * variables have to be continuous */
    1553 SCIP_VAR** objvar, /**< pointer to store the objective variable z */
    1554 SCIP_Real* scale, /**< pointer to store the value by which we have to scale the quadratic
    1555 * constraint such that the objective variable z has coefficient -1 */
    1556 SCIP_Real* objrhs, /**< pointer to store the right hand side -d of the objective constraint */
    1557 SCIP_Bool* isqp /**< pointer to store whether the problem is a (mixed-binary) QP */
    1558 )
    1559{
    1560 SCIP_CONSHDLR* conshdlr;
    1561 int nconss = 0;
    1562 SCIP_Real coef;
    1563 SCIP_Real obj;
    1564
    1565 SCIP_VAR* origObjVar;
    1566 SCIP_Real origObjConstant = 0.0;
    1567 SCIP_Real origObjScalar = 1.0;
    1568 SCIP_Real origObjUb;
    1569 SCIP_Real origObjLb;
    1570
    1571 SCIP_Real lhs;
    1572 SCIP_Real rhs;
    1573
    1574 SCIP_VAR* mayincrease;
    1575 SCIP_VAR* maydecrease;
    1576 SCIP_Real mayincreasecoef;
    1577 SCIP_Real maydecreasecoef;
    1578
    1579 SCIP_EXPR** linexprs;
    1580 SCIP_Real* lincoefs;
    1581 SCIP_Real constant;
    1582 int nbilinexprs;
    1583 int nquadexprs;
    1584 int nlinexprs;
    1585
    1586 assert(SCIPconshdlrGetNConss(SCIPfindConshdlr(scip, "nonlinear")) == 1);
    1587
    1588 *objrhs = 0.0;
    1589 *scale = 0.0;
    1590 *isqp = FALSE;
    1591 *objvar = NULL;
    1592
    1593 lhs = SCIPgetLhsNonlinear(cons);
    1594 rhs = SCIPgetRhsNonlinear(cons);
    1595
    1596 /* desired structure: there exists only one variable with nonzero objective value; this is the objective variable 'z' */
    1597 if( SCIPgetNObjVars(scip) != 1 )
    1598 return SCIP_OKAY;
    1599
    1600 /* desired structure: all integer variables are binary; if the parameter 'allowbinary' is set to FALSE, then all
    1601 * variables have to be continuous
    1602 */
    1603 if( SCIPgetNIntVars(scip) > 0 || (! allowbinary && SCIPgetNBinVars(scip) > 0) )
    1604 return SCIP_OKAY;
    1605
    1606 /* desired structure: the constraint has to take one of the three forms
    1607 * i) x^T Q x + c^T x <= d
    1608 * ii) x^T Q x + c^T x >= d
    1609 * iii) x^T Q x + c^T x == d
    1610 * the case a <= x^T Q x + c^T x <= d with 'a' and 'd' finite and a != d is not allowed.
    1611 */
    1612 if( ! SCIPisFeasEQ(scip, lhs, rhs) && ! SCIPisInfinity(scip, -lhs) && ! SCIPisInfinity(scip, rhs) )
    1613 return SCIP_OKAY;
    1614
    1615 /* get number of linear constraints (including special cases of linear constraints) */
    1616 conshdlr = SCIPfindConshdlr(scip, "linear");
    1617 if( conshdlr != NULL )
    1618 nconss += SCIPconshdlrGetNConss(conshdlr);
    1619
    1620 conshdlr = SCIPfindConshdlr(scip, "setppc");
    1621 if( conshdlr != NULL )
    1622 nconss += SCIPconshdlrGetNConss(conshdlr);
    1623
    1624 conshdlr = SCIPfindConshdlr(scip, "knapsack");
    1625 if( conshdlr != NULL )
    1626 nconss += SCIPconshdlrGetNConss(conshdlr);
    1627
    1628 conshdlr = SCIPfindConshdlr(scip, "varbound");
    1629 if( conshdlr != NULL )
    1630 nconss += SCIPconshdlrGetNConss(conshdlr);
    1631
    1632 conshdlr = SCIPfindConshdlr(scip, "logicor");
    1633 if( conshdlr != NULL )
    1634 nconss += SCIPconshdlrGetNConss(conshdlr);
    1635
    1636 /* desired structure: all the non-nonlinear constraints are linear constraints */
    1637 if( nconss != SCIPgetNConss(scip) - 1 )
    1638 return SCIP_OKAY;
    1639
    1640 /* get data of the quadratic expression */
    1641 SCIPexprGetQuadraticData(quadexpr, &constant, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
    1642
    1643 /* adjust lhs and rhs if constant is nonzero */
    1644 if( constant != 0.0 )
    1645 {
    1646 if( !SCIPisInfinity(scip, -lhs) )
    1647 lhs -= constant;
    1648 if( !SCIPisInfinity(scip, rhs) )
    1649 rhs -= constant;
    1650 }
    1651
    1652 /* compute the objective shift of the QP. Note that
    1653 *
    1654 * min z s.t. x^T Q x + c^T x <= d + z
    1655 * Ax <= b
    1656 *
    1657 * is equivalent to
    1658 *
    1659 * min x^T Q x + c^T x - d s.t. Ax <= b
    1660 *
    1661 * Here, -d is the objective shift. We define b to be the right hand side of the objective constraint.
    1662 */
    1663 if( ! SCIPisInfinity(scip, -lhs) )
    1664 *objrhs = lhs;
    1665 else
    1666 *objrhs = rhs;
    1667 assert( ! SCIPisInfinity(scip, REALABS(*objrhs)) );
    1668
    1669 /* search for the objective variable 'objvar' in the linear term of quadratic constraint (it is already known that
    1670 * at most one variable has a nonzero objective value); additionally, check the sign of the objective variable
    1671 */
    1672
    1673 SCIPgetLinvarMayIncreaseNonlinear(scip, cons, &mayincrease, &mayincreasecoef);
    1674 SCIPgetLinvarMayIncreaseNonlinear(scip, cons, &maydecrease, &maydecreasecoef);
    1675
    1676 if( maydecrease == NULL && mayincrease == NULL )
    1677 return SCIP_OKAY;
    1678 if( maydecrease != NULL )
    1679 {
    1680 *objvar = maydecrease;
    1681 coef = maydecreasecoef;
    1682
    1683 /* if both mayincrease and maydecrease are nonnegative, then check objective coefficient */
    1684 if( mayincrease != NULL && SCIPisFeasZero(scip, SCIPvarGetObj(maydecrease)) )
    1685 {
    1686 *objvar = mayincrease;
    1687 coef = mayincreasecoef;
    1688 }
    1689 }
    1690 else
    1691 {
    1692 *objvar = mayincrease;
    1693 coef = mayincreasecoef;
    1694 }
    1695 assert(*objvar != NULL);
    1696 obj = SCIPvarGetObj(*objvar);
    1697
    1698 /* check sign of coefficient */
    1699 if( SCIPisFeasPositive(scip, obj)
    1700 && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, rhs, *objrhs) )
    1701 || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, lhs, *objrhs) )
    1702 )
    1703 )
    1704 {
    1705 *scale = -coef; /* value by which we have to scale the quadratic constraint such that the objective variable
    1706 * has coefficient -1 */
    1707 }
    1708 else if( SCIPisFeasNegative(scip, obj)
    1709 && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, lhs, *objrhs) )
    1710 || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, rhs, *objrhs) )
    1711 )
    1712 )
    1713 {
    1714 *scale = coef; /* value by which we have to scale the quadratic constraint such that the objective variable
    1715 * has coefficient 1 */
    1716 }
    1717 else
    1718 return SCIP_OKAY;
    1719 assert( ! SCIPisFeasZero(scip, SCIPvarGetObj(*objvar)) );
    1720 assert( ! SCIPisFeasZero(scip, *scale) );
    1721
    1722 /* scale the right hand side of the objective constraint */
    1723 *objrhs = (*objrhs)/(*scale); /*lint !e414*/
    1724
    1725 /* check whether 'objvar' is part of a linear constraint; if this is true then return
    1726 * whether 'objvar' is part of a linear constraint can be deduced from the variable locks */
    1727 if( SCIPisFeasEQ(scip, lhs, rhs) )
    1728 {
    1729 if( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1
    1730 || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 )
    1731 return SCIP_OKAY;
    1732 }
    1733 else
    1734 {
    1735 assert( SCIPisInfinity(scip, -lhs) || SCIPisInfinity(scip, rhs) );
    1736
    1737 if( ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1
    1738 || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 0 )
    1739 && ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 0
    1740 || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 ) )
    1741 return SCIP_OKAY;
    1742 }
    1743
    1744 /* check bounds of original objective variable */
    1745 origObjVar = *objvar;
    1746 SCIP_CALL( SCIPvarGetOrigvarSum(&origObjVar, &origObjScalar, &origObjConstant) );
    1747 if( origObjVar == NULL )
    1748 return SCIP_OKAY;
    1749
    1750 if( SCIPisFeasPositive(scip, origObjScalar) )
    1751 {
    1752 origObjUb = SCIPvarGetUbOriginal(origObjVar);
    1753 origObjLb = SCIPvarGetLbOriginal(origObjVar);
    1754 }
    1755 else
    1756 {
    1757 origObjUb = -SCIPvarGetLbOriginal(origObjVar);
    1758 origObjLb = -SCIPvarGetUbOriginal(origObjVar);
    1759 origObjScalar *= -1;
    1760 origObjConstant *= -1;
    1761 }
    1762
    1763 /* not every optimal solution of the problem is a KKT point if the objective variable is bounded */
    1764 if( SCIPisFeasPositive(scip, obj))
    1765 {
    1766 if ( !SCIPisInfinity(scip, -origObjLb))
    1767 return SCIP_OKAY;
    1768 if ( !SCIPisInfinity(scip, origObjUb)
    1769 && !SCIPisFeasLE(scip, rhs/coef, (origObjUb-origObjConstant)/origObjScalar) )
    1770 return SCIP_OKAY;
    1771 }
    1772 else
    1773 {
    1774 if ( !SCIPisInfinity(scip, origObjUb) )
    1775 return SCIP_OKAY;
    1776 if ( !SCIPisInfinity(scip, -origObjLb)
    1777 && !SCIPisFeasGE(scip, lhs/coef, (origObjLb - origObjConstant)/origObjScalar) )
    1778 return SCIP_OKAY;
    1779 }
    1780
    1781 *isqp = TRUE;
    1782
    1783 return SCIP_OKAY;
    1784}
    1785
    1786/*
    1787 * Callback methods of presolver
    1788 */
    1789
    1790/** copy method for constraint handler plugins (called when SCIP copies plugins) */
    1791static
    1792SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref)
    1793{ /*lint --e{715}*/
    1794 assert(scip != NULL);
    1795 assert(presol != NULL);
    1796 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
    1797
    1798 /* call inclusion method of presolver */
    1799 SCIP_CALL( SCIPincludePresolQPKKTref(scip) );
    1800
    1801 return SCIP_OKAY;
    1802}
    1803
    1804
    1805/** destructor of presolver to free user data (called when SCIP is exiting) */
    1806static
    1807SCIP_DECL_PRESOLFREE(presolFreeQPKKTref)
    1808{ /*lint --e{715}*/
    1809 SCIP_PRESOLDATA* presoldata;
    1810
    1811 /* free presolver data */
    1812 presoldata = SCIPpresolGetData(presol);
    1813 assert(presoldata != NULL);
    1814
    1815 SCIPfreeBlockMemory(scip, &presoldata);
    1816 SCIPpresolSetData(presol, NULL);
    1817
    1818 return SCIP_OKAY;
    1819}
    1820
    1821
    1822/** execution method of presolver */
    1823static
    1824SCIP_DECL_PRESOLEXEC(presolExecQPKKTref)
    1825{ /*lint --e{715}*/
    1826 SCIP_PRESOLDATA* presoldata;
    1827 SCIP_CONSHDLR* linconshdlr;
    1828 SCIP_CONSHDLR* nlconshdlr;
    1829 SCIP_CONS** conss;
    1830 SCIP_CONS* cons;
    1831 SCIP_Bool isquadratic;
    1832 SCIP_EXPR* expr;
    1833
    1834 SCIP_CONS** savelinconss = NULL;
    1835 SCIP_CONS** linconss = NULL;
    1836 int nlinconss = 0;
    1837
    1838 SCIP_HASHMAP* varhash; /* hash map from variable to index of dual constraint */
    1839 SCIP_CONS** dualconss; /* constraints associated to the Lagrangean function */
    1840 int ndualconss = 0;
    1841
    1842 SCIP_EXPRCURV curv;
    1843
    1844 SCIP_CONS* objcons;
    1845 SCIP_VAR* objvar;
    1846 SCIP_Real scale;
    1847 SCIP_Real objrhs;
    1848 SCIP_Bool isqp;
    1849 int j;
    1850
    1851 assert( scip != NULL );
    1852 assert( naddconss != NULL );
    1853 assert( ndelconss != NULL );
    1854
    1855 /* desired structure: there exists only one nonlinear constraint */
    1856 nlconshdlr = SCIPfindConshdlr(scip, "nonlinear");
    1857 if( nlconshdlr == NULL || SCIPconshdlrGetNConss(nlconshdlr) != 1 )
    1858 return SCIP_OKAY;
    1859
    1860 /* get presolver data */
    1861 presoldata = SCIPpresolGetData(presol);
    1862 assert(presoldata != NULL);
    1863
    1864 /* get nonlinear constraint */
    1865 conss = SCIPconshdlrGetConss(nlconshdlr);
    1866 cons = conss[0];
    1867 assert( cons != NULL );
    1868
    1869 SCIPdebugMsg(scip, "tries to add the KKT conditions for constraint <%s>\n", SCIPconsGetName(cons));
    1870
    1871 /* get quadratic representation of the nonlinear constraint, if possible */
    1872 SCIP_CALL( SCIPcheckQuadraticNonlinear(scip, cons, &isquadratic) );
    1873
    1874 if( !isquadratic )
    1875 {
    1876 SCIPdebugMsg(scip, "nonlinear constraint is not quadratic -> skip\n");
    1877 return SCIP_OKAY;
    1878 }
    1879
    1880 /* desired structure: matrix associated to quadratic constraint is indefinite; otherwise, the problem usually can be
    1881 * solved faster by standard methods
    1882 */
    1883 expr = SCIPgetExprNonlinear(cons);
    1884 SCIP_CALL( SCIPcomputeExprQuadraticCurvature(scip, expr, &curv, NULL, FALSE) );
    1885
    1886 if( !presoldata->updatequadindef && (curv == SCIP_EXPRCURV_CONVEX || curv == SCIP_EXPRCURV_CONCAVE) )
    1887 {
    1888 SCIPdebugMsg(scip, "quadratic constraint update failed, since matrix associated to quadratic constraint <%s> is \
    1889 not indefinite.\n", SCIPconsGetName(cons) );
    1890 return SCIP_OKAY;
    1891 }
    1892
    1893 /* first, check whether the problem is equivalent to
    1894 *
    1895 * min z
    1896 * s.t. x^T Q x + c^T x <= b + z
    1897 * x \in \{0, 1\}^{p} \times R^{n-p}.
    1898 *
    1899 */
    1900 SCIP_CALL( checkConsQuadraticProblem(scip, cons, expr, presoldata->addkktbinary, &objvar, &scale,
    1901 &objrhs, &isqp) );
    1902 if( ! isqp )
    1903 return SCIP_OKAY;
    1904 assert( objvar != NULL );
    1905
    1906 /* get constraint handler data of linear constraints */
    1907 linconshdlr = SCIPfindConshdlr(scip, "linear");
    1908
    1909 /* get linear constraints and number of linear constraints */
    1910 if( linconshdlr != NULL )
    1911 {
    1912 nlinconss = SCIPconshdlrGetNConss(linconshdlr);
    1913 linconss = SCIPconshdlrGetConss(linconshdlr);
    1914 }
    1915
    1916 /* the update is only valid if a finite optimal solution of the problem exists,
    1917 * since only finite optimal solutions satisfy the KKT conditions;
    1918 * we check whether all variables have finite bounds, otherwise we return */
    1919 if( presoldata->updatequadbounded )
    1920 {
    1921 SCIP_VAR** vars;
    1922 SCIP_Bool success;
    1923 int nvars;
    1924 int i;
    1925
    1926 /* get total number of variables in the nonlinear constraint */
    1927 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, &success) );
    1928 assert(success);
    1929
    1930 /* allocate memory to store variables of the nonlinear constraint */
    1931 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
    1932
    1933 /* get variables */
    1934 SCIP_CALL( SCIPgetConsVars(scip, cons, vars, nvars, &success) );
    1935 assert(success);
    1936
    1937 /* check whether each variable has finite bounds */
    1938 success = TRUE;
    1939 for( i = 0; i < nvars && success; ++i )
    1940 {
    1941 SCIP_Real lb;
    1942 SCIP_Real ub;
    1943
    1944 assert(vars[i] != NULL);
    1945
    1946 lb = SCIPvarGetLbGlobal(vars[i]);
    1947 ub = SCIPvarGetUbGlobal(vars[i]);
    1948
    1949 if( vars[i] != objvar && (SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub)) )
    1950 success = FALSE;
    1951 }
    1952
    1953 /* free memory */
    1954 SCIPfreeBufferArray(scip, &vars);
    1955
    1956 if( !success )
    1957 {
    1958 SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables of <%s> have finite bounds.\n",
    1959 SCIPconsGetName(cons));
    1960 return SCIP_OKAY;
    1961 }
    1962 }
    1963
    1964 /* add KKT constraints */
    1965
    1966 /* set up hash map */
    1967 SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), SCIPgetNVars(scip) + SCIPgetNFixedVars(scip)) );
    1968
    1969 /* allocate buffer array */
    1970 SCIP_CALL( SCIPallocBufferArray(scip, &dualconss, 2 * SCIPgetNVars(scip) + 2 * SCIPgetNFixedVars(scip)) ); /*lint !e647*/
    1971
    1972 /* duplicate linconss for later use, since in the following, we create new linear constraints */
    1973 if( linconss != NULL )
    1974 {
    1975 SCIP_CALL( SCIPduplicateBufferArray(scip, &savelinconss, linconss, nlinconss) );
    1976 }
    1977
    1978 /* create new objective constraint */
    1979 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &objcons, "objcons", 0, NULL, NULL, objrhs, objrhs) );
    1980 if( SCIPisFeasNegative(scip, SCIPvarGetObj(objvar)) )
    1981 {
    1982 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, 1.0) );
    1983 }
    1984 else
    1985 {
    1986 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, -1.0) );
    1987 }
    1988
    1989 /* handle linear constraints */
    1990 if( savelinconss != NULL )
    1991 {
    1992 SCIP_CALL( presolveAddKKTLinearConss(scip, objcons, savelinconss, nlinconss, varhash, dualconss, &ndualconss,
    1993 naddconss, ndelconss) );
    1994 }
    1995
    1996 /* handle set packing constraints */
    1997 SCIP_CALL( presolveAddKKTSetppcConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
    1998
    1999 /* handle knapsack constraints */
    2000 SCIP_CALL( presolveAddKKTKnapsackConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
    2001
    2002 /* handle varbound constraints */
    2003 SCIP_CALL( presolveAddKKTVarboundConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
    2004
    2005 /* handle logicor constraints */
    2006 SCIP_CALL( presolveAddKKTLogicorConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
    2007
    2008 /* handle linear constraints associated to aggregations of variables */
    2009 if( SCIPgetNFixedVars(scip) > 0 )
    2010 {
    2011 SCIP_CALL( presolveAddKKTAggregatedVars(scip, objcons, SCIPgetFixedVars(scip), SCIPgetNFixedVars(scip),
    2012 varhash, dualconss, &ndualconss, naddconss) );
    2013 }
    2014
    2015 /* handle bilinear terms of quadratic constraint */
    2016 SCIP_CALL( presolveAddKKTQuadBilinearTerms(scip, objcons, expr, varhash, scale, dualconss, &ndualconss,
    2017 naddconss) );
    2018
    2019 /* handle quadratic terms of quadratic constraint */
    2020 SCIP_CALL( presolveAddKKTQuadQuadraticTerms(scip, objcons, expr, varhash, scale, dualconss, &ndualconss,
    2021 naddconss) );
    2022
    2023 /* handle linear terms of quadratic constraint */
    2024 SCIP_CALL( presolveAddKKTQuadLinearTerms(scip, objcons, expr, varhash, objvar, scale, dualconss, &ndualconss,
    2025 naddconss) );
    2026
    2027 /* add/release objective constraint */
    2028 SCIP_CALL( SCIPaddCons(scip, objcons) );
    2029 SCIP_CALL( SCIPreleaseCons(scip, &objcons) );
    2030 ++(*naddconss);
    2031
    2032 /* add/release dual constraints associated to the KKT conditions */
    2033 for( j = 0; j < ndualconss; ++j )
    2034 {
    2035 SCIP_CALL( SCIPaddCons(scip, dualconss[j]) );
    2036 SCIP_CALL( SCIPreleaseCons(scip, &dualconss[j]) );
    2037 }
    2038 *naddconss = *naddconss + ndualconss;
    2039
    2040 /* free buffer array */
    2041 SCIPfreeBufferArrayNull(scip, &savelinconss);
    2042 SCIPfreeBufferArray(scip, &dualconss);
    2043
    2044 /* free hash map */
    2045 SCIPhashmapFree(&varhash);
    2046
    2047 if( SCIPgetNBinVars(scip) > 0 )
    2048 SCIPdebugMsg(scip, "added the KKT conditions to the mixed-binary quadratic program\n");
    2049 else
    2050 SCIPdebugMsg(scip, "added the KKT conditions to the quadratic program\n");
    2051
    2052 /* SCIP_CALL( SCIPwriteTransProblem(scip, "trafoQP.lp", NULL, FALSE ) ); */
    2053
    2054 return SCIP_OKAY;
    2055}
    2056
    2057
    2058/*
    2059 * presolver specific interface methods
    2060 */
    2061
    2062/** creates the QP KKT reformulation presolver and includes it in SCIP */
    2063SCIP_RETCODE SCIPincludePresolQPKKTref(
    2064 SCIP* scip /**< SCIP data structure */
    2065 )
    2066{
    2067 SCIP_PRESOLDATA* presoldata;
    2068 SCIP_PRESOL* presol= NULL;
    2069
    2070 /* alloc presolve data object */
    2071 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
    2072
    2073 /* include presolver */
    2074 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
    2075 PRESOL_TIMING, presolExecQPKKTref, presoldata) );
    2076 assert(presol != NULL);
    2077
    2078 /* set non fundamental callbacks via setter functions */
    2079 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyQPKKTref) );
    2080 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeQPKKTref) );
    2081
    2082 /* add qpkktref presolver parameters */
    2083 SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/addkktbinary",
    2084 "if TRUE then allow binary variables for KKT update",
    2085 &presoldata->addkktbinary, TRUE, FALSE, NULL, NULL) );
    2086
    2087 SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadbounded",
    2088 "if TRUE then only apply the update to QPs with bounded variables; if the variables are not bounded then a "
    2089 "finite optimal solution might not exist and the KKT conditions would then be invalid",
    2090 &presoldata->updatequadbounded, TRUE, TRUE, NULL, NULL) );
    2091
    2092 SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadindef",
    2093 "if TRUE then apply quadratic constraint update even if the quadratic constraint matrix is known to be indefinite",
    2094 &presoldata->updatequadindef, TRUE, FALSE, NULL, NULL) );
    2095
    2096 return SCIP_OKAY;
    2097}
    cons_knapsack.h
    Constraint handler for knapsack constraints of the form , x binary and .
    cons_linear.h
    Constraint handler for linear constraints in their most general form, .
    cons_logicor.h
    Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
    cons_nonlinear.h
    constraint handler for nonlinear constraints specified by algebraic expressions
    cons_setppc.h
    Constraint handler for the set partitioning / packing / covering constraints .
    cons_sos1.h
    constraint handler for SOS type 1 constraints
    cons_varbound.h
    Constraint handler for variable bound constraints .
    NULL
    #define NULL
    Definition: def.h:248
    SCIP_MAXSTRLEN
    #define SCIP_MAXSTRLEN
    Definition: def.h:269
    SCIP_Longint
    #define SCIP_Longint
    Definition: def.h:141
    SCIP_Bool
    #define SCIP_Bool
    Definition: def.h:91
    SCIP_Real
    #define SCIP_Real
    Definition: def.h:156
    TRUE
    #define TRUE
    Definition: def.h:93
    FALSE
    #define FALSE
    Definition: def.h:94
    REALABS
    #define REALABS(x)
    Definition: def.h:182
    SCIP_CALL
    #define SCIP_CALL(x)
    Definition: def.h:355
    SCIPcheckQuadraticNonlinear
    SCIP_RETCODE SCIPcheckQuadraticNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *isquadratic)
    Definition: cons_nonlinear.c:14077
    SCIPgetNVarsKnapsack
    int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_knapsack.c:13845
    SCIPgetVbdcoefVarbound
    SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_varbound.c:5970
    SCIPgetNVarsLogicor
    int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_logicor.c:5549
    SCIPgetRhsLinear
    SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_linear.c:18346
    SCIPgetVarsLinear
    SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_linear.c:18433
    SCIPchgRhsLinear
    SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
    Definition: cons_linear.c:18391
    SCIPaddCoefLinear
    SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
    Definition: cons_linear.c:18064
    SCIPgetLhsLinear
    SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_linear.c:18322
    SCIPgetNVarsLinear
    int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_linear.c:18409
    SCIPaddVarSOS1
    SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
    Definition: cons_sos1.c:10725
    SCIPgetValsLinear
    SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_linear.c:18457
    SCIPcreateConsBasicSOS1
    SCIP_RETCODE SCIPcreateConsBasicSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
    Definition: cons_sos1.c:10709
    SCIPgetVbdvarVarbound
    SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_varbound.c:5947
    SCIPgetNVarsSetppc
    int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_setppc.c:9596
    SCIPgetLinvarMayIncreaseNonlinear
    void SCIPgetLinvarMayIncreaseNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **var, SCIP_Real *coef)
    Definition: cons_nonlinear.c:14480
    SCIPcreateConsBasicLinear
    SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
    Definition: cons_linear.c:17912
    SCIPgetVarsSetppc
    SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_setppc.c:9619
    SCIPgetExprNonlinear
    SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
    Definition: cons_nonlinear.c:13979
    SCIPgetRhsNonlinear
    SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
    Definition: cons_nonlinear.c:14011
    SCIPgetVarVarbound
    SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_varbound.c:5924
    SCIP_SETPPCTYPE
    enum SCIP_SetppcType SCIP_SETPPCTYPE
    Definition: cons_setppc.h:91
    SCIPgetWeightsKnapsack
    SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_knapsack.c:13891
    SCIPgetCapacityKnapsack
    SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_knapsack.c:13788
    SCIPgetLhsVarbound
    SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_varbound.c:5878
    SCIPgetTypeSetppc
    SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_setppc.c:9642
    SCIPgetVarsLogicor
    SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_logicor.c:5572
    SCIPgetRhsVarbound
    SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_varbound.c:5901
    SCIPgetVarsKnapsack
    SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
    Definition: cons_knapsack.c:13868
    SCIPchgLhsLinear
    SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
    Definition: cons_linear.c:18370
    SCIPgetLhsNonlinear
    SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
    Definition: cons_nonlinear.c:13995
    SCIP_SETPPCTYPE_PARTITIONING
    @ SCIP_SETPPCTYPE_PARTITIONING
    Definition: cons_setppc.h:87
    SCIP_SETPPCTYPE_COVERING
    @ SCIP_SETPPCTYPE_COVERING
    Definition: cons_setppc.h:89
    SCIP_SETPPCTYPE_PACKING
    @ SCIP_SETPPCTYPE_PACKING
    Definition: cons_setppc.h:88
    SCIPgetNObjVars
    int SCIPgetNObjVars(SCIP *scip)
    Definition: scip_prob.c:2616
    SCIPaddVar
    SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
    Definition: scip_prob.c:1907
    SCIPgetNIntVars
    int SCIPgetNIntVars(SCIP *scip)
    Definition: scip_prob.c:2340
    SCIPgetNVars
    int SCIPgetNVars(SCIP *scip)
    Definition: scip_prob.c:2246
    SCIPaddCons
    SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
    Definition: scip_prob.c:3274
    SCIPdelCons
    SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
    Definition: scip_prob.c:3420
    SCIPgetNConss
    int SCIPgetNConss(SCIP *scip)
    Definition: scip_prob.c:3620
    SCIPgetNFixedVars
    int SCIPgetNFixedVars(SCIP *scip)
    Definition: scip_prob.c:2705
    SCIPgetNBinVars
    int SCIPgetNBinVars(SCIP *scip)
    Definition: scip_prob.c:2293
    SCIPgetFixedVars
    SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
    Definition: scip_prob.c:2662
    SCIPhashmapFree
    void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
    Definition: misc.c:3095
    SCIPhashmapGetImageInt
    int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
    Definition: misc.c:3304
    SCIPhashmapCreate
    SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
    Definition: misc.c:3061
    SCIPhashmapExists
    SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
    Definition: misc.c:3466
    SCIPhashmapInsertInt
    SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
    Definition: misc.c:3179
    SCIPdebugMsg
    #define SCIPdebugMsg
    Definition: scip_message.h:78
    SCIPaddBoolParam
    SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
    Definition: scip_param.c:57
    SCIPswapPointers
    void SCIPswapPointers(void **pointer1, void **pointer2)
    Definition: misc.c:10511
    SCIPincludePresolQPKKTref
    SCIP_RETCODE SCIPincludePresolQPKKTref(SCIP *scip)
    Definition: presol_qpkktref.c:2063
    SCIPconshdlrGetNConss
    int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
    Definition: cons.c:4778
    SCIPfindConshdlr
    SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
    Definition: scip_cons.c:940
    SCIPconshdlrGetConss
    SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
    Definition: cons.c:4735
    SCIPgetConsNVars
    SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
    Definition: scip_cons.c:2621
    SCIPgetConsVars
    SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
    Definition: scip_cons.c:2577
    SCIPconsGetName
    const char * SCIPconsGetName(SCIP_CONS *cons)
    Definition: cons.c:8389
    SCIPreleaseCons
    SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
    Definition: scip_cons.c:1173
    SCIPexprGetQuadraticBilinTerm
    void SCIPexprGetQuadraticBilinTerm(SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
    Definition: expr.c:4226
    SCIPexprGetQuadraticData
    void SCIPexprGetQuadraticData(SCIP_EXPR *expr, SCIP_Real *constant, int *nlinexprs, SCIP_EXPR ***linexprs, SCIP_Real **lincoefs, int *nquadexprs, int *nbilinexprs, SCIP_Real **eigenvalues, SCIP_Real **eigenvectors)
    Definition: expr.c:4141
    SCIPisExprVar
    SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
    Definition: scip_expr.c:1457
    SCIPcomputeExprQuadraticCurvature
    SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
    Definition: scip_expr.c:2611
    SCIPgetVarExprVar
    SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
    Definition: expr_var.c:424
    SCIPexprGetQuadraticQuadTerm
    void SCIPexprGetQuadraticQuadTerm(SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
    Definition: expr.c:4186
    SCIPblkmem
    BMS_BLKMEM * SCIPblkmem(SCIP *scip)
    Definition: scip_mem.c:57
    SCIPallocBufferArray
    #define SCIPallocBufferArray(scip, ptr, num)
    Definition: scip_mem.h:124
    SCIPfreeBufferArray
    #define SCIPfreeBufferArray(scip, ptr)
    Definition: scip_mem.h:136
    SCIPduplicateBufferArray
    #define SCIPduplicateBufferArray(scip, ptr, source, num)
    Definition: scip_mem.h:132
    SCIPfreeBlockMemory
    #define SCIPfreeBlockMemory(scip, ptr)
    Definition: scip_mem.h:108
    SCIPfreeBufferArrayNull
    #define SCIPfreeBufferArrayNull(scip, ptr)
    Definition: scip_mem.h:137
    SCIPallocBlockMemory
    #define SCIPallocBlockMemory(scip, ptr)
    Definition: scip_mem.h:89
    SCIPpresolSetData
    void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
    Definition: presol.c:538
    SCIPpresolGetData
    SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
    Definition: presol.c:528
    SCIPsetPresolFree
    SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
    Definition: scip_presol.c:164
    SCIPsetPresolCopy
    SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
    Definition: scip_presol.c:148
    SCIPincludePresolBasic
    SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
    Definition: scip_presol.c:113
    SCIPpresolGetName
    const char * SCIPpresolGetName(SCIP_PRESOL *presol)
    Definition: presol.c:625
    SCIPisFeasGE
    SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:823
    SCIPinfinity
    SCIP_Real SCIPinfinity(SCIP *scip)
    Definition: scip_numerics.c:501
    SCIPisFeasEQ
    SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:771
    SCIPisFeasZero
    SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:836
    SCIPisInfinity
    SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:512
    SCIPisFeasNegative
    SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:860
    SCIPisFeasLE
    SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
    Definition: scip_numerics.c:797
    SCIPisFeasPositive
    SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:848
    SCIPvarGetOrigvarSum
    SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
    Definition: var.c:18320
    SCIPvarGetNegationConstant
    SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var)
    Definition: var.c:23889
    SCIPvarGetMultaggrConstant
    SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
    Definition: var.c:23843
    SCIPvarIsBinary
    SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
    Definition: var.c:23478
    SCIPvarGetStatus
    SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
    Definition: var.c:23386
    SCIPvarGetNLocksUpType
    int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
    Definition: var.c:4386
    SCIPvarGetAggrConstant
    SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
    Definition: var.c:23771
    SCIPvarGetLbOriginal
    SCIP_Real SCIPvarGetLbOriginal(SCIP_VAR *var)
    Definition: var.c:24020
    SCIPvarGetObj
    SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
    Definition: var.c:23900
    SCIPvarGetAggrScalar
    SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
    Definition: var.c:23748
    SCIPvarGetUbGlobal
    SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
    Definition: var.c:24142
    SCIPvarGetName
    const char * SCIPvarGetName(SCIP_VAR *var)
    Definition: var.c:23267
    SCIPvarGetUbOriginal
    SCIP_Real SCIPvarGetUbOriginal(SCIP_VAR *var)
    Definition: var.c:24063
    SCIPreleaseVar
    SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
    Definition: scip_var.c:1887
    SCIPvarGetMultaggrVars
    SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
    Definition: var.c:23806
    SCIPvarGetMultaggrNVars
    int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
    Definition: var.c:23794
    SCIPvarGetNegationVar
    SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
    Definition: var.c:23878
    SCIPvarGetLbGlobal
    SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
    Definition: var.c:24120
    SCIPcreateVarBasic
    SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
    Definition: scip_var.c:184
    SCIPvarGetNLocksDownType
    int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
    Definition: var.c:4328
    SCIPvarGetMultaggrScalars
    SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
    Definition: var.c:23818
    SCIPvarGetAggrVar
    SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
    Definition: var.c:23736
    SCIPsnprintf
    int SCIPsnprintf(char *t, int len, const char *s,...)
    Definition: misc.c:10827
    scalars
    static const SCIP_Real scalars[]
    Definition: lp.c:5959
    memory.h
    memory allocation routines
    createKKTComplementarityBinary
    static SCIP_RETCODE createKKTComplementarityBinary(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualbin1, SCIP_VAR *dualbin2, int *naddconss)
    Definition: presol_qpkktref.c:324
    presolveAddKKTKnapsackConss
    static SCIP_RETCODE presolveAddKKTKnapsackConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
    Definition: presol_qpkktref.c:765
    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)
    Definition: presol_qpkktref.c:1547
    PRESOL_NAME
    #define PRESOL_NAME
    Definition: presol_qpkktref.c:113
    createKKTComplementarityBounds
    static SCIP_RETCODE createKKTComplementarityBounds(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualvar, SCIP_Bool takelb, int *naddconss)
    Definition: presol_qpkktref.c:230
    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)
    Definition: presol_qpkktref.c:1359
    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)
    Definition: presol_qpkktref.c:1122
    PRESOL_PRIORITY
    #define PRESOL_PRIORITY
    Definition: presol_qpkktref.c:115
    presolveAddKKTSetppcConss
    static SCIP_RETCODE presolveAddKKTSetppcConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
    Definition: presol_qpkktref.c:845
    presolveAddKKTVarboundConss
    static SCIP_RETCODE presolveAddKKTVarboundConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
    Definition: presol_qpkktref.c:951
    SCIP_DECL_PRESOLFREE
    static SCIP_DECL_PRESOLFREE(presolFreeQPKKTref)
    Definition: presol_qpkktref.c:1807
    SCIP_DECL_PRESOLCOPY
    static SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref)
    Definition: presol_qpkktref.c:1792
    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)
    Definition: presol_qpkktref.c:1423
    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)
    Definition: presol_qpkktref.c:696
    presolveAddKKTLogicorConss
    static SCIP_RETCODE presolveAddKKTLogicorConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
    Definition: presol_qpkktref.c:1039
    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)
    Definition: presol_qpkktref.c:426
    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)
    Definition: presol_qpkktref.c:146
    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)
    Definition: presol_qpkktref.c:1281
    PRESOL_MAXROUNDS
    #define PRESOL_MAXROUNDS
    Definition: presol_qpkktref.c:117
    PRESOL_TIMING
    #define PRESOL_TIMING
    Definition: presol_qpkktref.c:119
    SCIP_DECL_PRESOLEXEC
    static SCIP_DECL_PRESOLEXEC(presolExecQPKKTref)
    Definition: presol_qpkktref.c:1824
    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)
    Definition: presol_qpkktref.c:579
    PRESOL_DESC
    #define PRESOL_DESC
    Definition: presol_qpkktref.c:114
    presol_qpkktref.h
    qpkktref presolver
    pub_cons.h
    public methods for managing constraints
    pub_message.h
    public methods for message output
    SCIPerrorMessage
    #define SCIPerrorMessage
    Definition: pub_message.h:64
    pub_misc.h
    public data structures and miscellaneous methods
    pub_presol.h
    public methods for presolvers
    pub_var.h
    public methods for problem variables
    scip_cons.h
    public methods for constraint handler plugins and constraints
    scip_mem.h
    public methods for memory management
    scip_message.h
    public methods for message handling
    scip_numerics.h
    public methods for numerical tolerances
    scip_param.h
    public methods for SCIP parameter handling
    scip_presol.h
    public methods for presolving plugins
    scip_prob.h
    public methods for global and local (sub)problems
    scip_var.h
    public methods for SCIP variables
    SCIP_Cons
    Definition: struct_cons.h:47
    SCIP_Conshdlr
    Definition: struct_cons.h:128
    SCIP_Expr
    Definition: struct_expr.h:106
    SCIP_HashMap
    Definition: struct_misc.h:139
    SCIP_Presol
    Definition: struct_presol.h:47
    SCIP_Var
    Definition: struct_var.h:262
    SCIP_EXPRCURV
    SCIP_EXPRCURV
    Definition: type_expr.h:61
    SCIP_EXPRCURV_CONVEX
    @ SCIP_EXPRCURV_CONVEX
    Definition: type_expr.h:63
    SCIP_EXPRCURV_CONCAVE
    @ SCIP_EXPRCURV_CONCAVE
    Definition: type_expr.h:64
    SCIP_PRESOLDATA
    struct SCIP_PresolData SCIP_PRESOLDATA
    Definition: type_presol.h:51
    SCIP_INVALIDDATA
    @ SCIP_INVALIDDATA
    Definition: type_retcode.h:52
    SCIP_OKAY
    @ SCIP_OKAY
    Definition: type_retcode.h:42
    SCIP_ERROR
    @ SCIP_ERROR
    Definition: type_retcode.h:43
    SCIP_RETCODE
    enum SCIP_Retcode SCIP_RETCODE
    Definition: type_retcode.h:63
    SCIP_VARTYPE_CONTINUOUS
    @ SCIP_VARTYPE_CONTINUOUS
    Definition: type_var.h:71
    SCIP_VARSTATUS_FIXED
    @ SCIP_VARSTATUS_FIXED
    Definition: type_var.h:54
    SCIP_VARSTATUS_MULTAGGR
    @ SCIP_VARSTATUS_MULTAGGR
    Definition: type_var.h:56
    SCIP_VARSTATUS_NEGATED
    @ SCIP_VARSTATUS_NEGATED
    Definition: type_var.h:57
    SCIP_VARSTATUS_AGGREGATED
    @ SCIP_VARSTATUS_AGGREGATED
    Definition: type_var.h:55
    SCIP_LOCKTYPE_MODEL
    @ SCIP_LOCKTYPE_MODEL
    Definition: type_var.h:141