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 matrix.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for MIP matrix data structure 28 * @author Dieter Weninger 29 * @author Gerald Gamrath 30 * 31 * The MIP matrix is organized as sparse data structure in row and 32 * and column major format. 33 * 34 * @todo disregard relaxation-only variables in lock check and don't copy them to the matrix 35 */ 36 37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 38 39 #include "blockmemshell/memory.h" 40 #include "scip/cons_knapsack.h" 41 #include "scip/cons_linear.h" 42 #include "scip/cons_logicor.h" 43 #include "scip/cons_setppc.h" 44 #include "scip/cons_varbound.h" 45 #include "scip/pub_matrix.h" 46 #include "scip/pub_cons.h" 47 #include "scip/pub_message.h" 48 #include "scip/pub_misc_sort.h" 49 #include "scip/pub_var.h" 50 #include "scip/scip_cons.h" 51 #include "scip/scip_general.h" 52 #include "scip/scip_mem.h" 53 #include "scip/scip_message.h" 54 #include "scip/scip_numerics.h" 55 #include "scip/scip_pricer.h" 56 #include "scip/scip_prob.h" 57 #include "scip/scip_var.h" 58 #include "scip/struct_matrix.h" 59 #include <string.h> 60 61 /* 62 * private functions 63 */ 64 65 /** transforms given variables, scalars and constant to the corresponding active variables, scalars and constant */ 66 static 67 SCIP_RETCODE getActiveVariables( 68 SCIP* scip, /**< SCIP instance */ 69 SCIP_VAR*** vars, /**< vars array to get active variables for */ 70 SCIP_Real** scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */ 71 int* nvars, /**< pointer to number of variables and values in vars and vals array */ 72 SCIP_Real* constant /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */ 73 ) 74 { 75 int requiredsize; 76 77 assert(scip != NULL); 78 assert(vars != NULL); 79 assert(scalars != NULL); 80 assert(*vars != NULL); 81 assert(*scalars != NULL); 82 assert(nvars != NULL); 83 assert(constant != NULL); 84 85 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) ); 86 87 if( requiredsize > *nvars ) 88 { 89 SCIP_CALL( SCIPreallocBufferArray(scip, vars, requiredsize) ); 90 SCIP_CALL( SCIPreallocBufferArray(scip, scalars, requiredsize) ); 91 92 /* call function a second time with enough memory */ 93 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) ); 94 assert(requiredsize <= *nvars); 95 } 96 97 return SCIP_OKAY; 98 } 99 100 /** add one row to the constraint matrix */ 101 static 102 SCIP_RETCODE addRow( 103 SCIP* scip, /**< SCIP data structure */ 104 SCIP_MATRIX* matrix, /**< constraint matrix */ 105 SCIP_VAR** vars, /**< variables of this row */ 106 SCIP_Real* vals, /**< coefficients of this row */ 107 int nvars, /**< number of variables of this row */ 108 SCIP_Real lhs, /**< left hand side */ 109 SCIP_Real rhs, /**< right hand side */ 110 int maxnnonzsmem, /**< maximal number of fillable elements */ 111 SCIP_Bool* rowadded /**< flag indicating if constraint was added to matrix */ 112 ) 113 { 114 int j; 115 int probindex; 116 int rowidx; 117 SCIP_Real factor; 118 SCIP_Bool rangedorequality; 119 120 assert(vars != NULL); 121 assert(vals != NULL); 122 123 rowidx = matrix->nrows; 124 rangedorequality = FALSE; 125 126 if( SCIPisInfinity(scip, -lhs) ) 127 { 128 factor = -1.0; 129 matrix->lhs[rowidx] = -rhs; 130 matrix->rhs[rowidx] = SCIPinfinity(scip); 131 matrix->isrhsinfinite[rowidx] = TRUE; 132 } 133 else 134 { 135 factor = 1.0; 136 matrix->lhs[rowidx] = lhs; 137 matrix->rhs[rowidx] = rhs; 138 matrix->isrhsinfinite[rowidx] = SCIPisInfinity(scip, matrix->rhs[rowidx]); 139 140 if( !SCIPisInfinity(scip, rhs) ) 141 rangedorequality = TRUE; 142 } 143 144 if(SCIPisInfinity(scip, -matrix->lhs[rowidx])) 145 { 146 /* ignore redundant constraint */ 147 *rowadded = FALSE; 148 return SCIP_OKAY; 149 } 150 151 matrix->rowmatbeg[rowidx] = matrix->nnonzs; 152 153 /* = or ranged */ 154 if( rangedorequality ) 155 { 156 assert(factor > 0); 157 158 for( j = 0; j < nvars; j++ ) 159 { 160 assert(maxnnonzsmem > matrix->nnonzs); 161 162 /* ignore variables with very small coefficients */ 163 if( SCIPisZero(scip, vals[j]) ) 164 continue; 165 166 matrix->rowmatval[matrix->nnonzs] = factor * vals[j]; 167 probindex = SCIPvarGetProbindex(vars[j]); 168 assert(matrix->vars[probindex] == vars[j]); 169 170 matrix->nuplocks[probindex]++; 171 matrix->ndownlocks[probindex]++; 172 173 assert(0 <= probindex && probindex < matrix->ncols); 174 matrix->rowmatind[matrix->nnonzs] = probindex; 175 176 (matrix->nnonzs)++; 177 } 178 } 179 /* >= or <= */ 180 else 181 { 182 for( j = 0; j < nvars; j++ ) 183 { 184 assert(maxnnonzsmem > matrix->nnonzs); 185 186 /* ignore variables with very small coefficients */ 187 if( SCIPisZero(scip, vals[j]) ) 188 continue; 189 190 /* due to the factor, <= constraints will be transfered to >= */ 191 matrix->rowmatval[matrix->nnonzs] = factor * vals[j]; 192 probindex = SCIPvarGetProbindex(vars[j]); 193 assert(matrix->vars[probindex] == vars[j]); 194 195 if( matrix->rowmatval[matrix->nnonzs] > 0 ) 196 matrix->ndownlocks[probindex]++; 197 else 198 { 199 assert(matrix->rowmatval[matrix->nnonzs] < 0); 200 matrix->nuplocks[probindex]++; 201 } 202 203 assert(0 <= probindex && probindex < matrix->ncols); 204 matrix->rowmatind[matrix->nnonzs] = probindex; 205 206 (matrix->nnonzs)++; 207 } 208 } 209 210 matrix->rowmatcnt[rowidx] = matrix->nnonzs - matrix->rowmatbeg[rowidx]; 211 212 ++(matrix->nrows); 213 *rowadded = TRUE; 214 215 return SCIP_OKAY; 216 } 217 218 /** add one constraint to matrix */ 219 static 220 SCIP_RETCODE addConstraint( 221 SCIP* scip, /**< current scip instance */ 222 SCIP_MATRIX* matrix, /**< constraint matrix */ 223 SCIP_VAR** vars, /**< variables of this constraint */ 224 SCIP_Real* vals, /**< variable coefficients of this constraint */ 225 int nvars, /**< number of variables */ 226 SCIP_Real lhs, /**< left hand side */ 227 SCIP_Real rhs, /**< right hand side */ 228 int maxnnonzsmem, /**< maximal number of fillable elements */ 229 SCIP_Bool* rowadded /**< flag indicating of row was added to matrix */ 230 ) 231 { 232 SCIP_VAR** activevars; 233 SCIP_Real* activevals; 234 SCIP_Real activeconstant; 235 int nactivevars; 236 int v; 237 238 assert(scip != NULL); 239 assert(matrix != NULL); 240 assert(vars != NULL || nvars == 0); 241 assert(SCIPisLE(scip, lhs, rhs)); 242 assert(rowadded != NULL); 243 244 *rowadded = FALSE; 245 246 /* constraint is redundant */ 247 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) ) 248 return SCIP_OKAY; 249 250 /* we do not add empty constraints to the matrix */ 251 if( nvars == 0 ) 252 return SCIP_OKAY; 253 254 activevars = NULL; 255 activevals = NULL; 256 nactivevars = nvars; 257 activeconstant = 0.0; 258 259 /* duplicate variable and value array */ 260 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) ); 261 if( vals != NULL ) 262 { 263 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) ); 264 } 265 else 266 { 267 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) ); 268 269 for( v = 0; v < nactivevars; v++ ) 270 activevals[v] = 1.0; 271 } 272 273 /* retransform given variables to active variables */ 274 SCIP_CALL( getActiveVariables(scip, &activevars, &activevals, &nactivevars, &activeconstant) ); 275 276 /* adapt left and right hand side */ 277 if( !SCIPisInfinity(scip, -lhs) ) 278 lhs -= activeconstant; 279 if( !SCIPisInfinity(scip, rhs) ) 280 rhs -= activeconstant; 281 282 /* add single row to matrix */ 283 if( nactivevars > 0 ) 284 { 285 SCIP_CALL( addRow(scip, matrix, activevars, activevals, nactivevars, lhs, rhs, maxnnonzsmem, rowadded) ); 286 } 287 288 /* free buffer arrays */ 289 SCIPfreeBufferArray(scip, &activevals); 290 SCIPfreeBufferArray(scip, &activevars); 291 292 return SCIP_OKAY; 293 } 294 295 /** transform row major format into column major format */ 296 static 297 SCIP_RETCODE setColumnMajorFormat( 298 SCIP* scip, /**< current scip instance */ 299 SCIP_MATRIX* matrix /**< constraint matrix */ 300 ) 301 { 302 int colidx; 303 int i; 304 int* rowpnt; 305 int* rowend; 306 SCIP_Real* valpnt; 307 int* fillidx; 308 309 assert(scip != NULL); 310 assert(matrix != NULL); 311 assert(matrix->colmatval != NULL); 312 assert(matrix->colmatind != NULL); 313 assert(matrix->colmatbeg != NULL); 314 assert(matrix->colmatcnt != NULL); 315 assert(matrix->rowmatval != NULL); 316 assert(matrix->rowmatind != NULL); 317 assert(matrix->rowmatbeg != NULL); 318 assert(matrix->rowmatcnt != NULL); 319 320 SCIP_CALL( SCIPallocBufferArray(scip, &fillidx, matrix->ncols) ); 321 BMSclearMemoryArray(fillidx, matrix->ncols); 322 BMSclearMemoryArray(matrix->colmatcnt, matrix->ncols); 323 324 for( i = 0; i < matrix->nrows; i++ ) 325 { 326 rowpnt = matrix->rowmatind + matrix->rowmatbeg[i]; 327 rowend = rowpnt + matrix->rowmatcnt[i]; 328 for( ; rowpnt < rowend; rowpnt++ ) 329 { 330 colidx = *rowpnt; 331 (matrix->colmatcnt[colidx])++; 332 } 333 } 334 335 matrix->colmatbeg[0] = 0; 336 for( i = 0; i < matrix->ncols-1; i++ ) 337 { 338 matrix->colmatbeg[i+1] = matrix->colmatbeg[i] + matrix->colmatcnt[i]; 339 } 340 341 for( i = 0; i < matrix->nrows; i++ ) 342 { 343 rowpnt = matrix->rowmatind + matrix->rowmatbeg[i]; 344 rowend = rowpnt + matrix->rowmatcnt[i]; 345 valpnt = matrix->rowmatval + matrix->rowmatbeg[i]; 346 347 for( ; rowpnt < rowend; rowpnt++, valpnt++ ) 348 { 349 assert(*rowpnt < matrix->ncols); 350 colidx = *rowpnt; 351 matrix->colmatval[matrix->colmatbeg[colidx] + fillidx[colidx]] = *valpnt; 352 matrix->colmatind[matrix->colmatbeg[colidx] + fillidx[colidx]] = i; 353 fillidx[colidx]++; 354 } 355 } 356 357 SCIPfreeBufferArray(scip, &fillidx); 358 359 return SCIP_OKAY; 360 } 361 362 /** calculate min/max activity per row */ 363 static 364 SCIP_RETCODE calcActivityBounds( 365 SCIP* scip, /**< current scip instance */ 366 SCIP_MATRIX* matrix /**< constraint matrix */ 367 ) 368 { 369 SCIP_Real val; 370 int* rowpnt; 371 int* rowend; 372 SCIP_Real* valpnt; 373 int col; 374 int row; 375 376 assert(scip != NULL); 377 assert(matrix != NULL); 378 379 for( row = 0; row < matrix->nrows; row++ ) 380 { 381 matrix->minactivity[row] = 0; 382 matrix->maxactivity[row] = 0; 383 matrix->minactivityneginf[row] = 0; 384 matrix->minactivityposinf[row] = 0; 385 matrix->maxactivityneginf[row] = 0; 386 matrix->maxactivityposinf[row] = 0; 387 388 rowpnt = matrix->rowmatind + matrix->rowmatbeg[row]; 389 rowend = rowpnt + matrix->rowmatcnt[row]; 390 valpnt = matrix->rowmatval + matrix->rowmatbeg[row]; 391 392 for( ; rowpnt < rowend; rowpnt++, valpnt++ ) 393 { 394 /* get column index */ 395 col = *rowpnt; 396 397 /* get variable coefficient */ 398 val = *valpnt; 399 assert(!SCIPisZero(scip, val)); 400 401 assert(matrix->ncols > col); 402 403 assert(!SCIPisInfinity(scip, matrix->lb[col])); 404 assert(!SCIPisInfinity(scip, -matrix->ub[col])); 405 406 /* positive coefficient */ 407 if( val > 0.0 ) 408 { 409 if( SCIPisInfinity(scip, matrix->ub[col]) ) 410 matrix->maxactivityposinf[row]++; 411 else 412 matrix->maxactivity[row] += val * matrix->ub[col]; 413 414 if( SCIPisInfinity(scip, -matrix->lb[col]) ) 415 matrix->minactivityneginf[row]++; 416 else 417 matrix->minactivity[row] += val * matrix->lb[col]; 418 } 419 /* negative coefficient */ 420 else 421 { 422 if( SCIPisInfinity(scip, -matrix->lb[col]) ) 423 matrix->maxactivityneginf[row]++; 424 else 425 matrix->maxactivity[row] += val * matrix->lb[col]; 426 427 if( SCIPisInfinity(scip, matrix->ub[col]) ) 428 matrix->minactivityposinf[row]++; 429 else 430 matrix->minactivity[row] += val * matrix->ub[col]; 431 } 432 } 433 434 /* consider infinite bound contributions for the activities */ 435 if( matrix->maxactivityneginf[row] + matrix->maxactivityposinf[row] > 0 ) 436 matrix->maxactivity[row] = SCIPinfinity(scip); 437 438 if( matrix->minactivityneginf[row] + matrix->minactivityposinf[row] > 0 ) 439 matrix->minactivity[row] = -SCIPinfinity(scip); 440 } 441 442 return SCIP_OKAY; 443 } 444 445 /* 446 * public functions 447 */ 448 449 /** initialize matrix by copying all check constraints 450 * 451 * @note Completeness is checked by testing whether all check constraints are from a list of linear constraint handlers 452 * that can be represented. 453 */ 454 SCIP_RETCODE SCIPmatrixCreate( 455 SCIP* scip, /**< current scip instance */ 456 SCIP_MATRIX** matrixptr, /**< pointer to constraint matrix object to be initialized */ 457 SCIP_Bool onlyifcomplete, /**< should matrix creation be skipped if matrix will not be complete? */ 458 SCIP_Bool* initialized, /**< was the initialization successful? */ 459 SCIP_Bool* complete, /**< are all constraint represented within the matrix? */ 460 SCIP_Bool* infeasible, /**< pointer to return whether problem was detected to be infeasible during matrix creation */ 461 int* naddconss, /**< pointer to count number of added (linear) constraints during matrix creation */ 462 int* ndelconss, /**< pointer to count number of deleted specialized linear constraints during matrix creation */ 463 int* nchgcoefs, /**< pointer to count number of changed coefficients during matrix creation */ 464 int* nchgbds, /**< pointer to count number of changed bounds during matrix creation */ 465 int* nfixedvars /**< pointer to count number of fixed variables during matrix creation */ 466 ) 467 { 468 SCIP_MATRIX* matrix; 469 SCIP_CONSHDLR** conshdlrs; 470 const char* conshdlrname; 471 SCIP_Bool stopped; 472 SCIP_VAR** vars; 473 SCIP_VAR* var; 474 SCIP_CONS* cons; 475 int nconshdlrs; 476 int nconss; 477 int nconssall; 478 int nnonzstmp; 479 int nvars; 480 int c; 481 int i; 482 int v; 483 int cnt; 484 485 nnonzstmp = 0; 486 487 assert(scip != NULL); 488 assert(matrixptr != NULL); 489 assert(initialized != NULL); 490 assert(complete != NULL); 491 492 *initialized = FALSE; 493 *complete = FALSE; 494 *infeasible = FALSE; 495 496 /* return if no variables or constraints are present */ 497 if( SCIPgetNVars(scip) == 0 || SCIPgetNConss(scip) == 0 ) 498 return SCIP_OKAY; 499 500 /* return if pricers are present and the matrix should only be built when complete */ 501 if( onlyifcomplete && SCIPgetNActivePricers(scip) != 0 ) 502 return SCIP_OKAY; 503 504 /* loop over all constraint handlers and collect the number of checked constraints */ 505 nconshdlrs = SCIPgetNConshdlrs(scip); 506 conshdlrs = SCIPgetConshdlrs(scip); 507 nconss = 0; 508 nconssall = 0; 509 510 for( i = 0; i < nconshdlrs; ++i ) 511 { 512 int nconshdlrconss; 513 514 nconshdlrconss = SCIPconshdlrGetNCheckConss(conshdlrs[i]); 515 516 if( nconshdlrconss > 0 ) 517 { 518 conshdlrname = SCIPconshdlrGetName(conshdlrs[i]); 519 520 if( (strcmp(conshdlrname, "linear") == 0) || (strcmp(conshdlrname, "setppc") == 0) 521 || (strcmp(conshdlrname, "logicor") == 0) || (strcmp(conshdlrname, "knapsack") == 0) 522 || (strcmp(conshdlrname, "varbound") == 0) ) 523 { 524 /* increment number of supported constraints */ 525 nconss += nconshdlrconss; 526 } 527 /* disabled because some of the presolvers can currently only handle 1-1 row-cons relationships */ 528 #ifdef SCIP_DISABLED_CODE 529 else if( strcmp(conshdlrname, "linking") == 0 ) 530 { 531 /* the linear representation of linking constraints involves two linear constraints */ 532 nconss += 2* nconshdlrconss; 533 } 534 #endif 535 /* increment number of supported and unsupported constraints */ 536 nconssall += nconshdlrconss; 537 } 538 } 539 540 /* print warning if we have unsupported constraint types; we only abort the matrix creation process if requested, 541 * because it makes sometimes sense to work on an incomplete matrix as long as the number of interesting variable 542 * uplocks or downlocks of the matrix and scip are the same 543 */ 544 if( nconss < nconssall ) 545 { 546 SCIPdebugMsg(scip, "Warning: milp matrix not complete!\n"); 547 if( onlyifcomplete ) 548 return SCIP_OKAY; 549 } 550 else 551 { 552 /* all constraints represented within the matrix */ 553 *complete = TRUE; 554 } 555 556 /* do nothing if we have no checked constraints */ 557 if( nconss == 0 ) 558 return SCIP_OKAY; 559 560 stopped = FALSE; 561 562 /* first, clean up aggregations and fixings in varbound costraints, since this can lead 563 * to boundchanges and the varbound constraint can get downgraded to a linear constraint 564 */ 565 SCIP_CALL( SCIPcleanupConssVarbound(scip, TRUE, infeasible, naddconss, ndelconss, nchgbds ) ); 566 if( *infeasible ) 567 return SCIP_OKAY; 568 569 /* next, clean up aggregations and fixings in setppc costraints, since this can lead 570 * to fixings and the setppc constraint can get downgraded to a linear constraint 571 */ 572 SCIP_CALL( SCIPcleanupConssSetppc(scip, TRUE, infeasible, naddconss, ndelconss, nchgcoefs, nfixedvars ) ); 573 if( *infeasible ) 574 return SCIP_OKAY; 575 576 /* next, clean up aggregations and fixings in logicor costraints, since this cannot lead 577 * to further fixings but the logicor constraint can also get downgraded to a linear constraint 578 */ 579 SCIP_CALL( SCIPcleanupConssLogicor(scip, TRUE, naddconss, ndelconss, nchgcoefs) ); 580 581 /* finally, clean up aggregations and fixings in knapsack and linear constraints since now no new linaer constraints 582 * can come up due to downgrading and the remaining cleanup methods cannot fix any more variables 583 */ 584 585 SCIP_CALL( SCIPcleanupConssKnapsack(scip, TRUE, infeasible) ); 586 if( *infeasible ) 587 return SCIP_OKAY; 588 589 SCIP_CALL( SCIPcleanupConssLinear(scip, TRUE, infeasible) ); 590 if( *infeasible ) 591 return SCIP_OKAY; 592 593 vars = SCIPgetVars(scip); 594 nvars = SCIPgetNVars(scip); 595 596 /* approximate number of nonzeros by taking for each variable the number of up- and downlocks; 597 * this counts nonzeros in equalities twice, but can be at most two times as high as the exact number 598 */ 599 for( i = nvars - 1; i >= 0; --i ) 600 { 601 nnonzstmp += SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL); 602 nnonzstmp += SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL); 603 } 604 605 /* do nothing if we have no entries */ 606 if( nnonzstmp == 0 ) 607 return SCIP_OKAY; 608 609 /* build the matrix structure */ 610 SCIP_CALL( SCIPallocBuffer(scip, matrixptr) ); 611 matrix = *matrixptr; 612 613 /* copy vars array and set number of variables */ 614 SCIP_CALL( SCIPduplicateBufferArray(scip, &matrix->vars, vars, nvars) ); 615 matrix->ncols = nvars; 616 617 matrix->nrows = 0; 618 matrix->nnonzs = 0; 619 620 /* allocate memory */ 621 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatval, nnonzstmp) ); 622 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatind, nnonzstmp) ); 623 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatbeg, matrix->ncols) ); 624 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatcnt, matrix->ncols) ); 625 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->lb, matrix->ncols) ); 626 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->ub, matrix->ncols) ); 627 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->nuplocks, matrix->ncols) ); 628 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->ndownlocks, matrix->ncols) ); 629 630 BMSclearMemoryArray(matrix->nuplocks, matrix->ncols); 631 BMSclearMemoryArray(matrix->ndownlocks, matrix->ncols); 632 633 /* init bounds */ 634 for( v = 0; v < matrix->ncols; v++ ) 635 { 636 var = matrix->vars[v]; 637 assert(var != NULL); 638 639 matrix->lb[v] = SCIPvarGetLbGlobal(var); 640 matrix->ub[v] = SCIPvarGetUbGlobal(var); 641 } 642 643 /* allocate memory */ 644 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatval, nnonzstmp) ); 645 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatind, nnonzstmp) ); 646 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatbeg, nconss) ); 647 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatcnt, nconss) ); 648 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->lhs, nconss) ); 649 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rhs, nconss) ); 650 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->cons, nconss) ); 651 SCIP_CALL( SCIPallocClearMemoryArray(scip, &matrix->isrhsinfinite, nconss) ); 652 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivity, nconss) ); 653 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivity, nconss) ); 654 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivityneginf, nconss) ); 655 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivityposinf, nconss) ); 656 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivityneginf, nconss) ); 657 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivityposinf, nconss) ); 658 659 cnt = 0; 660 661 /* loop a second time over constraints handlers and add supported constraints to the matrix */ 662 for( i = 0; i < nconshdlrs; ++i ) 663 { 664 SCIP_CONS** conshdlrconss; 665 int nconshdlrconss; 666 SCIP_Bool rowadded; 667 668 if( SCIPisStopped(scip) || (onlyifcomplete && !(*complete)) ) 669 { 670 stopped = TRUE; 671 break; 672 } 673 674 conshdlrname = SCIPconshdlrGetName(conshdlrs[i]); 675 conshdlrconss = SCIPconshdlrGetCheckConss(conshdlrs[i]); 676 nconshdlrconss = SCIPconshdlrGetNCheckConss(conshdlrs[i]); 677 678 if( strcmp(conshdlrname, "linear") == 0 ) 679 { 680 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c ) 681 { 682 cons = conshdlrconss[c]; 683 assert(SCIPconsIsTransformed(cons)); 684 685 /* do not include constraints that can be altered due to column generation */ 686 if( SCIPconsIsModifiable(cons) ) 687 { 688 *complete = FALSE; 689 690 if( onlyifcomplete ) 691 break; 692 693 continue; 694 } 695 696 SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsLinear(scip, cons), 697 SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons), 698 SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons), nnonzstmp, &rowadded) ); 699 700 if(rowadded) 701 { 702 assert(cnt < nconss); 703 matrix->cons[cnt] = cons; 704 cnt++; 705 } 706 } 707 } 708 else if( strcmp(conshdlrname, "setppc") == 0 ) 709 { 710 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c ) 711 { 712 SCIP_Real lhs; 713 SCIP_Real rhs; 714 715 cons = conshdlrconss[c]; 716 assert(SCIPconsIsTransformed(cons)); 717 718 /* do not include constraints that can be altered due to column generation */ 719 if( SCIPconsIsModifiable(cons) ) 720 { 721 *complete = FALSE; 722 723 if( onlyifcomplete ) 724 break; 725 726 continue; 727 } 728 729 switch( SCIPgetTypeSetppc(scip, cons) ) 730 { 731 case SCIP_SETPPCTYPE_PARTITIONING : 732 lhs = 1.0; 733 rhs = 1.0; 734 break; 735 case SCIP_SETPPCTYPE_PACKING : 736 lhs = -SCIPinfinity(scip); 737 rhs = 1.0; 738 break; 739 case SCIP_SETPPCTYPE_COVERING : 740 lhs = 1.0; 741 rhs = SCIPinfinity(scip); 742 break; 743 default: 744 return SCIP_ERROR; 745 } 746 747 SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsSetppc(scip, cons), NULL, 748 SCIPgetNVarsSetppc(scip, cons), lhs, rhs, nnonzstmp, &rowadded) ); 749 750 if(rowadded) 751 { 752 assert(cnt < nconss); 753 matrix->cons[cnt] = cons; 754 cnt++; 755 } 756 } 757 } 758 else if( strcmp(conshdlrname, "logicor") == 0 ) 759 { 760 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c ) 761 { 762 cons = conshdlrconss[c]; 763 assert(SCIPconsIsTransformed(cons)); 764 765 /* do not include constraints that can be altered due to column generation */ 766 if( SCIPconsIsModifiable(cons) ) 767 { 768 *complete = FALSE; 769 770 if( onlyifcomplete ) 771 break; 772 773 continue; 774 } 775 776 SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsLogicor(scip, cons), 777 NULL, SCIPgetNVarsLogicor(scip, cons), 1.0, SCIPinfinity(scip), nnonzstmp, &rowadded) ); 778 779 if(rowadded) 780 { 781 assert(cnt < nconss); 782 matrix->cons[cnt] = cons; 783 cnt++; 784 } 785 } 786 } 787 else if( strcmp(conshdlrname, "knapsack") == 0 ) 788 { 789 if( nconshdlrconss > 0 ) 790 { 791 SCIP_Real* consvals; 792 int valssize; 793 794 valssize = 100; 795 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, valssize) ); 796 797 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c ) 798 { 799 SCIP_Longint* weights; 800 801 cons = conshdlrconss[c]; 802 assert(SCIPconsIsTransformed(cons)); 803 804 /* do not include constraints that can be altered due to column generation */ 805 if( SCIPconsIsModifiable(cons) ) 806 { 807 *complete = FALSE; 808 809 if( onlyifcomplete ) 810 break; 811 812 continue; 813 } 814 815 weights = SCIPgetWeightsKnapsack(scip, cons); 816 nvars = SCIPgetNVarsKnapsack(scip, cons); 817 818 if( nvars > valssize ) 819 { 820 valssize = (int) (1.5 * nvars); 821 SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, valssize) ); 822 } 823 824 for( v = 0; v < nvars; v++ ) 825 consvals[v] = (SCIP_Real)weights[v]; 826 827 SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsKnapsack(scip, cons), consvals, 828 SCIPgetNVarsKnapsack(scip, cons), -SCIPinfinity(scip), 829 (SCIP_Real)SCIPgetCapacityKnapsack(scip, cons), nnonzstmp, &rowadded) ); 830 831 if(rowadded) 832 { 833 assert(cnt < nconss); 834 matrix->cons[cnt] = cons; 835 cnt++; 836 } 837 } 838 839 SCIPfreeBufferArray(scip, &consvals); 840 } 841 } 842 else if( strcmp(conshdlrname, "varbound") == 0 ) 843 { 844 if( nconshdlrconss > 0 ) 845 { 846 SCIP_VAR** consvars; 847 SCIP_Real* consvals; 848 849 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) ); 850 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) ); 851 consvals[0] = 1.0; 852 853 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c ) 854 { 855 cons = conshdlrconss[c]; 856 assert(SCIPconsIsTransformed(cons)); 857 858 /* do not include constraints that can be altered due to column generation */ 859 if( SCIPconsIsModifiable(cons) ) 860 { 861 *complete = FALSE; 862 863 if( onlyifcomplete ) 864 break; 865 866 continue; 867 } 868 869 consvars[0] = SCIPgetVarVarbound(scip, cons); 870 consvars[1] = SCIPgetVbdvarVarbound(scip, cons); 871 872 consvals[1] = SCIPgetVbdcoefVarbound(scip, cons); 873 874 SCIP_CALL( addConstraint(scip, matrix, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons), 875 SCIPgetRhsVarbound(scip, cons), nnonzstmp, &rowadded) ); 876 877 if(rowadded) 878 { 879 assert(cnt < nconss); 880 matrix->cons[cnt] = cons; 881 cnt++; 882 } 883 } 884 885 SCIPfreeBufferArray(scip, &consvals); 886 SCIPfreeBufferArray(scip, &consvars); 887 } 888 } 889 /* the code below is correct. However, it needs to be disabled 890 * because some of the presolvers can currently only handle 1-1 row-cons relationships, 891 * while the linking constraint handler requires a representation as 2 linear constraints. 892 */ 893 #ifdef SCIP_DISABLED_CODE 894 else if( strcmp(conshdlrname, "linking") == 0 ) 895 { 896 if( nconshdlrconss > 0 ) 897 { 898 SCIP_VAR** consvars; 899 SCIP_VAR** curconsvars; 900 SCIP_Real* consvals; 901 int* curconsvals; 902 int valssize; 903 int nconsvars; 904 int j; 905 906 valssize = 100; 907 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, valssize) ); 908 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, valssize) ); 909 910 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c ) 911 { 912 cons = conshdlrconss[c]; 913 assert(SCIPconsIsTransformed(cons)); 914 915 /* do not include constraints that can be altered due to column generation */ 916 if( SCIPconsIsModifiable(cons) ) 917 { 918 *complete = FALSE; 919 920 if( onlyifcomplete ) 921 break; 922 923 continue; 924 } 925 926 /* get constraint variables and their amount */ 927 SCIP_CALL( SCIPgetBinvarsLinking(scip, cons, &curconsvars, &nconsvars) ); 928 curconsvals = SCIPgetValsLinking(scip, cons); 929 930 /* SCIPgetBinVarsLinking returns the number of binary variables, but we also need the integer variable */ 931 nconsvars++; 932 933 if( nconsvars > valssize ) 934 { 935 valssize = (int) (1.5 * nconsvars); 936 SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, valssize) ); 937 SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, valssize) ); 938 } 939 940 /* copy vars and vals for binary variables */ 941 for( j = 0; j < nconsvars - 1; j++ ) 942 { 943 consvars[j] = curconsvars[j]; 944 consvals[j] = (SCIP_Real) curconsvals[j]; 945 } 946 947 /* set final entry of vars and vals to the linking variable and its coefficient, respectively */ 948 consvars[nconsvars - 1] = SCIPgetIntvarLinking(scip, cons); 949 consvals[nconsvars - 1] = -1; 950 951 SCIP_CALL( addConstraint(scip, matrix, consvars, consvals, nconsvars, 0.0, 0.0, nnonzstmp, &rowadded) ); 952 SCIP_CALL( addConstraint(scip, matrix, consvars, NULL, nconsvars - 1, 1.0, 1.0, nnonzstmp, &rowadded) ); 953 954 if(rowadded) 955 { 956 assert(cnt < nconss); 957 matrix->cons[cnt] = cons; 958 matrix->cons[cnt + 1] = cons; 959 cnt += 2; 960 } 961 } 962 963 SCIPfreeBufferArray(scip, &consvals); 964 SCIPfreeBufferArray(scip, &consvars); 965 } 966 } 967 #endif 968 } 969 assert(matrix->nrows == cnt); 970 assert(matrix->nrows <= nconss); 971 assert(matrix->nnonzs <= nnonzstmp); 972 973 if( *complete ) 974 { 975 SCIP_Bool lockmismatch = FALSE; 976 977 for( i = 0; i < matrix->ncols; ++i ) 978 { 979 if( SCIPmatrixUplockConflict(matrix, i) || SCIPmatrixDownlockConflict(matrix, i) ) 980 { 981 lockmismatch = TRUE; 982 break; 983 } 984 } 985 986 if( lockmismatch ) 987 { 988 *complete = FALSE; 989 if( onlyifcomplete ) 990 stopped = TRUE; 991 } 992 } 993 994 if( !stopped ) 995 { 996 /* calculate row activity bounds */ 997 SCIP_CALL( calcActivityBounds(scip, matrix) ); 998 999 /* transform row major format into column major format */ 1000 SCIP_CALL( setColumnMajorFormat(scip, matrix) ); 1001 1002 *initialized = TRUE; 1003 } 1004 else 1005 { 1006 SCIPfreeBufferArray(scip, &matrix->maxactivityposinf); 1007 SCIPfreeBufferArray(scip, &matrix->maxactivityneginf); 1008 SCIPfreeBufferArray(scip, &matrix->minactivityposinf); 1009 SCIPfreeBufferArray(scip, &matrix->minactivityneginf); 1010 SCIPfreeBufferArray(scip, &matrix->maxactivity); 1011 SCIPfreeBufferArray(scip, &matrix->minactivity); 1012 1013 SCIPfreeMemoryArray(scip, &matrix->isrhsinfinite); 1014 SCIPfreeBufferArray(scip, &matrix->cons); 1015 1016 SCIPfreeBufferArray(scip, &matrix->rhs); 1017 SCIPfreeBufferArray(scip, &matrix->lhs); 1018 SCIPfreeBufferArray(scip, &matrix->rowmatcnt); 1019 SCIPfreeBufferArray(scip, &matrix->rowmatbeg); 1020 SCIPfreeBufferArray(scip, &matrix->rowmatind); 1021 SCIPfreeBufferArray(scip, &matrix->rowmatval); 1022 1023 SCIPfreeBufferArray(scip, &matrix->ndownlocks); 1024 SCIPfreeBufferArray(scip, &matrix->nuplocks); 1025 SCIPfreeBufferArray(scip, &matrix->ub); 1026 SCIPfreeBufferArray(scip, &matrix->lb); 1027 SCIPfreeBufferArray(scip, &matrix->colmatcnt); 1028 SCIPfreeBufferArray(scip, &matrix->colmatbeg); 1029 SCIPfreeBufferArray(scip, &matrix->colmatind); 1030 SCIPfreeBufferArray(scip, &matrix->colmatval); 1031 SCIPfreeBufferArrayNull(scip, &matrix->vars); 1032 1033 SCIPfreeBuffer(scip, matrixptr); 1034 } 1035 1036 return SCIP_OKAY; 1037 } 1038 1039 1040 /** frees the constraint matrix */ 1041 void SCIPmatrixFree( 1042 SCIP* scip, /**< current SCIP instance */ 1043 SCIP_MATRIX** matrix /**< constraint matrix object */ 1044 ) 1045 { 1046 assert(scip != NULL); 1047 assert(matrix != NULL); 1048 1049 if( (*matrix) != NULL ) 1050 { 1051 assert((*matrix)->colmatval != NULL); 1052 assert((*matrix)->colmatind != NULL); 1053 assert((*matrix)->colmatbeg != NULL); 1054 assert((*matrix)->colmatcnt != NULL); 1055 assert((*matrix)->lb != NULL); 1056 assert((*matrix)->ub != NULL); 1057 assert((*matrix)->nuplocks != NULL); 1058 assert((*matrix)->ndownlocks != NULL); 1059 1060 assert((*matrix)->rowmatval != NULL); 1061 assert((*matrix)->rowmatind != NULL); 1062 assert((*matrix)->rowmatbeg != NULL); 1063 assert((*matrix)->rowmatcnt != NULL); 1064 assert((*matrix)->lhs != NULL); 1065 assert((*matrix)->rhs != NULL); 1066 1067 SCIPfreeBufferArray(scip, &((*matrix)->maxactivityposinf)); 1068 SCIPfreeBufferArray(scip, &((*matrix)->maxactivityneginf)); 1069 SCIPfreeBufferArray(scip, &((*matrix)->minactivityposinf)); 1070 SCIPfreeBufferArray(scip, &((*matrix)->minactivityneginf)); 1071 SCIPfreeBufferArray(scip, &((*matrix)->maxactivity)); 1072 SCIPfreeBufferArray(scip, &((*matrix)->minactivity)); 1073 1074 SCIPfreeMemoryArray(scip, &((*matrix)->isrhsinfinite)); 1075 SCIPfreeBufferArray(scip, &((*matrix)->cons)); 1076 1077 SCIPfreeBufferArray(scip, &((*matrix)->rhs)); 1078 SCIPfreeBufferArray(scip, &((*matrix)->lhs)); 1079 SCIPfreeBufferArray(scip, &((*matrix)->rowmatcnt)); 1080 SCIPfreeBufferArray(scip, &((*matrix)->rowmatbeg)); 1081 SCIPfreeBufferArray(scip, &((*matrix)->rowmatind)); 1082 SCIPfreeBufferArray(scip, &((*matrix)->rowmatval)); 1083 1084 SCIPfreeBufferArray(scip, &((*matrix)->ndownlocks)); 1085 SCIPfreeBufferArray(scip, &((*matrix)->nuplocks)); 1086 SCIPfreeBufferArray(scip, &((*matrix)->ub)); 1087 SCIPfreeBufferArray(scip, &((*matrix)->lb)); 1088 SCIPfreeBufferArray(scip, &((*matrix)->colmatcnt)); 1089 SCIPfreeBufferArray(scip, &((*matrix)->colmatbeg)); 1090 SCIPfreeBufferArray(scip, &((*matrix)->colmatind)); 1091 SCIPfreeBufferArray(scip, &((*matrix)->colmatval)); 1092 1093 (*matrix)->nrows = 0; 1094 (*matrix)->ncols = 0; 1095 (*matrix)->nnonzs = 0; 1096 1097 SCIPfreeBufferArrayNull(scip, &((*matrix)->vars)); 1098 1099 SCIPfreeBuffer(scip, matrix); 1100 } 1101 } 1102 1103 /** print one row of the matrix */ 1104 void SCIPmatrixPrintRow( 1105 SCIP* scip, /**< current SCIP instance */ 1106 SCIP_MATRIX* matrix, /**< constraint matrix object */ 1107 int row /**< row index */ 1108 ) 1109 { 1110 int* rowpnt; 1111 int* rowend; 1112 int col; 1113 SCIP_Real val; 1114 SCIP_Real* valpnt; 1115 1116 SCIP_UNUSED(scip); 1117 1118 rowpnt = matrix->rowmatind + matrix->rowmatbeg[row]; 1119 rowend = rowpnt + matrix->rowmatcnt[row]; 1120 valpnt = matrix->rowmatval + matrix->rowmatbeg[row]; 1121 1122 printf("### %s: %.15g <=", SCIPconsGetName(matrix->cons[row]), matrix->lhs[row]); 1123 for(; (rowpnt < rowend); rowpnt++, valpnt++) 1124 { 1125 col = *rowpnt; 1126 val = *valpnt; 1127 if( val < 0 ) 1128 printf(" %.15g %s [%.15g,%.15g]", val, SCIPvarGetName(matrix->vars[col]), 1129 SCIPvarGetLbGlobal(matrix->vars[col]), SCIPvarGetUbGlobal(matrix->vars[col])); 1130 else 1131 printf(" +%.15g %s [%.15g,%.15g]", val, SCIPvarGetName(matrix->vars[col]), 1132 SCIPvarGetLbGlobal(matrix->vars[col]), SCIPvarGetUbGlobal(matrix->vars[col])); 1133 } 1134 printf(" <= %.15g ###\n", matrix->rhs[row]); 1135 } 1136 1137 /** removes the bounds of a column and updates the activities accordingly */ 1138 void SCIPmatrixRemoveColumnBounds( 1139 SCIP* scip, /**< current scip instance */ 1140 SCIP_MATRIX* matrix, /**< constraint matrix */ 1141 int col /**< column variable to remove bounds from */ 1142 ) 1143 { 1144 int colmatend = matrix->colmatbeg[col] + matrix->colmatcnt[col]; 1145 int i; 1146 1147 for( i = matrix->colmatbeg[col]; i != colmatend; ++i ) 1148 { 1149 int row = matrix->colmatind[i]; 1150 SCIP_Real val = matrix->colmatval[i]; 1151 1152 /* set lower bound to -infinity if necessary */ 1153 if( !SCIPisInfinity(scip, -matrix->lb[col]) ) 1154 { 1155 if( val > 0.0 ) 1156 matrix->minactivityneginf[row]++; 1157 else 1158 matrix->maxactivityneginf[row]++; 1159 } 1160 1161 /* set upper bound to infinity if necessary */ 1162 if( !SCIPisInfinity(scip, matrix->ub[col]) ) 1163 { 1164 if( val > 0.0 ) 1165 matrix->maxactivityposinf[row]++; 1166 else 1167 matrix->minactivityposinf[row]++; 1168 } 1169 1170 assert(matrix->maxactivityneginf[row] + matrix->maxactivityposinf[row] > 0); 1171 assert(matrix->minactivityneginf[row] + matrix->minactivityposinf[row] > 0); 1172 1173 /* mark the activities of the rows to be infinite */ 1174 matrix->maxactivity[row] = SCIPinfinity(scip); 1175 matrix->minactivity[row] = -SCIPinfinity(scip); 1176 } 1177 1178 matrix->lb[col] = -SCIPinfinity(scip); 1179 matrix->ub[col] = SCIPinfinity(scip); 1180 } 1181 1182 /** detect parallel rows of matrix. rhs/lhs are ignored. */ 1183 SCIP_RETCODE SCIPmatrixGetParallelRows( 1184 SCIP* scip, /**< SCIP instance */ 1185 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 1186 SCIP_Real* scale, /**< scale factors of rows */ 1187 int* pclass /**< parallel row classes */ 1188 ) 1189 { 1190 SCIP_Real* valpnt; 1191 SCIP_Real* values; 1192 int* classsizes; 1193 int* pcset; 1194 int* colpnt; 1195 int* colend; 1196 int* rowindices; 1197 int* pcs; 1198 SCIP_Real startval; 1199 SCIP_Real aij; 1200 int startpc; 1201 int startk; 1202 int startt; 1203 int pcsetfill; 1204 int rowidx; 1205 int k; 1206 int t; 1207 int m; 1208 int i; 1209 int c; 1210 int newpclass; 1211 int pc; 1212 1213 assert(scip != NULL); 1214 assert(matrix != NULL); 1215 assert(pclass != NULL); 1216 1217 SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, matrix->nrows) ); 1218 SCIP_CALL( SCIPallocBufferArray(scip, &pcset, matrix->nrows) ); 1219 SCIP_CALL( SCIPallocBufferArray(scip, &values, matrix->nrows) ); 1220 SCIP_CALL( SCIPallocBufferArray(scip, &rowindices, matrix->nrows) ); 1221 SCIP_CALL( SCIPallocBufferArray(scip, &pcs, matrix->nrows) ); 1222 1223 /* init */ 1224 BMSclearMemoryArray(scale, matrix->nrows); 1225 BMSclearMemoryArray(pclass, matrix->nrows); 1226 BMSclearMemoryArray(classsizes, matrix->nrows); 1227 classsizes[0] = matrix->nrows; 1228 pcsetfill = 0; 1229 for( t = 1; t < matrix->nrows; ++t ) 1230 pcset[pcsetfill++] = t; 1231 1232 /* loop over all columns */ 1233 for( c = 0; c < matrix->ncols; ++c ) 1234 { 1235 if( matrix->colmatcnt[c] == 0 ) 1236 continue; 1237 1238 colpnt = matrix->colmatind + matrix->colmatbeg[c]; 1239 colend = colpnt + matrix->colmatcnt[c]; 1240 valpnt = matrix->colmatval + matrix->colmatbeg[c]; 1241 1242 i = 0; 1243 for( ; (colpnt < colend); colpnt++, valpnt++ ) 1244 { 1245 aij = *valpnt; 1246 rowidx = *colpnt; 1247 1248 if( scale[rowidx] == 0.0 ) 1249 scale[rowidx] = aij; 1250 assert(scale[rowidx] != 0.0); 1251 1252 rowindices[i] = rowidx; 1253 values[i] = aij / scale[rowidx]; 1254 pc = pclass[rowidx]; 1255 assert(pc < matrix->nrows); 1256 1257 /* update class sizes and pclass set */ 1258 assert(classsizes[pc] > 0); 1259 classsizes[pc]--; 1260 if( classsizes[pc] == 0 ) 1261 { 1262 assert(pcsetfill < matrix->nrows); 1263 pcset[pcsetfill++] = pc; 1264 } 1265 pcs[i] = pc; 1266 1267 i++; 1268 } 1269 1270 /* sort on the pclass values */ 1271 if( i > 1 ) 1272 { 1273 SCIPsortIntIntReal(pcs, rowindices, values, i); 1274 } 1275 1276 k = 0; 1277 while( TRUE ) /*lint !e716*/ 1278 { 1279 assert(k < i); 1280 startpc = pcs[k]; 1281 startk = k; 1282 1283 /* find pclass-sets */ 1284 while( k < i && pcs[k] == startpc ) 1285 k++; 1286 1287 /* sort on the A values which have equal pclass values */ 1288 if( k - startk > 1 ) 1289 SCIPsortRealInt(&(values[startk]), &(rowindices[startk]), k - startk); 1290 1291 t = 0; 1292 while( TRUE ) /*lint !e716*/ 1293 { 1294 assert(startk + t < i); 1295 startval = values[startk + t]; 1296 startt = t; 1297 1298 /* find A-sets */ 1299 while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) ) 1300 t++; 1301 1302 /* get new pclass */ 1303 newpclass = pcset[0]; 1304 assert(pcsetfill > 0); 1305 pcset[0] = pcset[--pcsetfill]; 1306 1307 /* renumbering */ 1308 for( m = startk + startt; m < startk + t; m++ ) 1309 { 1310 assert(m < i); 1311 assert(rowindices[m] < matrix->nrows); 1312 assert(newpclass < matrix->nrows); 1313 1314 pclass[rowindices[m]] = newpclass; 1315 classsizes[newpclass]++; 1316 } 1317 1318 if( t == k - startk ) 1319 break; 1320 } 1321 1322 if( k == matrix->colmatcnt[c] ) 1323 break; 1324 } 1325 } 1326 1327 SCIPfreeBufferArray(scip, &pcs); 1328 SCIPfreeBufferArray(scip, &rowindices); 1329 SCIPfreeBufferArray(scip, &values); 1330 SCIPfreeBufferArray(scip, &pcset); 1331 SCIPfreeBufferArray(scip, &classsizes); 1332 1333 return SCIP_OKAY; 1334 } 1335 1336 /** detect parallel rows of matrix. 1337 * obj coefficients are ignored. 1338 */ 1339 SCIP_RETCODE SCIPmatrixGetParallelCols( 1340 SCIP* scip, /**< SCIP instance */ 1341 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 1342 SCIP_Real* scale, /**< scale factors of cols */ 1343 int* pclass, /**< parallel column classes */ 1344 SCIP_Bool* varineq /**< indicating if variable is within an equation */ 1345 ) 1346 { 1347 SCIP_Real* valpnt; 1348 SCIP_Real* values; 1349 int* classsizes; 1350 int* pcset; 1351 int* rowpnt; 1352 int* rowend; 1353 int* colindices; 1354 int* pcs; 1355 SCIP_Real startval; 1356 SCIP_Real aij; 1357 int startpc; 1358 int startk; 1359 int startt; 1360 int pcsetfill; 1361 int colidx; 1362 int k; 1363 int t; 1364 int m; 1365 int i; 1366 int r; 1367 int newpclass; 1368 int pc; 1369 1370 assert(scip != NULL); 1371 assert(matrix != NULL); 1372 assert(pclass != NULL); 1373 assert(varineq != NULL); 1374 1375 SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, matrix->ncols) ); 1376 SCIP_CALL( SCIPallocBufferArray(scip, &pcset, matrix->ncols) ); 1377 SCIP_CALL( SCIPallocBufferArray(scip, &values, matrix->ncols) ); 1378 SCIP_CALL( SCIPallocBufferArray(scip, &colindices, matrix->ncols) ); 1379 SCIP_CALL( SCIPallocBufferArray(scip, &pcs, matrix->ncols) ); 1380 1381 /* init */ 1382 BMSclearMemoryArray(scale, matrix->ncols); 1383 BMSclearMemoryArray(pclass, matrix->ncols); 1384 BMSclearMemoryArray(classsizes, matrix->ncols); 1385 classsizes[0] = matrix->ncols; 1386 pcsetfill = 0; 1387 for( t = 1; t < matrix->ncols; ++t ) 1388 pcset[pcsetfill++] = t; 1389 1390 /* loop over all rows */ 1391 for( r = 0; r < matrix->nrows; ++r ) 1392 { 1393 /* we consider only equations or ranged rows */ 1394 if( !matrix->isrhsinfinite[r] ) 1395 { 1396 rowpnt = matrix->rowmatind + matrix->rowmatbeg[r]; 1397 rowend = rowpnt + matrix->rowmatcnt[r]; 1398 valpnt = matrix->rowmatval + matrix->rowmatbeg[r]; 1399 1400 i = 0; 1401 for( ; (rowpnt < rowend); rowpnt++, valpnt++ ) 1402 { 1403 aij = *valpnt; 1404 colidx = *rowpnt; 1405 1406 /* remember variable was part of an equation or ranged row */ 1407 varineq[colidx] = TRUE; 1408 1409 if( scale[colidx] == 0.0 ) 1410 scale[colidx] = aij; 1411 assert(scale[colidx] != 0.0); 1412 1413 colindices[i] = colidx; 1414 values[i] = aij / scale[colidx]; 1415 pc = pclass[colidx]; 1416 assert(pc < matrix->ncols); 1417 1418 /* update class sizes and pclass set */ 1419 assert(classsizes[pc] > 0); 1420 classsizes[pc]--; 1421 if( classsizes[pc] == 0 ) 1422 { 1423 assert(pcsetfill < matrix->ncols); 1424 pcset[pcsetfill++] = pc; 1425 } 1426 pcs[i] = pc; 1427 1428 i++; 1429 } 1430 1431 /* sort on the pclass values */ 1432 if( i > 1 ) 1433 { 1434 SCIPsortIntIntReal(pcs, colindices, values, i); 1435 } 1436 1437 k = 0; 1438 while( TRUE ) /*lint !e716*/ 1439 { 1440 assert(k < i); 1441 startpc = pcs[k]; 1442 startk = k; 1443 1444 /* find pclass-sets */ 1445 while( k < i && pcs[k] == startpc ) 1446 k++; 1447 1448 /* sort on the A values which have equal pclass values */ 1449 if( k - startk > 1 ) 1450 SCIPsortRealInt(&(values[startk]), &(colindices[startk]), k - startk); 1451 1452 t = 0; 1453 while( TRUE ) /*lint !e716*/ 1454 { 1455 assert(startk + t < i); 1456 startval = values[startk + t]; 1457 startt = t; 1458 1459 /* find A-sets */ 1460 while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) ) 1461 t++; 1462 1463 /* get new pclass */ 1464 newpclass = pcset[0]; 1465 assert(pcsetfill > 0); 1466 pcset[0] = pcset[--pcsetfill]; 1467 1468 /* renumbering */ 1469 for( m = startk + startt; m < startk + t; m++ ) 1470 { 1471 assert(m < i); 1472 assert(colindices[m] < matrix->ncols); 1473 assert(newpclass < matrix->ncols); 1474 1475 pclass[colindices[m]] = newpclass; 1476 classsizes[newpclass]++; 1477 } 1478 1479 if( t == k - startk ) 1480 break; 1481 } 1482 1483 if( k == matrix->rowmatcnt[r] ) 1484 break; 1485 } 1486 } 1487 } 1488 1489 SCIPfreeBufferArray(scip, &pcs); 1490 SCIPfreeBufferArray(scip, &colindices); 1491 SCIPfreeBufferArray(scip, &values); 1492 SCIPfreeBufferArray(scip, &pcset); 1493 SCIPfreeBufferArray(scip, &classsizes); 1494 1495 return SCIP_OKAY; 1496 } 1497 1498 1499 /* 1500 * access functions implemented as defines 1501 */ 1502 1503 /* In debug mode, the following methods are implemented as function calls to ensure 1504 * type validity. 1505 * In optimized mode, the methods are implemented as defines to improve performance. 1506 * However, we want to have them in the library anyways, so we have to undef the defines. 1507 */ 1508 1509 #undef SCIPmatrixGetColValPtr 1510 #undef SCIPmatrixGetColIdxPtr 1511 #undef SCIPmatrixGetColNNonzs 1512 #undef SCIPmatrixGetNColumns 1513 #undef SCIPmatrixGetColUb 1514 #undef SCIPmatrixGetColLb 1515 #undef SCIPmatrixGetColNUplocks 1516 #undef SCIPmatrixGetColNDownlocks 1517 #undef SCIPmatrixGetVar 1518 #undef SCIPmatrixGetColName 1519 #undef SCIPmatrixGetRowValPtr 1520 #undef SCIPmatrixGetRowIdxPtr 1521 #undef SCIPmatrixGetRowNNonzs 1522 #undef SCIPmatrixGetRowName 1523 #undef SCIPmatrixGetNRows 1524 #undef SCIPmatrixGetRowLhs 1525 #undef SCIPmatrixGetRowRhs 1526 #undef SCIPmatrixIsRowRhsInfinity 1527 #undef SCIPmatrixGetNNonzs 1528 #undef SCIPmatrixGetRowMinActivity 1529 #undef SCIPmatrixGetRowMaxActivity 1530 #undef SCIPmatrixGetRowNMinActNegInf 1531 #undef SCIPmatrixGetRowNMinActPosInf 1532 #undef SCIPmatrixGetRowNMaxActNegInf 1533 #undef SCIPmatrixGetRowNMaxActPosInf 1534 #undef SCIPmatrixGetCons 1535 1536 /** get column based start pointer of values */ 1537 SCIP_Real* SCIPmatrixGetColValPtr( 1538 SCIP_MATRIX* matrix, /**< matrix instance */ 1539 int col /**< column index */ 1540 ) 1541 { 1542 assert(matrix != NULL); 1543 assert(0 <= col && col < matrix->ncols); 1544 1545 return matrix->colmatval + matrix->colmatbeg[col]; 1546 } 1547 1548 /** get column based start pointer of row indices */ 1549 int* SCIPmatrixGetColIdxPtr( 1550 SCIP_MATRIX* matrix, /**< matrix instance */ 1551 int col /**< column index */ 1552 ) 1553 { 1554 assert(matrix != NULL); 1555 assert(0 <= col && col < matrix->ncols); 1556 1557 return matrix->colmatind + matrix->colmatbeg[col]; 1558 } 1559 1560 /** get the number of non-zero entries of this column */ 1561 int SCIPmatrixGetColNNonzs( 1562 SCIP_MATRIX* matrix, /**< matrix instance */ 1563 int col /**< column index */ 1564 ) 1565 { 1566 assert(matrix != NULL); 1567 assert(0 <= col && col < matrix->ncols); 1568 1569 return matrix->colmatcnt[col]; 1570 } 1571 1572 /** get number of columns of the matrix */ 1573 int SCIPmatrixGetNColumns( 1574 SCIP_MATRIX* matrix /**< matrix instance */ 1575 ) 1576 { 1577 assert(matrix != NULL); 1578 1579 return matrix->ncols; 1580 } 1581 1582 /** get upper bound of column */ 1583 SCIP_Real SCIPmatrixGetColUb( 1584 SCIP_MATRIX* matrix, /**< matrix instance */ 1585 int col /**< column index */ 1586 ) 1587 { 1588 assert(matrix != NULL); 1589 1590 return matrix->ub[col]; 1591 } 1592 1593 /** get lower bound of column */ 1594 SCIP_Real SCIPmatrixGetColLb( 1595 SCIP_MATRIX* matrix, /**< matrix instance */ 1596 int col /**< column index */ 1597 ) 1598 { 1599 assert(matrix != NULL); 1600 1601 return matrix->lb[col]; 1602 } 1603 1604 /** get number of uplocks of column */ 1605 int SCIPmatrixGetColNUplocks( 1606 SCIP_MATRIX* matrix, /**< matrix instance */ 1607 int col /**< column index */ 1608 ) 1609 { 1610 assert(matrix != NULL); 1611 assert(0 <= col && col < matrix->ncols); 1612 1613 return matrix->nuplocks[col]; 1614 } 1615 1616 /** get number of downlocks of column */ 1617 int SCIPmatrixGetColNDownlocks( 1618 SCIP_MATRIX* matrix, /**< matrix instance */ 1619 int col /**< column index */ 1620 ) 1621 { 1622 assert(matrix != NULL); 1623 assert(0 <= col && col < matrix->ncols); 1624 1625 return matrix->ndownlocks[col]; 1626 } 1627 1628 /** get variable pointer of column */ 1629 SCIP_VAR* SCIPmatrixGetVar( 1630 SCIP_MATRIX* matrix, /**< matrix instance */ 1631 int col /**< column index */ 1632 ) 1633 { 1634 assert(matrix != NULL); 1635 assert(0 <= col && col < matrix->ncols); 1636 1637 return matrix->vars[col]; 1638 } 1639 1640 /** get name of column/variable */ 1641 const char* SCIPmatrixGetColName( 1642 SCIP_MATRIX* matrix, /**< matrix instance */ 1643 int col /**< column index */ 1644 ) 1645 { 1646 assert(matrix != NULL); 1647 assert(0 <= col && col < matrix->ncols); 1648 1649 return SCIPvarGetName(matrix->vars[col]); 1650 } 1651 1652 /** get row based start pointer of values */ 1653 SCIP_Real* SCIPmatrixGetRowValPtr( 1654 SCIP_MATRIX* matrix, /**< matrix instance */ 1655 int row /**< row index */ 1656 ) 1657 { 1658 assert(matrix != NULL); 1659 assert(0 <= row && row < matrix->nrows); 1660 1661 return matrix->rowmatval + matrix->rowmatbeg[row]; 1662 } 1663 1664 /** get row based start pointer of column indices */ 1665 int* SCIPmatrixGetRowIdxPtr( 1666 SCIP_MATRIX* matrix, /**< matrix instance */ 1667 int row /**< row index */ 1668 ) 1669 { 1670 assert(matrix != NULL); 1671 assert(0 <= row && row < matrix->nrows); 1672 1673 return matrix->rowmatind + matrix->rowmatbeg[row]; 1674 } 1675 1676 /** get number of non-zeros of this row */ 1677 int SCIPmatrixGetRowNNonzs( 1678 SCIP_MATRIX* matrix, /**< matrix instance */ 1679 int row /**< row index */ 1680 ) 1681 { 1682 assert(matrix != NULL); 1683 assert(0 <= row && row < matrix->nrows); 1684 1685 return matrix->rowmatcnt[row]; 1686 } 1687 1688 /** get name of row */ 1689 const char* SCIPmatrixGetRowName( 1690 SCIP_MATRIX* matrix, /**< matrix instance */ 1691 int row /**< row index */ 1692 ) 1693 { 1694 assert(matrix != NULL); 1695 assert(0 <= row && row < matrix->nrows); 1696 1697 return SCIPconsGetName(matrix->cons[row]); 1698 } 1699 1700 /** get number of rows of the matrix */ 1701 int SCIPmatrixGetNRows( 1702 SCIP_MATRIX* matrix /**< matrix instance */ 1703 ) 1704 { 1705 assert(matrix != NULL); 1706 1707 return matrix->nrows; 1708 } 1709 1710 /** get left-hand-side of row */ 1711 SCIP_Real SCIPmatrixGetRowLhs( 1712 SCIP_MATRIX* matrix, /**< matrix instance */ 1713 int row /**< row index */ 1714 ) 1715 { 1716 assert(matrix != NULL); 1717 assert(0 <= row && row < matrix->nrows); 1718 1719 return matrix->lhs[row]; 1720 } 1721 1722 /** get right-hand-side of row */ 1723 SCIP_Real SCIPmatrixGetRowRhs( 1724 SCIP_MATRIX* matrix, /**< matrix instance */ 1725 int row /**< row index */ 1726 ) 1727 { 1728 assert(matrix != NULL); 1729 assert(0 <= row && row < matrix->nrows); 1730 1731 return matrix->rhs[row]; 1732 } 1733 1734 /** flag indicating if right-hand-side of row is infinity */ 1735 SCIP_Bool SCIPmatrixIsRowRhsInfinity( 1736 SCIP_MATRIX* matrix, /**< matrix instance */ 1737 int row /**< row index */ 1738 ) 1739 { 1740 assert(matrix != NULL); 1741 assert(0 <= row && row < matrix->nrows); 1742 1743 return matrix->isrhsinfinite[row]; 1744 } 1745 1746 /** get number of non-zeros of matrix */ 1747 int SCIPmatrixGetNNonzs( 1748 SCIP_MATRIX* matrix /**< matrix instance */ 1749 ) 1750 { 1751 assert(matrix != NULL); 1752 1753 return matrix->nnonzs; 1754 } 1755 1756 /** get minimal activity of row */ 1757 SCIP_Real SCIPmatrixGetRowMinActivity( 1758 SCIP_MATRIX* matrix, /**< matrix instance */ 1759 int row /**< row index */ 1760 ) 1761 { 1762 assert(matrix != NULL); 1763 assert(0 <= row && row < matrix->nrows); 1764 1765 return matrix->minactivity[row]; 1766 } 1767 1768 /** get maximal activity of row */ 1769 SCIP_Real SCIPmatrixGetRowMaxActivity( 1770 SCIP_MATRIX* matrix, /**< matrix instance */ 1771 int row /**< row index */ 1772 ) 1773 { 1774 assert(matrix != NULL); 1775 assert(0 <= row && row < matrix->nrows); 1776 1777 return matrix->maxactivity[row]; 1778 } 1779 1780 /** get number of negative infinities present within minimal activity */ 1781 int SCIPmatrixGetRowNMinActNegInf( 1782 SCIP_MATRIX* matrix, /**< matrix instance */ 1783 int row /**< row index */ 1784 ) 1785 { 1786 assert(matrix != NULL); 1787 assert(0 <= row && row < matrix->nrows); 1788 1789 return matrix->minactivityneginf[row]; 1790 } 1791 1792 /** get number of positive infinities present within minimal activity */ 1793 int SCIPmatrixGetRowNMinActPosInf( 1794 SCIP_MATRIX* matrix, /**< matrix instance */ 1795 int row /**< row index */ 1796 ) 1797 { 1798 assert(matrix != NULL); 1799 assert(0 <= row && row < matrix->nrows); 1800 1801 return matrix->minactivityposinf[row]; 1802 } 1803 1804 /** get number of negative infinities present within maximal activity */ 1805 int SCIPmatrixGetRowNMaxActNegInf( 1806 SCIP_MATRIX* matrix, /**< matrix instance */ 1807 int row /**< row index */ 1808 ) 1809 { 1810 assert(matrix != NULL); 1811 assert(0 <= row && row < matrix->nrows); 1812 1813 return matrix->maxactivityneginf[row]; 1814 } 1815 1816 /** get number of positive infinities present within maximal activity */ 1817 int SCIPmatrixGetRowNMaxActPosInf( 1818 SCIP_MATRIX* matrix, /**< matrix instance */ 1819 int row /**< row index */ 1820 ) 1821 { 1822 assert(matrix != NULL); 1823 assert(0 <= row && row < matrix->nrows); 1824 1825 return matrix->maxactivityposinf[row]; 1826 } 1827 1828 /** get constraint pointer for constraint representing row */ 1829 SCIP_CONS* SCIPmatrixGetCons( 1830 SCIP_MATRIX* matrix, /**< matrix instance */ 1831 int row /**< row index */ 1832 ) 1833 { 1834 assert(matrix != NULL); 1835 assert(0 <= row && row < matrix->nrows); 1836 1837 return matrix->cons[row]; 1838 } 1839 1840 /** get if conflicting uplocks of a specific variable present */ 1841 SCIP_Bool SCIPmatrixUplockConflict( 1842 SCIP_MATRIX* matrix, /**< matrix instance */ 1843 int col /**< column index */ 1844 ) 1845 { 1846 assert(matrix != NULL); 1847 assert(0 <= col && col < matrix->ncols); 1848 1849 return (SCIPvarGetNLocksUpType(matrix->vars[col], SCIP_LOCKTYPE_MODEL) != matrix->nuplocks[col]); 1850 } 1851 1852 /** get if conflicting downlocks of a specific variable present */ 1853 SCIP_Bool SCIPmatrixDownlockConflict( 1854 SCIP_MATRIX* matrix, /**< matrix instance */ 1855 int col /**< column index */ 1856 ) 1857 { 1858 assert(matrix != NULL); 1859 assert(0 <= col && col < matrix->ncols); 1860 1861 return (SCIPvarGetNLocksDownType(matrix->vars[col], SCIP_LOCKTYPE_MODEL) != matrix->ndownlocks[col]); 1862 } 1863