Scippy

SCIP

Solving Constraint Integer Programs

heur_coefdiving.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_coefdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that chooses fixings w.r.t. the matrix coefficients
28 * @author Tobias Achterberg
29 * @author Marc Pfetsch
30 *
31 * Indicator constraints are taken into account if present.
32 */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
37#include "scip/heuristics.h"
38#include "scip/pub_heur.h"
39#include "scip/pub_message.h"
40#include "scip/pub_misc.h"
41#include "scip/pub_var.h"
42#include "scip/scip_heur.h"
43#include "scip/scip_lp.h"
44#include "scip/scip_mem.h"
45#include "scip/scip_numerics.h"
46#include "scip/scip_sol.h"
47#include <string.h>
48
49#define HEUR_NAME "coefdiving"
50#define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the matrix coefficients"
51#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
52#define HEUR_PRIORITY -1001000
53#define HEUR_FREQ -1
54#define HEUR_FREQOFS 1
55#define HEUR_MAXDEPTH -1
56#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
57#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
58#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
59#define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
60
61
62/*
63 * Default parameter settings
64 */
65
66#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
67#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
68#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
69#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
70#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
71 * where diving is performed (0.0: no limit) */
72#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
73 * where diving is performed (0.0: no limit) */
74#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
75#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
76#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
77#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
78#define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
79#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
80 * more general constraint handler diving variable selection? */
81#define DEFAULT_RANDSEED 83 /**< default random seed */
82
83/* locally defined heuristic data */
84struct SCIP_HeurData
85{
86 SCIP_SOL* sol; /**< working solution */
87};
88
89/*
90 * local methods
91 */
92
93/*
94 * Callback methods
95 */
96
97/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
98static
99SCIP_DECL_HEURCOPY(heurCopyCoefdiving)
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 constraint handler */
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(heurFreeCoefdiving) /*lint --e{715}*/
114{ /*lint --e{715}*/
115 SCIP_HEURDATA* heurdata;
116
117 assert(heur != NULL);
118 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
119 assert(scip != NULL);
120
121 /* free heuristic data */
122 heurdata = SCIPheurGetData(heur);
123 assert(heurdata != NULL);
124 SCIPfreeBlockMemory(scip, &heurdata);
125 SCIPheurSetData(heur, NULL);
126
127 return SCIP_OKAY;
128}
129
130
131/** initialization method of primal heuristic (called after problem was transformed) */
132static
133SCIP_DECL_HEURINIT(heurInitCoefdiving) /*lint --e{715}*/
134{ /*lint --e{715}*/
135 SCIP_HEURDATA* heurdata;
136
137 assert(heur != NULL);
138 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
139
140 /* get heuristic data */
141 heurdata = SCIPheurGetData(heur);
142 assert(heurdata != NULL);
143
144 /* create working solution */
145 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
146
147 return SCIP_OKAY;
148}
149
150
151/** deinitialization method of primal heuristic (called before transformed problem is freed) */
152static
153SCIP_DECL_HEUREXIT(heurExitCoefdiving) /*lint --e{715}*/
154{ /*lint --e{715}*/
155 SCIP_HEURDATA* heurdata;
156
157 assert(heur != NULL);
158 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
159
160 /* get heuristic data */
161 heurdata = SCIPheurGetData(heur);
162 assert(heurdata != NULL);
163
164 /* free working solution */
165 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
166
167 return SCIP_OKAY;
168}
169
170
171/** execution method of primal heuristic */
172static
173SCIP_DECL_HEUREXEC(heurExecCoefdiving) /*lint --e{715}*/
174{ /*lint --e{715}*/
175 SCIP_HEURDATA* heurdata;
176 SCIP_DIVESET* diveset;
177
178 heurdata = SCIPheurGetData(heur);
179 assert(heurdata != NULL);
180
181 assert(SCIPheurGetNDivesets(heur) > 0);
182 assert(SCIPheurGetDivesets(heur) != NULL);
183 diveset = SCIPheurGetDivesets(heur)[0];
184 assert(diveset != NULL);
185
186 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
187
188 return SCIP_OKAY;
189}
190
191/** returns a score for the given candidate -- the best candidate maximizes the diving score */
192static
193SCIP_DECL_DIVESETGETSCORE(divesetGetScoreCoefdiving)
194{
195 SCIP_Bool mayrounddown = SCIPvarMayRoundDown(cand);
196 SCIP_Bool mayroundup = SCIPvarMayRoundUp(cand);
197
198 if( mayrounddown || mayroundup )
199 {
200 /* choose rounding direction:
201 * - if variable may be rounded in both directions, round corresponding to the fractionality
202 * - otherwise, round in the infeasible direction
203 */
204 if( mayrounddown && mayroundup )
205 {
206 assert( divetype != SCIP_DIVETYPE_SOS1VARIABLE );
207
208 /* try to avoid variability; decide randomly if the LP solution can contain some noise */
209 if( SCIPisEQ(scip, candsfrac, 0.5) )
210 *roundup = (SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0);
211 else
212 *roundup = (candsfrac > 0.5);
213 }
214 else
215 *roundup = mayrounddown;
216 }
217 else
218 {
219 /* the candidate may not be rounded */
220 int nlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL);
221 int nlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_MODEL);
222 *roundup = (nlocksdown > nlocksup || (nlocksdown == nlocksup && candsfrac > 0.5));
223 }
224
225 if( *roundup )
226 {
227 switch( divetype )
228 {
230 candsfrac = 1.0 - candsfrac;
231 break;
233 if ( SCIPisFeasPositive(scip, candsol) )
234 candsfrac = 1.0 - candsfrac;
235 break;
236 default:
237 SCIPerrorMessage("Error: Unsupported diving type\n");
238 SCIPABORT();
239 return SCIP_INVALIDDATA; /*lint !e527*/
240 } /*lint !e788*/
242 }
243 else
244 {
245 if ( divetype == SCIP_DIVETYPE_SOS1VARIABLE && SCIPisFeasNegative(scip, candsol) )
246 candsfrac = 1.0 - candsfrac;
248 }
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 scaling the score
255 */
257 (*score) *= 0.01;
258 }
259 else if( candsfrac < 0.01 )
260 (*score) *= 0.01;
261
262 /* prefer decisions on binary variables */
263 if( !SCIPvarIsBinary(cand) )
264 (*score) *= 0.1;
265
266 /* penalize the variable if it may be rounded. */
267 if( mayrounddown || mayroundup )
268 (*score) -= SCIPgetNLPRows(scip);
269
270 /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
271 assert( (0.0 < candsfrac && candsfrac < 1.0) || SCIPvarIsBinary(cand) || divetype == SCIP_DIVETYPE_SOS1VARIABLE );
272
273 return SCIP_OKAY;
274}
275
276/*
277 * heuristic specific interface methods
278 */
279
280#define divesetAvailableCoefdiving NULL
281
282/** creates the coefdiving heuristic and includes it in SCIP */
284 SCIP* scip /**< SCIP data structure */
285 )
286{
287 SCIP_HEURDATA* heurdata;
288 SCIP_HEUR* heur;
289
290 /* create coefdiving primal heuristic data */
291 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
292
293 /* include primal heuristic */
296 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCoefdiving, heurdata) );
297
298 assert(heur != NULL);
299
300 /* set non-NULL pointers to callback methods */
301 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCoefdiving) );
302 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCoefdiving) );
303 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCoefdiving) );
304 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitCoefdiving) );
305
306 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
310 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreCoefdiving, divesetAvailableCoefdiving) );
311
312 return SCIP_OKAY;
313}
314
#define NULL
Definition: def.h:267
#define SCIP_PROBINGSCORE_PENALTYRATIO
Definition: def.h:322
#define SCIP_Bool
Definition: def.h:91
#define SCIPABORT()
Definition: def.h:346
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPincludeHeurCoefdiving(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
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
#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 SCIPisFeasNegative(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
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3440
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
#define divesetAvailableCoefdiving
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define HEUR_TIMING
static SCIP_DECL_HEURFREE(heurFreeCoefdiving)
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
static SCIP_DECL_HEURCOPY(heurCopyCoefdiving)
#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_HEUREXIT(heurExitCoefdiving)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define HEUR_NAME
#define DEFAULT_RANDSEED
#define DIVESET_DIVETYPES
static SCIP_DECL_HEURINIT(heurInitCoefdiving)
static SCIP_DECL_HEUREXEC(heurExecCoefdiving)
#define DIVESET_ISPUBLIC
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
#define HEUR_USESSUBSCIP
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreCoefdiving)
LP diving heuristic that chooses fixings w.r.t. the matrix coefficients.
methods commonly used by primal heuristics
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
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 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_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97