Scippy

SCIP

Solving Constraint Integer Programs

heur_linesearchdiving.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_linesearchdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that fixes variables with a large difference to their root solution
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#include "scip/heuristics.h"
35#include "scip/pub_heur.h"
36#include "scip/pub_message.h"
37#include "scip/pub_var.h"
38#include "scip/scip_heur.h"
39#include "scip/scip_mem.h"
40#include "scip/scip_numerics.h"
41#include "scip/scip_sol.h"
42#include <string.h>
43
44#define HEUR_NAME "linesearchdiving"
45#define HEUR_DESC "LP diving heuristic that chooses fixings following the line from root solution to current solution"
46#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
47#define HEUR_PRIORITY -1006000
48#define HEUR_FREQ 10
49#define HEUR_FREQOFS 6
50#define HEUR_MAXDEPTH -1
51#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
52#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
53#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
54#define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
55
56
57/*
58 * Default parameter settings
59 */
60
61#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
62#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
63#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
64#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
65#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
66 * where diving is performed (0.0: no limit) */
67#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
68 * where diving is performed (0.0: no limit) */
69#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
70#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
71#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
72#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
73#define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
74#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
75 * more general constraint handler diving variable selection? */
76#define DEFAULT_RANDSEED 137 /**< default initialization for random seed number generation */
77/*
78 * Data structures
79 */
80
81/** primal heuristic data */
82struct SCIP_HeurData
83{
84 SCIP_SOL* sol; /**< working solution */
85};
86
87
88/*
89 * Local methods
90 */
91
92
93/*
94 * Callback methods of primal heuristic
95 */
96
97/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
98static
99SCIP_DECL_HEURCOPY(heurCopyLinesearchdiving)
100{ /*lint --e{715}*/
101 assert(scip != NULL);
102 assert(heur != NULL);
103 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
104
105 /* call inclusion method of primal heuristic */
107
108 return SCIP_OKAY;
109}
110
111/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
112static
113SCIP_DECL_HEURFREE(heurFreeLinesearchdiving)
114{ /*lint --e{715}*/
115 SCIP_HEURDATA* heurdata;
116
117 assert(heur != NULL);
118 assert(scip != NULL);
119
120 /* free heuristic data */
121 heurdata = SCIPheurGetData(heur);
122 assert(heurdata != NULL);
123 SCIPfreeBlockMemory(scip, &heurdata);
124 SCIPheurSetData(heur, NULL);
125
126 return SCIP_OKAY;
127}
128
129
130/** initialization method of primal heuristic (called after problem was transformed) */
131static
132SCIP_DECL_HEURINIT(heurInitLinesearchdiving)
133{ /*lint --e{715}*/
134 SCIP_HEURDATA* heurdata;
135
136 assert(heur != NULL);
137
138 /* get heuristic data */
139 heurdata = SCIPheurGetData(heur);
140 assert(heurdata != NULL);
141
142 /* create working solution */
143 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
144
145 return SCIP_OKAY;
146}
147
148
149/** deinitialization method of primal heuristic (called before transformed problem is freed) */
150static
151SCIP_DECL_HEUREXIT(heurExitLinesearchdiving)
152{ /*lint --e{715}*/
153 SCIP_HEURDATA* heurdata;
154
155 assert(heur != NULL);
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(heurExecLinesearchdiving)
171{ /*lint --e{715}*/
172 SCIP_HEURDATA* heurdata;
173 SCIP_DIVESET* diveset;
174
175 heurdata = SCIPheurGetData(heur);
176 assert(SCIPheurGetNDivesets(heur) > 0);
177 assert(SCIPheurGetDivesets(heur) != NULL);
178 diveset = SCIPheurGetDivesets(heur)[0];
179 assert(diveset != NULL);
180
181 *result = SCIP_DIDNOTRUN;
182
183 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
184
185 return SCIP_OKAY;
186}
187
188/* diving setting callbacks */
189
190/** returns a score for the given candidate -- the best candidate maximizes the diving score */
191static
192SCIP_DECL_DIVESETGETSCORE(divesetGetScoreLinesearchdiving)
193{ /*lint --e{715}*/
194 SCIP_Real rootsolval;
195 SCIP_Real distquot;
196
197 rootsolval = SCIPvarGetRootSol(cand);
198
199 /* preferred branching direction is further away from the root LP solution */
200 if( SCIPisLT(scip, candsol, rootsolval) )
201 {
202 /* round down*/
203 *roundup = FALSE;
204
205 switch( divetype )
206 {
208 distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol);
209 break;
211 if ( SCIPisFeasPositive(scip, candsol) )
212 distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol);
213 else
214 distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval);
215 break;
216 default:
217 SCIPerrorMessage("Error: Unsupported diving type\n");
218 SCIPABORT();
219 return SCIP_INVALIDDATA; /*lint !e527*/
220 } /*lint !e788*/
221
222 /* avoid roundable candidates */
223 if( SCIPvarMayRoundDown(cand) )
224 distquot *= 1000.0;
225 }
226 else if( SCIPisGT(scip, candsol, rootsolval) )
227 {
228 /* round up */
229 switch( divetype )
230 {
232 distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval);
233 break;
235 if ( SCIPisFeasPositive(scip, candsol) )
236 distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval);
237 else
238 distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol);
239 break;
240 default:
241 SCIPerrorMessage("Error: Unsupported diving type\n");
242 SCIPABORT();
243 return SCIP_INVALIDDATA; /*lint !e527*/
244 } /*lint !e788*/
245
246 /* avoid roundable candidates */
247 if( SCIPvarMayRoundUp(cand) )
248 distquot *= 1000.0;
249 *roundup = TRUE;
250 }
251 else
252 {
253 /* if the solution values are equal, we arbitrarily select branching downwards;
254 * candidates with equal LP solution values are penalized with an infinite score
255 */
256 *roundup = FALSE;
257 distquot = SCIPinfinity(scip);
258 }
259
260 *score = -distquot;
261
262 return SCIP_OKAY;
263}
264
265#define divesetAvailableLinesearchdiving NULL
266
267/*
268 * primal heuristic specific interface methods
269 */
270
271/** creates the linesearchdiving primal heuristic and includes it in SCIP */
273 SCIP* scip /**< SCIP data structure */
274 )
275{
276 SCIP_HEURDATA* heurdata;
277 SCIP_HEUR* heur;
278
279 /* create Linesearchdiving primal heuristic data */
280 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
281
282 /* include primal heuristic */
285 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLinesearchdiving, heurdata) );
286
287 assert(heur != NULL);
288
289 /* set non-NULL pointers to callback methods */
290 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLinesearchdiving) );
291 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLinesearchdiving) );
292 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLinesearchdiving) );
293 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitLinesearchdiving) );
294
295 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
300 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreLinesearchdiving, divesetAvailableLinesearchdiving) );
301
302 return SCIP_OKAY;
303}
#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 SCIPABORT()
Definition: def.h:346
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPincludeHeurLinesearchdiving(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
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
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
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_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3451
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3440
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13350
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
static SCIP_DECL_HEURINIT(heurInitLinesearchdiving)
#define DEFAULT_LPRESOLVEDOMCHGQUOT
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreLinesearchdiving)
#define HEUR_TIMING
#define divesetAvailableLinesearchdiving
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
static SCIP_DECL_HEUREXEC(heurExecLinesearchdiving)
static SCIP_DECL_HEURCOPY(heurCopyLinesearchdiving)
static SCIP_DECL_HEURFREE(heurFreeLinesearchdiving)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define HEUR_NAME
#define DEFAULT_RANDSEED
#define DIVESET_DIVETYPES
#define DIVESET_ISPUBLIC
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
static SCIP_DECL_HEUREXIT(heurExitLinesearchdiving)
#define HEUR_USESSUBSCIP
LP diving heuristic that fixes variables with a large difference to their root solution.
methods commonly used by primal heuristics
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public methods for problem variables
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for numerical tolerances
public methods for solutions
SCIP_SOL * sol
Definition: struct_heur.h:71
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
#define SCIP_DIVETYPE_SOS1VARIABLE
Definition: type_heur.h:61
#define SCIP_DIVETYPE_INTEGRALITY
Definition: type_heur.h:60
@ SCIP_DIVECONTEXT_SINGLE
Definition: type_heur.h:69
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63