1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file prop_dualfix.c
17 * @ingroup DEFPLUGINS_PROP
18 * @brief fixing roundable variables to best bound
19 * @author Tobias Achterberg
20 * @author Stefan Heinz
21 */
22
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24
25 #include "scip/prop_dualfix.h"
26 #include "scip/pub_message.h"
27 #include "scip/pub_prop.h"
28 #include "scip/pub_var.h"
29 #include "scip/scip_general.h"
30 #include "scip/scip_message.h"
31 #include "scip/scip_numerics.h"
32 #include "scip/scip_prob.h"
33 #include "scip/scip_probing.h"
34 #include "scip/scip_prop.h"
35 #include "scip/scip_tree.h"
36 #include "scip/scip_var.h"
37 #include <string.h>
38
39 #define PROP_NAME "dualfix"
40 #define PROP_DESC "roundable variables dual fixing"
41 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP
42 #define PROP_PRIORITY +8000000 /**< propagation priority */
43 #define PROP_FREQ 0 /**< propagation frequency */
44 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found
45 * reductions? */
46 #define PROP_PRESOL_PRIORITY +8000000 /**< priority of the propagator (>= 0: before, < 0: after constraint handlers) */
47 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of propving rounds the propver participates in (-1: no limit) */
48 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
49
50
51 /**@name Local methods
52 *
53 * @{
54 */
55
56 /** perform dual presolving */
57 static
performDualfix(SCIP * scip,int * nfixedvars,SCIP_Bool * unbounded,SCIP_Bool * cutoff)58 SCIP_RETCODE performDualfix(
59 SCIP* scip, /**< SCIP data structure */
60 int* nfixedvars, /**< pointer to store number of fixed variables */
61 SCIP_Bool* unbounded, /**< pointer to store if an unboundness was detected */
62 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
63 )
64 {
65 SCIP_VAR** vars;
66 int nvars;
67 int v;
68
69 /* get active problem variables */
70 vars = SCIPgetVars(scip);
71 nvars = SCIPgetNVars(scip);
72
73 /* look for fixable variables
74 * loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array
75 */
76 for( v = nvars - 1; v >= 0; --v )
77 {
78 SCIP_VAR* var;
79 SCIP_Real bound;
80 SCIP_Real obj;
81 SCIP_Bool infeasible;
82 SCIP_Bool fixed;
83
84 var = vars[v];
85 assert(var != NULL);
86
87 /* don't perform dual presolving operations on deleted variables */
88 if( SCIPvarIsDeleted(var) )
89 continue;
90
91 /* ignore already fixed variables */
92 if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
93 continue;
94
95 obj = SCIPvarGetObj(var);
96
97 /* if the objective coefficient of the variable is 0 and it may be rounded both
98 * up and down, then fix it to the closest feasible value to 0 */
99 if( SCIPisZero(scip, obj) && SCIPvarMayRoundDown(var) && SCIPvarMayRoundUp(var) )
100 {
101 SCIP_Real roundbound;
102
103 bound = SCIPvarGetLbGlobal(var);
104 if( SCIPisLT(scip, bound, 0.0) )
105 {
106 if( SCIPisLE(scip, 0.0, SCIPvarGetUbGlobal(var)) )
107 bound = 0.0;
108 else
109 {
110 /* try to take an integer value, only for polishing */
111 roundbound = SCIPfloor(scip, SCIPvarGetUbGlobal(var));
112
113 if( roundbound < bound )
114 bound = SCIPvarGetUbGlobal(var);
115 else
116 bound = roundbound;
117 }
118 }
119 else
120 {
121 /* try to take an integer value, only for polishing */
122 roundbound = SCIPceil(scip, bound);
123
124 if( roundbound < SCIPvarGetUbGlobal(var) )
125 bound = roundbound;
126 }
127 SCIPdebugMsg(scip, "fixing variable <%s> with objective 0 to %g\n", SCIPvarGetName(var), bound);
128 }
129 else
130 {
131 /* if it is always possible to round variable in direction of objective value, fix it to its proper bound */
132 if( SCIPvarMayRoundDown(var) && !SCIPisNegative(scip, obj) )
133 {
134 bound = SCIPvarGetLbGlobal(var);
135 if ( SCIPisInfinity(scip, -bound) )
136 {
137 /* variable can be fixed to -infinity */
138 if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
139 {
140 /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
141 * consistently. We thus have to ignore this (should better be handled in presolving). */
142 continue;
143 }
144 if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1 )
145 {
146 /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
147 * clever enough to set/aggregate the variable to something more useful than -infinity and do nothing
148 * here. */
149 continue;
150 }
151 }
152 SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d uplocks to lower bound %g\n",
153 SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL), bound);
154 }
155 else if( SCIPvarMayRoundUp(var) && !SCIPisPositive(scip, obj) )
156 {
157 bound = SCIPvarGetUbGlobal(var);
158 if ( SCIPisInfinity(scip, bound) )
159 {
160 /* variable can be fixed to infinity */
161 if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
162 {
163 /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
164 * consistently. We thus have to ignore this (should better be handled in presolving). */
165 continue;
166 }
167 if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 )
168 {
169 /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
170 * clever enough to set/aggregate the variable to something more useful than +infinity and do nothing
171 * here */
172 continue;
173 }
174 }
175 SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d downlocks to upper bound %g\n",
176 SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL), bound);
177 }
178 else
179 continue;
180 }
181
182 if( SCIPisInfinity(scip, REALABS(bound)) && !SCIPisZero(scip, obj) )
183 {
184 SCIPdebugMsg(scip, " -> unbounded fixing\n");
185 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
186 "problem infeasible or unbounded: variable <%s> with objective %.15g can be made infinitely %s\n",
187 SCIPvarGetName(var), SCIPvarGetObj(var), bound < 0.0 ? "small" : "large");
188 *unbounded = TRUE;
189 return SCIP_OKAY;
190 }
191
192 /* apply the fixing */
193 SCIPdebugMsg(scip, "apply fixing of variable %s to %g\n", SCIPvarGetName(var), bound);
194 SCIP_CALL( SCIPfixVar(scip, var, bound, &infeasible, &fixed) );
195
196 if( infeasible )
197 {
198 SCIPdebugMsg(scip, " -> infeasible fixing\n");
199 *cutoff = TRUE;
200 return SCIP_OKAY;
201 }
202
203 /* SCIPfixVar only changes bounds if not already feaseq.
204 * Only if in presolve and not probing, variables will always be fixed.
205 */
206 assert(fixed || (SCIPisFeasEQ(scip, bound, SCIPvarGetLbLocal(var))
207 && SCIPisFeasEQ(scip, bound, SCIPvarGetUbLocal(var))));
208 (*nfixedvars)++;
209 }
210
211 return SCIP_OKAY;
212 }
213
214 /**@} */
215
216 /**@name Callback methods
217 *
218 * @{
219 */
220
221 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
222 static
SCIP_DECL_PROPCOPY(propCopyDualfix)223 SCIP_DECL_PROPCOPY(propCopyDualfix)
224 { /*lint --e{715}*/
225 assert(scip != NULL);
226 assert(prop != NULL);
227 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
228
229 /* call inclusion method of propagator */
230 SCIP_CALL( SCIPincludePropDualfix(scip) );
231
232 return SCIP_OKAY;
233 }
234
235 /** presolving method of propagator */
236 static
SCIP_DECL_PROPPRESOL(propPresolDualfix)237 SCIP_DECL_PROPPRESOL(propPresolDualfix)
238 { /*lint --e{715}*/
239 SCIP_Bool cutoff;
240 SCIP_Bool unbounded;
241 int oldnfixedvars;
242
243 assert(prop != NULL);
244 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
245 assert(result != NULL);
246
247 *result = SCIP_DIDNOTRUN;
248
249 if( !SCIPallowStrongDualReds(scip) )
250 return SCIP_OKAY;
251
252 cutoff = FALSE;
253 unbounded = FALSE;
254 oldnfixedvars = *nfixedvars;
255
256 SCIP_CALL( performDualfix(scip, nfixedvars, &unbounded, &cutoff) );
257
258 /* evaluate propagation result */
259 if( cutoff )
260 *result = SCIP_CUTOFF;
261 else if( unbounded )
262 *result = SCIP_UNBOUNDED;
263 else if( *nfixedvars > oldnfixedvars )
264 *result = SCIP_SUCCESS;
265 else
266 *result = SCIP_DIDNOTFIND;
267
268 return SCIP_OKAY;
269 }
270
271 /** execution method of propagator */
272 static
SCIP_DECL_PROPEXEC(propExecDualfix)273 SCIP_DECL_PROPEXEC(propExecDualfix)
274 { /*lint --e{715}*/
275 int nfixedvars;
276 SCIP_Bool cutoff;
277 SCIP_Bool unbounded;
278
279 assert(prop != NULL);
280 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
281 assert(result != NULL);
282
283 *result = SCIP_DIDNOTRUN;
284
285 /** @warning Don't run in probing or in repropagation since this can lead to wrong conclusion
286 *
287 * do not run if propagation w.r.t. current objective is not allowed
288 */
289 if( SCIPinProbing(scip) || SCIPinRepropagation(scip) || !SCIPallowStrongDualReds(scip) )
290 return SCIP_OKAY;
291
292 cutoff = FALSE;
293 unbounded = FALSE;
294 nfixedvars = 0;
295
296 SCIP_CALL( performDualfix(scip, &nfixedvars, &unbounded, &cutoff) );
297
298 /* evaluate propagation result */
299 if( cutoff )
300 *result = SCIP_CUTOFF;
301 else if( unbounded )
302 *result = SCIP_UNBOUNDED;
303 else if( nfixedvars > 0 )
304 *result = SCIP_REDUCEDDOM;
305 else
306 *result = SCIP_DIDNOTFIND;
307
308 return SCIP_OKAY;
309 }
310
311
312 /**@} */
313
314 /**@name Interface methods
315 *
316 * @{
317 */
318
319 /** creates the dual fixing propagator and includes it in SCIP */
SCIPincludePropDualfix(SCIP * scip)320 SCIP_RETCODE SCIPincludePropDualfix(
321 SCIP* scip /**< SCIP data structure */
322 )
323 {
324 SCIP_PROP* prop;
325
326 /* include propagator */
327 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, propExecDualfix, NULL) );
328 assert(prop != NULL);
329
330 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyDualfix) );
331 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolDualfix, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
332
333 return SCIP_OKAY;
334 }
335
336 /**@} */
337