Scippy

SCIP

Solving Constraint Integer Programs

heur_mutation.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_mutation.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LNS heuristic that tries to randomly mutate the incumbent solution
28 * @author Timo Berthold
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/heuristics.h"
35#include "scip/heur_mutation.h"
36#include "scip/pub_heur.h"
37#include "scip/pub_message.h"
38#include "scip/pub_misc.h"
39#include "scip/pub_sol.h"
40#include "scip/pub_var.h"
41#include "scip/scip_branch.h"
42#include "scip/scip_cons.h"
43#include "scip/scip_copy.h"
44#include "scip/scip_general.h"
45#include "scip/scip_heur.h"
46#include "scip/scip_mem.h"
47#include "scip/scip_message.h"
48#include "scip/scip_nodesel.h"
49#include "scip/scip_numerics.h"
50#include "scip/scip_param.h"
51#include "scip/scip_prob.h"
53#include "scip/scip_sol.h"
54#include "scip/scip_solve.h"
56#include <string.h>
57
58#define HEUR_NAME "mutation"
59#define HEUR_DESC "mutation heuristic randomly fixing variables"
60#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
61#define HEUR_PRIORITY -1103010
62#define HEUR_FREQ -1
63#define HEUR_FREQOFS 8
64#define HEUR_MAXDEPTH -1
65#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
66#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
67
68#define DEFAULT_NODESOFS 500 /**< number of nodes added to the contingent of the total nodes */
69#define DEFAULT_MAXNODES 5000 /**< maximum number of nodes to regard in the subproblem */
70#define DEFAULT_MINIMPROVE 0.01 /**< factor by which Mutation should at least improve the incumbent */
71#define DEFAULT_MINNODES 500 /**< minimum number of nodes to regard in the subproblem */
72#define DEFAULT_MINFIXINGRATE 0.8 /**< minimum percentage of integer variables that have to be fixed */
73#define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
74#define DEFAULT_NWAITINGNODES 200 /**< number of nodes without incumbent change that heuristic should wait */
75#define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
76 * otherwise, the copy constructors of the constraints handlers are used */
77#define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
78 * cutpool of the original scip be copied to constraints of the subscip */
79#define DEFAULT_BESTSOLLIMIT -1 /**< limit on number of improving incumbent solutions in sub-CIP */
80#define DEFAULT_USEUCT FALSE /**< should uct node selection be used at the beginning of the search? */
81#define DEFAULT_RANDSEED 19 /**< initial random seed */
82/*
83 * Data structures
84 */
85
86/** primal heuristic data */
87struct SCIP_HeurData
88{
89 int nodesofs; /**< number of nodes added to the contingent of the total nodes */
90 int maxnodes; /**< maximum number of nodes to regard in the subproblem */
91 int minnodes; /**< minimum number of nodes to regard in the subproblem */
92 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
93 int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
94 SCIP_Real minimprove; /**< factor by which Mutation should at least improve the incumbent */
95 SCIP_Longint usednodes; /**< nodes already used by Mutation in earlier calls */
96 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
97 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
98 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
99 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
100 * to constraints in subproblem?
101 */
102 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
103 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
104};
105
106
107/*
108 * Local methods
109 */
110
111/** determine variables and values which should be fixed in the mutation subproblem */
112static
114 SCIP* scip, /**< original SCIP data structure */
115 SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */
116 SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */
117 int* nfixedvars, /**< pointer to store the number of variables that should be fixed */
118 SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */
119 SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
120 SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */
121 )
122{
123 SCIP_VAR** vars; /* original scip variables */
124 SCIP_SOL* sol; /* pool of solutions */
125
126 int nvars;
127 int nbinvars;
128 int nintvars;
129 int ndiscretevars;
130 int i;
131
132 assert(fixedvars != NULL);
133 assert(fixedvals != NULL);
134
135 /* get required data of the original problem */
136 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
137 sol = SCIPgetBestSol(scip);
138 assert(sol != NULL);
139
140 /* compute the number of variables that should be fixed in the subproblem */
141 *nfixedvars = (int)(minfixingrate * (nbinvars + nintvars));
142
143 /* avoid the two corner cases that no or all discrete variables should be fixed */
144 if( *nfixedvars == 0 || *nfixedvars == nbinvars + nintvars )
145 {
146 *success = FALSE;
147 return SCIP_OKAY;
148 }
149 assert(*nfixedvars < nbinvars + nintvars);
150
151 ndiscretevars = nbinvars + nintvars;
152 /* copy the binary and integer variables into fixedvars */
153 BMScopyMemoryArray(fixedvars, vars, ndiscretevars);
154
155 /* shuffle the array randomly */
156 SCIPrandomPermuteArray(randnumgen, (void **)fixedvars, 0, nbinvars + nintvars);
157
158 *success = TRUE;
159 /* store the fixing values for the subset of variables that should be fixed */
160 for( i = 0; i < *nfixedvars; ++i )
161 {
162 /* fix all randomly marked variables */
163 SCIP_Real solval;
164 SCIP_Real lb;
165 SCIP_Real ub;
166
167 solval = SCIPgetSolVal(scip, sol, fixedvars[i]);
168 lb = SCIPvarGetLbGlobal(fixedvars[i]);
169 ub = SCIPvarGetUbGlobal(fixedvars[i]);
170 assert(SCIPisLE(scip, lb, ub));
171
172 /* due to dual reductions, it may happen that the solution value is not in
173 the variable's domain anymore */
174 if( SCIPisLT(scip, solval, lb) )
175 solval = lb;
176 else if( SCIPisGT(scip, solval, ub) )
177 solval = ub;
178
179 /* we cannot fix to infinite solution values, better break in this case */
180 if( SCIPisInfinity(scip, REALABS(solval)) )
181 {
182 *success = FALSE;
183 break;
184 }
185
186 /* store the possibly adjusted solution value as fixing value */
187 fixedvals[i] = solval;
188 }
189
190 return SCIP_OKAY;
191}
192
193/** setup and solve mutation sub-SCIP */
194static
196 SCIP* scip, /**< SCIP data structure */
197 SCIP* subscip, /**< sub-SCIP data structure */
198 SCIP_HEUR* heur, /**< mutation heuristic */
199 SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */
200 SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */
201 int nfixedvars, /**< the number of variables that should be fixed */
202 SCIP_Longint nsubnodes, /**< node limit for the subproblem */
203 SCIP_RESULT* result /**< pointer to store the result */
204 )
205{
206 SCIP_VAR** subvars; /* subproblem's variables */
207 SCIP_VAR** vars; /* original problem's variables */
208 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
209 SCIP_HEURDATA* heurdata;
210 SCIP_Real cutoff; /* objective cutoff for the subproblem */
211 SCIP_Real upperbound;
212 int nvars; /* number of original problem's variables */
213 int i;
214 SCIP_Bool success;
215
216 assert(scip != NULL);
217 assert(subscip != NULL);
218 assert(heur != NULL);
219 assert(fixedvars != NULL);
220 assert(fixedvals != NULL);
221
222 heurdata = SCIPheurGetData(heur);
223 assert(heurdata != NULL);
224
225 vars = SCIPgetVars(scip);
226 nvars = SCIPgetNVars(scip);
227
228 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
229
230 /* create the variable mapping hash map */
231 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
232
233 /* create a problem copy as sub SCIP */
234 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "mutation", fixedvars, fixedvals, nfixedvars,
235 heurdata->uselprows, heurdata->copycuts, &success, NULL) );
236
237 for( i = 0; i < nvars; i++ )
238 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
239
240 /* free hash map */
241 SCIPhashmapFree(&varmapfw);
242
243 /* do not abort subproblem on CTRL-C */
244 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
245
246#ifdef SCIP_DEBUG
247 /* for debugging, enable full output */
248 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
249 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
250#else
251 /* disable statistic timing inside sub SCIP and output to console */
252 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
253 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
254#endif
255
256 /* set limits for the subproblem */
257 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
258 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
259 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
260
261 /* forbid recursive call of heuristics and separators solving subMIPs */
262 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
263
264 /* disable cutting plane separation */
266
267 /* disable expensive presolving */
269
270 /* use best estimate node selection */
271 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
272 {
273 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
274 }
275
276 /* activate uct node selection at the top of the tree */
277 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
278 {
279 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
280 }
281
282 /* use inference branching */
283 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
284 {
285 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
286 }
287
288 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
289 if( !SCIPisParamFixed(subscip, "conflict/enable") )
290 {
291 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
292 }
293 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
294 {
295 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
296 }
297 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
298 {
299 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
300 }
301
302 /* speed up sub-SCIP by not checking dual LP feasibility */
303 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
304
305 /* add an objective cutoff */
307
308 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
310 {
311 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
312 + heurdata->minimprove * SCIPgetLowerbound(scip);
313 }
314 else
315 {
316 if( SCIPgetUpperbound(scip) >= 0 )
317 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
318 else
319 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
320 }
321 cutoff = MIN(upperbound, cutoff);
322 SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
323
324 /* solve the subproblem
325 *
326 * Errors in solving the subproblem should not kill the overall solving process
327 * Hence, the return code is caught but only in debug mode, SCIP will stop.
328 */
329 SCIPdebugMsg(scip, "Solve Mutation subMIP\n");
330 SCIP_CALL_ABORT( SCIPsolve(subscip) );
331
332 /* transfer variable statistics from sub-SCIP */
333 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
334
335 /* print solving statistics of subproblem if we are in SCIP's debug mode */
337
338 heurdata->usednodes += SCIPgetNNodes(subscip);
339
340 /* check, whether a solution was found;
341 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
342 */
343 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
344 if( success )
345 *result = SCIP_FOUNDSOL;
346
347 /* free subproblem */
348 SCIPfreeBufferArray(scip, &subvars);
349
350 return SCIP_OKAY;
351}
352
353
354/*
355 * Callback methods of primal heuristic
356 */
357
358/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
359static
360SCIP_DECL_HEURCOPY(heurCopyMutation)
361{ /*lint --e{715}*/
362 assert(scip != NULL);
363 assert(heur != NULL);
364 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
365
366 /* call inclusion method of primal heuristic */
368
369 return SCIP_OKAY;
370}
371
372/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
373static
374SCIP_DECL_HEURFREE(heurFreeMutation)
375{ /*lint --e{715}*/
376 SCIP_HEURDATA* heurdata;
377
378 assert(heur != NULL);
379 assert(scip != NULL);
380
381 /* get heuristic data */
382 heurdata = SCIPheurGetData(heur);
383 assert(heurdata != NULL);
384
385 /* free heuristic data */
386 SCIPfreeBlockMemory(scip, &heurdata);
387 SCIPheurSetData(heur, NULL);
388
389 return SCIP_OKAY;
390}
391
392/** initialization method of primal heuristic (called after problem was transformed) */
393static
394SCIP_DECL_HEURINIT(heurInitMutation)
395{ /*lint --e{715}*/
396 SCIP_HEURDATA* heurdata;
397
398 assert(heur != NULL);
399 assert(scip != NULL);
400
401 /* get heuristic's data */
402 heurdata = SCIPheurGetData(heur);
403 assert(heurdata != NULL);
404
405 /* initialize data */
406 heurdata->usednodes = 0;
407
408 /* create random number generator */
409 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
411
412 return SCIP_OKAY;
413}
414
415/** deinitialization method of primal heuristic */
416static
417SCIP_DECL_HEUREXIT(heurExitMutation)
418{ /*lint --e{715}*/
419 SCIP_HEURDATA* heurdata;
420
421 assert(heur != NULL);
422 assert(scip != NULL);
423
424 /* get heuristic data */
425 heurdata = SCIPheurGetData(heur);
426 assert(heurdata != NULL);
427
428 /* free random number generator */
429 SCIPfreeRandom(scip, &heurdata->randnumgen);
430
431 return SCIP_OKAY;
432}
433
434/** execution method of primal heuristic */
435static
436SCIP_DECL_HEUREXEC(heurExecMutation)
437{ /*lint --e{715}*/
438 SCIP_Longint maxnnodes;
439 SCIP_Longint nsubnodes; /* node limit for the subproblem */
440
441 SCIP_HEURDATA* heurdata; /* heuristic's data */
442 SCIP* subscip; /* the subproblem created by mutation */
443 SCIP_VAR** fixedvars; /* array to store variables that should be fixed in the subproblem */
444 SCIP_Real* fixedvals; /* array to store fixing values for the variables */
445
446 SCIP_Real maxnnodesr;
447
448 int nfixedvars;
449 int nbinvars;
450 int nintvars;
451
452 SCIP_Bool success;
453
454 SCIP_RETCODE retcode;
455
456 assert( heur != NULL );
457 assert( scip != NULL );
458 assert( result != NULL );
459
460 /* get heuristic's data */
461 heurdata = SCIPheurGetData(heur);
462 assert(heurdata != NULL);
463
464 *result = SCIP_DELAYED;
465
466 /* only call heuristic, if feasible solution is available */
467 if( SCIPgetNSols(scip) <= 0 )
468 return SCIP_OKAY;
469
470 /* only call heuristic, if the best solution comes from transformed problem */
471 assert(SCIPgetBestSol(scip) != NULL);
473 return SCIP_OKAY;
474
475 /* only call heuristic, if enough nodes were processed since last incumbent */
476 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes)
477 return SCIP_OKAY;
478
479 *result = SCIP_DIDNOTRUN;
480
481 SCIP_CALL( SCIPgetVarsData(scip, NULL, NULL, &nbinvars, &nintvars, NULL, NULL) );
482
483 /* only call heuristic, if discrete variables are present */
484 if( nbinvars + nintvars == 0 )
485 return SCIP_OKAY;
486
487 /* calculate the maximal number of branching nodes until heuristic is aborted */
488 maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip);
489
490 /* reward mutation if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */
491 maxnnodesr *= 1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0);
492 maxnnodes = (SCIP_Longint) maxnnodesr - 100 * SCIPheurGetNCalls(heur);
493 maxnnodes += heurdata->nodesofs;
494
495 /* determine the node limit for the current process */
496 nsubnodes = maxnnodes - heurdata->usednodes;
497 nsubnodes = MIN(nsubnodes, heurdata->maxnodes);
498
499 /* check whether we have enough nodes left to call subproblem solving */
500 if( nsubnodes < heurdata->minnodes )
501 return SCIP_OKAY;
502
503 if( SCIPisStopped(scip) )
504 return SCIP_OKAY;
505
506 /* check whether there is enough time and memory left */
507 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
508
509 if( !success )
510 return SCIP_OKAY;
511
512 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
513 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
514
515 /* determine variables that should be fixed in the mutation subproblem */
516 SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata->minfixingrate, heurdata->randnumgen, &success) );
517
518 /* terminate if it is not possible to create the subproblem */
519 if( !success )
520 {
521 SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n");
522 goto TERMINATE;
523 }
524
525 *result = SCIP_DIDNOTFIND;
526
527 /* initializing the subproblem */
528 SCIP_CALL( SCIPcreate(&subscip) );
529
530 /* setup and solve the subproblem and catch the return code */
531 retcode = setupAndSolveSubscipMutation(scip, subscip, heur, fixedvars, fixedvals, nfixedvars, nsubnodes, result);
532
533 /* free the subscip in any case */
534 SCIP_CALL( SCIPfree(&subscip) );
535 SCIP_CALL( retcode );
536
537 /* free storage for subproblem fixings */
538 TERMINATE:
539 SCIPfreeBufferArray(scip, &fixedvals);
540 SCIPfreeBufferArray(scip, &fixedvars);
541
542 return SCIP_OKAY;
543}
544
545/*
546 * primal heuristic specific interface methods
547 */
548
549/** creates the mutation primal heuristic and includes it in SCIP */
551 SCIP* scip /**< SCIP data structure */
552 )
553{
554 SCIP_HEURDATA* heurdata;
555 SCIP_HEUR* heur;
556
557 /* create Mutation primal heuristic data */
558 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
559
560 /* include primal heuristic */
563 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMutation, heurdata) );
564
565 assert(heur != NULL);
566
567 /* set non-NULL pointers to callback methods */
568 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyMutation) );
569 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeMutation) );
570 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitMutation) );
571 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitMutation) );
572
573 /* add mutation primal heuristic parameters */
574 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
575 "number of nodes added to the contingent of the total nodes",
576 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
577
578 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
579 "maximum number of nodes to regard in the subproblem",
580 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
581
582 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
583 "minimum number of nodes required to start the subproblem",
584 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
585
586 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
587 "number of nodes without incumbent change that heuristic should wait",
588 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
589
590 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
591 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
592 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
593
594 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
595 "percentage of integer variables that have to be fixed",
596 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
597
598 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
599 "factor by which " HEUR_NAME " should at least improve the incumbent",
600 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
601
602 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
603 "should subproblem be created out of the rows in the LP rows?",
604 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
605
606 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
607 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
608 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
609
610 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
611 "limit on number of improving incumbent solutions in sub-CIP",
612 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
613
614 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
615 "should uct node selection be used at the beginning of the search?",
616 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
617
618 return SCIP_OKAY;
619}
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#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 SCIP_CALL_ABORT(x)
Definition: def.h:353
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
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:3253
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip_copy.c:1265
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
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_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
#define SCIPdebugMsg
Definition: scip_message.h:78
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:904
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
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:979
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randnumgen, void **array, int begin, int end)
Definition: misc.c:10179
SCIP_RETCODE SCIPincludeHeurMutation(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
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
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#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)
Definition: scip_nodesel.c:234
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2721
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1513
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(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:951
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define DEFAULT_NODESQUOT
Definition: heur_mutation.c:73
#define DEFAULT_NWAITINGNODES
Definition: heur_mutation.c:74
#define DEFAULT_NODESOFS
Definition: heur_mutation.c:68
#define DEFAULT_COPYCUTS
Definition: heur_mutation.c:77
#define DEFAULT_MAXNODES
Definition: heur_mutation.c:69
#define HEUR_TIMING
Definition: heur_mutation.c:65
#define DEFAULT_MINNODES
Definition: heur_mutation.c:71
#define HEUR_FREQOFS
Definition: heur_mutation.c:63
#define HEUR_DESC
Definition: heur_mutation.c:59
#define DEFAULT_MINFIXINGRATE
Definition: heur_mutation.c:72
#define DEFAULT_USEUCT
Definition: heur_mutation.c:80
#define HEUR_DISPCHAR
Definition: heur_mutation.c:60
#define HEUR_MAXDEPTH
Definition: heur_mutation.c:64
static SCIP_RETCODE setupAndSolveSubscipMutation(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Longint nsubnodes, SCIP_RESULT *result)
#define HEUR_PRIORITY
Definition: heur_mutation.c:61
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, SCIP_Real minfixingrate, SCIP_RANDNUMGEN *randnumgen, SCIP_Bool *success)
static SCIP_DECL_HEUREXEC(heurExecMutation)
#define DEFAULT_MINIMPROVE
Definition: heur_mutation.c:70
#define HEUR_NAME
Definition: heur_mutation.c:58
#define DEFAULT_USELPROWS
Definition: heur_mutation.c:75
#define DEFAULT_BESTSOLLIMIT
Definition: heur_mutation.c:79
static SCIP_DECL_HEUREXIT(heurExitMutation)
static SCIP_DECL_HEURFREE(heurFreeMutation)
#define DEFAULT_RANDSEED
Definition: heur_mutation.c:81
#define HEUR_FREQ
Definition: heur_mutation.c:62
#define HEUR_USESSUBSCIP
Definition: heur_mutation.c:66
static SCIP_DECL_HEURINIT(heurInitMutation)
static SCIP_DECL_HEURCOPY(heurCopyMutation)
LNS heuristic that tries to randomly mutate the incumbent solution.
methods commonly used by primal heuristics
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for primal heuristics
public methods for message output
#define SCIPdebug(x)
Definition: pub_message.h:93
public data structures and miscellaneous methods
public methods for primal CIP solutions
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
general public methods
public methods for primal heuristic plugins and divesets
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 random numbers
public methods for solutions
public solving methods
public methods for querying solving statistics
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:63
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
@ 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_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63