Scippy

SCIP

Solving Constraint Integer Programs

heur_subnlp.c File Reference

Detailed Description

NLP local search primal heuristic using sub-SCIPs.

Author
Stefan Vigerske

Definition in file heur_subnlp.c.

#include "blockmemshell/memory.h"
#include "nlpi/nlpi.h"
#include "scip/cons_bounddisjunction.h"
#include "scip/cons_knapsack.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/cons_varbound.h"
#include "scip/heur_subnlp.h"
#include "scip/pub_cons.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_numerics.h"
#include "scip/scip_param.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   'q'
 
#define HEUR_PRIORITY   -2000000
 
#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_Bool runHeuristic (SCIP *scip)
 
static SCIP_RETCODE createSubSCIP (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE freeSubSCIP (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_DECL_EVENTEXEC (processVarEvent)
 
static SCIP_RETCODE addLinearConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
 
static SCIP_RETCODE addVarboundConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
 
static SCIP_RETCODE addLogicOrConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr)
 
static SCIP_RETCODE addSetppcConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr)
 
static SCIP_RETCODE addKnapsackConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr)
 
static SCIP_RETCODE addLinearConstraintsToNlp (SCIP *scip, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
 
static SCIP_RETCODE createSolFromNLP (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol, SCIP_HEUR *authorheur)
 
static SCIP_RETCODE createSolFromSubScipSol (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol, SCIP_SOL *subsol, SCIP_HEUR *authorheur)
 
static SCIP_RETCODE solveSubNLP (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Longint *iterused, SCIP_Bool tighttolerances, SCIP_SOL *resultsol)
 
static SCIP_RETCODE forbidFixation (SCIP *scip, SCIP_HEURDATA *heurdata)
 
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_SOL *resultsol)
 
SCIP_RETCODE SCIPresolveSolHeurSubNlp (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Longint itercontingent, SCIP_Real timelimit)
 
static SCIP_DECL_HEURCOPY (heurCopySubNlp)
 
static SCIP_DECL_HEURFREE (heurFreeSubNlp)
 
static SCIP_DECL_HEURINITSOL (heurInitsolSubNlp)
 
static SCIP_DECL_HEUREXITSOL (heurExitsolSubNlp)
 
static SCIP_DECL_HEUREXEC (heurExecSubNlp)
 
SCIP_RETCODE SCIPincludeHeurSubNlp (SCIP *scip)
 
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp (SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
 
SCIP_RETCODE SCIPupdateStartpointHeurSubNlp (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *solcand, SCIP_Real violation)
 
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)
 

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

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

Definition at line 63 of file heur_subnlp.c.

Referenced by SCIPincludeHeurSubNlp().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'q'

Definition at line 64 of file heur_subnlp.c.

Referenced by SCIPincludeHeurSubNlp().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -2000000

Definition at line 65 of file heur_subnlp.c.

Referenced by SCIPincludeHeurSubNlp().

◆ HEUR_FREQ

#define HEUR_FREQ   1

Definition at line 66 of file heur_subnlp.c.

Referenced by SCIPincludeHeurSubNlp().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 67 of file heur_subnlp.c.

Referenced by SCIPincludeHeurSubNlp().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 68 of file heur_subnlp.c.

Referenced by SCIPincludeHeurSubNlp().

◆ HEUR_TIMING

◆ 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 70 of file heur_subnlp.c.

Referenced by SCIPincludeHeurSubNlp().

Function Documentation

◆ runHeuristic()

static SCIP_Bool runHeuristic ( SCIP scip)
static

indicates whether the heuristic should be running, i.e., whether we expect something nonlinear after fixing all discrete variables

Parameters
scipSCIP data structure

Definition at line 124 of file heur_subnlp.c.

References FALSE, NULL, SCIPgetNNlpis(), SCIPhasNLPContinuousNonlinearity(), SCIPisNLPConstructed(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEURINITSOL().

◆ createSubSCIP()

◆ freeSubSCIP()

static SCIP_RETCODE freeSubSCIP ( SCIP scip,
SCIP_HEURDATA heurdata 
)
static

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( processVarEvent  )
static

◆ addLinearConstraints()

static SCIP_RETCODE addLinearConstraints ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_Bool  addcombconss,
SCIP_Bool  addcontconss 
)
static

adds linear constraints from a SCIP instance to its NLP

Parameters
scipSCIP data structure
conshdlrconstraint handler for linear constraints
addcombconsswhether to add combinatorial linear constraints to NLP
addcontconsswhether to add continuous linear constraints to NLP

Definition at line 467 of file heur_subnlp.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPaddNlRow(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsEnabled(), SCIPcreateNlRow(), SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisRelLE(), SCIPreleaseNlRow(), SCIPvarGetType(), and TRUE.

Referenced by addLinearConstraintsToNlp().

◆ addVarboundConstraints()

static SCIP_RETCODE addVarboundConstraints ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_Bool  addcombconss,
SCIP_Bool  addcontconss 
)
static

adds variable bound constraints from a SCIP instance to its NLP

Parameters
scipSCIP data structure
conshdlrconstraint handler for linear constraints
addcombconsswhether to add combinatorial linear constraints to NLP
addcontconsswhether to add continuous linear constraints to NLP

