Scippy

SCIP

Solving Constraint Integer Programs

heur_mpec.c File Reference

Detailed Description

mpec primal heuristic

Author
Felipe Serrano
Benjamin Mueller

Definition in file heur_mpec.c.

#include <assert.h>
#include <string.h>
#include "scip/heur_mpec.h"
#include "scip/heur_subnlp.h"
#include "nlpi/nlpi.h"

Go to the source code of this file.

Macros

#define HEUR_NAME   "mpec"
 
#define HEUR_DESC   "regularization heuristic for convex and nonconvex MINLPs"
 
#define HEUR_DISPCHAR   'W'
 
#define HEUR_PRIORITY   -2050000
 
#define HEUR_FREQ   50
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE
 
#define HEUR_USESSUBSCIP   TRUE
 
#define DEFAULT_INITTHETA   0.125
 
#define DEFAULT_SIGMA   0.5
 
#define DEFAULT_MAXITER   100
 
#define DEFAULT_MAXNLPITER   500
 
#define DEFAULT_MINGAPLEFT   0.05
 
#define DEFAULT_SUBNLPTRIGGER   1e-3
 
#define DEFAULT_MAXNLPCOST   1e+8
 
#define DEFAULT_MINIMPROVE   0.01
 
#define DEFAULT_MAXNUNSUCC   10
 

Functions

static SCIP_RETCODE createNLP (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE freeNLP (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE addRegularScholtes (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **binvars, int nbinvars, SCIP_Real theta, SCIP_Bool update)
 
static int getExprSize (SCIP_EXPR *expr)
 
static int getExprtreeSize (SCIP_EXPRTREE *tree)
 
static SCIP_RETCODE getTimeLeft (SCIP *scip, SCIP_Real *timeleft)
 
static SCIP_RETCODE heurExec (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
 
static SCIP_DECL_HEURCOPY (heurCopyMpec)
 
static SCIP_DECL_HEURFREE (heurFreeMpec)
 
static SCIP_DECL_HEURINITSOL (heurInitsolMpec)
 
static SCIP_DECL_HEUREXITSOL (heurExitsolMpec)
 
static SCIP_DECL_HEUREXEC (heurExecMpec)
 
SCIP_RETCODE SCIPincludeHeurMpec (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "mpec"

Definition at line 32 of file heur_mpec.c.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeHeurMpec().

◆ HEUR_DESC

#define HEUR_DESC   "regularization heuristic for convex and nonconvex MINLPs"

Definition at line 33 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'W'

Definition at line 34 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -2050000

Definition at line 35 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_FREQ

#define HEUR_FREQ   50

Definition at line 36 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 37 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 38 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

Definition at line 39 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

disable the heuristic in sub-SCIPs, even though it does not use any

Definition at line 40 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_INITTHETA

#define DEFAULT_INITTHETA   0.125

default initial regularization right-hand side value (< 0.25)

Definition at line 42 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_SIGMA

#define DEFAULT_SIGMA   0.5

default regularization update factor (< 1)

Definition at line 43 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_MAXITER

#define DEFAULT_MAXITER   100

default maximum number of iterations of the MPEC loop

Definition at line 44 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_MAXNLPITER

#define DEFAULT_MAXNLPITER   500

default maximum number of NLP iterations per solve

Definition at line 45 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_MINGAPLEFT

#define DEFAULT_MINGAPLEFT   0.05

default minimum amount of gap left in order to call the heuristic

Definition at line 46 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_SUBNLPTRIGGER

#define DEFAULT_SUBNLPTRIGGER   1e-3

default maximum integrality violation before triggering a sub-NLP call

Definition at line 47 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_MAXNLPCOST

#define DEFAULT_MAXNLPCOST   1e+8

default maximum cost available for solving NLPs per call of the heuristic

Definition at line 48 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.01

default factor by which heuristic should at least improve the incumbent

Definition at line 49 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_MAXNUNSUCC

#define DEFAULT_MAXNUNSUCC   10

default maximum number of consecutive calls for which the heuristic did not find an improving solution

Definition at line 50 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

Function Documentation

◆ createNLP()

static SCIP_RETCODE createNLP ( SCIP scip,
SCIP_HEURDATA heurdata 
)
static

creates the data structure for generating the current NLP relaxation

Parameters
scipSCIP data structure
heurdataheuristic data

Definition at line 85 of file heur_mpec.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPcreateNlpiProb(), SCIPdebugMsg, SCIPgetLowerbound(), SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPinfinity(), SCIPisInfinity(), SCIPnlpiCreateProblem(), SCIPsumepsilon(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ freeNLP()

static SCIP_RETCODE freeNLP ( SCIP scip,
SCIP_HEURDATA heurdata 
)
static

frees the data structures for the NLP relaxation

Parameters
scipSCIP data structure
heurdataheuristic data

Definition at line 133 of file heur_mpec.c.

References SCIP_CALL, SCIP_OKAY, SCIPhashmapFree(), and SCIPnlpiFreeProblem().

Referenced by SCIP_DECL_HEUREXEC().

◆ addRegularScholtes()

static SCIP_RETCODE addRegularScholtes ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_VAR **  binvars,
int  nbinvars,
SCIP_Real  theta,
SCIP_Bool  update 
)
static

add or updates the regularization constraints to the NLP; for a given parameter theta we add for each non-fixed binary variable z the constraint z*(1-z) <= theta; if these constraint are already present we update the theta on the right-hand side

Parameters
scipSCIP data structure
heurdataheuristic data
binvarsarray containing all non-fixed binary variables
nbinvarstotal number of non-fixed binary variables
thetaregularization parameter
updateshould the regularization constraints be added or updated?

Definition at line 158 of file heur_mpec.c.

References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNNLPNlRows(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPnlpiAddConstraints(), and SCIPnlpiChgConsSides().

Referenced by heurExec().

◆ getExprSize()

static int getExprSize ( SCIP_EXPR expr)
static

recursive helper function to count the number of nodes in a sub-tree

Parameters
exprexpression

Definition at line 241 of file heur_mpec.c.

References SCIPexprGetChildren(), and SCIPexprGetNChildren().

Referenced by getExprtreeSize().

◆ getExprtreeSize()

static int getExprtreeSize ( SCIP_EXPRTREE tree)
static

returns the number of nodes in an expression tree

Parameters
treeexpression tree

Definition at line 261 of file heur_mpec.c.

References getExprSize(), and SCIPexprtreeGetRoot().

Referenced by heurExec().

◆ getTimeLeft()

static SCIP_RETCODE getTimeLeft ( SCIP scip,
SCIP_Real timeleft 
)
static

returns the available time limit that is left

Parameters
scipSCIP data structure
timeleftpointer to store the remaining time limit

Definition at line 272 of file heur_mpec.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinfinity(), and SCIPisInfinity().

Referenced by heurExec().

◆ heurExec()

static SCIP_RETCODE heurExec ( SCIP scip,
SCIP_HEUR heur,
SCIP_HEURDATA heurdata,
SCIP_RESULT result 
)
static

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyMpec  )
static

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

Definition at line 607 of file heur_mpec.c.

References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurMpec().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeMpec  )
static

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

Definition at line 619 of file heur_mpec.c.

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

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolMpec  )
static

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

Definition at line 632 of file heur_mpec.c.

References SCIP_OKAY, SCIPfindHeur(), SCIPgetNlpis(), SCIPgetNNlpis(), and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolMpec  )
static

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

Definition at line 651 of file heur_mpec.c.

References SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecMpec  )
static