SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_fracdiving.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_fracdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that chooses fixings w.r.t. the fractionalities
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_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 <string.h>
45
46#define HEUR_NAME "fracdiving"
47#define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the fractionalities"
48#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
49#define HEUR_PRIORITY -1003000
50#define HEUR_FREQ 10
51#define HEUR_FREQOFS 3
52#define HEUR_MAXDEPTH -1
53#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
54#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
55#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
56#define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
57
58
59/*
60 * Default parameter settings
61 */
62
63#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
64#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
65#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
66#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
67#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
68 * where diving is performed (0.0: no limit) */
69#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
70 * where diving is performed (0.0: no limit) */
71#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
72#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
73#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
74
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 FALSE /**< should only LP branching candidates be considered instead of the slower but
78 * more general constraint handler diving variable selection? */
79#define DEFAULT_RANDSEED 89 /**< initial random seed */
80
81/* locally defined heuristic data */
82struct SCIP_HeurData
83{
84 SCIP_SOL* sol; /**< working solution */
85};
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(heurCopyFracdiving)
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(heurFreeFracdiving) /*lint --e{715}*/
113{ /*lint --e{715}*/
115
116 assert(heur != NULL);
117 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
119
120 /* free heuristic data */
123
126
127 return SCIP_OKAY;
128}
129
130
131/** initialization method of primal heuristic (called after problem was transformed) */
132static
133SCIP_DECL_HEURINIT(heurInitFracdiving) /*lint --e{715}*/
134{ /*lint --e{715}*/
136
137 assert(heur != NULL);
138 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
139
140 /* get heuristic data */
142 assert(heurdata != NULL);
143
144 /* create working solution */
146
147 return SCIP_OKAY;
148}
149
150
151/** deinitialization method of primal heuristic (called before transformed problem is freed) */
152static
153SCIP_DECL_HEUREXIT(heurExitFracdiving) /*lint --e{715}*/
154{ /*lint --e{715}*/
156
157 assert(heur != NULL);
158 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
159
160 /* get heuristic data */
162 assert(heurdata != NULL);
163
164 /* free working solution */
166
167 return SCIP_OKAY;
168}
169
170
171/** execution method of primal heuristic */
172static
173SCIP_DECL_HEUREXEC(heurExecFracdiving) /*lint --e{715}*/
174{ /*lint --e{715}*/
177
179 assert(heurdata != NULL);
180
183 diveset = SCIPheurGetDivesets(heur)[0];
185
187
189
190 return SCIP_OKAY;
191}
192
193/** calculate score and preferred rounding direction for the candidate variable; the best candidate maximizes the
194 * score
195 */
196static
197SCIP_DECL_DIVESETGETSCORE(divesetGetScoreFracdiving)
198{
199 SCIP_Real obj;
200 SCIP_Real objnorm;
201 SCIP_Real objgain;
202 SCIP_Bool mayrounddown;
203 SCIP_Bool mayroundup;
204
205 /* score fractionality if candidate is an SOS1 variable */
206 if ( divetype == SCIP_DIVETYPE_SOS1VARIABLE )
207 {
208 *score = candsfrac;
209
210 /* 'round' in nonzero direction, i.e., fix the candidates neighbors in the conflict graph to zero */
211 *roundup = SCIPisFeasPositive(scip, candsol);
212
213 return SCIP_OKAY;
214 }
215
218
219 /* choose rounding direction:
220 * - if variable may be rounded in either both or neither direction, round corresponding to the fractionality
221 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
222 * the current fractional solution
223 */
224 if( mayrounddown != mayroundup )
226 /* try to avoid variability; decide randomly if the LP solution can contain some noise. */
227 else if( SCIPisEQ(scip, candsfrac, 0.5) )
229 else
230 *roundup = (candsfrac > 0.5);
231
232 obj = SCIPvarGetObj(cand);
233 objnorm = SCIPgetObjNorm(scip);
234
235 /* divide by objective norm to normalize obj into [-1,1] */
236 if( SCIPisPositive(scip, objnorm) )
237 obj /= objnorm;
238
239 /* calculate objective gain and fractionality for the selected rounding direction */
240 if( *roundup )
241 {
242 candsfrac = 1.0 - candsfrac;
243 objgain = obj * candsfrac;
244 }
245 else
246 objgain = -obj * candsfrac;
247
248 assert(objgain >= -1.0 && objgain <= 1.0);
249
250 /* penalize too small fractions */
251 if( SCIPisEQ(scip, candsfrac, 0.01) )
252 {
253 /* try to avoid variability; decide randomly if the LP solution can contain some noise.
254 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
255 */
257 candsfrac += 10.0;
258 }
259 else if( candsfrac < 0.01 )
260 candsfrac += 10.0;
261
262 /* prefer decisions on binary variables */
263 if( !SCIPvarIsBinary(cand) )
264 candsfrac *= 1000.0;
265
266 /* prefer variables which cannot be rounded by scoring their fractionality */
267 if( !(mayrounddown || mayroundup) )
268 *score = -candsfrac;
269 else
270 *score = -2.0 - objgain;
271
272 return SCIP_OKAY;
273}
274
275#define divesetAvailableFracdiving NULL
276
277/*
278 * heuristic specific interface methods
279 */
280
281/** creates the fracdiving heuristic and includes it in SCIP */
283 SCIP* scip /**< SCIP data structure */
284 )
285{
287 SCIP_HEUR* heur;
288
289 /* create Fracdiving primal heuristic data */
291
292 /* include primal heuristic */
295 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFracdiving, heurdata) );
296
297 assert(heur != NULL);
298
299 /* set non-NULL pointers to callback methods */
300 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFracdiving) );
301 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFracdiving) );
302 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitFracdiving) );
303 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitFracdiving) );
304
305 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
310 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreFracdiving, divesetAvailableFracdiving) );
311
312 return SCIP_OKAY;
313}
314
#define NULL
Definition def.h:267
#define SCIP_PROBINGSCORE_PENALTYRATIO
Definition def.h:322
#define SCIP_CALL(x)
Definition def.h:374
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition scip_prob.c:1641
SCIP_RETCODE SCIPincludeHeurFracdiving(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)),)
Definition scip_heur.c:318
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition heur.c:720
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition heur.c:1661
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
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
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(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 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
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10108
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
* result
#define DEFAULT_LPRESOLVEDOMCHGQUOT
SCIPheurSetData(heur, NULL)
#define HEUR_TIMING
return SCIP_OKAY
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE))
#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
SCIPfreeSol(scip, &heurdata->sol))
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define HEUR_NAME
#define DEFAULT_RANDSEED
#define DIVESET_DIVETYPES
#define divesetAvailableFracdiving
#define DIVESET_ISPUBLIC
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
#define HEUR_USESSUBSCIP
static SCIP_DIVESET * diveset
SCIPcreateSol(scip, &heurdata->sol, heur))
LP diving heuristic that chooses fixings w.r.t. the fractionalities.
static SCIP_SOL * sol
SCIP_Real obj
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Bool mayrounddown
SCIP_Bool mayroundup
SCIP_Bool roundup
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
SCIP_SOL * sol
Definition struct_heur.h:71
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:121
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_DIVESETGETSCORE(x)
Definition type_heur.h:184
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
#define SCIP_DIVETYPE_SOS1VARIABLE
Definition type_heur.h:61
@ SCIP_DIVECONTEXT_SINGLE
Definition type_heur.h:69
@ SCIP_DIDNOTRUN
Definition type_result.h:42
enum SCIP_Retcode SCIP_RETCODE