Scippy

SCIP

Solving Constraint Integer Programs

heur_subnlp.h File Reference

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)
 
SCIPSCIPgetSubScipHeurSubNlp (SCIP *scip, SCIP_HEUR *heur)
 
SCIP_VAR ** SCIPgetVarMappingScip2SubScipHeurSubNlp (SCIP *scip, SCIP_HEUR *heur)
 
SCIP_VAR ** SCIPgetVarMappingSubScip2ScipHeurSubNlp (SCIP *scip, SCIP_HEUR *heur)
 
SCIP_SOLSCIPgetStartCandidateHeurSubNlp (SCIP *scip, SCIP_HEUR *heur)
 

Function Documentation

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
scipSCIP data structure
heurNLP heuristic
solcandsolution candidate
violationconstraint violation of solution candidate

Definition at line 2364 of file heur_subnlp.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPcreateSolCopy(), SCIPdebugMessage, SCIPfreeSol(), SCIPgetSolTransObj(), SCIPgetStage(), SCIPheurGetData(), SCIPheurGetName(), 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
sciporiginal SCIP data structure
heurheuristic data structure
resultpointer to store result of: did not run, solution found, no solution found, or fixing is infeasible (cutoff)
refpointpoint to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used
itercontingentiteration limit for NLP solver, or -1 for default of NLP heuristic
timelimittime limit for NLP solver
minimprovedesired minimal relative improvement in objective function value
iterusedbuffer to store number of iterations used by NLP solver, or NULL if not of interest

Definition at line 1620 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
sciporiginal SCIP data structure
heurheuristic data structure
solsolution for which to solve NLP, and where to store resolved solution values
successbuffer where to store whether a feasible solution was found
itercontingentiteration limit for NLP solver, or -1 for default of NLP heuristic
timelimittime limit for NLP solver

Definition at line 1815 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
sciporiginal SCIP data structure
heurheuristic data structure
addcombconsswhether to add combinatorial linear constraints, i.e., linear constraints that involve only discrete variables
addcontconsswhether to add continuous linear constraints, i.e., linear constraints that involve not only discrete variables

Definition at line 2330 of file heur_subnlp.c.

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

Referenced by SCIP_DECL_CONSSEPALP().

SCIP* SCIPgetSubScipHeurSubNlp ( SCIP scip,
SCIP_HEUR heur 
)

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

Parameters
sciporiginal SCIP data structure
heurheuristic data structure

Definition at line 2414 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
sciporiginal SCIP data structure
heurheuristic data structure

Definition at line 2431 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
sciporiginal SCIP data structure
heurheuristic data structure

Definition at line 2448 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
sciporiginal SCIP data structure
heurheuristic data structure

Definition at line 2465 of file heur_subnlp.c.

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