SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_veclendiving.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-2023 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_veclendiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that rounds variables with long column vectors
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_lp.h"
37#include "scip/pub_message.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 "veclendiving"
47#define HEUR_DESC "LP diving heuristic that rounds variables with long column vectors"
48#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
49#define HEUR_PRIORITY -1003100
50#define HEUR_FREQ 10
51#define HEUR_FREQOFS 4
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 /**< 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#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
75#define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
76#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
77 * more general constraint handler diving variable selection? */
78#define DEFAULT_RANDSEED 113 /**< initial seed for random number generation */
79
80/* locally defined heuristic data */
81struct SCIP_HeurData
82{
83 SCIP_SOL* sol; /**< working solution */
84};
85
86
87/*
88 * local methods
89 */
90
91/*
92 * Callback methods
93 */
94
95/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
96static
98{ /*lint --e{715}*/
99 assert(scip != NULL);
100 assert(heur != NULL);
102
103 /* call inclusion method of primal heuristic */
105
106 return SCIP_OKAY;
107}
108
109/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
110static
112{ /*lint --e{715}*/
114
115 assert(heur != NULL);
118
119 /* free heuristic data */
122
125
126 return SCIP_OKAY;
127}
128
129
130/** initialization method of primal heuristic (called after problem was transformed) */
131static
133{ /*lint --e{715}*/
135
136 assert(heur != NULL);
138
139 /* get heuristic data */
141 assert(heurdata != NULL);
142
143 /* create working solution */
145
146 return SCIP_OKAY;
147}
148
149
150/** deinitialization method of primal heuristic (called before transformed problem is freed) */
151static
153{ /*lint --e{715}*/
155
156 assert(heur != NULL);
158
159 /* get heuristic data */
161 assert(heurdata != NULL);
162
163 /* free working solution */
165
166 return SCIP_OKAY;
167}
168
169
170/** execution method of primal heuristic */
171static
173{ /*lint --e{715}*/
176
180 diveset = SCIPheurGetDivesets(heur)[0];
182
184
185 /* terminate if there are no integer variables (note that, e.g., SOS1 variables may be present) */
187 return SCIP_OKAY;
188
190
191 return SCIP_OKAY;
192}
193
194/** calculate score and preferred rounding direction for the candidate variable */
195static
197{
198 SCIP_Real obj;
199 SCIP_Real objdelta;
200 SCIP_Real colveclen;
201
203 *roundup = (obj >= 0.0);
204 objdelta = ((*roundup) ? (1.0 - candsfrac) * obj : -candsfrac * obj);
205 assert(objdelta >= 0.0);
206
208
209 /* larger score is better */
210 *score = (colveclen + 1.0) / (objdelta + SCIPsumepsilon(scip));
211
212 /* prefer decisions on binary variables */
214 *score *= 0.001;
215
216 return SCIP_OKAY;
217}
218
219#define divesetAvailableVeclendiving NULL
220
221/*
222 * heuristic specific interface methods
223 */
224
225/** creates the veclendiving heuristic and includes it in SCIP */
227 SCIP* scip /**< SCIP data structure */
228 )
229{
231 SCIP_HEUR* heur;
232
233 /* create Veclendiving primal heuristic data */
235
236 /* include primal heuristic */
240
241 assert(heur != NULL);
242
243 /* set non-NULL pointers to callback methods */
248
249 /* veclendiving heuristic parameters */
250 /* create a diveset (this will automatically install some additional parameters for the heuristic) */
255
256 return SCIP_OKAY;
257}
258
#define SCIP_CALL(x)
Definition def.h:388
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
SCIP_RETCODE SCIPincludeHeurVeclendiving(SCIP *scip)
int SCIPcolGetNNonz(SCIP_COL *col)
Definition lp.c:17126
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_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1361
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:1658
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:1450
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition heur.c:1648
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17611
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, SCIP_DIVECONTEXT_ADAPTIVE))
static SCIP_SOL * sol
SCIP_Real obj
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Bool roundup
#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 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 DIVESET_ISPUBLIC
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
#define divesetAvailableVeclendiving
#define HEUR_USESSUBSCIP
static SCIP_DIVESET * diveset
SCIPcreateSol(scip, &heurdata->sol, heur))
LP diving heuristic that rounds variables with long column vectors.
methods commonly used by primal heuristics
#define NULL
Definition lpi_spx1.cpp:161
public methods for primal heuristics
public methods for LP management
public methods for message output
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:96
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:112
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:120
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:104
#define SCIP_DECL_DIVESETGETSCORE(x)
Definition type_heur.h:183
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ SCIP_DIVECONTEXT_SINGLE
Definition type_heur.h:69
@ SCIP_DIDNOTRUN
Definition type_result.h:42
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51