Detailed Description

NLP local search primal heuristic using sub-SCIPs.

Author: Stefan Vigerske

This heuristic applies a NLP local search to a nonlinear CIP after fixing all discrete variables. That is, the CIP is copied, all discrete variables are fixed, presolving is applied, and if the resulting CIP has a nonlinear relaxation, then it is tried to solve this relaxation by an NLP solver. The heuristic only runs if continuous nonlinearities are present (SCIPhasNLPContinuousNonlinearity()).

Fixing values for discrete values are either taken from a solution of the LP relaxation which satisfies all integrality constraints, or are provided by SCIPupdateStartpointHeurSubNlp().

This heuristic is orthogonal to the undercover heuristic (heur_undercover.h), which fixes variables in a nonlinear CIP in a way that a (possibly mixed-integer) linear subproblem is obtained.

Definition in file heur_subnlp.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeHeurSubNlp (SCIP *scip)

SCIP_RETCODE	SCIPupdateStartpointHeurSubNlp (SCIP scip, SCIP_HEUR heur, SCIP_SOL *solcand, SCIP_Real violation)

SCIP_RETCODE	SCIPapplyHeurSubNlp (SCIP scip, SCIP_HEUR heur, SCIP_RESULT result, SCIP_SOL refpoint, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Real minimprove, SCIP_Longint *iterused)

SCIP_RETCODE	SCIPresolveSolHeurSubNlp (SCIP scip, SCIP_HEUR heur, SCIP_SOL sol, SCIP_Bool success, SCIP_Longint itercontingent, SCIP_Real timelimit)

SCIP_RETCODE	SCIPaddLinearConsToNlpHeurSubNlp (SCIP scip, SCIP_HEUR heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)

SCIP *	SCIPgetSubScipHeurSubNlp (SCIP scip, SCIP_HEUR heur)

SCIP_VAR **	SCIPgetVarMappingScip2SubScipHeurSubNlp (SCIP scip, SCIP_HEUR heur)

SCIP_VAR **	SCIPgetVarMappingSubScip2ScipHeurSubNlp (SCIP scip, SCIP_HEUR heur)

SCIP_SOL *	SCIPgetStartCandidateHeurSubNlp (SCIP scip, SCIP_HEUR heur)

Function Documentation

SCIP_RETCODE SCIPincludeHeurSubNlp ( SCIP * scip )

creates the NLP local search primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2131 of file heur_subnlp.c.

References BMSclearMemory, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPaddStringParam(), SCIPallocMemory, SCIPincludeEventhdlrBasic(), SCIPincludeHeurBasic(), SCIPinfinity(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInitsol(), and TRUE.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPupdateStartpointHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_SOL *	solcand,
		SCIP_Real	violation
	)

updates the starting point for the NLP heuristic

Is called, for example, by a constraint handler that handles nonlinear constraints when a check on feasibility of a solution fails.

updates the starting point for the NLP heuristic

Is called by a constraint handler that handles nonlinear constraints when a check on feasibility of a solution fails.

Parameters

scip	SCIP data structure
heur	NLP heuristic
solcand	solution candidate
violation	constraint violation of solution candidate

Definition at line 2258 of file heur_subnlp.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPcreateSolCopy(), SCIPdebugMessage, SCIPfreeSol(), SCIPgetSolTransObj(), SCIPgetStage(), SCIPheurGetData(), SCIPheurGetName(), SCIPisGT(), SCIPisPositive(), SCIPisRelGT(), SCIPsolGetHeur(), and SCIPunlinkSol().

Referenced by SCIP_DECL_CONSCHECK().

SCIP_RETCODE SCIPapplyHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_RESULT *	result,
		SCIP_SOL *	refpoint,
		SCIP_Longint	itercontingent,
		SCIP_Real	timelimit,
		SCIP_Real	minimprove,
		SCIP_Longint *	iterused
	)

main procedure of the subNLP heuristic

Parameters

