Scippy

SCIP

Solving Constraint Integer Programs

heur_guideddiving.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_guideddiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that chooses fixings in direction of incumbent solutions
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/heuristics.h"
35#include "scip/pub_heur.h"
36#include "scip/pub_message.h"
37#include "scip/pub_sol.h"
38#include "scip/pub_var.h"
39#include "scip/scip_heur.h"
40#include "scip/scip_lp.h"
41#include "scip/scip_mem.h"
42#include "scip/scip_numerics.h"
43#include "scip/scip_prob.h"
44#include "scip/scip_sol.h"
45#include <string.h>
46
47#define HEUR_NAME "guideddiving"
48#define HEUR_DESC "LP diving heuristic that chooses fixings in direction of incumbent solutions"
49#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
50#define HEUR_PRIORITY -1007000
51#define HEUR_FREQ 10
52#define HEUR_FREQOFS 7
53#define HEUR_MAXDEPTH -1
54#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
55#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
56#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
57#define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
58
59
60/*
61 * Default parameter settings
62 */
63
64#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
65#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
66#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
67#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
68#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
69 * where diving is performed (0.0: no limit) */
70#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
71 * where diving is performed (0.0: no limit) */
72#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
73#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
74#define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
75#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
76 * more general constraint handler diving variable selection? */
77#define DEFAULT_RANDSEED 127 /**< initial seed for random number generation */
78
79/* locally defined heuristic data */
80struct SCIP_HeurData
81{
82 SCIP_SOL* sol; /**< working solution */
83};
84
85/*
86 * local methods
87 */
88
89/*
90 * Callback methods
91 */
92
93/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
94static
95SCIP_DECL_HEURCOPY(heurCopyGuideddiving)
96{ /*lint --e{715}*/
97 assert(scip != NULL);
98 assert(heur != NULL);
99 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
100
101 /* call inclusion method of primal heuristic */
103
104 return SCIP_OKAY;
105}
106
107/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
108static
109SCIP_DECL_HEURFREE(heurFreeGuideddiving) /*lint --e{715}*/
110{ /*lint --e{715}*/
111 SCIP_HEURDATA* heurdata;
112
113 assert(heur != NULL);
114 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
115 assert(scip != NULL);
116
117 /* free heuristic data */
118 heurdata = SCIPheurGetData(heur);
119 assert(heurdata != NULL);
120
121 SCIPfreeBlockMemory(scip, &heurdata);
122 SCIPheurSetData(heur, NULL);
123
124 return SCIP_OKAY;
125}
126
127
128/** initialization method of primal heuristic (called after problem was transformed) */
129static
130SCIP_DECL_HEURINIT(heurInitGuideddiving) /*lint --e{715}*/
131{ /*lint --e{715}*/
132 SCIP_HEURDATA* heurdata;
133
134 assert(heur != NULL);
135 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
136
137 /* get heuristic data */
138 heurdata = SCIPheurGetData(heur);
139 assert(heurdata != NULL);
140
141 /* create working solution */
142 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
143
144 return SCIP_OKAY;
145}
146
147
148/** deinitialization method of primal heuristic (called before transformed problem is freed) */
149static
150SCIP_DECL_HEUREXIT(heurExitGuideddiving) /*lint --e{715}*/
151{ /*lint --e{715}*/
152 SCIP_HEURDATA* heurdata;
153
154 assert(heur != NULL);
155 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
156
157 /* get heuristic data */
158 heurdata = SCIPheurGetData(heur);
159 assert(heurdata != NULL);
160
161 /* free working solution */
162 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
163
164 return SCIP_OKAY;
165}
166
167
168/** execution method of primal heuristic */
169static
170SCIP_DECL_HEUREXEC(heurExecGuideddiving) /*lint --e{715}*/
171{ /*lint --e{715}*/
172 SCIP_HEURDATA* heurdata;
173 SCIP_DIVESET* diveset;
174
175 assert(heur != NULL);
176 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
177 assert(scip != NULL);
178 assert(result != NULL);
179 assert(SCIPhasCurrentNodeLP(scip));
180
181 *result = SCIP_DIDNOTRUN;
182
183 /* don't dive, if no feasible solutions exist */
184 if( SCIPgetNSols(scip) == 0 )
185 return SCIP_OKAY;
186
187 /* get best solution that should guide the search; if this solution lives in the original variable space,
188 * we cannot use it since it might violate the global bounds of the current problem
189 */
191 return SCIP_OKAY;
192
193 /* get heuristic's data */
194 heurdata = SCIPheurGetData(heur);
195 assert(heurdata != NULL);
196
197 /* if there are no integer variables (note that, e.g., SOS1 variables may be present) */
199 return SCIP_OKAY;
200
201 assert(SCIPheurGetNDivesets(heur) > 0);
202 assert(SCIPheurGetDivesets(heur) != NULL);
203 diveset = SCIPheurGetDivesets(heur)[0];
204 assert(diveset != NULL);
205
206 /* call generic diving algorithm */
207 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
208
209 return SCIP_OKAY;
210}
211
212/* callbacks for diving */
213
214/** calculate score and preferred rounding direction for the candidate variable; the best candidate maximizes the
215 * score
216 */
217static
218SCIP_DECL_DIVESETGETSCORE(divesetGetScoreGuideddiving)
219{
220 SCIP_SOL* bestsol;
221 SCIP_Real bestsolval;
222 SCIP_Real obj;
223 SCIP_Real objnorm;
224 SCIP_Real objgain;
225
226 bestsol = SCIPgetBestSol(scip);
227 assert(bestsol != NULL);
228 assert(!SCIPsolIsOriginal(bestsol));
229
230 bestsolval = SCIPgetSolVal(scip, bestsol, cand);
231
232 /* variable should be rounded (guided) into the direction of its incumbent solution value */
233 if( candsol < bestsolval )
234 *roundup = TRUE;
235 else
236 *roundup = FALSE;
237
238 obj = SCIPvarGetObj(cand);
239 objnorm = SCIPgetObjNorm(scip);
240
241 /* divide by objective norm to normalize obj into [-1,1] */
242 if( SCIPisPositive(scip, objnorm) )
243 obj /= objnorm;
244
245 /* calculate objective gain and fractionality for the selected rounding direction */
246 if( *roundup )
247 {
248 candsfrac = 1.0 - candsfrac;
249 objgain = obj * candsfrac;
250 }
251 else
252 objgain = -obj * candsfrac;
253
254 assert(objgain >= -1.0 && objgain <= 1.0);
255
256 /* penalize too small fractions */
257 if( candsfrac < 0.01 )
258 candsfrac *= 0.1;
259
260 /* prefer decisions on binary variables */
261 if( !SCIPvarIsBinary(cand) )
262 candsfrac *= 0.1;
263
264 /* prefer variables which cannot be rounded by scoring their fractionality */
265 if( !(SCIPvarMayRoundDown(cand) || SCIPvarMayRoundUp(cand)) )
266 *score = -candsfrac;
267 else
268 *score = -2.0 - objgain;
269
270 return SCIP_OKAY;
271}
272
273/** callback to check preconditions for diving, e.g., if an incumbent solution is available */
274static
275SCIP_DECL_DIVESETAVAILABLE(divesetAvailableGuideddiving)
276{
277 /* don't dive with guided diving if no feasible solutions exists or
278 * if this solution lives in the original variable space,
279 * because it might violate the global bounds of the current problem
280 */
282 *available = FALSE;
283 else
284 *available = TRUE;
285
286 return SCIP_OKAY;
287}
288
289/*
290 * heuristic specific interface methods
291 */
292
293/** creates the guideddiving heuristic and includes it in SCIP */
295 SCIP* scip /**< SCIP data structure */
296 )
297{
298 SCIP_HEURDATA* heurdata;
299 SCIP_HEUR* heur;
300
301 /* create Guideddiving primal heuristic data */
302 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
303
304 /* include primal heuristic */
307 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGuideddiving, heurdata) );
308
309 assert(heur != NULL);
310
311 /* set non-NULL pointers to callback methods */
312 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGuideddiving) );
313 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGuideddiving) );
314 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGuideddiving) );
315 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGuideddiving) );
316
317 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
321 divesetGetScoreGuideddiving, divesetAvailableGuideddiving) );
322
323 return SCIP_OKAY;
324}
#define NULL
Definition: def.h:267
#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
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition: scip_prob.c:1641
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_RETCODE SCIPincludeHeurGuideddiving(SCIP *scip)
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool ispublic, SCIP_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)))
Definition: scip_heur.c:318
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
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1661
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1651
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2721
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3451
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3440
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_LPRESOLVEDOMCHGQUOT
static SCIP_DECL_HEURCOPY(heurCopyGuideddiving)
#define HEUR_TIMING
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
#define DEFAULT_BACKTRACK
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
static SCIP_DECL_HEUREXIT(heurExitGuideddiving)
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
#define HEUR_NAME
static SCIP_DECL_DIVESETAVAILABLE(divesetAvailableGuideddiving)
#define DEFAULT_RANDSEED
#define DIVESET_DIVETYPES
static SCIP_DECL_HEURFREE(heurFreeGuideddiving)
static SCIP_DECL_HEUREXEC(heurExecGuideddiving)
#define DIVESET_ISPUBLIC
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
static SCIP_DECL_HEURINIT(heurInitGuideddiving)
#define HEUR_USESSUBSCIP
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreGuideddiving)
LP diving heuristic that chooses fixings in direction of incumbent solutions.
methods commonly used by primal heuristics
public methods for primal heuristics
public methods for message output
public methods for primal CIP solutions
public methods for problem variables
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for solutions
SCIP_SOL * sol
Definition: struct_heur.h:71
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_DIVECONTEXT_SINGLE
Definition: type_heur.h:69
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63