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 /* #define SCIP_WRITEPROB */ 25 /* #define SCIP_OUTPUT */ 26 /**@file sepa_cgmip.c 27 * @ingroup DEFPLUGINS_SEPA 28 * @brief Chvatal-Gomory cuts computed via a sub-MIP 29 * @author Marc Pfetsch 30 * 31 * Separate Chvátal-Gomory cuts using a sub-MIP. The approach is based on the following papers. 32 * 33 * M. Fischetti and A. Lodi@n 34 * Optimizing over the first Chvátal closure,@n 35 * in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization IPCO 2005,@n 36 * LNCS 3509, pp. 12-22. Springer, Berlin Heidelberg New York (2005) 37 * 38 * M. Fischetti and A. Lodi@n 39 * Optimizing over the first Chvátal closure,@n 40 * Mathematical Programming 110, 3-20 (2007) 41 * 42 * P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, and A. Lodi@n 43 * Projected Chvátal-Gomory cuts for mixed integer linear programs,@n 44 * Mathematical Programming 113, No. 2 (2008) 45 * 46 * 47 * There are several possibilities to generate the final cut: 48 * 49 * - The CMIR-routines of SCIP can be used (if @p usecmir is true). One can determine which bound is 50 * used in the rounding operation (if @p cmirownbounds is true) or let SCIP choose the best. This 51 * version is generally numerically the most stable. 52 * - If @p usestrongcg is true, we try to generate Strong-CG cuts (as done in sepa_strongcg.c). 53 * - One can directly generate the CG-cut as computed (if @p usecmir and @p usestrongcg are 54 * false). The cut is not taken from the solution of the MIP, but is recomputed, and some care (but 55 * not as much as in the first version) has been taken to create a valid cut. 56 * 57 * The computation time of the separation MIP is limited as follows: 58 * - There is a node limit (parameters @a minnodelimit and @a maxnodelimit). 59 * - There is a time limit (parameter @a timelimit). 60 * - If paramter @a earlyterm is true, the separation is run until the first cut that is violated is 61 * found. (Note that these cuts are not necessarily added to the LP, because here also the norm of 62 * the cuts are taken into account - which cannot easily be included into the separation subscip.) 63 * Then the solution process is continued for a certain number of nodes. 64 * 65 * @todo Check whether one can weaken the conditions on the continuous variables. 66 * @todo Use pointers to originating separators to sort out cuts that should not be used. 67 * 68 * @warning This separator should be used carefully - it may require a long separation time. 69 */ 70 71 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 72 73 #include "blockmemshell/memory.h" 74 #include "scip/cons_linear.h" 75 #include "scip/cuts.h" 76 #include "scip/pub_cons.h" 77 #include "scip/pub_lp.h" 78 #include "scip/pub_message.h" 79 #include "scip/pub_misc.h" 80 #include "scip/pub_sepa.h" 81 #include "scip/pub_var.h" 82 #include "scip/scip_branch.h" 83 #include "scip/scip_cons.h" 84 #include "scip/scip_copy.h" 85 #include "scip/scip_cut.h" 86 #include "scip/scip_general.h" 87 #include "scip/scip_lp.h" 88 #include "scip/scip_mem.h" 89 #include "scip/scip_message.h" 90 #include "scip/scip_numerics.h" 91 #include "scip/scip_param.h" 92 #include "scip/scip_prob.h" 93 #include "scip/scip_randnumgen.h" 94 #include "scip/scip_sepa.h" 95 #include "scip/scip_sol.h" 96 #include "scip/scip_solve.h" 97 #include "scip/scip_solvingstats.h" 98 #include "scip/scip_timing.h" 99 #include "scip/scip_tree.h" 100 #include "scip/scip_var.h" 101 #include "scip/scipdefplugins.h" 102 #include "scip/sepa_cgmip.h" 103 #include <string.h> 104 105 106 #define SEPA_NAME "cgmip" 107 #define SEPA_DESC "Chvatal-Gomory cuts via MIPs separator" 108 #define SEPA_PRIORITY -1000 109 #define SEPA_FREQ -1 110 #define SEPA_MAXBOUNDDIST 0.0 111 #define SEPA_USESSUBSCIP TRUE /**< does the separator use a secondary SCIP instance? */ 112 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 113 114 #define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */ 115 #define DEFAULT_MAXROUNDSROOT 50 /**< maximal number of separation rounds in the root node (-1: unlimited) */ 116 #define DEFAULT_MAXDEPTH -1 /**< maximal depth at which the separator is applied */ 117 #define DEFAULT_DECISIONTREE FALSE /**< Use decision tree to turn separation on/off? */ 118 #define DEFAULT_TIMELIMIT 1e20 /**< time limit for sub-MIP (set to infinity in order to be deterministic) */ 119 #define DEFAULT_MEMORYLIMIT 1e20 /**< memory limit for sub-MIP */ 120 #define DEFAULT_CUTCOEFBND 1000.0 /**< bounds on the values of the coefficients in the CG-cut */ 121 #define DEFAULT_MINNODELIMIT 500LL /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */ 122 #define DEFAULT_MAXNODELIMIT 5000LL /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */ 123 #define DEFAULT_ONLYACTIVEROWS FALSE /**< Use only active rows to generate cuts? */ 124 #define DEFAULT_MAXROWAGE -1 /**< maximal age of rows to consider if onlyactiverows is false */ 125 #define DEFAULT_ONLYRANKONE FALSE /**< Separate rank 1 inequalities w.r.t. CG-MIP separator? */ 126 #define DEFAULT_ONLYINTVARS FALSE /**< Generate cuts for problems with only integer variables? */ 127 #define DEFAULT_CONTCONVERT FALSE /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */ 128 #define DEFAULT_CONTCONVFRAC 0.1 /**< fraction of integral variables converted to be continuous (if contconvert) */ 129 #define DEFAULT_CONTCONVMIN 100 /**< minimum number of integral variables before some are converted to be continuous */ 130 #define DEFAULT_INTCONVERT FALSE /**< Convert some integral variables attaining fractional values to have integral value? */ 131 #define DEFAULT_INTCONVFRAC 0.1 /**< fraction of fractional integral variables converted to have integral value (if intconvert) */ 132 #define DEFAULT_INTCONVMIN 100 /**< minimum number of integral variables before some are converted to have integral value */ 133 #define DEFAULT_SKIPMULTBOUNDS TRUE /**< Skip the upper bounds on the multipliers in the sub-MIP? */ 134 #define DEFAULT_OBJLONE FALSE /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */ 135 #define DEFAULT_OBJWEIGHT 1e-03 /**< objective weight for artificial variables */ 136 #define DEFAULT_OBJWEIGHTSIZE TRUE /**< Weight each row by its size? */ 137 #define DEFAULT_DYNAMICCUTS TRUE /**< Should generated cuts be removed from the LP if they are no longer tight? */ 138 #define DEFAULT_USECMIR TRUE /**< Use CMIR-generator (otherwise add cut directly)? */ 139 #define DEFAULT_USESTRONGCG FALSE /**< Use strong CG-function to strengthen cut? */ 140 #define DEFAULT_CMIROWNBOUNDS FALSE /**< Tell CMIR-generator which bounds to used in rounding? */ 141 #define DEFAULT_USECUTPOOL TRUE /**< Use cutpool to store CG-cuts even if the are not efficient? */ 142 #define DEFAULT_PRIMALSEPARATION TRUE /**< Only separate cuts that are tight for the best feasible solution? */ 143 #define DEFAULT_EARLYTERM TRUE /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */ 144 #define DEFAULT_ADDVIOLATIONCONS FALSE /**< Add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?*/ 145 #define DEFAULT_ADDVIOLCONSHDLR FALSE /**< Add constraint handler to filter out violated cuts? */ 146 #define DEFAULT_CONSHDLRUSENORM TRUE /**< Should the violation constraint handler use the norm of a cut to check for feasibility? */ 147 #define DEFAULT_USEOBJUB FALSE /**< Use upper bound on objective function (via primal solution)? */ 148 #define DEFAULT_USEOBJLB FALSE /**< Use lower bound on objective function (via lower bound)? */ 149 #define DEFAULT_SUBSCIPFAST TRUE /**< Should the settings for the sub-MIP be optimized for speed? */ 150 #define DEFAULT_OUTPUT FALSE /**< Should information about the sub-MIP and cuts be displayed? */ 151 #define DEFAULT_RANDSEED 101 /**< start random seed for random number generation */ 152 #define DEFAULT_GENPRIMALSOLS FALSE /**< Try to generate primal solutions from Gomory cuts? */ 153 154 155 #define NROWSTOOSMALL 5 /**< only separate if the number of rows is larger than this number */ 156 #define NCOLSTOOSMALL 5 /**< only separate if the number of columns is larger than this number */ 157 158 #define EPSILONVALUE 1e-03 /**< epsilon value needed to model strict-inequalities */ 159 #define BETAEPSILONVALUE 1e-02 /**< epsilon value for fracbeta - is larger than EPSILONVALUE for numerical stability */ 160 #define STALLNODELIMIT 1000LL /**< number of stalling nodes if earlyterm is true */ 161 #define CONSHDLRFULLNORM FALSE /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */ 162 #define MINEFFICACY 0.05 /**< minimum efficacy of a cut - compare set.c */ 163 #define MAXNSOLS 1000 /**< maximal number of solutions stored in sub-SCIP */ 164 #define OBJWEIGHTRANGE 0.01 /**< maximal range of scaling of objective w.r.t. size of rows */ 165 166 /* parameters used for CMIR-generation (taken from sepa_gomory) */ 167 #define BOUNDSWITCH 0.9999 168 #define USEVBDS TRUE 169 #define POSTPROCESS TRUE 170 #define MINFRAC 0.0009 /**< to allow a deviation of the same size as EPSILONVALUE */ 171 #define MAXFRAC 0.9991 /**< to allow a deviation of the same size as EPSILONVALUE */ 172 #define FIXINTEGRALRHS FALSE 173 #define MAKECONTINTEGRAL FALSE 174 #define MAXWEIGHTRANGE 1e+05 /**< maximal valid range max(|weights|)/min(|weights|) of row weights */ 175 #define AWAY 0.005 /**< minimal fractionality of a basic variable in order to try GMI cut */ 176 #define SEPARATEROWS TRUE /**< Separate rows with integral slack? */ 177 178 #define MAXAGGRLEN(nvars) nvars /**< currently very large to allow any generation; an alternative would be (0.1*(nvars)+1000) */ 179 180 /** separator data */ 181 struct SCIP_SepaData 182 { 183 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 184 int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */ 185 int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */ 186 int maxdepth; /**< maximal depth at which the separator is applied */ 187 SCIP_Bool decisiontree; /**< Use decision tree to turn separation on/off? */ 188 SCIP_Real timelimit; /**< time limit for subscip */ 189 SCIP_Real memorylimit; /**< memory limit for subscip */ 190 SCIP_Longint minnodelimit; /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */ 191 SCIP_Longint maxnodelimit; /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */ 192 SCIP_Real cutcoefbnd; /**< bounds on the values of the coefficients in the CG-cut */ 193 SCIP_Bool onlyactiverows; /**< Use only active rows to generate cuts? */ 194 int maxrowage; /**< maximal age of rows to consider if onlyactiverows is false */ 195 SCIP_Bool onlyrankone; /**< Separate only rank 1 inequalities w.r.t. CG-MIP separator? */ 196 SCIP_Bool onlyintvars; /**< Generate cuts for problems with only integer variables? */ 197 SCIP_Bool allowlocal; /**< Allow local cuts? */ 198 SCIP_Bool contconvert; /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */ 199 SCIP_Real contconvfrac; /**< fraction of integral variables converted to be continuous (if contconvert) */ 200 int contconvmin; /**< minimum number of integral variables before some are converted to be continuous */ 201 SCIP_Bool intconvert; /**< Convert some integral variables attaining fractional values to have integral value? */ 202 SCIP_Real intconvfrac; /**< fraction of frac. integral variables converted to have integral value (if intconvert) */ 203 int intconvmin; /**< minimum number of integral variables before some are converted to have integral value */ 204 SCIP_Bool skipmultbounds; /**< Skip the upper bounds on the multipliers in the sub-MIP? */ 205 SCIP_Bool objlone; /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */ 206 SCIP_Real objweight; /**< objective weight for artificial variables */ 207 SCIP_Bool objweightsize; /**< Weight each row by its size? */ 208 SCIP_Bool dynamiccuts; /**< Should generated cuts be removed from the LP if they are no longer tight? */ 209 SCIP_Bool usecmir; /**< Use CMIR-generator (otherwise add cut directly)? */ 210 SCIP_Bool usestrongcg; /**< Use strong CG-function to strengthen cut? */ 211 SCIP_Bool cmirownbounds; /**< Tell CMIR-generator which bounds to used in rounding? */ 212 SCIP_Bool usecutpool; /**< Use cutpool to store CG-cuts even if the are not efficient? */ 213 SCIP_Bool primalseparation; /**< Only separate cuts that are tight for the best feasible solution? */ 214 SCIP_Bool earlyterm; /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */ 215 SCIP_Bool addviolationcons; /**< Add constraint to subscip that only allows violated cuts? */ 216 SCIP_Bool addviolconshdlr; /**< Add constraint handler to filter out violated cuts? */ 217 SCIP_Bool conshdlrusenorm; /**< Should the violation constraint handler use the cut-norm to check for feasibility? */ 218 SCIP_Bool useobjub; /**< Use upper bound on objective function (via primal solution)? */ 219 SCIP_Bool useobjlb; /**< Use lower bound on objective function (via lower bound)? */ 220 SCIP_Bool subscipfast; /**< Should the settings for the sub-MIP be optimized for speed? */ 221 SCIP_Bool output; /**< Should information about the sub-MIP and cuts be displayed? */ 222 SCIP_Bool genprimalsols; /**< Try to generate primal solutions from Gomory cuts? */ 223 }; 224 225 226 /** what happens for columns in the LP */ 227 enum CGMIP_ColType 228 { 229 colPresent = 0, /**< column is present in the separating MIP */ 230 colContinuous = 1, /**< column corresponds to a continuous variable */ 231 colConverted = 2, /**< column is converted to be continuous */ 232 colAtUb = 3, /**< variable corresponding to column was at it's upper bound and was complemented */ 233 colAtLb = 4 /**< variable corresponding to column was at it's lower bound (possibly complemented) */ 234 }; 235 typedef enum CGMIP_ColType CGMIP_COLTYPE; 236 237 238 /** data for the sub-MIP */ 239 struct CGMIP_MIPData 240 { 241 SCIP* subscip; /**< pointer to (sub)SCIP data structure containing the auxiliary IP */ 242 unsigned int m; /**< number of constraints of subscip */ 243 unsigned int n; /**< number of variables of subscip */ 244 unsigned int nrows; /**< number of rows of original LP */ 245 unsigned int ncols; /**< number of columns of original LP */ 246 unsigned int ntotalrows; /**< number of total rows used (possibly including objective rows) */ 247 248 SCIP_VAR** alpha; /**< cut coefficient variable (NULL if not in separating MIP) */ 249 SCIP_VAR* beta; /**< rhs of cut */ 250 SCIP_VAR** fracalpha; /**< fractional part of lhs of cut (NULL if not present) */ 251 SCIP_VAR* fracbeta; /**< fractional part of rhs of cut */ 252 CGMIP_COLTYPE* coltype; /**< type for the columns */ 253 SCIP_Bool* iscomplemented; /**< whether the variable was complemented */ 254 SCIP_Bool* isshifted; /**< whether the variable was shifted to have 0 lower bound */ 255 256 SCIP_VAR** ylhs; /**< auxiliary row variables for lhs (NULL if not present) */ 257 SCIP_VAR** yrhs; /**< auxiliary row variables for rhs (NULL if not present) */ 258 259 SCIP_VAR** z; /**< auxiliary variables for upper bounds (NULL if not present) */ 260 261 SCIP_Real* lhs; /**< transformed left hand sides */ 262 SCIP_Real* rhs; /**< transformed left hand sides */ 263 264 char normtype; /**< type of norm to use for efficacy norm calculation */ 265 266 /* additional redundant data */ 267 SCIP_Bool conshdlrusenorm; /**< copy from sepadata */ 268 SCIP_Bool conshdlrfullnorm; /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */ 269 SCIP* scip; /**< original SCIP */ 270 SCIP_SEPA* sepa; /**< CG-cut separator */ 271 SCIP_SEPADATA* sepadata; /**< CG-cut separator data */ 272 }; 273 typedef struct CGMIP_MIPData CGMIP_MIPDATA; 274 275 276 /* 277 * constraint handler to filter out violated cuts 278 */ 279 280 /* constraint handler properties */ 281 #define CONSHDLR_NAME "violatedCuts" 282 #define CONSHDLR_DESC "only allow solutions corresponding to violated cuts" 283 284 /** constraint handler data */ 285 struct SCIP_ConshdlrData 286 { 287 CGMIP_MIPDATA* mipdata; /**< data of separating sub-MIP */ 288 }; 289 290 /* temporary forward declaration */ 291 static 292 SCIP_RETCODE computeCut( 293 SCIP* scip, /**< original scip */ 294 SCIP_SEPA* sepa, /**< separator */ 295 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 296 SCIP_SEPADATA* sepadata, /**< separator data */ 297 SCIP_SOL* sol, /**< current solution for sub-MIP */ 298 SCIP_Bool usefrac, /**< use fractional value of multipliers */ 299 SCIP_Real* cutcoefs, /**< coefficients of the cut */ 300 SCIP_Real* cutrhs, /**< rhs of the cut */ 301 SCIP_Bool* localrowsused, /**< pointer to store whether local rows were used in summation */ 302 SCIP_Bool* localboundsused, /**< pointer to store whether local bounds were used in summation */ 303 int * cutrank, /**< pointer to store the cut rank */ 304 SCIP_Bool* success /**< whether we produced a valid cut */ 305 ); 306 307 /** check whether cut corresponding to solution is violated */ 308 static 309 SCIP_RETCODE solCutIsViolated( 310 SCIP* scip, /**< SCIP data structure */ 311 CGMIP_MIPDATA* mipdata, /**< data of separating sub-MIP */ 312 SCIP_SOL* sol, /**< solution to be checked */ 313 SCIP_Bool* violated /**< pointer to store if the cut is violated */ 314 ) 315 { 316 SCIP_Real cutsqrnorm = 0.0; 317 SCIP* subscip; 318 SCIP_Real act; 319 SCIP_Real norm; 320 SCIP_Real val; 321 SCIP_VAR* var; 322 SCIP_Real rhs; 323 unsigned int j; 324 int len = 0; 325 326 assert( mipdata != NULL ); 327 subscip = mipdata->subscip; 328 assert( subscip != NULL ); 329 assert( violated != NULL ); 330 331 /* initialize activity and norm */ 332 act = 0.0; 333 norm = 1.0; 334 *violated = FALSE; 335 336 /* compute activity and norm */ 337 if ( mipdata->conshdlrusenorm ) 338 { 339 /* check whether we should compute the full cut and then compute the norm */ 340 if ( mipdata->conshdlrfullnorm ) 341 { 342 SCIP_Real* cutcoefs; 343 SCIP_Bool localrowsused; 344 SCIP_Bool localboundsused; 345 SCIP_Bool success; 346 SCIP_VAR** vars; 347 int cutrank = 0; 348 int nvars; 349 350 /* get data */ 351 SCIP_CALL( SCIPgetVarsData(mipdata->scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 352 assert(nvars >= 0); 353 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) ); 354 355 /* compute coefficients */ 356 SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, TRUE, cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) ); 357 358 /* try again if cut was not valid */ 359 if ( ! success ) 360 { 361 SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, FALSE, 362 cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) ); 363 364 if ( ! success ) 365 return SCIP_OKAY; 366 } 367 368 #ifdef SCIP_MORE_DEBUG 369 for (j = 0; j < (unsigned int) nvars; ++j) 370 { 371 if ( ! SCIPisZero(scip, cutcoefs[j]) ) 372 SCIPinfoMessage(scip, NULL, "+ %f x%d", cutcoefs[j], j); 373 } 374 SCIPinfoMessage(scip, NULL, "\n"); 375 #endif 376 377 /* compute activity and Euclidean norm (todo: use arbitrary norm) */ 378 cutsqrnorm = 0.0; 379 for (j = 0; j < (unsigned int) nvars; ++j) 380 { 381 if ( ! SCIPisZero(scip, cutcoefs[j]) ) 382 { 383 act += cutcoefs[j] * SCIPvarGetLPSol(vars[j]); 384 cutsqrnorm += SQR(cutcoefs[j]); 385 } 386 } 387 norm = SQRT(cutsqrnorm); 388 389 SCIPfreeBufferArray(scip, &cutcoefs); 390 } /*lint !e438*/ 391 else 392 { 393 switch ( mipdata->normtype ) 394 { 395 case 'e': 396 cutsqrnorm = 0.0; 397 for (j = 0; j < mipdata->ncols; ++j) 398 { 399 var = mipdata->alpha[j]; 400 if ( var == NULL ) 401 continue; 402 403 val = SCIPgetSolVal(subscip, sol, var); 404 if ( !SCIPisZero(scip, val) ) 405 { 406 act += val * SCIPvarGetObj(var); 407 cutsqrnorm += SQR(val); 408 } 409 } 410 norm = SQRT(cutsqrnorm); 411 break; 412 case 'm': 413 for (j = 0; j < mipdata->ncols; ++j) 414 { 415 var = mipdata->alpha[j]; 416 if ( var == NULL ) 417 continue; 418 419 val = SCIPgetSolVal(subscip, sol, var); 420 if ( !SCIPisZero(scip, val) ) 421 { 422 act += val * SCIPvarGetObj(var); 423 if ( REALABS(val) > norm ) 424 norm = REALABS(val); 425 } 426 } 427 break; 428 case 's': 429 for (j = 0; j < mipdata->ncols; ++j) 430 { 431 var = mipdata->alpha[j]; 432 if ( var == NULL ) 433 continue; 434 435 val = SCIPgetSolVal(subscip, sol, var); 436 if ( !SCIPisZero(scip, val) ) 437 { 438 act += val * SCIPvarGetObj(var); 439 norm += REALABS(val); 440 } 441 } 442 break; 443 case 'd': 444 for (j = 0; j < mipdata->ncols; ++j) 445 { 446 var = mipdata->alpha[j]; 447 if ( var == NULL ) 448 continue; 449 450 val = SCIPgetSolVal(subscip, sol, var); 451 if ( !SCIPisZero(scip, val) ) 452 { 453 act += val * SCIPvarGetObj(var); 454 ++len; 455 } 456 } 457 if ( len > 0 ) 458 norm = 1.0; 459 break; 460 default: 461 SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", mipdata->normtype); 462 return SCIP_INVALIDDATA; 463 } 464 /* get rhs */ 465 rhs = SCIPgetSolVal(subscip, sol, mipdata->beta); 466 } 467 468 /* if norm is 0, the cut is trivial */ 469 if ( SCIPisZero(subscip, norm) ) 470 return SCIP_OKAY; 471 } 472 else 473 { 474 for (j = 0; j < mipdata->ncols; ++j) 475 { 476 var = mipdata->alpha[j]; 477 if ( var == NULL ) 478 continue; 479 480 val = SCIPgetSolVal(subscip, sol, var); 481 if ( !SCIPisZero(subscip, val) ) 482 act += SCIPvarGetObj(var) * val; 483 } 484 485 /* get rhs */ 486 rhs = SCIPgetSolVal(subscip, sol, mipdata->beta); 487 } 488 489 #ifdef SCIP_DEBUG 490 if ( SCIPisEfficacious(subscip, (act - rhs)/norm) ) 491 { 492 SCIPdebugMsg(scip, "Violated cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm); 493 } 494 else 495 { 496 SCIPdebugMsg(scip, "Rejected cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm); 497 } 498 #endif 499 500 *violated = SCIPisEfficacious(subscip, (act - rhs)/norm); 501 502 return SCIP_OKAY; 503 } 504 505 506 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 507 static 508 SCIP_DECL_CONSFREE(consFreeViolatedCuts) 509 { /*lint --e{715}*/ 510 SCIP_CONSHDLRDATA* conshdlrdata; 511 512 assert( scip != NULL ); 513 assert( conshdlr != NULL ); 514 conshdlrdata = SCIPconshdlrGetData(conshdlr); 515 assert( conshdlrdata != NULL ); 516 517 SCIPfreeBlockMemory(scip, &conshdlrdata); 518 519 return SCIP_OKAY; 520 } 521 522 523 /** constraint enforcing method of constraint handler for LP solutions */ 524 static 525 SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts) 526 { /*lint --e{715}*/ 527 SCIP_CONSHDLRDATA* conshdlrdata; 528 SCIP_Bool violated; 529 530 assert( scip != NULL ); 531 assert( conshdlr != NULL ); 532 assert( result != NULL ); 533 534 assert( SCIPgetNLPBranchCands(scip) == 0 ); 535 536 conshdlrdata = SCIPconshdlrGetData(conshdlr); 537 assert( conshdlrdata != NULL ); 538 539 SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, NULL, &violated) ); 540 541 if ( violated ) 542 *result = SCIP_FEASIBLE; 543 else 544 *result = SCIP_CUTOFF; /* cutoff, since all integer variables are integer, but the solution is not feasible */ 545 546 return SCIP_OKAY; 547 } 548 549 550 /** constraint enforcing method of constraint handler for pseudo solutions */ 551 static 552 SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts) 553 { /*lint --e{715}*/ 554 assert( result != NULL ); 555 556 /* this function should better not be called, since we need an LP solution for the sub-MIP to 557 * make sense, because of the multiplier variables. We therefore return SCIP_FEASIBLE. */ 558 *result = SCIP_FEASIBLE; 559 560 return SCIP_OKAY; 561 } 562 563 564 /** feasibility check method of constraint handler for integral solutions */ 565 static 566 SCIP_DECL_CONSCHECK(consCheckViolatedCuts) 567 { /*lint --e{715}*/ 568 SCIP_CONSHDLRDATA* conshdlrdata; 569 SCIP_Bool violated; 570 571 assert( scip != NULL ); 572 assert( conshdlr != NULL ); 573 assert( sol != NULL ); 574 assert( result != NULL ); 575 576 conshdlrdata = SCIPconshdlrGetData(conshdlr); 577 assert( conshdlrdata != NULL ); 578 579 SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, sol, &violated) ); 580 581 if ( violated ) 582 *result = SCIP_FEASIBLE; 583 else 584 *result = SCIP_INFEASIBLE; 585 586 return SCIP_OKAY; 587 } 588 589 590 /** variable rounding lock method of constraint handler */ 591 static 592 SCIP_DECL_CONSLOCK(consLockViolatedCuts) 593 { /*lint --e{715}*/ 594 /* do not lock variables */ 595 return SCIP_OKAY; 596 } 597 598 599 /** creates the violated CG-cut constraint handler and includes it in SCIP */ 600 static 601 SCIP_RETCODE SCIPincludeConshdlrViolatedCut( 602 SCIP* scip, /**< SCIP data structure */ 603 CGMIP_MIPDATA* mipdata /**< data of separating sub-MIP */ 604 ) 605 { 606 SCIP_CONSHDLRDATA* conshdlrdata; 607 SCIP_CONSHDLR* conshdlr; 608 609 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 610 conshdlrdata->mipdata = mipdata; 611 612 /* include constraint handler */ 613 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 614 -1000000, -1000000, 100, FALSE, 615 consEnfolpViolatedCuts, consEnfopsViolatedCuts, consCheckViolatedCuts, consLockViolatedCuts, 616 conshdlrdata) ); 617 618 assert(conshdlr != NULL); 619 620 /* set non-fundamental callbacks via specific setter functions */ 621 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeViolatedCuts) ); 622 623 return SCIP_OKAY; 624 } 625 626 627 /* 628 * local methods 629 */ 630 631 632 /** stores nonzero elements of dense coefficient vector as sparse vector and calculates activity and norm 633 * 634 * copied from sepa_gomory.c 635 */ 636 static 637 SCIP_RETCODE storeCutInArrays( 638 SCIP* scip, /**< SCIP data structure */ 639 int nvars, /**< number of problem variables */ 640 SCIP_Real* cutcoefs, /**< dense coefficient vector */ 641 SCIP_Real* varsolvals, /**< dense variable LP solution vector */ 642 char normtype, /**< type of norm to use for efficacy norm calculation */ 643 int* cutinds, /**< array to store variables of sparse cut vector */ 644 SCIP_Real* cutvals, /**< array to store coefficients of sparse cut vector */ 645 int* cutlen, /**< pointer to store number of nonzero entries in cut */ 646 SCIP_Real* cutact, /**< pointer to store activity of cut */ 647 SCIP_Real* cutnorm /**< pointer to store norm of cut vector */ 648 ) 649 { 650 SCIP_Real val; 651 SCIP_Real cutsqrnorm; 652 SCIP_Real act; 653 SCIP_Real norm; 654 int len; 655 int v; 656 657 assert( nvars == 0 || cutcoefs != NULL ); 658 assert( nvars == 0 || varsolvals != NULL ); 659 assert( cutinds != NULL ); 660 assert( cutvals != NULL ); 661 assert( cutlen != NULL ); 662 assert( cutact != NULL ); 663 assert( cutnorm != NULL ); 664 665 len = 0; 666 act = 0.0; 667 norm = 0.0; 668 switch ( normtype ) 669 { 670 case 'e': 671 cutsqrnorm = 0.0; 672 for (v = 0; v < nvars; ++v) 673 { 674 val = cutcoefs[v]; 675 if ( !SCIPisZero(scip, val) ) 676 { 677 act += val * varsolvals[v]; 678 cutsqrnorm += SQR(val); 679 cutinds[len] = v; 680 cutvals[len++] = val; 681 } 682 } 683 norm = SQRT(cutsqrnorm); 684 break; 685 case 'm': 686 for (v = 0; v < nvars; ++v) 687 { 688 val = cutcoefs[v]; 689 if ( !SCIPisZero(scip, val) ) 690 { 691 act += val * varsolvals[v]; 692 if ( REALABS(val) > norm ) 693 norm = REALABS(val); 694 cutinds[len] = v; 695 cutvals[len++] = val; 696 } 697 } 698 break; 699 case 's': 700 for (v = 0; v < nvars; ++v) 701 { 702 val = cutcoefs[v]; 703 if ( !SCIPisZero(scip, val) ) 704 { 705 act += val * varsolvals[v]; 706 norm += REALABS(val); 707 cutinds[len] = v; 708 cutvals[len++] = val; 709 } 710 } 711 break; 712 case 'd': 713 for (v = 0; v < nvars; ++v) 714 { 715 val = cutcoefs[v]; 716 if ( !SCIPisZero(scip, val) ) 717 { 718 act += val * varsolvals[v]; 719 cutinds[len] = v; 720 cutvals[len++] = val; 721 } 722 } 723 if ( len > 0 ) 724 norm = 1.0; 725 break; 726 default: 727 SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", normtype); 728 return SCIP_INVALIDDATA; 729 } 730 731 *cutlen = len; 732 *cutact = act; 733 *cutnorm = norm; 734 735 return SCIP_OKAY; 736 } 737 738 739 /** Compute lhs/rhs for transformed column 740 * 741 * Consider a variable \f$x_j\f$ and some row of the original system: 742 * \f[ 743 * \gamma \leq a^T x \leq \delta, \quad \ell_j \leq x_j \leq u_j. 744 * \f] 745 * We perform the transformation 746 * \f[ 747 * x_i' = \left\{ 748 * \begin{array}{ll} 749 * s + \frac{1}{\sigma}\, x_j & \mbox{if }i = j\\ 750 * x_i & \mbox{otherwise}, 751 * \end{array} 752 * \right. 753 * \f] 754 * where \f$s\f$ is the offset value and \f$\sigma\f$ is a scaling factor. The new system is 755 * \f[ 756 * \gamma + \sigma\, a_j\,s \leq \sum_{i \neq j} a_i\, x_i' + \sigma a_j\, x_j' \leq \delta + \sigma\, a_j\, s 757 * \f] 758 * with bounds 759 * \f[ 760 * \frac{1}{\sigma} \ell_j + s \leq x_j' \leq \frac{1}{\sigma} u_j + s, \qquad \mbox{ if }\sigma > 0 761 * \f] 762 * and 763 * \f[ 764 * \frac{1}{\sigma} u_j + s \leq x_j' \leq \frac{1}{\sigma} \ell_j + s, \qquad \mbox{ if }\sigma < 0. 765 * \f] 766 * 767 * This can be used as follows: 768 * 769 * - If \f$x_j \geq \ell_j\f$ has a (nonzero) lower bound, one can use \f$s = -\ell_j\f$, \f$\sigma = 1\f$, 770 * and obtain \f$\gamma - a_j\,\ell_j \leq a^T x' \leq \delta - a_j\,\ell_j\f$, \f$0 \leq x_j' \leq u_j - \ell_j\f$. 771 * 772 * - If \f$x_j \leq u_j\f$ has a (nonzero) upper bound, one can use \f$s = u_j\f$, \f$\sigma = -1\f$, 773 * and obtain \f$\gamma - a_j\,u_j \leq \sum_{i \neq j} a_i\, x_i' - a_j\, x_j' \leq \delta - a_j\, u_j\f$, 774 * \f$0 \leq x_j' \leq u_j - \ell_j\f$. 775 */ 776 static 777 SCIP_RETCODE transformColumn( 778 SCIP* scip, /**< SCIP data structure */ 779 SCIP_SEPADATA* sepadata, /**< separator data */ 780 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 781 SCIP_COL* col, /**< column that should be complemented */ 782 SCIP_Real offset, /**< offset by which column should be shifted */ 783 SCIP_Real sigma, /**< scaling factor */ 784 SCIP_Real* lhs, /**< array of lhs of rows */ 785 SCIP_Real* rhs, /**< array rhs of rows */ 786 SCIP_Real* lb, /**< pointer to lb of column */ 787 SCIP_Real* ub, /**< pointer to ub of column */ 788 SCIP_Real* primsol /**< pointer to solution value */ 789 ) 790 { 791 SCIP_ROW** colrows; 792 SCIP_Real* colvals; 793 int pos, i; 794 795 assert( scip != NULL ); 796 assert( lhs != NULL ); 797 assert( rhs != NULL ); 798 assert( col != NULL ); 799 800 colrows = SCIPcolGetRows(col); 801 colvals = SCIPcolGetVals(col); 802 assert( SCIPcolGetNLPNonz(col) == 0 || colrows != NULL ); 803 assert( SCIPcolGetNLPNonz(col) == 0 || colvals != NULL ); 804 assert( ! SCIPisZero(scip, sigma) ); 805 806 /* loop through rows that contain column */ 807 for (i = 0; i < SCIPcolGetNLPNonz(col); ++i) 808 { 809 SCIP_ROW* row; 810 811 row = colrows[i]; 812 assert( row != NULL ); 813 814 /* skip modifiable rows and local rows, unless allowed */ 815 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) ) 816 continue; 817 818 pos = SCIProwGetLPPos(row); 819 assert( 0 <= pos && pos < (int) mipdata->nrows ); 820 821 assert( ! SCIPisInfinity(scip, lhs[pos]) ); 822 if ( ! SCIPisInfinity(scip, -lhs[pos]) ) 823 lhs[pos] += sigma * colvals[i] * offset; 824 825 assert( ! SCIPisInfinity(scip, -rhs[pos]) ); 826 if ( ! SCIPisInfinity(scip, rhs[pos]) ) 827 rhs[pos] += sigma * colvals[i] * offset; 828 } 829 830 /* check objective function */ 831 if ( sepadata->useobjub || sepadata->useobjlb ) 832 { 833 assert( SCIPisEQ(scip, SCIPcolGetObj(col), SCIPvarGetObj(SCIPcolGetVar(col))) ); 834 assert( mipdata->ntotalrows == mipdata->nrows + 1 ); 835 836 if ( ! SCIPisInfinity(scip, -lhs[mipdata->nrows]) ) 837 lhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset; 838 839 if ( ! SCIPisInfinity(scip, rhs[mipdata->nrows]) ) 840 rhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset; 841 } 842 843 /* correct lower and upper bounds and solution */ 844 if ( SCIPisNegative(scip, sigma) ) 845 { 846 SCIP_Real l; 847 848 assert( ! SCIPisInfinity(scip, -*ub) ); 849 if ( ! SCIPisInfinity(scip, *ub) ) 850 l = *ub/sigma + offset; 851 else 852 l = -SCIPinfinity(scip); 853 854 assert( ! SCIPisInfinity(scip, *lb) ); 855 if ( ! SCIPisInfinity(scip, -*lb) ) 856 *ub = *lb/sigma + offset; 857 else 858 *ub = SCIPinfinity(scip); 859 *lb = l; 860 } 861 else 862 { 863 assert( ! SCIPisInfinity(scip, *lb) ); 864 if ( ! SCIPisInfinity(scip, -*lb) ) 865 *lb = *lb/sigma + offset; 866 assert( ! SCIPisInfinity(scip, -*ub) ); 867 if ( ! SCIPisInfinity(scip, *ub) ) 868 *ub = *ub/sigma + offset; 869 } 870 *primsol = *primsol/sigma + offset; 871 872 return SCIP_OKAY; 873 } 874 875 876 /** compute objective coefficient for rows that are weighted by size 877 * 878 * The objective is computed by multiplying a default value by 879 * \f[ 880 * 1 - (r_{\mbox{max}} - r) \frac{1 - a}{r_{\mbox{max}} - r_{\mbox{min}}}, 881 * \f] 882 * where \f$r\f$ is the size of the current row, \f$a \in [0,1]\f$ is a parameter, and \f$r_{\mbox{max}}\f$ and 883 * \f$r_{\mbox{min}}\f$ are the maximal and minimal size of a row, respectively. 884 * 885 * Thus, if \f$r = r_{\mbox{max}}\f$, we get 1 and if \f$r = r_{\mbox{min}}\f$, we get \f$a\f$. 886 */ 887 static 888 SCIP_Real computeObjWeightSize( 889 int rowsize, /**< size of current row */ 890 int minrowsize, /**< maximal size of rows */ 891 int maxrowsize /**< minimal size of rows */ 892 ) 893 { 894 SCIP_Real a; 895 896 assert( maxrowsize > 0 ); 897 assert( minrowsize < INT_MAX ); 898 assert( minrowsize <= maxrowsize ); 899 assert( minrowsize <= rowsize && rowsize <= maxrowsize ); 900 901 if ( minrowsize == maxrowsize ) 902 return 1.0; 903 904 a = (1.0 - OBJWEIGHTRANGE)/((SCIP_Real) (maxrowsize - minrowsize)); 905 906 return 1.0 - a * ((SCIP_Real) (maxrowsize - rowsize)); 907 } 908 909 910 /** Creates a subscip representing the separating MIP. 911 * 912 * Let the constraints of the original MIP be of the following form: 913 * \f[ 914 * \begin{array}{l@{\;}ll} 915 * a \leq A x + & C r & \leq b\\ 916 * \ell \leq x & & \leq u\\ 917 * c \leq & r & \leq d\\ 918 * x \in Z^n. 919 * \end{array} 920 * \f] 921 * Here, some of the bounds may have value \f$\infty\f$ or \f$-\infty\f$. Written in 922 * \f$\leq\f$-form this becomes: 923 * \f[ 924 * \begin{array}{r@{\;}l} 925 * \tilde{A} x + \tilde{C} r & \leq \tilde{b}\\ 926 * -x & \leq -\ell\\ 927 * x & \leq u\\ 928 * -r & \leq -c\\ 929 * r & \leq d\\ 930 * x \in Z^n, 931 * \end{array} 932 * \f] 933 * where we use 934 * \f[ 935 * \tilde{A} = 936 * \left[ 937 * \begin{array}{r} 938 * -A \\ 939 * A 940 * \end{array} 941 * \right], 942 * \quad 943 * \tilde{C} = 944 * \left[ 945 * \begin{array}{r} 946 * - C\\ 947 * C 948 * \end{array} 949 * \right] 950 * \qquad\mbox{ and }\qquad 951 * \tilde{b} = 952 * \left[ 953 * \begin{array}{r} 954 * -a\\ 955 * b 956 * \end{array} 957 * \right]. 958 * \f] 959 * For the moment we assume that \f$c = 0\f$, i.e., the lower bounds on the continuous variables 960 * are 0. To obtain a Chvátal-Gomory cut we have to find nonnegative multipliers \f$y\f$, 961 * \f$\underline{z}\f$, and \f$\overline{z}\f$ such that 962 * \f[ 963 * y^T \tilde{A} - \underline{z}^T + \overline{z}^T \in Z \qquad\mbox{ and }\qquad 964 * y^T \tilde{C} \geq 0. 965 * \f] 966 * Note that we use zero multipliers for the bounds on the continuous variables \f$r\f$. Moreover, 967 * if some bounds are infinity, the corresponding multipliers are assumed to be 0. From these 968 * conditions, we obtain 969 * \f[ 970 * (y^T \tilde{A} - \underline{z}^T + \overline{z}^T)\, x + 971 * y^T \tilde{C} \, r \leq 972 * y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u. 973 * \f] 974 * Because \f$r \geq 0\f$, we can ignore the term \f$y^T \tilde{C} \, r \geq 0\f$ and obtain the 975 * following cut: 976 * \f[ 977 * (y^T \tilde{A} - \underline{z}^T + \overline{z}^T )\, x \leq 978 * \lfloor y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u \rfloor. 979 * \f] 980 * Assume that \f$\ell = 0\f$ for the meantime. Then the cut can be written as: 981 * \f[ 982 * \lfloor y^T \tilde{A} + \overline{z}^T \rfloor \, x \leq 983 * \lfloor y^T \tilde{b} + \overline{z}^T u \rfloor. 984 * \f] 985 * 986 * Following Fischetti and Lodi [2005], let \f$(x^*,r^*)\f$ be a fractional solution of the above 987 * original system. The separating MIP created below is 988 * \f[ 989 * \begin{array}{rlr@{\;}l} 990 * \max & (x^*)^T \alpha - \beta - w^T y \\ 991 * & f = \tilde{A}^T y + \overline{z} - \alpha \\ 992 * & \tilde{f} = \tilde{b}^T y + u^T \overline{z} - \beta\\ 993 * & \tilde{C}^T y \geq 0\\ 994 * & 0 \leq f \leq 1 - \epsilon \\ 995 * & 0 \leq \tilde{f} \leq 1 - \epsilon\\ 996 * & 0 \leq y, \overline{z} \leq 1 - \epsilon.\\ 997 * & \alpha \in Z^m, \beta \in Z. 998 * \end{array} 999 * \f] 1000 * Here, \f$w\f$ is a weight vector; it's idea is to make the sum over all components of \f$y\f$ as 1001 * small as possible, in order to generate sparse cuts. 1002 * 1003 * We perform the following additional computations: 1004 * 1005 * - If the lower bounds on \f$x_i\f$ or \f$r_j\f$ are finite, we shift the variable to have a zero 1006 * lower bound, i.e., we replace it by \f$x_i - \ell_i\f$ (or \f$r_j - u_j\f$). This is helpful in 1007 * several ways: As seen above, the resulting inequalities/formulations simplify. Moreover, it 1008 * allows to drop a variable if \f$x^*_i = 0\f$, see the next comment. If the lower bounds are not 1009 * finite, but the upper bounds are finite, we can complement the variable. If the variables are 1010 * free, the above formulation changes as follows: For free continuous variables, we require 1011 * \f$\tilde{C}^T y = 0\f$. For a free integer variable \f$x_j\f$ (which rarely occurs in 1012 * practice), we require \f$f_j = 0\f$, i.e., we force that \f$(\tilde{A}^T y + \overline{z})_j = 1013 * \alpha_j\f$. 1014 * 1015 * - If \f$x^*_j = 0 = \ell_j\f$ (after the above preprocessing), we drop variable \f$\alpha_j\f$ 1016 * from the formulation. Let \f$(\alpha^*, \beta^*, y^*, \overline{z}^*)\f$ be an 1017 * optimal solution to the separating MIP. Then we can compute \f$\alpha_j = 1018 * \lfloor(\tilde{A}_j^T y^* + \overline{z}^*)\rfloor\f$. 1019 * 1020 * - If \f$x^*_i = u_i\f$, we complement the variable and drop it from the formulation, since the 1021 * lower bound is 0 afterwards. 1022 * 1023 * - If a variable has been shifted or complemented, we have to recompute \f$\beta\f$ with the 1024 * original lhs/rhs. 1025 * 1026 * - If a continuous variable \f$r_j\f$ is free, we have to force equality for the corresponding components in 1027 * \f$y^T \tilde{C} \, r \geq 0\f$. 1028 * 1029 * - If an integer variable \f$x_i\f$ is free, we are not allowed to round the cut down. In this 1030 * case, the combintation of rows and bounds has to be integral. We force this by requiring that 1031 * \f$f_i = 0\f$. 1032 * 1033 * - If @p contconvert is true, some integral variables are randomly treated as if they were 1034 * continuous. This has the effect that in the resulting cut the corresponding coefficient has 1035 * value 0. This makes the cuts more sparse. Moreover, the separation problems should become 1036 * easier. 1037 * 1038 * - If required, i.e., parameter @p primalseparation is true, we force a primal separation step. For 1039 * this we require that the cut is tight at the currently best solution. To get reliable solutions 1040 * we relax equality by EPSILONVALUE. 1041 * 1042 * - If required (via parameters @p useobjub or @p useobjlb), we add a row corresponding to the objective function with 1043 * respect to the current lower and upper bounds. 1044 */ 1045 static 1046 SCIP_RETCODE createSubscip( 1047 SCIP* origscip, /**< SCIP data structure */ 1048 SCIP_SEPA* sepa, /**< separator */ 1049 SCIP_SEPADATA* sepadata, /**< separator data */ 1050 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */ 1051 ) 1052 { 1053 SCIP* subscip; 1054 SCIP_COL** cols; 1055 SCIP_ROW** rows; 1056 SCIP_Real* lhs; 1057 SCIP_Real* rhs; 1058 SCIP_Real* lb; 1059 SCIP_Real* ub; 1060 SCIP_Real* primsol; 1061 SCIP_Real multvarub; 1062 1063 unsigned int cnt; 1064 unsigned int ucnt; 1065 unsigned int nshifted; 1066 unsigned int ncomplemented; 1067 #ifndef NDEBUG 1068 unsigned int ncontconverted = 0; 1069 unsigned int nintconverted = 0; 1070 #endif 1071 unsigned int nlbounds; 1072 unsigned int nubounds; 1073 1074 SCIP_VAR** consvars; 1075 SCIP_Real* consvals; 1076 SCIP_CONS* cons; 1077 int nconsvars; 1078 char name[SCIP_MAXSTRLEN]; 1079 1080 int ncols; 1081 int nrows; 1082 int ntotalrows; 1083 int maxrowsize = 0; 1084 int minrowsize = INT_MAX; 1085 int i, j; 1086 1087 assert( origscip != NULL ); 1088 assert( sepadata != NULL ); 1089 1090 assert( mipdata->subscip == NULL ); 1091 1092 SCIP_CALL( SCIPgetLPColsData(origscip, &cols, &ncols) ); 1093 SCIP_CALL( SCIPgetLPRowsData(origscip, &rows, &nrows) ); 1094 assert( ncols > 0 && nrows > 0 ); 1095 1096 mipdata->m = 0; 1097 mipdata->n = 0; 1098 mipdata->nrows = (unsigned int) nrows; 1099 mipdata->ncols = (unsigned int) ncols; 1100 mipdata->ntotalrows = mipdata->nrows; 1101 1102 if ( sepadata->useobjub || sepadata->useobjlb ) 1103 mipdata->ntotalrows = mipdata->nrows + 1; 1104 1105 assert(mipdata->ntotalrows <= INT_MAX); 1106 ntotalrows = (int) mipdata->ntotalrows; 1107 1108 /* copy value */ 1109 mipdata->conshdlrusenorm = sepadata->conshdlrusenorm; 1110 1111 /* create subscip */ 1112 SCIP_CALL( SCIPcreate( &(mipdata->subscip) ) ); 1113 subscip = mipdata->subscip; 1114 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) ); 1115 1116 /* add violation constraint handler if requested */ 1117 if ( sepadata->addviolconshdlr ) 1118 { 1119 SCIP_CALL( SCIPincludeConshdlrViolatedCut(subscip, mipdata) ); 1120 } 1121 1122 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sepa_cgmip separating MIP (%s)", SCIPgetProbName(origscip)); 1123 SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL , NULL , NULL , NULL , NULL , NULL) ); 1124 SCIPsetSubscipDepth(subscip, SCIPgetSubscipDepth(origscip) + 1); 1125 SCIP_CALL( SCIPsetObjsense(subscip, SCIP_OBJSENSE_MAXIMIZE) ); 1126 1127 /* alloc memory for subscipdata elements */ 1128 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->alpha), ncols) ); 1129 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->fracalpha), ncols) ); 1130 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->coltype), ncols) ); 1131 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->iscomplemented), ncols) ); 1132 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->isshifted), ncols) ); 1133 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->ylhs), ntotalrows) ); 1134 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->yrhs), ntotalrows) ); 1135 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->z), 2*ncols) ); 1136 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->lhs), ntotalrows) ); 1137 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->rhs), ntotalrows) ); 1138 lhs = mipdata->lhs; 1139 rhs = mipdata->rhs; 1140 1141 /* get temporary storage */ 1142 SCIP_CALL( SCIPallocBufferArray(origscip, &lb, ncols) ); 1143 SCIP_CALL( SCIPallocBufferArray(origscip, &ub, ncols) ); 1144 SCIP_CALL( SCIPallocBufferArray(origscip, &primsol, ncols) ); 1145 1146 /* store lhs/rhs for complementing (see below) and compute maximal nonzeros of candidate rows */ 1147 for (i = 0; i < nrows; ++i) 1148 { 1149 SCIP_Real val; 1150 SCIP_ROW* row; 1151 1152 row = rows[i]; 1153 assert( row != NULL ); 1154 1155 val = SCIProwGetLhs(row) - SCIProwGetConstant(row); 1156 if ( SCIProwIsIntegral(row) ) 1157 val = SCIPfeasCeil(origscip, val); /* row is integral: round left hand side up */ 1158 lhs[i] = val; 1159 1160 val = SCIProwGetRhs(row) - SCIProwGetConstant(row); 1161 if ( SCIProwIsIntegral(row) ) 1162 val = SCIPfeasFloor(origscip, val); /* row is integral: round right hand side down */ 1163 rhs[i] = val; 1164 1165 /* skip modifiable rows and local rows, unless allowed */ 1166 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) ) 1167 continue; 1168 1169 /* skip rows that not have been active for a longer time */ 1170 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage ) 1171 continue; 1172 1173 /* check whether we want to skip cuts produced by the CGMIP separator */ 1174 if ( sepadata->onlyrankone ) 1175 { 1176 if ( SCIProwGetOriginSepa(row) == sepa ) 1177 continue; 1178 } 1179 1180 /* determine maximal row size: */ 1181 val = SCIPgetRowLPActivity(origscip, row); 1182 if ( ! SCIPisInfinity(origscip, REALABS(lhs[i])) ) 1183 { 1184 if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetLhs(row)) ) 1185 { 1186 if ( SCIProwGetNLPNonz(row) > maxrowsize ) 1187 maxrowsize = SCIProwGetNLPNonz(row); 1188 if ( SCIProwGetNLPNonz(row) < minrowsize ) 1189 minrowsize = SCIProwGetNLPNonz(row); 1190 } 1191 } 1192 else 1193 { 1194 if ( ! SCIPisInfinity(origscip, rhs[i]) ) 1195 { 1196 if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetRhs(row)) ) 1197 { 1198 if ( SCIProwGetNLPNonz(row) > maxrowsize ) 1199 maxrowsize = SCIProwGetNLPNonz(row); 1200 if ( SCIProwGetNLPNonz(row) < minrowsize ) 1201 minrowsize = SCIProwGetNLPNonz(row); 1202 } 1203 } 1204 } 1205 } 1206 assert( maxrowsize > 0 ); 1207 assert( minrowsize < INT_MAX ); 1208 1209 /* add cuts for objective function if required */ 1210 if ( sepadata->useobjub ) 1211 { 1212 assert( mipdata->ntotalrows == mipdata->nrows + 1 ); 1213 rhs[mipdata->nrows] = SCIPgetUpperbound(origscip); 1214 assert( ! SCIPisObjIntegral(origscip) || SCIPisFeasIntegral(origscip, SCIPgetUpperbound(origscip)) ); 1215 1216 if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize ) 1217 maxrowsize = SCIPgetNObjVars(origscip); 1218 if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize ) 1219 minrowsize = SCIPgetNObjVars(origscip); 1220 } 1221 if ( sepadata->useobjlb ) 1222 { 1223 assert( mipdata->ntotalrows == mipdata->nrows + 1 ); 1224 1225 if ( SCIPisObjIntegral(origscip) ) 1226 lhs[mipdata->nrows] = SCIPfeasCeil(origscip, SCIPgetLowerbound(origscip)); 1227 else 1228 lhs[mipdata->nrows] = SCIPgetLowerbound(origscip); 1229 1230 if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize ) 1231 maxrowsize = SCIPgetNObjVars(origscip); 1232 if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize ) 1233 minrowsize = SCIPgetNObjVars(origscip); 1234 } 1235 1236 /* store lb/ub for complementing and perform preprocessing */ 1237 nshifted = 0; 1238 ncomplemented = 0; 1239 nlbounds = 0; 1240 nubounds = 0; 1241 for (j = 0; j < ncols; ++j) 1242 { 1243 SCIP_COL* col; 1244 SCIP_VAR* var; 1245 1246 col = cols[j]; 1247 assert( col != NULL ); 1248 var = SCIPcolGetVar(col); 1249 assert( var != NULL ); 1250 1251 primsol[j] = SCIPcolGetPrimsol(col); 1252 assert( SCIPisEQ(origscip, SCIPgetVarSol(origscip, var), primsol[j]) ); 1253 1254 lb[j] = SCIPvarGetLbGlobal(var); 1255 assert( SCIPisEQ(origscip, SCIPvarGetLbLocal(var), SCIPcolGetLb(col)) ); 1256 1257 /* if allowed, try to use stronger local bound */ 1258 if ( sepadata->allowlocal && SCIPisGT(origscip, SCIPvarGetLbLocal(var), lb[j]) ) 1259 lb[j] = SCIPvarGetLbLocal(var); 1260 1261 ub[j] = SCIPvarGetUbGlobal(var); 1262 assert( SCIPisEQ(origscip, SCIPvarGetUbLocal(var), SCIPcolGetUb(col)) ); 1263 1264 /* if allowed, try to use stronger local bound */ 1265 if ( sepadata->allowlocal && SCIPisLT(origscip, SCIPvarGetUbLocal(var), ub[j]) ) 1266 ub[j] = SCIPvarGetUbLocal(var); 1267 1268 mipdata->coltype[j] = colPresent; 1269 mipdata->iscomplemented[j] = FALSE; 1270 mipdata->isshifted[j] = FALSE; 1271 1272 /* check status of column/variable */ 1273 if ( SCIPcolIsIntegral(col) ) 1274 { 1275 /* integral variables taking integral values are not interesting - will be substituted out below */ 1276 if ( ! SCIPisFeasIntegral(origscip, primsol[j]) ) 1277 { 1278 /* possibly convert fractional integral variables to take integral values */ 1279 if ( sepadata->intconvert && ncols >= sepadata->intconvmin ) 1280 { 1281 /* randomly convert variables */ 1282 if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->intconvfrac ) 1283 { 1284 assert( ! SCIPisInfinity(origscip, ub[j]) || ! SCIPisInfinity(origscip, -lb[j]) ); 1285 1286 /* if both bounds are finite, take the closer one */ 1287 if ( ! SCIPisInfinity(origscip, ub[j]) && ! SCIPisInfinity(origscip, -lb[j]) ) 1288 { 1289 assert( SCIPisFeasIntegral(origscip, ub[j]) ); 1290 assert( SCIPisFeasIntegral(origscip, lb[j]) ); 1291 assert( SCIPisFeasLT(origscip, primsol[j], ub[j]) ); 1292 assert( SCIPisFeasGT(origscip, primsol[j], lb[j]) ); 1293 if ( ub[j] - primsol[j] < primsol[j] - lb[j] ) 1294 primsol[j] = ub[j]; 1295 else 1296 primsol[j] = lb[j]; 1297 #ifndef NDEBUG 1298 ++nintconverted; 1299 #endif 1300 } 1301 else 1302 { 1303 /* if only lower bound is finite */ 1304 if ( ! SCIPisInfinity(origscip, -lb[j]) ) 1305 { 1306 assert( SCIPisFeasIntegral(origscip, lb[j]) ); 1307 primsol[j] = lb[j]; 1308 #ifndef NDEBUG 1309 ++nintconverted; 1310 #endif 1311 } 1312 else 1313 { 1314 assert( ! SCIPisInfinity(origscip, ub[j]) ); 1315 assert( SCIPisFeasIntegral(origscip, ub[j]) ); 1316 primsol[j] = ub[j]; 1317 #ifndef NDEBUG 1318 ++nintconverted; 1319 #endif 1320 } 1321 } 1322 } 1323 } 1324 } 1325 1326 /* integral variables taking integral values are not interesting - will be substituted out below */ 1327 if ( ! SCIPisFeasIntegral(origscip, primsol[j]) ) 1328 { 1329 /* possibly convert integral variables to be continuous */ 1330 if ( sepadata->contconvert && ncols >= sepadata->contconvmin ) 1331 { 1332 /* randomly convert variables */ 1333 if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->contconvfrac ) 1334 { 1335 /* preprocessing is also performed for converted columns */ 1336 mipdata->coltype[j] = colConverted; 1337 #ifndef NDEBUG 1338 ++ncontconverted; 1339 #endif 1340 } 1341 } 1342 } 1343 } 1344 else 1345 { 1346 /* detect continuous variables, but perform preprocessing for them */ 1347 mipdata->coltype[j] = colContinuous; 1348 } 1349 1350 /* if integer variable is at its upper bound -> complementing (this also generates a 0 lower bound) */ 1351 if ( mipdata->coltype[j] == colPresent && SCIPisFeasEQ(origscip, primsol[j], ub[j]) ) 1352 { 1353 assert( ! SCIPisInfinity(origscip, ub[j]) ); 1354 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) ); 1355 mipdata->iscomplemented[j] = TRUE; 1356 mipdata->coltype[j] = colAtUb; 1357 ++nubounds; 1358 } 1359 else 1360 { 1361 /* if a variable has a finite nonzero lower bound -> shift */ 1362 if ( ! SCIPisInfinity(origscip, -lb[j]) ) 1363 { 1364 if ( ! SCIPisZero(origscip, lb[j]) ) 1365 { 1366 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, -lb[j], 1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) ); 1367 assert( SCIPisZero(origscip, lb[j]) ); 1368 mipdata->isshifted[j] = TRUE; 1369 ++nshifted; 1370 } 1371 1372 /* if integer variable is at its lower bound */ 1373 if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) ) 1374 { 1375 mipdata->coltype[j] = colAtLb; 1376 ++nlbounds; 1377 } 1378 } 1379 else 1380 { 1381 /* lower bound is minus-infinity -> check whether upper bound is finite */ 1382 if ( ! SCIPisInfinity(origscip, ub[j]) ) 1383 { 1384 /* complement variable */ 1385 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) ); 1386 assert( SCIPisZero(origscip, lb[j]) ); 1387 mipdata->iscomplemented[j] = TRUE; 1388 ++ncomplemented; 1389 1390 /* if integer variable is at its lower bound */ 1391 if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) ) 1392 { 1393 mipdata->coltype[j] = colAtLb; 1394 ++nlbounds; 1395 } 1396 } 1397 } 1398 } 1399 1400 assert( SCIPisFeasLE(origscip, lb[j], primsol[j]) ); 1401 assert( SCIPisFeasLE(origscip, primsol[j], ub[j]) ); 1402 } 1403 1404 #ifndef NDEBUG 1405 if ( sepadata->intconvert && ncols >= sepadata->intconvmin ) 1406 { 1407 SCIPdebugMsg(origscip, "Converted %u fractional integral variables to have integral value.\n", nintconverted); 1408 } 1409 if ( sepadata->contconvert && ncols >= sepadata->contconvmin ) 1410 { 1411 SCIPdebugMsg(origscip, "Converted %u integral variables to be continuous.\n", ncontconverted); 1412 } 1413 #endif 1414 SCIPdebugMsg(origscip, "Original variables: %d integral, %d continuous, %u shifted, %u complemented, %u at lb, %u at ub\n", 1415 SCIPgetNBinVars(origscip) + SCIPgetNIntVars(origscip) + SCIPgetNImplVars(origscip), SCIPgetNContVars(origscip), 1416 nshifted, ncomplemented, nlbounds, nubounds); 1417 1418 /* prepare upper bound on y-variables */ 1419 if ( sepadata->skipmultbounds ) 1420 multvarub = SCIPinfinity(origscip); 1421 else 1422 multvarub = 1.0 - EPSILONVALUE; 1423 1424 /* create artificial variables for row combinations (y-variables) */ 1425 cnt = 0; 1426 for (i = 0; i < nrows; ++i) 1427 { 1428 SCIP_ROW* row; 1429 1430 row = rows[i]; 1431 assert( row != NULL ); 1432 1433 mipdata->ylhs[i] = NULL; 1434 mipdata->yrhs[i] = NULL; 1435 1436 /* skip modifiable rows and local rows, unless allowed */ 1437 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) ) 1438 continue; 1439 1440 /* skip rows that not have been active for a longer time */ 1441 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage ) 1442 continue; 1443 1444 /* check whether we want to skip cuts produced by the CGMIP separator */ 1445 if ( sepadata->onlyrankone ) 1446 { 1447 if ( SCIProwGetOriginSepa(row) == sepa ) 1448 continue; 1449 } 1450 1451 /* if we have an equation */ 1452 if ( SCIPisEQ(origscip, lhs[i], rhs[i]) ) 1453 { 1454 SCIP_Real weight = -sepadata->objweight; 1455 1456 assert( ! SCIPisInfinity(origscip, rhs[i]) ); 1457 assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) ); /* equations should always be active */ 1458 assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) ); 1459 1460 if ( sepadata->objweightsize ) 1461 weight = - sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize); 1462 1463 /* create two variables for each equation */ 1464 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq1_%d", i); 1465 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub, 1466 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1467 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) ); 1468 ++cnt; 1469 1470 #ifdef SCIP_MORE_DEBUG 1471 SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row)); 1472 #endif 1473 1474 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq2_%d", i); 1475 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub, 1476 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1477 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) ); 1478 ++cnt; 1479 1480 #ifdef SCIP_MORE_DEBUG 1481 SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row)); 1482 #endif 1483 } 1484 else 1485 { 1486 /* create variable for lhs of row if necessary */ 1487 if ( ! SCIPisInfinity(origscip, -lhs[i]) ) 1488 { 1489 SCIP_Bool isactive = FALSE; 1490 SCIP_Real weight = 0.0; 1491 1492 /* if the row is active, use objective weight equal to -sepadata->objweight */ 1493 if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) ) 1494 { 1495 isactive = TRUE; 1496 if ( sepadata->objweightsize ) 1497 weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize); 1498 else 1499 weight = -sepadata->objweight; 1500 } 1501 1502 if ( ! sepadata->onlyactiverows || isactive ) 1503 { 1504 /* add variable */ 1505 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ylhs_%d", i); 1506 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub, 1507 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1508 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) ); 1509 ++cnt; 1510 1511 #ifdef SCIP_MORE_DEBUG 1512 SCIPdebugMsg(origscip, "Created variable <%s> for >= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight); 1513 #endif 1514 } 1515 } 1516 1517 /* create variable for rhs of row if necessary */ 1518 if ( ! SCIPisInfinity(origscip, rhs[i]) ) 1519 { 1520 SCIP_Bool isactive = FALSE; 1521 SCIP_Real weight = 0.0; 1522 1523 /* if the row is active, use objective weight equal to -sepadata->objweight */ 1524 if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) ) 1525 { 1526 isactive = TRUE; 1527 if ( sepadata->objweightsize ) 1528 weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize); 1529 else 1530 weight = -sepadata->objweight; 1531 } 1532 1533 if ( ! sepadata->onlyactiverows || isactive ) 1534 { 1535 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yrhs_%d", i); 1536 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub, 1537 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1538 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) ); 1539 ++cnt; 1540 1541 #ifdef SCIP_MORE_DEBUG 1542 SCIPdebugMsg(origscip, "Created variable <%s> for <= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight); 1543 #endif 1544 } 1545 } 1546 } 1547 } 1548 assert( (int) cnt <= 2 * nrows ); 1549 mipdata->n += cnt; 1550 1551 /* create artificial variables for objective function (if required) (y-variables) */ 1552 if ( sepadata->useobjub || sepadata->useobjlb ) 1553 { 1554 SCIP_Real weight = 0.0; 1555 1556 assert( mipdata->ntotalrows == mipdata->nrows + 1 ); 1557 mipdata->ylhs[mipdata->nrows] = NULL; 1558 mipdata->yrhs[mipdata->nrows] = NULL; 1559 cnt = 0; 1560 1561 if ( sepadata->objweightsize ) 1562 weight = -sepadata->objweight * computeObjWeightSize(SCIPgetNObjVars(origscip), minrowsize, maxrowsize); 1563 else 1564 weight = -sepadata->objweight; 1565 1566 /* create variable for upper objective bound if necessary */ 1567 if ( sepadata->useobjub && ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) ) 1568 { 1569 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjub"); 1570 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[mipdata->nrows]), name, 0.0, multvarub, 1571 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1572 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[mipdata->nrows]) ); 1573 ++cnt; 1574 1575 #ifdef SCIP_MORE_DEBUG 1576 SCIPdebugMsg(origscip, "Created variable <%s> for upper bound on objective (weight: %f).\n", name, weight); 1577 #endif 1578 } 1579 1580 /* create variable for lower bound objective if necessary */ 1581 if ( sepadata->useobjlb && ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) ) 1582 { 1583 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjlb"); 1584 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[mipdata->nrows]), name, 0.0, multvarub, 1585 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1586 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[mipdata->nrows]) ); 1587 ++cnt; 1588 1589 #ifdef SCIP_MORE_DEBUG 1590 SCIPdebugMsg(origscip, "Created variable <%s> for lower bound on objective (weight: %f).\n", name, weight); 1591 #endif 1592 } 1593 1594 assert( (int) cnt <= 2 * ntotalrows ); 1595 mipdata->n += cnt; 1596 } 1597 1598 /* create alpha, bound, and fractional variables */ 1599 cnt = 0; 1600 ucnt = 0; 1601 for (j = 0; j < ncols; ++j) 1602 { 1603 mipdata->z[j] = NULL; 1604 mipdata->alpha[j] = NULL; 1605 mipdata->fracalpha[j] = NULL; 1606 1607 if ( mipdata->coltype[j] == colPresent ) 1608 { 1609 SCIP_Real obj; 1610 1611 if ( sepadata->objlone ) 1612 obj = 0.0; 1613 else 1614 obj = primsol[j]; 1615 1616 /* create alpha variables */ 1617 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j); 1618 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->alpha[j]), name, -sepadata->cutcoefbnd, sepadata->cutcoefbnd, obj, 1619 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1620 SCIP_CALL( SCIPaddVar(subscip, mipdata->alpha[j]) ); 1621 ++cnt; 1622 1623 /* create fractional variables */ 1624 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "f_%d", j); 1625 if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) ) 1626 { 1627 /* fix fractional value to be zero for free original variables */ 1628 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 0.0, 0.0, 1629 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1630 } 1631 else 1632 { 1633 /* fractional value in [0, 1) for variables with finite bounds */ 1634 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 1.0-EPSILONVALUE, 0.0, 1635 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1636 } 1637 SCIP_CALL( SCIPaddVar(subscip, mipdata->fracalpha[j]) ); 1638 ++cnt; 1639 1640 /* create variables for upper bounds */ 1641 if ( ! SCIPisInfinity(origscip, ub[j]) ) 1642 { 1643 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "zub_%d", j); 1644 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->z[j]), name, 0.0, multvarub, 1645 0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1646 SCIP_CALL( SCIPaddVar(subscip, mipdata->z[j]) ); 1647 ++ucnt; 1648 } 1649 } 1650 } 1651 assert( (int) cnt <= 2 * ncols ); 1652 assert( (int) ucnt <= ncols ); 1653 1654 /* create variable for the rhs of the cut */ 1655 if ( sepadata->objlone ) 1656 { 1657 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, 0.0, 1658 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1659 } 1660 else 1661 { 1662 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, -1.0, 1663 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1664 } 1665 SCIP_CALL( SCIPaddVar(subscip, mipdata->beta) ); 1666 1667 /* create fractional variable for the rhs */ 1668 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracbeta), "fracbeta", 0.0, 1.0-BETAEPSILONVALUE, 0.0, 1669 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1670 SCIP_CALL( SCIPaddVar(subscip, mipdata->fracbeta) ); 1671 mipdata->n += cnt + ucnt + 2; 1672 1673 /* get temporary storage */ 1674 SCIP_CALL( SCIPallocBufferArray(origscip, &consvals, (int) mipdata->n) ); 1675 SCIP_CALL( SCIPallocBufferArray(origscip, &consvars, (int) mipdata->n) ); 1676 1677 /* create constraints for alpha variables of CG-cut */ 1678 cnt = 0; 1679 for (j = 0; j < ncols; ++j) 1680 { 1681 SCIP_ROW** colrows; 1682 SCIP_Real* colvals; 1683 1684 /* create ordinary part for all selected variables */ 1685 if ( mipdata->coltype[j] == colPresent ) 1686 { 1687 SCIP_Real sigma; 1688 1689 assert( cols[j] != NULL ); 1690 colrows = SCIPcolGetRows(cols[j]); 1691 colvals = SCIPcolGetVals(cols[j]); 1692 nconsvars = 0; 1693 1694 if ( mipdata->iscomplemented[j] ) 1695 sigma = -1.0; 1696 else 1697 sigma = 1.0; 1698 1699 /* add part for columns */ 1700 for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i) 1701 { 1702 SCIP_ROW* row; 1703 int pos; 1704 1705 row = colrows[i]; 1706 assert( row != NULL ); 1707 1708 /* skip modifiable rows and local rows, unless allowed */ 1709 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) ) 1710 continue; 1711 1712 pos = SCIProwGetLPPos(row); 1713 assert( 0 <= pos && pos < nrows ); 1714 1715 if ( mipdata->ylhs[pos] != NULL ) 1716 { 1717 consvars[nconsvars] = mipdata->ylhs[pos]; 1718 consvals[nconsvars] = -sigma * colvals[i]; 1719 ++nconsvars; 1720 } 1721 if ( mipdata->yrhs[pos] != NULL ) 1722 { 1723 consvars[nconsvars] = mipdata->yrhs[pos]; 1724 consvals[nconsvars] = sigma * colvals[i]; 1725 ++nconsvars; 1726 } 1727 assert( nconsvars <= (int) mipdata->n ); 1728 } 1729 /* add part for upper bounds */ 1730 if ( mipdata->z[j] != NULL ) 1731 { 1732 assert( ! SCIPisInfinity(origscip, ub[j]) ); 1733 consvars[nconsvars] = mipdata->z[j]; 1734 consvals[nconsvars] = 1.0; 1735 ++nconsvars; 1736 } 1737 assert( nconsvars <= (int) mipdata->n ); 1738 1739 /* add alpha variable */ 1740 consvars[nconsvars] = mipdata->alpha[j]; 1741 consvals[nconsvars] = -1.0; 1742 ++nconsvars; 1743 assert( nconsvars <= (int) mipdata->n ); 1744 1745 /* add fractional-alpha variable */ 1746 consvars[nconsvars] = mipdata->fracalpha[j]; 1747 consvals[nconsvars] = -1.0; 1748 ++nconsvars; 1749 assert( nconsvars <= (int) mipdata->n ); 1750 1751 /* check for lower and upper objective bounds */ 1752 if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) ) 1753 { 1754 /* add lower objective bound */ 1755 if ( mipdata->ylhs[mipdata->nrows] != NULL ) 1756 { 1757 assert( sepadata->useobjlb ); 1758 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows]; 1759 consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]); 1760 ++nconsvars; 1761 } 1762 1763 /* add upper objective bound */ 1764 if ( mipdata->yrhs[mipdata->nrows] != NULL ) 1765 { 1766 assert( sepadata->useobjub ); 1767 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows]; 1768 consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]); 1769 ++nconsvars; 1770 } 1771 } 1772 1773 /* add linear constraint */ 1774 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j); 1775 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, 0.0, 1776 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1777 SCIP_CALL( SCIPaddCons(subscip, cons) ); 1778 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 1779 ++cnt; 1780 } 1781 /* generate part that makes sure that cut is valid for continuous variables */ 1782 else if ( mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted ) 1783 { 1784 SCIP_Real sigma; 1785 SCIP_Real r; 1786 1787 assert( cols[j] != NULL ); 1788 colrows = SCIPcolGetRows(cols[j]); 1789 colvals = SCIPcolGetVals(cols[j]); 1790 nconsvars = 0; 1791 1792 if ( mipdata->iscomplemented[j] ) 1793 sigma = -1.0; 1794 else 1795 sigma = 1.0; 1796 1797 /* add part for columns */ 1798 for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i) 1799 { 1800 SCIP_ROW* row; 1801 int pos; 1802 1803 row = colrows[i]; 1804 assert( row != NULL ); 1805 1806 /* skip modifiable rows and local rows, unless allowed */ 1807 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) ) 1808 continue; 1809 1810 pos = SCIProwGetLPPos(row); 1811 assert( 0 <= pos && pos < nrows ); 1812 1813 if ( mipdata->ylhs[pos] != NULL ) 1814 { 1815 consvars[nconsvars] = mipdata->ylhs[pos]; 1816 consvals[nconsvars] = -sigma * colvals[i]; 1817 ++nconsvars; 1818 } 1819 if ( mipdata->yrhs[pos] != NULL ) 1820 { 1821 consvars[nconsvars] = mipdata->yrhs[pos]; 1822 consvals[nconsvars] = sigma * colvals[i]; 1823 ++nconsvars; 1824 } 1825 assert( nconsvars <= (int) mipdata->n ); 1826 } 1827 1828 /* check for lower and upper objective bounds */ 1829 if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) ) 1830 { 1831 /* add lower objective bound */ 1832 if ( mipdata->ylhs[mipdata->nrows] ) 1833 { 1834 assert( sepadata->useobjlb ); 1835 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows]; 1836 consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]); 1837 ++nconsvars; 1838 } 1839 1840 /* add upper objective bound */ 1841 if ( mipdata->yrhs[mipdata->nrows] ) 1842 { 1843 assert( sepadata->useobjub ); 1844 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows]; 1845 consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]); 1846 ++nconsvars; 1847 } 1848 } 1849 1850 /* add linear constraint */ 1851 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cont_%d", j); 1852 1853 /* for free continuous variables require equality */ 1854 r = SCIPinfinity(subscip); 1855 if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) ) 1856 r = 0.0; 1857 else 1858 assert( SCIPisZero(origscip, lb[j]) ); 1859 1860 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, r, 1861 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1862 SCIP_CALL( SCIPaddCons(subscip, cons) ); 1863 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 1864 ++cnt; 1865 } 1866 } 1867 assert( (int) cnt <= ncols ); 1868 mipdata->m += cnt; 1869 1870 /* create constraints for rhs of cut */ 1871 nconsvars = 0; 1872 1873 /* first for the rows */ 1874 for (i = 0; i < nrows; ++i) 1875 { 1876 assert( rows[i] != NULL ); 1877 1878 /* skip modifiable rows and local rows, unless allowed */ 1879 if ( SCIProwIsModifiable(rows[i]) || (SCIProwIsLocal(rows[i]) && !sepadata->allowlocal) ) 1880 continue; 1881 1882 /* if lhs is there */ 1883 if ( mipdata->ylhs[i] != NULL && ! SCIPisZero(origscip, lhs[i]) ) 1884 { 1885 assert( ! SCIPisInfinity(origscip, -lhs[i]) ); 1886 consvars[nconsvars] = mipdata->ylhs[i]; 1887 consvals[nconsvars] = -lhs[i]; 1888 ++nconsvars; 1889 } 1890 /* if rhs is there */ 1891 if ( mipdata->yrhs[i] != NULL && ! SCIPisZero(origscip, rhs[i]) ) 1892 { 1893 assert( ! SCIPisInfinity(origscip, rhs[i]) ); 1894 consvars[nconsvars] = mipdata->yrhs[i]; 1895 consvals[nconsvars] = rhs[i]; 1896 ++nconsvars; 1897 } 1898 assert( nconsvars <= (int) mipdata->n ); 1899 } 1900 1901 if ( sepadata->useobjub || sepadata->useobjlb ) 1902 { 1903 /* add lower objective bound */ 1904 if ( mipdata->ylhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, lhs[mipdata->nrows]) ) 1905 { 1906 assert( sepadata->useobjlb ); 1907 assert( ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) ); 1908 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows]; 1909 consvals[nconsvars] = -lhs[mipdata->nrows]; 1910 ++nconsvars; 1911 } 1912 1913 /* add upper objective bound */ 1914 if ( mipdata->yrhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, rhs[mipdata->nrows]) ) 1915 { 1916 assert( sepadata->useobjub ); 1917 assert( ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) ); 1918 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows]; 1919 consvals[nconsvars] = rhs[mipdata->nrows]; 1920 ++nconsvars; 1921 } 1922 assert( nconsvars <= (int) mipdata->n ); 1923 } 1924 1925 /* next for the columns */ 1926 for (j = 0; j < ncols; ++j) 1927 { 1928 /* if ub is there */ 1929 if ( mipdata->z[j] != NULL && ! SCIPisZero(origscip, ub[j]) ) 1930 { 1931 assert( mipdata->coltype[j] == colPresent ); 1932 assert( ! SCIPisInfinity(origscip, ub[j]) ); 1933 consvars[nconsvars] = mipdata->z[j]; 1934 consvals[nconsvars] = ub[j]; 1935 ++nconsvars; 1936 assert( nconsvars <= (int) mipdata->n ); 1937 } 1938 } 1939 /* add beta variable */ 1940 consvars[nconsvars] = mipdata->beta; 1941 consvals[nconsvars] = -1.0; 1942 ++nconsvars; 1943 1944 /* add fractional-beta variable */ 1945 consvars[nconsvars] = mipdata->fracbeta; 1946 consvals[nconsvars] = -1.0; 1947 ++nconsvars; 1948 assert( nconsvars <= (int) mipdata->n ); 1949 1950 /* add linear constraint */ 1951 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "beta", nconsvars, consvars, consvals, 0.0, 0.0, 1952 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1953 SCIP_CALL( SCIPaddCons(subscip, cons) ); 1954 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 1955 ++mipdata->m; 1956 1957 /* add primal separation constraint if required */ 1958 if ( sepadata->primalseparation ) 1959 { 1960 SCIP_SOL* bestsol; 1961 bestsol = SCIPgetBestSol(origscip); 1962 if ( bestsol != NULL ) 1963 { 1964 nconsvars = 0; 1965 for (j = 0; j < ncols; ++j) 1966 { 1967 if ( mipdata->alpha[j] != NULL ) 1968 { 1969 SCIP_Real val; 1970 assert( mipdata->coltype[j] == colPresent ); 1971 1972 val = SCIPgetSolVal(origscip, bestsol, SCIPcolGetVar(cols[j])); 1973 consvars[nconsvars] = mipdata->alpha[j]; 1974 consvals[nconsvars] = val; 1975 ++nconsvars; 1976 assert( nconsvars <= (int) mipdata->n ); 1977 } 1978 } 1979 consvars[nconsvars] = mipdata->beta; 1980 consvals[nconsvars] = -1.0; 1981 ++nconsvars; 1982 1983 /* add linear constraint - allow slight deviation from equality */ 1984 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "primalseparation", nconsvars, consvars, consvals, -EPSILONVALUE, EPSILONVALUE, 1985 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1986 SCIP_CALL( SCIPaddCons(subscip, cons) ); 1987 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 1988 ++mipdata->m; 1989 } 1990 } 1991 1992 /* add constraint to force violated cuts if required */ 1993 if ( sepadata->addviolationcons ) 1994 { 1995 nconsvars = 0; 1996 for (j = 0; j < ncols; ++j) 1997 { 1998 if ( mipdata->alpha[j] != NULL ) 1999 { 2000 consvars[nconsvars] = mipdata->alpha[j]; 2001 consvals[nconsvars] = primsol[j]; 2002 ++nconsvars; 2003 assert( nconsvars <= (int) mipdata->n ); 2004 } 2005 } 2006 consvars[nconsvars] = mipdata->beta; 2007 consvals[nconsvars] = -1.0; 2008 ++nconsvars; 2009 2010 /* add linear constraint - allow slight deviation from equality */ 2011 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "violationConstraint", nconsvars, consvars, consvals, MINEFFICACY, SCIPinfinity(subscip), 2012 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 2013 SCIP_CALL( SCIPaddCons(subscip, cons) ); 2014 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 2015 ++mipdata->m; 2016 } 2017 2018 SCIPdebugMsg(origscip, "Subscip has %u vars (%d integral, %d continuous), %u conss.\n", 2019 mipdata->n, SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip), mipdata->m); 2020 2021 /* free temporary memory */ 2022 SCIPfreeBufferArray(origscip, &consvars); 2023 SCIPfreeBufferArray(origscip, &consvals); 2024 2025 SCIPfreeBufferArray(origscip, &primsol); 2026 SCIPfreeBufferArray(origscip, &lb); 2027 SCIPfreeBufferArray(origscip, &ub); 2028 2029 /* SCIPdebug( SCIP_CALL( SCIPprintOrigProblem(subscip, NULL, NULL, FALSE) ) ); */ 2030 2031 #ifdef SCIP_WRITEPROB 2032 { 2033 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.lp", 2034 sepadata->objlone ? "_l1" : "", 2035 sepadata->addviolationcons ? "_vc" : "", 2036 sepadata->skipmultbounds ? "_ub" : "", 2037 sepadata->primalseparation ? "_ps" : "", 2038 SCIPgetProbName(origscip)); 2039 SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) ); 2040 SCIPinfoMessage(origscip, NULL, "Wrote subscip to file <%s>.\n", name); 2041 } 2042 #endif 2043 2044 return SCIP_OKAY; 2045 } 2046 2047 2048 /** sets parameters for subscip */ 2049 static 2050 SCIP_RETCODE subscipSetParams( 2051 SCIP_SEPADATA* sepadata, /**< separator data */ 2052 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */ 2053 ) 2054 { 2055 SCIP* subscip; 2056 2057 assert( sepadata != NULL ); 2058 assert( mipdata != NULL ); 2059 2060 subscip = mipdata->subscip; 2061 assert( subscip != NULL ); 2062 2063 /* set objective limit, if no corresponding constraint has been added */ 2064 if ( ! sepadata->addviolationcons && ! sepadata->addviolconshdlr ) 2065 { 2066 SCIP_CALL( SCIPsetObjlimit(subscip, MINEFFICACY) ); 2067 } 2068 2069 /* do not abort subscip on CTRL-C */ 2070 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 2071 2072 /* disable memory saving mode: this is likely to result in the maximal depth being reached. This is because DFS 2073 * results in a repeated branching on the alpha-variables, which often have large bounds resulting in deep levels of 2074 * the tree. */ 2075 SCIP_CALL( SCIPsetRealParam(subscip, "memory/savefac", 1.0) ); 2076 2077 /* set number of solutions stored */ 2078 SCIP_CALL( SCIPsetIntParam(subscip, "limits/maxsol", MAXNSOLS) ); 2079 2080 /* determine output to console */ 2081 #ifdef SCIP_OUTPUT 2082 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 2083 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) ); 2084 SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) ); 2085 #else 2086 if ( sepadata->output ) 2087 { 2088 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 2089 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) ); 2090 SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) ); 2091 } 2092 else 2093 { 2094 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 2095 } 2096 #endif 2097 2098 if ( sepadata->subscipfast ) 2099 { 2100 /* forbid recursive call of plugins solving subMIPs (also disables CG-separation) */ 2101 #ifdef SCIP_OUTPUT 2102 SCIP_CALL( SCIPsetSubscipsOff(subscip, FALSE) ); 2103 #else 2104 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); /* quiet */ 2105 #endif 2106 } 2107 else 2108 { 2109 /* avoid recursive call */ 2110 if ( ! SCIPisParamFixed(subscip, "separating/cgmip/freq") ) 2111 { 2112 SCIP_CALL( SCIPsetIntParam(subscip, "separating/cgmip/freq", -1) ); 2113 } 2114 } 2115 2116 #ifdef SCIP_DISABLED_CODE 2117 /* the following possibly helps to improve performance (untested) */ 2118 SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) ); 2119 #else 2120 2121 /* zirounding is often successful, so allow it some more calls */ 2122 if ( ! SCIPisParamFixed(subscip, "heuristics/zirounding/minstopncalls") ) 2123 { 2124 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/zirounding/minstopncalls", 10000) ); 2125 } 2126 2127 if ( sepadata->subscipfast ) 2128 { 2129 /* set other heuristics */ 2130 if ( ! SCIPisParamFixed(subscip, "heuristics/shifting/freq") ) 2131 { 2132 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shifting/freq", 3) ); 2133 } 2134 if ( ! SCIPisParamFixed(subscip, "heuristics/simplerounding/freq") ) 2135 { 2136 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/simplerounding/freq", 1) ); 2137 } 2138 if ( ! SCIPisParamFixed(subscip, "heuristics/rounding/freq") ) 2139 { 2140 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rounding/freq", 1) ); 2141 } 2142 if ( ! SCIPisParamFixed(subscip, "heuristics/oneopt/freq") ) 2143 { 2144 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) ); 2145 } 2146 2147 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/pscostdiving/freq", 1) ); */ 2148 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", 3) ); */ 2149 2150 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/coefdiving/freq", -1) ); */ 2151 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) ); */ 2152 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/guideddiving/freq", -1) ); */ 2153 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/linesearchdiving/freq", -1) ); */ 2154 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/objpscostdiving/freq", -1) ); */ 2155 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rootsoldiving/freq", -1) ); */ 2156 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/veclendiving/freq", -1) ); */ 2157 2158 /* use fast presolving */ 2159 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 2160 2161 /* disable conflict analysis */ 2162 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) ); */ 2163 /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useinflp", 'o') ); */ 2164 /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); */ 2165 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) ); */ 2166 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) ); */ 2167 2168 /* use fast separation */ 2169 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 2170 } 2171 #endif 2172 2173 #ifdef SCIP_WRITEPROB 2174 { 2175 char name[SCIP_MAXSTRLEN]; 2176 2177 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.set", 2178 sepadata->objlone ? "_l1" : "", 2179 sepadata->addviolationcons ? "_vc" : "", 2180 sepadata->skipmultbounds ? "_ub" : "", 2181 sepadata->primalseparation ? "_ps" : "", 2182 SCIPgetProbName(mipdata->scip)); 2183 SCIP_CALL( SCIPwriteParams(subscip, name, TRUE, FALSE) ); 2184 SCIPinfoMessage(mipdata->scip, NULL, "Wrote settings to file <%s>.\n", name); 2185 } 2186 #endif 2187 2188 return SCIP_OKAY; 2189 } 2190 2191 2192 /** try to convert fractional gomory cuts to primal solutions of CG-MIP */ 2193 static 2194 SCIP_RETCODE createCGMIPprimalsols( 2195 SCIP* scip, /**< original SCIP data structure */ 2196 SCIP_SEPADATA* sepadata, /**< separator data */ 2197 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */ 2198 ) 2199 { 2200 SCIP_VAR** vars; 2201 SCIP_ROW** rows; 2202 SCIP_COL** cols; 2203 SCIP_Real* binvrow; 2204 SCIP_Real* cutcoefs; 2205 int* basisind; 2206 int nvars; 2207 int nrows; 2208 int ncols; 2209 int ngen = 0; 2210 int ntried = 0; 2211 int i; 2212 2213 assert( scip != NULL ); 2214 assert( sepadata != NULL ); 2215 assert( mipdata != NULL ); 2216 2217 /* get variables */ 2218 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 2219 2220 /* get rows and columns */ 2221 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 2222 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) ); 2223 assert( ncols <= nvars ); 2224 2225 /* get storage */ 2226 SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) ); 2227 SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) ); 2228 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) ); 2229 2230 /* get basis indices */ 2231 SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) ); 2232 2233 /* loop through rows */ 2234 for (i = 0; i < nrows; ++i) 2235 { 2236 SCIP_Bool tryrow = FALSE; 2237 SCIP_Real primsol = SCIP_INVALID; 2238 int c; 2239 int r; 2240 2241 c = basisind[i]; 2242 assert( c < ncols ); 2243 2244 if ( c >= 0 ) 2245 { 2246 SCIP_VAR* var; 2247 2248 var = SCIPcolGetVar(cols[c]); 2249 2250 if ( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ) 2251 { 2252 primsol = SCIPcolGetPrimsol(cols[c]); 2253 assert( SCIPgetVarSol(scip, var) == primsol ); /*lint !e777*/ 2254 2255 if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY ) 2256 tryrow = TRUE; 2257 } 2258 } 2259 #if ( SEPARATEROWS == TRUE ) 2260 else 2261 { 2262 SCIP_ROW* row; 2263 2264 assert(0 <= -c-1 && -c-1 < nrows); 2265 2266 row = rows[-c-1]; 2267 2268 if ( SCIProwIsIntegral(row) && ! SCIProwIsModifiable(row) ) 2269 { 2270 /* Compute value of the slack variable (we only care about the correct fractionality) */ 2271 if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) ) 2272 primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row); 2273 else 2274 primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row); 2275 2276 if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY ) 2277 tryrow = TRUE; 2278 } 2279 } 2280 #endif 2281 2282 if ( tryrow ) 2283 { 2284 SCIP_Bool success; 2285 SCIP_SOL* sol; 2286 SCIP_Real cutrhs = 0.0; 2287 SCIP_ROW* row; 2288 SCIP_Real val; 2289 int j; 2290 2291 assert( primsol != SCIP_INVALID ); /*lint !e777*/ 2292 2293 /* get the row of B^-1 for this basic integer variable with fractional solution value */ 2294 SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, NULL, NULL) ); 2295 2296 /* clear cutcoefs */ 2297 BMSclearMemoryArray(cutcoefs, ncols); 2298 2299 /* create solution */ 2300 SCIP_CALL( SCIPcreateSol(mipdata->subscip, &sol, NULL) ); 2301 2302 /* add values of multipliers to solution and compute coefficients */ 2303 for (r = 0; r < nrows; ++r) 2304 { 2305 SCIP_COL** rowcols; 2306 SCIP_Real* rowvals; 2307 SCIP_Real binvval; 2308 SCIP_Real weight; 2309 2310 row = rows[r]; 2311 assert( row != NULL ); 2312 2313 binvval = binvrow[r]; 2314 binvval = SCIPfrac(scip, binvval); /* can always take fractional value */ 2315 if ( ! SCIPisFeasZero(scip, binvval) ) 2316 { 2317 SCIP_Real lhs; 2318 SCIP_Real rhs; 2319 SCIP_Bool uselhs; 2320 2321 lhs = SCIProwGetLhs(row); 2322 rhs = SCIProwGetRhs(row); 2323 2324 if ( ! SCIPisEQ(scip, lhs, rhs) ) 2325 { 2326 SCIP_BASESTAT stat; 2327 2328 stat = SCIProwGetBasisStatus(row); 2329 2330 if ( stat == SCIP_BASESTAT_LOWER ) 2331 { 2332 assert( ! SCIPisInfinity(scip, -lhs) ); 2333 uselhs = TRUE; 2334 } 2335 else if ( stat == SCIP_BASESTAT_UPPER ) 2336 { 2337 assert( ! SCIPisInfinity(scip, rhs) ); 2338 uselhs = FALSE; 2339 } 2340 else if ( SCIPisInfinity(scip, rhs) ) 2341 uselhs = TRUE; 2342 else 2343 uselhs = FALSE; 2344 } 2345 else if ( binvval < 0.0 ) 2346 uselhs = TRUE; 2347 else 2348 uselhs = FALSE; 2349 2350 if ( uselhs ) 2351 { 2352 assert( mipdata->ylhs[r] != NULL ); 2353 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->ylhs[r], fabs(binvval)) ); 2354 weight = -fabs(binvval); 2355 } 2356 else 2357 { 2358 assert( mipdata->yrhs[r] != NULL ); 2359 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->yrhs[r], fabs(binvval)) ); 2360 weight = fabs(binvval); 2361 } 2362 2363 /* update cut coefficients */ 2364 rowcols = SCIProwGetCols(row); 2365 rowvals = SCIProwGetVals(row); 2366 2367 /* add the row coefficients to the sum */ 2368 for (j = 0; j < SCIProwGetNLPNonz(row); ++j) 2369 { 2370 int idx; 2371 2372 assert( rowcols[j] != NULL ); 2373 2374 idx = SCIPcolGetLPPos(rowcols[j]); 2375 assert( 0 <= idx && idx < ncols ); 2376 2377 cutcoefs[idx] += weight * rowvals[j]; 2378 } 2379 2380 /* compute rhs */ 2381 if ( uselhs ) 2382 { 2383 assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) ); 2384 val = mipdata->lhs[r]; 2385 } 2386 else 2387 { 2388 assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) ); 2389 val = mipdata->rhs[r]; 2390 } 2391 cutrhs += weight * val; 2392 } 2393 } 2394 2395 /* fill in values of cut */ 2396 for (c = 0; c < ncols; ++c) 2397 { 2398 if ( mipdata->coltype[c] != colPresent ) 2399 continue; 2400 2401 val = SCIPfloor(scip, cutcoefs[c]); 2402 if ( mipdata->iscomplemented[c] ) 2403 val = -val; 2404 if ( ! SCIPisFeasZero(scip, val) ) 2405 { 2406 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->alpha[c], val) ); 2407 } 2408 val = SCIPfeasFrac(scip, cutcoefs[c]); 2409 if ( ! SCIPisFeasZero(scip, val) ) 2410 { 2411 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracalpha[c], val) ); 2412 } 2413 } 2414 2415 if ( ! SCIPisFeasZero(scip, SCIPfloor(scip, cutrhs)) ) 2416 { 2417 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->beta, SCIPfloor(scip, cutrhs)) ); 2418 } 2419 if ( ! SCIPisFeasZero(scip, SCIPfeasFrac(scip, cutrhs)) ) 2420 { 2421 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracbeta, SCIPfeasFrac(scip, cutrhs)) ); 2422 } 2423 2424 SCIP_CALL( SCIPtrySolFree(mipdata->subscip, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 2425 ++ntried; 2426 if ( success ) 2427 ++ngen; 2428 } 2429 } 2430 2431 SCIPfreeBufferArray(scip, &cutcoefs); 2432 SCIPfreeBufferArray(scip, &binvrow); 2433 SCIPfreeBufferArray(scip, &basisind); 2434 2435 SCIPdebugMsg(scip, "Created %d primal solutions for CG-MIP from tableau cuts (tried: %d).\n", ngen, ntried); 2436 2437 return SCIP_OKAY; 2438 } 2439 2440 2441 /** solve subscip */ 2442 static 2443 SCIP_RETCODE solveSubscip( 2444 SCIP* origscip, /**< SCIP data structure */ 2445 SCIP_SEPADATA* sepadata, /**< separator data */ 2446 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 2447 SCIP_Bool* success /**< if setting was successful -> stop */ 2448 ) 2449 { 2450 SCIP* subscip; 2451 SCIP_RETCODE retcode; 2452 SCIP_STATUS status; 2453 SCIP_Real timelimit; 2454 SCIP_Real memorylimit; 2455 SCIP_Longint nodelimit; 2456 2457 assert( origscip != NULL ); 2458 assert( sepadata != NULL ); 2459 assert( mipdata != NULL ); 2460 assert( success != NULL ); 2461 2462 *success = TRUE; 2463 2464 subscip = mipdata->subscip; 2465 2466 SCIP_CALL( SCIPcheckCopyLimits(origscip, success) ); 2467 2468 if ( ! (*success) ) 2469 return SCIP_OKAY; 2470 2471 /* @todo Check whether copying the parameters is useful */ 2472 /* SCIP_CALL( SCIPcopyLimits(origscip, subscip) ); */ 2473 2474 /* determine time limit */ 2475 SCIP_CALL( SCIPgetRealParam(origscip, "limits/time", &timelimit) ); 2476 if ( sepadata->timelimit < timelimit ) 2477 timelimit = sepadata->timelimit; 2478 2479 if ( ! SCIPisInfinity(origscip, timelimit) ) 2480 { 2481 timelimit -= SCIPgetSolvingTime(origscip); 2482 if ( timelimit > 0.0 ) 2483 { 2484 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) ); 2485 } 2486 else 2487 { 2488 SCIPdebugMsg(origscip, "Reached timelimit.\n"); 2489 *success = FALSE; 2490 return SCIP_OKAY; 2491 } 2492 } 2493 2494 /* determine memory limit */ 2495 SCIP_CALL( SCIPgetRealParam(origscip, "limits/memory", &memorylimit) ); 2496 if ( sepadata->memorylimit < memorylimit ) 2497 memorylimit = sepadata->memorylimit; 2498 2499 if ( ! SCIPisInfinity(origscip, memorylimit) ) 2500 { 2501 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */ 2502 memorylimit -= SCIPgetMemUsed(origscip)/1048576.0; 2503 memorylimit -= SCIPgetMemExternEstim(origscip)/1048576.0; 2504 if ( memorylimit > 0.0 ) 2505 { 2506 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) ); 2507 } 2508 else 2509 { 2510 SCIPdebugMsg(origscip, "Reached memorylimit.\n"); 2511 *success = TRUE; 2512 return SCIP_OKAY; 2513 } 2514 } 2515 2516 /* set node limit for subproblem */ 2517 if ( sepadata->minnodelimit < 0 || sepadata->maxnodelimit < 0 ) 2518 nodelimit = SCIP_LONGINT_MAX; 2519 else 2520 { 2521 assert( sepadata->minnodelimit >= 0 && sepadata->maxnodelimit >= 0 ); 2522 nodelimit = SCIPgetNLPIterations(origscip); 2523 nodelimit = MAX(sepadata->minnodelimit, nodelimit); 2524 nodelimit = MIN(sepadata->maxnodelimit, nodelimit); 2525 } 2526 assert( nodelimit >= 0 ); 2527 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) ); 2528 2529 /* try to create primal solutions of CG-MIP problem via tableau cuts */ 2530 if ( sepadata->genprimalsols ) 2531 { 2532 SCIP_CALL( SCIPtransformProb(subscip) ); 2533 SCIP_CALL( createCGMIPprimalsols(origscip, sepadata, mipdata) ); 2534 } 2535 2536 SCIPdebugMsg(origscip, "Solving sub-SCIP (time limit: %f mem limit: %f node limit: %" SCIP_LONGINT_FORMAT ") ...\n", timelimit, memorylimit, nodelimit); 2537 2538 /* disable statistic timing inside sub SCIP */ 2539 if ( ! sepadata->output ) 2540 { 2541 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 2542 } 2543 2544 /* check whether we want a complete solve */ 2545 if ( ! sepadata->earlyterm ) 2546 { 2547 retcode = SCIPsolve(subscip); 2548 SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n", 2549 SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit); 2550 2551 /* errors in solving the subproblem should not kill the overall solving process; 2552 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */ 2553 if ( retcode != SCIP_OKAY ) 2554 { 2555 #ifndef NDEBUG 2556 SCIP_CALL( retcode ); 2557 #endif 2558 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode); 2559 *success = FALSE; 2560 return SCIP_OKAY; 2561 } 2562 2563 status = SCIPgetStatus(subscip); 2564 2565 #ifdef SCIP_OUTPUT 2566 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 2567 #else 2568 if ( sepadata->output ) 2569 { 2570 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 2571 } 2572 #endif 2573 2574 /* if the problem is infeasible (can happen because of violation constraint) */ 2575 if ( status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD ) 2576 { 2577 SCIPdebugMsg(origscip, "CG-MIP separation problem infeasible.\n"); 2578 *success = FALSE; 2579 return SCIP_OKAY; 2580 } 2581 2582 /* if the solution ran into the time limit */ 2583 if ( status == SCIP_STATUS_TIMELIMIT ) 2584 { 2585 SCIPdebugMsg(origscip, "CG-MIP separation problem ran into time limit.\n"); 2586 *success = FALSE; 2587 return SCIP_OKAY; 2588 } 2589 2590 /* if the solution process was terminated */ 2591 if ( status == SCIP_STATUS_USERINTERRUPT ) 2592 { 2593 SCIPdebugMsg(origscip, "CG-MIP separation problem stopped by user interrupt.\n"); 2594 *success = FALSE; 2595 return SCIP_OKAY; 2596 } 2597 2598 /* all other statuses except optimal or node limit are invalid */ 2599 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_NODELIMIT ) 2600 { 2601 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status); 2602 return SCIP_ERROR; 2603 } 2604 } 2605 else 2606 { 2607 /* otherwise we want a heuristic solve */ 2608 2609 /* -> solve until first solution is found */ 2610 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 1) ); 2611 retcode = SCIPsolve(subscip); 2612 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", -1) ); 2613 2614 /* errors in solving the subproblem should not kill the overall solving process; 2615 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */ 2616 if ( retcode != SCIP_OKAY ) 2617 { 2618 #ifndef NDEBUG 2619 SCIP_CALL( retcode ); 2620 #endif 2621 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode); 2622 *success = FALSE; 2623 return SCIP_OKAY; 2624 } 2625 2626 status = SCIPgetStatus(subscip); 2627 2628 /* if the solution process was terminated or the problem is infeasible (can happen because of violation constraint) */ 2629 if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_NODELIMIT || 2630 status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD || status == SCIP_STATUS_MEMLIMIT ) 2631 { 2632 /* output statistics before stopping */ 2633 #ifdef SCIP_OUTPUT 2634 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 2635 #else 2636 if ( sepadata->output ) 2637 { 2638 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 2639 } 2640 #endif 2641 *success = FALSE; 2642 return SCIP_OKAY; 2643 } 2644 2645 /* all other statuses except optimal or bestsollimit are invalid - (problem cannot be infeasible) */ 2646 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_BESTSOLLIMIT ) 2647 { 2648 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status); 2649 return SCIP_ERROR; 2650 } 2651 2652 /* solve some more, if a feasible solution was found */ 2653 if ( status == SCIP_STATUS_BESTSOLLIMIT ) 2654 { 2655 SCIPdebugMsg(origscip, "Continue solving separation problem (current time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ") ...\n", 2656 SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip)); 2657 2658 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", STALLNODELIMIT) ); 2659 retcode = SCIPsolve(subscip); 2660 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", -1LL) ); 2661 2662 SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n", 2663 SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit); 2664 2665 /* errors in solving the subproblem should not kill the overall solving process; 2666 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */ 2667 if ( retcode != SCIP_OKAY ) 2668 { 2669 #ifndef NDEBUG 2670 SCIP_CALL( retcode ); 2671 #endif 2672 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode); 2673 *success = FALSE; 2674 return SCIP_OKAY; 2675 } 2676 2677 status = SCIPgetStatus(subscip); 2678 assert( status != SCIP_STATUS_BESTSOLLIMIT ); 2679 2680 #ifdef SCIP_OUTPUT 2681 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 2682 #else 2683 if ( sepadata->output ) 2684 { 2685 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 2686 } 2687 #endif 2688 2689 /* if the solution process was terminated */ 2690 if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_MEMLIMIT ) 2691 { 2692 *success = FALSE; 2693 return SCIP_OKAY; 2694 } 2695 2696 /* all other statuses except optimal or bestsollimit are invalid */ 2697 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_STALLNODELIMIT && status != SCIP_STATUS_NODELIMIT ) 2698 { 2699 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status); 2700 return SCIP_ERROR; 2701 } 2702 } 2703 } 2704 2705 return SCIP_OKAY; 2706 } 2707 2708 /** Computes cut from the given multipliers 2709 * 2710 * When computing the cut, we take the fractional part of the multipliers. This is known to produce stronger cuts in 2711 * the pure integer case, since the cut is the sum of the one using fractional parts and integer multiples of the 2712 * original constraints. However, if there are continuous variables, the resulting cut might not be valid. This is 2713 * checked and returned. 2714 * 2715 * Moreover, the cut computed here in general will not be the same as the one computed with the 2716 * sub-MIP, because of numerical differences. Here, we only combine rows whose corresponding 2717 * multiplier is positive w.r.t. the feasibility tolerance. In the sub-MIP, however, the rows are 2718 * combined in any case. This makes a difference, if the coefficients in the matrix are large and 2719 * hence yield a value that is larger than the tolerance. 2720 * 2721 * Because of the transformations we have the following: 2722 * 2723 * If variable \f$x_j\f$ was complemented, we have \f$x'_j = u_j - x_j\f$. If in the transformed 2724 * system the lower bound is used, its corresponding multiplier is \f$y^T A'_j - \lfloor y^T A'_j 2725 * \rfloor\f$, which corresponds to 2726 * \f[ 2727 * y^T A'_j - \lfloor y^T A'_j \rfloor = - y^T A_j - \lfloor - y^T A_j \rfloor = - y^T A_j + \lceil y^T A_j \rceil 2728 * \f] 2729 * in the original system. 2730 * 2731 * If such a variable was at its upper bound before the transformation, it is at its lower bound 2732 * afterwards. Hence, its contribution to the cut is 0. 2733 * 2734 * Note that if the original LP-solution does not satisfy some of the rows with equality, the 2735 * violation of the cut might be smaller than what is computed with the reduced sub-MIP. 2736 * 2737 * Furthermore, note that if continuous variables have been shifted, the computed violation may be 2738 * different as well, because the necessary changes in the lhs/rhs are not used here anymore. 2739 * 2740 * @todo Check if cut is correct if continuous variables have been shifted. 2741 */ 2742 static 2743 SCIP_RETCODE computeCut( 2744 SCIP* scip, /**< original scip */ 2745 SCIP_SEPA* sepa, /**< separator */ 2746 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 2747 SCIP_SEPADATA* sepadata, /**< separator data */ 2748 SCIP_SOL* sol, /**< current solution for sub-MIP */ 2749 SCIP_Bool usefrac, /**< use fractional value of multipliers */ 2750 SCIP_Real* cutcoefs, /**< coefficients of the cut */ 2751 SCIP_Real* cutrhs, /**< rhs of the cut */ 2752 SCIP_Bool* localrowsused, /**< pointer to store whether local rows were used in summation */ 2753 SCIP_Bool* localboundsused, /**< pointer to store whether local bounds were used in summation */ 2754 int* cutrank, /**< pointer to store the cut rank */ 2755 SCIP_Bool* success /**< whether we produced a valid cut */ 2756 ) 2757 { 2758 SCIP* subscip; 2759 SCIP_VAR** vars; 2760 SCIP_ROW** rows; 2761 SCIP_COL** cols; 2762 SCIP_Real val; 2763 SCIP_Real maxabsweight; 2764 int nvars; 2765 int ncols; 2766 int nrows; 2767 int i; 2768 int j; 2769 2770 assert( scip != NULL ); 2771 assert( mipdata != NULL ); 2772 assert( sepadata != NULL ); 2773 assert( cutcoefs != NULL ); 2774 assert( cutrhs != NULL ); 2775 assert( localrowsused != NULL ); 2776 assert( localboundsused != NULL ); 2777 assert( cutrank != NULL ); 2778 assert( success != NULL ); 2779 2780 /* initialize */ 2781 *localrowsused = FALSE; 2782 *localboundsused = FALSE; 2783 *cutrank = 0; 2784 *success = TRUE; 2785 2786 subscip = mipdata->subscip; 2787 assert( subscip != NULL ); 2788 2789 /* get data */ 2790 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 2791 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 2792 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) ); 2793 assert( nrows == (int) mipdata->nrows ); 2794 assert( ncols == (int) mipdata->ncols ); 2795 2796 BMSclearMemoryArray(cutcoefs, nvars); 2797 *cutrhs = 0.0; 2798 2799 /* find maximal absolute weight */ 2800 maxabsweight = 0.0; 2801 for (i = 0; i < nrows; ++i) 2802 { 2803 SCIP_ROW* row; 2804 SCIP_Real absweight = 0.0; 2805 2806 row = rows[i]; 2807 assert( row != NULL ); 2808 2809 /* skip modifiable rows and local rows, unless allowed */ 2810 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) ) 2811 { 2812 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL ); 2813 continue; 2814 } 2815 2816 /* get weight from solution (take larger of the values of lhs/rhs) */ 2817 if ( mipdata->ylhs[i] != NULL ) 2818 { 2819 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]); 2820 2821 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 2822 if ( usefrac ) 2823 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 2824 2825 if ( SCIPisFeasPositive(scip, val) ) 2826 absweight = val; 2827 2828 assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa ); 2829 } 2830 if ( mipdata->yrhs[i] != NULL ) 2831 { 2832 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]); 2833 2834 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 2835 if ( usefrac ) 2836 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 2837 2838 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */ 2839 if ( SCIPisFeasGT(scip, val, absweight) ) 2840 absweight = val; 2841 2842 assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa ); 2843 } 2844 assert( ! SCIPisNegative(scip, absweight) ); 2845 2846 if ( absweight > maxabsweight ) 2847 maxabsweight = absweight; 2848 } 2849 2850 /* get weight from objective cuts */ 2851 if ( sepadata->useobjub || sepadata->useobjlb ) 2852 { 2853 SCIP_Real absweight = 0.0; 2854 2855 assert( mipdata->ntotalrows == mipdata->nrows + 1 ); 2856 2857 if ( mipdata->ylhs[mipdata->nrows] != NULL ) 2858 { 2859 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]); 2860 if ( usefrac ) 2861 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 2862 2863 if ( SCIPisFeasPositive(scip, val) ) 2864 absweight = val; 2865 } 2866 if ( mipdata->yrhs[mipdata->nrows] != NULL ) 2867 { 2868 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]); 2869 if ( usefrac ) 2870 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 2871 2872 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */ 2873 if ( SCIPisFeasGT(scip, val, absweight) ) 2874 absweight = val; 2875 } 2876 2877 if ( absweight > maxabsweight ) 2878 maxabsweight = absweight; 2879 } 2880 2881 /* calculate the row summation */ 2882 for (i = 0; i < nrows; ++i) 2883 { 2884 SCIP_ROW* row; 2885 SCIP_Real weight; 2886 SCIP_Real absweight; 2887 SCIP_Bool uselhs; 2888 2889 row = rows[i]; 2890 assert( row != NULL ); 2891 2892 /* skip modifiable rows and local rows, unless allowed */ 2893 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && ! sepadata->allowlocal) ) 2894 { 2895 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL ); 2896 continue; 2897 } 2898 2899 /* get weight from solution */ 2900 weight = 0.0; 2901 uselhs = FALSE; 2902 if ( mipdata->ylhs[i] != NULL ) 2903 { 2904 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]); 2905 assert( ! SCIPisFeasNegative(subscip, val) ); 2906 2907 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 2908 if ( usefrac ) 2909 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 2910 2911 if ( SCIPisFeasPositive(scip, val) ) 2912 { 2913 uselhs = TRUE; 2914 weight = -val; 2915 } 2916 } 2917 if ( mipdata->yrhs[i] != NULL ) 2918 { 2919 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]); 2920 assert( ! SCIPisFeasNegative(subscip, val) ); 2921 2922 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 2923 if ( usefrac ) 2924 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 2925 2926 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */ 2927 if ( SCIPisFeasGT(scip, val, REALABS(weight)) ) 2928 { 2929 uselhs = FALSE; 2930 weight = val; 2931 } 2932 } 2933 2934 /* add row if weight is nonzero and lies within range */ 2935 absweight = REALABS(weight); 2936 if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight ) 2937 { 2938 SCIP_COL** rowcols; 2939 SCIP_Real* rowvals; 2940 2941 rowcols = SCIProwGetCols(row); 2942 rowvals = SCIProwGetVals(row); 2943 2944 /* add the row coefficients to the sum */ 2945 for (j = 0; j < SCIProwGetNLPNonz(row); ++j) 2946 { 2947 SCIP_VAR* var; 2948 int idx; 2949 2950 assert( rowcols[j] != NULL ); 2951 var = SCIPcolGetVar(rowcols[j]); 2952 2953 assert( var != NULL ); 2954 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ); 2955 assert( SCIPvarGetCol(var) == rowcols[j] ); 2956 2957 idx = SCIPvarGetProbindex(var); 2958 assert( 0 <= idx && idx < nvars ); 2959 2960 cutcoefs[idx] += weight * rowvals[j]; 2961 } 2962 2963 /* compute rhs */ 2964 if ( uselhs ) 2965 { 2966 assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) ); 2967 val = SCIProwGetLhs(row) - SCIProwGetConstant(row); 2968 if ( SCIProwIsIntegral(row) ) 2969 val = SCIPfeasCeil(scip, val); /* row is integral: round left hand side up */ 2970 } 2971 else 2972 { 2973 assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) ); 2974 val = SCIProwGetRhs(row) - SCIProwGetConstant(row); 2975 if ( SCIProwIsIntegral(row) ) 2976 val = SCIPfeasFloor(scip, val); /* row is integral: round right hand side down */ 2977 } 2978 *cutrhs += weight * val; 2979 2980 *localrowsused = *localrowsused || SCIProwIsLocal(row); 2981 2982 if ( SCIProwGetRank(row) > *cutrank ) 2983 *cutrank = SCIProwGetRank(row); 2984 } 2985 } 2986 /* add 1 to cutrank */ 2987 ++(*cutrank); 2988 2989 /* get weight from objective bounds */ 2990 if ( sepadata->useobjub || sepadata->useobjlb ) 2991 { 2992 SCIP_Real weight = 0.0; 2993 SCIP_Bool uselhs = FALSE; 2994 SCIP_Real absweight; 2995 2996 assert( mipdata->ntotalrows == mipdata->nrows + 1 ); 2997 2998 if ( mipdata->ylhs[mipdata->nrows] != NULL ) 2999 { 3000 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]); 3001 assert( ! SCIPisFeasNegative(subscip, val) ); 3002 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 3003 if ( usefrac ) 3004 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 3005 3006 if ( SCIPisFeasPositive(scip, val) ) 3007 { 3008 uselhs = TRUE; 3009 weight = -val; 3010 } 3011 } 3012 if ( mipdata->yrhs[mipdata->nrows] != NULL ) 3013 { 3014 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]); 3015 assert( ! SCIPisFeasNegative(subscip, val) ); 3016 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 3017 if ( usefrac ) 3018 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 3019 3020 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */ 3021 if ( SCIPisFeasGT(scip, val, REALABS(weight)) ) 3022 { 3023 uselhs = FALSE; 3024 weight = val; 3025 } 3026 } 3027 3028 /* add objective row if weight is nonzero and lies within range */ 3029 absweight = REALABS(weight); 3030 if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight ) 3031 { 3032 SCIP_Real obj = 0.0; 3033 int idx; 3034 3035 /* add the objective row coefficients to the sum */ 3036 for (j = 0; j < ncols; ++j) 3037 { 3038 assert( cols[j] != NULL ); 3039 3040 obj = SCIPcolGetObj(cols[j]); 3041 if ( ! SCIPisZero(scip, obj) ) 3042 { 3043 idx = SCIPvarGetProbindex( SCIPcolGetVar(cols[j]) ); 3044 assert( 0 <= idx && idx < nvars ); 3045 cutcoefs[idx] += weight * obj; 3046 } 3047 } 3048 3049 /* compute rhs */ 3050 if ( uselhs ) 3051 { 3052 val = SCIPgetLowerbound(scip); 3053 assert( ! SCIPisInfinity(scip, -val) ); 3054 if ( SCIPisObjIntegral(scip) ) 3055 val = SCIPfeasCeil(scip, val); /* objective is integral: round left hand side up */ 3056 } 3057 else 3058 { 3059 val = SCIPgetUpperbound(scip); 3060 assert( ! SCIPisInfinity(scip, val) ); 3061 if ( SCIPisObjIntegral(scip) ) 3062 val = SCIPfeasFloor(scip, val); /* objective is integral: round right hand side down */ 3063 } 3064 *cutrhs += weight * val; 3065 } 3066 } 3067 3068 /* add upper bounds */ 3069 for (j = 0; j < ncols; ++j) 3070 { 3071 assert( cols[j] != NULL ); 3072 if ( mipdata->z[j] != NULL ) 3073 { 3074 assert( mipdata->coltype[j] == colPresent ); 3075 3076 val = SCIPgetSolVal(subscip, sol, mipdata->z[j]); 3077 assert( ! SCIPisFeasNegative(subscip, val) ); 3078 3079 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 3080 if ( usefrac ) 3081 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 3082 3083 /* if a bound has been used */ 3084 if ( SCIPisSumPositive(subscip, val) ) 3085 { 3086 SCIP_VAR* var; 3087 int idx; 3088 3089 var = SCIPcolGetVar(cols[j]); 3090 3091 assert( var != NULL ); 3092 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ); 3093 assert( SCIPvarIsIntegral(var) ); 3094 assert( SCIPvarGetCol(var) == cols[j] ); 3095 3096 idx = SCIPvarGetProbindex(var); 3097 assert( 0 <= idx && idx < nvars ); 3098 3099 /* check whether variable is complemented */ 3100 if ( mipdata->iscomplemented[j] ) 3101 { 3102 SCIP_Real lbnd; 3103 lbnd = SCIPvarGetLbGlobal(var); 3104 assert( ! SCIPisInfinity(scip, -lbnd) ); 3105 assert( SCIPisIntegral(scip, lbnd) ); 3106 assert( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPcolGetLb(cols[j])) ); 3107 3108 /* variable should not be free */ 3109 assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) ); 3110 3111 /* if allowed, try to use stronger local bound */ 3112 if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd ) 3113 { 3114 lbnd = SCIPvarGetLbLocal(var); 3115 assert( SCIPisIntegral(scip, lbnd) ); 3116 *localboundsused = TRUE; 3117 } 3118 3119 cutcoefs[idx] -= val; 3120 *cutrhs -= lbnd * val; 3121 } 3122 else 3123 { 3124 SCIP_Real ubnd; 3125 ubnd = SCIPvarGetUbGlobal(var); 3126 assert( ! SCIPisInfinity(scip, ubnd) ); 3127 assert( SCIPisIntegral(scip, ubnd) ); 3128 assert( SCIPisEQ(scip, SCIPvarGetUbLocal(var), SCIPcolGetUb(cols[j])) ); 3129 3130 /* if allowed, try to use stronger local bound */ 3131 if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd ) 3132 { 3133 ubnd = SCIPvarGetUbLocal(var); 3134 assert( SCIPisIntegral(scip, ubnd) ); 3135 *localboundsused = TRUE; 3136 } 3137 3138 cutcoefs[idx] += val; 3139 *cutrhs += ubnd * val; 3140 } 3141 } 3142 } 3143 } 3144 3145 /* check lower bounds for integral variables */ 3146 for (j = 0; j < nvars; ++j) 3147 { 3148 SCIP_VAR* var; 3149 int pos; 3150 3151 var = vars[j]; 3152 assert( var != NULL ); 3153 pos = SCIPcolGetLPPos(SCIPvarGetCol(var)); 3154 3155 /* a variable may have status COLUMN, but the corresponding column may not (yet) be in the LP */ 3156 if ( pos >= 0 && mipdata->coltype[pos] != colContinuous && mipdata->coltype[pos] != colConverted ) 3157 { 3158 assert( pos < ncols ); 3159 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ); 3160 assert( SCIPvarIsIntegral(var) ); 3161 3162 /* check whether variable is complemented */ 3163 if ( mipdata->iscomplemented[pos] ) 3164 { 3165 assert( ! mipdata->isshifted[pos] ); 3166 /* if the variable is complemented, the multiplier for the upper bound arises from the 3167 lower bound multiplier for the transformed problem - because of the minus-sign in the 3168 transformation this yields a round-up operation. */ 3169 val = SCIPfeasCeil(scip, cutcoefs[j]) - cutcoefs[j]; 3170 assert( ! SCIPisFeasNegative(scip, val) ); 3171 3172 /* only if variable needs to be rounded */ 3173 if ( SCIPisSumPositive(scip, val) ) 3174 { 3175 SCIP_Real ubnd; 3176 ubnd = SCIPvarGetUbGlobal(var); 3177 assert( ! SCIPisInfinity(scip, ubnd) ); 3178 assert( SCIPisIntegral(scip, ubnd) ); 3179 3180 /* variable should not be free */ 3181 assert( ! SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || ! SCIPisInfinity(scip, ubnd) ); 3182 3183 /* if allowed, try to use stronger local bound */ 3184 if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd ) 3185 { 3186 ubnd = SCIPvarGetUbLocal(var); 3187 assert( SCIPisIntegral(scip, ubnd) ); 3188 *localboundsused = TRUE; 3189 } 3190 3191 /* round cut coefficients, i.e., add val to cutcoefs[j] */ 3192 cutcoefs[j] = SCIPfeasCeil(scip, cutcoefs[j]); 3193 3194 /* correct rhs */ 3195 if ( ! SCIPisSumZero(scip, ubnd) ) 3196 *cutrhs += ubnd * val; 3197 } 3198 } 3199 else 3200 { 3201 /* compute multiplier for lower bound: */ 3202 val = cutcoefs[j] - SCIPfeasFloor(scip, cutcoefs[j]); 3203 assert( ! SCIPisFeasNegative(scip, val) ); 3204 3205 /* only if variable needs to be rounded */ 3206 if ( SCIPisSumPositive(scip, val) ) 3207 { 3208 SCIP_Real lbnd; 3209 lbnd = SCIPvarGetLbGlobal(var); 3210 assert( ! SCIPisInfinity(scip, -lbnd) ); 3211 assert( SCIPisIntegral(scip, lbnd) ); 3212 3213 /* variable should not be free */ 3214 assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) ); 3215 3216 /* if allowed, try to use stronger local bound */ 3217 if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd ) 3218 { 3219 lbnd = SCIPvarGetLbLocal(var); 3220 assert( SCIPisIntegral(scip, lbnd) ); 3221 *localboundsused = TRUE; 3222 } 3223 3224 /* round cut coefficients, i.e., subtract val from cutcoefs[j] */ 3225 cutcoefs[j] = SCIPfeasFloor(scip, cutcoefs[j]); 3226 3227 /* correct rhs */ 3228 if ( ! SCIPisSumZero(scip, lbnd) ) 3229 *cutrhs -= lbnd * val; 3230 } 3231 } 3232 } 3233 else 3234 { 3235 /* force coefficients of all continuous variables or of variables not in the lp to zero */ 3236 assert( pos == -1 || mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted ); 3237 3238 /* check whether all coefficients for continuous or converted variables are nonnegative */ 3239 if ( pos >= 0 ) 3240 { 3241 if ( SCIPisFeasNegative(scip, cutcoefs[j]) ) 3242 { 3243 *success = FALSE; 3244 break; 3245 } 3246 } 3247 3248 cutcoefs[j] = 0.0; 3249 } 3250 } 3251 3252 /* round rhs */ 3253 *cutrhs = SCIPfeasFloor(scip, *cutrhs); 3254 3255 return SCIP_OKAY; 3256 } 3257 3258 /** Create CG-cut directly from solution of sub-MIP */ 3259 static 3260 SCIP_RETCODE createCGCutDirect( 3261 SCIP* scip, /**< SCIP data structure */ 3262 SCIP_SEPA* sepa, /**< separator */ 3263 SCIP_SEPADATA* sepadata, /**< separator data */ 3264 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 3265 SCIP_SOL* sol, /**< solution of sub-MIP */ 3266 SCIP_Real* cutcoefs, /**< cut coefficients */ 3267 int* cutinds, /**< problem indices of variables appearing in cut */ 3268 SCIP_Real* cutvals, /**< values of variables in cut */ 3269 SCIP_Real* varsolvals, /**< solution value of variables */ 3270 SCIP_Real* weights, /**< weights to compute cmir cut */ 3271 int* nprevrows, /**< number of previously generated rows */ 3272 SCIP_ROW** prevrows, /**< previously generated rows */ 3273 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 3274 unsigned int* ngen /**< number of generated cuts */ 3275 ) 3276 { 3277 char name[SCIP_MAXSTRLEN]; 3278 SCIP_Bool cutislocal; 3279 SCIP_Bool localrowsused; 3280 SCIP_Bool localboundsused; 3281 SCIP_Real cutrhs; 3282 SCIP_Real cutact; 3283 SCIP_Bool success; 3284 SCIP_VAR** vars; 3285 int cutrank = 0; 3286 int nvars; 3287 int k; 3288 3289 assert( scip != NULL ); 3290 assert( sepadata != NULL ); 3291 assert( mipdata != NULL ); 3292 assert( sol != NULL ); 3293 assert( cutcoefs != NULL ); 3294 assert( cutinds != NULL ); 3295 assert( cutvals != NULL ); 3296 assert( varsolvals != NULL ); 3297 assert( weights != NULL ); 3298 assert( nprevrows != NULL ); 3299 assert( prevrows != NULL ); 3300 assert( cutoff != NULL ); 3301 assert( ngen != NULL ); 3302 3303 /* get variable data */ 3304 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 3305 3306 cutrhs = 0.0; 3307 localrowsused = FALSE; 3308 localboundsused = FALSE; 3309 *cutoff = FALSE; 3310 success = TRUE; 3311 3312 /* compute coefficients */ 3313 SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, TRUE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) ); 3314 cutislocal = localrowsused || localboundsused; 3315 3316 /* Take next solution if cut was not valid - this can easily happen for mixed-integer problems, see function computeCut(). */ 3317 if ( ! success ) 3318 { 3319 /* try again without using fractional value */ 3320 SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, FALSE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) ); 3321 cutislocal = localrowsused || localboundsused; 3322 3323 if ( ! success ) 3324 { 3325 SCIPdebugMsg(scip, "cut not valid - skipping ...\n"); 3326 return SCIP_OKAY; 3327 } 3328 } 3329 3330 /* compute activity */ 3331 cutact = 0.0; 3332 for (k = 0; k < nvars; ++k) 3333 cutact += cutcoefs[k] * varsolvals[k]; 3334 3335 #ifdef SCIP_DISABLED_CODE 3336 /* the following test should be treated with care because of numerical differences - see computeCut() */ 3337 { 3338 /* check for correctness of computed values */ 3339 SCIP* subscip; 3340 SCIP_Real obj = 0.0; 3341 SCIP_Real val; 3342 SCIP_Bool contVarShifted = FALSE; 3343 unsigned int j; 3344 SCIP_COL** cols; 3345 int ncols; 3346 3347 subscip = mipdata->subscip; 3348 assert( subscip != NULL ); 3349 3350 SCIP_CALL( SCIPprintSol(subscip, sol, NULL, FALSE) ); 3351 3352 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) ); 3353 for (j = 0; j < mipdata->ncols; ++j) 3354 { 3355 if ( mipdata->coltype[j] == colPresent ) 3356 { 3357 int idx; 3358 assert( mipdata->alpha[j] != NULL ); 3359 val = SCIPgetSolVal(subscip, sol, mipdata->alpha[j]); 3360 assert( SCIPisFeasIntegral(subscip, val) ); 3361 idx = SCIPvarGetProbindex(SCIPcolGetVar(cols[j])); 3362 assert( SCIPisFeasEQ(scip, val, cutcoefs[idx]) ); 3363 obj += val * SCIPvarGetObj(mipdata->alpha[j]); 3364 } 3365 else 3366 { 3367 if ( (mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted) && mipdata->isshifted[j] ) 3368 contVarShifted = TRUE; 3369 } 3370 } 3371 assert( mipdata->beta != NULL ); 3372 val = SCIPgetSolVal(subscip, sol, mipdata->beta); 3373 assert( SCIPisFeasIntegral(subscip, val) ); 3374 obj += val * SCIPvarGetObj(mipdata->beta); 3375 assert( contVarShifted || SCIPisFeasEQ(scip, obj, cutact - cutrhs) ); 3376 } 3377 #endif 3378 3379 /* if successful, convert dense cut into sparse row, and add the row as a cut */ 3380 if ( SCIPisFeasGT(scip, cutact, cutrhs) ) 3381 { 3382 SCIP_Real cutnorm; 3383 int cutlen; 3384 3385 /* store the cut as sparse row, calculate activity and norm of cut */ 3386 SCIP_CALL( storeCutInArrays(scip, nvars, cutcoefs, varsolvals, mipdata->normtype, 3387 cutinds, cutvals, &cutlen, &cutact, &cutnorm) ); 3388 3389 SCIPdebugMsg(scip, "act=%f, rhs=%f, norm=%f, eff=%f\n", cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm); 3390 3391 /* if norm is 0, the cut is trivial */ 3392 if ( SCIPisPositive(scip, cutnorm) ) 3393 { 3394 SCIP_Bool violated = SCIPisEfficacious(scip, (cutact - cutrhs)/cutnorm); 3395 3396 if ( violated || (sepadata->usecutpool && ! cutislocal ) ) 3397 { 3398 SCIP_ROW* cut; 3399 3400 /* create the cut */ 3401 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen); 3402 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) ); 3403 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 3404 3405 for (k = 0; k < cutlen; ++k) 3406 { 3407 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutvals[k]) ); 3408 } 3409 3410 /* set cut rank */ 3411 SCIProwChgRank(cut, cutrank); 3412 3413 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 3414 3415 /*SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );*/ 3416 3417 /* add cut to pool */ 3418 if ( ! cutislocal ) 3419 { 3420 assert( violated || sepadata->usecutpool ); 3421 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 3422 } 3423 3424 /* add cut if it is violated */ 3425 if ( violated ) 3426 { 3427 /* check whether cut has been found before - may happened due to projection */ 3428 for (k = 0; k < *nprevrows; ++k) 3429 { 3430 SCIP_Real parval; 3431 3432 assert( prevrows[k] != NULL ); 3433 parval = SCIProwGetParallelism(cut, prevrows[k], 'e'); 3434 /* exit if row is parallel to existing cut and rhs is not better */ 3435 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) ) 3436 break; 3437 } 3438 3439 /* if cut is new */ 3440 if ( k >= *nprevrows ) 3441 { 3442 prevrows[*nprevrows] = cut; 3443 ++(*nprevrows); 3444 3445 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n", 3446 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut), 3447 SCIPgetCutEfficacy(scip, NULL, cut), 3448 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut), 3449 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut)); 3450 #ifdef SCIP_DEBUG 3451 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3452 #else 3453 if ( sepadata->output ) 3454 { 3455 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3456 } 3457 #endif 3458 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) ); 3459 ++(*ngen); 3460 } 3461 else 3462 { 3463 SCIPdebugMsg(scip, "Cut already exists.\n"); 3464 /* release the row */ 3465 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3466 } 3467 } 3468 else 3469 { 3470 /* release the row */ 3471 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3472 } 3473 } 3474 } 3475 } 3476 3477 return SCIP_OKAY; 3478 } 3479 3480 3481 /** create CG-cut via CMIR-function */ 3482 static 3483 SCIP_RETCODE createCGCutCMIR( 3484 SCIP* scip, /**< SCIP data structure */ 3485 SCIP_SEPA* sepa, /**< separator */ 3486 SCIP_SEPADATA* sepadata, /**< separator data */ 3487 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 3488 SCIP_SOL* sol, /**< solution of sub-MIP */ 3489 SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */ 3490 SCIP_Real* cutcoefs, /**< cut coefficients */ 3491 int* cutinds, /**< problem indices of variables appearing in cut */ 3492 SCIP_Real* cutvals, /**< values of variables in cut */ 3493 SCIP_Real* varsolvals, /**< solution value of variables */ 3494 SCIP_Real* weights, /**< weights to compute cmir cut */ 3495 int* boundsfortrans, /**< bounds for cmir function of NULL */ 3496 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds for cmir function or NULL */ 3497 int* nprevrows, /**< number of previously generated rows */ 3498 SCIP_ROW** prevrows, /**< previously generated rows */ 3499 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 3500 unsigned int* ngen /**< number of generated cuts */ 3501 ) 3502 { 3503 char name[SCIP_MAXSTRLEN]; 3504 SCIP_Longint maxdnom; 3505 SCIP_Bool cutislocal; 3506 SCIP_Real maxscale; 3507 SCIP_Real cutrhs; 3508 SCIP_Real cutefficacy; 3509 SCIP_Bool success; 3510 SCIP_ROW** rows; 3511 SCIP_VAR** vars; 3512 SCIP* subscip; 3513 int nrows; 3514 int nvars; 3515 int k; 3516 int cutrank; 3517 int cutnnz; 3518 3519 assert( scip != NULL ); 3520 assert( sepadata != NULL ); 3521 assert( mipdata != NULL ); 3522 assert( sol != NULL ); 3523 assert( cutcoefs != NULL ); 3524 assert( cutinds != NULL ); 3525 assert( cutvals != NULL ); 3526 assert( varsolvals != NULL ); 3527 assert( weights != NULL ); 3528 assert( nprevrows != NULL ); 3529 assert( prevrows != NULL ); 3530 assert( cutoff != NULL ); 3531 assert( ngen != NULL ); 3532 3533 *cutoff = FALSE; 3534 subscip = mipdata->subscip; 3535 assert( subscip != NULL ); 3536 3537 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 3538 assert( nrows > 0 ); 3539 assert( (int) mipdata->nrows == nrows ); 3540 3541 /* @todo more advanced settings - compare sepa_gomory.c */ 3542 maxdnom = (SCIP_Longint) sepadata->cutcoefbnd+1; 3543 maxscale = 10000.0; 3544 3545 /* get variable data */ 3546 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 3547 3548 /* generate weights */ 3549 for (k = 0; k < nrows; ++k) 3550 { 3551 SCIP_Real val; 3552 3553 weights[k] = 0; 3554 if ( mipdata->ylhs[k] != NULL ) 3555 { 3556 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) ); 3557 3558 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]); 3559 assert( ! SCIPisFeasNegative(subscip, val) ); 3560 3561 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 3562 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 3563 3564 if ( SCIPisFeasPositive(subscip, val) ) 3565 weights[k] = -val; 3566 } 3567 3568 if ( mipdata->yrhs[k] != NULL ) 3569 { 3570 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) ); 3571 3572 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]); 3573 assert( ! SCIPisFeasNegative(subscip, val) ); 3574 3575 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 3576 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 3577 3578 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */ 3579 if ( SCIPisFeasGT(scip, val, ABS(weights[k])) ) 3580 weights[k] = val; 3581 } 3582 } 3583 3584 /* set up data for bounds to use */ 3585 if ( sepadata->cmirownbounds ) 3586 { 3587 int typefortrans; 3588 3589 assert( boundsfortrans != NULL ); 3590 assert( boundtypesfortrans != NULL ); 3591 3592 if ( sepadata->allowlocal ) 3593 typefortrans = -2; 3594 else 3595 typefortrans = -1; 3596 3597 /* check all variables */ 3598 for (k = 0; k < nvars; ++k) 3599 { 3600 int pos; 3601 SCIP_VAR* var; 3602 3603 var = vars[k]; 3604 assert( var != NULL ); 3605 pos = SCIPcolGetLPPos(SCIPvarGetCol(var)); 3606 3607 if ( pos < 0 ) 3608 continue; 3609 3610 assert( pos < (int) mipdata->ncols ); 3611 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ); 3612 3613 boundsfortrans[k] = typefortrans; 3614 boundtypesfortrans[k] = SCIP_BOUNDTYPE_LOWER; 3615 3616 if ( mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted ) 3617 { 3618 assert( SCIPvarIsIntegral(var) || mipdata->coltype[pos] != colContinuous ); 3619 continue; 3620 } 3621 3622 /* check upper bound */ 3623 if ( mipdata->z[pos] != NULL && SCIPisSumPositive(subscip, SCIPgetSolVal(subscip, sol, mipdata->z[pos])) ) 3624 { 3625 /* check whether variable is complemented */ 3626 if ( ! mipdata->iscomplemented[pos] ) 3627 boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER; 3628 /* otherwise use lower bound */ 3629 } 3630 else 3631 { 3632 /* check whether variable is complemented */ 3633 if ( mipdata->iscomplemented[pos] ) 3634 boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER; 3635 /* otherwise use lower bound */ 3636 } 3637 } 3638 } 3639 3640 /* create a MIR cut using the above calculated weights */ 3641 cutefficacy = -1.0; 3642 cutrhs = -1.0; 3643 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE, 3644 sepadata->allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) ); 3645 3646 if ( ! success ) 3647 return SCIP_OKAY; 3648 3649 SCIP_CALL( SCIPcalcMIR(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, sepadata->allowlocal, FIXINTEGRALRHS, boundsfortrans, 3650 boundtypesfortrans, MINFRAC, MAXFRAC, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, 3651 &cutrank, &cutislocal, &success) ); 3652 3653 assert( sepadata->allowlocal || !cutislocal ); 3654 SCIPdebugMsg(scip, "CMIR: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success, 3655 SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs); 3656 3657 /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is 3658 * not violated we might store non-local cuts in the pool. */ 3659 if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) ) 3660 { 3661 SCIP_ROW* cut; 3662 3663 /* create the cut */ 3664 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen); 3665 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) ); 3666 3667 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 3668 3669 for (k = 0; k < cutnnz; ++k) 3670 { 3671 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) ); 3672 } 3673 3674 assert( success ); 3675 3676 /* set cut rank */ 3677 SCIProwChgRank(cut, cutrank); 3678 3679 #ifdef SCIP_DEBUG 3680 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3681 #else 3682 if ( sepadata->output ) 3683 { 3684 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3685 } 3686 #endif 3687 3688 /* try to scale the cut to integral values */ 3689 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip), 3690 maxdnom, maxscale, MAKECONTINTEGRAL, &success) ); 3691 3692 /* if the cut could be made integral */ 3693 if ( success ) 3694 { 3695 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 3696 3697 /* add cut to pool */ 3698 if ( ! cutislocal ) 3699 { 3700 assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool ); 3701 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 3702 } 3703 3704 if ( ! SCIPisCutEfficacious(scip, NULL, cut) ) 3705 { 3706 SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n", 3707 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut), 3708 SCIPgetCutEfficacy(scip, NULL, cut)); 3709 3710 /* release the row */ 3711 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3712 } 3713 else 3714 { 3715 /* check whether cut has been found before - may happend due to projection */ 3716 for (k = 0; k < *nprevrows; ++k) 3717 { 3718 SCIP_Real parval; 3719 3720 assert( prevrows[k] != NULL ); 3721 parval = SCIProwGetParallelism(cut, prevrows[k], 'e'); 3722 /* exit if row is parallel to existing cut and rhs is not better */ 3723 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) ) 3724 break; 3725 } 3726 3727 /* if cut is new */ 3728 if ( k >= *nprevrows ) 3729 { 3730 prevrows[*nprevrows] = cut; 3731 ++(*nprevrows); 3732 3733 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n", 3734 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut), 3735 SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut), 3736 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut), 3737 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut)); 3738 #ifdef SCIP_OUTPUT 3739 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3740 #else 3741 if ( sepadata->output ) 3742 { 3743 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3744 } 3745 #endif 3746 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) ); 3747 ++(*ngen); 3748 } 3749 else 3750 { 3751 SCIPdebugMsg(scip, "Cut already exists.\n"); 3752 /* release the row */ 3753 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3754 } 3755 } 3756 } 3757 else 3758 { 3759 SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n", 3760 name, cutefficacy, cutrhs); 3761 3762 /* release the row */ 3763 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3764 } 3765 } 3766 3767 return SCIP_OKAY; 3768 } 3769 3770 3771 /** create CG-cut via strong-CG-function */ 3772 static 3773 SCIP_RETCODE createCGCutStrongCG( 3774 SCIP* scip, /**< SCIP data structure */ 3775 SCIP_SEPA* sepa, /**< separator */ 3776 SCIP_SEPADATA* sepadata, /**< separator data */ 3777 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 3778 SCIP_SOL* sol, /**< solution of sub-MIP */ 3779 SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */ 3780 SCIP_Real* cutcoefs, /**< cut coefficients */ 3781 int* cutinds, /**< problem indices of variables appearing in cut */ 3782 SCIP_Real* cutvals, /**< values of variables in cut */ 3783 SCIP_Real* varsolvals, /**< solution value of variables */ 3784 SCIP_Real* weights, /**< weights to compute cmir cut */ 3785 int* nprevrows, /**< number of previously generated rows */ 3786 SCIP_ROW** prevrows, /**< previously generated rows */ 3787 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 3788 unsigned int* ngen /**< number of generated cuts */ 3789 ) 3790 { 3791 char name[SCIP_MAXSTRLEN]; 3792 SCIP_Longint maxdnom; 3793 SCIP_Bool cutislocal; 3794 SCIP_Real maxscale; 3795 SCIP_Real cutrhs; 3796 SCIP_Real cutefficacy; 3797 SCIP_Bool success; 3798 SCIP_ROW** rows; 3799 SCIP_VAR** vars; 3800 SCIP* subscip; 3801 int nrows; 3802 int nvars; 3803 int k; 3804 int cutrank; 3805 int cutnnz; 3806 3807 assert( scip != NULL ); 3808 assert( sepadata != NULL ); 3809 assert( mipdata != NULL ); 3810 assert( sol != NULL ); 3811 assert( cutcoefs != NULL ); 3812 assert( cutinds != NULL ); 3813 assert( cutvals != NULL ); 3814 assert( varsolvals != NULL ); 3815 assert( weights != NULL ); 3816 assert( nprevrows != NULL ); 3817 assert( prevrows != NULL ); 3818 assert( cutoff != NULL ); 3819 assert( ngen != NULL ); 3820 3821 *cutoff = FALSE; 3822 subscip = mipdata->subscip; 3823 assert( subscip != NULL ); 3824 3825 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 3826 assert( nrows > 0 ); 3827 assert( (int) mipdata->nrows == nrows ); 3828 3829 /* @todo more advanced settings - compare sepa_gomory.c */ 3830 maxdnom = (SCIP_Longint) sepadata->cutcoefbnd + 1; 3831 maxscale = 10000.0; 3832 3833 /* get variable data */ 3834 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 3835 3836 /* generate weights */ 3837 for (k = 0; k < nrows; ++k) 3838 { 3839 SCIP_Real val; 3840 3841 weights[k] = 0; 3842 if ( mipdata->ylhs[k] != NULL ) 3843 { 3844 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) ); 3845 3846 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]); 3847 assert( ! SCIPisFeasNegative(subscip, val) ); 3848 3849 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 3850 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 3851 3852 if ( SCIPisFeasPositive(subscip, val) ) 3853 weights[k] = -val; 3854 } 3855 3856 if ( mipdata->yrhs[k] != NULL ) 3857 { 3858 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) ); 3859 3860 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]); 3861 assert( ! SCIPisFeasNegative(subscip, val) ); 3862 3863 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) ); 3864 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */ 3865 3866 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */ 3867 if ( SCIPisFeasGT(scip, val, ABS(weights[k])) ) 3868 weights[k] = val; 3869 } 3870 } 3871 3872 /* create a strong CG cut out of the weighted LP rows using the B^-1 row as weights */ 3873 cutefficacy = -1.0; 3874 cutrhs = -1.0; 3875 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE, 3876 sepadata->allowlocal, 1, (int) MAXAGGRLEN(nvars), &success) ); 3877 3878 if ( ! success ) 3879 return SCIP_OKAY; 3880 3881 SCIP_CALL( SCIPcalcStrongCG(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, sepadata->allowlocal, MINFRAC, MAXFRAC, 3882 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) ); 3883 3884 assert( sepadata->allowlocal || !cutislocal ); 3885 SCIPdebugMsg(scip, "Strong-CG: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success, 3886 SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs); 3887 3888 /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is 3889 * not violated we might store non-local cuts in the pool. */ 3890 if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) ) 3891 { 3892 SCIP_ROW* cut; 3893 3894 /* create the cut */ 3895 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen); 3896 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) ); 3897 3898 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 3899 3900 for (k = 0; k < cutnnz; ++k) 3901 { 3902 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) ); 3903 } 3904 3905 assert( success ); 3906 3907 /* set cut rank */ 3908 SCIProwChgRank(cut, cutrank); 3909 3910 #ifdef SCIP_DEBUG 3911 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3912 #else 3913 if ( sepadata->output ) 3914 { 3915 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3916 } 3917 #endif 3918 3919 /* try to scale the cut to integral values */ 3920 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip), 3921 maxdnom, maxscale, MAKECONTINTEGRAL, &success) ); 3922 3923 /* if the cut could be made integral */ 3924 if ( success ) 3925 { 3926 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 3927 3928 /* add cut to pool */ 3929 if ( ! cutislocal ) 3930 { 3931 assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool ); 3932 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 3933 } 3934 3935 if ( ! SCIPisCutEfficacious(scip, NULL, cut) ) 3936 { 3937 SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n", 3938 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut), 3939 SCIPgetCutEfficacy(scip, NULL, cut)); 3940 3941 /* release the row */ 3942 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3943 } 3944 else 3945 { 3946 /* check whether cut has been found before - may happend due to projection */ 3947 for (k = 0; k < *nprevrows; ++k) 3948 { 3949 SCIP_Real parval; 3950 3951 assert( prevrows[k] != NULL ); 3952 parval = SCIProwGetParallelism(cut, prevrows[k], 'e'); 3953 /* exit if row is parallel to existing cut and rhs is not better */ 3954 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) ) 3955 break; 3956 } 3957 3958 /* if cut is new */ 3959 if ( k >= *nprevrows ) 3960 { 3961 prevrows[*nprevrows] = cut; 3962 ++(*nprevrows); 3963 3964 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n", 3965 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut), 3966 SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut), 3967 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut), 3968 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut)); 3969 #ifdef SCIP_OUTPUT 3970 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3971 #else 3972 if ( sepadata->output ) 3973 { 3974 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 3975 } 3976 #endif 3977 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) ); 3978 ++(*ngen); 3979 } 3980 else 3981 { 3982 SCIPdebugMsg(scip, "Cut already exists.\n"); 3983 /* release the row */ 3984 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3985 } 3986 } 3987 } 3988 else 3989 { 3990 SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n", 3991 name, cutefficacy, cutrhs); 3992 3993 /* release the row */ 3994 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 3995 } 3996 } 3997 3998 return SCIP_OKAY; 3999 } 4000 4001 4002 /** Create CG-cuts from solutions of sub-MIP */ 4003 static 4004 SCIP_RETCODE createCGCuts( 4005 SCIP* scip, /**< SCIP data structure */ 4006 SCIP_SEPA* sepa, /**< separator */ 4007 SCIP_SEPADATA* sepadata, /**< separator data */ 4008 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */ 4009 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 4010 unsigned int* ngen /**< number of generated cuts */ 4011 ) 4012 { 4013 SCIP_BOUNDTYPE* boundtypesfortrans; 4014 SCIP_STAGE stage; 4015 SCIP_AGGRROW* aggrrow = NULL; 4016 SCIP_Real* varsolvals; 4017 SCIP_Real* weights; 4018 int* cutinds; 4019 SCIP_Real* cutvals; 4020 SCIP_Real* cutcoefs; 4021 SCIP_ROW** prevrows; 4022 SCIP_SOL** sols; 4023 SCIP_VAR** vars; 4024 SCIP* subscip; 4025 int* boundsfortrans; 4026 int nprevrows; 4027 int ntotalrows; 4028 int nsols; 4029 int nvars; 4030 int k; 4031 int s; 4032 4033 assert( scip != NULL ); 4034 assert( sepadata != NULL ); 4035 assert( mipdata != NULL ); 4036 assert( cutoff != NULL ); 4037 assert( ngen != NULL ); 4038 4039 subscip = mipdata->subscip; 4040 assert( subscip != NULL ); 4041 4042 *cutoff = FALSE; 4043 *ngen = 0; 4044 4045 /* check if solving was successful and get solutions */ 4046 stage = SCIPgetStage(subscip); 4047 if ( stage == SCIP_STAGE_SOLVING || stage == SCIP_STAGE_SOLVED ) 4048 nsols = SCIPgetNSols(subscip); 4049 else 4050 nsols = 0; 4051 4052 /* only if solutions have been found */ 4053 if ( nsols == 0 ) 4054 return SCIP_OKAY; 4055 4056 SCIPdebugMsg(scip, "Generating CG-cuts from %d sols (cmir: %u, strong-cg: %u) ...\n", nsols, sepadata->usecmir, sepadata->usestrongcg); 4057 4058 sols = SCIPgetSols(subscip); 4059 4060 /* get variable data */ 4061 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 4062 4063 /* allocate temporary memory */ 4064 assert(mipdata->ntotalrows <= INT_MAX); 4065 ntotalrows = (int)mipdata->ntotalrows; 4066 assert( ntotalrows >= SCIPgetNLPRows(scip) && ntotalrows <= SCIPgetNLPRows(scip) + 1 ); 4067 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) ); 4068 SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) ); 4069 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) ); 4070 SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars) ); 4071 SCIP_CALL( SCIPallocBufferArray(scip, &weights, ntotalrows) ); 4072 SCIP_CALL( SCIPallocBufferArray(scip, &prevrows, 2 * nsols) ); 4073 4074 if ( sepadata->usecmir || sepadata->usestrongcg ) 4075 { 4076 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) ); 4077 } 4078 4079 /* prepare arrays for bound information, if requested */ 4080 if ( sepadata->usecmir && sepadata->cmirownbounds ) 4081 { 4082 SCIP_CALL( SCIPallocBufferArray(scip, &boundsfortrans, nvars) ); 4083 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesfortrans, nvars) ); 4084 } 4085 else 4086 { 4087 boundsfortrans = NULL; 4088 boundtypesfortrans = NULL; 4089 } 4090 4091 /* get solution values */ 4092 for (k = 0; k < nvars; ++k) 4093 { 4094 if ( SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_COLUMN ) 4095 varsolvals[k] = SCIPvarGetLPSol(vars[k]); 4096 else 4097 varsolvals[k] = 0.0; 4098 } 4099 4100 /* loop through solutions found */ 4101 nprevrows = 0; 4102 for (s = 0; s < nsols; ++s) 4103 { 4104 SCIP_SOL* sol; 4105 sol = sols[s]; 4106 4107 /* generate cuts by the C-MIR and/or Strong-CG functions */ 4108 if ( sepadata->usecmir ) 4109 { 4110 SCIP_CALL( createCGCutCMIR(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights, 4111 boundsfortrans, boundtypesfortrans, &nprevrows, prevrows, cutoff, ngen) ); 4112 } 4113 4114 if ( sepadata->usestrongcg ) 4115 { 4116 SCIP_CALL( createCGCutStrongCG(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights, 4117 &nprevrows, prevrows, cutoff, ngen) ); 4118 } 4119 4120 if ( ! sepadata->usecmir && ! sepadata->usestrongcg ) 4121 { 4122 SCIP_CALL( createCGCutDirect(scip, sepa, sepadata, mipdata, sol, cutcoefs, cutinds, cutvals, varsolvals, weights, 4123 &nprevrows, prevrows, cutoff, ngen) ); 4124 4125 assert(! sepadata->usecmir && ! sepadata->usestrongcg); 4126 } 4127 } 4128 assert( nprevrows <= 2 * nsols ); 4129 assert( sepadata->usecmir || nprevrows <= nsols ); 4130 assert( sepadata->usestrongcg || nprevrows <= nsols ); 4131 4132 /* release rows */ 4133 for (k = 0; k < nprevrows; ++k) 4134 { 4135 SCIP_CALL( SCIPreleaseRow(scip, &(prevrows[k])) ); 4136 } 4137 4138 if ( sepadata->usecmir || sepadata->usestrongcg ) 4139 SCIPaggrRowFree(scip, &aggrrow); 4140 4141 /* free temporary memory */ 4142 SCIPfreeBufferArrayNull(scip, &boundsfortrans); 4143 SCIPfreeBufferArrayNull(scip, &boundtypesfortrans); 4144 4145 SCIPfreeBufferArray(scip, &prevrows); 4146 SCIPfreeBufferArray(scip, &weights); 4147 SCIPfreeBufferArray(scip, &cutvals); 4148 SCIPfreeBufferArray(scip, &cutinds); 4149 SCIPfreeBufferArray(scip, &varsolvals); 4150 SCIPfreeBufferArray(scip, &cutcoefs); 4151 4152 return SCIP_OKAY; 4153 } 4154 4155 4156 /** frees "subscip" data */ 4157 static 4158 SCIP_RETCODE freeSubscip( 4159 SCIP* scip, /**< SCIP data structure */ 4160 SCIP_SEPA* sepa, /**< separator data */ 4161 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */ 4162 ) 4163 { 4164 SCIP_SEPADATA* sepadata; 4165 unsigned int i, j; 4166 SCIP* subscip; 4167 4168 assert( scip != NULL ); 4169 assert( sepa != NULL ); 4170 assert( mipdata != NULL ); 4171 4172 /* free separator data */ 4173 sepadata = SCIPsepaGetData(sepa); 4174 assert( sepadata != NULL ); 4175 4176 SCIPdebugMsg(scip, "Freeing subscip ...\n"); 4177 4178 subscip = mipdata->subscip; 4179 assert( subscip != NULL ); 4180 4181 for (j = 0; j < mipdata->ncols; ++j) 4182 { 4183 if ( mipdata->coltype[j] == colPresent ) 4184 { 4185 assert( mipdata->alpha[j] != NULL ); 4186 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->alpha[j])) ); 4187 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracalpha[j])) ); 4188 } 4189 } 4190 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->beta)) ); 4191 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracbeta)) ); 4192 4193 for (i = 0; i < mipdata->nrows; ++i) 4194 { 4195 if ( mipdata->ylhs[i] != NULL ) 4196 { 4197 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[i])) ); 4198 } 4199 if ( mipdata->yrhs[i] != NULL ) 4200 { 4201 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[i])) ); 4202 } 4203 } 4204 4205 if ( sepadata->useobjub || sepadata->useobjlb ) 4206 { 4207 if ( mipdata->yrhs[mipdata->nrows] ) 4208 { 4209 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[mipdata->nrows])) ); 4210 } 4211 if ( mipdata->ylhs[mipdata->nrows] ) 4212 { 4213 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[mipdata->nrows])) ); 4214 } 4215 } 4216 4217 for (j = 0; j < mipdata->ncols; ++j) 4218 { 4219 if ( mipdata->z[j] != NULL ) 4220 { 4221 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->z[j])) ); 4222 } 4223 } 4224 4225 SCIP_CALL( SCIPfree(&(mipdata->subscip)) ); 4226 4227 SCIPfreeBlockMemoryArray(scip, &(mipdata->rhs), mipdata->ntotalrows); 4228 SCIPfreeBlockMemoryArray(scip, &(mipdata->lhs), mipdata->ntotalrows); 4229 SCIPfreeBlockMemoryArray(scip, &(mipdata->z), 2*mipdata->ncols); /*lint !e647*/ 4230 SCIPfreeBlockMemoryArray(scip, &(mipdata->yrhs), mipdata->ntotalrows); 4231 SCIPfreeBlockMemoryArray(scip, &(mipdata->ylhs), mipdata->ntotalrows); 4232 SCIPfreeBlockMemoryArray(scip, &(mipdata->isshifted), mipdata->ncols); 4233 SCIPfreeBlockMemoryArray(scip, &(mipdata->iscomplemented), mipdata->ncols); 4234 SCIPfreeBlockMemoryArray(scip, &(mipdata->coltype), mipdata->ncols); 4235 SCIPfreeBlockMemoryArray(scip, &(mipdata->fracalpha), mipdata->ncols); 4236 SCIPfreeBlockMemoryArray(scip, &(mipdata->alpha), mipdata->ncols); 4237 4238 return SCIP_OKAY; 4239 } 4240 4241 4242 /* 4243 * Callback methods 4244 */ 4245 4246 4247 /** initialization method of separator (called after problem was transformed) */ 4248 static 4249 SCIP_DECL_SEPAINIT(sepaInitCGMIP) 4250 { 4251 SCIP_SEPADATA* sepadata; 4252 4253 sepadata = SCIPsepaGetData(sepa); 4254 assert(sepadata != NULL); 4255 4256 /* create and initialize random number generator */ 4257 SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, DEFAULT_RANDSEED, TRUE) ); 4258 4259 return SCIP_OKAY; 4260 } 4261 4262 /** deinitialization method of separator (called before transformed problem is freed) */ 4263 static 4264 SCIP_DECL_SEPAEXIT(sepaExitCGMIP) 4265 { /*lint --e{715}*/ 4266 SCIP_SEPADATA* sepadata; 4267 4268 sepadata = SCIPsepaGetData(sepa); 4269 assert(sepadata != NULL); 4270 4271 SCIPfreeRandom(scip, &sepadata->randnumgen); 4272 4273 return SCIP_OKAY; 4274 } 4275 4276 /** copy method for separator plugins (called when SCIP copies plugins) */ 4277 static 4278 SCIP_DECL_SEPACOPY(sepaCopyCGMIP) 4279 { /*lint --e{715}*/ 4280 assert( scip != NULL ); 4281 assert( sepa != NULL ); 4282 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 4283 4284 /* call inclusion method of constraint handler */ 4285 SCIP_CALL( SCIPincludeSepaCGMIP(scip) ); 4286 4287 return SCIP_OKAY; 4288 } 4289 4290 4291 /** destructor of separator to free user data (called when SCIP is exiting) */ 4292 static 4293 SCIP_DECL_SEPAFREE(sepaFreeCGMIP) 4294 { /*lint --e{715}*/ 4295 SCIP_SEPADATA* sepadata; 4296 4297 assert( scip != NULL ); 4298 assert( sepa != NULL ); 4299 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 4300 4301 /* free separator data */ 4302 sepadata = SCIPsepaGetData(sepa); 4303 assert( sepadata != NULL ); 4304 4305 SCIPfreeBlockMemory(scip, &sepadata); 4306 4307 SCIPsepaSetData(sepa, NULL); 4308 4309 return SCIP_OKAY; 4310 } 4311 4312 4313 /** LP solution separation method of separator */ 4314 static 4315 SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP) 4316 { /*lint --e{715}*/ 4317 SCIP_SEPADATA* sepadata; 4318 CGMIP_MIPDATA* mipdata; 4319 4320 int ncalls; 4321 int ncols; 4322 int nrows; 4323 unsigned int ngen = 0; 4324 SCIP_Bool success; 4325 SCIP_Bool cutoff = FALSE; 4326 4327 assert( scip != NULL ); 4328 assert( sepa != NULL ); 4329 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 4330 assert( result != NULL ); 4331 4332 *result = SCIP_DIDNOTRUN; 4333 4334 sepadata = SCIPsepaGetData(sepa); 4335 assert(sepadata != NULL); 4336 4337 /* only call separator, if we are not close to terminating */ 4338 if ( SCIPisStopped(scip) ) 4339 return SCIP_OKAY; 4340 4341 /* only call separator up to a maximum depth */ 4342 if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth ) 4343 return SCIP_OKAY; 4344 4345 /* only call separator a given number of times at each node */ 4346 ncalls = SCIPsepaGetNCallsAtNode(sepa); 4347 if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) 4348 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) ) 4349 return SCIP_OKAY; 4350 4351 /* only call separator, if an optimal LP solution is at hand */ 4352 if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 4353 return SCIP_OKAY; 4354 4355 /* skip separation if there are continuous variables, but only integers required */ 4356 if ( SCIPgetNContVars(scip) > 0 && sepadata->onlyintvars ) 4357 return SCIP_OKAY; 4358 4359 /* only call separator, if there are fractional variables */ 4360 if ( SCIPgetNLPBranchCands(scip) == 0 ) 4361 return SCIP_OKAY; 4362 4363 /* check for parameters */ 4364 if ( ( sepadata->useobjub || sepadata->useobjlb ) && ( sepadata->usecmir || sepadata->usestrongcg ) ) 4365 { 4366 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, 4367 "WARNING - sepa_cgmip: Using objective function bounds and CMIR or Strong-CG functions is useless. Turning off usage of objective function bounds.\n"); 4368 SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjub", FALSE) ); 4369 SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjlb", FALSE) ); 4370 } 4371 sepadata->allowlocal = allowlocal; 4372 4373 /* get LP data */ 4374 ncols = SCIPgetNLPCols(scip); 4375 nrows = SCIPgetNLPRows(scip); 4376 if ( ncols <= NCOLSTOOSMALL || nrows <= NROWSTOOSMALL ) 4377 return SCIP_OKAY; 4378 4379 /* determine whether we should run the separation based on a decision tree */ 4380 if ( sepadata->decisiontree ) 4381 { 4382 SCIP_Bool separate; 4383 SCIP_Real firstlptime; 4384 4385 separate = FALSE; 4386 firstlptime = SCIPgetFirstLPTime(scip); 4387 4388 if ( nrows <= 136 && firstlptime <= 0.05 && ncols <= 143 ) 4389 separate = TRUE; 4390 else if ( nrows <= 136 && 0.05 < firstlptime && firstlptime <= 0.15 && ncols <= 143 ) 4391 separate = TRUE; 4392 else if ( 136 < nrows && nrows <= 332 && ncols <= 143 ) 4393 separate = TRUE; 4394 else if ( 136 < nrows && nrows <= 332 && 655 < ncols && ncols <= 1290 ) 4395 separate = TRUE; 4396 else if ( 333 < nrows && nrows <= 874 && 0.15 < firstlptime && firstlptime <= 0.25 && 2614 < ncols && ncols <= 5141 ) 4397 separate = TRUE; 4398 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 143 < ncols && ncols <= 265 ) 4399 separate = TRUE; 4400 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 265 < ncols && ncols <= 654 ) 4401 separate = TRUE; 4402 else if ( 875 < nrows && nrows <= 1676 && 0.05 < firstlptime && firstlptime <= 0.15 ) 4403 separate = TRUE; 4404 else if ( 875 < nrows && nrows <= 1676 && 0.15 < firstlptime && firstlptime <= 0.25 && 1291 < ncols && ncols <= 2613 ) 4405 separate = TRUE; 4406 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 655 < ncols && ncols <= 1290 ) 4407 separate = TRUE; 4408 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 1291 < ncols && ncols <= 2613 ) 4409 separate = TRUE; 4410 else if ( nrows > 8146 && firstlptime > 6.25 ) 4411 separate = TRUE; 4412 4413 if ( ! separate ) 4414 { 4415 return SCIP_OKAY; 4416 } 4417 } 4418 4419 /* preceed with separation */ 4420 *result = SCIP_DIDNOTFIND; 4421 4422 SCIPdebugMsg(scip, "separating CG-cuts via sub-MIPs: %d cols, %d rows\n", ncols, nrows); 4423 4424 /* prepare data */ 4425 SCIP_CALL( SCIPallocBlockMemory(scip, &mipdata) ); 4426 mipdata->subscip = NULL; 4427 mipdata->alpha = NULL; 4428 mipdata->fracalpha = NULL; 4429 mipdata->beta = NULL; 4430 mipdata->fracbeta = NULL; 4431 mipdata->coltype = NULL; 4432 mipdata->iscomplemented = NULL; 4433 mipdata->isshifted = NULL; 4434 mipdata->ylhs = NULL; 4435 mipdata->yrhs = NULL; 4436 mipdata->z = NULL; 4437 mipdata->lhs = NULL; 4438 mipdata->rhs = NULL; 4439 mipdata->normtype = ' '; 4440 4441 mipdata->conshdlrfullnorm = CONSHDLRFULLNORM; 4442 mipdata->scip = scip; 4443 mipdata->sepa = sepa; 4444 mipdata->sepadata = sepadata; 4445 4446 /* get the type of norm to use for efficacy calculations */ 4447 SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &mipdata->normtype) ); 4448 4449 /* create subscip */ 4450 SCIP_CALL( createSubscip(scip, sepa, sepadata, mipdata) ); 4451 4452 /* set parameters */ 4453 SCIP_CALL( subscipSetParams(sepadata, mipdata) ); 4454 4455 if ( ! SCIPisStopped(scip) ) 4456 { 4457 /* solve subscip */ 4458 SCIP_CALL( solveSubscip(scip, sepadata, mipdata, &success) ); 4459 4460 /* preceed if solution was successful */ 4461 if ( success && ! SCIPisStopped(scip) ) 4462 { 4463 SCIP_CALL( createCGCuts(scip, sepa, sepadata, mipdata, &cutoff, &ngen) ); 4464 } 4465 } 4466 4467 SCIP_CALL( freeSubscip(scip, sepa, mipdata) ); 4468 SCIPfreeBlockMemory(scip, &mipdata); 4469 4470 SCIPdebugMsg(scip, "Found %u CG-cuts.\n", ngen); 4471 4472 if ( cutoff ) 4473 *result = SCIP_CUTOFF; 4474 else if ( ngen > 0 ) 4475 *result = SCIP_SEPARATED; 4476 4477 #ifdef SCIP_OUTPUT 4478 /* SCIP_CALL( SCIPwriteLP(scip, "cuts.lp") ); */ 4479 /* SCIP_CALL( SCIPwriteMIP(scip, "cuts.lp", FALSE, TRUE) ); */ 4480 #endif 4481 4482 return SCIP_OKAY; 4483 } 4484 4485 /* 4486 * separator specific interface methods 4487 */ 4488 4489 /** creates the CGMIP MIR cut separator and includes it in SCIP */ 4490 SCIP_RETCODE SCIPincludeSepaCGMIP( 4491 SCIP* scip /**< SCIP data structure */ 4492 ) 4493 { 4494 SCIP_SEPADATA* sepadata; 4495 SCIP_SEPA* sepa = NULL; 4496 4497 /* create separator data */ 4498 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 4499 4500 /* include separator */ 4501 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 4502 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpCGMIP, NULL, sepadata) ); 4503 assert(sepa != NULL); 4504 4505 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyCGMIP) ); 4506 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeCGMIP) ); 4507 SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitCGMIP) ); 4508 SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitCGMIP) ); 4509 4510 /* add separator parameters */ 4511 SCIP_CALL( SCIPaddIntParam(scip, 4512 "separating/" SEPA_NAME "/maxrounds", 4513 "maximal number of cgmip separation rounds per node (-1: unlimited)", 4514 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) ); 4515 4516 SCIP_CALL( SCIPaddIntParam(scip, 4517 "separating/" SEPA_NAME "/maxroundsroot", 4518 "maximal number of cgmip separation rounds in the root node (-1: unlimited)", 4519 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) ); 4520 4521 SCIP_CALL( SCIPaddIntParam(scip, 4522 "separating/" SEPA_NAME "/maxdepth", 4523 "maximal depth at which the separator is applied (-1: unlimited)", 4524 &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) ); 4525 4526 SCIP_CALL( SCIPaddBoolParam(scip, 4527 "separating/" SEPA_NAME "/decisiontree", 4528 "Use decision tree to turn separation on/off?", 4529 &sepadata->decisiontree, FALSE, DEFAULT_DECISIONTREE, NULL, NULL) ); 4530 4531 SCIP_CALL( SCIPaddRealParam(scip, 4532 "separating/" SEPA_NAME "/timelimit", 4533 "time limit for sub-MIP", 4534 &sepadata->timelimit, TRUE, DEFAULT_TIMELIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 4535 4536 SCIP_CALL( SCIPaddRealParam(scip, 4537 "separating/" SEPA_NAME "/memorylimit", 4538 "memory limit for sub-MIP", 4539 &sepadata->memorylimit, TRUE, DEFAULT_MEMORYLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 4540 4541 SCIP_CALL( SCIPaddLongintParam(scip, 4542 "separating/" SEPA_NAME "/minnodelimit", 4543 "minimum number of nodes considered for sub-MIP (-1: unlimited)", 4544 &sepadata->minnodelimit, FALSE, DEFAULT_MINNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) ); 4545 4546 SCIP_CALL( SCIPaddLongintParam(scip, 4547 "separating/" SEPA_NAME "/maxnodelimit", 4548 "maximum number of nodes considered for sub-MIP (-1: unlimited)", 4549 &sepadata->maxnodelimit, FALSE, DEFAULT_MAXNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) ); 4550 4551 SCIP_CALL( SCIPaddRealParam(scip, 4552 "separating/" SEPA_NAME "/cutcoefbnd", 4553 "bounds on the values of the coefficients in the CG-cut", 4554 &sepadata->cutcoefbnd, TRUE, DEFAULT_CUTCOEFBND, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 4555 4556 SCIP_CALL( SCIPaddBoolParam(scip, 4557 "separating/" SEPA_NAME "/onlyactiverows", 4558 "Use only active rows to generate cuts?", 4559 &sepadata->onlyactiverows, FALSE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) ); 4560 4561 SCIP_CALL( SCIPaddIntParam(scip, 4562 "separating/" SEPA_NAME "/maxrowage", 4563 "maximal age of rows to consider if onlyactiverows is false", 4564 &sepadata->maxrowage, FALSE, DEFAULT_MAXROWAGE, -1, INT_MAX, NULL, NULL) ); 4565 4566 SCIP_CALL( SCIPaddBoolParam(scip, 4567 "separating/" SEPA_NAME "/onlyrankone", 4568 "Separate only rank 1 inequalities w.r.t. CG-MIP separator?", 4569 &sepadata->onlyrankone, FALSE, DEFAULT_ONLYRANKONE, NULL, NULL) ); 4570 4571 SCIP_CALL( SCIPaddBoolParam(scip, 4572 "separating/" SEPA_NAME "/onlyintvars", 4573 "Generate cuts for problems with only integer variables?", 4574 &sepadata->onlyintvars, FALSE, DEFAULT_ONLYINTVARS, NULL, NULL) ); 4575 4576 SCIP_CALL( SCIPaddBoolParam(scip, 4577 "separating/" SEPA_NAME "/contconvert", 4578 "Convert some integral variables to be continuous to reduce the size of the sub-MIP?", 4579 &sepadata->contconvert, FALSE, DEFAULT_CONTCONVERT, NULL, NULL) ); 4580 4581 SCIP_CALL( SCIPaddRealParam(scip, 4582 "separating/" SEPA_NAME "/contconvfrac", 4583 "fraction of integral variables converted to be continuous (if contconvert)", 4584 &sepadata->contconvfrac, FALSE, DEFAULT_CONTCONVFRAC, 0.0, 1.0, NULL, NULL) ); 4585 4586 SCIP_CALL( SCIPaddIntParam(scip, 4587 "separating/" SEPA_NAME "/contconvmin", 4588 "minimum number of integral variables before some are converted to be continuous", 4589 &sepadata->contconvmin, FALSE, DEFAULT_CONTCONVMIN, -1, INT_MAX, NULL, NULL) ); 4590 4591 SCIP_CALL( SCIPaddBoolParam(scip, 4592 "separating/" SEPA_NAME "/intconvert", 4593 "Convert some integral variables attaining fractional values to have integral value?", 4594 &sepadata->intconvert, FALSE, DEFAULT_INTCONVERT, NULL, NULL) ); 4595 4596 SCIP_CALL( SCIPaddRealParam(scip, 4597 "separating/" SEPA_NAME "/intconvfrac", 4598 "fraction of frac. integral variables converted to have integral value (if intconvert)", 4599 &sepadata->intconvfrac, FALSE, DEFAULT_INTCONVFRAC, 0.0, 1.0, NULL, NULL) ); 4600 4601 SCIP_CALL( SCIPaddIntParam(scip, 4602 "separating/" SEPA_NAME "/intconvmin", 4603 "minimum number of integral variables before some are converted to have integral value", 4604 &sepadata->intconvmin, FALSE, DEFAULT_INTCONVMIN, -1, INT_MAX, NULL, NULL) ); 4605 4606 SCIP_CALL( SCIPaddBoolParam(scip, 4607 "separating/" SEPA_NAME "/skipmultbounds", 4608 "Skip the upper bounds on the multipliers in the sub-MIP?", 4609 &sepadata->skipmultbounds, FALSE, DEFAULT_SKIPMULTBOUNDS, NULL, NULL) ); 4610 4611 SCIP_CALL( SCIPaddBoolParam(scip, 4612 "separating/" SEPA_NAME "/objlone", 4613 "Should the objective of the sub-MIP minimize the l1-norm of the multipliers?", 4614 &sepadata->objlone, FALSE, DEFAULT_OBJLONE, NULL, NULL) ); 4615 4616 SCIP_CALL( SCIPaddRealParam(scip, 4617 "separating/" SEPA_NAME "/objweight", 4618 "weight used for the row combination coefficient in the sub-MIP objective", 4619 &sepadata->objweight, TRUE, DEFAULT_OBJWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 4620 4621 SCIP_CALL( SCIPaddBoolParam(scip, 4622 "separating/" SEPA_NAME "/objweightsize", 4623 "Weight each row by its size?", 4624 &sepadata->objweightsize, FALSE, DEFAULT_OBJWEIGHTSIZE, NULL, NULL) ); 4625 4626 SCIP_CALL( SCIPaddBoolParam(scip, 4627 "separating/" SEPA_NAME "/dynamiccuts", 4628 "should generated cuts be removed from the LP if they are no longer tight?", 4629 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) ); 4630 4631 SCIP_CALL( SCIPaddBoolParam(scip, 4632 "separating/" SEPA_NAME "/usecmir", 4633 "use CMIR-generator (otherwise add cut directly)?", 4634 &sepadata->usecmir, FALSE, DEFAULT_USECMIR, NULL, NULL) ); 4635 4636 SCIP_CALL( SCIPaddBoolParam(scip, 4637 "separating/" SEPA_NAME "/usestrongcg", 4638 "use strong CG-function to strengthen cut?", 4639 &sepadata->usestrongcg, FALSE, DEFAULT_USESTRONGCG, NULL, NULL) ); 4640 4641 SCIP_CALL( SCIPaddBoolParam(scip, 4642 "separating/" SEPA_NAME "/cmirownbounds", 4643 "tell CMIR-generator which bounds to used in rounding?", 4644 &sepadata->cmirownbounds, FALSE, DEFAULT_CMIROWNBOUNDS, NULL, NULL) ); 4645 4646 SCIP_CALL( SCIPaddBoolParam(scip, 4647 "separating/" SEPA_NAME "/usecutpool", 4648 "use cutpool to store CG-cuts even if the are not efficient?", 4649 &sepadata->usecutpool, FALSE, DEFAULT_USECUTPOOL, NULL, NULL) ); 4650 4651 SCIP_CALL( SCIPaddBoolParam(scip, 4652 "separating/" SEPA_NAME "/primalseparation", 4653 "only separate cuts that are tight for the best feasible solution?", 4654 &sepadata->primalseparation, FALSE, DEFAULT_PRIMALSEPARATION, NULL, NULL) ); 4655 4656 SCIP_CALL( SCIPaddBoolParam(scip, 4657 "separating/" SEPA_NAME "/earlyterm", 4658 "terminate separation if a violated (but possibly sub-optimal) cut has been found?", 4659 &sepadata->earlyterm, FALSE, DEFAULT_EARLYTERM, NULL, NULL) ); 4660 4661 SCIP_CALL( SCIPaddBoolParam(scip, 4662 "separating/" SEPA_NAME "/addviolationcons", 4663 "add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?", 4664 &sepadata->addviolationcons, FALSE, DEFAULT_ADDVIOLATIONCONS, NULL, NULL) ); 4665 4666 SCIP_CALL( SCIPaddBoolParam(scip, 4667 "separating/" SEPA_NAME "/addviolconshdlr", 4668 "add constraint handler to filter out violated cuts?", 4669 &sepadata->addviolconshdlr, FALSE, DEFAULT_ADDVIOLCONSHDLR, NULL, NULL) ); 4670 4671 SCIP_CALL( SCIPaddBoolParam(scip, 4672 "separating/" SEPA_NAME "/conshdlrusenorm", 4673 "should the violation constraint handler use the norm of a cut to check for feasibility?", 4674 &sepadata->conshdlrusenorm, FALSE, DEFAULT_CONSHDLRUSENORM, NULL, NULL) ); 4675 4676 SCIP_CALL( SCIPaddBoolParam(scip, 4677 "separating/" SEPA_NAME "/useobjub", 4678 "Use upper bound on objective function (via primal solution)?", 4679 &sepadata->useobjub, FALSE, DEFAULT_USEOBJUB, NULL, NULL) ); 4680 4681 SCIP_CALL( SCIPaddBoolParam(scip, 4682 "separating/" SEPA_NAME "/useobjlb", 4683 "Use lower bound on objective function (via primal solution)?", 4684 &sepadata->useobjlb, FALSE, DEFAULT_USEOBJLB, NULL, NULL) ); 4685 4686 SCIP_CALL( SCIPaddBoolParam(scip, 4687 "separating/" SEPA_NAME "/subscipfast", 4688 "Should the settings for the sub-MIP be optimized for speed?", 4689 &sepadata->subscipfast, FALSE, DEFAULT_SUBSCIPFAST, NULL, NULL) ); 4690 4691 SCIP_CALL( SCIPaddBoolParam(scip, 4692 "separating/" SEPA_NAME "/output", 4693 "Should information about the sub-MIP and cuts be displayed?", 4694 &sepadata->output, FALSE, DEFAULT_OUTPUT, NULL, NULL) ); 4695 4696 SCIP_CALL( SCIPaddBoolParam(scip, 4697 "separating/" SEPA_NAME "/genprimalsols", 4698 "Try to generate primal solutions from Gomory cuts?", 4699 &sepadata->genprimalsols, FALSE, DEFAULT_GENPRIMALSOLS, NULL, NULL) ); 4700 4701 return SCIP_OKAY; 4702 } 4703