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 sepa_aggregation.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief flow cover and complemented mixed integer rounding cuts separator (Marchand's version) 28 * @author Leona Gottwald 29 * @author Kati Wolter 30 * @author Tobias Achterberg 31 * 32 * For an overview see: 33 * 34 * Marchand, H., & Wolsey, L. A. (2001).@n 35 * Aggregation and mixed integer rounding to solve MIPs.@n 36 * Operations research, 49(3), 363-371. 37 * 38 * Some remarks: 39 * - In general, continuous variables are less prefered than integer variables, since their cut 40 * coefficient is worse. 41 * - We seek for aggregations that project out continuous variables that are far away from their bound, 42 * since if it is at its bound then it doesn't contribute to the violation 43 * - These aggregations are also useful for the flowcover separation, so after building an aggregation 44 * we try to generate a MIR cut and a flowcover cut. 45 * - We only keep the best cut. 46 */ 47 48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 49 50 #include "blockmemshell/memory.h" 51 #include "scip/cuts.h" 52 #include "scip/pub_lp.h" 53 #include "scip/pub_message.h" 54 #include "scip/pub_misc.h" 55 #include "scip/pub_misc_sort.h" 56 #include "scip/pub_sepa.h" 57 #include "scip/pub_var.h" 58 #include "scip/scip_branch.h" 59 #include "scip/scip_cut.h" 60 #include "scip/scip_general.h" 61 #include "scip/scip_lp.h" 62 #include "scip/scip_mem.h" 63 #include "scip/scip_message.h" 64 #include "scip/scip_numerics.h" 65 #include "scip/scip_param.h" 66 #include "scip/scip_prob.h" 67 #include "scip/scip_sepa.h" 68 #include "scip/scip_sol.h" 69 #include "scip/scip_solvingstats.h" 70 #include "scip/scip_tree.h" 71 #include "scip/scip_var.h" 72 #include "scip/sepa_aggregation.h" 73 #include <string.h> 74 75 76 #define SEPA_NAME "aggregation" 77 #define SEPA_DESC "aggregation heuristic for complemented mixed integer rounding cuts and flowcover cuts" 78 #define SEPA_PRIORITY -3000 79 #define SEPA_FREQ 10 80 #define SEPA_MAXBOUNDDIST 1.0 81 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */ 82 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 83 84 #define DEFAULT_MAXROUNDS -1 /**< maximal number of cmir separation rounds per node (-1: unlimited) */ 85 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of cmir separation rounds in the root node (-1: unlimited) */ 86 #define DEFAULT_MAXTRIES 200 /**< maximal number of rows to start aggregation with per separation round 87 * (-1: unlimited) */ 88 #define DEFAULT_MAXTRIESROOT -1 /**< maximal number of rows to start aggregation with per round in the root node 89 * (-1: unlimited) */ 90 #define DEFAULT_MAXFAILS 20 /**< maximal number of consecutive unsuccessful aggregation tries (-1: unlimited) */ 91 #define DEFAULT_MAXFAILSROOT 100 /**< maximal number of consecutive unsuccessful aggregation tries in the root node 92 * (-1: unlimited) */ 93 #define DEFAULT_MAXAGGRS 3 /**< maximal number of aggregations for each row per separation round */ 94 #define DEFAULT_MAXAGGRSROOT 6 /**< maximal number of aggregations for each row per round in the root node */ 95 #define DEFAULT_MAXSEPACUTS 100 /**< maximal number of cmir cuts separated per separation round */ 96 #define DEFAULT_MAXSEPACUTSROOT 500 /**< maximal number of cmir cuts separated per separation round in root node */ 97 #define DEFAULT_MAXSLACK 0.0 /**< maximal slack of rows to be used in aggregation */ 98 #define DEFAULT_MAXSLACKROOT 0.1 /**< maximal slack of rows to be used in aggregation in the root node */ 99 #define DEFAULT_DENSITYSCORE 1e-4 /**< weight of row density in the aggregation scoring of the rows */ 100 #define DEFAULT_SLACKSCORE 1e-3 /**< weight of slack in the aggregation scoring of the rows */ 101 #define DEFAULT_MAXAGGDENSITY 0.20 /**< maximal density of aggregated row */ 102 #define DEFAULT_MAXROWDENSITY 0.05 /**< maximal density of row to be used in aggregation */ 103 #define DEFAULT_DENSITYOFFSET 100 /**< additional number of variables allowed in row on top of density */ 104 #define DEFAULT_MAXROWFAC 1e+4 /**< maximal row aggregation factor */ 105 #define DEFAULT_MAXTESTDELTA -1 /**< maximal number of different deltas to try (-1: unlimited) */ 106 #define DEFAULT_AGGRTOL 1e-2 /**< aggregation heuristic: we try to delete continuous variables from the current 107 * aggregation, whose distance to its tightest bound is >= L - DEFAULT_AGGRTOL, 108 * where L is the largest of the distances between a continuous variable's value 109 * and its tightest bound in the current aggregation */ 110 #define DEFAULT_TRYNEGSCALING TRUE /**< should negative values also be tested in scaling? */ 111 #define DEFAULT_FIXINTEGRALRHS TRUE /**< should an additional variable be complemented if f0 = 0? */ 112 #define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */ 113 114 #define BOUNDSWITCH 0.5 115 #define POSTPROCESS TRUE 116 #define USEVBDS TRUE 117 #define MINFRAC 0.05 118 #define MAXFRAC 0.999 119 #define MAKECONTINTEGRAL FALSE 120 #define IMPLINTSARECONT 121 122 123 /* 124 * Data structures 125 */ 126 127 /** separator data */ 128 struct SCIP_SepaData 129 { 130 SCIP_Real maxslack; /**< maximal slack of rows to be used in aggregation */ 131 SCIP_Real maxslackroot; /**< maximal slack of rows to be used in aggregation in the root node */ 132 SCIP_Real densityscore; /**< weight of row density in the aggregation scoring of the rows */ 133 SCIP_Real slackscore; /**< weight of slack in the aggregation scoring of the rows */ 134 SCIP_Real maxaggdensity; /**< maximal density of aggregated row */ 135 SCIP_Real maxrowdensity; /**< maximal density of row to be used in aggregation */ 136 SCIP_Real maxrowfac; /**< maximal row aggregation factor */ 137 SCIP_Real aggrtol; /**< tolerance for bound distance used in aggregation heuristic */ 138 int maxrounds; /**< maximal number of cmir separation rounds per node (-1: unlimited) */ 139 int maxroundsroot; /**< maximal number of cmir separation rounds in the root node (-1: unlimited) */ 140 int maxtries; /**< maximal number of rows to start aggregation with per separation round 141 * (-1: unlimited) */ 142 int maxtriesroot; /**< maximal number of rows to start aggregation with per round in the root node 143 * (-1: unlimited) */ 144 int maxfails; /**< maximal number of consecutive unsuccessful aggregation tries 145 * (-1: unlimited) */ 146 int maxfailsroot; /**< maximal number of consecutive unsuccessful aggregation tries in the root 147 * node (-1: unlimited) */ 148 int maxaggrs; /**< maximal number of aggregations for each row per separation round */ 149 int maxaggrsroot; /**< maximal number of aggregations for each row per round in the root node */ 150 int maxsepacuts; /**< maximal number of cmir cuts separated per separation round */ 151 int maxsepacutsroot; /**< maximal number of cmir cuts separated per separation round in root node */ 152 int densityoffset; /**< additional number of variables allowed in row on top of density */ 153 int maxtestdelta; /**< maximal number of different deltas to try (-1: unlimited) */ 154 SCIP_Bool trynegscaling; /**< should negative values also be tested in scaling? */ 155 SCIP_Bool fixintegralrhs; /**< should an additional variable be complemented if f0 = 0? */ 156 SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */ 157 SCIP_Bool sepflowcover; /**< whether flowcover cuts should be separated in the current call */ 158 SCIP_Bool sepknapsackcover; /**< whether knapsack cover cuts should be separated in the current call */ 159 SCIP_Bool sepcmir; /**< whether cMIR cuts should be separated in the current call */ 160 SCIP_SEPA* cmir; /**< separator for adding cmir cuts */ 161 SCIP_SEPA* flowcover; /**< separator for adding flowcover cuts */ 162 SCIP_SEPA* knapsackcover; /**< separator for adding knapsack cover cuts */ 163 }; 164 165 /** data used for aggregation of row */ 166 typedef 167 struct AggregationData { 168 SCIP_Real* bounddist; /**< bound distance of continuous variables */ 169 int* bounddistinds; /**< problem indices of the continUous variables corresponding to the bounddistance value */ 170 int nbounddistvars; /**< number of continuous variables that are not at their bounds */ 171 SCIP_ROW** aggrrows; /**< array of rows suitable for substitution of continuous variable */ 172 SCIP_Real* aggrrowscoef; /**< coefficient of continuous variable in row that is suitable for substitution of that variable */ 173 int aggrrowssize; /**< size of aggrrows array */ 174 int naggrrows; /**< occupied positions in aggrrows array */ 175 int* aggrrowsstart; /**< array with start positions of suitable rows for substitution for each 176 * continuous variable with non-zero bound distance */ 177 int* ngoodaggrrows; /**< array with number of rows suitable for substitution that only contain 178 * one continuous variable that is not at it's bound */ 179 int* nbadvarsinrow; /**< number of continuous variables that are not at their bounds for each row */ 180 SCIP_AGGRROW* aggrrow; /**< store aggregation row here so that it can be reused */ 181 } AGGREGATIONDATA; 182 183 /* 184 * Local methods 185 */ 186 187 /** adds given cut to LP if violated */ 188 static 189 SCIP_RETCODE addCut( 190 SCIP* scip, /**< SCIP data structure */ 191 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */ 192 SCIP_SEPA* sepa, /**< separator */ 193 SCIP_Bool makeintegral, /**< should cut be scaled to integral coefficients if possible? */ 194 SCIP_Real* cutcoefs, /**< coefficients of active variables in cut */ 195 int* cutinds, /**< problem indices of variables in cut */ 196 int cutnnz, /**< number of non-zeros in cut */ 197 SCIP_Real cutrhs, /**< right hand side of cut */ 198 SCIP_Real cutefficacy, /**< efficacy of cut */ 199 SCIP_Bool cutislocal, /**< is the cut only locally valid? */ 200 SCIP_Bool cutremovable, /**< should the cut be removed from the LP due to aging or cleanup? */ 201 int cutrank, /**< rank of the cut */ 202 const char* cutclassname, /**< name of cut class to use for row names */ 203 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 204 int* ncuts, /**< pointer to count the number of added cuts */ 205 SCIP_ROW** thecut /**< pointer to return cut if it was added */ 206 ) 207 { 208 assert(scip != NULL); 209 assert(cutcoefs != NULL); 210 assert(cutoff != NULL); 211 assert(ncuts != NULL); 212 213 *cutoff = FALSE; 214 215 if( cutnnz > 0 && SCIPisEfficacious(scip, cutefficacy) ) 216 { 217 SCIP_VAR** vars; 218 int i; 219 SCIP_ROW* cut; 220 char cutname[SCIP_MAXSTRLEN]; 221 SCIP_Bool success; 222 223 /* get active problem variables */ 224 vars = SCIPgetVars(scip); 225 226 /* create cut name */ 227 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s%" SCIP_LONGINT_FORMAT "_%d", cutclassname, SCIPgetNLPs(scip), *ncuts); 228 229 tryagain: 230 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, cutremovable) ); 231 232 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 233 234 for( i = 0; i < cutnnz; ++i ) 235 { 236 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[i]], cutcoefs[i]) ); 237 } 238 239 /* set cut rank */ 240 SCIProwChgRank(cut, cutrank); 241 242 SCIPdebugMsg(scip, " -> found potential %s cut <%s>: rhs=%f, eff=%f\n", cutclassname, cutname, cutrhs, cutefficacy); 243 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) ); 244 245 /* if requested, try to scale the cut to integral values but only if the scaling is small; otherwise keep the fractional cut */ 246 if( makeintegral && SCIPgetRowNumIntCols(scip, cut) == SCIProwGetNNonz(cut) ) 247 { 248 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip), 249 1000LL, 1000.0, MAKECONTINTEGRAL, &success) ); 250 251 if( SCIPisInfinity(scip, SCIProwGetRhs(cut)) ) 252 { 253 /* release the row */ 254 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 255 256 /* the scaling destroyed the cut, so try to add it again, but this time do not scale it */ 257 makeintegral = FALSE; 258 goto tryagain; 259 } 260 } 261 else 262 { 263 success = FALSE; 264 } 265 266 if( success && !SCIPisCutEfficacious(scip, sol, cut) ) 267 { 268 SCIPdebugMsg(scip, " -> %s cut <%s> no longer efficacious: rhs=%f, eff=%f\n", cutclassname, cutname, cutrhs, cutefficacy); 269 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) ); 270 271 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 272 273 /* the cut is not efficacious anymore due to the scaling, so do not add it */ 274 return SCIP_OKAY; 275 } 276 277 SCIPdebugMsg(scip, " -> found %s cut <%s>: rhs=%f, eff=%f, rank=%d, min=%f, max=%f (range=%g)\n", 278 cutclassname, cutname, cutrhs, cutefficacy, SCIProwGetRank(cut), 279 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut), 280 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut)); 281 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) ); 282 283 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 284 285 if( SCIPisCutNew(scip, cut) ) 286 { 287 (*ncuts)++; 288 289 if( !cutislocal ) 290 { 291 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 292 } 293 else 294 { 295 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) ); 296 } 297 298 *thecut = cut; 299 } 300 else 301 { 302 /* release the row */ 303 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 304 } 305 } 306 307 return SCIP_OKAY; 308 } 309 310 /** setup data for aggregating rows */ 311 static 312 SCIP_RETCODE setupAggregationData( 313 SCIP* scip, /**< SCIP data structure */ 314 SCIP_SOL* sol, /**< solution to separate, NULL for LP solution */ 315 SCIP_Bool allowlocal, /**< should local cuts be allowed */ 316 AGGREGATIONDATA* aggrdata /**< pointer to aggregation data to setup */ 317 ) 318 { 319 SCIP_VAR** vars; 320 int nvars; 321 int nbinvars; 322 int nintvars; 323 int ncontvars; 324 int firstcontvar; 325 int nimplvars; 326 SCIP_ROW** rows; 327 int nrows; 328 int i; 329 330 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, &ncontvars) ); 331 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 332 333 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->bounddist, ncontvars + nimplvars) ); 334 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->bounddistinds, ncontvars + nimplvars) ); 335 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->ngoodaggrrows, ncontvars + nimplvars) ); 336 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->aggrrowsstart, ncontvars + nimplvars + 1) ); 337 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->nbadvarsinrow, nrows) ); 338 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrdata->aggrrow) ); 339 assert( aggrdata->aggrrow != NULL ); 340 BMSclearMemoryArray(aggrdata->nbadvarsinrow, nrows); 341 342 aggrdata->nbounddistvars = 0; 343 aggrdata->aggrrows = NULL; 344 aggrdata->aggrrowscoef = NULL; 345 aggrdata->aggrrowssize = 0; 346 aggrdata->naggrrows = 0; 347 348 firstcontvar = nvars - ncontvars; 349 350 for( i = nbinvars + nintvars; i < nvars; ++i ) 351 { 352 SCIP_Real bounddist; 353 SCIP_Real primsol; 354 SCIP_Real distlb; 355 SCIP_Real distub; 356 SCIP_Real bestlb; 357 SCIP_Real bestub; 358 SCIP_Real bestvlb; 359 SCIP_Real bestvub; 360 int bestvlbidx; 361 int bestvubidx; 362 363 /* compute the bound distance of the variable */ 364 if( allowlocal ) 365 { 366 bestlb = SCIPvarGetLbLocal(vars[i]); 367 bestub = SCIPvarGetUbLocal(vars[i]); 368 } 369 else 370 { 371 bestlb = SCIPvarGetLbGlobal(vars[i]); 372 bestub = SCIPvarGetUbGlobal(vars[i]); 373 } 374 375 SCIP_CALL( SCIPgetVarClosestVlb(scip, vars[i], sol, &bestvlb, &bestvlbidx) ); 376 SCIP_CALL( SCIPgetVarClosestVub(scip, vars[i], sol, &bestvub, &bestvubidx) ); 377 if( bestvlbidx >= 0 ) 378 bestlb = MAX(bestlb, bestvlb); 379 if( bestvubidx >= 0 ) 380 bestub = MIN(bestub, bestvub); 381 382 primsol = SCIPgetSolVal(scip, sol, vars[i]); 383 distlb = primsol - bestlb; 384 distub = bestub - primsol; 385 386 bounddist = MIN(distlb, distub); 387 bounddist = MAX(bounddist, 0.0); 388 389 /* prefer continuous variables over implicit integers to be aggregated out */ 390 if( i < firstcontvar ) 391 bounddist *= 0.1; 392 393 /* when variable is not at its bound, we want to project it out, so add it to the aggregation data */ 394 if( !SCIPisZero(scip, bounddist) ) 395 { 396 int k = aggrdata->nbounddistvars++; 397 398 aggrdata->bounddist[k] = bounddist; 399 aggrdata->bounddistinds[k] = i; 400 aggrdata->aggrrowsstart[k] = aggrdata->naggrrows; 401 402 /* the current variable is a bad variable (continuous, not at its bound): increase the number of bad variable 403 * count on each row this variables appears in; also each of these rows can be used to project the variable out 404 * so store them. 405 */ 406 if( SCIPvarIsInLP(vars[i]) ) 407 { 408 SCIP_COL* col = SCIPvarGetCol(vars[i]); 409 SCIP_ROW** colrows = SCIPcolGetRows(col); 410 SCIP_Real* colrowvals = SCIPcolGetVals(col); 411 int ncolnonzeros = SCIPcolGetNLPNonz(col); 412 int aggrrowsminsize = aggrdata->naggrrows + ncolnonzeros; 413 414 if( aggrrowsminsize > aggrdata->aggrrowssize ) 415 { 416 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrdata->aggrrows, aggrrowsminsize) ); 417 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrdata->aggrrowscoef, aggrrowsminsize) ); 418 aggrdata->aggrrowssize = aggrrowsminsize; 419 } 420 assert(aggrdata->aggrrows != NULL || aggrdata->aggrrowssize == 0); 421 assert(aggrdata->aggrrowscoef != NULL || aggrdata->aggrrowssize == 0); 422 assert(aggrdata->aggrrowssize > 0 || ncolnonzeros == 0); 423 424 for( k = 0; k < ncolnonzeros; ++k ) 425 { 426 /* ignore modifiable rows and local rows if those are not permitted */ 427 if( SCIProwIsModifiable(colrows[k]) || (!allowlocal && SCIProwIsLocal(colrows[k])) ) 428 continue; 429 430 ++aggrdata->nbadvarsinrow[SCIProwGetLPPos(colrows[k])]; 431 assert(aggrdata->aggrrows != NULL); /* for lint */ 432 assert(aggrdata->aggrrowscoef != NULL); 433 /* coverity[var_deref_op] */ 434 aggrdata->aggrrows[aggrdata->naggrrows] = colrows[k]; 435 aggrdata->aggrrowscoef[aggrdata->naggrrows] = colrowvals[k]; 436 ++aggrdata->naggrrows; 437 } 438 } 439 } 440 } 441 442 /* add sentinel entry at the end */ 443 aggrdata->aggrrowsstart[aggrdata->nbounddistvars] = aggrdata->naggrrows; 444 445 /* for each continous variable that is not at its bounds check if there is a 446 * row where it is the only such variable ("good" rows). In the array with the rows that are 447 * suitable for substituting this variable move the good rows to the beginning 448 * and store the number of good rows for each of the variables. 449 * If a variable has at least one good row, then it is a "better" variable and we make 450 * the value of the bounddistance for this variable negative, to mark it. 451 * Note that better variables are continous variables that are not at their bounds 452 * and can be projected out without introducing bad variables (by using a good row). 453 */ 454 { 455 int beg; 456 457 beg = aggrdata->aggrrowsstart[0]; 458 for( i = 0; i < aggrdata->nbounddistvars; ++i ) 459 { 460 int k; 461 int ngoodrows; 462 int end; 463 464 end = aggrdata->aggrrowsstart[i + 1]; 465 ngoodrows = 0; 466 for( k = beg; k < end; ++k ) 467 { 468 /* coverity[var_deref_op] */ 469 int lppos = SCIProwGetLPPos(aggrdata->aggrrows[k]); 470 471 if( aggrdata->nbadvarsinrow[lppos] == 1 && 472 SCIPisEQ(scip, SCIProwGetLhs(aggrdata->aggrrows[k]), SCIProwGetRhs(aggrdata->aggrrows[k])) ) 473 { 474 int nextgoodrowpos = beg + ngoodrows; 475 if( k > nextgoodrowpos ) 476 { 477 SCIPswapPointers((void**) (&aggrdata->aggrrows[k]), (void**) (&aggrdata->aggrrows[nextgoodrowpos])); 478 SCIPswapReals(&aggrdata->aggrrowscoef[k], &aggrdata->aggrrowscoef[nextgoodrowpos]); 479 } 480 ++ngoodrows; 481 } 482 } 483 if( ngoodrows > 0 ) 484 { 485 aggrdata->bounddist[i] = -aggrdata->bounddist[i]; 486 } 487 aggrdata->ngoodaggrrows[i] = ngoodrows; 488 beg = end; 489 } 490 } 491 492 return SCIP_OKAY; 493 } 494 495 /** free resources held in aggregation data */ 496 static 497 void destroyAggregationData( 498 SCIP* scip, /**< SCIP datastructure */ 499 AGGREGATIONDATA* aggrdata /**< pointer to ggregation data */ 500 ) 501 { 502 SCIPaggrRowFree(scip, &aggrdata->aggrrow); 503 SCIPfreeBufferArrayNull(scip, &aggrdata->aggrrowscoef); 504 SCIPfreeBufferArrayNull(scip, &aggrdata->aggrrows); 505 SCIPfreeBufferArray(scip, &aggrdata->nbadvarsinrow); 506 SCIPfreeBufferArray(scip, &aggrdata->aggrrowsstart); 507 SCIPfreeBufferArray(scip, &aggrdata->ngoodaggrrows); 508 SCIPfreeBufferArray(scip, &aggrdata->bounddistinds); 509 SCIPfreeBufferArray(scip, &aggrdata->bounddist); 510 } 511 512 /** retrieves the candidate rows for canceling out the given variable, also returns the number of "good" rows which are the 513 * rows stored at the first ngoodrows positions. A row is good if its continuous variables are all at their bounds, except 514 * maybe the given continuous variable (in probvaridx) 515 */ 516 static 517 SCIP_Bool getRowAggregationCandidates( 518 AGGREGATIONDATA* aggrdata, /**< pointer to ggregation data */ 519 int probvaridx, /**< problem index of variables to retrieve candidates for */ 520 SCIP_ROW*** rows, /**< pointer to store array to candidate rows */ 521 SCIP_Real** rowvarcoefs, /**< pointer to store array of coefficients of given variable in the corresponding rows */ 522 int* nrows, /**< pointer to return number of rows in returned arrays */ 523 int* ngoodrows /**< pointer to return number of "good" rows in the returned arrays */ 524 ) 525 { 526 int aggrdataidx; 527 528 if( !SCIPsortedvecFindInt(aggrdata->bounddistinds, probvaridx, aggrdata->nbounddistvars, &aggrdataidx) ) 529 return FALSE; 530 531 *rows = aggrdata->aggrrows + aggrdata->aggrrowsstart[aggrdataidx]; 532 *nrows = aggrdata->aggrrowsstart[aggrdataidx + 1] - aggrdata->aggrrowsstart[aggrdataidx]; 533 *rowvarcoefs = aggrdata->aggrrowscoef + aggrdata->aggrrowsstart[aggrdataidx]; 534 *ngoodrows = aggrdata->ngoodaggrrows[aggrdataidx]; 535 536 return TRUE; 537 } 538 539 /** find the bound distance value in the aggregation data struct for the given variable problem index */ 540 static 541 SCIP_Real aggrdataGetBoundDist( 542 AGGREGATIONDATA* aggrdata, /**< SCIP datastructure */ 543 int probvaridx /**< problem index of variables to retrieve candidates for */ 544 ) 545 { 546 int aggrdataidx; 547 548 if( !SCIPsortedvecFindInt(aggrdata->bounddistinds, probvaridx, aggrdata->nbounddistvars, &aggrdataidx) ) 549 return 0.0; 550 551 return aggrdata->bounddist[aggrdataidx]; 552 } 553 554 /** Aggregates the next row suitable for cancelling out an active continuous variable. 555 * 556 * Equality rows that contain no other active continuous variables are preffered and apart from that 557 * the scores for the rows are used to determine which row is aggregated next 558 */ 559 static 560 SCIP_RETCODE aggregateNextRow( 561 SCIP* scip, /**< SCIP data structure */ 562 SCIP_SEPADATA* sepadata, /**< separator data */ 563 SCIP_Real* rowlhsscores, /**< aggregation scores for left hand sides of row */ 564 SCIP_Real* rowrhsscores, /**< aggregation scores for right hand sides of row */ 565 AGGREGATIONDATA* aggrdata, /**< aggregation data */ 566 SCIP_AGGRROW* aggrrow, /**< current aggregation row */ 567 int* naggrs, /**< pointer to increase counter if real aggregation took place */ 568 SCIP_Bool* success /**< pointer to return whether another row was added to the aggregation row */ 569 ) 570 { 571 int i; 572 int firstcontvar; 573 int* badvarinds; 574 SCIP_Real* badvarbddist; 575 int nbadvars; 576 SCIP_Real minbddist; 577 SCIP_ROW* bestrow; 578 SCIP_Real bestrowscore; 579 SCIP_Real aggrfac; 580 int bestrowside; 581 int ncontvars; 582 int nnz = SCIPaggrRowGetNNz(aggrrow); 583 int* inds = SCIPaggrRowGetInds(aggrrow); 584 585 assert( success != NULL ); 586 *success = FALSE; 587 588 firstcontvar = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 589 ncontvars = SCIPgetNImplVars(scip) + SCIPgetNContVars(scip); 590 assert( firstcontvar + ncontvars == SCIPgetNVars(scip) ); 591 592 SCIP_CALL( SCIPallocBufferArray(scip, &badvarinds, MIN(ncontvars, nnz)) ); 593 SCIP_CALL( SCIPallocBufferArray(scip, &badvarbddist, MIN(ncontvars, nnz)) ); 594 595 nbadvars = 0; 596 597 for( i = 0; i < nnz; ++i ) 598 { 599 SCIP_Real bounddist; 600 601 /* only consider continuous variables */ 602 if( inds[i] < firstcontvar ) 603 continue; 604 605 bounddist = aggrdataGetBoundDist(aggrdata, inds[i]); 606 607 if( bounddist == 0.0 ) 608 continue; 609 610 badvarinds[nbadvars] = inds[i]; 611 badvarbddist[nbadvars] = bounddist; 612 ++nbadvars; 613 } 614 615 if( nbadvars == 0 ) 616 goto TERMINATE; 617 618 SCIPsortDownRealInt(badvarbddist, badvarinds, nbadvars); 619 620 aggrfac = 0.0; 621 bestrowscore = 0.0; 622 bestrowside = 0; 623 minbddist = 0.0; 624 bestrow = NULL; 625 626 /* because the "good" bad variables have a negative bound distance, they are at the end */ 627 for( i = nbadvars - 1; i >= 0; --i ) 628 { 629 int probvaridx; 630 SCIP_ROW** candrows; 631 SCIP_Real* candrowcoefs; 632 int nrows; 633 int ngoodrows; 634 int k; 635 636 /* if the bound distance is not negative, there are no more good variables so stop */ 637 if( badvarbddist[i] > 0.0 ) 638 break; 639 640 /* if no best row was found yet, this variable has the currently best bound distance */ 641 if( aggrfac == 0.0 ) 642 minbddist = -badvarbddist[i] * (1.0 - sepadata->aggrtol); 643 644 /* if the bound distance of the current variable is smaller than the minimum bound distance stop looping */ 645 if( -badvarbddist[i] < minbddist ) 646 break; 647 648 probvaridx = badvarinds[i]; 649 650 if( !getRowAggregationCandidates(aggrdata, probvaridx, &candrows, &candrowcoefs, &nrows, &ngoodrows) ) 651 return SCIP_ERROR; 652 653 assert(ngoodrows > 0); /* bounddistance was negative for this variable, so it should have good rows */ 654 assert(ngoodrows <= nrows); 655 656 for( k = 0; k < ngoodrows; ++k ) 657 { 658 SCIP_Real rowaggrfac; 659 SCIP_Real rowscore; 660 int lppos; 661 662 /* do not add rows twice */ 663 if( SCIPaggrRowHasRowBeenAdded(aggrrow, candrows[k]) ) 664 continue; 665 666 rowaggrfac = - SCIPaggrRowGetProbvarValue(aggrrow, probvaridx) / candrowcoefs[k]; 667 668 /* if factor is too extreme skip this row */ 669 if( SCIPisFeasZero(scip, rowaggrfac) || REALABS(rowaggrfac) > sepadata->maxrowfac ) 670 continue; 671 672 lppos = SCIProwGetLPPos(candrows[k]); 673 674 /* row could be used and good rows are equalities, so ignore sidetype */ 675 rowscore = MAX(rowlhsscores[lppos], rowrhsscores[lppos]); 676 677 /* if this rows score is better than the currently best score, remember it */ 678 if( aggrfac == 0.0 || rowscore > bestrowscore ) 679 { 680 bestrow = candrows[k]; 681 aggrfac = rowaggrfac; 682 bestrowscore = rowscore; 683 bestrowside = 0; 684 } 685 } 686 } 687 688 /* found a row among the good rows, so aggregate it and stop */ 689 if( aggrfac != 0.0 ) 690 { 691 ++(*naggrs); 692 SCIP_CALL( SCIPaggrRowAddRow(scip, aggrrow, bestrow, aggrfac, bestrowside) ); 693 SCIPaggrRowRemoveZeros(scip, aggrrow, FALSE, success); 694 goto TERMINATE; 695 } 696 697 for( i = 0; i < nbadvars; ++i ) 698 { 699 int probvaridx; 700 SCIP_ROW** candrows; 701 SCIP_Real* candrowcoefs; 702 int nrows; 703 int ngoodrows; 704 int k; 705 706 /* if the bound distance is negative, there are no more variables to be tested, so stop */ 707 if( badvarbddist[i] < 0.0 ) 708 break; 709 710 /* if no best row was found yet, this variable has the currently best bound distance */ 711 if( aggrfac == 0.0 ) 712 minbddist = badvarbddist[i] * (1.0 - sepadata->aggrtol); 713 714 /* if the bound distance of the current variable is smaller than the minimum bound distance stop looping */ 715 if( badvarbddist[i] < minbddist ) 716 break; 717 718 probvaridx = badvarinds[i]; 719 720 if( !getRowAggregationCandidates(aggrdata, probvaridx, &candrows, &candrowcoefs, &nrows, &ngoodrows) ) 721 return SCIP_ERROR; 722 723 /* bounddistance was positive for this variable, so it should not have good rows */ 724 assert(ngoodrows == 0); 725 726 for( k = 0; k < nrows; ++k ) 727 { 728 SCIP_Real rowaggrfac; 729 SCIP_Real rowscore; 730 int rowside; 731 int lppos; 732 733 /* do not add rows twice */ 734 if( SCIPaggrRowHasRowBeenAdded(aggrrow, candrows[k]) ) 735 continue; 736 737 rowaggrfac = - SCIPaggrRowGetProbvarValue(aggrrow, probvaridx) / candrowcoefs[k]; 738 739 /* if factor is too extreme skip this row */ 740 if( SCIPisFeasZero(scip, rowaggrfac) || REALABS(rowaggrfac) > sepadata->maxrowfac ) 741 continue; 742 743 /* row could be used, decide which side */ 744 lppos = SCIProwGetLPPos(candrows[k]); 745 746 /* either both or none of the rowscores are 0.0 so use the one which gives a positive slack */ 747 if( (rowaggrfac < 0.0 && !SCIPisInfinity(scip, -SCIProwGetLhs(candrows[k]))) || SCIPisInfinity(scip, SCIProwGetRhs(candrows[k])) ) 748 { 749 rowscore = rowlhsscores[lppos]; 750 rowside = -1; 751 } 752 else 753 { 754 rowscore = rowrhsscores[lppos]; 755 rowside = 1; 756 } 757 758 /* if this rows score is better than the currently best score, remember it */ 759 if( aggrfac == 0.0 || SCIPisGT(scip, rowscore, bestrowscore) || 760 (SCIPisEQ(scip, rowscore, bestrowscore) && aggrdata->nbadvarsinrow[lppos] < aggrdata->nbadvarsinrow[SCIProwGetLPPos(bestrow)]) ) 761 { 762 bestrow = candrows[k]; 763 aggrfac = rowaggrfac; 764 bestrowscore = rowscore; 765 bestrowside = rowside; 766 } 767 } 768 } 769 770 /* found a row so aggregate it */ 771 if( aggrfac != 0.0 ) 772 { 773 ++(*naggrs); 774 SCIP_CALL( SCIPaggrRowAddRow(scip, aggrrow, bestrow, aggrfac, bestrowside) ); 775 SCIPaggrRowRemoveZeros(scip, aggrrow, FALSE, success); 776 } 777 778 TERMINATE: 779 SCIPfreeBufferArray(scip, &badvarbddist); 780 SCIPfreeBufferArray(scip, &badvarinds); 781 782 return SCIP_OKAY; 783 } 784 785 /** aggregates different single mixed integer constraints by taking linear combinations of the rows of the LP */ 786 static 787 SCIP_RETCODE aggregation( 788 SCIP* scip, /**< SCIP data structure */ 789 AGGREGATIONDATA* aggrdata, /**< pointer to aggregation data */ 790 SCIP_SEPA* sepa, /**< separator */ 791 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */ 792 SCIP_Bool allowlocal, /**< should local cuts be allowed */ 793 SCIP_Real* rowlhsscores, /**< aggregation scores for left hand sides of row */ 794 SCIP_Real* rowrhsscores, /**< aggregation scores for right hand sides of row */ 795 int startrow, /**< index of row to start aggregation; -1 for using the objective cutoff constraint */ 796 int maxaggrs, /**< maximal number of aggregations */ 797 SCIP_Bool* wastried, /**< pointer to store whether the given startrow was actually tried */ 798 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 799 int* cutinds, /**< buffer array to store temporarily cut */ 800 SCIP_Real* cutcoefs, /**< buffer array to store temporarily cut */ 801 SCIP_Bool negate, /**< should the start row be multiplied by -1 */ 802 int* ncuts /**< pointer to count the number of generated cuts */ 803 ) 804 { 805 SCIP_SEPADATA* sepadata; 806 SCIP_ROW** rows; 807 808 SCIP_Real startweight; 809 SCIP_Real startrowact; 810 int maxaggrnonzs; 811 int naggrs; 812 int nrows; 813 int maxtestdelta; 814 815 assert(scip != NULL); 816 assert(aggrdata != NULL); 817 assert(aggrdata->aggrrow != NULL); 818 assert(sepa != NULL); 819 assert(rowlhsscores != NULL); 820 assert(rowrhsscores != NULL); 821 assert(wastried != NULL); 822 assert(cutoff != NULL); 823 assert(ncuts != NULL); 824 825 sepadata = SCIPsepaGetData(sepa); 826 assert(sepadata != NULL); 827 828 *cutoff = FALSE; 829 *wastried = FALSE; 830 831 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 832 assert(nrows == 0 || rows != NULL); 833 834 maxtestdelta = sepadata->maxtestdelta == -1 ? INT_MAX : sepadata->maxtestdelta; 835 836 /* calculate maximal number of non-zeros in aggregated row */ 837 maxaggrnonzs = (int)(sepadata->maxaggdensity * SCIPgetNLPCols(scip)) + sepadata->densityoffset; 838 839 /* add start row to the initially empty aggregation row (aggrrow) */ 840 if( startrow < 0 ) 841 { 842 SCIP_Real rhs; 843 844 /* if the objective is integral we round the right hand side of the cutoff constraint. 845 * Therefore the constraint may not be valid for the problem but it is valid for the set 846 * of all improving solutions. We refrain from adding an epsilon cutoff for the case 847 * of a non-integral objective function to avoid cutting of any improving solution even 848 * if the improvement is below some epsilon value. 849 */ 850 if( SCIPisObjIntegral(scip) ) 851 rhs = floor(SCIPgetUpperbound(scip) - 0.5); 852 else 853 rhs = SCIPgetUpperbound(scip); 854 855 SCIP_CALL( SCIPaggrRowAddObjectiveFunction(scip, aggrdata->aggrrow, rhs, 1.0) ); 856 857 if( SCIPaggrRowGetNNz(aggrdata->aggrrow) == 0 ) 858 { 859 SCIPaggrRowClear(aggrdata->aggrrow); 860 return SCIP_OKAY; 861 } 862 } 863 else 864 { 865 assert(0 <= startrow && startrow < nrows); 866 867 SCIPdebugMsg(scip, "start c-MIR aggregation with row <%s> (%d/%d)\n", SCIProwGetName(rows[startrow]), startrow, nrows); 868 869 startrowact = SCIPgetRowSolActivity(scip, rows[startrow], sol); 870 871 if( startrowact <= 0.5 * SCIProwGetLhs(rows[startrow]) + 0.5 * SCIProwGetRhs(rows[startrow]) ) 872 startweight = -1.0; 873 else 874 startweight = 1.0; 875 876 SCIP_CALL( SCIPaggrRowAddRow(scip, aggrdata->aggrrow, rows[startrow], negate ? -startweight : startweight, 0) ); /*lint !e644*/ 877 } 878 879 /* try to generate cut from the current aggregated row; add cut if found, otherwise add another row to aggrrow 880 * in order to get rid of a continuous variable 881 */ 882 naggrs = 0; 883 while( naggrs <= maxaggrs ) 884 { 885 int cutrank = 0; 886 int cutnnz = 0; 887 SCIP_Bool aggrsuccess; 888 SCIP_Bool cmirsuccess; 889 SCIP_Bool cmircutislocal = FALSE; 890 SCIP_Bool flowcoversuccess; 891 SCIP_Real flowcoverefficacy; 892 SCIP_Bool flowcovercutislocal = FALSE; 893 SCIP_Bool knapsackcoversuccess; 894 SCIP_Real knapsackcoverefficacy; 895 SCIP_Bool knapsackcovercutislocal = FALSE; 896 SCIP_ROW* cut = NULL; 897 SCIP_Real cutrhs = SCIP_INVALID; 898 SCIP_Real cutefficacy; 899 900 *wastried = TRUE; 901 902 /* Step 1: 903 * try to generate a MIR cut out of the current aggregated row 904 */ 905 906 flowcoverefficacy = -SCIPinfinity(scip); 907 908 if( sepadata->sepflowcover ) 909 { 910 SCIP_CALL( SCIPcalcFlowCover(scip, sol, POSTPROCESS, BOUNDSWITCH, allowlocal, aggrdata->aggrrow, /*lint !e644*/ 911 cutcoefs, &cutrhs, cutinds, &cutnnz, &flowcoverefficacy, &cutrank, &flowcovercutislocal, &flowcoversuccess) ); 912 } 913 else 914 { 915 flowcoversuccess = FALSE; 916 } 917 918 /* initialize the knapsack cover cut efficacy variable with the flowcover efficacy so that 919 * only knapsack cover cuts better than that efficacy are returned. 920 */ 921 knapsackcoverefficacy = flowcoverefficacy; 922 923 if( sepadata->sepknapsackcover ) 924 { 925 SCIP_CALL( SCIPcalcKnapsackCover(scip, sol, allowlocal, aggrdata->aggrrow, /*lint !e644*/ 926 cutcoefs, &cutrhs, cutinds, &cutnnz, &knapsackcoverefficacy, &cutrank, &knapsackcovercutislocal, &knapsackcoversuccess) ); 927 } 928 else 929 { 930 knapsackcoversuccess = FALSE; 931 } 932 933 /* initialize the cutefficacy variable with the knapsackcoverefficacy, so that only CMIR cuts 934 * that have a higher efficacy than that of a flowcover or knapsack cover cut possibly 935 * found in the call above are returned since the previous cut is overwritten in that case. 936 */ 937 cutefficacy = knapsackcoverefficacy; 938 939 if( sepadata->sepcmir ) 940 { 941 SCIP_CALL( SCIPcutGenerationHeuristicCMIR(scip, sol, POSTPROCESS, BOUNDSWITCH, USEVBDS, allowlocal, maxtestdelta, NULL, NULL, MINFRAC, MAXFRAC, 942 aggrdata->aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cmircutislocal, &cmirsuccess) ); 943 } 944 else 945 { 946 cmirsuccess = FALSE; 947 } 948 949 if( cmirsuccess ) 950 { 951 /* cppcheck-suppress uninitvar */ 952 SCIP_CALL( addCut(scip, sol, sepadata->cmir, FALSE, cutcoefs, cutinds, cutnnz, cutrhs, cutefficacy, 953 cmircutislocal, sepadata->dynamiccuts, cutrank, startrow < 0 ? "objcmir" : "cmir", cutoff, ncuts, &cut) ); /*lint !e644*/ 954 } 955 else if ( knapsackcoversuccess ) 956 { 957 /* cppcheck-suppress uninitvar */ 958 SCIP_CALL( addCut(scip, sol, sepadata->knapsackcover, FALSE, cutcoefs, cutinds, cutnnz, cutrhs, cutefficacy, 959 knapsackcovercutislocal, sepadata->dynamiccuts, cutrank, startrow < 0 ? "objlci" : "lci", cutoff, ncuts, &cut) ); /*lint !e644*/ 960 } 961 else if ( flowcoversuccess ) 962 { 963 /* cppcheck-suppress uninitvar */ 964 SCIP_CALL( addCut(scip, sol, sepadata->flowcover, FALSE, cutcoefs, cutinds, cutnnz, cutrhs, cutefficacy, 965 flowcovercutislocal, sepadata->dynamiccuts, cutrank, startrow < 0 ? "objflowcover" : "flowcover", cutoff, ncuts, &cut) ); /*lint !e644*/ 966 } 967 968 if ( *cutoff ) 969 { 970 if( cut != NULL ) 971 { 972 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 973 } 974 break; 975 } 976 977 /* if the cut was successfully added, decrease the score of the rows used in the aggregation and clean the aggregation 978 * row (and call this function again with a different start row for aggregation) 979 */ 980 if( cut != NULL ) 981 { 982 int* rowinds; 983 int i; 984 985 rowinds = SCIPaggrRowGetRowInds(aggrdata->aggrrow); 986 nrows = SCIPaggrRowGetNRows(aggrdata->aggrrow); 987 988 /* decrease row score of used rows slightly */ 989 for( i = 0; i < nrows; ++i ) 990 { 991 SCIP_Real fac = 1.0 - 0.999 * SCIProwGetParallelism(rows[rowinds[i]], cut, 'e'); 992 993 rowlhsscores[rowinds[i]] *= fac; 994 rowrhsscores[rowinds[i]] *= fac; 995 } 996 997 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 998 999 SCIPdebugMsg(scip, " -> abort aggregation: cut found\n"); 1000 break; 1001 } 1002 1003 /* Step 2: 1004 * aggregate an additional row in order to remove a continuous variable 1005 */ 1006 1007 /* abort, if we reached the maximal number of aggregations */ 1008 if( naggrs == maxaggrs ) 1009 { 1010 SCIPdebugMsg(scip, " -> abort aggregation: maximal number of aggregations reached\n"); 1011 break; 1012 } 1013 1014 SCIP_CALL( aggregateNextRow(scip, sepadata, rowlhsscores, rowrhsscores, aggrdata, aggrdata->aggrrow, 1015 &naggrs, &aggrsuccess) ); 1016 1017 /* no suitable aggregation was found or number of non-zeros is now too large so abort */ 1018 if( ! aggrsuccess || SCIPaggrRowGetNNz(aggrdata->aggrrow) > maxaggrnonzs || SCIPaggrRowGetNNz(aggrdata->aggrrow) == 0 ) 1019 { 1020 break; 1021 } 1022 1023 SCIPdebugMsg(scip, " -> current aggregation has %d/%d nonzeros and consists of %d/%d rows\n", 1024 SCIPaggrRowGetNNz(aggrdata->aggrrow), maxaggrnonzs, naggrs, maxaggrs); 1025 } 1026 1027 SCIPaggrRowClear(aggrdata->aggrrow); 1028 1029 return SCIP_OKAY; 1030 } 1031 1032 /** gives an estimate of how much the activity of this row is affected by fractionality in the current solution */ 1033 static 1034 SCIP_Real getRowFracActivity( 1035 SCIP_ROW* row, /**< the LP row */ 1036 SCIP_Real* fractionalities /**< array of fractionalities for each variable */ 1037 ) 1038 { 1039 int nlpnonz; 1040 int i; 1041 SCIP_COL** cols; 1042 SCIP_Real* vals; 1043 SCIP_Real fracsum = 0.0; 1044 1045 cols = SCIProwGetCols(row); 1046 vals = SCIProwGetVals(row); 1047 nlpnonz = SCIProwGetNLPNonz(row); 1048 1049 for( i = 0; i < nlpnonz; ++i ) 1050 { 1051 SCIP_VAR* var = SCIPcolGetVar(cols[i]); 1052 fracsum += REALABS(vals[i] * fractionalities[SCIPvarGetProbindex(var)]); 1053 } 1054 1055 return fracsum; 1056 } 1057 1058 /** searches for and adds c-MIR cuts that separate the given primal solution */ 1059 static 1060 SCIP_RETCODE separateCuts( 1061 SCIP* scip, /**< SCIP data structure */ 1062 SCIP_SEPA* sepa, /**< the c-MIR separator */ 1063 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */ 1064 SCIP_Bool allowlocal, /**< should local cuts be allowed */ 1065 int depth, /**< current depth */ 1066 SCIP_RESULT* result /**< pointer to store the result */ 1067 ) 1068 { 1069 AGGREGATIONDATA aggrdata; 1070 SCIP_SEPADATA* sepadata; 1071 SCIP_VAR** vars; 1072 SCIP_Real* varsolvals; 1073 SCIP_Real* bestcontlbs; 1074 SCIP_Real* bestcontubs; 1075 SCIP_Real* fractionalities; 1076 SCIP_ROW** rows; 1077 SCIP_Real* rowlhsscores; 1078 SCIP_Real* rowrhsscores; 1079 SCIP_Real* rowscores; 1080 int* roworder; 1081 SCIP_Real maxslack; 1082 SCIP_Bool cutoff = FALSE; 1083 SCIP_Bool wastried; 1084 int nvars; 1085 int nintvars; 1086 int ncontvars; 1087 int nrows; 1088 int nnonzrows; 1089 int ntries; 1090 int nfails; 1091 int ncalls; 1092 int maxtries; 1093 int maxfails; 1094 int maxaggrs; 1095 int maxsepacuts; 1096 int ncuts; 1097 int r; 1098 int v; 1099 int oldncuts; 1100 1101 int* cutinds; 1102 SCIP_Real* cutcoefs; 1103 1104 assert(result != NULL); 1105 assert(*result == SCIP_DIDNOTRUN); 1106 1107 sepadata = SCIPsepaGetData(sepa); 1108 assert(sepadata != NULL); 1109 1110 ncalls = SCIPsepaGetNCallsAtNode(sepa); 1111 1112 /* only call the cmir cut separator a given number of times at each node */ 1113 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) 1114 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) ) 1115 return SCIP_OKAY; 1116 1117 /* check which cuts should be separated */ 1118 { 1119 int cmirfreq; 1120 int flowcoverfreq; 1121 int knapsackcoverfreq; 1122 1123 cmirfreq = SCIPsepaGetFreq(sepadata->cmir); 1124 flowcoverfreq = SCIPsepaGetFreq(sepadata->flowcover); 1125 knapsackcoverfreq = SCIPsepaGetFreq(sepadata->knapsackcover); 1126 1127 sepadata->sepcmir = cmirfreq > 0 ? (depth % cmirfreq) == 0 : cmirfreq == depth; 1128 sepadata->sepflowcover = flowcoverfreq > 0 ? (depth % flowcoverfreq) == 0 : flowcoverfreq == depth; 1129 sepadata->sepknapsackcover = knapsackcoverfreq > 0 ? (depth % knapsackcoverfreq) == 0 : knapsackcoverfreq == depth; 1130 } 1131 1132 if( ! sepadata->sepcmir && ! sepadata->sepflowcover && ! sepadata->sepknapsackcover ) 1133 return SCIP_OKAY; 1134 1135 /* get all rows and number of columns */ 1136 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 1137 assert(nrows == 0 || rows != NULL); 1138 1139 /* nothing to do, if LP is empty */ 1140 if( nrows == 0 ) 1141 return SCIP_OKAY; 1142 1143 /* check whether SCIP was stopped in the meantime */ 1144 if( SCIPisStopped(scip) ) 1145 return SCIP_OKAY; 1146 1147 /* get active problem variables */ 1148 vars = SCIPgetVars(scip); 1149 nvars = SCIPgetNVars(scip); 1150 ncontvars = SCIPgetNContVars(scip); 1151 #ifdef IMPLINTSARECONT 1152 ncontvars += SCIPgetNImplVars(scip); /* also aggregate out implicit integers */ 1153 #endif 1154 nintvars = nvars - ncontvars; 1155 assert(nvars == 0 || vars != NULL); 1156 1157 /* nothing to do, if problem has no variables */ 1158 if( nvars == 0 ) 1159 return SCIP_OKAY; 1160 1161 SCIPdebugMsg(scip, "separating c-MIR cuts\n"); 1162 1163 *result = SCIP_DIDNOTFIND; 1164 1165 /* get data structure */ 1166 SCIP_CALL( SCIPallocBufferArray(scip, &rowlhsscores, nrows) ); 1167 SCIP_CALL( SCIPallocBufferArray(scip, &rowrhsscores, nrows) ); 1168 SCIP_CALL( SCIPallocBufferArray(scip, &roworder, nrows) ); 1169 SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) ); 1170 SCIP_CALL( SCIPallocBufferArray(scip, &bestcontlbs, ncontvars) ); 1171 SCIP_CALL( SCIPallocBufferArray(scip, &bestcontubs, ncontvars) ); 1172 SCIP_CALL( SCIPallocBufferArray(scip, &fractionalities, nvars) ); 1173 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) ); 1174 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) ); 1175 SCIP_CALL( SCIPallocBufferArray(scip, &rowscores, nrows) ); 1176 1177 /* get the solution values for all active variables */ 1178 SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, varsolvals) ); 1179 1180 /* calculate the fractionality of the integer variables in the current solution */ 1181 for( v = 0; v < nintvars; ++v ) 1182 { 1183 fractionalities[v] = SCIPfeasFrac(scip, varsolvals[v]); 1184 fractionalities[v] = MIN(fractionalities[v], 1.0 - fractionalities[v]); 1185 } 1186 1187 /* calculate the fractionality of the continuous variables in the current solution; 1188 * The fractionality of a continuous variable x is defined to be a * f_y, 1189 * if there is a variable bound x <= a * y + c where f_y is the fractionality of y 1190 * and in the current solution the variable bound has no slack. 1191 */ 1192 for( ; v < nvars; ++v ) 1193 { 1194 SCIP_VAR** vlbvars; 1195 SCIP_VAR** vubvars; 1196 SCIP_Real* vlbcoefs; 1197 SCIP_Real* vubcoefs; 1198 SCIP_Real closestvlb; 1199 SCIP_Real closestvub; 1200 int closestvlbidx; 1201 int closestvubidx; 1202 1203 SCIP_CALL( SCIPgetVarClosestVlb(scip, vars[v], sol, &closestvlb, &closestvlbidx) ); 1204 SCIP_CALL( SCIPgetVarClosestVub(scip, vars[v], sol, &closestvub, &closestvubidx) ); 1205 1206 vlbvars = SCIPvarGetVlbVars(vars[v]); 1207 vubvars = SCIPvarGetVubVars(vars[v]); 1208 vlbcoefs = SCIPvarGetVlbCoefs(vars[v]); 1209 vubcoefs = SCIPvarGetVubCoefs(vars[v]); 1210 1211 fractionalities[v] = 0.0; 1212 if( closestvlbidx != -1 && SCIPisEQ(scip, varsolvals[v], closestvlb) ) 1213 { 1214 int vlbvarprobidx = SCIPvarGetProbindex(vlbvars[closestvlbidx]); 1215 SCIP_Real frac = SCIPfeasFrac(scip, varsolvals[vlbvarprobidx]); 1216 1217 if( frac < 0.0 ) 1218 frac = 0.0; 1219 assert(frac >= 0.0 && frac < 1.0); 1220 frac = MIN(frac, 1.0 - frac) * vlbcoefs[closestvlbidx]; 1221 fractionalities[v] += frac; 1222 } 1223 1224 if( closestvubidx != -1 && SCIPisEQ(scip, varsolvals[v], closestvub) ) 1225 { 1226 int vubvarprobidx = SCIPvarGetProbindex(vubvars[closestvubidx]); 1227 SCIP_Real frac = SCIPfeasFrac(scip, varsolvals[vubvarprobidx]); 1228 1229 if( frac < 0.0 ) 1230 frac = 0.0; 1231 assert(frac >= 0.0 && frac < 1.0); 1232 frac = MIN(frac, 1.0 - frac) * vubcoefs[closestvubidx]; 1233 fractionalities[v] += frac; 1234 } 1235 } 1236 1237 /* get the maximal number of cuts allowed in a separation round */ 1238 if( depth == 0 ) 1239 { 1240 maxtries = sepadata->maxtriesroot; 1241 maxfails = sepadata->maxfailsroot; 1242 maxaggrs = sepadata->maxaggrsroot; 1243 maxsepacuts = sepadata->maxsepacutsroot; 1244 maxslack = sepadata->maxslackroot; 1245 } 1246 else 1247 { 1248 maxtries = sepadata->maxtries; 1249 maxfails = sepadata->maxfails; 1250 maxaggrs = sepadata->maxaggrs; 1251 maxsepacuts = sepadata->maxsepacuts; 1252 maxslack = sepadata->maxslack; 1253 } 1254 1255 /* calculate aggregation scores for both sides of all rows, and sort rows by decreasing maximal score 1256 * TODO: document score definition */ 1257 1258 /* count the number of non-zero rows and zero rows. these values are used for the sorting of the rowscores. 1259 * only the non-zero rows need to be sorted. */ 1260 nnonzrows = 0; 1261 for( r = 0; r < nrows; r++ ) 1262 { 1263 int nnonz; 1264 1265 assert(SCIProwGetLPPos(rows[r]) == r); 1266 1267 nnonz = SCIProwGetNLPNonz(rows[r]); 1268 if( nnonz == 0 || SCIProwIsModifiable(rows[r]) || (!allowlocal && SCIProwIsLocal(rows[r])) ) 1269 { 1270 /* ignore empty rows, modifiable rows, and local rows if they are not allowed */ 1271 rowlhsscores[r] = 0.0; 1272 rowrhsscores[r] = 0.0; 1273 } 1274 else 1275 { 1276 SCIP_Real activity; 1277 SCIP_Real lhs; 1278 SCIP_Real rhs; 1279 SCIP_Real dualsol; 1280 SCIP_Real dualscore; 1281 SCIP_Real rowdensity; 1282 SCIP_Real rownorm; 1283 SCIP_Real slack; 1284 SCIP_Real fracact; 1285 SCIP_Real fracscore; 1286 SCIP_Real objnorm; 1287 1288 objnorm = SCIPgetObjNorm(scip); 1289 objnorm = MAX(objnorm, 1.0); 1290 1291 fracact = getRowFracActivity(rows[r], fractionalities); 1292 dualsol = (sol == NULL ? SCIProwGetDualsol(rows[r]) : 1.0); 1293 activity = SCIPgetRowSolActivity(scip, rows[r], sol); 1294 lhs = SCIProwGetLhs(rows[r]); 1295 rhs = SCIProwGetRhs(rows[r]); 1296 rownorm = SCIProwGetNorm(rows[r]); 1297 rownorm = MAX(rownorm, 0.1); 1298 rowdensity = (SCIP_Real)(nnonz - sepadata->densityoffset)/(SCIP_Real)nvars; 1299 assert(SCIPisPositive(scip, rownorm)); 1300 fracscore = fracact / rownorm; 1301 1302 slack = (activity - lhs)/rownorm; 1303 dualscore = MAX(fracscore * dualsol/objnorm, 0.0001); 1304 if( !SCIPisInfinity(scip, -lhs) && SCIPisLE(scip, slack, maxslack) 1305 && rowdensity <= sepadata->maxrowdensity 1306 && rowdensity <= sepadata->maxaggdensity ) /*lint !e774*/ 1307 { 1308 rowlhsscores[r] = dualscore + sepadata->densityscore * (1.0-rowdensity) + sepadata->slackscore * MAX(1.0 - slack, 0.0); 1309 assert(rowlhsscores[r] > 0.0); 1310 } 1311 else 1312 rowlhsscores[r] = 0.0; 1313 1314 slack = (rhs - activity)/rownorm; 1315 dualscore = MAX(-fracscore * dualsol/objnorm, 0.0001); 1316 if( !SCIPisInfinity(scip, rhs) && SCIPisLE(scip, slack, maxslack) 1317 && rowdensity <= sepadata->maxrowdensity 1318 && rowdensity <= sepadata->maxaggdensity ) /*lint !e774*/ 1319 { 1320 rowrhsscores[r] = dualscore + sepadata->densityscore * (1.0-rowdensity) + sepadata->slackscore * MAX(1.0 - slack, 0.0); 1321 assert(rowrhsscores[r] > 0.0); 1322 } 1323 else 1324 rowrhsscores[r] = 0.0; 1325 1326 /* for the row order only use the fractionality score since it best indicates how likely it is to find a cut */ 1327 if( fracscore != 0.0 ) 1328 { 1329 roworder[nnonzrows] = r; 1330 rowscores[nnonzrows] = fracscore; 1331 ++nnonzrows; 1332 } 1333 } 1334 1335 SCIPdebugMsg(scip, " -> row %d <%s>: lhsscore=%g rhsscore=%g maxscore=%g\n", r, SCIProwGetName(rows[r]), 1336 rowlhsscores[r], rowrhsscores[r], rowscores[r]); 1337 } 1338 assert(nnonzrows <= nrows); 1339 1340 SCIPsortDownRealInt(rowscores, roworder, nnonzrows); 1341 SCIPfreeBufferArray(scip, &rowscores); 1342 1343 /* calculate the data required for performing the row aggregation */ 1344 SCIP_CALL( setupAggregationData(scip, sol, allowlocal, &aggrdata) ); 1345 1346 ncuts = 0; 1347 if( maxtries < 0 ) 1348 maxtries = INT_MAX; 1349 if( maxfails < 0 ) 1350 maxfails = INT_MAX; 1351 else if( depth == 0 && 2 * SCIPgetNSepaRounds(scip) < maxfails ) 1352 maxfails += maxfails - 2 * SCIPgetNSepaRounds(scip); /* allow up to double as many fails in early separounds of root node */ 1353 1354 /* start aggregation heuristic for each row in the LP and generate resulting cuts */ 1355 ntries = 0; 1356 nfails = 0; 1357 1358 if( !SCIPisInfinity(scip, SCIPgetCutoffbound(scip)) ) 1359 { 1360 /* try separating the objective function with the cutoff bound */ 1361 SCIP_CALL( aggregation(scip, &aggrdata, sepa, sol, allowlocal, rowlhsscores, rowrhsscores, 1362 -1, 2 * maxaggrs, &wastried, &cutoff, cutinds, cutcoefs, FALSE, &ncuts) ); 1363 1364 if( cutoff ) 1365 goto TERMINATE; 1366 } 1367 1368 for( r = 0; r < nnonzrows && ntries < maxtries && ncuts < maxsepacuts && !SCIPisStopped(scip); r++ ) 1369 { 1370 oldncuts = ncuts; 1371 SCIP_CALL( aggregation(scip, &aggrdata, sepa, sol, allowlocal, rowlhsscores, rowrhsscores, 1372 roworder[r], maxaggrs, &wastried, &cutoff, cutinds, cutcoefs, FALSE, &ncuts) ); 1373 1374 /* if trynegscaling is true we start the aggregation heuristic again for this row, but multiply it by -1 first. 1375 * This is done by calling the aggregation function with the parameter negate equal to TRUE 1376 */ 1377 if( sepadata->trynegscaling && !cutoff ) 1378 { 1379 SCIP_CALL( aggregation(scip, &aggrdata, sepa, sol, allowlocal, rowlhsscores, rowrhsscores, 1380 roworder[r], maxaggrs, &wastried, &cutoff, cutinds, cutcoefs, TRUE, &ncuts) ); 1381 } 1382 1383 if ( cutoff ) 1384 break; 1385 1386 if( !wastried ) 1387 { 1388 continue; 1389 } 1390 ntries++; 1391 1392 if( ncuts == oldncuts ) 1393 { 1394 nfails++; 1395 if( nfails >= maxfails ) 1396 { 1397 break; 1398 } 1399 } 1400 else 1401 { 1402 nfails = 0; 1403 } 1404 } 1405 TERMINATE: 1406 /* free data structure */ 1407 destroyAggregationData(scip, &aggrdata); 1408 SCIPfreeBufferArray(scip, &cutcoefs); 1409 SCIPfreeBufferArray(scip, &cutinds); 1410 SCIPfreeBufferArray(scip, &fractionalities); 1411 SCIPfreeBufferArray(scip, &bestcontubs); 1412 SCIPfreeBufferArray(scip, &bestcontlbs); 1413 SCIPfreeBufferArray(scip, &varsolvals); 1414 SCIPfreeBufferArray(scip, &roworder); 1415 SCIPfreeBufferArray(scip, &rowrhsscores); 1416 SCIPfreeBufferArray(scip, &rowlhsscores); 1417 1418 if ( cutoff ) 1419 *result = SCIP_CUTOFF; 1420 else if ( ncuts > 0 ) 1421 *result = SCIP_SEPARATED; 1422 1423 return SCIP_OKAY; 1424 } 1425 1426 /* 1427 * Callback methods of separator 1428 */ 1429 1430 /** copy method for separator plugins (called when SCIP copies plugins) */ 1431 static 1432 SCIP_DECL_SEPACOPY(sepaCopyAggregation) 1433 { /*lint --e{715}*/ 1434 assert(scip != NULL); 1435 assert(sepa != NULL); 1436 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 1437 1438 /* call inclusion method of constraint handler */ 1439 SCIP_CALL( SCIPincludeSepaAggregation(scip) ); 1440 1441 return SCIP_OKAY; 1442 } 1443 1444 /** destructor of separator to free user data (called when SCIP is exiting) */ 1445 static 1446 SCIP_DECL_SEPAFREE(sepaFreeAggregation) 1447 { /*lint --e{715}*/ 1448 SCIP_SEPADATA* sepadata; 1449 1450 /* free separator data */ 1451 sepadata = SCIPsepaGetData(sepa); 1452 assert(sepadata != NULL); 1453 1454 SCIPfreeBlockMemory(scip, &sepadata); 1455 1456 SCIPsepaSetData(sepa, NULL); 1457 1458 return SCIP_OKAY; 1459 } 1460 1461 /** LP solution separation method of separator */ 1462 static 1463 SCIP_DECL_SEPAEXECLP(sepaExeclpAggregation) 1464 { /*lint --e{715}*/ 1465 assert( result != NULL ); 1466 1467 *result = SCIP_DIDNOTRUN; 1468 1469 /* only call separator, if we are not close to terminating */ 1470 if( SCIPisStopped(scip) ) 1471 return SCIP_OKAY; 1472 1473 /* only call separator, if an optimal LP solution is at hand */ 1474 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 1475 return SCIP_OKAY; 1476 1477 /* only call separator, if there are fractional variables */ 1478 if( SCIPgetNLPBranchCands(scip) == 0 ) 1479 return SCIP_OKAY; 1480 1481 SCIP_CALL( separateCuts(scip, sepa, NULL, allowlocal, depth, result) ); 1482 1483 return SCIP_OKAY; 1484 } 1485 1486 /** arbitrary primal solution separation method of separator */ 1487 static 1488 SCIP_DECL_SEPAEXECSOL(sepaExecsolAggregation) 1489 { /*lint --e{715}*/ 1490 assert( result != NULL ); 1491 1492 *result = SCIP_DIDNOTRUN; 1493 1494 SCIP_CALL( separateCuts(scip, sepa, sol, allowlocal, depth, result) ); 1495 1496 return SCIP_OKAY; 1497 } 1498 1499 /** LP solution separation method of dummy separator */ 1500 static 1501 SCIP_DECL_SEPAEXECLP(sepaExeclpDummy) 1502 { /*lint --e{715}*/ 1503 assert( result != NULL ); 1504 1505 *result = SCIP_DIDNOTRUN; 1506 1507 return SCIP_OKAY; 1508 } 1509 1510 /** arbitrary primal solution separation method of dummy separator */ 1511 static 1512 SCIP_DECL_SEPAEXECSOL(sepaExecsolDummy) 1513 { /*lint --e{715}*/ 1514 assert( result != NULL ); 1515 1516 *result = SCIP_DIDNOTRUN; 1517 1518 return SCIP_OKAY; 1519 } 1520 1521 /* 1522 * separator specific interface methods 1523 */ 1524 1525 /** creates the cmir separator and includes it in SCIP */ 1526 SCIP_RETCODE SCIPincludeSepaAggregation( 1527 SCIP* scip /**< SCIP data structure */ 1528 ) 1529 { 1530 SCIP_SEPADATA* sepadata; 1531 SCIP_SEPA* sepa; 1532 1533 /* create cmir separator data */ 1534 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 1535 1536 /* include dummy separators */ 1537 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->flowcover, "flowcover", "separator for flowcover cuts", -100000, SEPA_FREQ, 0.0, 1538 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) ); 1539 1540 assert(sepadata->flowcover != NULL); 1541 1542 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->cmir, "cmir", "separator for cmir cuts", -100000, SEPA_FREQ, 0.0, 1543 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) ); 1544 1545 assert(sepadata->cmir != NULL); 1546 1547 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->knapsackcover, "knapsackcover", "separator for knapsack cover cuts", -100000, SEPA_FREQ, 0.0, 1548 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) ); 1549 1550 assert(sepadata->knapsackcover != NULL); 1551 1552 /* include separator */ 1553 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 1554 SEPA_USESSUBSCIP, SEPA_DELAY, 1555 sepaExeclpAggregation, sepaExecsolAggregation, 1556 sepadata) ); 1557 1558 assert(sepa != NULL); 1559 1560 /* set non-NULL pointers to callback methods */ 1561 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyAggregation) ); 1562 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeAggregation) ); 1563 1564 /* mark main separator as a parent */ 1565 SCIPsetSepaIsParentsepa(scip, sepa); 1566 1567 /* set pointer from child separators to main separator */ 1568 SCIPsetSepaParentsepa(scip, sepadata->flowcover, sepa); 1569 SCIPsetSepaParentsepa(scip, sepadata->cmir, sepa); 1570 SCIPsetSepaParentsepa(scip, sepadata->knapsackcover, sepa); 1571 1572 /* add cmir separator parameters */ 1573 SCIP_CALL( SCIPaddIntParam(scip, 1574 "separating/" SEPA_NAME "/maxrounds", 1575 "maximal number of cmir separation rounds per node (-1: unlimited)", 1576 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) ); 1577 SCIP_CALL( SCIPaddIntParam(scip, 1578 "separating/" SEPA_NAME "/maxroundsroot", 1579 "maximal number of cmir separation rounds in the root node (-1: unlimited)", 1580 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) ); 1581 SCIP_CALL( SCIPaddIntParam(scip, 1582 "separating/" SEPA_NAME "/maxtries", 1583 "maximal number of rows to start aggregation with per separation round (-1: unlimited)", 1584 &sepadata->maxtries, TRUE, DEFAULT_MAXTRIES, -1, INT_MAX, NULL, NULL) ); 1585 SCIP_CALL( SCIPaddIntParam(scip, 1586 "separating/" SEPA_NAME "/maxtriesroot", 1587 "maximal number of rows to start aggregation with per separation round in the root node (-1: unlimited)", 1588 &sepadata->maxtriesroot, TRUE, DEFAULT_MAXTRIESROOT, -1, INT_MAX, NULL, NULL) ); 1589 SCIP_CALL( SCIPaddIntParam(scip, 1590 "separating/" SEPA_NAME "/maxfails", 1591 "maximal number of consecutive unsuccessful aggregation tries (-1: unlimited)", 1592 &sepadata->maxfails, TRUE, DEFAULT_MAXFAILS, -1, INT_MAX, NULL, NULL) ); 1593 SCIP_CALL( SCIPaddIntParam(scip, 1594 "separating/" SEPA_NAME "/maxfailsroot", 1595 "maximal number of consecutive unsuccessful aggregation tries in the root node (-1: unlimited)", 1596 &sepadata->maxfailsroot, TRUE, DEFAULT_MAXFAILSROOT, -1, INT_MAX, NULL, NULL) ); 1597 SCIP_CALL( SCIPaddIntParam(scip, 1598 "separating/" SEPA_NAME "/maxaggrs", 1599 "maximal number of aggregations for each row per separation round", 1600 &sepadata->maxaggrs, TRUE, DEFAULT_MAXAGGRS, 0, INT_MAX, NULL, NULL) ); 1601 SCIP_CALL( SCIPaddIntParam(scip, 1602 "separating/" SEPA_NAME "/maxaggrsroot", 1603 "maximal number of aggregations for each row per separation round in the root node", 1604 &sepadata->maxaggrsroot, TRUE, DEFAULT_MAXAGGRSROOT, 0, INT_MAX, NULL, NULL) ); 1605 SCIP_CALL( SCIPaddIntParam(scip, 1606 "separating/" SEPA_NAME "/maxsepacuts", 1607 "maximal number of cmir cuts separated per separation round", 1608 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) ); 1609 SCIP_CALL( SCIPaddIntParam(scip, 1610 "separating/" SEPA_NAME "/maxsepacutsroot", 1611 "maximal number of cmir cuts separated per separation round in the root node", 1612 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) ); 1613 SCIP_CALL( SCIPaddRealParam(scip, 1614 "separating/" SEPA_NAME "/maxslack", 1615 "maximal slack of rows to be used in aggregation", 1616 &sepadata->maxslack, TRUE, DEFAULT_MAXSLACK, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 1617 SCIP_CALL( SCIPaddRealParam(scip, 1618 "separating/" SEPA_NAME "/maxslackroot", 1619 "maximal slack of rows to be used in aggregation in the root node", 1620 &sepadata->maxslackroot, TRUE, DEFAULT_MAXSLACKROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 1621 SCIP_CALL( SCIPaddRealParam(scip, 1622 "separating/" SEPA_NAME "/densityscore", 1623 "weight of row density in the aggregation scoring of the rows", 1624 &sepadata->densityscore, TRUE, DEFAULT_DENSITYSCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 1625 SCIP_CALL( SCIPaddRealParam(scip, 1626 "separating/" SEPA_NAME "/slackscore", 1627 "weight of slack in the aggregation scoring of the rows", 1628 &sepadata->slackscore, TRUE, DEFAULT_SLACKSCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 1629 SCIP_CALL( SCIPaddRealParam(scip, 1630 "separating/" SEPA_NAME "/maxaggdensity", 1631 "maximal density of aggregated row", 1632 &sepadata->maxaggdensity, TRUE, DEFAULT_MAXAGGDENSITY, 0.0, 1.0, NULL, NULL) ); 1633 SCIP_CALL( SCIPaddRealParam(scip, 1634 "separating/" SEPA_NAME "/maxrowdensity", 1635 "maximal density of row to be used in aggregation", 1636 &sepadata->maxrowdensity, TRUE, DEFAULT_MAXROWDENSITY, 0.0, 1.0, NULL, NULL) ); 1637 SCIP_CALL( SCIPaddIntParam(scip, 1638 "separating/" SEPA_NAME "/densityoffset", 1639 "additional number of variables allowed in row on top of density", 1640 &sepadata->densityoffset, TRUE, DEFAULT_DENSITYOFFSET, 0, INT_MAX, NULL, NULL) ); 1641 SCIP_CALL( SCIPaddRealParam(scip, 1642 "separating/" SEPA_NAME "/maxrowfac", 1643 "maximal row aggregation factor", 1644 &sepadata->maxrowfac, TRUE, DEFAULT_MAXROWFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 1645 SCIP_CALL( SCIPaddIntParam(scip, 1646 "separating/" SEPA_NAME "/maxtestdelta", 1647 "maximal number of different deltas to try (-1: unlimited)", 1648 &sepadata->maxtestdelta, TRUE, DEFAULT_MAXTESTDELTA, -1, INT_MAX, NULL, NULL) ); 1649 SCIP_CALL( SCIPaddRealParam(scip, 1650 "separating/" SEPA_NAME "/aggrtol", 1651 "tolerance for bound distances used to select continuous variable in current aggregated constraint to be eliminated", 1652 &sepadata->aggrtol, TRUE, DEFAULT_AGGRTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 1653 SCIP_CALL( SCIPaddBoolParam(scip, 1654 "separating/" SEPA_NAME "/trynegscaling", 1655 "should negative values also be tested in scaling?", 1656 &sepadata->trynegscaling, TRUE, DEFAULT_TRYNEGSCALING, NULL, NULL) ); 1657 SCIP_CALL( SCIPaddBoolParam(scip, 1658 "separating/" SEPA_NAME "/fixintegralrhs", 1659 "should an additional variable be complemented if f0 = 0?", 1660 &sepadata->fixintegralrhs, TRUE, DEFAULT_FIXINTEGRALRHS, NULL, NULL) ); 1661 SCIP_CALL( SCIPaddBoolParam(scip, 1662 "separating/" SEPA_NAME "/dynamiccuts", 1663 "should generated cuts be removed from the LP if they are no longer tight?", 1664 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) ); 1665 1666 return SCIP_OKAY; 1667 } 1668