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 presolve.h 26 * @ingroup PUBLICCOREAPI 27 * @brief methods commonly used for presolving 28 * @author Michael Winkler 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_PRESOLVE_H__ 34 #define __SCIP_PRESOLVE_H__ 35 36 #include "scip/def.h" 37 #include "scip/type_retcode.h" 38 #include "scip/type_scip.h" 39 #include "scip/type_var.h" 40 41 #ifdef __cplusplus 42 extern "C" { 43 #endif 44 45 /**@defgroup PublicSpecialPresolveMethods Special Methods 46 * @ingroup PublicPresolverMethods 47 * @brief methods commonly used for presolving 48 * 49 * @{ 50 */ 51 /** try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one 52 * must be fulfilled 53 * 54 * e.g. a set of logicor or bounddisjunctive constraint variables would be such a set 55 * 56 * consider the following set: 57 * 58 * x1 >= 1, x2 >= 3, x3 >= 1, x4 <= 0 59 * 60 * by (global) implication data (cliques, implications, and variable bounds) we have also the following implications 61 * given: 62 * 63 * x1 >= 1 => x3 >= 1 64 * x2 >= 2 => x3 >= 1 65 * x4 <= 0 => x1 >= 1 66 * 67 * Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we 68 * can reduce the set by x4. 69 * Also, the both other implications and x3 >= 1 (in the given variable set) all imply exactly x3 >= 1, so we tighten 70 * the global lower bound of x3 to 1 and the set of variables gets redundant. 71 */ 72 SCIP_EXPORT 73 SCIP_RETCODE SCIPshrinkDisjunctiveVarSet( 74 SCIP* scip, /**< SCIP data structure */ 75 SCIP_VAR** vars, /**< variables array for which at least one must be fulfilled in the 76 * following bounds and boundtypes */ 77 SCIP_Real* bounds, /**< bounds array for which at least one must be fulfilled */ 78 SCIP_Bool* boundtypes, /**< boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE == SCIP_BOUNDTYPE_LOWER) 79 * for which at least one must be fulfilled */ 80 SCIP_Bool* redundants, /**< array which be filled and then indicate if a variable in the set is redundant */ 81 int nvars, /**< number of variables */ 82 int* nredvars, /**< pointer to store how many variables can be removed */ 83 int* nglobalred, /**< pointer to store number of global reductions on variable bounds found 84 * through this set of variables */ 85 SCIP_Bool* setredundant, /**< pointer to store if we found a global reduction on a variable which was part 86 * of the given set of variables, this makes this disjunction redundant */ 87 SCIP_Bool* glbinfeas, /**< pointer to store if global infeasibility was detected */ 88 SCIP_Bool fullshortening /**< do we want to try the shortening procedure over the whole set (which might be expensive) */ 89 ); 90 91 /** @} */ 92 93 #ifdef __cplusplus 94 } 95 #endif 96 97 #endif 98