Scippy

SCIP

Solving Constraint Integer Programs

heur_proximity.c File Reference

Detailed Description

improvement heuristic which uses an auxiliary objective instead of the original objective function which is itself added as a constraint to a sub-SCIP instance. The heuristic was presented by Matteo Fischetti and Michele Monaci.

Author
Gregor Hendel

Definition in file heur_proximity.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heuristics.h"
#include "scip/heur_proximity.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_nodesel.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_var.h"
#include <string.h>

Go to the source code of this file.

Macros

#define HEUR_NAME   "proximity"
 
#define HEUR_DESC   "heuristic trying to improve the incumbent by an auxiliary proximity objective function"
 
#define HEUR_DISPCHAR   'P'
 
#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   TRUE
 
#define EVENTHDLR_NAME   "Proximity"
 
#define EVENTHDLR_DESC   "LP event handler for " HEUR_NAME " heuristic"
 
#define DEFAULT_MAXNODES   10000LL
 
#define DEFAULT_MINIMPROVE   0.02
 
#define DEFAULT_MINGAP   0.01
 
#define DEFAULT_MINNODES   1LL
 
#define DEFAULT_MINLPITERS   200LL
 
#define DEFAULT_MAXLPITERS   100000LL
 
#define DEFAULT_NODESOFS   50LL
 
#define DEFAULT_WAITINGNODES   100LL
 
#define DEFAULT_NODESQUOT   0.1
 
#define DEFAULT_USELPROWS   FALSE
 
#define DEFAULT_BINVARQUOT   0.1
 
#define DEFAULT_RESTART   TRUE
 
#define DEFAULT_USEFINALLP   FALSE
 
#define DEFAULT_LPITERSQUOT   0.2
 
#define DEFAULT_USEUCT   FALSE
 

Functions

static SCIP_RETCODE solveLp (SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
 
static SCIP_RETCODE createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool usefinallp, SCIP_Bool *success)
 
static SCIP_RETCODE setupSubproblem (SCIP_HEURDATA *heurdata, SCIP *subscip)
 