scip	original SCIP data structure
heur	heuristic data structure
result	pointer to store result of: did not run, solution found, no solution found, or fixing is infeasible (cutoff)
refpoint	point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used
itercontingent	iteration limit for NLP solver, or -1 for default of NLP heuristic
timelimit	time limit for NLP solver
minimprove	desired minimal relative improvement in objective function value
iterused	buffer to store number of iterations used by NLP solver, or NULL if not of interest

Definition at line 1517 of file heur_subnlp.c.

References createSubSCIP(), FALSE, forbidFixation(), freeSubSCIP(), MAX, MIN, NULL, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPdebugMessage, SCIPfloor(), SCIPgetLowerbound(), SCIPgetLPSolstat(), SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNSols(), SCIPgetOrigVarsData(), SCIPgetSolVal(), SCIPgetStage(), SCIPgetUpperbound(), SCIPheurGetData(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPisTransformed(), SCIPsetObjlimit(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and solveSubNLP().

Referenced by SCIP_DECL_HEUREXEC(), and SCIPapplyUndercover().

SCIP_RETCODE SCIPresolveSolHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_SOL *	sol,
		SCIP_Bool *	success,
		SCIP_Longint	itercontingent,
		SCIP_Real	timelimit
	)

for a given solution, resolves the corresponding subNLP and updates solution values for continuous variables, if NLP solution is feasible in original problem

Parameters

scip	original SCIP data structure
heur	heuristic data structure
sol	solution for which to solve NLP, and where to store resolved solution values
success	buffer where to store whether a feasible solution was found
itercontingent	iteration limit for NLP solver, or -1 for default of NLP heuristic
timelimit	time limit for NLP solver

Definition at line 1712 of file heur_subnlp.c.

References createSubSCIP(), FALSE, freeSubSCIP(), MAX, MIN, NULL, REALABS, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPdebugMessage, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetObjsense(), SCIPgetOrigVarsData(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetStage(), SCIPheurGetData(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisTransformed(), SCIPround(), SCIPsetObjlimit(), SCIPtransformObj(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), solveSubNLP(), and TRUE.

SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_Bool	addcombconss,
		SCIP_Bool	addcontconss
	)

adds all known linear constraint to the NLP, if initialized and not done already This function is temporary and will hopefully become obsolete in the near future.

Parameters

scip	original SCIP data structure
heur	heuristic data structure
addcombconss	whether to add combinatorial linear constraints, i.e., linear constraints that involve only discrete variables
addcontconss	whether to add continuous linear constraints, i.e., linear constraints that involve not only discrete variables

Definition at line 2224 of file heur_subnlp.c.

References addLinearConstraintsToNlp(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetData(), and SCIPheurGetName().

Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_HEURINITSOL().

SCIP* SCIPgetSubScipHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur
	)

gets sub-SCIP used by NLP heuristic, or NULL if none

Parameters

scip	original SCIP data structure
heur	heuristic data structure

Definition at line 2308 of file heur_subnlp.c.

References HEUR_NAME, NULL, SCIPheurGetData(), and SCIPheurGetName().

SCIP_VAR** SCIPgetVarMappingScip2SubScipHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur
	)

gets mapping of SCIP variables to sub-SCIP variables

Parameters

scip	original SCIP data structure
heur	heuristic data structure

Definition at line 2325 of file heur_subnlp.c.

References HEUR_NAME, NULL, SCIPheurGetData(), and SCIPheurGetName().

SCIP_VAR** SCIPgetVarMappingSubScip2ScipHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur
	)

gets mapping of sub-SCIP variables to SCIP variables

Parameters

scip	original SCIP data structure
heur	heuristic data structure

Definition at line 2342 of file heur_subnlp.c.

References HEUR_NAME, NULL, SCIPheurGetData(), and SCIPheurGetName().

SCIP_SOL* SCIPgetStartCandidateHeurSubNlp	(	SCIP *	scip,
		SCIP_HEUR *	heur
	)

gets startpoint candidate to be used in next call to NLP heuristic, or NULL if none

Parameters

scip	original SCIP data structure
heur	heuristic data structure

Definition at line 2359 of file heur_subnlp.c.

References HEUR_NAME, NULL, SCIPheurGetData(), and SCIPheurGetName().

SCIP

Detailed Description

Functions

Function Documentation