SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_actconsdiving.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_actconsdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that chooses fixings w.r.t. the active constraints the variable appear in
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_lp.h"
37#include "scip/pub_message.h"
38#include "scip/pub_misc.h"
39#include "scip/pub_var.h"
40#include "scip/scip_branch.h"
41#include "scip/scip_heur.h"
42#include "scip/scip_lp.h"
43#include "scip/scip_mem.h"
44#include "scip/scip_numerics.h"
45#include "scip/scip_prob.h"
46#include "scip/scip_sol.h"
47#include <string.h>
48
49#define HEUR_NAME "actconsdiving"
50#define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the active constraints"
51#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
52#define HEUR_PRIORITY -1003700
53#define HEUR_FREQ -1
54#define HEUR_FREQOFS 5
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 /**< 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 * Default parameter settings
63 */
64
65#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
66#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
67#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
68#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
69#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
70 * where diving is performed (0.0: no limit) */
71#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
72 * where diving is performed (0.0: no limit) */
73#define DEFAULT_MAXDIVEUBQUOTNOSOL 1.0 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
74#define DEFAULT_MAXDIVEAVGQUOTNOSOL 1.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
75#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
76#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
77#define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
78#define DEFAULT_ONLYLPBRANCHCANDS TRUE /**< should only LP branching candidates be considered instead of the slower but
79 * more general constraint handler diving variable selection? */
80#define DEFAULT_RANDSEED 149 /**< default random seed */
81
82/* locally defined heuristic data */
83struct SCIP_HeurData
84{
85 SCIP_SOL* sol; /**< working solution */
86};
87
88
89/*
90 * local methods
91 */
92
93/** returns a score value for the given variable based on the active constraints that the variable appears in */
94static
96 SCIP* scip, /**< SCIP data structure */
97 SCIP_SOL* sol, /**< working solution */
98 SCIP_VAR* var, /**< variable to get the score value for */
99 SCIP_Real* downscore, /**< pointer to store the score for branching downwards */
100 SCIP_Real* upscore /**< pointer to store the score for branching upwards */
101 )
102{
103 SCIP_COL* col;
104 SCIP_ROW** rows;
105 SCIP_Real* vals;
106 int nrows;
107 int r;
108 int nactrows;
109 SCIP_Real nlprows;
110 SCIP_Real downcoefsum;
111 SCIP_Real upcoefsum;
112 SCIP_Real score;
113
115 assert(upscore != NULL);
116
117 *downscore = 0.0;
118 *upscore = 0.0;
120 return 0.0;
121
122 col = SCIPvarGetCol(var);
123 assert(col != NULL);
124
125 rows = SCIPcolGetRows(col);
126 vals = SCIPcolGetVals(col);
127 nrows = SCIPcolGetNLPNonz(col);
128 nactrows = 0;
129 downcoefsum = 0.0;
130 upcoefsum = 0.0;
131 for( r = 0; r < nrows; ++r )
132 {
133 SCIP_ROW* row;
134 SCIP_Real activity;
135 SCIP_Real lhs;
136 SCIP_Real rhs;
137 SCIP_Real dualsol;
138
139 row = rows[r];
140 /* calculate number of active constraint sides, i.e., count equations as two */
141 lhs = SCIProwGetLhs(row);
142 rhs = SCIProwGetRhs(row);
143
144 /* @todo this is suboptimal because activity is calculated by looping over all nonzeros of this row, need to
145 * store LP activities instead (which cannot be retrieved if no LP was solved at this node)
146 */
147 activity = SCIPgetRowSolActivity(scip, row, sol);
148
149 dualsol = SCIProwGetDualsol(row);
150 if( SCIPisFeasEQ(scip, activity, lhs) )
151 {
152 SCIP_Real coef;
153
154 nactrows++;
155 coef = vals[r] / SCIProwGetNorm(row);
156 if( SCIPisFeasPositive(scip, dualsol) )
157 {
158 if( coef > 0.0 )
159 downcoefsum += coef;
160 else
161 upcoefsum -= coef;
162 }
163 }
164 else if( SCIPisFeasEQ(scip, activity, rhs) )
165 {
166 SCIP_Real coef;
167
168 nactrows++;
169 coef = vals[r] / SCIProwGetNorm(row);
170 if( SCIPisFeasNegative(scip, dualsol) )
171 {
172 if( coef > 0.0 )
173 upcoefsum += coef;
174 else
175 downcoefsum -= coef;
176 }
177 }
178 }
179
180 /* use the number of LP rows for normalization */
184
185 /* calculate the score using SCIP's branch score. Pass NULL as variable to not have the var branch factor influence
186 * the result
187 */
189
190 assert(score <= 3.0);
191 assert(score >= 0.0);
192
195
196 return score;
197}
198
199
200/*
201 * Callback methods
202 */
203
204/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
205static
207{ /*lint --e{715}*/
208 assert(scip != NULL);
209 assert(heur != NULL);
211
212 /* call inclusion method of primal heuristic */
214
215 return SCIP_OKAY;
216}
217
218/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
219static
221{ /*lint --e{715}*/
223
224 assert(heur != NULL);
227
228 /* free heuristic data */
231
234
235 return SCIP_OKAY;
236}
237
238
239/** initialization method of primal heuristic (called after problem was transformed) */
240static
242{ /*lint --e{715}*/
244
245 assert(heur != NULL);
247
248 /* get heuristic data */
250 assert(heurdata != NULL);
251
252 /* create working solution */
254
255 return SCIP_OKAY;
256}
257
258
259/** deinitialization method of primal heuristic (called before transformed problem is freed) */
260static
262{ /*lint --e{715}*/
264
265 assert(heur != NULL);
267
268 /* get heuristic data */
270 assert(heurdata != NULL);
271
272 /* free working solution */
274
275 return SCIP_OKAY;
276}
277
278
279/** execution method of primal heuristic */
280static
282{ /*lint --e{715}*/
285
287
290 diveset = SCIPheurGetDivesets(heur)[0];
292
294
295 /* if there are no integer variables, stop execution */
297 return SCIP_OKAY;
298
300
301 return SCIP_OKAY;
302}
303
304/** calculate score and preferred rounding direction for the candidate variable; the best candidate maximizes the
305 * score
306 */
307static
309{
310 SCIP_Bool mayrounddown;
311 SCIP_Bool mayroundup;
312 SCIP_Real downscore;
313 SCIP_Real upscore;
314
317
318 /* first, calculate the variable score */
321
322 /* get the rounding direction: prefer an unroundable direction */
323 if( mayrounddown && mayroundup )
324 {
325 /* try to avoid variability; decide randomly if the LP solution can contain some noise */
326 if( SCIPisEQ(scip, candsfrac, 0.5) )
328 else
329 *roundup = (candsfrac > 0.5);
330 }
331 else if( mayrounddown || mayroundup )
333 else
335
336 if( *roundup )
337 candsfrac = 1.0 - candsfrac;
338
339 /* penalize too small fractions */
340 if( SCIPisEQ(scip, candsfrac, 0.01) )
341 {
342 /* try to avoid variability; decide randomly if the LP solution can contain some noise.
343 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for scaling the score
344 */
346 (*score) *= 0.01;
347 }
348 else if( candsfrac < 0.01 )
349 (*score) *= 0.01;
350
351 /* prefer decisions on binary variables */
352 if( !SCIPvarIsBinary(cand) )
353 (*score) *= 0.01;
354
355 /* penalize variable if it may be rounded */
356 if( mayrounddown || mayroundup )
357 *score -= 3.0;
358
359 assert(!(mayrounddown || mayroundup) || *score <= 0.0);
360
361 return SCIP_OKAY;
362}
363
364#define divesetAvailableActconsdiving NULL
365
366/*
367 * heuristic specific interface methods
368 */
369
370/** creates the actconsdiving heuristic and includes it in SCIP */
372 SCIP* scip /**< SCIP data structure */
373 )
374{
376 SCIP_HEUR* heur;
377
378 /* create actconsdiving primal heuristic data */
380
381 /* include primal heuristic */
385
386 assert(heur != NULL);
387
388 /* set non-NULL pointers to callback methods */
393
394 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
400
401 return SCIP_OKAY;
402}
403
#define NULL
Definition def.h:267
#define SCIP_PROBINGSCORE_PENALTYRATIO
Definition def.h:322
#define SCIP_Real
Definition def.h:173
#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 SCIPincludeHeurActconsdiving(SCIP *scip)
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition lp.c:17151
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition lp.c:17140
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
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_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition lp.c:17268
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition lp.c:17312
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition scip_lp.c:2144
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17789
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition var.c:3451
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17599
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition var.c:3440
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10108
SCIP_SOL * SCIPdivesetGetWorkSolution(SCIP_DIVESET *diveset)
Definition heur.c:424
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_LPRESOLVEDOMCHGQUOT
SCIPheurSetData(heur, NULL)
#define HEUR_TIMING
return SCIP_OKAY
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
#define divesetAvailableActconsdiving
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
static SCIP_Real getNActiveConsScore(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real *downscore, SCIP_Real *upscore)
#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 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 active constraints the variable appear in.
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
int nlprows
static SCIP_SOL * sol
int r
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Bool mayrounddown
SCIP_VAR * var
SCIP_Bool mayroundup
SCIP_Bool roundup
methods commonly used by primal heuristics
public methods for primal heuristics
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
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
#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
@ SCIP_DIVECONTEXT_SINGLE
Definition type_heur.h:69
@ SCIP_DIDNOTRUN
Definition type_result.h:42
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51