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_lp.h 26 * @ingroup PUBLICCOREAPI 27 * @brief public methods for LP management 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_PUB_LP_H__ 34 #define __SCIP_PUB_LP_H__ 35 36 37 #include "lpi/type_lpi.h" 38 #include "scip/def.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 #include "scip/type_misc.h" 44 45 #ifdef NDEBUG 46 #include "scip/struct_lp.h" 47 #endif 48 49 #ifdef __cplusplus 50 extern "C" { 51 #endif 52 53 54 /**@addtogroup PublicColumnMethods 55 * 56 * @{ 57 */ 58 59 /** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones 60 */ 61 SCIP_EXPORT 62 void SCIPcolSort( 63 SCIP_COL* col /**< column to be sorted */ 64 ); 65 66 /** gets objective value of column */ 67 SCIP_EXPORT 68 SCIP_Real SCIPcolGetObj( 69 SCIP_COL* col /**< LP column */ 70 ); 71 72 /** gets lower bound of column */ 73 SCIP_EXPORT 74 SCIP_Real SCIPcolGetLb( 75 SCIP_COL* col /**< LP column */ 76 ); 77 78 /** gets upper bound of column */ 79 SCIP_EXPORT 80 SCIP_Real SCIPcolGetUb( 81 SCIP_COL* col /**< LP column */ 82 ); 83 84 /** gets best bound of column with respect to the objective function */ 85 SCIP_EXPORT 86 SCIP_Real SCIPcolGetBestBound( 87 SCIP_COL* col /**< LP column */ 88 ); 89 90 /** gets the primal LP solution of a column */ 91 SCIP_EXPORT 92 SCIP_Real SCIPcolGetPrimsol( 93 SCIP_COL* col /**< LP column */ 94 ); 95 96 /** gets the minimal LP solution value, this column ever assumed */ 97 SCIP_EXPORT 98 SCIP_Real SCIPcolGetMinPrimsol( 99 SCIP_COL* col /**< LP column */ 100 ); 101 102 /** gets the maximal LP solution value, this column ever assumed */ 103 SCIP_EXPORT 104 SCIP_Real SCIPcolGetMaxPrimsol( 105 SCIP_COL* col /**< LP column */ 106 ); 107 108 /** gets the basis status of a column in the LP solution; only valid for LPs with status SCIP_LPSOLSTAT_OPTIMAL 109 * and with SCIPisLPSolBasic(scip) == TRUE; returns SCIP_BASESTAT_ZERO for columns not in the current SCIP_LP 110 */ 111 SCIP_EXPORT 112 SCIP_BASESTAT SCIPcolGetBasisStatus( 113 SCIP_COL* col /**< LP column */ 114 ); 115 116 /** gets variable this column represents */ 117 SCIP_EXPORT 118 SCIP_VAR* SCIPcolGetVar( 119 SCIP_COL* col /**< LP column */ 120 ); 121 122 /** gets unique index of col */ 123 SCIP_EXPORT 124 int SCIPcolGetIndex( 125 SCIP_COL* col /**< LP col */ 126 ); 127 128 /** gets probindex of corresponding variable */ 129 SCIP_EXPORT 130 int SCIPcolGetVarProbindex( 131 SCIP_COL* col /**< LP col */ 132 ); 133 134 /** returns whether the associated variable is of integral type (binary, integer, implicit integer) */ 135 SCIP_EXPORT 136 SCIP_Bool SCIPcolIsIntegral( 137 SCIP_COL* col /**< LP column */ 138 ); 139 140 /** returns TRUE iff column is removable from the LP (due to aging or cleanup) */ 141 SCIP_EXPORT 142 SCIP_Bool SCIPcolIsRemovable( 143 SCIP_COL* col /**< LP column */ 144 ); 145 146 /** gets position of column in current LP, or -1 if it is not in LP */ 147 SCIP_EXPORT 148 int SCIPcolGetLPPos( 149 SCIP_COL* col /**< LP column */ 150 ); 151 152 /** gets depth in the tree where the column entered the LP, or -1 if it is not in LP */ 153 SCIP_EXPORT 154 int SCIPcolGetLPDepth( 155 SCIP_COL* col /**< LP column */ 156 ); 157 158 /** returns TRUE iff column is member of current LP */ 159 SCIP_EXPORT 160 SCIP_Bool SCIPcolIsInLP( 161 SCIP_COL* col /**< LP column */ 162 ); 163 164 /** get number of nonzero entries in column vector */ 165 SCIP_EXPORT 166 int SCIPcolGetNNonz( 167 SCIP_COL* col /**< LP column */ 168 ); 169 170 /** get number of nonzero entries in column vector, that correspond to rows currently in the SCIP_LP; 171 * 172 * @warning This method is only applicable on columns, that are completely linked to their rows (e.g. a column 173 * that is in the current LP and the LP was solved, or a column that was in a solved LP and didn't change afterwards 174 */ 175 SCIP_EXPORT 176 int SCIPcolGetNLPNonz( 177 SCIP_COL* col /**< LP column */ 178 ); 179 180 /** gets array with rows of nonzero entries */ 181 SCIP_EXPORT 182 SCIP_ROW** SCIPcolGetRows( 183 SCIP_COL* col /**< LP column */ 184 ); 185 186 /** gets array with coefficients of nonzero entries */ 187 SCIP_EXPORT 188 SCIP_Real* SCIPcolGetVals( 189 SCIP_COL* col /**< LP column */ 190 ); 191 192 /** gets node number of the last node in current branch and bound run, where strong branching was used on the 193 * given column, or -1 if strong branching was never applied to the column in current run 194 */ 195 SCIP_EXPORT 196 SCIP_Longint SCIPcolGetStrongbranchNode( 197 SCIP_COL* col /**< LP column */ 198 ); 199 200 /** gets number of times, strong branching was applied in current run on the given column */ 201 SCIP_EXPORT 202 int SCIPcolGetNStrongbranchs( 203 SCIP_COL* col /**< LP column */ 204 ); 205 206 /** gets the age of a column, i.e., the total number of successive times a column was in the LP and was 0.0 in the solution */ 207 SCIP_EXPORT 208 int SCIPcolGetAge( 209 SCIP_COL* col /**< LP column */ 210 ); 211 212 /** gets opposite bound type of given bound type */ 213 SCIP_EXPORT 214 SCIP_BOUNDTYPE SCIPboundtypeOpposite( 215 SCIP_BOUNDTYPE boundtype /**< type of bound (lower or upper) */ 216 ); 217 218 #ifdef NDEBUG 219 220 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 221 * speed up the algorithms. 222 */ 223 224 #define SCIPcolGetObj(col) (col)->obj 225 #define SCIPcolGetLb(col) (col)->lb 226 #define SCIPcolGetUb(col) (col)->ub 227 #define SCIPcolGetBestBound(col) ((col)->obj >= 0.0 ? (col)->lb : (col)->ub) 228 #define SCIPcolGetPrimsol(col) ((col)->lppos >= 0 ? (col)->primsol : 0.0) 229 #define SCIPcolGetMinPrimsol(col) ((col)->minprimsol) 230 #define SCIPcolGetMaxPrimsol(col) ((col)->maxprimsol) 231 #define SCIPcolGetBasisStatus(col) ((SCIP_BASESTAT)(col)->basisstatus) 232 #define SCIPcolGetVar(col) (col)->var 233 #define SCIPcolGetIndex(col) (col)->index 234 #define SCIPcolIsIntegral(col) (col)->integral 235 #define SCIPcolIsRemovable(col) (col)->removable 236 #define SCIPcolGetLPPos(col) (col)->lppos 237 #define SCIPcolGetLPDepth(col) (col)->lpdepth 238 #define SCIPcolIsInLP(col) ((col)->lppos >= 0) 239 #define SCIPcolGetNNonz(col) (col)->len 240 #define SCIPcolGetNLPNonz(col) (col)->nlprows 241 #define SCIPcolGetRows(col) (col)->rows 242 #define SCIPcolGetVals(col) (col)->vals 243 #define SCIPcolGetStrongbranchNode(col) (col)->sbnode 244 #define SCIPcolGetNStrongbranchs(col) (col)->nsbcalls 245 #define SCIPcolGetAge(col) (col)->age 246 #define SCIPboundtypeOpposite(boundtype) \ 247 ((boundtype) == SCIP_BOUNDTYPE_LOWER ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER) 248 249 #endif 250 251 /**@} */ 252 253 254 255 /**@addtogroup PublicRowMethods 256 * 257 * @{ 258 */ 259 260 /** comparison method for sorting rows by non-decreasing index */ 261 SCIP_EXPORT 262 SCIP_DECL_SORTPTRCOMP(SCIProwComp); 263 264 /** locks an unmodifiable row, which forbids further changes; has no effect on modifiable rows */ 265 SCIP_EXPORT 266 void SCIProwLock( 267 SCIP_ROW* row /**< LP row */ 268 ); 269 270 /** unlocks a lock of an unmodifiable row; a row with no sealed lock may be modified; has no effect on modifiable rows */ 271 SCIP_EXPORT 272 void SCIProwUnlock( 273 SCIP_ROW* row /**< LP row */ 274 ); 275 276 /** returns the scalar product of the coefficient vectors of the two given rows */ 277 SCIP_EXPORT 278 SCIP_Real SCIProwGetScalarProduct( 279 SCIP_ROW* row1, /**< first LP row */ 280 SCIP_ROW* row2 /**< second LP row */ 281 ); 282 283 /** returns the degree of parallelism between the hyperplanes defined by the two row vectors v, w: 284 * p = |v*w|/(|v|*|w|); 285 * the hyperplanes are parallel, iff p = 1, they are orthogonal, iff p = 0 286 */ 287 SCIP_EXPORT 288 SCIP_Real SCIProwGetParallelism( 289 SCIP_ROW* row1, /**< first LP row */ 290 SCIP_ROW* row2, /**< second LP row */ 291 char orthofunc /**< function used for calc. scalar prod. ('e'uclidean, 'd'iscrete) */ 292 ); 293 294 /** returns the degree of orthogonality between the hyperplanes defined by the two row vectors v, w: 295 * o = 1 - |v*w|/(|v|*|w|); 296 * the hyperplanes are orthogonal, iff p = 1, they are parallel, iff p = 0 297 */ 298 SCIP_EXPORT 299 SCIP_Real SCIProwGetOrthogonality( 300 SCIP_ROW* row1, /**< first LP row */ 301 SCIP_ROW* row2, /**< second LP row */ 302 char orthofunc /**< function used for calc. scalar prod. ('e'uclidean, 'd'iscrete) */ 303 ); 304 305 /** sorts row entries such that LP columns precede non-LP columns and inside both parts lower column indices precede 306 * higher ones 307 */ 308 SCIP_EXPORT 309 void SCIProwSort( 310 SCIP_ROW* row /**< row to be sorted */ 311 ); 312 313 /** get number of nonzero entries in row vector */ 314 SCIP_EXPORT 315 int SCIProwGetNNonz( 316 SCIP_ROW* row /**< LP row */ 317 ); 318 319 /** get number of nonzero entries in row vector, that correspond to columns currently in the SCIP_LP; 320 * 321 * @warning This method is only applicable on rows, that are completely linked to their columns (e.g. a row 322 * that is in the current LP and the LP was solved, or a row that was in a solved LP and didn't change afterwards 323 */ 324 SCIP_EXPORT 325 int SCIProwGetNLPNonz( 326 SCIP_ROW* row /**< LP row */ 327 ); 328 329 /** gets array with columns of nonzero entries */ 330 SCIP_EXPORT 331 SCIP_COL** SCIProwGetCols( 332 SCIP_ROW* row /**< LP row */ 333 ); 334 335 /** gets array with coefficients of nonzero entries */ 336 SCIP_EXPORT 337 SCIP_Real* SCIProwGetVals( 338 SCIP_ROW* row /**< LP row */ 339 ); 340 341 /** gets constant shift of row */ 342 SCIP_EXPORT 343 SCIP_Real SCIProwGetConstant( 344 SCIP_ROW* row /**< LP row */ 345 ); 346 347 /** gets Euclidean norm of row vector */ 348 SCIP_EXPORT 349 SCIP_Real SCIProwGetNorm( 350 SCIP_ROW* row /**< LP row */ 351 ); 352 353 /** gets sum norm of row vector (sum of absolute values of coefficients) */ 354 SCIP_EXPORT 355 SCIP_Real SCIProwGetSumNorm( 356 SCIP_ROW* row /**< LP row */ 357 ); 358 359 /** returns the left hand side of the row */ 360 SCIP_EXPORT 361 SCIP_Real SCIProwGetLhs( 362 SCIP_ROW* row /**< LP row */ 363 ); 364 365 /** returns the right hand side of the row */ 366 SCIP_EXPORT 367 SCIP_Real SCIProwGetRhs( 368 SCIP_ROW* row /**< LP row */ 369 ); 370 371 /** gets the dual LP solution of a row */ 372 SCIP_EXPORT 373 SCIP_Real SCIProwGetDualsol( 374 SCIP_ROW* row /**< LP row */ 375 ); 376 377 /** gets the dual Farkas coefficient of a row in an infeasible LP */ 378 SCIP_EXPORT 379 SCIP_Real SCIProwGetDualfarkas( 380 SCIP_ROW* row /**< LP row */ 381 ); 382 383 /** gets the basis status of a row in the LP solution; only valid for LPs with status SCIP_LPSOLSTAT_OPTIMAL 384 * and with SCIPisLPSolBasic(scip) == TRUE; returns SCIP_BASESTAT_BASIC for rows not in the current SCIP_LP 385 */ 386 SCIP_EXPORT 387 SCIP_BASESTAT SCIProwGetBasisStatus( 388 SCIP_ROW* row /**< LP row */ 389 ); 390 391 /** returns the name of the row */ 392 SCIP_EXPORT 393 const char* SCIProwGetName( 394 SCIP_ROW* row /**< LP row */ 395 ); 396 397 /** gets unique index of row */ 398 SCIP_EXPORT 399 int SCIProwGetIndex( 400 SCIP_ROW* row /**< LP row */ 401 ); 402 403 /** gets age of row */ 404 SCIP_EXPORT 405 int SCIProwGetAge( 406 SCIP_ROW* row /**< LP row */ 407 ); 408 409 /** gets rank of row */ 410 SCIP_EXPORT 411 int SCIProwGetRank( 412 SCIP_ROW* row /**< LP row */ 413 ); 414 415 /** returns TRUE iff the activity of the row (without the row's constant) is always integral in a feasible solution */ 416 SCIP_EXPORT 417 SCIP_Bool SCIProwIsIntegral( 418 SCIP_ROW* row /**< LP row */ 419 ); 420 421 /** returns TRUE iff row is only valid locally */ 422 SCIP_EXPORT 423 SCIP_Bool SCIProwIsLocal( 424 SCIP_ROW* row /**< LP row */ 425 ); 426 427 /** returns TRUE iff row is modifiable during node processing (subject to column generation) */ 428 SCIP_EXPORT 429 SCIP_Bool SCIProwIsModifiable( 430 SCIP_ROW* row /**< LP row */ 431 ); 432 433 /** returns TRUE iff row is removable from the LP (due to aging or cleanup) */ 434 SCIP_EXPORT 435 SCIP_Bool SCIProwIsRemovable( 436 SCIP_ROW* row /**< LP row */ 437 ); 438 439 /** returns type of origin that created the row */ 440 SCIP_EXPORT 441 SCIP_ROWORIGINTYPE SCIProwGetOrigintype( 442 SCIP_ROW* row /**< LP row */ 443 ); 444 445 /** returns origin constraint handler that created the row (NULL if not available) */ 446 SCIP_EXPORT 447 SCIP_CONSHDLR* SCIProwGetOriginConshdlr( 448 SCIP_ROW* row /**< LP row */ 449 ); 450 451 /** returns origin constraint that created the row (NULL if not available) */ 452 SCIP_EXPORT 453 SCIP_CONS* SCIProwGetOriginCons( 454 SCIP_ROW* row /**< LP row */ 455 ); 456 457 /** returns origin separator that created the row (NULL if not available) */ 458 SCIP_EXPORT 459 SCIP_SEPA* SCIProwGetOriginSepa( 460 SCIP_ROW* row /**< LP row */ 461 ); 462 463 /** returns TRUE iff row is member of the global cut pool */ 464 SCIP_EXPORT 465 SCIP_Bool SCIProwIsInGlobalCutpool( 466 SCIP_ROW* row /**< LP row */ 467 ); 468 469 /** gets position of row in current LP, or -1 if it is not in LP */ 470 SCIP_EXPORT 471 int SCIProwGetLPPos( 472 SCIP_ROW* row /**< LP row */ 473 ); 474 475 /** gets depth in the tree where the row entered the LP, or -1 if it is not in LP */ 476 SCIP_EXPORT 477 int SCIProwGetLPDepth( 478 SCIP_ROW* row /**< LP row */ 479 ); 480 481 /** returns TRUE iff row is member of current LP */ 482 SCIP_EXPORT 483 SCIP_Bool SCIProwIsInLP( 484 SCIP_ROW* row /**< LP row */ 485 ); 486 487 /** returns the number of times that this row has been sharp in an optimal LP solution */ 488 SCIP_EXPORT 489 SCIP_Longint SCIProwGetActiveLPCount( 490 SCIP_ROW* row /**< row */ 491 ); 492 493 /** returns the number of LPs since this row has been created */ 494 SCIP_EXPORT 495 SCIP_Longint SCIProwGetNLPsAfterCreation( 496 SCIP_ROW* row /**< row */ 497 ); 498 499 /** changes the rank of LP row */ 500 SCIP_EXPORT 501 void SCIProwChgRank( 502 SCIP_ROW* row, /**< LP row */ 503 int rank /**< new value for rank */ 504 ); 505 506 #ifdef NDEBUG 507 508 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 509 * speed up the algorithms. 510 */ 511 512 #define SCIProwGetNNonz(row) (row)->len 513 #define SCIProwGetNLPNonz(row) (row)->nlpcols 514 #define SCIProwGetCols(row) (row)->cols 515 #define SCIProwGetVals(row) (row)->vals 516 #define SCIProwGetConstant(row) (row)->constant 517 #define SCIProwGetNorm(row) sqrt((row)->sqrnorm) 518 #define SCIProwGetSumNorm(row) (row)->sumnorm 519 #define SCIProwGetLhs(row) (row)->lhs 520 #define SCIProwGetRhs(row) (row)->rhs 521 #define SCIProwGetDualsol(row) ((row)->lppos >= 0 ? (row)->dualsol : 0.0) 522 #define SCIProwGetDualfarkas(row) ((row)->lppos >= 0 ? (row)->dualfarkas : 0.0) 523 #define SCIProwGetBasisStatus(row) ((SCIP_BASESTAT) (row)->basisstatus) 524 #define SCIProwGetName(row) (row)->name 525 #define SCIProwGetIndex(row) (row)->index 526 #define SCIProwGetAge(row) (row)->age 527 #define SCIProwGetRank(row) (row)->rank 528 #define SCIProwIsIntegral(row) (row)->integral 529 #define SCIProwIsLocal(row) (row)->local 530 #define SCIProwIsModifiable(row) (row)->modifiable 531 #define SCIProwIsRemovable(row) (row)->removable 532 #define SCIProwGetOrigintype(row) (row)->origintype 533 #define SCIProwGetOriginCons(row) ((SCIP_CONS*) ((SCIP_ROWORIGINTYPE) row->origintype == SCIP_ROWORIGINTYPE_CONS ? (row)->origin : NULL)) 534 #define SCIProwGetOriginSepa(row) ((SCIP_SEPA*) ((SCIP_ROWORIGINTYPE) row->origintype == SCIP_ROWORIGINTYPE_SEPA ? (row)->origin : NULL)) 535 #define SCIProwIsInGlobalCutpool(row) (row)->inglobalcutpool 536 #define SCIProwGetLPPos(row) (row)->lppos 537 #define SCIProwGetLPDepth(row) (row)->lpdepth 538 #define SCIProwIsInLP(row) ((row)->lppos >= 0) 539 #define SCIProwGetActiveLPCount(row) ((row)->activeinlpcounter) 540 #define SCIProwGetNLPsAfterCreation(row) ((row)->nlpsaftercreation) 541 #define SCIProwChgRank(row, cutrank) ((row)->rank = (cutrank)) 542 543 #endif 544 545 /**@} */ 546 547 #ifdef __cplusplus 548 } 549 #endif 550 551 #endif 552