Scippy

SCIP

Solving Constraint Integer Programs

heur_repair.c File Reference

Detailed Description

repair primal heuristic

Author
Gregor Hendel
Thomas Nagel

Definition in file heur_repair.c.

#include <assert.h>
#include <string.h>
#include "scip/heur_repair.h"
#include "scip/cons_linear.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_varbound.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   '!'
 
#define HEUR_PRIORITY   0
 
#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 *infeasible, 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 39 of file heur_repair.c.

◆ HEUR_DESC

#define HEUR_DESC   "tries to repair a primal infeasible solution"

Definition at line 40 of file heur_repair.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   '!'

Definition at line 41 of file heur_repair.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   0

Definition at line 42 of file heur_repair.c.

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 43 of file heur_repair.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 44 of file heur_repair.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 45 of file heur_repair.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 46 of file heur_repair.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 47 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 48 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 50 of file heur_repair.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   5000 /* maximum number of nodes to regard in the subproblem */

Definition at line 51 of file heur_repair.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   50 /* minimum number of nodes to regard in the subproblem */

Definition at line 52 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 53 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 55 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 56 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 63 of file heur_repair.c.

◆ DEFAULT_USEVARFIX

#define DEFAULT_USEVARFIX   TRUE

should variable fixings be used in repair subproblem?

Definition at line 68 of file heur_repair.c.

◆ DEFAULT_USESLACKVARS

#define DEFAULT_USESLACKVARS   FALSE

should slack variables be used in repair subproblem?

Definition at line 69 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 70 of file heur_repair.c.

Function Documentation

◆ getObjectiveFactor()

static SCIP_RETCODE getObjectiveFactor ( SCIP scip,
SCIP subscip,
SCIP_Real factor,
SCIP_Bool success 
)
static

computes a factor, so that (factor) * (original objective upper bound) <= 1.

Parameters
scipSCIP data structure
subscipSCIP data structure
factorSCIP_Real to save the factor for the old objective function
successSCIP_Bool: Is the factor real?

Definition at line 125 of file heur_repair.c.

References getPotentialContributed(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddOrigObjoffset(), SCIPgetLowerbound(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by applyRepair().

◆ getPotentialContributed()

static SCIP_Real getPotentialContributed ( SCIP scip,
SCIP_SOL sol,
SCIP_VAR var,
SCIP_Real  coefficient,
int  sgn 
)
static

returns the contributed potential for a variable

Parameters
scipSCIP data structure
solinfeasible solution
varvariable, which potential should be returned
coefficientvariables coefficient in corresponding row
sgnsign of the slack

Definition at line 201 of file heur_repair.c.

References SCIP_Real, SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and tryFixVar().

Referenced by applyRepair(), getObjectiveFactor(), and tryFixVar().

◆ tryFixVar()

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 infeasible,
SCIP_Bool fixed 
)
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
scipSCIP data structure
subscipsub-SCIP data structure
solsolution data structure
potentialarray with all potential values
slackarray with all slack values
varvariable to be fixed?
subvarrepresentative variable for var in the sub-SCIP
inftycountercounters how many variables have an infinity potential in a row
heurdatarepairs heuristic data
infeasiblepointer to store whether the fixing is infeasible
fixedpointer to store whether the fixing was performed (variable was unfixed)

Definition at line 248 of file heur_repair.c.

References checkCands(), FALSE, getPotentialContributed(), 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 SCIP_RETCODE checkCands ( SCIP scip,
SCIP_SOL sol,
SCIP_Bool  roundit,
SCIP_Bool success 
)
static

checks if all integral variables in the given solution are integral.

Parameters
scipSCIP data structure
solsolution pointer to the to be checked solution
rounditround fractional solution values of integer variables
successpointer to store if all integral variables are integral or could be rounded

Definition at line 381 of file heur_repair.c.

References createNewSol(), FALSE, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPsetSolVal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), and TRUE.

Referenced by tryFixVar().

◆ createNewSol()

static SCIP_RETCODE createNewSol ( SCIP scip,
SCIP subscip,
SCIP_VAR **  subvars,
SCIP_HEUR heur,
SCIP_SOL subsol,
SCIP_Bool success 
)
static

creates a new solution for the original problem by copying the solution of the subproblem

Parameters
sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
subvarsthe variables of the subproblem
heurRepair heuristic structure
subsolsolution of the subproblem
successused to store whether new solution was found or not

Definition at line 462 of file heur_repair.c.

References applyRepair(), FALSE, nnodes, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolOrigObj(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPheurGetData(), SCIPsetSolVals(), SCIPtrySolFree(), and TRUE.

Referenced by applyRepair(), and checkCands().

◆ applyRepair()

static SCIP_RETCODE applyRepair ( SCIP scip,
SCIP_HEUR heur,
SCIP_RESULT result,
SCIP_Longint  nnodes 
)
static

tries to fix variables as an approach to repair a solution.

Parameters
scipSCIP data structure of the problem
heurpointer to this heuristic instance
resultpointer to return the result status
nnodesnodelimit for sub-SCIP

Definition at line 519 of file heur_repair.c.

References createNewSol(), FALSE, getObjectiveFactor(), getPotentialContributed(), MAX, nnodes, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURFREE(), SCIP_FOUNDSOL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVED, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_NONE, SCIPABORT, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddSolFree(), SCIPaddVar(), SCIPallocBufferArray, SCIPchgVarLbGlobal(), SCIPchgVarType(), SCIPchgVarUbGlobal(), SCIPcolGetVar(), SCIPcopyParamSettings(), SCIPcreate(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicVarbound(), SCIPcreateProb(), SCIPcreateSol(), SCIPcreateVarBasic(), SCIPdebug, SCIPdebugMsg, SCIPfindBranchrule(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetBestSol(), 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(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), TRUE, and tryFixVar().

Referenced by createNewSol().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeRepair  )
static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 1029 of file heur_repair.c.

Referenced by applyRepair().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitRepair  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 1046 of file heur_repair.c.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitRepair  )
static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 1083 of file heur_repair.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecRepair  )
static

execution method of primal heuristic. Repair needs an incorrect solution, in which all variables are in their bound.

Definition at line 1159 of file heur_repair.c.