COMPLETESOL - primal heuristic trying to complete given partial solutions.
Definition in file heur_completesol.c.
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "scip/heur_completesol.h"
#include "scip/scipdefplugins.h"
#include "scip/pub_misc.h"
#include "scip/def.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "completesol" |
#define | HEUR_DESC "primal heuristic trying to complete given partial solutions" |
#define | HEUR_DISPCHAR 'h' |
#define | HEUR_PRIORITY 0 |
#define | HEUR_FREQ 1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH 0 |
#define | HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_MAXNODES 5000LL |
#define | DEFAULT_MAXUNKRATE 0.85 |
#define | DEFAULT_ADDALLSOLS FALSE |
#define | DEFAULT_MINNODES 50LL |
#define | DEFAULT_NODESOFS 500LL |
#define | DEFAULT_NODESQUOT 0.1 |
#define | DEFAULT_LPLIMFAC 2.0 |
#define | DEFAULT_OBJWEIGHT 1.0 |
#define | DEFAULT_BOUNDWIDENING 0.1 |
#define | DEFAULT_MINIMPROVE 0.01 |
#define | DEFAULT_MINOBJWEIGHT 1e-3 |
#define | DEFAULT_IGNORECONT FALSE |
#define | DEFAULT_BESTSOLS 5 |
#define | DEFAULT_MAXPROPROUNDS 10 |
#define | DEFAULT_MAXLPITER -1LL |
#define | DEFAULT_MAXCONTVARS -1 |
#define | DEFAULT_BEFOREPRESOL TRUE |
#define | EVENTHDLR_NAME "Completesol" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Functions | |
static | SCIP_DECL_EVENTEXEC (eventExecCompletesol) |
static SCIP_RETCODE | createSubproblem (SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_SOL *partialsol, SCIP_Bool *tightened, SCIP_Bool *success) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success) |
static SCIP_RETCODE | chgProbingBound (SCIP *scip, SCIP_VAR *var, SCIP_Real newval, SCIP_BRANCHDIR branchdir, SCIP_Bool *success) |
static SCIP_RETCODE | tightenVariables (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Bool *tightened, SCIP_Bool *success) |
static SCIP_RETCODE | setupAndSolve (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_SOL *partialsol, SCIP_Bool *tightened) |
static SCIP_RETCODE | applyCompletesol (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_SOL *partialsol) |
static | SCIP_DECL_HEURCOPY (heurCopyCompletesol) |
static | SCIP_DECL_HEURFREE (heurFreeCompletesol) |
static | SCIP_DECL_HEUREXEC (heurExecCompletesol) |
SCIP_RETCODE | SCIPincludeHeurCompletesol (SCIP *scip) |
#define HEUR_NAME "completesol" |
Definition at line 32 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol(), and setupAndSolve().
#define HEUR_DESC "primal heuristic trying to complete given partial solutions" |
Definition at line 33 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define HEUR_DISPCHAR 'h' |
Definition at line 34 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define HEUR_PRIORITY 0 |
Definition at line 35 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define HEUR_FREQ 1 |
Definition at line 36 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define HEUR_FREQOFS 0 |
Definition at line 37 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define HEUR_MAXDEPTH 0 |
Definition at line 38 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE |
Definition at line 39 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 40 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MAXNODES 5000LL |
maximum number of nodes to regard in the subproblem
Definition at line 43 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MAXUNKRATE 0.85 |
maximum percentage of unknown solution values
Definition at line 44 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_ADDALLSOLS FALSE |
should all subproblem solutions be added to the original SCIP?
Definition at line 45 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MINNODES 50LL |
minimum number of nodes to regard in the subproblem
Definition at line 46 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_NODESOFS 500LL |
number of nodes added to the contingent of the total nodes
Definition at line 47 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 48 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_LPLIMFAC 2.0 |
factor by which the limit on the number of LP depends on the node limit
Definition at line 49 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_OBJWEIGHT 1.0 |
weight of the original objective function (1: only original objective)
Definition at line 50 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_BOUNDWIDENING 0.1 |
bound widening factor applied to continuous variables (0: round bounds to next integer, 1: relax to global bounds)
Definition at line 51 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MINIMPROVE 0.01 |
factor by which the incumbent should be improved at least
Definition at line 56 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MINOBJWEIGHT 1e-3 |
minimal weight for original objective function (zero could lead to infinite solutions)
Definition at line 57 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_IGNORECONT FALSE |
should solution values for continuous variables be ignored?
Definition at line 58 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_BESTSOLS 5 |
heuristic stops, if the given number of improving solutions were found (-1: no limit)
Definition at line 59 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MAXPROPROUNDS 10 |
maximal number of iterations in propagation (-1: no limit)
Definition at line 60 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MAXLPITER -1LL |
maximal number of LP iterations (-1: no limit)
Definition at line 61 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_MAXCONTVARS -1 |
maximal number of continuous variables after presolving (-1: no limit)
Definition at line 62 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define DEFAULT_BEFOREPRESOL TRUE |
should the heuristic run before presolving?
Definition at line 63 of file heur_completesol.c.
Referenced by SCIPincludeHeurCompletesol().
#define EVENTHDLR_NAME "Completesol" |
Definition at line 66 of file heur_completesol.c.
Referenced by setupAndSolve().
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 67 of file heur_completesol.c.
Referenced by setupAndSolve().
|
static |
Definition at line 101 of file heur_completesol.c.
|
static |
creates a subproblem by fixing a number of variables
scip | original SCIP data structure |
subscip | SCIP data structure for the subproblem |
heurdata | heuristic's private data structure |
subvars | the variables of the subproblem |
partialsol | partial solution |
tightened | array to store for which variables we have found bound tightenings |
success | pointer to store whether the creation was successful |
Definition at line 126 of file heur_completesol.c.
References createNewSol(), eps, FALSE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPchgVarObj(), SCIPcreateConsBasicLinear(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPfeasFrac(), SCIPgetLowerbound(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetObjsense(), SCIPgetSolVal(), SCIPgetUpperbound(), SCIPgetVars(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPsumepsilon(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.
Referenced by setupAndSolve().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
subvars | the variables of the subproblem |
heur | Completesol heuristic structure |
subsol | solution of the subproblem or the partial |
success | used to store whether new solution was found or not |
Definition at line 319 of file heur_completesol.c.
References chgProbingBound(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPcreateSol(), SCIPgetNOrigVars(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisInfinity(), SCIPsetSolVal(), SCIPtrySolFree(), and TRUE.
Referenced by createSubproblem(), and setupAndSolve().
|
static |
perform a probing bound change or fixes the variable
scip | original SCIP data structure |
var | problem variable |
newval | new bound |
branchdir | bound change direction |
success | pointer to store whether the bound could be tightened |
Definition at line 367 of file heur_completesol.c.
References FALSE, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_FIXED, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPfixVarProbing(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), tightenVariables(), and TRUE.
Referenced by createNewSol(), and tightenVariables().
|
static |
tries variables bound changes guided by the given solution
scip | original SCIP data structure |
heurdata | heuristic's private data structure |
vars | problem variables |
nvars | number of problem variables |
sol | solution to guide the bound changes |
tightened | array to store if variable bound could be tightened |
success | pointer to store the success |
Definition at line 417 of file heur_completesol.c.
References chgProbingBound(), FALSE, REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_FIXED, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_Longint, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_SOLORIGIN_PARTIAL, SCIP_UNKNOWN, SCIPbacktrackProbing(), SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPgetNContVars(), SCIPgetProbingDepth(), SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisIntegral(), SCIPisLT(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPsolGetOrigin(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsIntegral(), setupAndSolve(), and TRUE.
Referenced by applyCompletesol(), and chgProbingBound().
|
static |
scip | original SCIP data structure |
subscip | sub-SCIP data structure |
heur | heuristic data structure |
heurdata | heuristic's private data structure |
result | result data structure |
nstallnodes | number of stalling nodes for the subproblem |
partialsol | partial solution |
tightened | array to store whether a variable was already tightened |
Definition at line 730 of file heur_completesol.c.
References applyCompletesol(), createNewSol(), createSubproblem(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_PLUGINNOTFOUND, SCIP_STAGE_PRESOLVED, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_NONE, SCIPABORT, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyConsCompression(), SCIPcopyLimits(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfindBranchrule(), SCIPfindNodesel(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetPrimalbound(), SCIPgetSols(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPincludeEventhdlrBasic(), SCIPinfinity(), SCIPisNLPEnabled(), SCIPisParamFixed(), SCIPpresolve(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolGetNodenum(), SCIPsolve(), SCIPstatisticPrintf, SCIPtransformProb(), SCIPwarningMessage(), and TRUE.
Referenced by applyCompletesol(), and tightenVariables().
|
static |
main procedure of the completesol heuristic, creates and solves a sub-SCIP
scip | original SCIP data structure |
heur | heuristic data structure |
heurdata | heuristic's private data structure |
result | result data structure |
nstallnodes | number of stalling nodes for the subproblem |
partialsol | partial solution |
Definition at line 948 of file heur_completesol.c.
References SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURCOPY(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPallocClearBufferArray, SCIPcheckCopyLimits(), SCIPcreate(), SCIPdebugMsg, SCIPendProbing(), SCIPfree(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPstartProbing(), setupAndSolve(), and tightenVariables().
Referenced by setupAndSolve().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 1022 of file heur_completesol.c.
Referenced by applyCompletesol().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1036 of file heur_completesol.c.
|
static |
execution method of primal heuristic
Definition at line 1056 of file heur_completesol.c.