repair primal heuristic
Definition in file heur_repair.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/cons_varbound.h"
#include "scip/heur_repair.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/scipdefplugins.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "repair" |
#define | HEUR_DESC "tries to repair a primal infeasible solution" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -20 |
#define | HEUR_FREQ -1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
#define | DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ |
#define | DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ |
#define | DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
#define | DEFAULT_FILENAME "-" |
#define | DEFAULT_ROUNDIT TRUE |
#define | DEFAULT_USEOBJFACTOR FALSE |
#define | DEFAULT_USEVARFIX TRUE |
#define | DEFAULT_USESLACKVARS FALSE |
#define | DEFAULT_ALPHA 2.0 |
Functions | |
static SCIP_RETCODE | getObjectiveFactor (SCIP *scip, SCIP *subscip, SCIP_Real *factor, SCIP_Bool *success) |
static SCIP_Real | getPotentialContributed (SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real coefficient, int sgn) |
static SCIP_RETCODE | tryFixVar (SCIP *scip, SCIP *subscip, SCIP_SOL *sol, SCIP_Real *potential, SCIP_Real *slack, SCIP_VAR *var, SCIP_VAR *subvar, int *inftycounter, SCIP_HEURDATA *heurdata, SCIP_Bool *fixed) |
static SCIP_RETCODE | checkCands (SCIP *scip, SCIP_SOL *sol, SCIP_Bool roundit, 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 | applyRepair (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Longint nnodes) |
static | SCIP_DECL_HEURFREE (heurFreeRepair) |
static | SCIP_DECL_HEURINIT (heurInitRepair) |
static | SCIP_DECL_HEUREXIT (heurExitRepair) |
static | SCIP_DECL_HEUREXEC (heurExecRepair) |
SCIP_RETCODE | SCIPincludeHeurRepair (SCIP *scip) |
#define HEUR_NAME "repair" |
Definition at line 71 of file heur_repair.c.
#define HEUR_DESC "tries to repair a primal infeasible solution" |
Definition at line 72 of file heur_repair.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 73 of file heur_repair.c.
#define HEUR_PRIORITY -20 |
Definition at line 74 of file heur_repair.c.
#define HEUR_FREQ -1 |
Definition at line 75 of file heur_repair.c.
#define HEUR_FREQOFS 0 |
Definition at line 76 of file heur_repair.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 77 of file heur_repair.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 78 of file heur_repair.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 79 of file heur_repair.c.
#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 80 of file heur_repair.c.
#define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ |
Definition at line 82 of file heur_repair.c.
#define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ |
Definition at line 83 of file heur_repair.c.
#define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ |
Definition at line 84 of file heur_repair.c.
#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 85 of file heur_repair.c.
#define DEFAULT_FILENAME "-" |
file name of a solution to be used as infeasible starting point
Definition at line 87 of file heur_repair.c.
Referenced by SCIP_DECL_HEUREXEC(), SCIPincludeEventHdlrBoundwriting(), SCIPincludeHeurRepair(), SCIPincludeReaderCmin(), and SCIPincludeReaderSm().
#define DEFAULT_ROUNDIT TRUE |
if it is TRUE : fractional variables which are not fractional in the given solution are rounded, if it is FALSE : solving process of this heuristic is stopped
Definition at line 88 of file heur_repair.c.
Referenced by SCIPincludeHeurRepair().
#define DEFAULT_USEOBJFACTOR FALSE |
should a scaled objective function for original variables be used in repair subproblem?
Definition at line 92 of file heur_repair.c.
Referenced by SCIPincludeHeurRepair().
#define DEFAULT_USEVARFIX TRUE |
should variable fixings be used in repair subproblem?
Definition at line 95 of file heur_repair.c.
Referenced by SCIPincludeHeurRepair().
#define DEFAULT_USESLACKVARS FALSE |
should slack variables be used in repair subproblem?
Definition at line 96 of file heur_repair.c.
Referenced by SCIPincludeHeurRepair().
#define DEFAULT_ALPHA 2.0 |
how many times the potential should be bigger than the slack?
Definition at line 97 of file heur_repair.c.
|
static |
computes a factor, so that (factor) * (original objective upper bound) <= 1.
scip | SCIP data structure |
subscip | SCIP data structure |
factor | SCIP_Real to save the factor for the old objective function |
success | SCIP_Bool: Is the factor real? |
Definition at line 152 of file heur_repair.c.
References i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddOrigObjoffset(), SCIPgetLowerbound(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), TRUE, and vars.
Referenced by applyRepair().
|
static |
returns the contributed potential for a variable
scip | SCIP data structure |
sol | infeasible solution |
var | variable, which potential should be returned |
coefficient | variables coefficient in corresponding row |
sgn | sign of the slack |
Definition at line 228 of file heur_repair.c.
References assert(), NULL, SCIP_Real, SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), sol, and var.
Referenced by applyRepair(), and tryFixVar().
|
static |
finds out if a variable can be fixed with respect to the potentials of all rows, if it is possible, the potentials of rows are adapted and TRUE is returned.
scip | SCIP data structure |
subscip | sub-SCIP data structure |
sol | solution data structure |
potential | array with all potential values |
slack | array with all slack values |
var | variable to be fixed? |
subvar | representative variable for var in the sub-SCIP |
inftycounter | counters how many variables have an infinity potential in a row |
heurdata | repairs heuristic data |
fixed | pointer to store whether the fixing was performed (variable was unfixed) |
Definition at line 275 of file heur_repair.c.
References alpha, assert(), FALSE, getPotentialContributed(), heurdata, i, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPfixVar(), SCIPgetSolVal(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasZero(), SCIPisInfinity(), SCIProwGetLPPos(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), sol, TRUE, and var.
Referenced by applyRepair().
|
static |
checks if all integral variables in the given solution are integral.
scip | SCIP data structure |
sol | solution pointer to the to be checked solution |
roundit | round fractional solution values of integer variables |
success | pointer to store if all integral variables are integral or could be rounded |
Definition at line 408 of file heur_repair.c.
References assert(), FALSE, i, nbinvars, nintvars, NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPsetSolVal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), sol, TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
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 | Repair heuristic structure |
subsol | solution of the subproblem |
success | used to store whether new solution was found or not |
Definition at line 489 of file heur_repair.c.
References assert(), FALSE, heurdata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPtranslateSubSol(), SCIPtrySolFree(), and TRUE.
Referenced by applyRepair().
|
static |
tries to fix variables as an approach to repair a solution.
scip | SCIP data structure of the problem |
heur | pointer to this heuristic instance |
result | pointer to return the result status |
nnodes | nodelimit for sub-SCIP |
Definition at line 527 of file heur_repair.c.
References assert(), createNewSol(), FALSE, getObjectiveFactor(), getPotentialContributed(), heurdata, i, MAX, nbinvars, nintvars, nnodes, NULL, nvars, objval, REALABS, result, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_INVALID, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVED, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_NONE, SCIPABORT, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddSolFree(), SCIPaddVar(), SCIPallocBufferArray, SCIPcolGetVar(), SCIPcopyParamSettings(), SCIPcreate(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicVarbound(), SCIPcreateProb(), SCIPcreateSol(), SCIPcreateVarBasic(), SCIPdebug, SCIPdebugMsg, SCIPfindBranchrule(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetBoolParam(), SCIPgetLPRows(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNRuns(), SCIPgetNSols(), SCIPgetNTotalNodes(), SCIPgetPresolvingTime(), SCIPgetProbName(), SCIPgetRealParam(), SCIPgetRowSolActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetVarsData(), SCIPheurGetData(), SCIPincludeDefaultPlugins(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisParamFixed(), SCIPisZero(), SCIPprintStatistics(), SCIPreleaseCons(), SCIPreleaseVar(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetRealParam(), SCIPsetSolVal(), SCIPsetSubscipsOff(), SCIPsnprintf(), SCIPsolve(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), sol, TRUE, tryFixVar(), and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1042 of file heur_repair.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1059 of file heur_repair.c.
References heurdata, SCIP_INVALID, SCIP_OKAY, SCIP_UNKNOWN, and SCIPheurGetData().
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 1095 of file heur_repair.c.
References heurdata, MAX, NULL, nvars, SCIP_INVALID, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPheurGetData(), SCIPsnprintf(), SCIPstatistic, and SCIPverbMessage().
|
static |
execution method of primal heuristic. Repair needs an incorrect solution, in which all variables are in their bound.
Definition at line 1170 of file heur_repair.c.
References applyRepair(), assert(), checkCands(), cutoff, DEFAULT_FILENAME, FALSE, heurdata, MIN, nnodes, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_NOFILE, SCIP_OKAY, SCIPconstructLP(), SCIPcreateOrigSol(), SCIPcutoffNode(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisLPConstructed(), SCIPlinkLPSol(), SCIPreadSolFile(), SCIPtrySol(), SCIPwarningMessage(), and TRUE.