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 presol_inttobinary.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief presolver that converts integer variables with domain [a,a+1] to binaries 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/debug.h" 35 #include "scip/presol_inttobinary.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_misc.h" 38 #include "scip/pub_presol.h" 39 #include "scip/pub_var.h" 40 #include "scip/scip_mem.h" 41 #include "scip/scip_message.h" 42 #include "scip/scip_numerics.h" 43 #include "scip/scip_presol.h" 44 #include "scip/scip_prob.h" 45 #include "scip/scip_var.h" 46 #include <string.h> 47 48 #define PRESOL_NAME "inttobinary" 49 #define PRESOL_DESC "converts integer variables with domain [a,a+1] to binaries" 50 #define PRESOL_PRIORITY +7000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 51 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 52 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */ 53 54 /* 55 * Callback methods of presolver 56 */ 57 58 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 59 static 60 SCIP_DECL_PRESOLCOPY(presolCopyInttobinary) 61 { /*lint --e{715}*/ 62 assert(scip != NULL); 63 assert(presol != NULL); 64 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 65 66 /* call inclusion method of presolver */ 67 SCIP_CALL( SCIPincludePresolInttobinary(scip) ); 68 69 return SCIP_OKAY; 70 } 71 72 73 /** presolving execution method */ 74 static 75 SCIP_DECL_PRESOLEXEC(presolExecInttobinary) 76 { /*lint --e{715}*/ 77 SCIP_VAR** scipvars; 78 SCIP_VAR** vars; 79 int nbinvars; 80 int nintvars; 81 int v; 82 83 assert(result != NULL); 84 85 *result = SCIP_DIDNOTRUN; 86 87 if( SCIPdoNotAggr(scip) ) 88 return SCIP_OKAY; 89 90 /* get the problem variables */ 91 scipvars = SCIPgetVars(scip); 92 nbinvars = SCIPgetNBinVars(scip); 93 nintvars = SCIPgetNIntVars(scip); 94 if( nintvars == 0 ) 95 return SCIP_OKAY; 96 97 *result = SCIP_DIDNOTFIND; 98 99 /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the 100 * array and thereby interferes with our search loop 101 */ 102 SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) ); 103 104 /* scan the integer variables for possible conversion into binaries */ 105 for( v = 0; v < nintvars; ++v ) 106 { 107 SCIP_Real lb; 108 SCIP_Real ub; 109 110 assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER); 111 112 /* get variable's bounds */ 113 lb = SCIPvarGetLbGlobal(vars[v]); 114 ub = SCIPvarGetUbGlobal(vars[v]); 115 116 /* check if bounds are exactly one apart; if the lower bound is too large, aggregations will be rejected */ 117 if( SCIPisEQ(scip, lb, ub - 1.0) && !SCIPisHugeValue(scip, REALABS(lb) / SCIPfeastol(scip)) ) 118 { 119 SCIP_VAR* binvar; 120 char binvarname[SCIP_MAXSTRLEN]; 121 SCIP_Bool infeasible; 122 SCIP_Bool redundant; 123 SCIP_Bool aggregated; 124 125 SCIPdebugMsg(scip, "converting <%s>[%g,%g] into binary variable\n", SCIPvarGetName(vars[v]), lb, ub); 126 127 /* create binary variable */ 128 (void) SCIPsnprintf(binvarname, SCIP_MAXSTRLEN, "%s_bin", SCIPvarGetName(vars[v])); 129 SCIP_CALL( SCIPcreateVar(scip, &binvar, binvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, 130 SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) ); 131 SCIP_CALL( SCIPaddVar(scip, binvar) ); 132 133 /* set up debug solution */ 134 #ifdef WITH_DEBUG_SOLUTION 135 if( SCIPdebugSolIsEnabled(scip) ) 136 { 137 SCIP_SOL* debugsol; 138 139 SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) ); 140 141 /* set solution value in the debug solution if it is available */ 142 if( debugsol != NULL ) 143 { 144 SCIP_Real val; 145 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) ); 146 SCIP_CALL( SCIPdebugAddSolVal(scip, binvar, val - lb) ); 147 } 148 } 149 #endif 150 151 /* aggregate integer and binary variable */ 152 SCIP_CALL( SCIPaggregateVars(scip, vars[v], binvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) ); 153 154 /* release binary variable */ 155 SCIP_CALL( SCIPreleaseVar(scip, &binvar) ); 156 157 /* it can be the case that this aggregation detects an infeasibility; for example, during the copy of the 158 * variable bounds from the integer variable to the binary variable, infeasibility can be detected; this can 159 * happen because an upper bound or a lower bound of such a variable bound variable was "just" changed and the 160 * varbound constraint handler, who would detect that infeasibility (since it was creating it from a varbound 161 * constraint), was called before that bound change was detected due to the presolving priorities; 162 */ 163 if( infeasible ) 164 { 165 *result = SCIP_CUTOFF; 166 break; 167 } 168 else if( aggregated ) 169 { 170 assert(redundant); 171 172 (*nchgvartypes)++; 173 ++(*naggrvars); 174 *result = SCIP_SUCCESS; 175 } 176 } 177 } 178 179 /* free temporary memory */ 180 SCIPfreeBufferArray(scip, &vars); 181 182 return SCIP_OKAY; 183 } 184 185 186 /* 187 * presolver specific interface methods 188 */ 189 190 /** creates the inttobinary presolver and includes it in SCIP */ 191 SCIP_RETCODE SCIPincludePresolInttobinary( 192 SCIP* scip /**< SCIP data structure */ 193 ) 194 { 195 SCIP_PRESOLDATA* presoldata; 196 SCIP_PRESOL* presolptr; 197 198 /* create inttobinary presolver data */ 199 presoldata = NULL; 200 201 /* include presolver */ 202 SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, 203 presolExecInttobinary, 204 presoldata) ); 205 206 assert(presolptr != NULL); 207 208 SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyInttobinary) ); 209 210 return SCIP_OKAY; 211 } 212