1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 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 */ 127 struct 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 */ 145 static 146 SCIP_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 */ 229 static 230 SCIP_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 */ 323 static 324 SCIP_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 */ 425 static 426 SCIP_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 */ 578 static 579 SCIP_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 */ 695 static 696 SCIP_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 */ 764 static 765 SCIP_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 */ 844 static 845 SCIP_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 */ 950 static 951 SCIP_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 */ 1038 static 1039 SCIP_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 */ 1121 static 1122 SCIP_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 **/ 1280 static 1281 SCIP_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 **/ 1358 static 1359 SCIP_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 **/ 1422 static 1423 SCIP_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 */ 1546 static 1547 SCIP_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 @p 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 @p z has coefficient -1 */ 1556 SCIP_Real* objrhs, /**< pointer to store the right hand side @p -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 else 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 obj = SCIPvarGetObj(*objvar); 1696 1697 /* check sign of coefficient */ 1698 if( SCIPisFeasPositive(scip, obj) 1699 && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, rhs, *objrhs) ) 1700 || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, lhs, *objrhs) ) 1701 ) 1702 ) 1703 { 1704 *scale = -coef; /* value by which we have to scale the quadratic constraint such that the objective variable 1705 * has coefficient -1 */ 1706 } 1707 else if( SCIPisFeasNegative(scip, obj) 1708 && ( ( SCIPisFeasNegative(scip, coef) && SCIPisFeasEQ(scip, lhs, *objrhs) ) 1709 || ( SCIPisFeasPositive(scip, coef) && SCIPisFeasEQ(scip, rhs, *objrhs) ) 1710 ) 1711 ) 1712 { 1713 *scale = coef; /* value by which we have to scale the quadratic constraint such that the objective variable 1714 * has coefficient 1 */ 1715 } 1716 else 1717 return SCIP_OKAY; 1718 assert( *objvar != NULL && ! SCIPisFeasZero(scip, SCIPvarGetObj(*objvar)) ); 1719 assert( ! SCIPisFeasZero(scip, *scale) ); 1720 1721 /* scale the right hand side of the objective constraint */ 1722 *objrhs = (*objrhs)/(*scale); /*lint !e414*/ 1723 1724 /* check whether 'objvar' is part of a linear constraint; if this is true then return 1725 * whether 'objvar' is part of a linear constraint can be deduced from the variable locks */ 1726 if( SCIPisFeasEQ(scip, lhs, rhs) ) 1727 { 1728 if( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 1729 || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 ) 1730 return SCIP_OKAY; 1731 } 1732 else 1733 { 1734 assert( SCIPisInfinity(scip, -lhs) || SCIPisInfinity(scip, rhs) ); 1735 1736 if( ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 1737 || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 0 ) 1738 && ( SCIPvarGetNLocksDownType(*objvar, SCIP_LOCKTYPE_MODEL) != 0 1739 || SCIPvarGetNLocksUpType(*objvar, SCIP_LOCKTYPE_MODEL) != 1 ) ) 1740 return SCIP_OKAY; 1741 } 1742 1743 /* check bounds of original objective variable */ 1744 origObjVar = *objvar; 1745 SCIP_CALL( SCIPvarGetOrigvarSum(&origObjVar, &origObjScalar, &origObjConstant) ); 1746 if( origObjVar == NULL ) 1747 return SCIP_OKAY; 1748 1749 if( SCIPisFeasPositive(scip, origObjScalar) ) 1750 { 1751 origObjUb = SCIPvarGetUbOriginal(origObjVar); 1752 origObjLb = SCIPvarGetLbOriginal(origObjVar); 1753 } 1754 else 1755 { 1756 origObjUb = -SCIPvarGetLbOriginal(origObjVar); 1757 origObjLb = -SCIPvarGetUbOriginal(origObjVar); 1758 origObjScalar *= -1; 1759 origObjConstant *= -1; 1760 } 1761 1762 /* not every optimal solution of the problem is a KKT point if the objective variable is bounded */ 1763 if( SCIPisFeasPositive(scip, obj)) 1764 { 1765 if ( !SCIPisInfinity(scip, -origObjLb)) 1766 return SCIP_OKAY; 1767 if ( !SCIPisInfinity(scip, origObjUb) 1768 && !SCIPisFeasLE(scip, rhs/coef, (origObjUb-origObjConstant)/origObjScalar) ) 1769 return SCIP_OKAY; 1770 } 1771 else 1772 { 1773 if ( !SCIPisInfinity(scip, origObjUb) ) 1774 return SCIP_OKAY; 1775 if ( !SCIPisInfinity(scip, -origObjLb) 1776 && !SCIPisFeasGE(scip, lhs/coef, (origObjLb - origObjConstant)/origObjScalar) ) 1777 return SCIP_OKAY; 1778 } 1779 1780 *isqp = TRUE; 1781 1782 return SCIP_OKAY; 1783 } 1784 1785 /* 1786 * Callback methods of presolver 1787 */ 1788 1789 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1790 static 1791 SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref) 1792 { /*lint --e{715}*/ 1793 assert(scip != NULL); 1794 assert(presol != NULL); 1795 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 1796 1797 /* call inclusion method of presolver */ 1798 SCIP_CALL( SCIPincludePresolQPKKTref(scip) ); 1799 1800 return SCIP_OKAY; 1801 } 1802 1803 1804 /** destructor of presolver to free user data (called when SCIP is exiting) */ 1805 static 1806 SCIP_DECL_PRESOLFREE(presolFreeQPKKTref) 1807 { /*lint --e{715}*/ 1808 SCIP_PRESOLDATA* presoldata; 1809 1810 /* free presolver data */ 1811 presoldata = SCIPpresolGetData(presol); 1812 assert(presoldata != NULL); 1813 1814 SCIPfreeBlockMemory(scip, &presoldata); 1815 SCIPpresolSetData(presol, NULL); 1816 1817 return SCIP_OKAY; 1818 } 1819 1820 1821 /** execution method of presolver */ 1822 static 1823 SCIP_DECL_PRESOLEXEC(presolExecQPKKTref) 1824 { /*lint --e{715}*/ 1825 SCIP_PRESOLDATA* presoldata; 1826 SCIP_CONSHDLR* linconshdlr; 1827 SCIP_CONSHDLR* nlconshdlr; 1828 SCIP_CONS** conss; 1829 SCIP_CONS* cons; 1830 SCIP_Bool isquadratic; 1831 SCIP_EXPR* expr; 1832 1833 SCIP_CONS** savelinconss = NULL; 1834 SCIP_CONS** linconss = NULL; 1835 int nlinconss = 0; 1836 1837 SCIP_HASHMAP* varhash; /* hash map from variable to index of dual constraint */ 1838 SCIP_CONS** dualconss; /* constraints associated to the Lagrangean function */ 1839 int ndualconss = 0; 1840 1841 SCIP_EXPRCURV curv; 1842 1843 SCIP_CONS* objcons; 1844 SCIP_VAR* objvar; 1845 SCIP_Real scale; 1846 SCIP_Real objrhs; 1847 SCIP_Bool isqp; 1848 int j; 1849 1850 assert( scip != NULL ); 1851 assert( naddconss != NULL ); 1852 assert( ndelconss != NULL ); 1853 1854 /* desired structure: there exists only one nonlinear constraint */ 1855 nlconshdlr = SCIPfindConshdlr(scip, "nonlinear"); 1856 if( nlconshdlr == NULL || SCIPconshdlrGetNConss(nlconshdlr) != 1 ) 1857 return SCIP_OKAY; 1858 1859 /* get presolver data */ 1860 presoldata = SCIPpresolGetData(presol); 1861 assert(presoldata != NULL); 1862 1863 /* get nonlinear constraint */ 1864 conss = SCIPconshdlrGetConss(nlconshdlr); 1865 cons = conss[0]; 1866 assert( cons != NULL ); 1867 1868 SCIPdebugMsg(scip, "tries to add the KKT conditions for constraint <%s>\n", SCIPconsGetName(cons)); 1869 1870 /* get quadratic representation of the nonlinear constraint, if possible */ 1871 SCIP_CALL( SCIPcheckQuadraticNonlinear(scip, cons, &isquadratic) ); 1872 1873 if( !isquadratic ) 1874 { 1875 SCIPdebugMsg(scip, "nonlinear constraint is not quadratic -> skip\n"); 1876 return SCIP_OKAY; 1877 } 1878 1879 /* desired structure: matrix associated to quadratic constraint is indefinite; otherwise, the problem usually can be 1880 * solved faster by standard methods 1881 */ 1882 expr = SCIPgetExprNonlinear(cons); 1883 SCIP_CALL( SCIPcomputeExprQuadraticCurvature(scip, expr, &curv, NULL, FALSE) ); 1884 1885 if( !presoldata->updatequadindef && (curv == SCIP_EXPRCURV_CONVEX || curv == SCIP_EXPRCURV_CONCAVE) ) 1886 { 1887 SCIPdebugMsg(scip, "quadratic constraint update failed, since matrix associated to quadratic constraint <%s> is \ 1888 not indefinite.\n", SCIPconsGetName(cons) ); 1889 return SCIP_OKAY; 1890 } 1891 1892 /* first, check whether the problem is equivalent to 1893 * 1894 * min z 1895 * s.t. x^T Q x + c^T x <= b + z 1896 * x \in \{0, 1\}^{p} \times R^{n-p}. 1897 * 1898 */ 1899 SCIP_CALL( checkConsQuadraticProblem(scip, cons, expr, presoldata->addkktbinary, &objvar, &scale, 1900 &objrhs, &isqp) ); 1901 if( ! isqp ) 1902 return SCIP_OKAY; 1903 assert( objvar != NULL ); 1904 1905 /* get constraint handler data of linear constraints */ 1906 linconshdlr = SCIPfindConshdlr(scip, "linear"); 1907 1908 /* get linear constraints and number of linear constraints */ 1909 if( linconshdlr != NULL ) 1910 { 1911 nlinconss = SCIPconshdlrGetNConss(linconshdlr); 1912 linconss = SCIPconshdlrGetConss(linconshdlr); 1913 } 1914 1915 /* the update is only valid if a finite optimal solution of the problem exists, 1916 * since only finite optimal solutions satisfy the KKT conditions; 1917 * we check whether all variables have finite bounds, otherwise we return */ 1918 if( presoldata->updatequadbounded ) 1919 { 1920 SCIP_VAR** vars; 1921 SCIP_Bool success; 1922 int nvars; 1923 int i; 1924 1925 /* get total number of variables in the nonlinear constraint */ 1926 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, &success) ); 1927 assert(success); 1928 1929 /* allocate memory to store variables of the nonlinear constraint */ 1930 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 1931 1932 /* get variables */ 1933 SCIP_CALL( SCIPgetConsVars(scip, cons, vars, nvars, &success) ); 1934 assert(success); 1935 1936 /* check whether each variable has finite bounds */ 1937 success = TRUE; 1938 for( i = 0; i < nvars && success; ++i ) 1939 { 1940 SCIP_Real lb; 1941 SCIP_Real ub; 1942 1943 assert(vars[i] != NULL); 1944 1945 lb = SCIPvarGetLbGlobal(vars[i]); 1946 ub = SCIPvarGetUbGlobal(vars[i]); 1947 1948 if( vars[i] != objvar && (SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub)) ) 1949 success = FALSE; 1950 } 1951 1952 /* free memory */ 1953 SCIPfreeBufferArray(scip, &vars); 1954 1955 if( !success ) 1956 { 1957 SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables of <%s> have finite bounds.\n", 1958 SCIPconsGetName(cons)); 1959 return SCIP_OKAY; 1960 } 1961 } 1962 1963 /* add KKT constraints */ 1964 1965 /* set up hash map */ 1966 SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), SCIPgetNVars(scip) + SCIPgetNFixedVars(scip)) ); 1967 1968 /* allocate buffer array */ 1969 SCIP_CALL( SCIPallocBufferArray(scip, &dualconss, 2 * SCIPgetNVars(scip) + 2 * SCIPgetNFixedVars(scip)) ); /*lint !e647*/ 1970 1971 /* duplicate linconss for later use, since in the following, we create new linear constraints */ 1972 if( linconss != NULL ) 1973 { 1974 SCIP_CALL( SCIPduplicateBufferArray(scip, &savelinconss, linconss, nlinconss) ); 1975 } 1976 1977 /* create new objective constraint */ 1978 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &objcons, "objcons", 0, NULL, NULL, objrhs, objrhs) ); 1979 if( SCIPisFeasNegative(scip, SCIPvarGetObj(objvar)) ) 1980 { 1981 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, 1.0) ); 1982 } 1983 else 1984 { 1985 SCIP_CALL( SCIPaddCoefLinear(scip, objcons, objvar, -1.0) ); 1986 } 1987 1988 /* handle linear constraints */ 1989 if( savelinconss != NULL ) 1990 { 1991 SCIP_CALL( presolveAddKKTLinearConss(scip, objcons, savelinconss, nlinconss, varhash, dualconss, &ndualconss, 1992 naddconss, ndelconss) ); 1993 } 1994 1995 /* handle set packing constraints */ 1996 SCIP_CALL( presolveAddKKTSetppcConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) ); 1997 1998 /* handle knapsack constraints */ 1999 SCIP_CALL( presolveAddKKTKnapsackConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) ); 2000 2001 /* handle varbound constraints */ 2002 SCIP_CALL( presolveAddKKTVarboundConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) ); 2003 2004 /* handle logicor constraints */ 2005 SCIP_CALL( presolveAddKKTLogicorConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) ); 2006 2007 /* handle linear constraints associated to aggregations of variables */ 2008 if( SCIPgetNFixedVars(scip) > 0 ) 2009 { 2010 SCIP_CALL( presolveAddKKTAggregatedVars(scip, objcons, SCIPgetFixedVars(scip), SCIPgetNFixedVars(scip), 2011 varhash, dualconss, &ndualconss, naddconss) ); 2012 } 2013 2014 /* handle bilinear terms of quadratic constraint */ 2015 SCIP_CALL( presolveAddKKTQuadBilinearTerms(scip, objcons, expr, varhash, scale, dualconss, &ndualconss, 2016 naddconss) ); 2017 2018 /* handle quadratic terms of quadratic constraint */ 2019 SCIP_CALL( presolveAddKKTQuadQuadraticTerms(scip, objcons, expr, varhash, scale, dualconss, &ndualconss, 2020 naddconss) ); 2021 2022 /* handle linear terms of quadratic constraint */ 2023 SCIP_CALL( presolveAddKKTQuadLinearTerms(scip, objcons, expr, varhash, objvar, scale, dualconss, &ndualconss, 2024 naddconss) ); 2025 2026 /* add/release objective constraint */ 2027 SCIP_CALL( SCIPaddCons(scip, objcons) ); 2028 SCIP_CALL( SCIPreleaseCons(scip, &objcons) ); 2029 ++(*naddconss); 2030 2031 /* add/release dual constraints associated to the KKT conditions */ 2032 for( j = 0; j < ndualconss; ++j ) 2033 { 2034 SCIP_CALL( SCIPaddCons(scip, dualconss[j]) ); 2035 SCIP_CALL( SCIPreleaseCons(scip, &dualconss[j]) ); 2036 } 2037 *naddconss = *naddconss + ndualconss; 2038 2039 /* free buffer array */ 2040 SCIPfreeBufferArrayNull(scip, &savelinconss); 2041 SCIPfreeBufferArray(scip, &dualconss); 2042 2043 /* free hash map */ 2044 SCIPhashmapFree(&varhash); 2045 2046 if( SCIPgetNBinVars(scip) > 0 ) 2047 SCIPdebugMsg(scip, "added the KKT conditions to the mixed-binary quadratic program\n"); 2048 else 2049 SCIPdebugMsg(scip, "added the KKT conditions to the quadratic program\n"); 2050 2051 /* SCIP_CALL( SCIPwriteTransProblem(scip, "trafoQP.lp", NULL, FALSE ) ); */ 2052 2053 return SCIP_OKAY; 2054 } 2055 2056 2057 /* 2058 * presolver specific interface methods 2059 */ 2060 2061 /** creates the QP KKT reformulation presolver and includes it in SCIP */ 2062 SCIP_RETCODE SCIPincludePresolQPKKTref( 2063 SCIP* scip /**< SCIP data structure */ 2064 ) 2065 { 2066 SCIP_PRESOLDATA* presoldata; 2067 SCIP_PRESOL* presol= NULL; 2068 2069 /* alloc presolve data object */ 2070 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) ); 2071 2072 /* include presolver */ 2073 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, 2074 PRESOL_TIMING, presolExecQPKKTref, presoldata) ); 2075 assert(presol != NULL); 2076 2077 /* set non fundamental callbacks via setter functions */ 2078 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyQPKKTref) ); 2079 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeQPKKTref) ); 2080 2081 /* add qpkktref presolver parameters */ 2082 SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/addkktbinary", 2083 "if TRUE then allow binary variables for KKT update", 2084 &presoldata->addkktbinary, TRUE, FALSE, NULL, NULL) ); 2085 2086 SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadbounded", 2087 "if TRUE then only apply the update to QPs with bounded variables; if the variables are not bounded then a " 2088 "finite optimal solution might not exist and the KKT conditions would then be invalid", 2089 &presoldata->updatequadbounded, TRUE, TRUE, NULL, NULL) ); 2090 2091 SCIP_CALL( SCIPaddBoolParam(scip, "presolving/" PRESOL_NAME "/updatequadindef", 2092 "if TRUE then apply quadratic constraint update even if the quadratic constraint matrix is known to be indefinite", 2093 &presoldata->updatequadindef, TRUE, FALSE, NULL, NULL) ); 2094 2095 return SCIP_OKAY; 2096 } 2097