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 pub_misc_rowprep.h 26 * @brief preparation of a linear inequality to become a SCIP_ROW 27 * @ingroup PUBLICCOREAPI 28 * @author Stefan Vigerske 29 * @author Benjamin Mueller 30 * @author Felipe Serrano 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #ifndef __SCIP_PUB_MISC_ROWPREP_H__ 36 #define __SCIP_PUB_MISC_ROWPREP_H__ 37 38 #include "scip/type_misc.h" 39 #include "scip/type_cons.h" 40 #include "scip/type_lp.h" 41 #include "scip/type_sepa.h" 42 #include "scip/type_var.h" 43 44 #ifdef NDEBUG 45 #include "scip/struct_misc.h" 46 #endif 47 48 #ifdef __cplusplus 49 extern "C" { 50 #endif 51 52 /**@defgroup RowPrep Linear Inequality 53 * @ingroup DataStructures 54 * @brief a linear inequality that is prepared to become a SCIP_ROW 55 * 56 * This data structure helps to work around some limitations of SCIP_ROW's, in particular, 57 * that it rounds coefficients or sides close to integral values without the appropriate care. 58 * On the other hand, a SCIP_ROWPREP is limited to inequalities. 59 * 60 *@{ 61 */ 62 63 /** creates a SCIP_ROWPREP datastructure 64 * 65 * Initial row represents 0 ≤ 0. 66 */ 67 SCIP_EXPORT 68 SCIP_RETCODE SCIPcreateRowprep( 69 SCIP* scip, /**< SCIP data structure */ 70 SCIP_ROWPREP** rowprep, /**< buffer to store pointer to rowprep */ 71 SCIP_SIDETYPE sidetype, /**< whether cut will be or lower-equal or larger-equal type */ 72 SCIP_Bool local /**< whether cut will be valid only locally */ 73 ); 74 75 /** frees a SCIP_ROWPREP datastructure */ 76 SCIP_EXPORT 77 void SCIPfreeRowprep( 78 SCIP* scip, /**< SCIP data structure */ 79 SCIP_ROWPREP** rowprep /**< pointer that stores pointer to rowprep */ 80 ); 81 82 /** creates a copy of a SCIP_ROWPREP datastructure */ 83 SCIP_EXPORT 84 SCIP_RETCODE SCIPcopyRowprep( 85 SCIP* scip, /**< SCIP data structure */ 86 SCIP_ROWPREP** target, /**< buffer to store pointer of rowprep copy */ 87 SCIP_ROWPREP* source /**< rowprep to copy */ 88 ); 89 90 /** gives number of terms in rowprep */ 91 SCIP_EXPORT 92 int SCIProwprepGetNVars( 93 SCIP_ROWPREP* rowprep /**< rowprep */ 94 ); 95 96 /** gives variables of rowprep (feel free to modify) */ 97 SCIP_EXPORT 98 SCIP_VAR** SCIProwprepGetVars( 99 SCIP_ROWPREP* rowprep /**< rowprep */ 100 ); 101 102 /** gives coefficients of rowprep (feel free to modify) */ 103 SCIP_EXPORT 104 SCIP_Real* SCIProwprepGetCoefs( 105 SCIP_ROWPREP* rowprep /**< rowprep */ 106 ); 107 108 /** gives side of rowprep */ 109 SCIP_EXPORT 110 SCIP_Real SCIProwprepGetSide( 111 SCIP_ROWPREP* rowprep /**< rowprep */ 112 ); 113 114 /** gives kind of inequality of rowprep */ 115 SCIP_EXPORT 116 SCIP_SIDETYPE SCIProwprepGetSidetype( 117 SCIP_ROWPREP* rowprep /**< rowprep */ 118 ); 119 120 /** returns whether rowprep is locally valid only */ 121 SCIP_EXPORT 122 SCIP_Bool SCIProwprepIsLocal( 123 SCIP_ROWPREP* rowprep /**< rowprep */ 124 ); 125 126 /** returns name of rowprep (feel free to modify) */ 127 SCIP_EXPORT 128 char* SCIProwprepGetName( 129 SCIP_ROWPREP* rowprep /**< rowprep */ 130 ); 131 132 /** returns number of variables which coefficients were modified in cleanup */ 133 SCIP_EXPORT 134 int SCIProwprepGetNModifiedVars( 135 SCIP_ROWPREP* rowprep /**< rowprep */ 136 ); 137 138 /** returns variables which coefficients were modified in cleanup */ 139 SCIP_EXPORT 140 SCIP_VAR** SCIProwprepGetModifiedVars( 141 SCIP_ROWPREP* rowprep /**< rowprep */ 142 ); 143 144 /** resets rowprep to have 0 terms and side 0.0 */ 145 SCIP_EXPORT 146 void SCIProwprepReset( 147 SCIP_ROWPREP* rowprep /**< rowprep */ 148 ); 149 150 /** sets coefficient idx of rowprep */ 151 SCIP_EXPORT 152 void SCIProwprepSetCoef( 153 SCIP_ROWPREP* rowprep, /**< rowprep */ 154 int idx, /**< index of coef to set */ 155 SCIP_Real newcoef /**< new coefficient */ 156 ); 157 158 /** adds constant value to side of rowprep */ 159 SCIP_EXPORT 160 void SCIProwprepAddSide( 161 SCIP_ROWPREP* rowprep, /**< rowprep */ 162 SCIP_Real side /**< constant value to be added to side */ 163 ); 164 165 /** adds constant term to rowprep 166 * 167 * Substracts constant from side. 168 */ 169 SCIP_EXPORT 170 void SCIProwprepAddConstant( 171 SCIP_ROWPREP* rowprep, /**< rowprep */ 172 SCIP_Real constant /**< constant value to be added */ 173 ); 174 175 /** sets side type of rowprep */ 176 SCIP_EXPORT 177 void SCIProwprepSetSidetype( 178 SCIP_ROWPREP* rowprep, /**< rowprep */ 179 SCIP_SIDETYPE sidetype /**< new side type */ 180 ); 181 182 /** sets whether rowprep is local */ 183 SCIP_EXPORT 184 void SCIProwprepSetLocal( 185 SCIP_ROWPREP* rowprep, /**< rowprep */ 186 SCIP_Bool islocal /**< whether rowprep is local */ 187 ); 188 189 /** enables recording for where modifications were done in cleanup */ 190 SCIP_EXPORT 191 void SCIProwprepRecordModifications( 192 SCIP_ROWPREP* rowprep /**< rowprep */ 193 ); 194 195 #ifdef NDEBUG 196 /* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and 197 * speed up the algorithms. 198 */ 199 #define SCIProwprepGetNVars(rowprep) (rowprep)->nvars 200 #define SCIProwprepGetVars(rowprep) (rowprep)->vars 201 #define SCIProwprepGetCoefs(rowprep) (rowprep)->coefs 202 #define SCIProwprepGetSide(rowprep) (rowprep)->side 203 #define SCIProwprepGetSidetype(rowprep) (rowprep)->sidetype 204 #define SCIProwprepIsLocal(rowprep) (rowprep)->local 205 #define SCIProwprepGetName(rowprep) (rowprep)->name 206 #define SCIProwprepGetNModifiedVars(rowprep) (rowprep)->nmodifiedvars 207 #define SCIProwprepGetModifiedVars(rowprep) (rowprep)->modifiedvars 208 #define SCIProwprepSetCoef(rowprep, idx, newcoef) ((rowprep)->coefs[idx] = (newcoef)) 209 #define SCIProwprepAddSide(rowprep, sideadd) ((rowprep)->side += (sideadd)) 210 #define SCIProwprepAddConstant(rowprep, constant) SCIProwprepAddSide(rowprep, -(constant)) 211 #define SCIProwprepSetSidetype(rowprep, sidetype_) (rowprep)->sidetype = sidetype_ 212 #define SCIProwprepSetLocal(rowprep, islocal) (rowprep)->local = islocal 213 #define SCIProwprepRecordModifications(rowprep) (rowprep)->recordmodifications = TRUE 214 #endif 215 216 /** prints a rowprep */ 217 SCIP_EXPORT 218 void SCIPprintRowprep( 219 SCIP* scip, /**< SCIP data structure */ 220 SCIP_ROWPREP* rowprep, /**< rowprep to be printed */ 221 FILE* file /**< file to print to, or NULL for stdout */ 222 ); 223 224 /** prints a rowprep and values in solution */ 225 SCIP_EXPORT 226 void SCIPprintRowprepSol( 227 SCIP* scip, /**< SCIP data structure */ 228 SCIP_ROWPREP* rowprep, /**< rowprep to be printed */ 229 SCIP_SOL* sol, /**< solution for activity */ 230 FILE* file /**< file to print to, or NULL for stdout */ 231 ); 232 233 /** ensures that rowprep has space for at least given number of additional terms 234 * 235 * Useful when knowing in advance how many terms will be added. 236 */ 237 SCIP_EXPORT 238 SCIP_RETCODE SCIPensureRowprepSize( 239 SCIP* scip, /**< SCIP data structure */ 240 SCIP_ROWPREP* rowprep, /**< rowprep */ 241 int size /**< number of additional terms for which to alloc space in rowprep */ 242 ); 243 244 /** adds a term coef*var to a rowprep */ 245 SCIP_EXPORT 246 SCIP_RETCODE SCIPaddRowprepTerm( 247 SCIP* scip, /**< SCIP data structure */ 248 SCIP_ROWPREP* rowprep, /**< rowprep */ 249 SCIP_VAR* var, /**< variable to add */ 250 SCIP_Real coef /**< coefficient to add */ 251 ); 252 253 /** adds several terms coef*var to a rowprep */ 254 SCIP_EXPORT 255 SCIP_RETCODE SCIPaddRowprepTerms( 256 SCIP* scip, /**< SCIP data structure */ 257 SCIP_ROWPREP* rowprep, /**< rowprep */ 258 int nvars, /**< number of terms to add */ 259 SCIP_VAR** vars, /**< variables to add */ 260 SCIP_Real* coefs /**< coefficients to add */ 261 ); 262 263 /** computes violation of rowprep in a given solution 264 * 265 * Can return whether the violation value is reliable from a floating-point accuracy point of view. 266 * The value will not be deemed reliable when its calculation involved the subtraction of large numbers. 267 * To be precise, the violation of an inequality \f$ \sum_i a_ix_i \leq b \f$ in a solution \f$x^*\f$ is deemed 268 * reliable if \f$ |\sum_i a_ix^*_i - b| \geq 2^{-50} \max (|b|, \max_i |a_ix^*_i|) \f$. 269 */ 270 SCIP_EXPORT 271 SCIP_Real SCIPgetRowprepViolation( 272 SCIP* scip, /**< SCIP data structure */ 273 SCIP_ROWPREP* rowprep, /**< rowprep */ 274 SCIP_SOL* sol, /**< solution or NULL for LP solution */ 275 SCIP_Bool* reliable /**< buffer to store whether computed violation is reliable (numerically), or NULL if not of interest */ 276 ); 277 278 /** computes violation of rowprep in a given solution and reports whether that value seem numerically reliable 279 * 280 * @see SCIPgetRowprepViolation() 281 */ 282 SCIP_EXPORT 283 SCIP_Bool SCIPisRowprepViolationReliable( 284 SCIP* scip, /**< SCIP data structure */ 285 SCIP_ROWPREP* rowprep, /**< rowprep */ 286 SCIP_SOL* sol /**< solution or NULL for LP solution */ 287 ); 288 289 /** Merge terms that use same variable and eliminate zero coefficients. 290 * 291 * Removes a variable if its bounds have a relative difference of below epsilon. 292 * Local bounds are checked for local rows, otherwise global bounds are used. 293 * If the bounds are not absolute equal, the bound that relaxes the row is used. 294 * 295 * Terms are sorted by variable (see SCIPvarComp()) after return. 296 */ 297 SCIP_EXPORT 298 void SCIPmergeRowprepTerms( 299 SCIP* scip, /**< SCIP data structure */ 300 SCIP_ROWPREP* rowprep /**< rowprep to be cleaned up */ 301 ); 302 303 /** Cleans up and attempts to improve rowprep 304 * 305 * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol, 306 * if this can be done by relaxing the row. 307 * Scales coefficients up to reach minimal violation, if possible. 308 * Scaling is omitted if violation is very small (\ref ROWPREP_SCALEUP_VIOLNONZERO) or 309 * maximal coefficient would become huge (\ref ROWPREP_SCALEUP_MAXMAXCOEF). 310 * Scales coefficients and side down if they are large and if the minimal violation is still reached. 311 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row. 312 * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least. 313 * 314 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order. 315 * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0). 316 * 317 * `success` is set to TRUE if and only if the rowprep satisfies the following: 318 * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol 319 * - the violation is at least `minviol` 320 * - the violation is reliable or `minviol` = 0 321 * - the absolute value of coefficients are below SCIPinfinity() 322 * - the absolute value of the side is below SCIPinfinity() 323 */ 324 SCIP_EXPORT 325 SCIP_RETCODE SCIPcleanupRowprep( 326 SCIP* scip, /**< SCIP data structure */ 327 SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */ 328 SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */ 329 SCIP_Real minviol, /**< minimal absolute violation the row should achieve (w.r.t. sol) */ 330 SCIP_Real* viol, /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */ 331 SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */ 332 ); 333 334 /** Cleans up and attempts to improve rowprep without regard for violation 335 * 336 * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol, 337 * if this can be done by relaxing the row. 338 * Scales coefficients and side to have maximal coefficient in `[1/maxcoefbound,maxcoefbound]`. 339 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row. 340 * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least. 341 * 342 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order. 343 * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0). 344 * 345 * `success` is set to TRUE if and only if the rowprep satisfies the following: 346 * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol 347 * - the absolute value of coefficients are below SCIPinfinity() 348 * - the absolute value of the side is below SCIPinfinity() 349 * 350 * In difference to SCIPcleanupRowprep(), this function does not scale up the row to increase the absolute violation. 351 */ 352 SCIP_EXPORT 353 SCIP_RETCODE SCIPcleanupRowprep2( 354 SCIP* scip, /**< SCIP data structure */ 355 SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */ 356 SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */ 357 SCIP_Real maxcoefbound, /**< bound on absolute value of largest coefficient */ 358 SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */ 359 ); 360 361 /** Scales up a rowprep to increase coefficients/sides that are within epsilon to an integer value, if possible. 362 * 363 * Computes the minimal fractionality of all fractional coefficients and the side of the rowprep. 364 * If this fractionality is below epsilon, the rowprep is scaled up such that the fractionality exceeds epsilon, 365 * if this will not put any coefficient or side above SCIPhugeValue(). 366 * 367 * This function does not relax the rowprep. 368 * 369 * `success` is set to TRUE if the resulting rowprep can be turned into a SCIP_ROW, that is, 370 * all coefs and the side is below SCIPinfinity() and fractionalities are above epsilon. 371 * If `success` is set to FALSE, then the rowprep will not have been modified. 372 * 373 * @return The applied scaling factor, if `success` is set to TRUE. 374 */ 375 SCIP_EXPORT 376 SCIP_Real SCIPscaleupRowprep( 377 SCIP* scip, /**< SCIP data structure */ 378 SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */ 379 SCIP_Real minscaleup, /**< minimal factor by which to scale up row, or <= 1.0 if to be ignored */ 380 SCIP_Bool* success /**< buffer to store whether rowprep could be turned into SCIP_ROW without loss, or NULL if not of interest */ 381 ); 382 383 /** scales a rowprep by given factor (after some rounding) 384 * 385 * @return Exponent of actually applied scaling factor, if written as \f$2^x\f$. 386 */ 387 SCIP_EXPORT 388 int SCIPscaleRowprep( 389 SCIP_ROWPREP* rowprep, /**< rowprep to be scaled */ 390 SCIP_Real factor /**< suggested scale factor */ 391 ); 392 393 /** generates a SCIP_ROW from a rowprep, setting its origin to given constraint handler */ 394 SCIP_EXPORT 395 SCIP_RETCODE SCIPgetRowprepRowConshdlr( 396 SCIP* scip, /**< SCIP data structure */ 397 SCIP_ROW** row, /**< buffer to store pointer to new row */ 398 SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ 399 SCIP_CONSHDLR* conshdlr /**< constraint handler */ 400 ); 401 402 /** generates a SCIP_ROW from a rowprep, setting its origin to given constraint */ 403 SCIP_EXPORT 404 SCIP_RETCODE SCIPgetRowprepRowCons( 405 SCIP* scip, /**< SCIP data structure */ 406 SCIP_ROW** row, /**< buffer to store pointer to new row */ 407 SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ 408 SCIP_CONS* cons /**< constraint */ 409 ); 410 411 /** generates a SCIP_ROW from a rowprep, setting its origin to given separator */ 412 SCIP_EXPORT 413 SCIP_RETCODE SCIPgetRowprepRowSepa( 414 SCIP* scip, /**< SCIP data structure */ 415 SCIP_ROW** row, /**< buffer to store pointer to new row */ 416 SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ 417 SCIP_SEPA* sepa /**< separator */ 418 ); 419 420 /** @} */ 421 422 #ifdef __cplusplus 423 } 424 #endif 425 426 #endif /* __SCIP_PUB_MISC_ROWPREP_H__ */ 427