SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
prop_dualfix.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 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 prop_dualfix.c
26 * @ingroup DEFPLUGINS_PROP
27 * @brief fixing roundable variables to best bound
28 * @author Tobias Achterberg
29 * @author Stefan Heinz
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include "scip/prop_dualfix.h"
35#include "scip/pub_message.h"
36#include "scip/pub_prop.h"
37#include "scip/pub_var.h"
38#include "scip/scip_general.h"
39#include "scip/scip_message.h"
40#include "scip/scip_numerics.h"
41#include "scip/scip_prob.h"
42#include "scip/scip_probing.h"
43#include "scip/scip_prop.h"
44#include "scip/scip_tree.h"
45#include "scip/scip_var.h"
46#include <string.h>
47
48#define PROP_NAME "dualfix"
49#define PROP_DESC "roundable variables dual fixing"
50#define PROP_TIMING SCIP_PROPTIMING_BEFORELP
51#define PROP_PRIORITY +8000000 /**< propagation priority */
52#define PROP_FREQ 0 /**< propagation frequency */
53#define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found
54 * reductions? */
55#define PROP_PRESOL_PRIORITY +8000000 /**< priority of the propagator (>= 0: before, < 0: after constraint handlers) */
56#define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of propving rounds the propver participates in (-1: no limit) */
57#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
58
59
60/**@name Local methods
61 *
62 * @{
63 */
64
65/** perform dual presolving */
66static
68 SCIP* scip, /**< SCIP data structure */
69 int* nfixedvars, /**< pointer to store number of fixed variables */
70 SCIP_Bool* unbounded, /**< pointer to store if an unboundness was detected */
71 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
72 )
73{
74 SCIP_VAR** vars;
75 int nvars;
76 int v;
77
78 /* get active problem variables */
81
82 /* look for fixable variables
83 * loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array
84 */
85 for( v = nvars - 1; v >= 0; --v )
86 {
90 SCIP_Bool infeasible;
91 SCIP_Bool fixed;
92
93 var = vars[v];
94 assert(var != NULL);
95
96 /* don't perform dual presolving operations on deleted variables */
98 continue;
99
100 /* ignore already fixed variables */
102 continue;
103
105
106 /* if the objective coefficient of the variable is 0 and it may be rounded both
107 * up and down, then fix it to the closest feasible value to 0 */
109 {
110 SCIP_Real roundbound;
111
113 if( SCIPisLT(scip, bound, 0.0) )
114 {
115 if( SCIPisLE(scip, 0.0, SCIPvarGetUbGlobal(var)) )
116 bound = 0.0;
117 else
118 {
119 /* try to take an integer value, only for polishing */
120 roundbound = SCIPfloor(scip, SCIPvarGetUbGlobal(var));
121
122 if( roundbound < bound )
124 else
125 bound = roundbound;
126 }
127 }
128 else
129 {
130 /* try to take an integer value, only for polishing */
131 roundbound = SCIPceil(scip, bound);
132
133 if( roundbound < SCIPvarGetUbGlobal(var) )
134 bound = roundbound;
135 }
136 SCIPdebugMsg(scip, "fixing variable <%s> with objective 0 to %g\n", SCIPvarGetName(var), bound);
137 }
138 else
139 {
140 /* if it is always possible to round variable in direction of objective value, fix it to its proper bound */
142 {
144 if ( SCIPisInfinity(scip, -bound) )
145 {
146 /* variable can be fixed to -infinity */
148 {
149 /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
150 * consistently. We thus have to ignore this (should better be handled in presolving). */
151 continue;
152 }
154 {
155 /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
156 * clever enough to set/aggregate the variable to something more useful than -infinity and do nothing
157 * here. */
158 continue;
159 }
160 }
161 SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d uplocks to lower bound %g\n",
163 }
165 {
167 if ( SCIPisInfinity(scip, bound) )
168 {
169 /* variable can be fixed to infinity */
171 {
172 /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
173 * consistently. We thus have to ignore this (should better be handled in presolving). */
174 continue;
175 }
177 {
178 /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
179 * clever enough to set/aggregate the variable to something more useful than +infinity and do nothing
180 * here */
181 continue;
182 }
183 }
184 SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d downlocks to upper bound %g\n",
186 }
187 else
188 continue;
189 }
190
192 {
193 SCIPdebugMsg(scip, " -> unbounded fixing\n");
195 "problem infeasible or unbounded: variable <%s> with objective %.15g can be made infinitely %s\n",
196 SCIPvarGetName(var), SCIPvarGetObj(var), bound < 0.0 ? "small" : "large");
197 *unbounded = TRUE;
198 return SCIP_OKAY;
199 }
200
201 /* apply the fixing */
202 SCIPdebugMsg(scip, "apply fixing of variable %s to %g\n", SCIPvarGetName(var), bound);
203 SCIP_CALL( SCIPfixVar(scip, var, bound, &infeasible, &fixed) );
204
205 if( infeasible )
206 {
207 SCIPdebugMsg(scip, " -> infeasible fixing\n");
208 *cutoff = TRUE;
209 return SCIP_OKAY;
210 }
211
212 /* SCIPfixVar only changes bounds if not already feaseq.
213 * Only if in presolve and not probing, variables will always be fixed.
214 */
217 (*nfixedvars)++;
218 }
219
220 return SCIP_OKAY;
221}
222
223/**@} */
224
225/**@name Callback methods
226 *
227 * @{
228 */
229
230/** copy method for constraint handler plugins (called when SCIP copies plugins) */
231static
232SCIP_DECL_PROPCOPY(propCopyDualfix)
233{ /*lint --e{715}*/
234 assert(scip != NULL);
235 assert(prop != NULL);
236 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
237
238 /* call inclusion method of propagator */
240
241 return SCIP_OKAY;
242}
243
244/** presolving method of propagator */
245static
246SCIP_DECL_PROPPRESOL(propPresolDualfix)
247{ /*lint --e{715}*/
249 SCIP_Bool unbounded;
250 int oldnfixedvars;
251
252 assert(prop != NULL);
253 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
254 assert(result != NULL);
255
257
259 return SCIP_OKAY;
260
261 cutoff = FALSE;
262 unbounded = FALSE;
263 oldnfixedvars = *nfixedvars;
264
265 SCIP_CALL( performDualfix(scip, nfixedvars, &unbounded, &cutoff) );
266
267 /* evaluate propagation result */
268 if( cutoff )
270 else if( unbounded )
272 else if( *nfixedvars > oldnfixedvars )
274 else
276
277 return SCIP_OKAY;
278}
279
280/** execution method of propagator */
281static
282SCIP_DECL_PROPEXEC(propExecDualfix)
283{ /*lint --e{715}*/
284 int nfixedvars;
286 SCIP_Bool unbounded;
287
288 assert(prop != NULL);
289 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
290 assert(result != NULL);
291
293
294 /** @warning Don't run in probing or in repropagation since this can lead to wrong conclusion
295 *
296 * do not run if propagation w.r.t. current objective is not allowed
297 */
299 return SCIP_OKAY;
300
301 cutoff = FALSE;
302 unbounded = FALSE;
303 nfixedvars = 0;
304
305 SCIP_CALL( performDualfix(scip, &nfixedvars, &unbounded, &cutoff) );
306
307 /* evaluate propagation result */
308 if( cutoff )
310 else if( unbounded )
312 else if( nfixedvars > 0 )
314 else
316
317 return SCIP_OKAY;
318}
319
320
321/**@} */
322
323
324/** creates the dual fixing propagator and includes it in SCIP */
326 SCIP* scip /**< SCIP data structure */
327 )
328{
329 SCIP_PROP* prop;
330
331 /* include propagator */
333 assert(prop != NULL);
334
335 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyDualfix) );
337
338 return SCIP_OKAY;
339}
static long bound
#define NULL
Definition def.h:266
#define SCIP_Bool
Definition def.h:91
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define REALABS(x)
Definition def.h:196
#define SCIP_CALL(x)
Definition def.h:373
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_RETCODE SCIPincludePropDualfix(SCIP *scip)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:151
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition scip_prop.c:279
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition prop.c:941
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition scip_prop.c:114
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition scip_tree.c:146
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition var.c:17639
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition var.c:3451
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18143
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition var.c:3440
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17925
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18087
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17418
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18133
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18077
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8399
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:8752
return SCIP_OKAY
SCIP_Bool cutoff
SCIP_Real obj
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
#define PROP_PRESOL_MAXROUNDS
#define PROP_PRESOLTIMING
#define PROP_DESC
#define PROP_NAME
#define PROP_DELAY
#define PROP_TIMING
static SCIP_RETCODE performDualfix(SCIP *scip, int *nfixedvars, SCIP_Bool *unbounded, SCIP_Bool *cutoff)
#define PROP_FREQ
#define PROP_PRIORITY
#define PROP_PRESOL_PRIORITY
fixing roundable variables to best bound
public methods for message output
public methods for propagators
public methods for problem variables
general public methods
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for the probing mode
public methods for propagator plugins
public methods for the branch-and-bound tree
public methods for SCIP variables
@ SCIP_VERBLEVEL_NORMAL
#define SCIP_DECL_PROPCOPY(x)
Definition type_prop.h:61
struct SCIP_Prop SCIP_PROP
Definition type_prop.h:51
#define SCIP_DECL_PROPPRESOL(x)
Definition type_prop.h:193
#define SCIP_DECL_PROPEXEC(x)
Definition type_prop.h:217
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_REDUCEDDOM
Definition type_result.h:51
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_UNBOUNDED
Definition type_result.h:47
@ SCIP_SUCCESS
Definition type_result.h:58
enum SCIP_Retcode SCIP_RETCODE
struct Scip SCIP
Definition type_scip.h:39
@ SCIP_STAGE_PRESOLVING
Definition type_set.h:49
struct SCIP_Var SCIP_VAR
Definition type_var.h:119
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97