static SCIP_RETCODE deleteSubproblem (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_DECL_EVENTEXEC (eventExecProximity)
 
static SCIP_DECL_HEURCOPY (heurCopyProximity)
 
static SCIP_DECL_HEURFREE (heurFreeProximity)
 
static SCIP_DECL_HEURINIT (heurInitProximity)
 
static SCIP_DECL_HEUREXITSOL (heurExitsolProximity)
 
static SCIP_DECL_HEUREXEC (heurExecProximity)
 
SCIP_RETCODE SCIPdeleteSubproblemProximity (SCIP *scip)
 
SCIP_RETCODE SCIPapplyProximity (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes, SCIP_Longint nlpiters, SCIP_Longint *nusednodes, SCIP_Longint *nusedlpiters, SCIP_Bool freesubscip)
 
SCIP_RETCODE SCIPincludeHeurProximity (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "proximity"

◆ HEUR_DESC

#define HEUR_DESC   "heuristic trying to improve the incumbent by an auxiliary proximity objective function"

Definition at line 57 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'P'

Definition at line 58 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -2000000

Definition at line 59 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 60 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 61 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 62 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 63 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 64 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "Proximity"

Definition at line 67 of file heur_proximity.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPapplyProximity().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC   "LP event handler for " HEUR_NAME " heuristic"

Definition at line 68 of file heur_proximity.c.

Referenced by SCIPapplyProximity().

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   10000LL

maximum number of nodes to regard in the subproblem

Definition at line 72 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.02

factor by which proximity should at least improve the incumbent

Definition at line 73 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_MINGAP

#define DEFAULT_MINGAP   0.01

minimum primal-dual gap for which the heuristic is executed

Definition at line 74 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   1LL

minimum number of nodes to regard in the subproblem

Definition at line 75 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_MINLPITERS

#define DEFAULT_MINLPITERS   200LL

minimum number of LP iterations to perform in one sub-mip

Definition at line 76 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_MAXLPITERS

#define DEFAULT_MAXLPITERS   100000LL

maximum number of LP iterations to be performed in the subproblem

Definition at line 77 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS   50LL

number of nodes added to the contingent of the total nodes

Definition at line 78 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_WAITINGNODES

#define DEFAULT_WAITINGNODES   100LL

default waiting nodes since last incumbent before heuristic is executed

Definition at line 79 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

default quotient of sub-MIP nodes with respect to number of processed nodes

Definition at line 80 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_USELPROWS

#define DEFAULT_USELPROWS   FALSE

should subproblem be constructed based on LP row information?

Definition at line 81 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_BINVARQUOT

#define DEFAULT_BINVARQUOT   0.1

default threshold for percentage of binary variables required to start

Definition at line 82 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_RESTART

#define DEFAULT_RESTART   TRUE

should the heuristic immediately run again on its newly found solution?

Definition at line 83 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_USEFINALLP

#define DEFAULT_USEFINALLP   FALSE

should the heuristic solve a final LP in case of continuous objective variables?

Definition at line 84 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_LPITERSQUOT

#define DEFAULT_LPITERSQUOT   0.2

default quotient of sub-MIP LP iterations with respect to LP iterations so far

Definition at line 85 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_USEUCT

#define DEFAULT_USEUCT   FALSE

should uct node selection be used at the beginning of the search?

Definition at line 86 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

Function Documentation

◆ solveLp()

static SCIP_RETCODE solveLp ( SCIP scip,
SCIP_SOL sol,
SCIP_Bool success 
)
static

optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values

Parameters
scipSCIP data structure
solcandidate solution for which continuous variables should be optimized
successwas the dive successful?

Definition at line 131 of file heur_proximity.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPdebugMsg, SCIPendDive(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisNLPConstructed(), SCIPlinkLPSol(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), and TRUE.

Referenced by createNewSol().

◆ createNewSol()

static SCIP_RETCODE createNewSol ( SCIP scip,
SCIP subscip,
SCIP_VAR **  subvars,
SCIP_HEUR heur,
SCIP_SOL subsol,
SCIP_Bool  usefinallp,
SCIP_Bool success 
)
static

creates a new solution for the original problem by copying the solution of the subproblem

Parameters
sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
subvarsthe variables of the subproblem
heurproximity heuristic structure
subsolsolution of the subproblem
usefinallpshould continuous variables be optimized by a final LP
successused to store whether new solution was found or not

Definition at line 217 of file heur_proximity.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetNOrigVars(), SCIPgetObjNorm(), SCIPgetSolOrigObj(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPisLPConstructed(), SCIPisZero(), SCIPsetSolVal(), SCIPsetSolVals(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsIntegral(), solveLp(), and TRUE.

Referenced by SCIPapplyProximity().

◆ setupSubproblem()

static SCIP_RETCODE setupSubproblem ( SCIP_HEURDATA heurdata,
SCIP subscip 
)
static

sets solving parameters for the subproblem created by the heuristic

Parameters
heurdataheuristic data structure
subscipcopied SCIP data structure

Definition at line 310 of file heur_proximity.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.

Referenced by SCIPapplyProximity().

◆ deleteSubproblem()

static SCIP_RETCODE deleteSubproblem ( SCIP scip,
SCIP_HEURDATA heurdata 
)
static

frees the subproblem

Parameters
scipSCIP data structure
heurdataheuristic data

Definition at line 395 of file heur_proximity.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseCons().

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), SCIPapplyProximity(), and SCIPdeleteSubproblemProximity().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecProximity  )
static

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyProximity  )
static

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

Definition at line 456 of file heur_proximity.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeProximity  )
static

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

Definition at line 470 of file heur_proximity.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitProximity  )
static

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

Definition at line 491 of file heur_proximity.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolProximity  )
static

solution process exiting method of proximity heuristic

Definition at line 520 of file heur_proximity.c.

References deleteSubproblem(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()