Detailed Description

NLP local search primal heuristic using sub-SCIPs.

Author: Stefan Vigerske

Definition in file heur_subnlp.c.

#include "blockmemshell/memory.h"
#include "scip/nlpi_ipopt.h"
#include "scip/cons_bounddisjunction.h"
#include "scip/cons_setppc.h"
#include "scip/heur_subnlp.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_event.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_nlp.h"
#include "scip/scip_nlpi.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_presol.h"
#include "scip/scip_pricer.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_var.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	HEUR_NAME "subnlp"
#define	HEUR_DESC "primal heuristic that performs a local search in an NLP after fixing integer variables and presolving"
#define	HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
#define	HEUR_PRIORITY -2000010
#define	HEUR_FREQ 1
#define	HEUR_FREQOFS 0
#define	HEUR_MAXDEPTH -1
#define	HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
#define	HEUR_USESSUBSCIP FALSE

Functions
static SCIP_RETCODE	freeSubSCIP (SCIP scip, SCIP_HEURDATA heurdata)
static SCIP_RETCODE	createSubSCIP (SCIP scip, SCIP_HEURDATA heurdata)
static	SCIP_DECL_EVENTEXEC (processVarEvent)
static SCIP_RETCODE	createSolFromNLP (SCIP scip, SCIP_HEUR heur, SCIP_SOL *sol, SCIP_HEUR authorheur)
static SCIP_RETCODE	processNLPSol (SCIP scip, SCIP_HEUR heur, SCIP_HEUR authorheur, SCIP_RESULT result, SCIP_SOL *resultsol)
static SCIP_RETCODE	createSolFromSubScipSol (SCIP scip, SCIP_HEUR heur, SCIP_SOL *sol, SCIP_SOL subsol, SCIP_HEUR *authorheur)
static int	calcIterLimit (SCIP scip, SCIP_HEURDATA heurdata)
static SCIP_RETCODE	solveSubNLP (SCIP scip, SCIP_HEUR heur, SCIP_RESULT result, SCIP_SOL refpoint, SCIP_SOL *resultsol)
static SCIP_RETCODE	forbidFixation (SCIP scip, SCIP_HEURDATA heurdata)
static	SCIP_DECL_HEURCOPY (heurCopySubNlp)
static	SCIP_DECL_HEURFREE (heurFreeSubNlp)
static	SCIP_DECL_HEURINIT (heurInitSubNlp)
static	SCIP_DECL_HEURINITSOL (heurInitsolSubNlp)
static	SCIP_DECL_HEUREXITSOL (heurExitsolSubNlp)
static	SCIP_DECL_HEUREXEC (heurExecSubNlp)
SCIP_RETCODE	SCIPincludeHeurSubNlp (SCIP *scip)
SCIP_RETCODE	SCIPapplyHeurSubNlp (SCIP scip, SCIP_HEUR heur, SCIP_RESULT result, SCIP_SOL refpoint, SCIP_SOL *resultsol)
SCIP_RETCODE	SCIPupdateStartpointHeurSubNlp (SCIP scip, SCIP_HEUR heur, SCIP_SOL *solcand, SCIP_Real violation)
SCIP_SOL *	SCIPgetStartCandidateHeurSubNlp (SCIP scip, SCIP_HEUR heur)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "subnlp"

Definition at line 69 of file heur_subnlp.c.

◆ HEUR_DESC

#define HEUR_DESC "primal heuristic that performs a local search in an NLP after fixing integer variables and presolving"

Definition at line 70 of file heur_subnlp.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS

Definition at line 71 of file heur_subnlp.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -2000010

Definition at line 72 of file heur_subnlp.c.

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 73 of file heur_subnlp.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 74 of file heur_subnlp.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 75 of file heur_subnlp.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE

Definition at line 76 of file heur_subnlp.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance? we set this to FALSE because we want this heuristic to also run within other heuristics

Definition at line 77 of file heur_subnlp.c.

Function Documentation

◆ freeSubSCIP()

SCIP_RETCODE freeSubSCIP	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata )

static

free sub-SCIP data structure

Parameters

scip	SCIP data structure
heurdata	heuristic data structure

Definition at line 137 of file heur_subnlp.c.

References assert(), heurdata, i, NULL, SCIP_CALL, SCIP_EVENTTYPE_GBDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), SCIPfree(), SCIPfreeBlockMemoryArray, SCIPgetOrigVarsData(), SCIPreleaseVar(), SCIPvarGetProbindex(), SCIPvarIsActive(), and var.

Referenced by createSubSCIP(), SCIP_DECL_HEUREXITSOL(), SCIPapplyHeurSubNlp(), and solveSubNLP().

◆ createSubSCIP()

SCIP_RETCODE createSubSCIP	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata )

static

creates copy of CIP from problem in SCIP

Parameters

scip	SCIP data structure
heurdata	heuristic data structure

Definition at line 190 of file heur_subnlp.c.

