SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_ofins.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_ofins.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief OFINS - Objective Function Induced Neighborhood Search - a primal heuristic for reoptimization
28 * @author Jakob Witzig
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_ofins.h"
36#include "scip/pub_event.h"
37#include "scip/pub_heur.h"
38#include "scip/pub_message.h"
39#include "scip/pub_misc.h"
40#include "scip/pub_sol.h"
41#include "scip/pub_var.h"
42#include "scip/scip_branch.h"
43#include "scip/scip_copy.h"
44#include "scip/scip_event.h"
45#include "scip/scip_general.h"
46#include "scip/scip_heur.h"
47#include "scip/scip_mem.h"
48#include "scip/scip_message.h"
49#include "scip/scip_nodesel.h"
50#include "scip/scip_numerics.h"
51#include "scip/scip_param.h"
52#include "scip/scip_prob.h"
53#include "scip/scip_sol.h"
54#include "scip/scip_solve.h"
56#include "scip/scip_timing.h"
57#include <string.h>
58
59#define HEUR_NAME "ofins"
60#define HEUR_DESC "primal heuristic for reoptimization, objective function induced neighborhood search"
61#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
62#define HEUR_PRIORITY 60000
63#define HEUR_FREQ 0
64#define HEUR_FREQOFS 0
65#define HEUR_MAXDEPTH 0
66#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
67#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
68
69/* default values for OFINS-specific plugins */
70#define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
71#define DEFAULT_MAXCHGRATE 0.50 /**< maximum percentage of changed objective coefficients */
72#define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
73 * of the original scip be copied to constraints of the subscip */
74#define DEFAULT_MAXCHANGE 0.04 /**< maximal rate of change per coefficient to get fixed */
75#define DEFAULT_MINIMPROVE 0.01 /**< factor by which OFINS should at least improve the incumbent */
76#define DEFAULT_ADDALLSOLS FALSE /**< should all subproblem solutions be added to the original SCIP? */
77#define DEFAULT_MINNODES 50LL /**< minimum number of nodes to regard in the subproblem */
78#define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
79#define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
80#define DEFAULT_LPLIMFAC 2.0 /**< factor by which the limit on the number of LP depends on the node limit */
81
82/* event handler properties */
83#define EVENTHDLR_NAME "Ofins"
84#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
85
86
87/** primal heuristic data */
88struct SCIP_HeurData
89{
90 SCIP_Real maxchangerate; /**< maximal rate of changed coefficients in the objective function */
91 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
92 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in subproblem? */
93 SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
94 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
95 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
96 SCIP_Real maxchange; /**< maximal rate of change per coefficient to get fixed */
97 SCIP_Real minimprove; /**< factor by which OFINS should at least improve the incumbent */
98 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
99 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
100 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
101};
102
103/* ---------------- Callback methods of event handler ---------------- */
104
105/* exec the event handler
106 *
107 * we interrupt the solution process
108 */
109static
110SCIP_DECL_EVENTEXEC(eventExecOfins)
111{
113
114 assert(eventhdlr != NULL);
115 assert(eventdata != NULL);
116 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
117 assert(event != NULL);
119
120 heurdata = (SCIP_HEURDATA*)eventdata;
121 assert(heurdata != NULL);
122
123 /* interrupt solution process of sub-SCIP */
124 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
125 {
126 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
128 }
129
130 return SCIP_OKAY;
131}
132
133/* setup and solve the sub-SCIP */
134static
136 SCIP* scip, /**< original SCIP data structure */
137 SCIP* subscip, /**< sub-SCIP data structure */
138 SCIP_HEUR* heur, /**< heuristic data structure */
139 SCIP_HEURDATA* heurdata, /**< euristic's private data structure */
140 SCIP_RESULT* result, /**< result data structure */
141 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
142 SCIP_Bool* chgcoeffs /**< array of changed coefficients */
143
144 )
145{
146 SCIP_HASHMAP* varmapfw;
147 SCIP_VAR** vars;
148 SCIP_VAR** subvars;
149 SCIP_EVENTHDLR* eventhdlr;
150
151 SCIP_SOL* sol;
152 SCIP_VAR** fixedvars;
153 SCIP_Real* fixedvals;
154 int nfixedvars;
155
156 int nvars;
157 int nintvars;
158 int i;
159
160 SCIP_SOL** subsols;
161 int nsubsols = 0;
162
163 SCIP_Bool success;
164 SCIP_RETCODE retcode;
165 SCIP_STATUS status;
166
167 assert(scip != NULL);
168 assert(subscip != NULL);
169 assert(heur != NULL);
170 assert(heurdata != NULL);
171 assert(result != NULL);
172 assert(chgcoeffs != NULL);
173
174 SCIPdebugMsg(scip, "+---+ Start OFINS heuristic +---+\n");
175
176 /* get variable data */
179
180 /* create the variable mapping hash map */
181 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
182
183 /* get optimal solution of the last iteration */
185
186 /* if the solution is NULL the last problem was infeasible */
187 if( sol == NULL )
188 return SCIP_OKAY;
189
191 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nvars) );
192 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nvars) );
193
194 /* determine variables to fix in the sub-SCIP */
195 nfixedvars = 0;
196 for( i = 0; i < nintvars; i++ )
197 {
198 if( !chgcoeffs[i] )
199 {
200 fixedvars[nfixedvars] = vars[i];
201 fixedvals[nfixedvars] = SCIPgetSolVal(scip, sol, vars[i]);
202 ++nfixedvars;
203 }
204 }
205
206 /* create a problem copy as sub SCIP */
207 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "ofins", fixedvars, fixedvals, nfixedvars, FALSE,
208 FALSE, &success, NULL) );
209 assert(success);
210
211 SCIPfreeBufferArrayNull(scip, &fixedvals);
212 SCIPfreeBufferArrayNull(scip, &fixedvars);
213
214 /* create event handler for LP events */
215 eventhdlr = NULL;
216 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecOfins, NULL) );
217 if( eventhdlr == NULL )
218 {
219 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
220 return SCIP_PLUGINNOTFOUND;
221 }
222
224 for( i = 0; i < nvars; i++ )
225 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
226
227 /* free hash map */
228 SCIPhashmapFree(&varmapfw);
229
230 /* set an objective limit */
231 SCIPdebugMsg(scip, "set objective limit of %g to sub-SCIP\n", SCIPgetUpperbound(scip));
233
234 SCIPdebugMsg(scip, "OFINS subproblem: %d vars, %d cons\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip));
235
236 /* do not abort subproblem on CTRL-C */
237 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
238
239#ifdef SCIP_DEBUG
240 /* for debugging, enable full output */
241 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
242 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
243#else
244 /* disable statistic timing inside sub SCIP and output to console */
245 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
246 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
247#endif
248
249 /* set limits for the subproblem */
250 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
251 heurdata->nodelimit = heurdata->maxnodes;
252 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
253 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
254
255 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
256 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
257
258 /* disable cutting plane separation */
260
261 /* disable expensive presolving */
263
264 /* use best estimate node selection */
265 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
266 {
267 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
268 }
269
270 /* use inference branching */
271 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
272 {
273 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
274 }
275
276 /* disable conflict analysis */
277 if( !SCIPisParamFixed(subscip, "conflict/enable") )
278 {
279 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
280 }
281
282 /* speed up sub-SCIP by not checking dual LP feasibility */
283 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
284
285 /* presolve the subproblem */
286 retcode = SCIPpresolve(subscip);
287
288 /* errors in solving the subproblem should not kill the overall solving process;
289 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
290 */
291 if( retcode != SCIP_OKAY )
292 {
293 SCIPwarningMessage(scip, "Error while presolving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode);
294
295 SCIPABORT(); /*lint --e{527}*/
296
297 /* free */
298 SCIPfreeBufferArray(scip, &subvars);
299 return SCIP_OKAY;
300 }
301
302 SCIPdebugMsg(scip, "%s presolved subproblem: %d vars, %d cons\n", HEUR_NAME, SCIPgetNVars(subscip), SCIPgetNConss(subscip));
303
304 assert(eventhdlr != NULL);
305
306 SCIP_CALL( SCIPtransformProb(subscip) );
308
309 /* solve the subproblem */
310 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
311
312 /* errors in solving the subproblem should not kill the overall solving process;
313 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
314 */
315 SCIP_CALL_ABORT( SCIPsolve(subscip) );
316
318
319 /* print solving statistics of subproblem if we are in SCIP's debug mode */
321
322 status = SCIPgetStatus(subscip);
323
324 switch (status) {
326 break;
329 {
330 /* transfer the primal ray from the sub-SCIP to the main SCIP */
331 if( SCIPhasPrimalRay(subscip) )
332 {
333 SCIP_SOL* primalray;
334
335 SCIP_CALL( SCIPcreateSol(scip, &primalray, heur) );
336
337 /* transform the ray into the space of the source scip */
338 for( i = 0; i < nvars; i++ )
339 {
340 SCIP_CALL( SCIPsetSolVal(scip, primalray, vars[i],
341 subvars[i] != NULL ? SCIPgetPrimalRayVal(subscip, subvars[i]) : 0.0) );
342 }
343
344 SCIPdebug( SCIP_CALL( SCIPprintRay(scip, primalray, 0, FALSE) ); );
345
346 /* update the primal ray of the source scip */
347 SCIP_CALL( SCIPupdatePrimalRay(scip, primalray) );
348 SCIP_CALL( SCIPfreeSol(scip, &primalray) );
349
351 }
352
353 break;
354 }
355 default:
356 /* check, whether a solution was found;
357 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
358 */
359 nsubsols = SCIPgetNSols(subscip);
360 subsols = SCIPgetSols(subscip);
361 success = FALSE;
362 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); i++ )
363 {
364 SCIP_SOL* newsol;
365
366 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) );
367
368 /* try to add new solution to scip and free it immediately */
369 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
370
371 if( success )
373 }
374 break;
375 } /*lint !e788*/
376
377 SCIPstatisticPrintf("%s statistic: fixed %6.3f integer variables, needed %6.1f seconds, %" SCIP_LONGINT_FORMAT " nodes, solution %10.4f found at node %" SCIP_LONGINT_FORMAT "\n",
378 HEUR_NAME, 0.0, SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip),
379 nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
380
381 /* free subproblem */
382 SCIPfreeBufferArray(scip, &subvars);
383
384 return SCIP_OKAY;
385}
386
387/** main procedure of the OFINS heuristic, creates and solves a sub-SCIP */
388static
390 SCIP* scip, /**< original SCIP data structure */
391 SCIP_HEUR* heur, /**< heuristic data structure */
392 SCIP_HEURDATA* heurdata, /**< euristic's private data structure */
393 SCIP_RESULT* result, /**< result data structure */
394 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
395 SCIP_Bool* chgcoeffs /**< array of changed coefficients */
396 )
397{
398 SCIP* subscip;
399 SCIP_RETCODE retcode;
400 SCIP_Bool success;
401
402 assert(scip != NULL);
403 assert(heur != NULL);
404 assert(heurdata != NULL);
405 assert(result != NULL);
406 assert(chgcoeffs != NULL);
407
409
410 /* check whether there is enough time and memory left */
411 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
412
413 if( !success )
414 return SCIP_OKAY;
415
417
418 /* do not run, if no solution was found */
420 return SCIP_OKAY;
421
422 /* initialize the subproblem */
423 SCIP_CALL( SCIPcreate(&subscip) );
424
425 retcode = setupAndSolve(scip, subscip, heur, heurdata, result, nstallnodes, chgcoeffs);
426
427 SCIP_CALL( SCIPfree(&subscip) );
428
429 SCIP_CALL( retcode );
430
431 return SCIP_OKAY;
432}
433
434
435
436
437/*
438 * Callback methods of primal heuristic
439 */
440
441/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
442static
443SCIP_DECL_HEURCOPY(heurCopyOfins)
444{ /*lint --e{715}*/
445 assert(scip != NULL);
446 assert(heur != NULL);
447 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
448
449 /* call inclusion method of primal heuristic */
451
452 return SCIP_OKAY;
453}
454
455/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
456static
457SCIP_DECL_HEURFREE(heurFreeOfins)
458{ /*lint --e{715}*/
460
461 assert(heur != NULL);
462 assert(scip != NULL);
463
464 /* get heuristic data */
466 assert(heurdata != NULL);
467
468 /* free heuristic data */
470 SCIPheurSetData(heur, NULL);
471
472 return SCIP_OKAY;
473}
474
475/** execution method of primal heuristic */
476static
477SCIP_DECL_HEUREXEC(heurExecOfins)
478{/*lint --e{715}*/
480 SCIP_VAR** vars;
481 SCIP_Bool* chgcoeffs;
482 SCIP_Longint nstallnodes;
483 int nchgcoefs;
484 int nvars;
485 int v;
486
487 assert( heur != NULL );
488 assert( scip != NULL );
489 assert( result != NULL );
490
492
493 /* do not call heuristic of node was already detected to be infeasible */
494 if( nodeinfeasible )
495 return SCIP_OKAY;
496
497 /* get heuristic data */
499 assert( heurdata != NULL );
500
501 /* only call heuristic, if reoptimization is enabled */
503 return SCIP_OKAY;
504
505 /* only call the heuristic, if we are in run >= 2 */
506 if( SCIPgetNReoptRuns(scip) <= 1 )
507 return SCIP_OKAY;
508
510
511 if( SCIPisStopped(scip) )
512 return SCIP_OKAY;
513
514 /* calculate the maximal number of branching nodes until heuristic is aborted */
515 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
516
517 /* reward OFINS if it succeeded often */
518 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
519 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
520 nstallnodes += heurdata->nodesofs;
521
522 /* determine the node limit for the current process */
523 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
524
525 /* check whether we have enough nodes left to call subproblem solving */
526 if( nstallnodes < heurdata->minnodes )
527 {
528 SCIPdebugMsg(scip, "skipping OFINS: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
529 return SCIP_OKAY;
530 }
531
532 /* get variable data and check which coefficient has changed */
535 nchgcoefs = 0;
536
537 SCIP_CALL( SCIPallocBufferArray(scip, &chgcoeffs, nvars) );
538
539 for( v = 0; v < nvars; v++ )
540 {
541 SCIP_Real newcoef;
542 SCIP_Real oldcoef;
543 SCIP_Real newcoefabs;
544 SCIP_Real oldcoefabs;
545 SCIP_Real frac;
546
547 /* we only want to count variables that are unfixed after the presolving */
550
553 newcoefabs = REALABS(newcoef);
554 oldcoefabs = REALABS(oldcoef);
555
556 /* if both coefficients are zero nothing has changed */
557 if( SCIPisZero(scip, newcoef) && SCIPisZero(scip, oldcoef) )
558 {
559 frac = 0;
560 }
561 /* if exactly one coefficient is zero, the other need to be close to zero */
562 else if( SCIPisZero(scip, newcoef) || SCIPisZero(scip, oldcoef) )
563 {
564 assert(SCIPisZero(scip, newcoef) != SCIPisZero(scip, oldcoef));
565 if( !SCIPisZero(scip, newcoef) )
566 frac = MIN(1, newcoefabs);
567 else
568 frac = MIN(1, oldcoefabs);
569 }
570 /* if both coefficients have the same sign we calculate the quotient
571 * MIN(newcoefabs, oldcoefabs)/MAX(newcoefabs, oldcoefabs)
572 */
573 else if( SCIPisPositive(scip, newcoef) == SCIPisPositive(scip, oldcoef) )
574 {
575 frac = 1.0 - MIN(newcoefabs, oldcoefabs)/MAX(newcoefabs, oldcoefabs);
576 }
577 /* if both coefficients have a different sign, we set frac = 1 */
578 else
579 {
580 assert((SCIPisPositive(scip, newcoef) && SCIPisNegative(scip, oldcoef))
581 || (SCIPisNegative(scip, newcoef) && SCIPisPositive(scip, oldcoef)));
582
583 frac = 1;
584 }
585
586 if( frac > heurdata->maxchange )
587 {
588 chgcoeffs[v] = TRUE;
589 nchgcoefs++;
590 }
591 else
592 chgcoeffs[v] = FALSE;
593 }
594
595 SCIPdebugMsg(scip, "%d (rate %.4f) changed coefficients\n", nchgcoefs, nchgcoefs/((SCIP_Real)nvars));
596
597 /* we only want to run the heuristic, if there at least 3 changed coefficients.
598 * if the number of changed coefficients is 2 the trivialnegation heuristic will construct an
599 * optimal solution without solving a MIP.
600 */
601 if( nchgcoefs < 3 )
602 goto TERMINATE;
603
604 /* run the heuristic, if not too many coefficients have changed */
605 if( nchgcoefs/((SCIP_Real)nvars) > heurdata->maxchangerate )
606 goto TERMINATE;
607
608 SCIP_CALL( applyOfins(scip, heur, heurdata, result, nstallnodes, chgcoeffs) );
609
610 TERMINATE:
611 SCIPfreeBufferArray(scip, &chgcoeffs);
612
613 return SCIP_OKAY;
614}
615
616
617/*
618 * primal heuristic specific interface methods
619 */
620
621/** creates the ofins primal heuristic and includes it in SCIP */
623 SCIP* scip /**< SCIP data structure */
624 )
625{
627 SCIP_HEUR* heur;
628
629 /* create ofins primal heuristic data */
631 assert(heurdata != NULL);
632
633 /* include primal heuristic */
637
638 assert(heur != NULL);
639
640 /* set non fundamental callbacks via setter functions */
641 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyOfins) );
642 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeOfins) );
643
644 /* add ofins primal heuristic parameters */
645
646 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
647 "maximum number of nodes to regard in the subproblem",
648 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
649
650 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
651 "minimum number of nodes required to start the subproblem",
652 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
653
654 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxchangerate",
655 "maximal rate of changed coefficients",
656 &heurdata->maxchangerate, FALSE, DEFAULT_MAXCHGRATE, 0.0, 1.0, NULL, NULL) );
657
658 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxchange",
659 "maximal rate of change per coefficient to get fixed",
660 &heurdata->maxchange, FALSE, DEFAULT_MAXCHANGE, 0.0, 1.0, NULL, NULL) );
661
662 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
663 "should all active cuts from cutpool be copied to constraints in subproblem?",
664 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
665
666 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
667 "should all subproblem solutions be added to the original SCIP?",
668 &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
669
670 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
671 "number of nodes added to the contingent of the total nodes",
673
674 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
675 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
676 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
677
678 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
679 "factor by which RENS should at least improve the incumbent",
680 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
681
682 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
683 "factor by which the limit on the number of LP depends on the node limit",
684 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
685
686 return SCIP_OKAY;
687}
#define NULL
Definition def.h:266
#define SCIP_Longint
Definition def.h:157
#define SCIP_REAL_MAX
Definition def.h:173
#define MIN(x, y)
Definition def.h:242
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:238
#define SCIP_CALL_ABORT(x)
Definition def.h:352
#define SCIP_LONGINT_FORMAT
Definition def.h:164
#define SCIPABORT()
Definition def.h:345
#define REALABS(x)
Definition def.h:196
#define SCIP_LONGINT_MAX
Definition def.h:158
#define SCIP_CALL(x)
Definition def.h:373
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition scip_copy.c:3253
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition scip_copy.c:1408
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition scip_copy.c:3296
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition scip_prob.c:2127
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition scip_prob.c:1422
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3043
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3111
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3264
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3077
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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 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 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
SCIP_RETCODE SCIPincludeHeurOfins(SCIP *scip)
Definition heur_ofins.c:622
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
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: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_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1599
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1579
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 SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_SOL * SCIPgetReoptLastOptSol(SCIP *scip)
SCIP_RETCODE SCIPgetReoptOldObjCoef(SCIP *scip, SCIP_VAR *var, int run, SCIP_Real *objcoef)
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2165
SCIP_RETCODE SCIPprintRay(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:2030
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition sol.c:2784
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2066
SCIP_Real SCIPgetPrimalRayVal(SCIP *scip, SCIP_VAR *var)
Definition scip_sol.c:3362
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2115
SCIP_Bool SCIPhasPrimalRay(SCIP *scip)
Definition scip_sol.c:3344
SCIP_RETCODE SCIPtrySolFree(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:3046
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1073
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1213
SCIP_RETCODE SCIPupdatePrimalRay(SCIP *scip, SCIP_SOL *primalray)
Definition scip_sol.c:3389
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:223
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPgetNReoptRuns(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_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17747
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17537
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_Real frac
#define DEFAULT_MAXCHGRATE
Definition heur_ofins.c:71
#define DEFAULT_MAXCHANGE
Definition heur_ofins.c:74
#define DEFAULT_NODESQUOT
Definition heur_ofins.c:79
#define DEFAULT_NODESOFS
Definition heur_ofins.c:78
#define DEFAULT_COPYCUTS
Definition heur_ofins.c:72
#define DEFAULT_MAXNODES
Definition heur_ofins.c:70
#define HEUR_TIMING
Definition heur_ofins.c:66
#define DEFAULT_MINNODES
Definition heur_ofins.c:77
#define HEUR_FREQOFS
Definition heur_ofins.c:64
#define HEUR_DESC
Definition heur_ofins.c:60
#define DEFAULT_LPLIMFAC
Definition heur_ofins.c:80
static SCIP_RETCODE setupAndSolve(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_Bool *chgcoeffs)
Definition heur_ofins.c:135
#define DEFAULT_ADDALLSOLS
Definition heur_ofins.c:76
#define HEUR_DISPCHAR
Definition heur_ofins.c:61
#define HEUR_MAXDEPTH
Definition heur_ofins.c:65
#define HEUR_PRIORITY
Definition heur_ofins.c:62
#define DEFAULT_MINIMPROVE
Definition heur_ofins.c:75
#define HEUR_NAME
Definition heur_ofins.c:59
static SCIP_RETCODE applyOfins(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_Bool *chgcoeffs)
Definition heur_ofins.c:389
#define EVENTHDLR_DESC
Definition heur_ofins.c:84
#define HEUR_FREQ
Definition heur_ofins.c:63
#define HEUR_USESSUBSCIP
Definition heur_ofins.c:67
#define EVENTHDLR_NAME
Definition heur_ofins.c:83
OFINS - Objective Function Induced Neighborhood Search - a primal heuristic for reoptimization.
static SCIP_VAR ** vars
int nintvars
methods commonly used by primal heuristics
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
#define SCIPstatisticPrintf
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 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 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 timing
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_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ 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_UNBOUNDED
Definition type_result.h:47
@ 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_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_INFORUNBD
Definition type_stat.h:64
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
enum SCIP_Status SCIP_STATUS
Definition type_stat.h:67
@ SCIP_VARSTATUS_ORIGINAL
Definition type_var.h:49