SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_zeroobj.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file heur_zeroobj.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "Hail Mary"
28 * @author Timo Berthold
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/cons_linear.h"
35#include "scip/heur_zeroobj.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_var.h"
41#include "scip/scip_branch.h"
42#include "scip/scip_cons.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_lp.h"
48#include "scip/scip_mem.h"
49#include "scip/scip_message.h"
50#include "scip/scip_nodesel.h"
51#include "scip/scip_numerics.h"
52#include "scip/scip_param.h"
53#include "scip/scip_prob.h"
54#include "scip/scip_sol.h"
55#include "scip/scip_solve.h"
57#include "scip/scip_tree.h"
58#include "scip/scip_var.h"
59#include <string.h>
60
61#define HEUR_NAME "zeroobj"
62#define HEUR_DESC "heuristic trying to solve the problem without objective"
63#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
64#define HEUR_PRIORITY 100
65#define HEUR_FREQ -1
66#define HEUR_FREQOFS 0
67#define HEUR_MAXDEPTH 0
68#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_BEFOREPRESOL
69#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
70
71/* event handler properties */
72#define EVENTHDLR_NAME "Zeroobj"
73#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
74
75/* default values for zeroobj-specific plugins */
76#define DEFAULT_MAXNODES 1000LL /* maximum number of nodes to regard in the subproblem */
77#define DEFAULT_MINIMPROVE 0.01 /* factor by which zeroobj should at least improve the incumbent */
78#define DEFAULT_MINNODES 100LL /* minimum number of nodes to regard in the subproblem */
79#define DEFAULT_MAXLPITERS 5000LL /* maximum number of LP iterations to be performed in the subproblem */
80#define DEFAULT_NODESOFS 100LL /* number of nodes added to the contingent of the total nodes */
81#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
82#define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */
83#define DEFAULT_ONLYWITHOUTSOL TRUE /**< should heuristic only be executed if no primal solution was found, yet? */
84#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
85
86/*
87 * Data structures
88 */
89
90/** primal heuristic data */
91struct SCIP_HeurData
92{
93 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
94 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
95 SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */
96 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
97 SCIP_Longint usednodes; /**< nodes already used by zeroobj in earlier calls */
98 SCIP_Real minimprove; /**< factor by which zeroobj should at least improve the incumbent */
99 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
100 SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
101 SCIP_Bool onlywithoutsol; /**< should heuristic only be executed if no primal solution was found, yet? */
102 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
103};
104
105
106/*
107 * Local methods
108 */
109
110/* ---------------- Callback methods of event handler ---------------- */
111
112/* exec the event handler
113 *
114 * we interrupt the solution process
115 */
116static
117SCIP_DECL_EVENTEXEC(eventExecZeroobj)
118{
120
121 assert(eventhdlr != NULL);
122 assert(eventdata != NULL);
123 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
124 assert(event != NULL);
126
127 heurdata = (SCIP_HEURDATA*)eventdata;
128 assert(heurdata != NULL);
129
130 /* interrupt solution process of sub-SCIP */
132 {
134 }
135
136 return SCIP_OKAY;
137}
138/* ---------------- Callback methods of primal heuristic ---------------- */
139
140/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
141static
142SCIP_DECL_HEURCOPY(heurCopyZeroobj)
143{ /*lint --e{715}*/
144 assert(scip != NULL);
145 assert(heur != NULL);
146 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
147
148 /* call inclusion method of primal heuristic */
150
151 return SCIP_OKAY;
152}
153
154/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
155static
156SCIP_DECL_HEURFREE(heurFreeZeroobj)
157{ /*lint --e{715}*/
159
160 assert( heur != NULL );
161 assert( scip != NULL );
162
163 /* get heuristic data */
165 assert( heurdata != NULL );
166
167 /* free heuristic data */
169 SCIPheurSetData(heur, NULL);
170
171 return SCIP_OKAY;
172}
173
174
175/** initialization method of primal heuristic (called after problem was transformed) */
176static
177SCIP_DECL_HEURINIT(heurInitZeroobj)
178{ /*lint --e{715}*/
180
181 assert( heur != NULL );
182 assert( scip != NULL );
183
184 /* get heuristic data */
186 assert( heurdata != NULL );
187
188 /* initialize data */
189 heurdata->usednodes = 0;
190
191 return SCIP_OKAY;
192}
193
194
195/** execution method of primal heuristic */
196static
197SCIP_DECL_HEUREXEC(heurExecZeroobj)
198{ /*lint --e{715}*/
199 SCIP_HEURDATA* heurdata; /* heuristic's data */
200 SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */
201
202 assert( heur != NULL );
203 assert( scip != NULL );
204 assert( result != NULL );
205
206 /* get heuristic data */
208 assert( heurdata != NULL );
209
210 /* calculate the maximal number of branching nodes until heuristic is aborted */
211 nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
212
213 /* reward zeroobj if it succeeded often */
214 nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
215 nnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
216 nnodes += heurdata->nodesofs;
217
218 /* determine the node limit for the current process */
219 nnodes -= heurdata->usednodes;
220 nnodes = MIN(nnodes, heurdata->maxnodes);
221
222 /* check whether we have enough nodes left to call subproblem solving */
223 if( nnodes < heurdata->minnodes )
224 {
225 SCIPdebugMsg(scip, "skipping zeroobj: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
226 return SCIP_OKAY;
227 }
228
229 /* do not run zeroobj, if the problem does not have an objective function anyway */
230 if( SCIPgetNObjVars(scip) == 0 )
231 {
232 SCIPdebugMsg(scip, "skipping zeroobj: pure feasibility problem anyway\n");
233 return SCIP_OKAY;
234 }
235
236 if( SCIPisStopped(scip) )
237 return SCIP_OKAY;
238
239 SCIP_CALL( SCIPapplyZeroobj(scip, heur, result, heurdata->minimprove, nnodes) );
240
241 return SCIP_OKAY;
242}
243
244/** setup and solve subscip */
245static
247 SCIP* scip, /**< SCIP data structure */
248 SCIP* subscip, /**< SCIP data structure */
249 SCIP_HEUR* heur, /**< heuristic data structure */
250 SCIP_RESULT* result, /**< result data structure */
251 SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
252 SCIP_Longint nnodes /**< node limit for the subproblem */
253 )
254{
255 SCIP_Real cutoff; /* objective cutoff for the subproblem */
256 SCIP_Real large;
257 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
258 SCIP_VAR** vars; /* original problem's variables */
259 SCIP_VAR** subvars; /* subproblem's variables */
260 SCIP_SOL** subsols;
261 SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
262 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
263
264 int nsubsols;
265 int nvars; /* number of original problem's variables */
266 int i;
267 SCIP_Bool success;
269
270 assert(scip != NULL);
271 assert(subscip != NULL);
272 assert(heur != NULL);
273 assert(result != NULL);
274
276 assert(heurdata != NULL);
277
278 /* get variable data */
280
281 /* create the variable mapping hash map */
282 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
284
285 /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
286 valid = FALSE;
287
288 /* copy complete SCIP instance */
289 SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj", TRUE, FALSE, FALSE, TRUE, &valid) );
290 SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
291
292 /* create event handler for LP events */
293 eventhdlr = NULL;
294 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) );
295 if( eventhdlr == NULL )
296 {
297 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
298 return SCIP_PLUGINNOTFOUND;
299 }
300
301 /* determine large value to set variables to */
302 large = SCIPinfinity(scip);
303 if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
304 large = 0.1 / SCIPfeastol(scip);
305
306 /* get variable image and change to 0.0 in sub-SCIP */
307 for( i = 0; i < nvars; i++ )
308 {
309 SCIP_Real adjustedbound;
310 SCIP_Real lb;
311 SCIP_Real ub;
312 SCIP_Real inf;
313
314 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
315 if( subvars[i] == NULL )
316 continue;
317
318 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
319
320 lb = SCIPvarGetLbGlobal(subvars[i]);
321 ub = SCIPvarGetUbGlobal(subvars[i]);
322 inf = SCIPinfinity(subscip);
323
324 /* adjust infinite bounds in order to avoid that variables with non-zero objective
325 * get fixed to infinite value in zeroobj subproblem
326 */
327 if( SCIPisInfinity(subscip, ub ) )
328 {
329 adjustedbound = MAX(large, lb+large);
330 adjustedbound = MIN(adjustedbound, inf);
331 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
332 }
333 if( SCIPisInfinity(subscip, -lb ) )
334 {
335 adjustedbound = MIN(-large, ub-large);
336 adjustedbound = MAX(adjustedbound, -inf);
337 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
338 }
339 }
340
341 /* free hash map */
342 SCIPhashmapFree(&varmapfw);
343
344 /* do not abort subproblem on CTRL-C */
345 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
346
347#ifdef SCIP_DEBUG
348 /* for debugging, enable full output */
349 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
350 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
351#else
352 /* disable statistic timing inside sub SCIP and output to console */
353 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
354 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
355#endif
356
357 /* set limits for the subproblem */
358 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
359 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
360 SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
361
362 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
363 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
364
365 /* disable expensive techniques that merely work on the dual bound */
366
367 /* disable cutting plane separation */
369
370 /* disable expensive presolving */
372 if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
373 {
374 SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
375 }
376
377 /* use restart dfs node selection */
378 if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
379 {
380 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
381 }
382
383 /* activate uct node selection at the top of the tree */
384 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
385 {
386 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
387 }
388 /* use least infeasible branching */
389 if( SCIPfindBranchrule(subscip, "leastinf") != NULL && !SCIPisParamFixed(subscip, "branching/leastinf/priority") )
390 {
391 SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) );
392 }
393
394 /* disable feaspump and fracdiving */
395 if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
396 {
397 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
398 }
399 if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
400 {
401 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
402 }
403
404 /* speed up sub-SCIP by not checking dual LP feasibility */
405 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
406
407 /* restrict LP iterations */
408 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) );
409 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) );
410
411 /* if there is already a solution, add an objective cutoff */
412 if( SCIPgetNSols(scip) > 0 )
413 {
414 SCIP_Real upperbound;
415 SCIP_CONS* origobjcons;
416#ifndef NDEBUG
417 int nobjvars;
418 nobjvars = 0;
419#endif
420
422
423 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
424
426 {
427 cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
428 }
429 else
430 {
431 if( SCIPgetUpperbound(scip) >= 0 )
432 cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
433 else
434 cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
435 }
436 cutoff = MIN(upperbound, cutoff);
437
438 SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
440 for( i = 0; i < nvars; ++i)
441 {
442 if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
443 {
444 assert(subvars[i] != NULL); /* subvars[i] can be NULL for relax-only vars, but they cannot appear in the objective */
445 SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
446#ifndef NDEBUG
447 nobjvars++;
448#endif
449 }
450 }
451 SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
452 SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
453 assert(nobjvars == SCIPgetNObjVars(scip));
454 }
455
456 /* catch LP events of sub-SCIP */
457 SCIP_CALL( SCIPtransformProb(subscip) );
459
460 SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes);
461
462 /* errors in solving the subproblem should not kill the overall solving process;
463 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
464 */
465 SCIP_CALL_ABORT( SCIPsolve(subscip) );
466
467 /* drop LP events of sub-SCIP */
469
470 /* check, whether a solution was found;
471 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
472 */
473 nsubsols = SCIPgetNSols(subscip);
474 subsols = SCIPgetSols(subscip);
475 success = FALSE;
476 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
477 {
478 SCIP_SOL* newsol;
479
480 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) );
481
482 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
483 if( success )
485 }
486
487#ifdef SCIP_DEBUG
489#endif
490
491 /* free subproblem */
492 SCIPfreeBufferArray(scip, &subvars);
493
494 return SCIP_OKAY;
495}
496
497
498/*
499 * primal heuristic specific interface methods
500 */
501
502
503/** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
505 SCIP* scip, /**< original SCIP data structure */
506 SCIP_HEUR* heur, /**< heuristic data structure */
507 SCIP_RESULT* result, /**< result data structure */
508 SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
509 SCIP_Longint nnodes /**< node limit for the subproblem */
510 )
511{
512 SCIP* subscip; /* the subproblem created by zeroobj */
513 SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
514 SCIP_Bool success;
515 SCIP_RETCODE retcode;
516
517 assert(scip != NULL);
518 assert(heur != NULL);
519 assert(result != NULL);
520
521 assert(nnodes >= 0);
522 assert(0.0 <= minimprove && minimprove <= 1.0);
523
525
526 /* only call heuristic once at the root */
527 if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
528 return SCIP_OKAY;
529
530 /* get heuristic data */
532 assert(heurdata != NULL);
533
534 /* only call the heuristic if we do not have an incumbent */
535 if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
536 return SCIP_OKAY;
537
538 /* check whether there is enough time and memory left */
539 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
540
541 if( !success )
542 return SCIP_OKAY;
543
545
546 /* initialize the subproblem */
547 SCIP_CALL( SCIPcreate(&subscip) );
548
549 retcode = setupAndSolveSubscip(scip, subscip, heur, result, minimprove, nnodes);
550
551 SCIP_CALL( SCIPfree(&subscip) );
552
553 return retcode;
554}
555
556
557/** creates the zeroobj primal heuristic and includes it in SCIP */
559 SCIP* scip /**< SCIP data structure */
560 )
561{
563 SCIP_HEUR* heur;
564
565 /* create heuristic data */
567
568 /* include primal heuristic */
569 heur = NULL;
572 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) );
573 assert(heur != NULL);
574
575 /* set non-NULL pointers to callback methods */
576 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) );
577 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) );
578 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) );
579
580 /* add zeroobj primal heuristic parameters */
581 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
582 "maximum number of nodes to regard in the subproblem",
584
585 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
586 "number of nodes added to the contingent of the total nodes",
588
589 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
590 "minimum number of nodes required to start the subproblem",
591 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
592
593 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
594 "maximum number of LP iterations to be performed in the subproblem",
595 &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
596
597 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
598 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
599 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
600
601 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
602 "factor by which zeroobj should at least improve the incumbent",
603 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
604
605 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
606 "should all subproblem solutions be added to the original SCIP?",
607 &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
608
609 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
610 "should heuristic only be executed if no primal solution was found, yet?",
611 &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
612 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
613 "should uct node selection be used at the beginning of the search?",
614 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
615
616 return SCIP_OKAY;
617}
#define EVENTHDLR_NAME
#define EVENTHDLR_DESC
#define DEFAULT_MAXNODES
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:266
#define SCIP_Longint
Definition def.h:157
#define SCIP_Bool
Definition def.h:91
#define MIN(x, y)
Definition def.h:242
#define SCIP_Real
Definition def.h:172
#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 SCIP_LONGINT_MAX
Definition def.h:158
#define SCIP_CALL(x)
Definition def.h:373
#define DEFAULT_MINNODES
#define nnodes
Definition gastrans.c:74
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
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 SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition scip_copy.c:2875
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)
int SCIPgetNObjVars(SCIP *scip)
Definition scip_prob.c:2220
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
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
SCIP_RETCODE SCIPapplyZeroobj(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
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 SCIPincludeHeurZeroobj(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
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:111
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:293
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition scip_event.c:327
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:183
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1364
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition scip_heur.c:122
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1599
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:167
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1579
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:199
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition heur.c:1374
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
#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)
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2066
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2115
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 SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:223
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 SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:672
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17953
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18115
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:5066
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:5155
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18105
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_var.c:4636
#define HEUR_TIMING
return SCIP_OKAY
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define HEUR_NAME
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
#define DEFAULT_NODESQUOT
Definition heur_alns.c:91
#define DEFAULT_ONLYWITHOUTSOL
Definition heur_bound.c:69
#define DEFAULT_NODESOFS
Definition heur_clique.c:93
#define DEFAULT_MINIMPROVE
Definition heur_clique.c:90
#define DEFAULT_ADDALLSOLS
#define DEFAULT_USEUCT
SCIP_Bool cutoff
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
heurdata usednodes
Definition heur_locks.c:158
#define DEFAULT_MAXLPITERS
static SCIP_VAR ** vars
static SCIP_RETCODE setupAndSolveSubscip(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "H...
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
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 the branch-and-bound tree
public methods for SCIP variables
struct SCIP_Cons SCIP_CONS
Definition type_cons.h:63
struct SCIP_Eventhdlr SCIP_EVENTHDLR
Definition type_event.h:154
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_NODESOLVED
Definition type_event.h:136
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
struct SCIP_Heur SCIP_HEUR
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ SCIP_LPSOLSTAT_ITERLIMIT
Definition type_lp.h:47
struct SCIP_HashMap SCIP_HASHMAP
Definition type_misc.h:105
@ SCIP_PARAMSETTING_OFF
@ SCIP_PARAMSETTING_FAST
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_PLUGINNOTFOUND
enum SCIP_Retcode SCIP_RETCODE
struct Scip SCIP
Definition type_scip.h:39
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
struct SCIP_Var SCIP_VAR
Definition type_var.h:119