References assert(), FALSE, freeSubSCIP(), heurdata, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GBDCHANGED, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMSETTING_OFF, SCIP_STAGE_PRESOLVED, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIP_STATUS_NODELIMIT, SCIPallocClearBlockMemoryArray, SCIPblkmem(), SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPcopyConss(), SCIPcopyParamSettings(), SCIPcopyPlugins(), SCIPcopyProb(), SCIPcopyVars(), SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPgetNConss(), SCIPgetNContImplVars(), SCIPgetNContVars(), SCIPgetNNlpis(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetStage(), SCIPgetStatus(), SCIPgetVars(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapEntryGetImage(), SCIPhashmapEntryGetOrigin(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetImage(), SCIPhashmapGetNEntries(), SCIPisFeasEQ(), SCIPisNLPConstructed(), SCIPisParamFixed(), SCIPpresolve(), SCIPresetParam(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPsnprintf(), SCIPsolve(), SCIPtransformProb(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPwarningMessage(), TRUE, var, and vars.

Referenced by SCIPapplyHeurSubNlp().

◆ SCIP_DECL_EVENTEXEC()

SCIP_DECL_EVENTEXEC ( processVarEvent )

static

process variable global bound change event

Definition at line 441 of file heur_subnlp.c.

References assert(), heurdata, NULL, nvars, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPeventGetNewbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPgetVars(), SCIPvarGetProbindex(), and var.

◆ createSolFromNLP()

SCIP_RETCODE createSolFromNLP	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_SOL **	sol,
		SCIP_HEUR *	authorheur )

static

Parameters

scip	SCIP data structure
heur	heuristic data structure
sol	buffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten
authorheur	the heuristic which should be registered as author of the solution

Definition at line 498 of file heur_subnlp.c.

References assert(), heurdata, i, MAX, MIN, NULL, nvars, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPcreateSol(), SCIPgetVarsData(), SCIPhasNLPSolution(), SCIPheurGetData(), SCIPsetSolVal(), SCIPsolSetHeur(), SCIPvarGetLbLocal(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), SCIPvarIsActive(), sol, var, and vars.

Referenced by processNLPSol().

◆ processNLPSol()

SCIP_RETCODE processNLPSol	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_HEUR *	authorheur,
		SCIP_RESULT *	result,
		SCIP_SOL *	resultsol )

static

creates SCIP solution from NLP and tries adding to SCIP or only checks feasibility

Parameters

scip	original SCIP data structure
heur	heuristic data structure
authorheur	the heuristic that should be the author of solution, if any
result	buffer to store result FOUNDSOL if a solution has been found and accepted
resultsol	a solution where to store found solution values, if any, or NULL if to try adding to SCIP

Definition at line 564 of file heur_subnlp.c.

References assert(), createSolFromNLP(), FALSE, heurdata, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_OKAY, SCIPcheckSol(), SCIPdebugMsg, SCIPgetNLPObjval(), SCIPgetUpperbound(), SCIPhasNLPSolution(), SCIPheurGetData(), SCIPinfoMessage(), SCIPisLE(), SCIPtrySolFree(), sol, and TRUE.

Referenced by solveSubNLP().

◆ createSolFromSubScipSol()

SCIP_RETCODE createSolFromSubScipSol	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_SOL **	sol,
		SCIP_SOL *	subsol,
		SCIP_HEUR *	authorheur )

static

Parameters

scip	SCIP data structure
heur	heuristic data structure
sol	buffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten
subsol	solution of sub-SCIP
authorheur	the heuristic which should be registered as author of the solution

Definition at line 680 of file heur_subnlp.c.

References assert(), heurdata, i, MAX, MIN, NULL, nvars, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPcreateSol(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPheurGetData(), SCIPsetSolVal(), SCIPsolSetHeur(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsActive(), sol, var, and vars.

Referenced by solveSubNLP().

◆ calcIterLimit()

int calcIterLimit	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata )

static

finds an iteration limit

Parameters

scip	original SCIP data structure
heurdata	heuristic data

Definition at line 747 of file heur_subnlp.c.

References heurdata, MAX, and MAX3.

Referenced by SCIP_DECL_HEUREXEC(), and solveSubNLP().

◆ solveSubNLP()

SCIP_RETCODE solveSubNLP	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_RESULT *	result,
		SCIP_SOL *	refpoint,
		SCIP_SOL *	resultsol )

static

solves the subNLP specified in subscip

Parameters

scip	original SCIP data structure
heur	heuristic data structure
result	buffer to store result, DIDNOTFIND, FOUNDSOL, or CUTOFF
refpoint	point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used
resultsol	a solution where to store found solution values, if any, or NULL if to try adding to SCIP

Definition at line 772 of file heur_subnlp.c.

References assert(), SCIP_NlpStatistics::boundviol, calcIterLimit(), SCIP_NlpStatistics::consviol, createSolFromSubScipSol(), FALSE, freeSubSCIP(), heurdata, i, MAX, MIN, SCIP_NlpStatistics::niterations, NULL, processNLPSol(), REALABS, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_ERROR, SCIP_FOUNDSOL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBINFEASIBLE, SCIP_NLPSOLSTAT_LOCINFEASIBLE, SCIP_NLPTERMSTAT_ITERLIMIT, SCIP_NLPTERMSTAT_OKAY, SCIP_NLPTERMSTAT_OUTOFMEMORY, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVED, SCIP_STAGE_PRESOLVING, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_USERINTERRUPT, SCIP_VERBLEVEL_MINIMAL, SCIPABORT, SCIPallocBufferArray, SCIPcheckSol(), SCIPdebug, SCIPdebugMsg, SCIPerrorMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPgetNLPObjval(), SCIPgetNLPSolstat(), SCIPgetNLPStatistics(), SCIPgetNLPTermstat(), SCIPgetNLPVars(), SCIPgetNNLPVars(), SCIPgetNPresolRounds(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetRealParam(), SCIPgetSols(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPheurGetData(), SCIPinfoMessage(), SCIPisInfinity(), SCIPisLE(), SCIPisNLPConstructed(), SCIPisTransformed(), SCIPisZero(), SCIPmergeNLPIStatistics(), SCIPpresolve(), SCIPprintStatistics(), SCIPsetLongintParam(), SCIPsetNLPInitialGuess(), SCIPsetRealParam(), SCIPsolGetHeur(), SCIPsolve(), SCIPsolveNLP, SCIPtrySolFree(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetOrigvarSum(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPverbMessage(), SCIPwarningMessage(), sol, SCIP_NlpStatistics::totaltime, TRUE, and var.

Referenced by SCIPapplyHeurSubNlp().

◆ forbidFixation()

SCIP_RETCODE forbidFixation	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata )

static

adds a set covering or bound disjunction constraint to the original problem

Parameters

scip	SCIP data structure
heurdata	heuristic data

Definition at line 1233 of file heur_subnlp.c.

References assert(), FALSE, heurdata, i, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPceil(), SCIPcreateConsBounddisjunction(), SCIPcreateConsSetcover(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNegatedVar(), SCIPgetOrigVarsData(), SCIPisEQ(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsImpliedIntegral(), TRUE, and var.

Referenced by SCIPapplyHeurSubNlp().

◆ SCIP_DECL_HEURCOPY()

SCIP_DECL_HEURCOPY ( heurCopySubNlp )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 1406 of file heur_subnlp.c.

References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurSubNlp().

◆ SCIP_DECL_HEURFREE()

SCIP_DECL_HEURFREE ( heurFreeSubNlp )

static

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

Definition at line 1420 of file heur_subnlp.c.

References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPheurGetData().

◆ SCIP_DECL_HEURINIT()

SCIP_DECL_HEURINIT ( heurInitSubNlp )

static

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

Definition at line 1440 of file heur_subnlp.c.

References assert(), FALSE, heurdata, NULL, SCIP_OKAY, SCIPfeastol(), and SCIPheurGetData().

◆ SCIP_DECL_HEURINITSOL()

SCIP_DECL_HEURINITSOL ( heurInitsolSubNlp )

static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 1469 of file heur_subnlp.c.

References assert(), heurdata, NULL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_HEURTIMING_NONE, SCIP_OKAY, SCIPgetNNlpis(), SCIPheurGetData(), SCIPheurGetFreqofs(), SCIPheurGetTimingmask(), SCIPheurSetTimingmask(), and SCIPisNLPConstructed().

◆ SCIP_DECL_HEUREXITSOL()

SCIP_DECL_HEUREXITSOL ( heurExitsolSubNlp )

static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 1495 of file heur_subnlp.c.

References assert(), FALSE, freeSubSCIP(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurSetTimingmask().

◆ SCIP_DECL_HEUREXEC()

SCIP_DECL_HEUREXEC ( heurExecSubNlp )

static

execution method of primal heuristic

Definition at line 1527 of file heur_subnlp.c.

References assert(), calcIterLimit(), HEUR_TIMING, heurdata, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_HEURTIMING_NONE, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_Real, SCIPapplyHeurSubNlp(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetLocalDualbound(), SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPgetNNlpis(), SCIPgetNNodes(), SCIPgetPrimalbound(), SCIPhasNLPContinuousNonlinearity(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPheurSetTimingmask(), SCIPinfoMessage(), SCIPisEQ(), SCIPisInfinity(), SCIPisNLPConstructed(), and SCIPsolGetHeur().

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

Function Documentation

◆ freeSubSCIP()

◆ createSubSCIP()

◆ SCIP_DECL_EVENTEXEC()

◆ createSolFromNLP()

◆ processNLPSol()

◆ createSolFromSubScipSol()

◆ calcIterLimit()

◆ solveSubNLP()

◆ forbidFixation()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()