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-2025 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 /* todo: try to backtrack */
172 /* stop if infeasible */
173 if( infeasible )
174 break;
175 }
176
177 SCIPdebugMsg(scip, "probing ended with %sfeasible problem\n", infeasible ? "in" : "");
178
179 /*************************** Probing LP Solving ***************************/
180
181 /* solve lp only if the problem is still feasible */
182 if( !infeasible )
183 {
184 char strbuf[SCIP_MAXSTRLEN];
185 SCIP_LPSOLSTAT lpstatus;
187 int ncols;
188
189 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
190 * which the user sees no output; more detailed probing stats only in debug mode */
191 ncols = SCIPgetNLPCols(scip);
192 if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
193 {
194 int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
195
196 if( nunfixedcols > 0.5 * ncols )
197 {
199 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
200 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
201 }
202 }
203 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
205
206 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
207 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
208 * SCIP will stop.
209 */
210 SCIPdebugMsg(scip, "starting solving bound-heur LP at time %g, LP iterations: %" SCIP_LONGINT_FORMAT "\n",
212#ifdef NDEBUG
213 {
214 SCIP_Bool retstat;
215 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
216 if( retstat != SCIP_OKAY )
217 {
218 SCIPwarningMessage(scip, "Error while solving LP in bound heuristic; LP solve terminated with code <%d>\n",
219 retstat);
220 }
221 }
222#else
224#endif
225 SCIPdebugMsg(scip, "ending solving bound-heur LP at time %g\n", SCIPgetSolvingTime(scip));
226
227 lpstatus = SCIPgetLPSolstat(scip);
228
229 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
230 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
231
232 /* check if this is a feasible solution */
233 if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
234 {
235 SCIP_SOL* newsol;
236 SCIP_Bool stored;
237 SCIP_Bool success;
238
239 /* create temporary solution */
240 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
241
242 /* copy the current LP solution to the working solution */
243 SCIP_CALL( SCIPlinkLPSol(scip, newsol) );
244
245 SCIP_CALL( SCIProundSol(scip, newsol, &success) );
246
247 if( success )
248 {
249 SCIPdebugMsg(scip, "bound heuristic found roundable primal solution: obj=%g\n",
250 SCIPgetSolOrigObj(scip, newsol));
251
252 /* check solution for feasibility, and add it to solution store if possible.
253 * Neither integrality nor feasibility of LP rows have to be checked, because they
254 * are guaranteed by the heuristic at this stage.
255 */
256#ifdef SCIP_DEBUG
257 SCIP_CALL( SCIPtrySol(scip, newsol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
258#else
259 SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
260#endif
261
262 if( stored )
263 {
264 SCIPdebugMsg(scip, "found feasible solution:\n");
266 }
267 }
268
269 /* free solution */
270 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
271 }
272 }
273
274 /* exit probing mode */
276
277 return SCIP_OKAY;
278}
279
280
281/*
282 * Callback methods of primal heuristic
283 */
284
285/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
286static
287SCIP_DECL_HEURCOPY(heurCopyBound)
288{ /*lint --e{715}*/
289 assert(scip != NULL);
290 assert(heur != NULL);
291 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
292
293 /* call inclusion method of heuristic */
295
296 return SCIP_OKAY;
297}
298
299/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
300static
301SCIP_DECL_HEURFREE(heurFreeBound)
302{ /*lint --e{715}*/
304
305 /* free heuristic data */
307
309 SCIPheurSetData(heur, NULL);
310
311 return SCIP_OKAY;
312}
313
314/** execution method of primal heuristic */
315static
316SCIP_DECL_HEUREXEC(heurExecBound)
317{ /*lint --e{715}*/
319
320 assert(heur != NULL);
321 assert(scip != NULL);
322 assert(result != NULL);
323
325
327 return SCIP_OKAY;
328
330 return SCIP_OKAY;
331
333 assert(heurdata != NULL);
334
336
337 if( SCIPisStopped(scip) )
338 return SCIP_OKAY;
339
340 /* stop execution method if there is already a primal feasible solution at hand */
341 if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
342 return SCIP_OKAY;
343
344 SCIPdebugMsg(scip, "apply bound heuristic at node %lld\n",
346
348 {
350
352
353 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
354 if( cutoff )
355 {
357 return SCIP_OKAY;
358 }
359
361 }
362
363 if( heurdata->bound == 'l' || heurdata->bound == 'b' )
364 {
366 }
367 if( heurdata->bound == 'u' || heurdata->bound == 'b' )
368 {
370 }
371
372 return SCIP_OKAY;
373}
374
375/*
376 * primal heuristic specific interface methods
377 */
378
379/** creates the bound primal heuristic and includes it in SCIP */
381 SCIP* scip /**< SCIP data structure */
382 )
383{
385 SCIP_HEUR* heur;
386
387 /* create bound primal heuristic data */
389
390 /* include primal heuristic */
394
395 assert(heur != NULL);
396
397 /* set non-NULL pointers to callback methods */
398 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyBound) );
399 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeBound) );
400
401 /* add bound heuristic parameters */
402
403 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
404 "Should heuristic only be executed if no primal solution was found, yet?",
405 &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
406
407 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
408 "maximum number of propagation rounds during probing (-1 infinity, -2 parameter settings)",
409 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
410
411 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/bound",
412 "to which bound should integer variables be fixed? ('l'ower, 'u'pper, or 'b'oth)",
413 &heurdata->bound, FALSE, DEFAULT_BOUND, "lub", NULL, NULL) );
414
415 return SCIP_OKAY;
416}
static long bound
#define DEFAULT_MAXPROPROUNDS
internal methods for clocks and timing issues
#define NULL
Definition def.h:266
#define SCIP_MAXSTRLEN
Definition def.h:287
#define SCIP_Bool
Definition def.h:91
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_LONGINT_FORMAT
Definition def.h:164
#define SCIP_CALL(x)
Definition def.h:373
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:380
int SCIPgetNPseudoBranchCands(SCIP *scip)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:183
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:122
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:167
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:7511
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
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:2165
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition scip_sol.c:2307
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:2950
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1296
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:436
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition scip_tree.c:91
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18171
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17611
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17446
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18161
#define HEUR_TIMING
return SCIP_OKAY
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
SCIPfreeSol(scip, &heurdata->sol))
#define HEUR_NAME
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
SCIPcreateSol(scip, &heurdata->sol, heur))
#define DEFAULT_ONLYWITHOUTSOL
Definition heur_bound.c:69
static SCIP_RETCODE applyBoundHeur(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_Bool lower, SCIP_RESULT *result)
Definition heur_bound.c:92
#define DEFAULT_BOUND
Definition heur_bound.c:71
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
struct SCIP_Heur SCIP_HEUR
Definition type_heur.h:76
#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
struct Scip SCIP
Definition type_scip.h:39
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
struct SCIP_Var SCIP_VAR
Definition type_var.h:119
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64