SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_bound.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_bound.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief heuristic which fixes all integer variables to a bound (lower/upper) and solves the remaining LP
28 * @author Gerald Gamrath
29 *
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include "scip/heur_bound.h"
35#include "scip/pub_heur.h"
36#include "scip/pub_message.h"
37#include "scip/pub_tree.h"
38#include "scip/pub_var.h"
39#include "scip/scip_branch.h"
40#include "scip/scip_general.h"
41#include "scip/scip_heur.h"
42#include "scip/scip_lp.h"
43#include "scip/scip_mem.h"
44#include "scip/scip_message.h"
45#include "scip/scip_numerics.h"
46#include "scip/scip_param.h"
47#include "scip/scip_prob.h"
48#include "scip/scip_probing.h"
49#include "scip/scip_sol.h"
51#include "scip/scip_timing.h"
52#include "scip/scip_tree.h"
53#include <string.h>
54
55#ifdef SCIP_STATISTIC
56#include "scip/clock.h"
57#endif
58
59#define HEUR_NAME "bound"
60#define HEUR_DESC "heuristic which fixes all integer variables to a bound and solves the remaining LP"
61#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
62#define HEUR_PRIORITY -1107000
63#define HEUR_FREQ -1
64#define HEUR_FREQOFS 0
65#define HEUR_MAXDEPTH -1
66#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
67#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
68
69#define DEFAULT_ONLYWITHOUTSOL TRUE /**< Should heuristic only be executed if no primal solution was found, yet? */
70#define DEFAULT_MAXPROPROUNDS 0 /* maximum number of propagation rounds during probing */
71#define DEFAULT_BOUND 'l' /**< to which bound should integer variables be fixed? */
72
73
74/*
75 * Data structures
76 */
77
78/** primal heuristic data */
79struct SCIP_HeurData
80{
81 SCIP_Bool onlywithoutsol; /**< Should heuristic only be executed if no primal solution was found, yet? */
82 int maxproprounds; /**< maximum number of propagation rounds during probing */
83 char bound; /**< to which bound should integer variables be fixed? */
84};
85
86/*
87 * Local methods
88 */
89
90/** main procedure of the bound heuristic */
91static
93 SCIP* scip, /**< original SCIP data structure */
94 SCIP_HEUR* heur, /**< heuristic */
95 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
96 SCIP_Bool lower, /**< should integer variables be fixed to their lower bound? */
97 SCIP_RESULT* result /**< pointer to store the result */
98 )
99{
100 SCIP_VAR** vars;
101 SCIP_VAR* var;
102 SCIP_Bool infeasible = FALSE;
103 int maxproprounds;
104 int nbinvars;
105 int nintvars;
106 int nvars;
107 int v;
108
109 /* get variable data of original problem */
111
112 maxproprounds = heurdata->maxproprounds;
113 if( maxproprounds == -2 )
114 maxproprounds = 0;
115
116 /* only look at binary and integer variables */
118
119 /* stop if we would have infinite fixings */
120 if( lower )
121 {
122 for( v = 0; v < nvars; ++v )
123 {
125 return SCIP_OKAY;
126 }
127 }
128 else
129 {
130 for( v = 0; v < nvars; ++v )
131 {
133 return SCIP_OKAY;
134 }
135 }
136
137 /* start probing */
139
140 for( v = 0; v < nvars; ++v )
141 {
142 var = vars[v];
143
145
146 /* skip variables which are already fixed */
148 continue;
149
150 /* fix variable to lower bound */
151 if( lower )
152 {
154 SCIPdebugMsg(scip, "fixing %d: variable <%s> to lower bound <%g> (%d pseudo cands)\n",
156 }
157 /* fix variable to upper bound */
158 else
159 {
161 SCIPdebugMsg(scip, "fixing %d: variable <%s> to upper bound <%g> (%d pseudo cands)\n",
163 }
164
165 /* propagate fixings */
166 if( heurdata->maxproprounds != 0 )
167 {
168 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) );
169 }
170
171 /* try to repair probing */
172 if( infeasible )
173 {
174#if 0
176
177 /* fix the last variable, which was fixed the reverse bound */
179
180 /* propagate fixings */
181 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) );
182
183 SCIPdebugMsg(scip, "backtracking ended with %sfeasible problem\n", (infeasible ? "in" : ""));
184
185 if( infeasible )
186#endif
187 break;
188 }
189 }
190
191 SCIPdebugMsg(scip, "probing ended with %sfeasible problem\n", infeasible ? "in" : "");
192
193 /*************************** Probing LP Solving ***************************/
194
195 /* solve lp only if the problem is still feasible */
196 if( !infeasible )
197 {
198 char strbuf[SCIP_MAXSTRLEN];
200 SCIP_Bool lperror;
201 int ncols;
202
203 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
204 * which the user sees no output; more detailed probing stats only in debug mode */
205 ncols = SCIPgetNLPCols(scip);
206 if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
207 {
209
210 if( nunfixedcols > 0.5 * ncols )
211 {
213 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
214 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
215 }
216 }
217 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
219
220 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
221 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
222 * SCIP will stop.
223 */
224 SCIPdebugMsg(scip, "starting solving bound-heur LP at time %g, LP iterations: %" SCIP_LONGINT_FORMAT "\n",
226#ifdef NDEBUG
227 {
228 SCIP_Bool retstat;
230 if( retstat != SCIP_OKAY )
231 {
232 SCIPwarningMessage(scip, "Error while solving LP in bound heuristic; LP solve terminated with code <%d>\n",
233 retstat);
234 }
235 }
236#else
238#endif
239 SCIPdebugMsg(scip, "ending solving bound-heur LP at time %g\n", SCIPgetSolvingTime(scip));
240
242
243 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
244 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
245
246 /* check if this is a feasible solution */
248 {
250 SCIP_Bool stored;
251 SCIP_Bool success;
252
253 /* create temporary solution */
255
256 /* copy the current LP solution to the working solution */
258
260
261 if( success )
262 {
263 SCIPdebugMsg(scip, "bound heuristic found roundable primal solution: obj=%g\n",
265
266 /* check solution for feasibility, and add it to solution store if possible.
267 * Neither integrality nor feasibility of LP rows have to be checked, because they
268 * are guaranteed by the heuristic at this stage.
269 */
270#ifdef SCIP_DEBUG
272#else
274#endif
275
276 if( stored )
277 {
278 SCIPdebugMsg(scip, "found feasible solution:\n");
280 }
281 }
282
283 /* free solution */
285 }
286 }
287
288 /* exit probing mode */
290
291 return SCIP_OKAY;
292}
293
294
295/*
296 * Callback methods of primal heuristic
297 */
298
299/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
300static
302{ /*lint --e{715}*/
303 assert(scip != NULL);
304 assert(heur != NULL);
306
307 /* call inclusion method of heuristic */
309
310 return SCIP_OKAY;
311}
312
313/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
314static
316{ /*lint --e{715}*/
318
319 /* free heuristic data */
321
323 SCIPheurSetData(heur, NULL);
324
325 return SCIP_OKAY;
326}
327
328/** execution method of primal heuristic */
329static
331{ /*lint --e{715}*/
333
334 assert(heur != NULL);
335 assert(scip != NULL);
336 assert(result != NULL);
337
339
341 return SCIP_OKAY;
342
344 return SCIP_OKAY;
345
347 assert(heurdata != NULL);
348
350
351 if( SCIPisStopped(scip) )
352 return SCIP_OKAY;
353
354 /* stop execution method if there is already a primal feasible solution at hand */
355 if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
356 return SCIP_OKAY;
357
358 SCIPdebugMsg(scip, "apply bound heuristic at node %lld\n",
360
362 {
363 SCIP_Bool cutoff;
364
366
367 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
368 if( cutoff )
369 {
371 return SCIP_OKAY;
372 }
373
375 }
376
377 if( heurdata->bound == 'l' || heurdata->bound == 'b' )
378 {
380 }
381 if( heurdata->bound == 'u' || heurdata->bound == 'b' )
382 {
384 }
385
386 return SCIP_OKAY;
387}
388
389/*
390 * primal heuristic specific interface methods
391 */
392
393/** creates the bound primal heuristic and includes it in SCIP */
395 SCIP* scip /**< SCIP data structure */
396 )
397{
399 SCIP_HEUR* heur;
400
401 /* create bound primal heuristic data */
403
404 /* include primal heuristic */
408
409 assert(heur != NULL);
410
411 /* set non-NULL pointers to callback methods */
414
415 /* add bound heuristic parameters */
416
417 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
418 "Should heuristic only be executed if no primal solution was found, yet?",
419 &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
420
421 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
422 "maximum number of propagation rounds during probing (-1 infinity, -2 parameter settings)",
423 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
424
425 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/bound",
426 "to which bound should integer variables be fixed? ('l'ower, 'u'pper, or 'b'oth)",
427 &heurdata->bound, FALSE, DEFAULT_BOUND, "lub", NULL, NULL) );
428
429 return SCIP_OKAY;
430}
internal methods for clocks and timing issues
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define SCIP_CALL(x)
Definition def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:167
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIP_RETCODE SCIPincludeHeurBound(SCIP *scip)
Definition heur_bound.c:394
int SCIPgetNPseudoBranchCands(SCIP *scip)
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
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition heur.c:1374
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition scip_lp.c:148
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition scip_lp.c:83
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition scip_lp.c:124
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition scip_lp.c:101
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
int SCIPgetNUnfixedLPCols(SCIP *scip)
Definition scip_lp.c:548
int SCIPgetNLPCols(SCIP *scip)
Definition scip_lp.c:527
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition scip_lp.c:667
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition tree.c:7444
int SCIPgetProbingDepth(SCIP *scip)
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2169
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition scip_sol.c:2311
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition scip_sol.c:2954
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1300
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition scip_tree.c:434
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition scip_tree.c:91
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
#define DEFAULT_ONLYWITHOUTSOL
Definition heur_bound.c:69
#define HEUR_TIMING
Definition heur_bound.c:66
#define HEUR_FREQOFS
Definition heur_bound.c:64
#define HEUR_DESC
Definition heur_bound.c:60
#define HEUR_DISPCHAR
Definition heur_bound.c:61
#define HEUR_MAXDEPTH
Definition heur_bound.c:65
#define HEUR_PRIORITY
Definition heur_bound.c:62
static SCIP_RETCODE applyBoundHeur(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_Bool lower, SCIP_RESULT *result)
Definition heur_bound.c:92
#define HEUR_NAME
Definition heur_bound.c:59
#define DEFAULT_BOUND
Definition heur_bound.c:71
#define HEUR_FREQ
Definition heur_bound.c:63
#define HEUR_USESSUBSCIP
Definition heur_bound.c:67
#define DEFAULT_MAXPROPROUNDS
Definition heur_bound.c:70
heuristic which fixes all integer variables to a bound (lower/upper) and solves the remaining LP
SCIP_Bool lperror
SCIPendProbing(scip))
SCIP_Bool cutoff
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIPlinkLPSol(scip, sol))
SCIP_VAR * var
static SCIP_VAR ** vars
int nbinvars
int nintvars
public methods for primal heuristics
public methods for message output
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
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 message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition type_lp.h:51
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_VERBLEVEL_FULL
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64