Scippy

SCIP

Solving Constraint Integer Programs

heur_pscostdiving.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_pscostdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that chooses fixings w.r.t. the pseudo cost values
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_misc.h"
38#include "scip/pub_var.h"
39#include "scip/scip_heur.h"
40#include "scip/scip_mem.h"
41#include "scip/scip_numerics.h"
42#include "scip/scip_prob.h"
43#include "scip/scip_sol.h"
44#include "scip/scip_var.h"
45#include <string.h>
46
47#define HEUR_NAME "pscostdiving"
48#define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the pseudo cost values"
49#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
50#define HEUR_PRIORITY -1002000
51#define HEUR_FREQ 10
52#define HEUR_FREQOFS 2
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_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
73#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
74#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
75#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
76#define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
77#define DEFAULT_ONLYLPBRANCHCANDS TRUE /**< should only LP branching candidates be considered instead of the slower but
78 * more general constraint handler diving variable selection? */
79#define DEFAULT_RANDSEED 103 /**< initial random seed */
80
81
82/* locally defined heuristic data */
83struct SCIP_HeurData
84{
85 SCIP_SOL* sol; /**< working solution */
86};
87
88/*
89 * local methods
90 */
91
92/*
93 * Callback methods
94 */
95
96/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
97static
98SCIP_DECL_HEURCOPY(heurCopyPscostdiving)
99{ /*lint --e{715}*/
100 assert(scip != NULL);
101 assert(heur != NULL);
102 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
103
104 /* call inclusion method of primal heuristic */
106
107 return SCIP_OKAY;
108}
109
110/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
111static
112SCIP_DECL_HEURFREE(heurFreePscostdiving) /*lint --e{715}*/
113{ /*lint --e{715}*/
114 SCIP_HEURDATA* heurdata;
115
116 assert(heur != NULL);
117 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
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(heurInitPscostdiving) /*lint --e{715}*/
133{ /*lint --e{715}*/
134 SCIP_HEURDATA* heurdata;
135
136 assert(heur != NULL);
137 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
138
139 /* get heuristic data */
140 heurdata = SCIPheurGetData(heur);
141 assert(heurdata != NULL);
142
143 /* create working solution */
144 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
145
146 return SCIP_OKAY;
147}
148
149
150/** deinitialization method of primal heuristic (called before transformed problem is freed) */
151static
152SCIP_DECL_HEUREXIT(heurExitPscostdiving) /*lint --e{715}*/
153{ /*lint --e{715}*/
154 SCIP_HEURDATA* heurdata;
155
156 assert(heur != NULL);
157 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
158
159 /* get heuristic data */
160 heurdata = SCIPheurGetData(heur);
161 assert(heurdata != NULL);
162
163 /* free working solution */
164 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
165
166 return SCIP_OKAY;
167}
168
169/** execution method of primal heuristic */
170static
171SCIP_DECL_HEUREXEC(heurExecPscostdiving) /*lint --e{715}*/
172{ /*lint --e{715}*/
173 SCIP_HEURDATA* heurdata;
174 SCIP_DIVESET* diveset;
175
176 heurdata = SCIPheurGetData(heur);
177 assert(heurdata != NULL);
178 assert(SCIPheurGetNDivesets(heur) > 0);
179 assert(SCIPheurGetDivesets(heur) != NULL);
180 diveset = SCIPheurGetDivesets(heur)[0];
181 assert(diveset != NULL);
182
183 *result = SCIP_DIDNOTRUN;
184
185 /* terminate if there are no integer variables (note that, e.g., SOS1 variables may be present) */
187 return SCIP_OKAY;
188
189 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
190
191 return SCIP_OKAY;
192}
193
194
195/** returns a score for the given candidate -- the best candidate maximizes the diving score */
196static
197SCIP_DECL_DIVESETGETSCORE(divesetGetScorePscostdiving)
198{
199 SCIP_Real pscostdown;
200 SCIP_Real pscostup;
201 SCIP_Real pscostquot;
202
203 SCIP_Bool mayrounddown;
204 SCIP_Bool mayroundup;
205
206 mayrounddown = SCIPvarMayRoundDown(cand);
207 mayroundup = SCIPvarMayRoundUp(cand);
208
209 /* bound fractions to not prefer variables that are nearly integral */
210 candsfrac = MAX(candsfrac, 0.1);
211 candsfrac = MIN(candsfrac, 0.9);
212
213 pscostdown = SCIPgetVarPseudocostVal(scip, cand, 0.0 - candsfrac);
214 pscostup = SCIPgetVarPseudocostVal(scip, cand, 1.0 - candsfrac);
215
216 /* determine the candidate direction. if the variable may be trivially rounded in one direction, take the other direction;
217 * otherwise, consider first the direction from the root solution, second the candidate fractionality, and
218 * last the direction of smaller pseudo costs
219 *
220 * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or
221 * round down if the values to compare are equal within tolerances.
222 */
223 assert(pscostdown >= 0.0 && pscostup >= 0.0);
224 if( mayrounddown != mayroundup )
225 *roundup = mayrounddown;
226 else if( SCIPisLT(scip, candsol, SCIPvarGetRootSol(cand) - 0.4)
227 || (SCIPisEQ(scip, candsol, SCIPvarGetRootSol(cand) - 0.4) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
228 *roundup = FALSE;
229 else if( SCIPisGT(scip, candsol, SCIPvarGetRootSol(cand) + 0.4)
230 || (SCIPisEQ(scip, candsol, SCIPvarGetRootSol(cand) + 0.4) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
231 *roundup = TRUE;
232 else if( SCIPisLT(scip, candsfrac, 0.3)
233 || (SCIPisEQ(scip, candsfrac, 0.3) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
234 *roundup = FALSE;
235 else if( SCIPisGT(scip, candsfrac, 0.7)
236 || (SCIPisEQ(scip, candsfrac, 0.7) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
237 *roundup = TRUE;
238 else if( SCIPisEQ(scip, pscostdown, pscostup) )
239 *roundup = (SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0);
240 else if( pscostdown > pscostup )
241 *roundup = TRUE;
242 else
243 *roundup = FALSE;
244
245 if( *roundup )
246 pscostquot = sqrt(candsfrac) * (1.0 + pscostdown) / (1.0 + pscostup);
247 else
248 pscostquot = sqrt(1.0 - candsfrac) * (1.0 + pscostup) / (1.0 + pscostdown);
249
250 /* prefer decisions on binary variables */
251 if( SCIPvarIsBinary(cand) && !(SCIPvarMayRoundDown(cand) || SCIPvarMayRoundUp(cand)))
252 pscostquot *= 1000.0;
253
254 assert(pscostquot >= 0);
255 *score = pscostquot;
256
257 return SCIP_OKAY;
258}
259
260#define divesetAvailablePscostdiving NULL
261
262/*
263 * heuristic specific interface methods
264 */
265
266/** creates the pscostdiving heuristic and includes it in SCIP */
268 SCIP* scip /**< SCIP data structure */
269 )
270{
271 SCIP_HEURDATA* heurdata;
272 SCIP_HEUR* heur;
273
274 /* create Pscostdiving primal heuristic data */
275 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
276
277 /* include primal heuristic */
280 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecPscostdiving, heurdata) );
281
282 assert(heur != NULL);
283
284 /* set non-NULL pointers to callback methods */
285 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyPscostdiving) );
286 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreePscostdiving) );
287 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitPscostdiving) );
288 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitPscostdiving) );
289
290 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
294 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScorePscostdiving, divesetAvailablePscostdiving) );
295
296 return SCIP_OKAY;
297}
298
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_RETCODE SCIPincludeHeurPscostdiving(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_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:720
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_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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 SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13350
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8814
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define HEUR_TIMING
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
static SCIP_DECL_DIVESETGETSCORE(divesetGetScorePscostdiving)
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
static SCIP_DECL_HEURCOPY(heurCopyPscostdiving)
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
#define divesetAvailablePscostdiving
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
static SCIP_DECL_HEURINIT(heurInitPscostdiving)
#define HEUR_NAME
static SCIP_DECL_HEUREXIT(heurExitPscostdiving)
#define DEFAULT_RANDSEED
#define DIVESET_DIVETYPES
#define DIVESET_ISPUBLIC
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
#define HEUR_USESSUBSCIP
static SCIP_DECL_HEURFREE(heurFreePscostdiving)
static SCIP_DECL_HEUREXEC(heurExecPscostdiving)
LP diving heuristic that chooses fixings w.r.t. the pseudo cost values.
methods commonly used by primal heuristics
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
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 global and local (sub)problems
public methods for solutions
public methods for SCIP variables
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