Scippy

SCIP

Solving Constraint Integer Programs

heur_fixandinfer.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 heur_fixandinfer.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief fix-and-infer primal heuristic
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/pub_heur.h"
35#include "scip/pub_message.h"
36#include "scip/pub_var.h"
37#include "scip/scip_branch.h"
38#include "scip/scip_general.h"
39#include "scip/scip_heur.h"
40#include "scip/scip_mem.h"
41#include "scip/scip_message.h"
42#include "scip/scip_numerics.h"
43#include "scip/scip_param.h"
44#include "scip/scip_prob.h"
45#include "scip/scip_probing.h"
46#include "scip/scip_sol.h"
47#include "scip/scip_tree.h"
48#include "scip/scip_var.h"
49#include <string.h>
50
51#define HEUR_NAME "fixandinfer"
52#define HEUR_DESC "iteratively fixes variables and propagates inferences"
53#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
54#define HEUR_PRIORITY -500000
55#define HEUR_FREQ -1 /* at the moment, the heuristic seems to be useless */
56#define HEUR_FREQOFS 0
57#define HEUR_MAXDEPTH -1
58#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
59#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
60
61#define MAXDIVEDEPTH 100
62
63
64/*
65 * Default parameter settings
66 */
67
68#define DEFAULT_PROPROUNDS 0 /**< maximal number of propagation rounds in probing subproblems */
69#define DEFAULT_MINFIXINGS 100 /**< minimal number of fixings to apply before dive may be aborted */
70
71
72/*
73 * Data structures
74 */
75
76/** primal heuristic data */
77struct SCIP_HeurData
78{
79 int proprounds; /**< maximal number of propagation rounds in probing subproblems */
80 int minfixings; /**< minimal number of fixings to apply before dive may be aborted */
81};
82
83
84/*
85 * Local methods
86 */
87
88/** selects a variable and fixes it to its current pseudo solution value */
89static
91 SCIP* scip, /**< SCIP data structure */
92 SCIP_VAR** pseudocands, /**< array of unfixed variables */
93 int npseudocands, /**< number of unfixed variables */
94 SCIP_Real large /**< large value to be used instead of infinity */
95 )
96{
97 SCIP_VAR* var;
98 SCIP_Real bestscore;
99 SCIP_Real score;
100 SCIP_Real solval;
101 int bestcand;
102 int ncands;
103 int c;
104
105 assert(pseudocands != NULL);
106 assert(npseudocands > 0);
107
108 /* if existing, choose one of the highest priority binary variables; if no high priority binary variables
109 * exist, choose a variable among all unfixed integral variables
110 */
112 if( ncands == 0 )
113 ncands = npseudocands;
114
115 /* select variable to tighten the domain for */
116 bestscore = -SCIPinfinity(scip);
117 bestcand = -1;
118 for( c = 0; c < ncands; ++c )
119 {
120 score = SCIPgetVarAvgInferenceScore(scip, pseudocands[c]);
121 if( score > bestscore )
122 {
123 bestscore = score;
124 bestcand = c;
125 }
126 }
127 assert(bestcand != -1);
128
129 /* fix variable to its current pseudo solution value */
130 var = pseudocands[bestcand];
131 solval = SCIPgetVarSol(scip, var);
132
133 /* adapt solution value if it is infinite */
134 if( SCIPisInfinity(scip, solval) )
135 {
136 SCIP_Real lb;
138 lb = SCIPvarGetLbLocal(var);
139
140 /* adapt fixing value by changing it to a large value */
141 if( SCIPisInfinity(scip, -lb) )
142 solval = SCIPceil(scip, large);
143 else if( !SCIPisInfinity(scip, SCIPceil(scip, lb+large)) )
144 solval = SCIPceil(scip, lb+large);
145 }
146 else if( SCIPisInfinity(scip, -solval) )
147 {
148 SCIP_Real ub;
149 assert(SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)));
150 ub = SCIPvarGetUbLocal(var);
151
152 /* adapt fixing value by changing it to a large negative value */
153 if( SCIPisInfinity(scip, ub) )
154 solval = SCIPfloor(scip, -large);
155 else if( !SCIPisInfinity(scip, -SCIPfloor(scip, ub-large)) )
156 solval = SCIPfloor(scip, ub-large);
157 }
158
159 assert(SCIPisFeasIntegral(scip, solval)); /* in probing, we always have the pseudo solution */
160 SCIPdebugMsg(scip, " -> fixed variable <%s>[%g,%g] = %g (%d candidates left)\n",
161 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), solval, npseudocands - 1);
162 SCIP_CALL( SCIPfixVarProbing(scip, var, solval) );
163
164 return SCIP_OKAY;
165}
166
167
168/*
169 * Callback methods of primal heuristic
170 */
171
172/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
173static
174SCIP_DECL_HEURCOPY(heurCopyFixandinfer)
175{ /*lint --e{715}*/
176 assert(scip != NULL);
177 assert(heur != NULL);
178 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
179
180 /* call inclusion method of primal heuristic */
182
183 return SCIP_OKAY;
184}
185
186/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
187static
188SCIP_DECL_HEURFREE(heurFreeFixandinfer) /*lint --e{715}*/
189{ /*lint --e{715}*/
190 SCIP_HEURDATA* heurdata;
191
192 /* free heuristic data */
193 heurdata = SCIPheurGetData(heur);
194 assert(heurdata != NULL);
195 SCIPfreeBlockMemory(scip, &heurdata);
196 SCIPheurSetData(heur, NULL);
197
198 return SCIP_OKAY;
199}
200
201
202/** execution method of primal heuristic */
203static
204SCIP_DECL_HEUREXEC(heurExecFixandinfer)
205{ /*lint --e{715}*/
206 SCIP_HEURDATA* heurdata;
207 SCIP_VAR** cands;
208 int ncands;
209 int startncands;
210 int divedepth;
211 SCIP_Bool cutoff;
212 SCIP_Real large;
213
214 *result = SCIP_DIDNOTRUN;
215
216 /* do not call heuristic of node was already detected to be infeasible */
217 if( nodeinfeasible )
218 return SCIP_OKAY;
219
220 /* we cannot run on problems with continuous variables */
221 if( SCIPgetNContVars(scip) > 0 )
222 return SCIP_OKAY;
223
224 /* get unfixed variables */
225 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
226 if( ncands == 0 )
227 return SCIP_OKAY;
228
229 /* get heuristic data */
230 heurdata = SCIPheurGetData(heur);
231 assert(heurdata != NULL);
232
233 /* fix variables and propagate inferences as long as the problem is still feasible and there are
234 * unfixed integral variables
235 */
236 cutoff = FALSE;
237 divedepth = 0;
238 startncands = ncands;
239
240 /* start probing */
242
244 {
246 return SCIP_OKAY;
247 }
248
249 SCIPdebugMsg(scip, "starting fix-and-infer heuristic with %d unfixed integral variables\n", ncands);
250
251 *result = SCIP_DIDNOTFIND;
252
253 /* create next probing node */
255
256 /* determine large value to set variables to */
257 large = SCIPinfinity(scip);
258 if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
259 large = 0.1 / SCIPfeastol(scip);
260
261 while( !cutoff && ncands > 0
262 && (divedepth < heurdata->minfixings || (startncands - ncands) * 2 * MAXDIVEDEPTH >= startncands * divedepth)
263 && !SCIPisStopped(scip) )
264 {
265 divedepth++;
266
267 /* fix next variable */
268 SCIP_CALL( fixVariable(scip, cands, ncands, large) );
269
270 /* propagate the fixing */
271 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->proprounds, &cutoff, NULL) );
272
273 /* get remaining unfixed variables */
274 if( !cutoff )
275 {
276 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
277 }
278 }
279
280 /* check, if we are still feasible */
281 if( cutoff )
282 {
283 SCIPdebugMsg(scip, "propagation detected a cutoff\n");
284 }
285 else if( ncands == 0 )
286 {
287 SCIP_Bool success;
288
289 success = FALSE;
290
291 /* try to add solution to SCIP */
292 SCIP_CALL( SCIPtryCurrentSol(scip, heur, FALSE, FALSE, FALSE, TRUE, &success) );
293
294 if( success )
295 {
296 SCIPdebugMsg(scip, "found primal feasible solution\n");
297 *result = SCIP_FOUNDSOL;
298 }
299 else
300 {
301 SCIPdebugMsg(scip, "primal solution was rejected\n");
302 }
303 }
304 else
305 {
306 SCIPdebugMsg(scip, "probing was aborted (probing depth: %d, fixed: %d/%d)", divedepth, startncands - ncands, startncands);
307 }
308
309 /* end probing */
311
312 return SCIP_OKAY;
313}
314
315
316/*
317 * primal heuristic specific interface methods
318 */
319
320/** creates the fix-and-infer primal heuristic and includes it in SCIP */
322 SCIP* scip /**< SCIP data structure */
323 )
324{
325 SCIP_HEURDATA* heurdata;
326 SCIP_HEUR* heur;
327
328 /* create Fixandinfer primal heuristic data */
329 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
330
331 /* include primal heuristic */
334 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFixandinfer, heurdata) );
335
336 assert(heur != NULL);
337
338 /* set non-NULL pointers to callback methods */
339 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFixandinfer) );
340 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFixandinfer) );
341
342 /* fixandinfer heuristic parameters */
344 "heuristics/fixandinfer/proprounds",
345 "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
346 &heurdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
348 "heuristics/fixandinfer/minfixings",
349 "minimal number of fixings to apply before dive may be aborted",
350 &heurdata->minfixings, TRUE, DEFAULT_MINFIXINGS, 0, INT_MAX, NULL, NULL) );
351
352 return SCIP_OKAY;
353}
#define NULL
Definition: def.h:267
#define SCIP_MAXTREEDEPTH
Definition: def.h:316
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPincludeHeurFixandinfer(SCIP *scip)
int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:795
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:418
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
SCIP_RETCODE SCIPtryCurrentSol(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3146
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9473
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2307
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
#define HEUR_TIMING
static SCIP_DECL_HEURFREE(heurFreeFixandinfer)
#define HEUR_FREQOFS
#define HEUR_DESC
static SCIP_DECL_HEUREXEC(heurExecFixandinfer)
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_PROPROUNDS
#define HEUR_NAME
#define DEFAULT_MINFIXINGS
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
#define MAXDIVEDEPTH
static SCIP_DECL_HEURCOPY(heurCopyFixandinfer)
static SCIP_RETCODE fixVariable(SCIP *scip, SCIP_VAR **pseudocands, int npseudocands, SCIP_Real large)
fix-and-infer primal heuristic
public methods for primal heuristics
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63