Definition at line 540 of file heur_subnlp.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddNlRow(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsEnabled(), SCIPcreateNlRow(), SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPreleaseNlRow(), and SCIPvarGetType().

Referenced by addLinearConstraintsToNlp().

◆ addLogicOrConstraints()

static SCIP_RETCODE addLogicOrConstraints ( SCIP scip,
SCIP_CONSHDLR conshdlr 
)
static

◆ addSetppcConstraints()

◆ addKnapsackConstraints()

◆ addLinearConstraintsToNlp()

static SCIP_RETCODE addLinearConstraintsToNlp ( SCIP scip,
SCIP_Bool  addcombconss,
SCIP_Bool  addcontconss 
)
static

adds combinatorial and/or continuous variants of linear constraints from a SCIP instance to its NLP

Parameters
scipSCIP data structure
addcombconsswhether to add combinatorial linear constraints to NLP
addcontconsswhether to add continuous linear constraints to NLP

Definition at line 828 of file heur_subnlp.c.

References addKnapsackConstraints(), addLinearConstraints(), addLogicOrConstraints(), addSetppcConstraints(), addVarboundConstraints(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPfindConshdlr().

Referenced by SCIPaddLinearConsToNlpHeurSubNlp(), and solveSubNLP().

◆ createSolFromNLP()

static SCIP_RETCODE createSolFromNLP ( SCIP scip,
SCIP_HEUR heur,
SCIP_SOL **  sol,
SCIP_HEUR authorheur 
)
static
Parameters
scipSCIP data structure
heurheuristic data structure
solbuffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten
authorheurthe heuristic which should be registered as author of the solution

Definition at line 879 of file heur_subnlp.c.

References NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPcreateSol(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPheurGetData(), SCIPsetSolVal(), SCIPsolSetHeur(), SCIPvarGetNLPSol(), and SCIPvarIsActive().

Referenced by solveSubNLP().

◆ createSolFromSubScipSol()

static SCIP_RETCODE createSolFromSubScipSol ( SCIP scip,
SCIP_HEUR heur,
SCIP_SOL **  sol,
SCIP_SOL subsol,
SCIP_HEUR authorheur 
)
static
Parameters
scipSCIP data structure
heurheuristic data structure
solbuffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten
subsolsolution of sub-SCIP
authorheurthe heuristic which should be registered as author of the solution

Definition at line 930 of file heur_subnlp.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPgetSolVal(), SCIPheurGetData(), SCIPsetSolVal(), SCIPsolSetHeur(), and SCIPvarIsActive().

Referenced by solveSubNLP().

◆ solveSubNLP()

static SCIP_RETCODE solveSubNLP ( SCIP scip,
SCIP_HEUR heur,
SCIP_RESULT result,
SCIP_SOL refpoint,
SCIP_Longint  itercontingent,
SCIP_Real  timelimit,
SCIP_Longint iterused,
SCIP_Bool  tighttolerances,
SCIP_SOL resultsol 
)
static
Parameters
sciporiginal SCIP data structure
heurheuristic data structure
resultbuffer to store result, DIDNOTFIND, FOUNDSOL, or 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
iterusedbuffer to store number of iterations used by NLP solver, or NULL if not of interest
tighttoleranceswhether to use tight feasibility tolerances and reduce presolve
resultsola solution where to store found solution values, if any, or NULL if to try adding to SCIP

Definition at line 972 of file heur_subnlp.c.

References addLinearConstraintsToNlp(), createSolFromNLP(), createSolFromSubScipSol(), FALSE, freeSubSCIP(), MAX, MIN, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_ERROR, SCIP_FOUNDSOL, SCIP_LONGINT_FORMAT, SCIP_NLPPAR_FEASTOL, SCIP_NLPPAR_ITLIM, SCIP_NLPPAR_OPTFILE, SCIP_NLPPAR_TILIM, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPTERMSTAT_MEMERR, SCIP_OKAY, SCIP_PARAMSETTING_DEFAULT, SCIP_PARAMSETTING_FAST, SCIP_Real, SCIP_STAGE_PRESOLVED, SCIP_STAGE_PRESOLVING, SCIP_STAGE_SOLVED, 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(), SCIPdebugMsg, SCIPepsilon(), SCIPerrorMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetMessagehdlr(), SCIPgetNLPObjval(), SCIPgetNLPSolstat(), SCIPgetNLPStatistics(), SCIPgetNLPTermstat(), SCIPgetNLPVars(), SCIPgetNNLPVars(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetObjlimit(), SCIPgetProbName(), SCIPgetRealParam(), SCIPgetSols(), SCIPgetSolVal(), SCIPgetStage(), SCIPgetStatus(), SCIPheurGetData(), SCIPisLE(), SCIPisNLPConstructed(), SCIPisParamFixed(), SCIPisZero(), SCIPmessagePrintInfo(), SCIPnlpStatisticsGetNIterations(), SCIPnlpStatisticsGetTotalTime(), SCIPpresolve(), SCIPpressedCtrlC(), SCIPresetParam(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetNLPInitialGuess(), SCIPsetNLPIntPar(), SCIPsetNLPRealPar(), SCIPsetNLPStringPar(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsolGetHeur(), SCIPsolve(), SCIPsolveNLP(), SCIPtransformProb(), SCIPtrySol(), SCIPtrySolFree(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetOrigvarSum(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPverbMessage(), SCIPwarningMessage(), and TRUE.

Referenced by SCIPapplyHeurSubNlp(), and SCIPresolveSolHeurSubNlp().

◆ forbidFixation()

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopySubNlp  )
static

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

Definition at line 2061 of file heur_subnlp.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeSubNlp  )
static

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

Definition at line 2075 of file heur_subnlp.c.

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

◆ SCIP_DECL_HEURINITSOL()

static 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 2095 of file heur_subnlp.c.

References createSubSCIP(), HEUR_TIMING, NULL, runHeuristic(), SCIP_CALL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetFreq(), SCIPheurGetFreqofs(), and SCIPheurSetTimingmask().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolSubNlp  )
static

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

Definition at line 2132 of file heur_subnlp.c.

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

◆ SCIP_DECL_HEUREXEC()