Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

mpec primal heuristic

Author
Felipe Serrano
Benjamin Mueller

Definition in file heur_mpec.c.

#include "blockmemshell/memory.h"
#include "scip/pub_expr.h"
#include "scip/expr_var.h"
#include "scip/expr_sum.h"
#include "scip/expr_pow.h"
#include "scip/heur_mpec.h"
#include "scip/heur_subnlp.h"
#include "scip/pub_cons.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_nlp.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.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_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include <string.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   SCIP_HEURDISPCHAR_DIVING
 
#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 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 63 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 64 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_DIVING

Definition at line 65 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -2050000

Definition at line 66 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_FREQ

#define HEUR_FREQ   50

Definition at line 67 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 68 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 69 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

Definition at line 70 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 71 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 73 of file heur_mpec.c.

Referenced by SCIPincludeHeurMpec().

◆ DEFAULT_SIGMA

#define DEFAULT_SIGMA   0.5

default regularization update factor (< 1)

Definition at line 74 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 75 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 76 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 77 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 78 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 79 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 80 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 81 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 116 of file heur_mpec.c.

References FALSE, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPcreateNlpiProblemFromNlRows(), SCIPdebugMsg, SCIPgetLowerbound(), SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPinfinity(), SCIPisInfinity(), 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 163 of file heur_mpec.c.

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

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

adds 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 188 of file heur_mpec.c.

References NULL, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProblemNlRows(), SCIPallocBufferArray, SCIPcreateExprPow(), SCIPcreateExprSum(), SCIPcreateExprVar(), SCIPcreateNlRow(), SCIPfreeBufferArray, SCIPgetNNLPNlRows(), SCIPinfinity(), SCIPreleaseExpr(), SCIPreleaseNlRow(), SCIPsnprintf(), and SCIPvarGetName().

Referenced by heurExec().

◆ getExprSize()

static int getExprSize ( SCIP_EXPR expr)
static

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

Parameters
exprexpression

Definition at line 272 of file heur_mpec.c.

References NULL, SCIPexprGetChildren(), and SCIPexprGetNChildren().

Referenced by heurExec().

◆ heurExec()

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyMpec  )
static

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

Definition at line 589 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 601 of file heur_mpec.c.

References NULL, 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 614 of file heur_mpec.c.

References NULL, 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 633 of file heur_mpec.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecMpec  )
static