heur_slackprune.c
Go to the documentation of this file.
20 * This file implements a dual-ascent and reduction based heuristic for Steiner problems. It is based on an approach
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
55 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
58 #define DEFAULT_SLACKPRUNE_MAXFREQ FALSE /**< executions of the heuristic at maximum frequency? */
59 #define SLACKPRUNE_MINREDELIMS 2 /**< minimum number of eliminations for reduction package when called by slack-and-prune heuristic */
60 #define SLACKPRUNE_MAXREDROUNDS 10 /**< maximum number of reduction rounds in slack-prune heuristic */
61 #define SLACKPRUNE_MINSTALLPROPORTION 0.2 /**< minimum proportion of arcs to be fixed before restarting slack-prune heuristic */
62 #define SLACKPRUNE_MAXSTALLPROPORTION 0.5 /**< maximum proportion of arcs to be fixed before restarting slack-prune heuristic */
275 RPARAMS parameters = { .dualascent = FALSE, .boundreduce = FALSE, .nodereplacing = TRUE, .reductbound_min = SLACKPRUNE_MINREDELIMS,
357 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
383 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
482 SCIPdebugMessage("SP final solution: best: old %f, new %f \n", SCIPgetSolOrigObj(scip, bestsol), pobj + SCIPprobdataGetOffset(scip));
490 SCIPdebugMessage("better solution added by SLACKPRUNE %f \n", pobj + SCIPprobdataGetOffset(scip));
633 SCIP_CALL( reduceExact(scip, prunegraph, reductbound, fullreduce, soledge, solnode, &offsetnew) );
650 setMinMaxElims(scip, &minnelims, &lminnelims, annodes, anedges, anterms, i + 1, SLACKPRUNE_MAXREDROUNDS);
655 SCIP_CALL( reduce_daSlackPrune(scip, prunegraph, minnelims, solgiven, soledge, solnode, &danelims, &ubnew, &solIsImproved, &solIsRebuilt) );
695 SCIPdebugMessage("old solution: %f new solution %f \n\n", ubbest + SCIPprobdataGetOffset(scip), obj + SCIPprobdataGetOffset(scip));
703 SCIP_CALL( reduceExact(scip, prunegraph, reductbound, fullreduce, soledge, solnode, &offsetnew) );
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
Definition: type_result.h:33
Definition: type_result.h:47
Definition: graphdefs.h:184
Definition: struct_scip.h:59
SCIP_RETCODE SCIPStpHeurPruneUpdateSols(SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success)
Definition: heur_prune.c:489
Constraint handler for Steiner problems.
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
SCIP_RETCODE reduce_redLoopPc(SCIP *, REDSOL *, GRAPH *, PATH *, PATH *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, SCIP_Bool, SCIP_Bool, SCIP_Bool, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1896
static void setMinMaxElims(SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxnrounds)
Definition: heur_slackprune.c:105
Definition: struct_var.h:198
includes methods for Steiner tree problem solutions
dual-ascent and reduction based primal heuristic for Steiner problems
reduction and dual-cost based primal heuristic for Steiner problems
Problem data for stp problem.
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE reduce_redLoopMw(SCIP *, REDSOL *, GRAPH *, PATH *, SCIP_Real *, int *, int *, int *, STP_Bool *, STP_Bool, STP_Bool, STP_Bool, int, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1771
void reduce_solGetNodesol(const GRAPH *, REDSOL *, int *)
Definition: reduce_sol.c:1176
Definition: graphdefs.h:284
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:108
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
Definition: reducedefs.h:100
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2948
Definition: struct_sol.h:64
SCIP_Bool graph_pc_edgeIsExtended(const GRAPH *, int)
Definition: graph_pcbase.c:1232
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
static SCIP_RETCODE reduceExact(SCIP *scip, GRAPH *prunegraph, int reductbound, SCIP_Bool fullreduce, int *soledge, int *solnode, SCIP_Real *offset)
Definition: heur_slackprune.c:223
Definition: type_result.h:35
static SCIP_Bool probtypeIsValidForSlackPrune(const GRAPH *graph)
Definition: heur_slackprune.c:159
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
Definition: reduce_sol.c:70
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: probdata_stp.c:3693
static SCIP_DECL_HEURINITSOL(heurInitsolSlackPrune)
Definition: heur_slackprune.c:359
static SCIP_DECL_HEUREXITSOL(heurExitsolSlackPrune)
Definition: heur_slackprune.c:385
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
Definition: type_retcode.h:33
Definition: reducedefs.h:75
Definition: struct_heur.h:88
Improvement heuristic for Steiner problems.
reduction-based primal heuristic for Steiner problems
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
propagator for Steiner tree problems, using the LP reduced costs
public data structures and miscellaneous methods
SCIP_RETCODE SCIPStpHeurSlackPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool initialreduce, SCIP_Bool fullreduce)
Definition: heur_slackprune.c:532
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
static SCIP_Bool abortSlackPruneEarly(SCIP *scip, const GRAPH *graph, SCIP_HEURDATA *heurdata)
Definition: heur_slackprune.c:170
SCIP_RETCODE reduce_solAddNodesol(const GRAPH *, const int *, REDSOL *)
Definition: reduce_sol.c:1150
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
Definition: probdata_stp.c:3190
shortest paths based primal heuristics for Steiner problems
SCIP_RETCODE SCIPStpIncludeHeurSlackPrune(SCIP *scip)
Definition: heur_slackprune.c:730
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_RETCODE reduce_redLoopStp(SCIP *, GRAPH *, REDBASE *)
Definition: reduce_base.c:2074
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
Definition: objbenders.h:33
includes various reduction methods for Steiner tree problems
default SCIP plugins
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
SCIP callable library.
SCIP_RETCODE reduce_daSlackPrune(SCIP *, GRAPH *, int, SCIP_Bool, int *, int *, int *, SCIP_Real *, SCIP_Bool *, SCIP_Bool *)
Definition: reduce_da.c:2741
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:48