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 implics.h 26 * @ingroup INTERNALAPI 27 * @brief methods for implications, variable bounds, and cliques 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_IMPLICS_H__ 34 #define __SCIP_IMPLICS_H__ 35 36 37 #include "blockmemshell/memory.h" 38 #include "scip/def.h" 39 #include "scip/type_branch.h" 40 #include "scip/type_event.h" 41 #include "scip/type_implics.h" 42 #include "scip/type_lp.h" 43 #include "scip/type_prob.h" 44 #include "scip/type_reopt.h" 45 #include "scip/type_retcode.h" 46 #include "scip/type_set.h" 47 #include "scip/type_stat.h" 48 #include "scip/type_tree.h" 49 #include "scip/type_var.h" 50 51 #ifdef NDEBUG 52 #include "scip/pub_implics.h" 53 #include "scip/struct_implics.h" 54 #endif 55 56 #ifdef __cplusplus 57 extern "C" { 58 #endif 59 60 /* 61 * Methods for Variable Bounds 62 */ 63 64 /** frees a variable bounds data structure */ 65 void SCIPvboundsFree( 66 SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */ 67 BMS_BLKMEM* blkmem /**< block memory */ 68 ); 69 70 /** adds a variable bound to the variable bounds data structure */ 71 SCIP_RETCODE SCIPvboundsAdd( 72 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */ 73 BMS_BLKMEM* blkmem, /**< block memory */ 74 SCIP_SET* set, /**< global SCIP settings */ 75 SCIP_BOUNDTYPE vboundtype, /**< type of variable bound (LOWER or UPPER) */ 76 SCIP_VAR* var, /**< variable z in x <= b*z + d or x >= b*z + d */ 77 SCIP_Real coef, /**< coefficient b in x <= b*z + d or x >= b*z + d */ 78 SCIP_Real constant, /**< constant d in x <= b*z + d or x >= b*z + d */ 79 SCIP_Bool* added /**< pointer to store whether the variable bound was added */ 80 ); 81 82 /** removes from variable x a variable bound x >=/<= b*z + d with binary or integer z */ 83 SCIP_RETCODE SCIPvboundsDel( 84 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */ 85 BMS_BLKMEM* blkmem, /**< block memory */ 86 SCIP_VAR* vbdvar, /**< variable z in x >=/<= b*z + d */ 87 SCIP_Bool negativecoef /**< is coefficient b negative? */ 88 ); 89 90 /** reduces the number of variable bounds stored in the given variable bounds data structure */ 91 void SCIPvboundsShrink( 92 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */ 93 BMS_BLKMEM* blkmem, /**< block memory */ 94 int newnvbds /**< new number of variable bounds */ 95 ); 96 97 98 /** gets number of variable bounds contained in given variable bounds data structure */ 99 int SCIPvboundsGetNVbds( 100 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 101 ); 102 103 /** gets array of variables contained in given variable bounds data structure */ 104 SCIP_VAR** SCIPvboundsGetVars( 105 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 106 ); 107 108 /** gets array of coefficients contained in given variable bounds data structure */ 109 SCIP_Real* SCIPvboundsGetCoefs( 110 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 111 ); 112 113 /** gets array of constants contained in given variable bounds data structure */ 114 SCIP_Real* SCIPvboundsGetConstants( 115 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 116 ); 117 118 #ifdef NDEBUG 119 120 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 121 * speed up the algorithms. 122 */ 123 124 #define SCIPvboundsGetNVbds(vbounds) ((vbounds) != NULL ? (vbounds)->len : 0) 125 #define SCIPvboundsGetVars(vbounds) ((vbounds) != NULL ? (vbounds)->vars : NULL) 126 #define SCIPvboundsGetCoefs(vbounds) ((vbounds) != NULL ? (vbounds)->coefs : NULL) 127 #define SCIPvboundsGetConstants(vbounds) ((vbounds) != NULL ? (vbounds)->constants : NULL) 128 129 #endif 130 131 132 133 134 /* 135 * Methods for Implications 136 */ 137 138 /** frees an implications data structure */ 139 void SCIPimplicsFree( 140 SCIP_IMPLICS** implics, /**< pointer of implications data structure to free */ 141 BMS_BLKMEM* blkmem /**< block memory */ 142 ); 143 144 /** adds an implication x == 0/1 -> y <= b or y >= b to the implications data structure; 145 * the implication must be non-redundant 146 */ 147 SCIP_RETCODE SCIPimplicsAdd( 148 SCIP_IMPLICS** implics, /**< pointer to implications data structure */ 149 BMS_BLKMEM* blkmem, /**< block memory */ 150 SCIP_SET* set, /**< global SCIP settings */ 151 SCIP_STAT* stat, /**< problem statistics */ 152 SCIP_Bool varfixing, /**< FALSE if implication for x == 0 has to be added, TRUE for x == 1 */ 153 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */ 154 SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */ 155 SCIP_Real implbound, /**< bound b in implication y <= b or y >= b */ 156 SCIP_Bool isshortcut, /**< is the implication a shortcut, i.e., added as part of the transitive closure of another implication? */ 157 SCIP_Bool* conflict, /**< pointer to store whether implication causes a conflict for variable x */ 158 SCIP_Bool* added /**< pointer to store whether the implication was added */ 159 ); 160 161 /** removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure */ 162 SCIP_RETCODE SCIPimplicsDel( 163 SCIP_IMPLICS** implics, /**< pointer to implications data structure */ 164 BMS_BLKMEM* blkmem, /**< block memory */ 165 SCIP_SET* set, /**< global SCIP settings */ 166 SCIP_Bool varfixing, /**< FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1 */ 167 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */ 168 SCIP_BOUNDTYPE impltype /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */ 169 ); 170 171 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */ 172 void SCIPimplicsGetVarImplics( 173 SCIP_IMPLICS* implics, /**< implications data structure */ 174 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */ 175 SCIP_VAR* implvar, /**< variable y to search for */ 176 SCIP_Bool* haslowerimplic, /**< pointer to store whether there exists an implication y >= l */ 177 SCIP_Bool* hasupperimplic /**< pointer to store whether there exists an implication y <= u */ 178 ); 179 180 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */ 181 void SCIPimplicsGetVarImplicPoss( 182 SCIP_IMPLICS* implics, /**< implications data structure */ 183 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */ 184 SCIP_VAR* implvar, /**< variable y to search for */ 185 int* haslowerimplic, /**< pointer to store the position of an implication y >= l */ 186 int* hasupperimplic /**< pointer to store the position of an implication y <= u */ 187 ); 188 189 /** returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1 */ 190 SCIP_Bool SCIPimplicsContainsImpl( 191 SCIP_IMPLICS* implics, /**< implications data structure */ 192 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */ 193 SCIP_VAR* implvar, /**< variable y to search for */ 194 SCIP_BOUNDTYPE impltype /**< type of implication y <=/>= b to search for */ 195 ); 196 197 198 /** gets number of implications for a given binary variable fixing */ 199 int SCIPimplicsGetNImpls( 200 SCIP_IMPLICS* implics, /**< implication data */ 201 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 202 ); 203 204 /** gets array with implied variables for a given binary variable fixing */ 205 SCIP_VAR** SCIPimplicsGetVars( 206 SCIP_IMPLICS* implics, /**< implication data */ 207 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 208 ); 209 210 /** gets array with implication types for a given binary variable fixing */ 211 SCIP_BOUNDTYPE* SCIPimplicsGetTypes( 212 SCIP_IMPLICS* implics, /**< implication data */ 213 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 214 ); 215 216 /** gets array with implication bounds for a given binary variable fixing */ 217 SCIP_Real* SCIPimplicsGetBounds( 218 SCIP_IMPLICS* implics, /**< implication data */ 219 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 220 ); 221 222 /** Gets array with unique implication identifiers for a given binary variable fixing. 223 * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication, 224 * its id is negative, otherwise it is nonnegative. 225 */ 226 int* SCIPimplicsGetIds( 227 SCIP_IMPLICS* implics, /**< implication data */ 228 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 229 ); 230 231 #ifdef NDEBUG 232 233 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 234 * speed up the algorithms. 235 */ 236 237 #define SCIPimplicsGetNImpls(implics, varfixing) ((implics) != NULL ? (implics)->nimpls[varfixing] : 0) 238 #define SCIPimplicsGetNBinImpls(implics, varfixing) ((implics) != NULL ? (implics)->nbinimpls[varfixing] : 0) 239 #define SCIPimplicsGetVars(implics, varfixing) ((implics) != NULL ? (implics)->vars[varfixing] : NULL) 240 #define SCIPimplicsGetTypes(implics, varfixing) ((implics) != NULL ? (implics)->types[varfixing] : NULL) 241 #define SCIPimplicsGetBounds(implics, varfixing) ((implics) != NULL ? (implics)->bounds[varfixing] : NULL) 242 #define SCIPimplicsGetIds(implics, varfixing) ((implics) != NULL ? (implics)->ids[varfixing] : NULL) 243 244 #endif 245 246 247 248 249 /* 250 * methods for cliques 251 */ 252 253 /** adds a single variable to the given clique */ 254 SCIP_RETCODE SCIPcliqueAddVar( 255 SCIP_CLIQUE* clique, /**< clique data structure */ 256 BMS_BLKMEM* blkmem, /**< block memory */ 257 SCIP_SET* set, /**< global SCIP settings */ 258 SCIP_VAR* var, /**< variable to add to the clique */ 259 SCIP_Bool value, /**< value of the variable in the clique */ 260 SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */ 261 SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */ 262 ); 263 264 /** removes a single variable from the given clique */ 265 void SCIPcliqueDelVar( 266 SCIP_CLIQUE* clique, /**< clique data structure */ 267 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 268 SCIP_VAR* var, /**< variable to remove from the clique */ 269 SCIP_Bool value /**< value of the variable in the clique */ 270 ); 271 272 /** frees a clique list data structure */ 273 void SCIPcliquelistFree( 274 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */ 275 BMS_BLKMEM* blkmem /**< block memory */ 276 ); 277 278 /** adds a clique to the clique list */ 279 SCIP_RETCODE SCIPcliquelistAdd( 280 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */ 281 BMS_BLKMEM* blkmem, /**< block memory */ 282 SCIP_SET* set, /**< global SCIP settings */ 283 SCIP_Bool value, /**< value of the variable for which the clique list should be extended */ 284 SCIP_CLIQUE* clique /**< clique that should be added to the clique list */ 285 ); 286 287 /** removes a clique from the clique list */ 288 SCIP_RETCODE SCIPcliquelistDel( 289 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */ 290 BMS_BLKMEM* blkmem, /**< block memory */ 291 SCIP_Bool value, /**< value of the variable for which the clique list should be reduced */ 292 SCIP_CLIQUE* clique /**< clique that should be deleted from the clique list */ 293 ); 294 295 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears 296 * in both lists 297 */ 298 SCIP_Bool SCIPcliquelistsHaveCommonClique( 299 SCIP_CLIQUELIST* cliquelist1, /**< first clique list data structure */ 300 SCIP_Bool value1, /**< value of first variable */ 301 SCIP_CLIQUELIST* cliquelist2, /**< second clique list data structure */ 302 SCIP_Bool value2 /**< value of second variable */ 303 ); 304 305 /** removes all listed entries from the cliques */ 306 void SCIPcliquelistRemoveFromCliques( 307 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 308 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 309 SCIP_VAR* var, /**< active problem variable the clique list belongs to */ 310 SCIP_Bool irrelevantvar /**< has the variable become irrelevant, meaning that equality 311 * cliques need to be relaxed? */ 312 ); 313 314 /** creates a clique table data structure */ 315 SCIP_RETCODE SCIPcliquetableCreate( 316 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */ 317 SCIP_SET* set, /**< global SCIP settings */ 318 BMS_BLKMEM* blkmem /**< block memory */ 319 ); 320 321 /** frees a clique table data structure */ 322 SCIP_RETCODE SCIPcliquetableFree( 323 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */ 324 BMS_BLKMEM* blkmem /**< block memory */ 325 ); 326 327 /** adds a clique to the clique table, using the given values for the given variables; 328 * performs implications if the clique contains the same variable twice 329 */ 330 SCIP_RETCODE SCIPcliquetableAdd( 331 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 332 BMS_BLKMEM* blkmem, /**< block memory */ 333 SCIP_SET* set, /**< global SCIP settings */ 334 SCIP_STAT* stat, /**< problem statistics */ 335 SCIP_PROB* transprob, /**< transformed problem */ 336 SCIP_PROB* origprob, /**< original problem */ 337 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */ 338 SCIP_REOPT* reopt, /**< reoptimization data structure */ 339 SCIP_LP* lp, /**< current LP data */ 340 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 341 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 342 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */ 343 SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */ 344 int nvars, /**< number of variables in the clique */ 345 SCIP_Bool isequation, /**< is the clique an equation or an inequality? */ 346 SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */ 347 int* nbdchgs /**< pointer to count the number of performed bound changes, or NULL */ 348 ); 349 350 /** removes all empty and single variable cliques from the clique table; removes double entries from the clique table 351 * 352 * @note cliques can be processed several times by this method 353 */ 354 SCIP_RETCODE SCIPcliquetableCleanup( 355 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 356 BMS_BLKMEM* blkmem, /**< block memory */ 357 SCIP_SET* set, /**< global SCIP settings */ 358 SCIP_STAT* stat, /**< problem statistics */ 359 SCIP_PROB* transprob, /**< transformed problem */ 360 SCIP_PROB* origprob, /**< original problem */ 361 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */ 362 SCIP_REOPT* reopt, /**< reoptimization data structure */ 363 SCIP_LP* lp, /**< current LP data */ 364 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 365 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 366 int* nchgbds, /**< pointer to store number of fixed variables */ 367 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */ 368 ); 369 370 /** computes connected components of the clique graph 371 * 372 * use depth-first search similarly to the components presolver/constraint handler, representing a clique as a 373 * path to reduce memory usage, but leaving the connected components the same 374 * 375 * an update becomes necessary if a clique gets added with variables from different components 376 */ 377 SCIP_RETCODE SCIPcliquetableComputeCliqueComponents( 378 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 379 SCIP_SET* set, /**< global SCIP settings */ 380 BMS_BLKMEM* blkmem, /**< block memory */ 381 SCIP_VAR** vars, /**< array of problem variables, sorted by variable type */ 382 int nbinvars, /**< number of binary variables */ 383 int nintvars, /**< number of integer variables */ 384 int nimplvars /**< number of implicit integer variables */ 385 ); 386 387 /** returns the index of the connected component of the clique graph that the variable belongs to, or -1 */ 388 int SCIPcliquetableGetVarComponentIdx( 389 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 390 SCIP_VAR* var /**< problem variable */ 391 ); 392 393 /** returns the number of cliques stored in the clique list */ 394 int SCIPcliquelistGetNCliques( 395 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 396 SCIP_Bool value /**< value of the variable for which the cliques should be returned */ 397 ); 398 399 /** returns the cliques stored in the clique list, or NULL if the clique list is empty */ 400 SCIP_CLIQUE** SCIPcliquelistGetCliques( 401 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 402 SCIP_Bool value /**< value of the variable for which the cliques should be returned */ 403 ); 404 405 /** checks whether variable is contained in all cliques of the cliquelist */ 406 void SCIPcliquelistCheck( 407 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 408 SCIP_VAR* var /**< variable, the clique list belongs to */ 409 ); 410 411 /** gets the number of cliques stored in the clique table */ 412 int SCIPcliquetableGetNCliques( 413 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 414 ); 415 416 /** gets the number of cliques created so far by the clique table */ 417 int SCIPcliquetableGetNCliquesCreated( 418 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 419 ); 420 421 /** gets the array of cliques stored in the clique table */ 422 SCIP_CLIQUE** SCIPcliquetableGetCliques( 423 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 424 ); 425 426 /** gets the number of entries in the whole clique table */ 427 SCIP_Longint SCIPcliquetableGetNEntries( 428 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 429 ); 430 431 /** returns the number of clique components, or -1 if update is necessary first */ 432 int SCIPcliquetableGetNCliqueComponents( 433 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 434 ); 435 436 /** returns TRUE iff the connected clique components need an update (because new cliques were added) */ 437 SCIP_Bool SCIPcliquetableNeedsComponentUpdate( 438 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 439 ); 440 441 #ifdef NDEBUG 442 443 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 444 * speed up the algorithms. 445 */ 446 447 #define SCIPcliquelistGetNCliques(cliquelist, value) ((cliquelist) != NULL ? (cliquelist)->ncliques[value] : 0) 448 #define SCIPcliquelistGetCliques(cliquelist, value) ((cliquelist) != NULL ? (cliquelist)->cliques[value] : NULL) 449 #define SCIPcliquelistCheck(cliquelist, var) /**/ 450 #define SCIPcliquetableGetNCliques(cliquetable) ((cliquetable)->ncliques) 451 #define SCIPcliquetableGetCliques(cliquetable) ((cliquetable)->cliques) 452 #define SCIPcliquetableGetNEntries(cliquetable) ((cliquetable)->nentries) 453 #define SCIPcliquetableGetNCliqueComponents(cliquetable) (cliquetable->compsfromscratch ? -1 : cliquetable->ncliquecomponents) 454 #define SCIPcliquetableNeedsComponentUpdate(cliquetable) (cliquetable->compsfromscratch || cliquetable->djset == NULL) 455 #endif 456 457 #ifdef __cplusplus 458 } 459 #endif 460 461 #endif 462