Detailed Description

repair primal heuristic

Author: Gregor Hendel; Thomas Nagel

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 '!'

#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 61 of file heur_repair.c.

◆ HEUR_DESC

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

Definition at line 62 of file heur_repair.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR '!'

Definition at line 63 of file heur_repair.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 0

Definition at line 64 of file heur_repair.c.

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 65 of file heur_repair.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 66 of file heur_repair.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 67 of file heur_repair.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE

Definition at line 68 of file heur_repair.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP TRUE

does the heuristic use a secondary SCIP instance?

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

◆ DEFAULT_MAXNODES

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

Definition at line 73 of file heur_repair.c.

◆ DEFAULT_MINNODES

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

Definition at line 74 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 75 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 77 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 78 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 85 of file heur_repair.c.

◆ DEFAULT_USEVARFIX

#define DEFAULT_USEVARFIX TRUE

should variable fixings be used in repair subproblem?

Definition at line 90 of file heur_repair.c.

◆ DEFAULT_USESLACKVARS

#define DEFAULT_USESLACKVARS FALSE

should slack variables be used in repair subproblem?

Definition at line 91 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 92 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

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 147 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 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

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 223 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 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

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
infeasible	pointer to store whether the fixing is infeasible
fixed	pointer to store whether the fixing was performed (variable was unfixed)

Definition at line 270 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 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

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 403 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 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

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 484 of file heur_repair.c.

References applyRepair(), FALSE, nnodes, NULL, 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

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 541 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_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(), 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 1046 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 1063 of file heur_repair.c.

References SCIP_Real.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitRepair )

static

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

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

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MINFIXINGRATE

◆ DEFAULT_NODESOFS

◆ DEFAULT_MAXNODES

◆ DEFAULT_MINNODES

◆ DEFAULT_NODESQUOT

◆ DEFAULT_FILENAME

◆ DEFAULT_ROUNDIT

◆ DEFAULT_USEOBJFACTOR

◆ DEFAULT_USEVARFIX

◆ DEFAULT_USESLACKVARS

◆ DEFAULT_ALPHA

Function Documentation

◆ getObjectiveFactor()

◆ getPotentialContributed()

◆ tryFixVar()

◆ checkCands()

◆ createNewSol()

◆ applyRepair()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEUREXEC()