1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file cons_quadratic.h 17 * @ingroup CONSHDLRS 18 * @brief constraint handler for quadratic constraints \f$\textrm{lhs} \leq \sum_{i,j=1}^n a_{i,j} x_ix_j + \sum_{i=1}^n b_i x_i \leq \textrm{rhs}\f$ 19 * @author Stefan Vigerske 20 * 21 */ 22 23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 24 25 #ifndef __SCIP_CONS_QUADRATIC_H__ 26 #define __SCIP_CONS_QUADRATIC_H__ 27 28 #include "scip/def.h" 29 #include "scip/type_cons.h" 30 #include "scip/type_lp.h" 31 #include "scip/type_misc.h" 32 #include "scip/type_nlp.h" 33 #include "nlpi/type_nlpi.h" 34 #include "scip/type_retcode.h" 35 #include "scip/type_scip.h" 36 #include "scip/type_sepa.h" 37 #include "scip/type_sol.h" 38 #include "scip/type_timing.h" 39 #include "scip/type_var.h" 40 41 #ifdef __cplusplus 42 extern "C" { 43 #endif 44 45 46 /** creates the handler for quadratic constraints and includes it in SCIP 47 * 48 * @ingroup ConshdlrIncludes 49 * */ 50 SCIP_EXPORT 51 SCIP_RETCODE SCIPincludeConshdlrQuadratic( 52 SCIP* scip /**< SCIP data structure */ 53 ); 54 55 /**@addtogroup CONSHDLRS 56 * 57 * @{ 58 * 59 * @name Quadratic Constraints 60 * 61 * @{ 62 * 63 * This constraint handler handles constraints of the form 64 * \f[ 65 * \textrm{lhs} \leq \sum_{i,j=1}^n a_{i,j} x_ix_j + \sum_{i=1}^n b_i x_i \leq \textrm{rhs} 66 * \f] 67 * 68 * Constraints are enforced by separation, domain propagation, and spatial branching. 69 * 70 * For semidefinite matrices \f$A=(a_{i,j})_{i,j}\f$, cuts based on linearization of \f$\langle x, Ax\rangle\f$ are implemented. 71 * For underestimating a non-convex term, McCormick underestimators and secants for univariate concave quadratic terms are implemented. 72 * If \f$\langle x, Ax\rangle\f$ is factorable (i.e., can be written as product of two linear functions), 73 * specialized separation techniques (e.g., lifted tangent inequalities) that take the constraint sides into account are applied. 74 * 75 * Branching is performed for variables in nonconvex terms, if the relaxation solution cannot be separated. 76 * Further, domain propagation is applied. 77 * 78 * During presolve, variable products which contain binary variables may be reformulated into linear constraints, thereby introducing new variables. 79 * 80 * See also 81 * @par 82 * Timo Berthold and Stefan Heinz and Stefan Vigerske@n 83 * <a href="http://dx.doi.org/10.1007/978-1-4614-1927-3">Extending a CIP framework to solve MIQCPs</a>@n 84 * In: Jon Lee and Sven Leyffer (eds.), 85 * Mixed-integer nonlinear optimization: Algorithmic advances and applications, 86 * IMA volumes in Mathematics and its Applications, volume 154, 427-444, 2012. 87 * 88 * @par 89 * Stefan Vigerske@n 90 * Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming@n 91 * PhD Thesis, Humboldt-University Berlin, 2012, submitted. 92 * 93 * @par 94 * Pietro Belotti and Andrew J. Miller and Mahdi Namazifar@n 95 * Linear inequalities for bounded products of variables@n 96 * SIAG/OPT Views-and-News 22:1, 1-8, 2011. 97 */ 98 99 /** event data for variable bound changes in quadratic constraints */ 100 typedef struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA; 101 102 /** data structure to store a single term associated to a quadratic variable 103 */ 104 struct SCIP_QuadVarTerm 105 { 106 SCIP_VAR* var; /**< quadratic variable */ 107 SCIP_Real lincoef; /**< linear coefficient of variable */ 108 SCIP_Real sqrcoef; /**< square coefficient of variable */ 109 110 int nadjbilin; /**< number of bilinear terms this variable is involved in */ 111 int adjbilinsize; /**< size of adjacent bilinear terms array */ 112 int* adjbilin; /**< indices of associated bilinear terms */ 113 114 SCIP_QUADVAREVENTDATA* eventdata; /**< event data for bound change events */ 115 }; 116 typedef struct SCIP_QuadVarTerm SCIP_QUADVARTERM; 117 118 /** data structure to store a single bilinear term (similar to SCIP_QUADELEM) 119 * except for temporary reasons, we assume that the index of var1 is smaller than the index of var2 120 */ 121 struct SCIP_BilinTerm 122 { 123 SCIP_VAR* var1; 124 SCIP_VAR* var2; 125 SCIP_Real coef; 126 }; 127 typedef struct SCIP_BilinTerm SCIP_BILINTERM; 128 129 /** storage for a linear row in preparation 130 * 131 * Uses to assemble data that could eventually make a SCIP_ROW. 132 * @note Only one-sided rows are allowed here. 133 */ 134 struct SCIP_RowPrep 135 { 136 SCIP_VAR** vars; /**< variables */ 137 SCIP_Real* coefs; /**< coefficients of variables */ 138 int nvars; /**< number of variables (= number of coefficients) */ 139 int varssize; /**< length of variables array (= lengths of coefficients array) */ 140 SCIP_Real side; /**< side */ 141 SCIP_SIDETYPE sidetype; /**< type of side */ 142 SCIP_Bool local; /**< whether the row is only locally valid (i.e., for the current node) */ 143 char name[SCIP_MAXSTRLEN]; /**< row name */ 144 }; 145 typedef struct SCIP_RowPrep SCIP_ROWPREP; 146 147 /** upgrading method for quadratic constraints into more specific constraints 148 * 149 * the method might upgrade a quadratic constraint into a set of quadratic constraints 150 * the caller provided an array upgdconss to store upgrade constraints 151 * the length of upgdconss is given by upgdconsssize 152 * if an upgrade is not possible, set *nupgdconss to zero 153 * if more than upgdconsssize many constraints shall replace cons, the function 154 * should return the required number as negated value in *nupgdconss 155 * i.e., if cons should be replaced by 3 constraints, the function should set 156 * *nupgdconss to -3 and return with SCIP_OKAY 157 * 158 * input: 159 * - scip : SCIP main data structure 160 * - cons : the quadratic constraint to upgrade 161 * - nbinlin : number of binary variables in linear part 162 * - nbinquad : number of binary variables in quadratic part 163 * - nintlin : number of integer variables in linear part 164 * - nintquad : number of integer variables in quadratic part 165 * - nimpllin : number of implicit integer variables in linear part 166 * - nimplquad : number of implicit integer variables in quadratic part 167 * - ncontlin : number of continuous variables in linear part 168 * - ncontquad : number of continuous variables in quadratic part 169 * - integral : TRUE iff constraints activity value is always integral 170 * - nupgdconss : pointer to store number of constraints that replace this constraint 171 * - upgdconss : array to store constraints that replace this constraint 172 * - upgdconsssize : length of the provided upgdconss array 173 * - presoltiming : current presolve timing 174 */ 175 #define SCIP_DECL_QUADCONSUPGD(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, \ 176 int nbinlin, int nbinquad, int nintlin, int nintquad, int nimpllin, int nimplquad, int ncontlin, int ncontquad, \ 177 SCIP_Bool integral, int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize, SCIP_PRESOLTIMING presoltiming) 178 179 /** includes a quadratic constraint upgrade method into the quadratic constraint handler */ 180 SCIP_EXPORT 181 SCIP_RETCODE SCIPincludeQuadconsUpgrade( 182 SCIP* scip, /**< SCIP data structure */ 183 SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), /**< method to call for upgrading quadratic constraint */ 184 int priority, /**< priority of upgrading method */ 185 SCIP_Bool active, /**< should the upgrading method be active by default? */ 186 const char* conshdlrname /**< name of the constraint handler */ 187 ); 188 189 /** Creates and captures a quadratic constraint. 190 * 191 * The constraint should be given in the form 192 * \f[ 193 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_j z_j \leq u, 194 * \f] 195 * where \f$x_i = y_j = z_k\f$ is possible. 196 * 197 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 198 */ 199 SCIP_EXPORT 200 SCIP_RETCODE SCIPcreateConsQuadratic( 201 SCIP* scip, /**< SCIP data structure */ 202 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 203 const char* name, /**< name of constraint */ 204 int nlinvars, /**< number of linear terms (n) */ 205 SCIP_VAR** linvars, /**< variables in linear part (x_i) or NULL if nlinvars == 0 */ 206 SCIP_Real* lincoefs, /**< coefficients of variables in linear part (b_i) or NULL if nlinvars == 0 */ 207 int nquadterms, /**< number of quadratic terms (m) */ 208 SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) or NULL if nquadterms == 0 */ 209 SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) or NULL if nquadterms == 0 */ 210 SCIP_Real* quadcoeffs, /**< array with coefficients of quadratic terms (a_j) or NULL if nquadterms == 0 */ 211 SCIP_Real lhs, /**< left hand side of quadratic equation (l) */ 212 SCIP_Real rhs, /**< right hand side of quadratic equation (u) */ 213 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 214 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 215 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 216 * Usually set to TRUE. */ 217 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 218 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 219 SCIP_Bool check, /**< should the constraint be checked for feasibility? 220 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 221 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 222 * Usually set to TRUE. */ 223 SCIP_Bool local, /**< is constraint only valid locally? 224 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 225 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 226 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 227 * adds coefficients to this constraint. */ 228 SCIP_Bool dynamic, /**< is constraint subject to aging? 229 * Usually set to FALSE. Set to TRUE for own cuts which 230 * are separated as constraints. */ 231 SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup? 232 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 233 ); 234 235 /** creates and captures a quadratic constraint 236 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set 237 * afterwards using SCIPsetConsFLAGNAME() in scip.h 238 * 239 * The constraint should be given in the form 240 * \f[ 241 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m a_j y_jz_j \leq u, 242 * \f] 243 * where \f$x_i = y_j = z_k\f$ is possible. 244 * 245 * @see SCIPcreateConsQuadratic() for the default constraint flag configuration 246 * 247 248 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 249 */ 250 SCIP_EXPORT 251 SCIP_RETCODE SCIPcreateConsBasicQuadratic( 252 SCIP* scip, /**< SCIP data structure */ 253 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 254 const char* name, /**< name of constraint */ 255 int nlinvars, /**< number of linear terms (n) */ 256 SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */ 257 SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */ 258 int nquadterms, /**< number of quadratic terms (m) */ 259 SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) */ 260 SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) */ 261 SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms (a_j) */ 262 SCIP_Real lhs, /**< left hand side of quadratic equation (ell) */ 263 SCIP_Real rhs /**< right hand side of quadratic equation (u) */ 264 ); 265 266 /** creates and captures a quadratic constraint. 267 * 268 * The constraint should be given in the form 269 * \f[ 270 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_k v_k w_k \leq u. 271 * \f] 272 * 273 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 274 */ 275 SCIP_EXPORT 276 SCIP_RETCODE SCIPcreateConsQuadratic2( 277 SCIP* scip, /**< SCIP data structure */ 278 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 279 const char* name, /**< name of constraint */ 280 int nlinvars, /**< number of linear terms (n) */ 281 SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */ 282 SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */ 283 int nquadvarterms, /**< number of quadratic terms (m) */ 284 SCIP_QUADVARTERM* quadvarterms, /**< quadratic variable terms */ 285 int nbilinterms, /**< number of bilinear terms (p) */ 286 SCIP_BILINTERM* bilinterms, /**< bilinear terms */ 287 SCIP_Real lhs, /**< constraint left hand side (ell) */ 288 SCIP_Real rhs, /**< constraint right hand side (u) */ 289 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */ 290 SCIP_Bool separate, /**< should the constraint be separated during LP processing? */ 291 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */ 292 SCIP_Bool check, /**< should the constraint be checked for feasibility? */ 293 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */ 294 SCIP_Bool local, /**< is constraint only valid locally? */ 295 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */ 296 SCIP_Bool dynamic, /**< is constraint dynamic? */ 297 SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */ 298 ); 299 300 /** creates and captures a quadratic constraint 301 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set 302 * afterwards using SCIPsetConsFLAGNAME() in scip.h 303 * 304 * The constraint should be given in the form 305 * \f[ 306 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_kv_kw_k \leq u. 307 * \f] 308 * 309 * @see SCIPcreateConsQuadratic2() for the default constraint flag configuration 310 * 311 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 312 */ 313 SCIP_EXPORT 314 SCIP_RETCODE SCIPcreateConsBasicQuadratic2( 315 SCIP* scip, /**< SCIP data structure */ 316 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 317 const char* name, /**< name of constraint */ 318 int nlinvars, /**< number of linear terms (n) */ 319 SCIP_VAR** linvars, /**< array with variables in linear part (x_i) */ 320 SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part (b_i) */ 321 int nquadvarterms, /**< number of quadratic terms (m) */ 322 SCIP_QUADVARTERM* quadvarterms, /**< quadratic variable terms */ 323 int nbilinterms, /**< number of bilinear terms (p) */ 324 SCIP_BILINTERM* bilinterms, /**< bilinear terms */ 325 SCIP_Real lhs, /**< constraint left hand side (ell) */ 326 SCIP_Real rhs /**< constraint right hand side (u) */ 327 ); 328 329 /** Adds a constant to the constraint function, that is, subtracts a constant from both sides */ 330 SCIP_EXPORT 331 void SCIPaddConstantQuadratic( 332 SCIP* scip, /**< SCIP data structure */ 333 SCIP_CONS* cons, /**< constraint */ 334 SCIP_Real constant /**< constant to subtract from both sides */ 335 ); 336 337 /** Adds a linear variable with coefficient to a quadratic constraint. 338 */ 339 SCIP_EXPORT 340 SCIP_RETCODE SCIPaddLinearVarQuadratic( 341 SCIP* scip, /**< SCIP data structure */ 342 SCIP_CONS* cons, /**< constraint */ 343 SCIP_VAR* var, /**< variable */ 344 SCIP_Real coef /**< coefficient of variable */ 345 ); 346 347 /** Adds a quadratic variable with linear and square coefficient to a quadratic constraint. 348 */ 349 SCIP_EXPORT 350 SCIP_RETCODE SCIPaddQuadVarQuadratic( 351 SCIP* scip, /**< SCIP data structure */ 352 SCIP_CONS* cons, /**< constraint */ 353 SCIP_VAR* var, /**< variable */ 354 SCIP_Real lincoef, /**< linear coefficient of variable */ 355 SCIP_Real sqrcoef /**< square coefficient of variable */ 356 ); 357 358 /** Adds a linear coefficient for a quadratic variable. 359 * 360 * Variable will be added with square coefficient 0.0 if not existing yet. 361 */ 362 SCIP_EXPORT 363 SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic( 364 SCIP* scip, /**< SCIP data structure */ 365 SCIP_CONS* cons, /**< constraint */ 366 SCIP_VAR* var, /**< variable */ 367 SCIP_Real coef /**< value to add to linear coefficient of variable */ 368 ); 369 370 /** Adds a square coefficient for a quadratic variable. 371 * 372 * Variable will be added with linear coefficient 0.0 if not existing yet. 373 */ 374 SCIP_EXPORT 375 SCIP_RETCODE SCIPaddSquareCoefQuadratic( 376 SCIP* scip, /**< SCIP data structure */ 377 SCIP_CONS* cons, /**< constraint */ 378 SCIP_VAR* var, /**< variable */ 379 SCIP_Real coef /**< value to add to square coefficient of variable */ 380 ); 381 382 /** Adds a bilinear term to a quadratic constraint. 383 * 384 * Variables will be added with linear and square coefficient 0.0 if not existing yet. 385 * If variables are equal, only the square coefficient of the variable is updated. 386 */ 387 SCIP_EXPORT 388 SCIP_RETCODE SCIPaddBilinTermQuadratic( 389 SCIP* scip, /**< SCIP data structure */ 390 SCIP_CONS* cons, /**< constraint */ 391 SCIP_VAR* var1, /**< first variable */ 392 SCIP_VAR* var2, /**< second variable */ 393 SCIP_Real coef /**< coefficient of bilinear term */ 394 ); 395 396 /** Gets the quadratic constraint as a nonlinear row representation. 397 */ 398 SCIP_EXPORT 399 SCIP_RETCODE SCIPgetNlRowQuadratic( 400 SCIP* scip, /**< SCIP data structure */ 401 SCIP_CONS* cons, /**< constraint */ 402 SCIP_NLROW** nlrow /**< pointer to store nonlinear row */ 403 ); 404 405 /** Gets the number of variables in the linear part of a quadratic constraint. 406 */ 407 SCIP_EXPORT 408 int SCIPgetNLinearVarsQuadratic( 409 SCIP* scip, /**< SCIP data structure */ 410 SCIP_CONS* cons /**< constraint */ 411 ); 412 413 /** Gets the variables in the linear part of a quadratic constraint. 414 * Length is given by SCIPgetNLinearVarsQuadratic. 415 */ 416 SCIP_EXPORT 417 SCIP_VAR** SCIPgetLinearVarsQuadratic( 418 SCIP* scip, /**< SCIP data structure */ 419 SCIP_CONS* cons /**< constraint */ 420 ); 421 422 /** Gets the coefficients in the linear part of a quadratic constraint. 423 * Length is given by SCIPgetNLinearVarsQuadratic. 424 */ 425 SCIP_EXPORT 426 SCIP_Real* SCIPgetCoefsLinearVarsQuadratic( 427 SCIP* scip, /**< SCIP data structure */ 428 SCIP_CONS* cons /**< constraint */ 429 ); 430 431 /** Gets the number of quadratic variable terms of a quadratic constraint. 432 */ 433 SCIP_EXPORT 434 int SCIPgetNQuadVarTermsQuadratic( 435 SCIP* scip, /**< SCIP data structure */ 436 SCIP_CONS* cons /**< constraint */ 437 ); 438 439 /** Gets the quadratic variable terms of a quadratic constraint. 440 * Length is given by SCIPgetNQuadVarTermsQuadratic. 441 */ 442 SCIP_EXPORT 443 SCIP_QUADVARTERM* SCIPgetQuadVarTermsQuadratic( 444 SCIP* scip, /**< SCIP data structure */ 445 SCIP_CONS* cons /**< constraint */ 446 ); 447 448 /** Ensures that quadratic variable terms are sorted. */ 449 SCIP_EXPORT 450 SCIP_RETCODE SCIPsortQuadVarTermsQuadratic( 451 SCIP* scip, /**< SCIP data structure */ 452 SCIP_CONS* cons /**< constraint */ 453 ); 454 455 /** Finds the position of a quadratic variable term for a given variable. 456 * 457 * @note If the quadratic variable terms have not been sorted before, then a search may reorder the current order of the terms. 458 */ 459 SCIP_EXPORT 460 SCIP_RETCODE SCIPfindQuadVarTermQuadratic( 461 SCIP* scip, /**< SCIP data structure */ 462 SCIP_CONS* cons, /**< constraint */ 463 SCIP_VAR* var, /**< variable to search for */ 464 int* pos /**< buffer to store position of quadvarterm for var, or -1 if not found */ 465 ); 466 467 /** Gets the number of bilinear terms of a quadratic constraint. 468 */ 469 SCIP_EXPORT 470 int SCIPgetNBilinTermsQuadratic( 471 SCIP* scip, /**< SCIP data structure */ 472 SCIP_CONS* cons /**< constraint */ 473 ); 474 475 /** Gets the bilinear terms of a quadratic constraint. 476 * Length is given by SCIPgetNBilinTermQuadratic. 477 */ 478 SCIP_EXPORT 479 SCIP_BILINTERM* SCIPgetBilinTermsQuadratic( 480 SCIP* scip, /**< SCIP data structure */ 481 SCIP_CONS* cons /**< constraint */ 482 ); 483 484 /** Gets the left hand side of a quadratic constraint. 485 */ 486 SCIP_EXPORT 487 SCIP_Real SCIPgetLhsQuadratic( 488 SCIP* scip, /**< SCIP data structure */ 489 SCIP_CONS* cons /**< constraint */ 490 ); 491 492 /** Gets the right hand side of a quadratic constraint. 493 */ 494 SCIP_EXPORT 495 SCIP_Real SCIPgetRhsQuadratic( 496 SCIP* scip, /**< SCIP data structure */ 497 SCIP_CONS* cons /**< constraint */ 498 ); 499 500 /** get index of a variable in linvars that may be decreased without making any other constraint infeasible, or -1 if none */ 501 SCIP_EXPORT 502 int SCIPgetLinvarMayDecreaseQuadratic( 503 SCIP* scip, /**< SCIP data structure */ 504 SCIP_CONS* cons /**< constraint */ 505 ); 506 507 /** get index of a variable in linvars that may be increased without making any other constraint infeasible, or -1 if none */ 508 SCIP_EXPORT 509 int SCIPgetLinvarMayIncreaseQuadratic( 510 SCIP* scip, /**< SCIP data structure */ 511 SCIP_CONS* cons /**< constraint */ 512 ); 513 514 /** Check the quadratic function of a quadratic constraint for its semi-definiteness, if not done yet. 515 */ 516 SCIP_EXPORT 517 SCIP_RETCODE SCIPcheckCurvatureQuadratic( 518 SCIP* scip, /**< SCIP data structure */ 519 SCIP_CONS* cons /**< constraint */ 520 ); 521 522 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) convex. 523 */ 524 SCIP_EXPORT 525 SCIP_Bool SCIPisConvexQuadratic( 526 SCIP* scip, /**< SCIP data structure */ 527 SCIP_CONS* cons /**< constraint */ 528 ); 529 530 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) concave. 531 */ 532 SCIP_EXPORT 533 SCIP_Bool SCIPisConcaveQuadratic( 534 SCIP* scip, /**< SCIP data structure */ 535 SCIP_CONS* cons /**< constraint */ 536 ); 537 538 /** Checks and indicates whether the quadratic constraint is convex. */ 539 SCIP_EXPORT 540 SCIP_RETCODE SCIPisConvexConsQuadratic( 541 SCIP* scip, /**< SCIP data structure */ 542 SCIP_CONS* cons, /**< constraint */ 543 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */ 544 SCIP_Bool* result /**< buffer where to store whether constraint is convex (under given variable fixing) */ 545 ); 546 547 /** Gets the violation of a constraint by a solution. */ 548 SCIP_EXPORT 549 SCIP_RETCODE SCIPgetViolationQuadratic( 550 SCIP* scip, /**< SCIP data structure */ 551 SCIP_CONS* cons, /**< constraint */ 552 SCIP_SOL* sol, /**< solution which violation to calculate, or NULL for LP solution */ 553 SCIP_Real* violation /**< pointer to store violation of constraint */ 554 ); 555 556 /** Indicates whether the quadratic constraint is local w.r.t. the current local bounds. 557 * 558 * That is, checks whether each variable with a square term is fixed and for each bilinear term at least one variable is fixed. 559 */ 560 SCIP_EXPORT 561 SCIP_Bool SCIPisLinearLocalQuadratic( 562 SCIP* scip, /**< SCIP data structure */ 563 SCIP_CONS* cons /**< constraint */ 564 ); 565 566 /** Adds the constraint to an NLPI problem. */ 567 SCIP_EXPORT 568 SCIP_RETCODE SCIPaddToNlpiProblemQuadratic( 569 SCIP* scip, /**< SCIP data structure */ 570 SCIP_CONS* cons, /**< constraint */ 571 SCIP_NLPI* nlpi, /**< interface to NLP solver */ 572 SCIP_NLPIPROBLEM* nlpiprob, /**< NLPI problem where to add constraint */ 573 SCIP_HASHMAP* scipvar2nlpivar, /**< mapping from SCIP variables to variable indices in NLPI */ 574 SCIP_Bool names /**< whether to pass constraint names to NLPI */ 575 ); 576 577 /** sets the left hand side of a quadratic constraint 578 * 579 * @note This method may only be called during problem creation stage for an original constraint. 580 */ 581 SCIP_EXPORT 582 SCIP_RETCODE SCIPchgLhsQuadratic( 583 SCIP* scip, /**< SCIP data structure */ 584 SCIP_CONS* cons, /**< constraint data */ 585 SCIP_Real lhs /**< new left hand side */ 586 ); 587 588 /** sets the right hand side of a quadratic constraint 589 * 590 * @note This method may only be called during problem creation stage for an original constraint. 591 */ 592 SCIP_EXPORT 593 SCIP_RETCODE SCIPchgRhsQuadratic( 594 SCIP* scip, /**< SCIP data structure */ 595 SCIP_CONS* cons, /**< constraint data */ 596 SCIP_Real rhs /**< new right hand side */ 597 ); 598 599 SCIP_EXPORT 600 /** gets the feasibility of the quadratic constraint in the given solution */ 601 SCIP_RETCODE SCIPgetFeasibilityQuadratic( 602 SCIP* scip, /**< SCIP data structure */ 603 SCIP_CONS* cons, /**< constraint data */ 604 SCIP_SOL* sol, /**< solution, or NULL to use current node's solution */ 605 SCIP_Real* feasibility /**< pointer to store the feasibility */ 606 ); 607 608 /** gets the activity of the quadratic constraint in the given solution */ 609 SCIP_EXPORT 610 SCIP_RETCODE SCIPgetActivityQuadratic( 611 SCIP* scip, /**< SCIP data structure */ 612 SCIP_CONS* cons, /**< constraint data */ 613 SCIP_SOL* sol, /**< solution, or NULL to use current node's solution */ 614 SCIP_Real* activity /**< pointer to store the activity */ 615 ); 616 617 /** changes the linear coefficient value for a given quadratic variable in a quadratic constraint data; if not 618 * available, it adds it 619 * 620 * @note this is only allowed for original constraints and variables in problem creation stage 621 */ 622 SCIP_EXPORT 623 SCIP_RETCODE SCIPchgLinearCoefQuadratic( 624 SCIP* scip, /**< SCIP data structure */ 625 SCIP_CONS* cons, /**< constraint data */ 626 SCIP_VAR* var, /**< quadratic variable */ 627 SCIP_Real coef /**< new coefficient */ 628 ); 629 630 /** changes the square coefficient value for a given quadratic variable in a quadratic constraint data; if not 631 * available, it adds it 632 * 633 * @note this is only allowed for original constraints and variables in problem creation stage 634 */ 635 SCIP_EXPORT 636 SCIP_RETCODE SCIPchgSquareCoefQuadratic( 637 SCIP* scip, /**< SCIP data structure */ 638 SCIP_CONS* cons, /**< constraint data */ 639 SCIP_VAR* var, /**< quadratic variable */ 640 SCIP_Real coef /**< new coefficient */ 641 ); 642 643 /** changes the bilinear coefficient value for a given quadratic variable in a quadratic constraint data; if not 644 * available, it adds it 645 * 646 * @note this is only allowed for original constraints and variables in problem creation stage 647 */ 648 SCIP_EXPORT 649 SCIP_RETCODE SCIPchgBilinCoefQuadratic( 650 SCIP* scip, /**< SCIP data structure */ 651 SCIP_CONS* cons, /**< constraint */ 652 SCIP_VAR* var1, /**< first quadratic variable */ 653 SCIP_VAR* var2, /**< second quadratic variable */ 654 SCIP_Real coef /**< coefficient of bilinear term */ 655 ); 656 657 /** returns the total number of bilinear terms that are contained in all quadratic constraints */ 658 SCIP_EXPORT 659 int SCIPgetNAllBilinearTermsQuadratic( 660 SCIP* scip /**< SCIP data structure */ 661 ); 662 663 /** returns all bilinear terms that are contained in all quadratic constraints */ 664 SCIP_EXPORT 665 SCIP_RETCODE SCIPgetAllBilinearTermsQuadratic( 666 SCIP* scip, /**< SCIP data structure */ 667 SCIP_VAR** RESTRICT x, /**< array to store first variable of each bilinear term */ 668 SCIP_VAR** RESTRICT y, /**< array to second variable of each bilinear term */ 669 int* RESTRICT nbilinterms, /**< buffer to store the total number of bilinear terms */ 670 int* RESTRICT nunderests, /**< array to store the total number of constraints that require to underestimate a bilinear term */ 671 int* RESTRICT noverests, /**< array to store the total number of constraints that require to overestimate a bilinear term */ 672 SCIP_Real* maxnonconvexity /**< estimate of nonconvex eigenvalues of all quadratic constraints containing a bilinear term */ 673 ); 674 675 /** adds a globally valid inequality of the form xcoef x <= ycoef y + constant for a bilinear term (x,y) 676 * 677 * @note the indices of bilinear terms match with the entries of bilinear terms returned by SCIPgetAllBilinearTermsQuadratic 678 */ 679 SCIP_EXPORT 680 SCIP_RETCODE SCIPaddBilinearIneqQuadratic( 681 SCIP* scip, /**< SCIP data structure */ 682 SCIP_VAR* x, /**< first variable */ 683 SCIP_VAR* y, /**< second variable */ 684 int idx, /**< index of the bilinear term */ 685 SCIP_Real xcoef, /**< x coefficient */ 686 SCIP_Real ycoef, /**< y coefficient */ 687 SCIP_Real constant, /**< constant part */ 688 SCIP_Bool* success /**< buffer to store whether inequality has been accepted */ 689 ); 690 691 /** @} */ 692 693 694 #ifdef SCIP_PRIVATE_ROWPREP 695 696 /** creates a SCIP_ROWPREP datastructure 697 * 698 * Initial row represents 0 <= 0. 699 */ 700 SCIP_EXPORT 701 SCIP_RETCODE SCIPcreateRowprep( 702 SCIP* scip, /**< SCIP data structure */ 703 SCIP_ROWPREP** rowprep, /**< buffer to store pointer to rowprep */ 704 SCIP_SIDETYPE sidetype, /**< whether cut will be or lower-equal or larger-equal type */ 705 SCIP_Bool local /**< whether cut will be valid only locally */ 706 ); 707 708 /** frees a SCIP_ROWPREP datastructure */ 709 SCIP_EXPORT 710 void SCIPfreeRowprep( 711 SCIP* scip, /**< SCIP data structure */ 712 SCIP_ROWPREP** rowprep /**< pointer that stores pointer to rowprep */ 713 ); 714 715 /** creates a copy of a SCIP_ROWPREP datastructure */ 716 SCIP_EXPORT 717 SCIP_RETCODE SCIPcopyRowprep( 718 SCIP* scip, /**< SCIP data structure */ 719 SCIP_ROWPREP** target, /**< buffer to store pointer of rowprep copy */ 720 SCIP_ROWPREP* source /**< rowprep to copy */ 721 ); 722 723 /** ensures that rowprep has space for at least given number of additional terms 724 * 725 * Useful when knowing in advance how many terms will be added. 726 */ 727 SCIP_EXPORT 728 SCIP_RETCODE SCIPensureRowprepSize( 729 SCIP* scip, /**< SCIP data structure */ 730 SCIP_ROWPREP* rowprep, /**< rowprep */ 731 int size /**< number of additional terms for which to alloc space in rowprep */ 732 ); 733 734 /** prints a rowprep */ 735 SCIP_EXPORT 736 void SCIPprintRowprep( 737 SCIP* scip, /**< SCIP data structure */ 738 SCIP_ROWPREP* rowprep, /**< rowprep to be printed */ 739 FILE* file /**< file to print to, or NULL for stdout */ 740 ); 741 742 /** adds a term coef*var to a rowprep */ 743 SCIP_EXPORT 744 SCIP_RETCODE SCIPaddRowprepTerm( 745 SCIP* scip, /**< SCIP data structure */ 746 SCIP_ROWPREP* rowprep, /**< rowprep */ 747 SCIP_VAR* var, /**< variable to add */ 748 SCIP_Real coef /**< coefficient to add */ 749 ); 750 751 /** adds several terms coef*var to a rowprep */ 752 SCIP_EXPORT 753 SCIP_RETCODE SCIPaddRowprepTerms( 754 SCIP* scip, /**< SCIP data structure */ 755 SCIP_ROWPREP* rowprep, /**< rowprep */ 756 int nvars, /**< number of terms to add */ 757 SCIP_VAR** vars, /**< variables to add */ 758 SCIP_Real* coefs /**< coefficients to add */ 759 ); 760 761 /** adds constant value to side of rowprep */ 762 SCIP_EXPORT 763 void SCIPaddRowprepSide( 764 SCIP_ROWPREP* rowprep, /**< rowprep */ 765 SCIP_Real side /**< constant value to be added to side */ 766 ); 767 768 /** adds constant term to rowprep 769 * 770 * Substracts constant from side. 771 */ 772 SCIP_EXPORT 773 void SCIPaddRowprepConstant( 774 SCIP_ROWPREP* rowprep, /**< rowprep */ 775 SCIP_Real constant /**< constant value to be added */ 776 ); 777 778 #ifdef NDEBUG 779 #define SCIPaddRowprepSide(rowprep, sideadd) ((rowprep)->side += (sideadd)) 780 #define SCIPaddRowprepConstant(rowprep, constant) SCIPaddRowprepSide(rowprep, -(constant)) 781 #endif 782 783 /** computes violation of cut in a given solution */ 784 SCIP_EXPORT 785 SCIP_Real SCIPgetRowprepViolation( 786 SCIP* scip, /**< SCIP data structure */ 787 SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ 788 SCIP_SOL* sol /**< solution or NULL for LP solution */ 789 ); 790 791 /** Merge terms that use same variable and eliminate zero coefficients. 792 * 793 * Terms are sorted by variable (@see SCIPvarComp) after return. 794 */ 795 SCIP_EXPORT 796 void SCIPmergeRowprepTerms( 797 SCIP* scip, /**< SCIP data structure */ 798 SCIP_ROWPREP* rowprep /**< rowprep to be cleaned up */ 799 ); 800 801 /* Cleans up and attempts to improve rowprep 802 * 803 * Drops small or large coefficients if coefrange is too large, if this can be done by relaxing the cut. 804 * Scales coefficients up to reach minimal violation, if possible. 805 * Scaling is omitted if violation is very small (ROWPREP_SCALEUP_VIOLNONZERO) or 806 * maximal coefficient would become huge (ROWPREP_SCALEUP_MAXMAXCOEF). 807 * Scales coefficients and side down if they are large and if the minimal violation is still reached. 808 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the cut. 809 * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the cut least. 810 * 811 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order. 812 */ 813 SCIP_EXPORT 814 SCIP_RETCODE SCIPcleanupRowprep( 815 SCIP* scip, /**< SCIP data structure */ 816 SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */ 817 SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */ 818 SCIP_Real maxcoefrange, /**< maximal allowed coefficients range */ 819 SCIP_Real minviol, /**< minimal absolute violation the row should achieve (w.r.t. sol) */ 820 SCIP_Real* coefrange, /**< buffer to store coefrange of cleaned up cut, or NULL if not of interest */ 821 SCIP_Real* viol /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */ 822 ); 823 824 /** scales a rowprep 825 * 826 * @return Exponent of actually applied scaling factor, if written as 2^x. 827 */ 828 SCIP_EXPORT 829 int SCIPscaleRowprep( 830 SCIP_ROWPREP* rowprep, /**< rowprep to be scaled */ 831 SCIP_Real factor /**< suggested scale factor */ 832 ); 833 834 /** generates a SCIP_ROW from a rowprep */ 835 SCIP_EXPORT 836 SCIP_RETCODE SCIPgetRowprepRowConshdlr( 837 SCIP* scip, /**< SCIP data structure */ 838 SCIP_ROW** row, /**< buffer to store pointer to new row */ 839 SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ 840 SCIP_CONSHDLR* conshdlr /**< constraint handler */ 841 ); 842 843 /** generates a SCIP_ROW from a rowprep */ 844 SCIP_EXPORT 845 SCIP_RETCODE SCIPgetRowprepRowCons( 846 SCIP* scip, /**< SCIP data structure */ 847 SCIP_ROW** row, /**< buffer to store pointer to new row */ 848 SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ 849 SCIP_CONS* cons /**< constraint */ 850 ); 851 852 /** generates a SCIP_ROW from a rowprep */ 853 SCIP_EXPORT 854 SCIP_RETCODE SCIPgetRowprepRowSepa( 855 SCIP* scip, /**< SCIP data structure */ 856 SCIP_ROW** row, /**< buffer to store pointer to new row */ 857 SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ 858 SCIP_SEPA* sepa /**< separator */ 859 ); 860 861 #endif 862 863 /** @} */ 864 865 #ifdef __cplusplus 866 } 867 #endif 868 869 #endif 870