SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_dins.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_dins.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief DINS primal heuristic (according to Ghosh)
28 * @author Timo Berthold
29 * @author Robert Waniek
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/cons_linear.h"
36#include "scip/heur_dins.h"
37#include "scip/heuristics.h"
38#include "scip/pub_event.h"
39#include "scip/pub_heur.h"
40#include "scip/pub_message.h"
41#include "scip/pub_misc.h"
42#include "scip/pub_var.h"
43#include "scip/scip_branch.h"
44#include "scip/scip_cons.h"
45#include "scip/scip_copy.h"
46#include "scip/scip_event.h"
47#include "scip/scip_general.h"
48#include "scip/scip_heur.h"
49#include "scip/scip_lp.h"
50#include "scip/scip_mem.h"
51#include "scip/scip_message.h"
52#include "scip/scip_nodesel.h"
53#include "scip/scip_numerics.h"
54#include "scip/scip_param.h"
55#include "scip/scip_prob.h"
56#include "scip/scip_sol.h"
57#include "scip/scip_solve.h"
59#include "scip/scip_var.h"
60#include <string.h>
61
62#define HEUR_NAME "dins"
63#define HEUR_DESC "distance induced neighborhood search by Ghosh"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
65#define HEUR_PRIORITY -1105000
66#define HEUR_FREQ -1
67#define HEUR_FREQOFS 0
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
70#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
71
72#define DEFAULT_NODESOFS 5000LL /* number of nodes added to the contingent of the total nodes */
73#define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */
74#define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */
75#define DEFAULT_MINIMPROVE 0.01 /* factor by which DINS should at least improve the incumbent */
76#define DEFAULT_NODESQUOT 0.05 /* subproblem nodes in relation to nodes of the original problem */
77#define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */
78#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */
79#define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change that heuristic should wait */
80#define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */
81#define DEFAULT_SOLNUM 5 /* number of pool-solutions to be checked for flag array update */
82#define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
83 * otherwise, the copy constructors of the constraints handlers are used */
84#define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
85 * of the original scip be copied to constraints of the subscip */
87#define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */
88#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
89
91/* event handler properties */
92#define EVENTHDLR_NAME "Dins"
93#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
94
95/*
96 * Data structures
97 */
98
99/** DINS primal heuristic data */
100struct SCIP_HeurData
101{
102 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
103 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
104 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
105 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
106 SCIP_Longint nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
107 SCIP_Real minimprove; /**< factor by which DINS should at least improve the incumbent */
108 SCIP_Longint usednodes; /**< nodes already used by DINS in earlier calls */
109 SCIP_Longint lastnsolsfound; /**< total number of found solutions at previous execution of DINS */
110 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
111 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
112 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
113 int neighborhoodsize; /**< radius of the incumbent's neighborhood to be searched */
114 SCIP_Bool* delta; /**< stores whether a variable kept its value from root LP all the time */
115 int deltalength; /**< if there are no binary variables, we need no flag array */
116 int solnum; /**< number of pool-solutions to be checked for flag array update */
117 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
118 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
119 * to constraints in subproblem?
120 */
121 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
122 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
123};
124
125
126/*
127 * Local methods
128 */
129
130/** compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ */
131static
133 SCIP* scip, /**< SCIP data structure of the original problem */
134 SCIP_VAR* var, /**< the variable for which bounds should be computed */
135 SCIP_Real* lbptr, /**< pointer to store the lower bound in the DINS sub-SCIP */
136 SCIP_Real* ubptr /**< pointer to store the upper bound in the DINS sub-SCIP */
137 )
138{
139 SCIP_Real mipsol;
140 SCIP_Real lpsol;
141
142 SCIP_Real lbglobal;
143 SCIP_Real ubglobal;
144 SCIP_SOL* bestsol;
145
146 /* get the bounds for each variable */
149
151 /* get the current LP solution for each variable */
153
154 /* get the current MIP solution for each variable */
155 bestsol = SCIPgetBestSol(scip);
156 mipsol = SCIPgetSolVal(scip, bestsol, var);
157
158 /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */
159 if( REALABS(lpsol - mipsol) >= 0.5 )
160 {
161 SCIP_Real range;
162
163 *lbptr = lbglobal;
164 *ubptr = ubglobal;
165
166 /* create a equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */
167 range = 2*lpsol-mipsol;
168
169 if( mipsol >= lpsol )
170 {
172 *lbptr = MAX(*lbptr, range);
173
174 /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
175 if( SCIPisFeasEQ(scip, mipsol, *lbptr) )
176 *ubptr = *lbptr;
177 else
178 *ubptr = mipsol;
179 }
180 else
181 {
183 *ubptr = MIN(*ubptr, range);
184
185 /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
186 if( SCIPisFeasEQ(scip, mipsol, *ubptr) )
187 *lbptr = *ubptr;
188 else
189 *lbptr = mipsol;
190 }
191
192 /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */
193 *lbptr = MAX(*lbptr, lbglobal);
194 *ubptr = MIN(*ubptr, ubglobal);
195 }
196 else
197 {
198 /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */
201 }
202}
203
204/** creates a subproblem for subscip by fixing a number of variables */
205static
207 SCIP* scip, /**< SCIP data structure of the original problem */
208 SCIP_HEUR* heur, /**< DINS heuristic structure */
209 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
210 SCIP_VAR** vars, /**< variables of the original problem */
211 SCIP_VAR** fixedvars, /**< array to store variables that should be fixed in the sub-SCIP */
212 SCIP_Real* fixedvals, /**< array to store fixing values for fixed variables */
213 int nbinvars, /**< number of binary variables of problem and subproblem */
214 int nintvars, /**< number of general integer variables of problem and subproblem */
215 int* binfixings, /**< pointer to store number of binary variables that should be fixed */
216 int* intfixings /**< pointer to store number of integer variables that should be fixed */
217 )
218{
219 SCIP_SOL* bestsol;
220 SCIP_SOL** sols;
221 SCIP_Bool* delta;
222 int i;
223 int nsols;
224 SCIP_Longint nsolsfound;
225 int checklength;
226 int nfixedvars;
227
228 assert(scip != NULL);
229 assert(vars != NULL);
230 assert(fixedvars != NULL);
234 assert(heur != NULL);
235
236 /* get the best MIP-solution known so far */
237 bestsol = SCIPgetBestSol(scip);
238 assert(bestsol != NULL);
239
240 /* get solution pool and number of solutions in pool */
241 sols = SCIPgetSols(scip);
242 nsols = SCIPgetNSols(scip);
244 checklength = MIN(nsols, heurdata->solnum);
245 assert(sols != NULL);
246 assert(nsols > 0);
247
248 /* if new binary variables have been created, e.g., due to column generation, reallocate the delta array */
249 if( heurdata->deltalength < nbinvars )
250 {
251 int newsize;
252
255
257
258 /* initialize new part of delta array */
259 for( i = heurdata->deltalength; i < newsize; i++ )
260 heurdata->delta[i] = TRUE;
261
262 heurdata->deltalength = newsize;
263 }
264
265 delta = heurdata->delta;
266 /* fixing for binary variables */
267 /* hard fixing for some with mipsol(s)=lpsolval=rootlpsolval and preparation for soft fixing for the remaining */
268 nfixedvars = 0;
269 *intfixings = *binfixings = 0;
270 for( i = 0; i < nbinvars; i++ )
271 {
272 SCIP_Real lpsolval;
273 SCIP_Real mipsolval;
274 SCIP_Real rootlpsolval;
275 int j;
276
277 /* get the current LP solution for each variable */
278 lpsolval = SCIPvarGetLPSol(vars[i]);
279 /* get the current MIP solution for each variable */
280 mipsolval = SCIPgetSolVal(scip, bestsol, vars[i]);
281 /* get the root LP solution for each variable */
283
285 {
286 /* update delta */
287 if( nsols > 1 && heurdata->lastnsolsfound != nsolsfound && delta[i] ) /* no need to update delta[i] if already FALSE */
288 {
289 /* no need to update delta[i] if already FALSE or sols[i] already checked on previous run or worse than DINS-solution of last run */
290 for( j = 1; delta[i] && j < checklength && SCIPgetSolHeur(scip, sols[j]) != heur ; j++ )
291 {
292 SCIP_Real solval;
293 solval = SCIPgetSolVal(scip, sols[j], vars[i]);
294 delta[i] = delta[i] && SCIPisFeasEQ(scip, mipsolval, solval);
295 }
296 }
297
298 /* hard fixing if rootlpsolval=nodelpsolval=mipsolval(s) and delta (is TRUE) */
299 if( delta[i] )
300 {
301 fixedvars[nfixedvars] = vars[i];
302 fixedvals[nfixedvars] = mipsolval;
303 ++nfixedvars;
304 }
305 }
306 }
307
308 *binfixings = nfixedvars;
309
310 /* store the number of found solutions for next run */
311 heurdata->lastnsolsfound = nsolsfound;
312
313 /* compute a tighter bound for the variable in the subproblem; */
314 for( i = nbinvars; i < nbinvars + nintvars; ++i )
315 {
316 SCIP_Real lb;
317 SCIP_Real ub;
319
320 /* hard fixing if heuristic bounds coincide */
321 if( ub - lb < 0.5 )
322 {
323 fixedvars[(nfixedvars)] = vars[i];
324 fixedvals[(nfixedvars)] = lb;
325 ++nfixedvars;
326 }
327 }
328
329 *intfixings = nfixedvars - *binfixings;
330
331 return SCIP_OKAY;
332}
333
334/** creates a subproblem for subscip by fixing a number of variables */
335static
337 SCIP* scip, /**< SCIP data structure of the original problem */
338 SCIP* subscip, /**< SCIP data structure of the subproblem */
339 SCIP_VAR** vars, /**< variables of the original problem */
340 SCIP_VAR** subvars, /**< variables of the DINS sub-SCIP */
341 int nbinvars, /**< number of binary variables of problem and subproblem */
342 int nintvars /**< number of general integer variables of problem and subproblem */
343 )
344{
345 int i;
346 /* compute a tighter bound for the variable in the subproblem; */
347 for( i = nbinvars; i < nbinvars + nintvars; ++i )
348 {
349 SCIP_Real lb;
350 SCIP_Real ub;
351
352 if( subvars[i] == NULL )
353 continue;
354
356
357 /* change variable bounds in the DINS subproblem; if bounds coincide, variable should already be fixed */
358 if( ub - lb >= 0.5 )
359 {
360 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) );
361 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) );
362 }
363 else
364 {
366 }
367 }
368
369 return SCIP_OKAY;
370}
371
372/** create the extra constraint of local branching and add it to subscip */
373static
375 SCIP* scip, /**< SCIP data structure of the original problem */
376 SCIP* subscip, /**< SCIP data structure of the subproblem */
377 SCIP_VAR** subvars, /**< variables of the subproblem */
378 SCIP_HEURDATA* heurdata /**< heuristic's data structure */
379 )
380{
381 SCIP_CONS* cons; /* local branching constraint to create */
382 SCIP_VAR** vars;
383 SCIP_SOL* bestsol;
384
385 SCIP_VAR** consvars;
386 SCIP_Real* consvals;
387 SCIP_Real solval;
388 SCIP_Real lhs;
389 SCIP_Real rhs;
390
391 char consname[SCIP_MAXSTRLEN];
392
393 int nbinvars;
394 int i;
395 int nconsvars;
396
397 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_dinsLBcons", SCIPgetProbName(scip));
398
399 /* get the data of the variables and the best solution */
401 bestsol = SCIPgetBestSol(scip);
402 assert(bestsol != NULL);
403
404 /* memory allocation */
407 nconsvars = 0;
408
409 /* set initial left and right hand sides of local branching constraint */
410 lhs = 0.0;
411 rhs = (SCIP_Real) heurdata->neighborhoodsize;
412
413 /* create the distance function of the binary variables (to incumbent solution) */
414 for( i = 0; i < nbinvars; i++ )
415 {
416 if( subvars[i] == NULL )
417 continue;
418
420 if( SCIPvarGetUbGlobal(subvars[i]) - SCIPvarGetLbGlobal(subvars[i]) < 0.5 )
421 continue;
422
423 solval = SCIPgetSolVal(scip, bestsol, vars[i]);
425
426 /* is variable i part of the binary support of the current solution? */
427 if( SCIPisFeasEQ(scip, solval, 1.0) )
428 {
429 consvals[nconsvars] = -1.0;
430 rhs -= 1.0;
431 lhs -= 1.0;
432 }
433 else
434 consvals[nconsvars] = 1.0;
435 consvars[nconsvars++] = subvars[i];
436 }
437
438 /* creates local branching constraint and adds it to subscip */
439 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, consname, nconsvars, consvars, consvals,
440 lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
441 SCIP_CALL( SCIPaddCons(subscip, cons) );
442 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
443
444 /* free local memory */
445 SCIPfreeBufferArray(scip, &consvars);
447
448 return SCIP_OKAY;
449}
450
451static
453
454/** wrapper for the part of heuristic that runs a subscip. Wrapper is needed to avoid possible ressource leaks */
455static
457 SCIP* scip, /**< original SCIP data structure */
458 SCIP* subscip, /**< SCIP structure of the subproblem */
459 SCIP_HEUR* heur, /**< Heuristic pointer */
460 SCIP_HEURDATA* heurdata, /**< Heuristic's data */
461 SCIP_VAR** vars, /**< original problem's variables */
462 SCIP_VAR** fixedvars, /**< Fixed variables of original SCIP */
463 SCIP_Real* fixedvals, /**< Fixed values of original SCIP */
464 SCIP_RESULT* result, /**< Result pointer */
465 int nvars, /**< Number of variables */
466 int nbinvars, /**< Number of binary variables in original SCIP */
467 int nintvars, /**< Number of integer variables in original SCIP */
468 int binfixings, /**< Number of binary fixing in original SCIP */
469 int intfixings, /**< Number of integer fixings in original SCIP */
470 SCIP_Longint nsubnodes /**< Number of nodes in the subscip */
471 )
472{
473 SCIP_VAR** subvars; /* variables of the subscip */
474 SCIP_HASHMAP* varmapfw; /* hashmap for mapping between vars of scip and subscip */
475 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
476 SCIP_Real upperbound; /* upperbound of the original SCIP */
477 SCIP_Real cutoff; /* objective cutoff for the subproblem */
478
479 SCIP_Bool success;
480
481 int i;
482 int nsubsols;
483
484 /* create the variable mapping hash map */
486 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
487
488 success = FALSE;
489 eventhdlr = NULL;
490
491 /* create a problem copy as sub SCIP */
492 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "dins", fixedvars, fixedvals, binfixings + intfixings,
493 heurdata->uselprows, heurdata->copycuts, &success, NULL) );
494
495 /* create event handler for LP events */
497 if( eventhdlr == NULL )
498 {
499 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
500 return SCIP_PLUGINNOTFOUND;
501 }
502
503 SCIPdebugMsg(scip, "Copying the SCIP instance was %ssuccessful.\n", success ? "" : "not ");
504
505 SCIPdebugMsg(scip, "DINS subproblem: %d vars (%d binvars & %d intvars), %d cons\n",
506 SCIPgetNVars(subscip), SCIPgetNBinVars(subscip) , SCIPgetNIntVars(subscip) , SCIPgetNConss(subscip));
507
508 /* store subproblem variables that correspond to original variables */
509 for( i = 0; i < nvars; i++ )
510 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
511
512 /* free hash map */
513 SCIPhashmapFree(&varmapfw);
514
515 /* perform prepared softfixing for all unfixed vars if the number of unfixed vars is larger than the neighborhoodsize (otherwise it will be useless) */
516 if( nbinvars - binfixings > heurdata->neighborhoodsize )
517 {
518 SCIP_CALL( addLocalBranchingConstraint(scip, subscip, subvars, heurdata) );
519 }
520
521 /* rebound integer variables if not all were fixed */
522 if( intfixings < nintvars )
523 {
524 assert(nintvars > 0);
526 }
527
528 /* do not abort subproblem on CTRL-C */
529 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
530
531#ifdef SCIP_DEBUG
532 /* for debugging, enable full output */
533 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
534 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
535#else
536 /* disable statistic timing inside sub SCIP and output to console */
537 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
538 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
539#endif
540
541 /* set limits for the subproblem */
542 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
543 heurdata->nodelimit = nsubnodes;
544 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
545 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nsubnodes/10)) );
546 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
547
548 /* forbid recursive call of heuristics and separators solving subMIPs */
549 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
550
551 /* disable cutting plane separation */
553
554 /* disable expensive presolving */
556
557 /* use best estimate node selection */
558 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
559 {
560 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
561 }
562
563 /* activate uct node selection at the top of the tree */
564 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
565 {
566 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
567 }
568
569 /* use inference branching */
570 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
571 {
572 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
573 }
574
575 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
576 if( !SCIPisParamFixed(subscip, "conflict/enable") )
577 {
578 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
579 }
580 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
581 {
582 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
583 }
584 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
585 {
586 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
587 }
588
589 /* speed up sub-SCIP by not checking dual LP feasibility */
590 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
591
592 /* add an objective cutoff */
594
596 {
597 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
598 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
599 cutoff = MIN(upperbound, cutoff);
600 }
601 else
602 {
603 if( SCIPgetUpperbound(scip) >= 0 )
604 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
605 else
606 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
607 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
608 cutoff = MIN(upperbound, cutoff);
609 }
610 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
611
612 /* catch LP events of sub-SCIP */
613 if( !heurdata->uselprows )
614 {
615 assert(eventhdlr != NULL);
616
617 SCIP_CALL( SCIPtransformProb(subscip) );
619 }
620
621 /* solve the subproblem */
622 SCIPdebugMsg(scip, "solving DINS sub-MIP with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT "\n", heurdata->neighborhoodsize, nsubnodes);
623
624 /* Errors in solving the subproblem should not kill the overall solving process
625 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
626 */
627 SCIP_CALL_ABORT( SCIPsolve(subscip) );
628
629 /* drop LP events of sub-SCIP */
630 if( !heurdata->uselprows )
631 {
632 assert(eventhdlr != NULL);
633
635 }
636
637 /* print solving statistics of subproblem if we are in SCIP's debug mode */
639
640 heurdata->usednodes += SCIPgetNNodes(subscip);
641 nsubsols = SCIPgetNSols(subscip);
642 SCIPdebugMsg(scip, "DINS used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes and found %d solutions\n", SCIPgetNNodes(subscip), nsubnodes, nsubsols);
643
644 /* check, whether a (new) solution was found */
645 if( nsubsols > 0 )
646 {
647 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
648 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
649 if( success )
650 {
651 SCIPdebugMsg(scip, "DINS successfully found new solution\n");
653 }
654 }
655
656 /* free subproblem */
657 SCIPfreeBufferArray(scip, &subvars);
658
659 return SCIP_OKAY;
660}
661
662
663/* ---------------- Callback methods of event handler ---------------- */
664
665/* exec the event handler
666 *
667 * we interrupt the solution process
668 */
669static
671{
673
674 assert(eventhdlr != NULL);
675 assert(eventdata != NULL);
677 assert(event != NULL);
679
680 heurdata = (SCIP_HEURDATA*)eventdata;
681 assert(heurdata != NULL);
682
683 /* interrupt solution process of sub-SCIP */
684 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
685 {
686 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
688 }
689
690 return SCIP_OKAY;
691}
692
693
694/*
695 * Callback methods of primal heuristic
696 */
697
698/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
699static
701{ /*lint --e{715}*/
702 assert(scip != NULL);
703 assert(heur != NULL);
705
706 /* call inclusion method of primal heuristic */
708
709 return SCIP_OKAY;
710}
711
712/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
713static
715{ /*lint --e{715}*/
717
718 assert(heur != NULL);
719 assert(scip != NULL);
720
721 /* get heuristic data */
723 assert(heurdata != NULL);
724
725 /* free heuristic data */
727 SCIPheurSetData(heur, NULL);
728
729 return SCIP_OKAY;
730}
731
732
733/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
734static
736{
738 int i;
739
740 assert(heur != NULL);
741 assert(scip != NULL);
742
743 /* get heuristic's data */
745 assert(heurdata != NULL);
746
747 /* initialize data */
748 heurdata->usednodes = 0;
749 heurdata->lastnsolsfound = 0;
750
751 /* create flag array */
752 heurdata->deltalength = SCIPgetNBinVars(scip);
753
754 /* no binvars => no flag array needed */
755 if( heurdata->deltalength > 0 )
756 {
757 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength) );
758 for( i = 0; i < heurdata->deltalength; i++ )
759 heurdata->delta[i] = TRUE;
760 }
761 return SCIP_OKAY;
762}
763
764/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
765static
767{ /*lint --e{715}*/
769
770 assert(heur != NULL);
771 assert(scip != NULL);
772
773 /* get heuristic data */
775 assert(heurdata != NULL);
776
777 /* free flag array if exist */
778 if( heurdata->deltalength > 0 )
779 {
780 SCIPfreeBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength);
781 }
782 return SCIP_OKAY;
783}
784
785/** execution method of primal heuristic */
786static
788{ /*lint --e{715}*/
790 SCIP* subscip; /* the subproblem created by DINS */
791 SCIP_VAR** vars; /* variables of the original problem */
792 SCIP_VAR** fixedvars;
793 SCIP_Real* fixedvals;
794
795 SCIP_Longint maxnnodes; /* maximum number of subnodes */
796 SCIP_Longint nsubnodes; /* nodelimit for subscip */
797
798 SCIP_RETCODE retcode;
799
800 int nvars; /* number of variables in original SCIP */
801 int nbinvars; /* number of binary variables in original SCIP */
802 int nintvars; /* number of general integer variables in original SCIP */
803 int binfixings;
804 int intfixings;
805
806 SCIP_Bool success; /* used to store whether new solution was found or not */
807
808 assert(heur != NULL);
809 assert(scip != NULL);
810 assert(result != NULL);
812
814
815 /* do not call heuristic of node was already detected to be infeasible */
816 if( nodeinfeasible )
817 return SCIP_OKAY;
818
819 /* only call heuristic, if a CIP solution is at hand */
820 if( SCIPgetNSols(scip) <= 0 )
821 return SCIP_OKAY;
822
823 /* only call heuristic, if an optimal LP solution is at hand */
825 return SCIP_OKAY;
826
827 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
829 return SCIP_OKAY;
830
831 /* get heuristic's data */
833 assert(heurdata != NULL);
834
835 /* only call heuristic, if enough nodes were processed since last incumbent */
837 return SCIP_OKAY;
838
840
841 /* determine the node limit for the current process */
842 maxnnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip));
843
844 /* reward DINS if it succeeded often */
845 maxnnodes = (SCIP_Longint) (maxnnodes * (1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0) / (SCIPheurGetNCalls(heur) + 1.0)));
846
847 /* count the setup costs for the sub-MIP as 100 nodes */
848 maxnnodes -= 100 * SCIPheurGetNCalls(heur);
849 maxnnodes += heurdata->nodesofs;
850
851 /* determine the node limit for the current process */
852 nsubnodes = maxnnodes - heurdata->usednodes;
853 nsubnodes = MIN(nsubnodes , heurdata->maxnodes);
854
855 /* check whether we have enough nodes left to call sub problem solving */
856 if( nsubnodes < heurdata->minnodes )
857 return SCIP_OKAY;
858
859 if( SCIPisStopped(scip) )
860 return SCIP_OKAY;
861
862 /* get required data of the original problem */
865
866 /* do not run heuristic if only continuous variables are present */
867 if( nbinvars == 0 && nintvars == 0 )
868 return SCIP_OKAY;
869
870 /* check whether there is enough time and memory left */
872
873 /* abort if no time is left or not enough memory to create a copy of SCIP */
874 if( !success )
875 return SCIP_OKAY;
876
877 assert(vars != NULL);
878
881
882 /* collect variables that should be fixed in the DINS subproblem */
885
886 /* abort, if all integer variables were fixed (which should not happen for MIP),
887 * but frequently happens for MINLPs using an LP relaxation */
889 goto TERMINATE;
890
891 /* abort, if the amount of fixed variables is insufficient */
892 if( (binfixings + intfixings) / (SCIP_Real)(MAX(nbinvars + nintvars, 1)) < heurdata->minfixingrate )
893 goto TERMINATE;
894
896
897 /* initialize the subproblem */
898 SCIP_CALL( SCIPcreate(&subscip) );
899
900 retcode = wrapperDins(scip, subscip, heur, heurdata, vars, fixedvars, fixedvals, result, nvars, nbinvars, nintvars, binfixings, intfixings, nsubnodes);
901 SCIP_CALL( SCIPfree(&subscip) );
902
903 SCIP_CALL( retcode );
904
905 TERMINATE:
907 SCIPfreeBufferArray(scip, &fixedvars);
908
909 return SCIP_OKAY;
910}
911
912
913/*
914 * primal heuristic specific interface methods
915 */
917/** creates the DINS primal heuristic and includes it in SCIP */
919 SCIP* scip /**< SCIP data structure */
920 )
921{
923 SCIP_HEUR* heur;
924
925 /* create Dins primal heuristic data */
927
928 /* include primal heuristic */
932
933 assert(heur != NULL);
934
935 /* set non-NULL pointers to callback methods */
940
941 /* add DINS primal heuristic parameters */
942 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
943 "number of nodes added to the contingent of the total nodes",
945 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
946 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
947 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
948 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
949 "minimum number of nodes required to start the subproblem",
951 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solnum",
952 "number of pool-solutions to be checked for flag array update (for hard fixing of binary variables)",
953 &heurdata->solnum, FALSE, DEFAULT_SOLNUM, 1, INT_MAX, NULL, NULL) );
954 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize",
955 "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
956 &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
957 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
958 "maximum number of nodes to regard in the subproblem",
960 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
961 "factor by which " HEUR_NAME " should at least improve the incumbent",
962 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
963 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
964 "number of nodes without incumbent change that heuristic should wait",
966
967 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
968 "factor by which the limit on the number of LP depends on the node limit",
969 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
970
971 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
972 "minimum percentage of integer variables that have to be fixable",
973 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
974
975 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
976 "should subproblem be created out of the rows in the LP rows?",
977 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
978
979 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
980 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
981 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
982
983 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
984 "should uct node selection be used at the beginning of the search?",
985 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
986
987 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
988 "limit on number of improving incumbent solutions in sub-CIP",
989 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
990
991 return SCIP_OKAY;
992}
Constraint handler for linear constraints in their most general form, .
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_Longint
Definition def.h:171
#define SCIP_REAL_MAX
Definition def.h:187
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL_ABORT(x)
Definition def.h:367
#define REALABS(x)
Definition def.h:210
#define SCIP_LONGINT_MAX
Definition def.h:172
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition scip_copy.c:1448
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition scip_copy.c:3249
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition scip_copy.c:3292
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3042
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3058
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3024
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:111
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition scip_param.c:219
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 SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition scip_param.c:545
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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition scip_param.c:883
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:932
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition scip_param.c:661
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 SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:958
SCIP_RETCODE SCIPincludeHeurDins(SCIP *scip)
Definition heur_dins.c:916
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition scip_event.c:104
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition event.c:324
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition event.c:1030
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition scip_event.c:320
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 SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1596
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1576
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:242
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition heur.c:1371
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
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2313
SCIP_HEUR * SCIPgetSolHeur(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1684
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2214
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1657
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2263
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:367
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition heuristics.c:925
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition var.c:13339
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4943
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18274
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:5032
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
#define DEFAULT_NODESQUOT
Definition heur_dins.c:76
#define DEFAULT_NWAITINGNODES
Definition heur_dins.c:79
#define DEFAULT_NODESOFS
Definition heur_dins.c:72
#define DEFAULT_COPYCUTS
Definition heur_dins.c:83
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nbinvars, int nintvars, int *binfixings, int *intfixings)
Definition heur_dins.c:204
#define DEFAULT_MAXNODES
Definition heur_dins.c:73
#define HEUR_TIMING
Definition heur_dins.c:69
#define DEFAULT_MINNODES
Definition heur_dins.c:74
#define HEUR_FREQOFS
Definition heur_dins.c:67
#define HEUR_DESC
Definition heur_dins.c:63
#define DEFAULT_LPLIMFAC
Definition heur_dins.c:77
#define DEFAULT_NEIGHBORHOODSIZE
Definition heur_dins.c:80
#define DEFAULT_MINFIXINGRATE
Definition heur_dins.c:78
#define DEFAULT_USEUCT
Definition heur_dins.c:86
#define HEUR_DISPCHAR
Definition heur_dins.c:64
#define HEUR_MAXDEPTH
Definition heur_dins.c:68
#define HEUR_PRIORITY
Definition heur_dins.c:65
#define DEFAULT_SOLNUM
Definition heur_dins.c:81
#define DEFAULT_MINIMPROVE
Definition heur_dins.c:75
#define HEUR_NAME
Definition heur_dins.c:62
#define DEFAULT_USELPROWS
Definition heur_dins.c:82
#define DEFAULT_BESTSOLLIMIT
Definition heur_dins.c:85
#define EVENTHDLR_DESC
Definition heur_dins.c:91
#define HEUR_FREQ
Definition heur_dins.c:66
#define HEUR_USESSUBSCIP
Definition heur_dins.c:70
#define EVENTHDLR_NAME
Definition heur_dins.c:90
static void computeIntegerVariableBounds(SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr)
Definition heur_dins.c:130
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata)
Definition heur_dins.c:372
static SCIP_RETCODE reboundIntegerVariables(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_VAR **subvars, int nbinvars, int nintvars)
Definition heur_dins.c:334
static SCIP_RETCODE wrapperDins(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, SCIP_RESULT *result, int nvars, int nbinvars, int nintvars, int binfixings, int intfixings, SCIP_Longint nsubnodes)
Definition heur_dins.c:454
DINS primal heuristic.
SCIP_Longint nsolsfound
SCIP_Bool cutoff
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
heurdata usednodes
Definition heur_locks.c:158
SCIP_VAR * var
static SCIP_VAR ** vars
int nbinvars
int nintvars
methods commonly used by primal heuristics
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing events
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebug(x)
Definition pub_message.h:93
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for event handler plugins and event handlers
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 node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for SCIP variables
#define MAX(x, y)
Definition tclique_def.h:92
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_LPSOLVED
Definition type_event.h:101
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:131
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:96
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:104
#define SCIP_DECL_HEUREXITSOL(x)
Definition type_heur.h:142
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_PARAMSETTING_OFF
@ SCIP_PARAMSETTING_FAST
@ 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
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_PLUGINNOTFOUND
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62