Scippy

SCIP

Solving Constraint Integer Programs

heur_intdiving.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_intdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that fixes variables with integral LP value
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/heur_intdiving.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_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_tree.h"
52#include "scip/scip_var.h"
53#include <string.h>
54
55#define HEUR_NAME "intdiving"
56#define HEUR_DESC "LP diving heuristic that fixes binary variables with large LP value to one"
57#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
58#define HEUR_PRIORITY -1003500
59#define HEUR_FREQ -1
60#define HEUR_FREQOFS 9
61#define HEUR_MAXDEPTH -1
62#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
63#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
64
65
66/*
67 * Default parameter settings
68 */
69
70#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
71#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
72#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
73#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
74#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
75 * where diving is performed (0.0: no limit) */
76#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
77 * where diving is performed (0.0: no limit) */
78#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
79#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
80#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
81
82#define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
83
84
85/* locally defined heuristic data */
86struct SCIP_HeurData
87{
88 SCIP_SOL* sol; /**< working solution */
89 SCIP_Real minreldepth; /**< minimal relative depth to start diving */
90 SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
91 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
92 int maxlpiterofs; /**< additional number of allowed LP iterations */
93 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
94 * where diving is performed (0.0: no limit) */
95 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
96 * where diving is performed (0.0: no limit) */
97 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
98 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
99 SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */
100 SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */
101 int nsuccess; /**< number of runs that produced at least one feasible solution */
102};
103
104
105/*
106 * local methods
107 */
108
109
110/*
111 * Callback methods
112 */
113
114/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
115static
116SCIP_DECL_HEURCOPY(heurCopyIntdiving)
117{ /*lint --e{715}*/
118 assert(scip != NULL);
119 assert(heur != NULL);
120 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
121
122 /* call inclusion method of primal heuristic */
124
125 return SCIP_OKAY;
126}
127
128/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
129static
130SCIP_DECL_HEURFREE(heurFreeIntdiving) /*lint --e{715}*/
131{ /*lint --e{715}*/
132 SCIP_HEURDATA* heurdata;
133
134 assert(heur != NULL);
135 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
136 assert(scip != NULL);
137
138 /* free heuristic data */
139 heurdata = SCIPheurGetData(heur);
140 assert(heurdata != NULL);
141 SCIPfreeBlockMemory(scip, &heurdata);
142 SCIPheurSetData(heur, NULL);
143
144 return SCIP_OKAY;
145}
146
147
148/** initialization method of primal heuristic (called after problem was transformed) */
149static
150SCIP_DECL_HEURINIT(heurInitIntdiving) /*lint --e{715}*/
151{ /*lint --e{715}*/
152 SCIP_HEURDATA* heurdata;
153
154 assert(heur != NULL);
155 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
156
157 /* get heuristic data */
158 heurdata = SCIPheurGetData(heur);
159 assert(heurdata != NULL);
160
161 /* create working solution */
162 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
163
164 /* initialize data */
165 heurdata->nlpiterations = 0;
166 heurdata->nsuccess = 0;
167
168 return SCIP_OKAY;
169}
170
171
172/** deinitialization method of primal heuristic (called before transformed problem is freed) */
173static
174SCIP_DECL_HEUREXIT(heurExitIntdiving) /*lint --e{715}*/
175{ /*lint --e{715}*/
176 SCIP_HEURDATA* heurdata;
177
178 assert(heur != NULL);
179 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
180
181 /* get heuristic data */
182 heurdata = SCIPheurGetData(heur);
183 assert(heurdata != NULL);
184
185 /* free working solution */
186 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
187
188 return SCIP_OKAY;
189}
190
191
192/** execution method of primal heuristic */
193static
194SCIP_DECL_HEUREXEC(heurExecIntdiving) /*lint --e{715}*/
195{ /*lint --e{715}*/
196 SCIP_HEURDATA* heurdata;
197 SCIP_LPSOLSTAT lpsolstat;
198 SCIP_VAR** pseudocands;
199 SCIP_VAR** fixcands;
200 SCIP_Real* fixcandscores;
201 SCIP_Real searchubbound;
202 SCIP_Real searchavgbound;
203 SCIP_Real searchbound;
204 SCIP_Real objval;
205 SCIP_Bool lperror;
206 SCIP_Bool cutoff;
207 SCIP_Bool backtracked;
208 SCIP_Longint ncalls;
209 SCIP_Longint nsolsfound;
210 SCIP_Longint nlpiterations;
211 SCIP_Longint maxnlpiterations;
212 int nfixcands;
213 int nbinfixcands;
214 int depth;
215 int maxdepth;
216 int maxdivedepth;
217 int divedepth;
218 int nextcand;
219 int c;
220
221 assert(heur != NULL);
222 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
223 assert(scip != NULL);
224 assert(result != NULL);
225 assert(SCIPhasCurrentNodeLP(scip));
226
227 *result = SCIP_DELAYED;
228
229 /* do not call heuristic of node was already detected to be infeasible */
230 if( nodeinfeasible )
231 return SCIP_OKAY;
232
233 /* only call heuristic, if an optimal LP solution is at hand */
235 return SCIP_OKAY;
236
237 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
239 return SCIP_OKAY;
240
241 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
242 if( !SCIPisLPSolBasic(scip) )
243 return SCIP_OKAY;
244
245 /* don't dive two times at the same node */
247 return SCIP_OKAY;
248
249 *result = SCIP_DIDNOTRUN;
250
251 /* get heuristic's data */
252 heurdata = SCIPheurGetData(heur);
253 assert(heurdata != NULL);
254
255 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
256 depth = SCIPgetDepth(scip);
257 maxdepth = SCIPgetMaxDepth(scip);
258 maxdepth = MAX(maxdepth, 100);
259 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
260 return SCIP_OKAY;
261
262 /* calculate the maximal number of LP iterations until heuristic is aborted */
263 nlpiterations = SCIPgetNNodeLPIterations(scip);
264 ncalls = SCIPheurGetNCalls(heur);
265 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
266 maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
267 maxnlpiterations += heurdata->maxlpiterofs;
268
269 /* don't try to dive, if we took too many LP iterations during diving */
270 if( heurdata->nlpiterations >= maxnlpiterations )
271 return SCIP_OKAY;
272
273 /* allow at least a certain number of LP iterations in this dive */
274 maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
275
276 /* get unfixed integer variables */
277 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &nfixcands, NULL) );
278
279 /* don't try to dive, if there are no fractional variables */
280 if( nfixcands == 0 )
281 return SCIP_OKAY;
282
283 /* calculate the objective search bound */
284 if( SCIPgetNSolsFound(scip) == 0 )
285 {
286 if( heurdata->maxdiveubquotnosol > 0.0 )
287 searchubbound = SCIPgetLowerbound(scip)
288 + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
289 else
290 searchubbound = SCIPinfinity(scip);
291 if( heurdata->maxdiveavgquotnosol > 0.0 )
292 searchavgbound = SCIPgetLowerbound(scip)
293 + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
294 else
295 searchavgbound = SCIPinfinity(scip);
296 }
297 else
298 {
299 if( heurdata->maxdiveubquot > 0.0 )
300 searchubbound = SCIPgetLowerbound(scip)
301 + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
302 else
303 searchubbound = SCIPinfinity(scip);
304 if( heurdata->maxdiveavgquot > 0.0 )
305 searchavgbound = SCIPgetLowerbound(scip)
306 + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
307 else
308 searchavgbound = SCIPinfinity(scip);
309 }
310 searchbound = MIN(searchubbound, searchavgbound);
312 searchbound = SCIPceil(scip, searchbound);
313
314 /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
315 maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
316 maxdivedepth = MIN(maxdivedepth, maxdepth);
317 maxdivedepth *= 10;
318
319 *result = SCIP_DIDNOTFIND;
320
321 /* start diving */
323
324 /* enables collection of variable statistics during probing */
326
327 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing intdiving heuristic: depth=%d, %d non-fixed, dualbound=%g, searchbound=%g\n",
329
330 /* copy the pseudo candidates into own array, because we want to reorder them */
331 SCIP_CALL( SCIPduplicateBufferArray(scip, &fixcands, pseudocands, nfixcands) );
332
333 /* sort non-fixed variables by non-increasing inference score, but prefer binaries over integers in any case */
334 SCIP_CALL( SCIPallocBufferArray(scip, &fixcandscores, nfixcands) );
335 nbinfixcands = 0;
336 for( c = 0; c < nfixcands; ++c )
337 {
338 SCIP_VAR* var;
339 SCIP_Real score;
340 int colveclen;
341 int left;
342 int right;
343 int i;
344
345 assert(c >= nbinfixcands);
346 var = fixcands[c];
347 assert(SCIPvarIsIntegral(var));
349 if( SCIPvarIsBinary(var) )
350 {
351 score = 500.0 * SCIPvarGetNCliques(var, TRUE) + 100.0 * SCIPvarGetNImpls(var, TRUE)
352 + SCIPgetVarAvgInferenceScore(scip, var) + (SCIP_Real)colveclen/100.0;
353
354 /* shift the non-binary variables one slot to the right */
355 for( i = c; i > nbinfixcands; --i )
356 {
357 fixcands[i] = fixcands[i-1];
358 fixcandscores[i] = fixcandscores[i-1];
359 }
360 /* put the new candidate into the first nbinfixcands slot */
361 left = 0;
362 right = nbinfixcands;
363 nbinfixcands++;
364 }
365 else
366 {
367 score = 5.0 * (SCIPvarGetNCliques(var, FALSE) + SCIPvarGetNCliques(var, TRUE))
369 + (SCIP_Real)colveclen/10000.0;
370
371 /* put the new candidate in the slots after the binary candidates */
372 left = nbinfixcands;
373 right = c;
374 }
375 for( i = right; i > left && score > fixcandscores[i-1]; --i )
376 {
377 fixcands[i] = fixcands[i-1];
378 fixcandscores[i] = fixcandscores[i-1];
379 }
380 fixcands[i] = var;
381 fixcandscores[i] = score;
382 SCIPdebugMsg(scip, " <%s>: ncliques=%d/%d, nimpls=%d/%d, inferencescore=%g, colveclen=%d -> score=%g\n",
385 colveclen, score);
386 }
387 SCIPfreeBufferArray(scip, &fixcandscores);
388
389 /* get LP objective value */
390 lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
391 objval = SCIPgetLPObjval(scip);
392
393 /* dive as long we are in the given objective, depth and iteration limits, but if possible, we dive at least with
394 * the depth 10
395 */
396 lperror = FALSE;
397 cutoff = FALSE;
398 divedepth = 0;
399 nextcand = 0;
400 while( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL
401 && (divedepth < 10
402 || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
403 && !SCIPisStopped(scip) )
404 {
405 SCIP_VAR* var;
406 SCIP_Real bestsolval;
407 SCIP_Real bestfixval;
408 int bestcand;
409 SCIP_Longint nnewlpiterations;
410 SCIP_Longint nnewdomreds;
411
412 /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
414 {
416 divedepth++;
417 }
418 else
419 break;
420
421 nnewlpiterations = 0;
422 nnewdomreds = 0;
423
424 /* fix binary variable that is closest to 1 in the LP solution to 1;
425 * if all binary variables are fixed, fix integer variable with least fractionality in LP solution
426 */
427 bestcand = -1;
428 bestsolval = -1.0;
429 bestfixval = 1.0;
430
431 /* look in the binary variables for fixing candidates */
432 for( c = nextcand; c < nbinfixcands; ++c )
433 {
434 SCIP_Real solval;
435
436 var = fixcands[c];
437
438 /* ignore already fixed variables */
439 if( var == NULL )
440 continue;
441 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
442 {
443 fixcands[c] = NULL;
444 continue;
445 }
446
447 /* get the LP solution value */
448 solval = SCIPvarGetLPSol(var);
449
450 if( solval > bestsolval )
451 {
452 bestcand = c;
453 bestfixval = 1.0;
454 bestsolval = solval;
455 if( SCIPisGE(scip, bestsolval, 1.0) )
456 {
457 /* we found an unfixed binary variable with LP solution value of 1.0 - there cannot be a better candidate */
458 break;
459 }
460 else if( SCIPisLE(scip, bestsolval, 0.0) )
461 {
462 /* the variable is currently at 0.0 - this is the only situation where we want to fix it to 0.0 */
463 bestfixval = 0.0;
464 }
465 }
466 }
467
468 /* if all binary variables are fixed, look in the integer variables for a fixing candidate */
469 if( bestcand == -1 )
470 {
471 SCIP_Real bestfrac;
472
473 bestfrac = SCIP_INVALID;
474 for( c = MAX(nextcand, nbinfixcands); c < nfixcands; ++c )
475 {
476 SCIP_Real solval;
477 SCIP_Real frac;
478
479 var = fixcands[c];
480
481 /* ignore already fixed variables */
482 if( var == NULL )
483 continue;
484 if( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) < 0.5 )
485 {
486 fixcands[c] = NULL;
487 continue;
488 }
489
490 /* get the LP solution value */
491 solval = SCIPvarGetLPSol(var);
492 frac = SCIPfrac(scip, solval);
493
494 /* ignore integer variables that are currently integral */
495 if( SCIPisFeasFracIntegral(scip, frac) )
496 continue;
497
498 if( frac < bestfrac )
499 {
500 bestcand = c;
501 bestsolval = solval;
502 bestfrac = frac;
503 bestfixval = SCIPfloor(scip, bestsolval + 0.5);
504 if( SCIPisZero(scip, bestfrac) )
505 {
506 /* we found an unfixed integer variable with integral LP solution value */
507 break;
508 }
509 }
510 }
511 }
512 assert(-1 <= bestcand && bestcand < nfixcands);
513
514 /* if there is no unfixed candidate left, we are done */
515 if( bestcand == -1 )
516 break;
517
518 var = fixcands[bestcand];
519 assert(var != NULL);
520 assert(SCIPvarIsIntegral(var));
521 assert(SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) > 0.5);
522 assert(SCIPisGE(scip, bestfixval, SCIPvarGetLbLocal(var)));
523 assert(SCIPisLE(scip, bestfixval, SCIPvarGetUbLocal(var)));
524
525 backtracked = FALSE;
526 do
527 {
528 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
529 * occured or variable was fixed by propagation while backtracking => Abort diving!
530 */
531 if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
532 {
533 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g], diving aborted \n",
535 cutoff = TRUE;
536 break;
537 }
538 if( SCIPisFeasLT(scip, bestfixval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestfixval, SCIPvarGetUbLocal(var)) )
539 {
540 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
541 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
542 assert(backtracked);
543 break;
544 }
545
546 /* apply fixing of best candidate */
547 SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", %d unfixed: var <%s>, sol=%g, oldbounds=[%g,%g], fixed to %g\n",
548 divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations, SCIPgetNPseudoBranchCands(scip),
549 SCIPvarGetName(var), bestsolval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
550 SCIP_CALL( SCIPfixVarProbing(scip, var, bestfixval) );
551
552 /* apply domain propagation */
553 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &nnewdomreds) );
554 if( !cutoff )
555 {
556 /* if the best candidate was just fixed to its LP value and no domain reduction was found, the LP solution
557 * stays valid, and the LP does not need to be resolved
558 */
559 if( nnewdomreds > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
560 {
561 /* resolve the diving LP */
562 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
563 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
564 */
565#ifdef NDEBUG
566 SCIP_RETCODE retstat;
567 nlpiterations = SCIPgetNLPIterations(scip);
568 retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff);
569 if( retstat != SCIP_OKAY )
570 {
571 SCIPwarningMessage(scip, "Error while solving LP in Intdiving heuristic; LP solve terminated with code <%d>\n",retstat);
572 }
573#else
574 nlpiterations = SCIPgetNLPIterations(scip);
575 SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) );
576#endif
577
578 if( lperror )
579 break;
580
581 /* update iteration count */
582 nnewlpiterations = SCIPgetNLPIterations(scip) - nlpiterations;
583 heurdata->nlpiterations += nnewlpiterations;
584
585 /* get LP solution status */
586 lpsolstat = SCIPgetLPSolstat(scip);
587 assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
589 }
590 }
591
592 /* perform backtracking if a cutoff was detected */
593 if( cutoff && !backtracked && heurdata->backtrack )
594 {
595 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
597
598 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
600
602
603 bestfixval = SCIPvarIsBinary(var)
604 ? 1.0 - bestfixval
605 : (SCIPisGT(scip, bestsolval, bestfixval) && SCIPisFeasLE(scip, bestfixval + 1, SCIPvarGetUbLocal(var)) ? bestfixval + 1 : bestfixval - 1);
606
607 backtracked = TRUE;
608 }
609 else
610 backtracked = FALSE;
611 }
612 while( backtracked );
613
614 if( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
615 {
616 SCIP_Bool success;
617
618 /* get new objective value */
619 objval = SCIPgetLPObjval(scip);
620
621 if( nnewlpiterations > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
622 {
623 /* we must start again with the first candidate, since the LP solution changed */
624 nextcand = 0;
625
626 /* create solution from diving LP and try to round it */
627 SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
628 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
629 if( success )
630 {
631 SCIPdebugMsg(scip, "intdiving found roundable primal solution: obj=%g\n",
632 SCIPgetSolOrigObj(scip, heurdata->sol));
633
634 /* try to add solution to SCIP */
635 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
636
637 /* check, if solution was feasible and good enough */
638 if( success )
639 {
640 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
641 *result = SCIP_FOUNDSOL;
642 }
643 }
644 }
645 else
646 nextcand = bestcand+1; /* continue with the next candidate in the following loop */
647 }
648 SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g\n", lpsolstat, objval, searchbound);
649 }
650
651 /* free temporary memory */
652 SCIPfreeBufferArray(scip, &fixcands);
653
654 /* end diving */
656
657 if( *result == SCIP_FOUNDSOL )
658 heurdata->nsuccess++;
659
660 SCIPdebugMsg(scip, "intdiving heuristic finished\n");
661
662 return SCIP_OKAY; /*lint !e438*/
663}
664
665
666/*
667 * heuristic specific interface methods
668 */
669
670/** creates the intdiving heuristic and includes it in SCIP */
672 SCIP* scip /**< SCIP data structure */
673 )
674{
675 SCIP_HEURDATA* heurdata;
676 SCIP_HEUR* heur;
677
678 /* create Intdiving primal heuristic data */
679 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
680
681 /* include primal heuristic */
684 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntdiving, heurdata) );
685
686 assert(heur != NULL);
687
688 /* set non-NULL pointers to callback methods */
689 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntdiving) );
690 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIntdiving) );
691 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntdiving) );
692 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntdiving) );
693
694 /* intdiving heuristic parameters */
696 "heuristics/intdiving/minreldepth",
697 "minimal relative depth to start diving",
698 &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
700 "heuristics/intdiving/maxreldepth",
701 "maximal relative depth to start diving",
702 &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
704 "heuristics/intdiving/maxlpiterquot",
705 "maximal fraction of diving LP iterations compared to node LP iterations",
706 &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
708 "heuristics/intdiving/maxlpiterofs",
709 "additional number of allowed LP iterations",
710 &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
712 "heuristics/intdiving/maxdiveubquot",
713 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
714 &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
716 "heuristics/intdiving/maxdiveavgquot",
717 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
718 &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
720 "heuristics/intdiving/maxdiveubquotnosol",
721 "maximal UBQUOT when no solution was found yet (0.0: no limit)",
722 &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
724 "heuristics/intdiving/maxdiveavgquotnosol",
725 "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
726 &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
728 "heuristics/intdiving/backtrack",
729 "use one level of backtracking if infeasibility is encountered?",
730 &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
731
732 return SCIP_OKAY;
733}
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_MAXTREEDEPTH
Definition: def.h:316
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1562
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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 SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
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 SCIPincludeHeurIntdiving(SCIP *scip)
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:758
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:17126
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
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
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
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2745
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:820
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:418
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
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 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_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1432
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasFracIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9473
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18356
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8741
#define DEFAULT_MAXDIVEUBQUOT
static SCIP_DECL_HEURFREE(heurFreeIntdiving)
#define HEUR_TIMING
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
static SCIP_DECL_HEURCOPY(heurCopyIntdiving)
#define MINLPITER
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_BACKTRACK
static SCIP_DECL_HEUREXEC(heurExecIntdiving)
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define HEUR_NAME
static SCIP_DECL_HEURINIT(heurInitIntdiving)
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
static SCIP_DECL_HEUREXIT(heurExitIntdiving)
#define HEUR_USESSUBSCIP
LP diving heuristic that fixes variables with integral LP value.
memory allocation routines
public methods for primal heuristics
public methods for LP management
public methods for message output
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 the branch-and-bound tree
public methods for SCIP variables
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:51
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:44
@ SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:46
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DELAYED
Definition: type_result.h:43
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51