1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file sepa_intobj.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief integer objective value separator 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 */ 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/pub_event.h" 34 #include "scip/pub_lp.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_sepa.h" 37 #include "scip/pub_var.h" 38 #include "scip/scip_branch.h" 39 #include "scip/scip_cut.h" 40 #include "scip/scip_event.h" 41 #include "scip/scip_general.h" 42 #include "scip/scip_lp.h" 43 #include "scip/scip_message.h" 44 #include "scip/scip_mem.h" 45 #include "scip/scip_numerics.h" 46 #include "scip/scip_prob.h" 47 #include "scip/scip_sepa.h" 48 #include "scip/scip_sol.h" 49 #include "scip/scip_solvingstats.h" 50 #include "scip/scip_var.h" 51 #include "scip/sepa_intobj.h" 52 #include <string.h> 53 54 55 #define SEPA_NAME "intobj" 56 #define SEPA_DESC "integer objective value separator" 57 #define SEPA_PRIORITY -100 58 #define SEPA_FREQ -1 59 #define SEPA_MAXBOUNDDIST 0.0 60 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */ 61 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 62 63 #define EVENTHDLR_NAME "intobj" 64 #define EVENTHDLR_DESC "objective change event handler for integer objective value separator" 65 66 67 /* 68 * Data structures 69 */ 70 71 /** separator data */ 72 struct SCIP_SepaData 73 { 74 SCIP_ROW* objrow; /**< objective value inequality */ 75 SCIP_VAR* objvar; /**< objective value variable */ 76 SCIP_Real setoff; /**< setoff of the inequality */ 77 }; 78 79 80 /* 81 * Local methods 82 */ 83 84 /** creates separator data */ 85 static 86 SCIP_RETCODE sepadataCreate( 87 SCIP* scip, /**< SCIP data structure */ 88 SCIP_SEPADATA** sepadata /**< pointer to store separator data */ 89 ) 90 { 91 assert(sepadata != NULL); 92 93 SCIP_CALL( SCIPallocBlockMemory(scip, sepadata) ); 94 (*sepadata)->objrow = NULL; 95 (*sepadata)->objvar = NULL; 96 (*sepadata)->setoff = 0.0; 97 98 return SCIP_OKAY; 99 } 100 101 /** frees separator data */ 102 static 103 SCIP_RETCODE sepadataFree( 104 SCIP* scip, /**< SCIP data structure */ 105 SCIP_SEPADATA** sepadata /**< pointer to separator data */ 106 ) 107 { 108 assert(sepadata != NULL); 109 assert(*sepadata != NULL); 110 assert((*sepadata)->objrow == NULL); 111 assert((*sepadata)->objvar == NULL); 112 113 SCIPfreeBlockMemory(scip, sepadata); 114 115 return SCIP_OKAY; 116 } 117 118 /** creates the objective value inequality and the objective value variable, if not yet existing */ 119 static 120 SCIP_RETCODE createObjRow( 121 SCIP* scip, /**< SCIP data structure */ 122 SCIP_SEPA* sepa, /**< separator */ 123 SCIP_SEPADATA* sepadata /**< separator data */ 124 ) 125 { 126 assert(sepadata != NULL); 127 128 if( sepadata->objrow == NULL ) 129 { 130 SCIP_VAR** vars; 131 SCIP_Real obj; 132 SCIP_Real intobjval; 133 int nvars; 134 int v; 135 SCIP_Bool attendobjvarbound; 136 137 attendobjvarbound = FALSE; 138 /* create and add objective value variable */ 139 if( sepadata->objvar == NULL ) 140 { 141 SCIP_CALL( SCIPcreateVar(scip, &sepadata->objvar, "objvar", -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, 142 SCIP_VARTYPE_IMPLINT, FALSE, TRUE, NULL, NULL, NULL, NULL, NULL) ); 143 SCIPvarMarkRelaxationOnly(sepadata->objvar); 144 SCIP_CALL( SCIPaddVar(scip, sepadata->objvar) ); 145 SCIP_CALL( SCIPaddVarLocksType(scip, sepadata->objvar, SCIP_LOCKTYPE_MODEL, +1, +1) ); 146 } 147 else 148 attendobjvarbound = TRUE; 149 150 /* get problem variables */ 151 vars = SCIPgetVars(scip); 152 nvars = SCIPgetNVars(scip); 153 154 /* create objective value inequality */ 155 if( attendobjvarbound ) 156 intobjval = SCIPceil(scip, SCIPgetLowerbound(scip)) - SCIPvarGetLbGlobal(sepadata->objvar); 157 else 158 intobjval = SCIPceil(scip, SCIPgetLowerbound(scip)); 159 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &sepadata->objrow, sepa, "objrow", intobjval, SCIPinfinity(scip), 160 FALSE, !SCIPallVarsInProb(scip), TRUE) ); 161 sepadata->setoff = intobjval; 162 163 SCIP_CALL( SCIPcacheRowExtensions(scip, sepadata->objrow) ); 164 for( v = 0; v < nvars; ++v ) 165 { 166 obj = SCIPvarGetObj(vars[v]); 167 if( !SCIPisZero(scip, obj) ) 168 { 169 SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, vars[v], obj) ); 170 } 171 } 172 SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, sepadata->objvar, -1.0) ); 173 SCIP_CALL( SCIPflushRowExtensions(scip, sepadata->objrow) ); 174 175 SCIPdebugMsg(scip, "created objective value row: "); 176 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, sepadata->objrow, NULL) ) ); 177 } 178 179 return SCIP_OKAY; 180 } 181 182 /** searches and adds integral objective cuts that separate the given primal solution */ 183 static 184 SCIP_RETCODE separateCuts( 185 SCIP* scip, /**< SCIP data structure */ 186 SCIP_SEPA* sepa, /**< the intobj separator */ 187 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */ 188 SCIP_RESULT* result /**< pointer to store the result */ 189 ) 190 { 191 SCIP_SEPADATA* sepadata; 192 SCIP_Real objval; 193 SCIP_Real intbound; 194 SCIP_Bool infeasible; 195 SCIP_Bool tightened; 196 197 assert(result != NULL); 198 assert(*result == SCIP_DIDNOTRUN); 199 200 /* if the objective value may be fractional, we cannot do anything */ 201 if( !SCIPisObjIntegral(scip) ) 202 return SCIP_OKAY; 203 204 *result = SCIP_DIDNOTFIND; 205 206 /* if the current objective value is integral, there is no integral objective value cut */ 207 if( sol == NULL ) 208 objval = SCIPgetLPObjval(scip); 209 else 210 objval = SCIPgetSolTransObj(scip, sol); 211 if( SCIPisFeasIntegral(scip, objval) ) 212 return SCIP_OKAY; 213 214 sepadata = SCIPsepaGetData(sepa); 215 assert(sepadata != NULL); 216 217 /* the objective value is fractional: create the objective value inequality, if not yet existing */ 218 SCIP_CALL( createObjRow(scip, sepa, sepadata) ); 219 220 /* adjust the bounds of the objective value variable */ 221 intbound = SCIPceil(scip, objval) - sepadata->setoff; 222 SCIP_CALL( SCIPtightenVarLb(scip, sepadata->objvar, intbound, FALSE, &infeasible, &tightened) ); 223 SCIPdebugMsg(scip, "new objective variable lower bound: <%s>[%g,%g]\n", 224 SCIPvarGetName(sepadata->objvar), SCIPvarGetLbLocal(sepadata->objvar), SCIPvarGetUbLocal(sepadata->objvar)); 225 226 /* add the objective value inequality as a cut to the LP */ 227 if( infeasible ) 228 *result = SCIP_CUTOFF; 229 else 230 { 231 if( !SCIProwIsInLP(sepadata->objrow) ) 232 { 233 SCIP_CALL( SCIPaddRow(scip, sepadata->objrow, FALSE, &infeasible) ); 234 } 235 if ( infeasible ) 236 *result = SCIP_CUTOFF; 237 else if ( tightened ) 238 *result = SCIP_REDUCEDDOM; 239 else 240 *result = SCIP_SEPARATED; 241 } 242 243 return SCIP_OKAY; 244 } 245 246 247 /* 248 * Callback methods of separator 249 */ 250 251 /** copy method for separator plugins (called when SCIP copies plugins) */ 252 static 253 SCIP_DECL_SEPACOPY(sepaCopyIntobj) 254 { /*lint --e{715}*/ 255 assert(scip != NULL); 256 assert(sepa != NULL); 257 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 258 259 /* call inclusion method of constraint handler */ 260 SCIP_CALL( SCIPincludeSepaIntobj(scip) ); 261 262 return SCIP_OKAY; 263 } 264 265 /** destructor of separator to free user data (called when SCIP is exiting) */ 266 static 267 SCIP_DECL_SEPAFREE(sepaFreeIntobj) 268 { /*lint --e{715}*/ 269 SCIP_SEPADATA* sepadata; 270 271 /* free separator data */ 272 sepadata = SCIPsepaGetData(sepa); 273 assert(sepadata != NULL); 274 275 SCIP_CALL( sepadataFree(scip, &sepadata) ); 276 277 SCIPsepaSetData(sepa, NULL); 278 279 return SCIP_OKAY; 280 } 281 282 283 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */ 284 static 285 SCIP_DECL_SEPAEXITSOL(sepaExitsolIntobj) 286 { /*lint --e{715}*/ 287 SCIP_SEPADATA* sepadata; 288 289 sepadata = SCIPsepaGetData(sepa); 290 assert(sepadata != NULL); 291 292 /* release objective row */ 293 if( sepadata->objrow != NULL ) 294 { 295 SCIP_CALL( SCIPreleaseRow(scip, &sepadata->objrow) ); 296 } 297 298 /* release objective variable */ 299 if( sepadata->objvar != NULL ) 300 { 301 /* remove locks in createObjRow() */ 302 SCIP_CALL( SCIPaddVarLocksType(scip, sepadata->objvar, SCIP_LOCKTYPE_MODEL, -1, -1) ); 303 SCIP_CALL( SCIPreleaseVar(scip, &sepadata->objvar) ); 304 } 305 306 return SCIP_OKAY; 307 } 308 309 310 /** LP solution separation method of separator */ 311 static 312 SCIP_DECL_SEPAEXECLP(sepaExeclpIntobj) 313 { /*lint --e{715}*/ 314 *result = SCIP_DIDNOTRUN; 315 316 /* only call separator, if we are not close to terminating */ 317 if( SCIPisStopped(scip) ) 318 return SCIP_OKAY; 319 320 /* only call separator, if an optimal LP solution is at hand */ 321 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 322 return SCIP_OKAY; 323 324 /* only call separator, if there are fractional variables */ 325 if( SCIPgetNLPBranchCands(scip) == 0 ) 326 return SCIP_OKAY; 327 328 SCIP_CALL( separateCuts(scip, sepa, NULL, result) ); 329 330 return SCIP_OKAY; 331 } 332 333 334 /** arbitrary primal solution separation method of separator */ 335 static 336 SCIP_DECL_SEPAEXECSOL(sepaExecsolIntobj) 337 { /*lint --e{715}*/ 338 *result = SCIP_DIDNOTRUN; 339 340 /* only call separator, if we are not close to terminating */ 341 if( SCIPisStopped(scip) ) 342 return SCIP_OKAY; 343 344 /* only call separator, if there can be no feasible integral objective value at least as good */ 345 if( SCIPfloor(scip, SCIPgetSolTransObj(scip, sol)) >= SCIPceil(scip, SCIPgetLocalLowerbound(scip)) ) 346 return SCIP_OKAY; 347 348 SCIP_CALL( separateCuts(scip, sepa, sol, result) ); 349 350 return SCIP_OKAY; 351 } 352 353 354 /* 355 * event handler for objective changes 356 */ 357 358 359 /** initialization method of event handler (called after problem was transformed) */ 360 static 361 SCIP_DECL_EVENTINIT(eventInitIntobj) 362 { /*lint --e{715}*/ 363 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_VARADDED | SCIP_EVENTTYPE_OBJCHANGED, eventhdlr, NULL, NULL) ); 364 365 return SCIP_OKAY; 366 } 367 368 /** deinitialization method of event handler (called before transformed problem is freed) */ 369 static 370 SCIP_DECL_EVENTEXIT(eventExitIntobj) 371 { /*lint --e{715}*/ 372 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_VARADDED | SCIP_EVENTTYPE_OBJCHANGED, eventhdlr, NULL, -1) ); 373 374 return SCIP_OKAY; 375 } 376 377 378 /** execution method of objective change event handler */ 379 static 380 SCIP_DECL_EVENTEXEC(eventExecIntobj) 381 { /*lint --e{715}*/ 382 SCIP_EVENTHDLRDATA* eventhdlrdata; 383 SCIP_SEPADATA* sepadata; 384 SCIP_VAR* var; 385 SCIP_Real objdelta; 386 387 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 388 sepadata = (SCIP_SEPADATA*)eventhdlrdata; 389 assert(sepadata != NULL); 390 391 /* we don't have anything to do, if the objective value inequality doesn't yet exist */ 392 if( sepadata->objrow == NULL ) 393 return SCIP_OKAY; 394 395 var = SCIPeventGetVar(event); 396 397 switch( SCIPeventGetType(event) ) 398 { 399 case SCIP_EVENTTYPE_VARADDED: 400 SCIPdebugMsg(scip, "variable <%s> with obj=%g was added to the problem\n", SCIPvarGetName(var), SCIPvarGetObj(var)); 401 objdelta = SCIPvarGetObj(var); 402 if( !SCIPisZero(scip, objdelta) ) 403 { 404 SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, var, SCIPvarGetObj(var)) ); 405 } 406 break; 407 408 case SCIP_EVENTTYPE_OBJCHANGED: 409 SCIPdebugMsg(scip, "variable <%s> changed objective value from %g to %g\n", SCIPvarGetName(var), SCIPeventGetOldobj(event), SCIPeventGetNewobj(event)); 410 objdelta = SCIPeventGetNewobj(event) - SCIPeventGetOldobj(event); 411 SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, var, objdelta) ); 412 break; 413 414 default: 415 SCIPerrorMessage("invalid event type %" SCIP_EVENTTYPE_FORMAT "\n", SCIPeventGetType(event)); 416 return SCIP_INVALIDDATA; 417 } 418 419 return SCIP_OKAY; 420 } 421 422 423 /* 424 * separator specific interface methods 425 */ 426 427 /** creates the integer objective value separator and includes it in SCIP */ 428 SCIP_RETCODE SCIPincludeSepaIntobj( 429 SCIP* scip /**< SCIP data structure */ 430 ) 431 { 432 SCIP_SEPADATA* sepadata; 433 SCIP_EVENTHDLRDATA* eventhdlrdata; 434 SCIP_SEPA* sepa; 435 SCIP_EVENTHDLR* eventhdlr; 436 437 /* create intobj separator data */ 438 SCIP_CALL( sepadataCreate(scip, &sepadata) ); 439 440 /* include separator */ 441 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 442 SEPA_USESSUBSCIP, SEPA_DELAY, 443 sepaExeclpIntobj, sepaExecsolIntobj, 444 sepadata) ); 445 446 assert(sepa != NULL); 447 448 /* set non-NULL pointers to callback methods */ 449 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyIntobj) ); 450 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeIntobj) ); 451 SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolIntobj) ); 452 453 /* include event handler for objective change events */ 454 eventhdlr = NULL; 455 eventhdlrdata = (SCIP_EVENTHDLRDATA*)sepadata; 456 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, 457 eventExecIntobj, eventhdlrdata) ); 458 assert(eventhdlr != NULL); 459 460 SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitIntobj) ); 461 SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitIntobj) ); 462 463 return SCIP_OKAY; 464 } 465