Detailed Description
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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "repair" |
Definition at line 71 of file heur_repair.c.
◆ HEUR_DESC
#define HEUR_DESC "tries to repair a primal infeasible solution" |
Definition at line 72 of file heur_repair.c.
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 73 of file heur_repair.c.
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -20 |
Definition at line 74 of file heur_repair.c.
◆ HEUR_FREQ
#define HEUR_FREQ -1 |
Definition at line 75 of file heur_repair.c.
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 76 of file heur_repair.c.
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 77 of file heur_repair.c.
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 78 of file heur_repair.c.
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 79 of file heur_repair.c.
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 80 of file heur_repair.c.
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ |
Definition at line 82 of file heur_repair.c.
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ |
Definition at line 83 of file heur_repair.c.
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ |
Definition at line 84 of file heur_repair.c.
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 85 of file heur_repair.c.
◆ DEFAULT_FILENAME
#define DEFAULT_FILENAME "-" |
file name of a solution to be used as infeasible starting point
Definition at line 87 of file heur_repair.c.
◆ DEFAULT_ROUNDIT
#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.
◆ DEFAULT_USEOBJFACTOR
#define DEFAULT_USEOBJFACTOR FALSE |
should a scaled objective function for original variables be used in repair subproblem?
Definition at line 95 of file heur_repair.c.
◆ DEFAULT_USEVARFIX
#define DEFAULT_USEVARFIX TRUE |
should variable fixings be used in repair subproblem?
Definition at line 100 of file heur_repair.c.
◆ DEFAULT_USESLACKVARS
#define DEFAULT_USESLACKVARS FALSE |
should slack variables be used in repair subproblem?
Definition at line 101 of file heur_repair.c.
◆ DEFAULT_ALPHA
#define DEFAULT_ALPHA 2.0 |
how many times the potential should be bigger than the slack?
Definition at line 102 of file heur_repair.c.
Function Documentation
◆ getObjectiveFactor()
|
static |
computes a factor, so that (factor) * (original objective upper bound) <= 1.
- Parameters
-
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 157 of file heur_repair.c.
References getPotentialContributed(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddOrigObjoffset(), SCIPgetLowerbound(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by applyRepair().
◆ getPotentialContributed()
|
static |
returns the contributed potential for a variable
- Parameters
-
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 233 of file heur_repair.c.
References NULL, SCIP_Real, SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and tryFixVar().
Referenced by applyRepair(), getObjectiveFactor(), and tryFixVar().
◆ 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.
- Parameters
-
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 280 of file heur_repair.c.
References checkCands(), FALSE, getPotentialContributed(), 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(), and TRUE.
Referenced by applyRepair(), and getPotentialContributed().
◆ checkCands()
|
static |
checks if all integral variables in the given solution are integral.
- Parameters
-
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 413 of file heur_repair.c.
References createNewSol(), FALSE, NULL, REALABS, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPsetSolVal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), and TRUE.
Referenced by tryFixVar().
◆ createNewSol()
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
- Parameters
-
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 494 of file heur_repair.c.
References applyRepair(), FALSE, nnodes, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPtranslateSubSol(), SCIPtrySolFree(), and TRUE.
Referenced by applyRepair(), and checkCands().
◆ applyRepair()
|
static |
tries to fix variables as an approach to repair a solution.
- Parameters
-
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 532 of file heur_repair.c.
References createNewSol(), FALSE, getObjectiveFactor(), getPotentialContributed(), MAX, nnodes, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURFREE(), SCIP_FOUNDSOL, 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(), TRUE, and tryFixVar().
Referenced by createNewSol().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1043 of file heur_repair.c.
Referenced by applyRepair().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1060 of file heur_repair.c.
References SCIP_Real.
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 1096 of file heur_repair.c.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic. Repair needs an incorrect solution, in which all variables are in their bound.
Definition at line 1171 of file heur_repair.c.