Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_restmaster.c File Reference

Detailed Description

Restricted Master Heuristic.

Author
Christian Puchert
Jonas Witt

Definition in file heur_restmaster.c.

#include <assert.h>
#include "heur_restmaster.h"
#include "gcg.h"
#include "pricer_gcg.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

Data Structures

struct  SCIP_HeurData
 

Macros

#define HEUR_NAME   "restmaster"
 
#define HEUR_DESC   "LNS heuristic for the master problem that fixes some master variables to zero"
 
#define HEUR_DISPCHAR   'P'
 
#define HEUR_PRIORITY   100
 
#define HEUR_FREQ   30
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP
 
#define HEUR_USESSUBSCIP   TRUE
 
#define DEFAULT_MAXNODES   5000LL
 
#define DEFAULT_MINFIXINGRATE   0.5
 
#define DEFAULT_MINIMPROVE   0.01
 
#define DEFAULT_MINNODES   500LL
 
#define DEFAULT_NODESOFS   500LL
 
#define DEFAULT_NODESQUOT   0.1
 
#define DEFAULT_USELPROWS   FALSE
 
#define DEFAULT_COPYCUTS   TRUE
 
#define DEFAULT_PBHEUR   FALSE
 
#define heurCopyRestmaster   NULL
 
#define heurExitRestmaster   NULL
 
#define heurInitsolRestmaster   NULL
 
#define heurExitsolRestmaster   NULL
 

Functions

static SCIP_RETCODE setupSubproblem (SCIP *scip, SCIP *restmaster, SCIP_VAR **restmastervars, SCIP_Real minfixingrate, SCIP_Bool uselprows, SCIP_Bool pbheur, SCIP_Bool *success)
 
static SCIP_RETCODE createNewSol (SCIP *origprob, SCIP *scip, SCIP *restmaster, SCIP_VAR **restmastervars, SCIP_HEUR *heur, SCIP_SOL *restmastersol, SCIP_Bool *success)
 
static SCIP_DECL_HEURFREE (heurFreeRestmaster)
 
static SCIP_DECL_HEURINIT (heurInitRestmaster)
 
static SCIP_DECL_HEUREXEC (heurExecRestmaster)
 
SCIP_RETCODE SCIPincludeHeurRestmaster (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "restmaster"

Definition at line 45 of file heur_restmaster.c.

◆ HEUR_DESC

#define HEUR_DESC   "LNS heuristic for the master problem that fixes some master variables to zero"

Definition at line 46 of file heur_restmaster.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'P'

Definition at line 47 of file heur_restmaster.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   100

Definition at line 48 of file heur_restmaster.c.

◆ HEUR_FREQ

#define HEUR_FREQ   30

Definition at line 49 of file heur_restmaster.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 50 of file heur_restmaster.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 51 of file heur_restmaster.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP

Definition at line 52 of file heur_restmaster.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

Definition at line 53 of file heur_restmaster.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   5000LL

maximum number of nodes to regard in the subproblem

Definition at line 55 of file heur_restmaster.c.

◆ DEFAULT_MINFIXINGRATE

#define DEFAULT_MINFIXINGRATE   0.5

minimum percentage of integer variables that have to be fixed

Definition at line 56 of file heur_restmaster.c.

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.01

factor by which restricted master should at least improve the incumbent

Definition at line 57 of file heur_restmaster.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   500LL

minimum number of nodes to regard in the subproblem

Definition at line 58 of file heur_restmaster.c.

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS   500LL

number of nodes added to the contingent of the total nodes

Definition at line 59 of file heur_restmaster.c.

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 60 of file heur_restmaster.c.

◆ DEFAULT_USELPROWS

#define DEFAULT_USELPROWS   FALSE

should subproblem be created out of the rows in the LP rows, otherwise, the copy constructor of the constraints handlers are used

Definition at line 61 of file heur_restmaster.c.

◆ DEFAULT_COPYCUTS

#define DEFAULT_COPYCUTS   TRUE

if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool of the original scip be copied to constraints of the subscip

Definition at line 63 of file heur_restmaster.c.

◆ DEFAULT_PBHEUR

#define DEFAULT_PBHEUR   FALSE

default value for using the restricted master heuristic as price-and-branch heuristic? (this changes the HEUR_TIMING to SCIP_HEURTIMING_AFTERNODE, and it changes the HEUR_FREQ to 0.

Definition at line 66 of file heur_restmaster.c.

◆ heurCopyRestmaster

#define heurCopyRestmaster   NULL

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

Definition at line 275 of file heur_restmaster.c.

◆ heurExitRestmaster

#define heurExitRestmaster   NULL

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 328 of file heur_restmaster.c.

◆ heurInitsolRestmaster

#define heurInitsolRestmaster   NULL

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

Definition at line 332 of file heur_restmaster.c.

◆ heurExitsolRestmaster

#define heurExitsolRestmaster   NULL

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

Definition at line 336 of file heur_restmaster.c.

Function Documentation

◆ setupSubproblem()

static SCIP_RETCODE setupSubproblem ( SCIP *  scip,
SCIP *  restmaster,
SCIP_VAR **  restmastervars,
SCIP_Real  minfixingrate,
SCIP_Bool  uselprows,
SCIP_Bool  pbheur,
SCIP_Bool *  success 
)
static

set up the restricted master problem by fixing master variables to zero

Parameters
scipSCIP data structure for master problem
restmasterSCIP data structure for restricted master problem
restmastervarsthe variables of the restricted
minfixingratepercentage of integer variables that have to be fixed
uselprowsshould subproblem be created out of the rows in the LP rows?
pbheuruse heuristic as price-and-branch heuristic?
successpointer to store whether the problem was created successfully

Definition at line 104 of file heur_restmaster.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ createNewSol()

static SCIP_RETCODE createNewSol ( SCIP *  origprob,
SCIP *  scip,
SCIP *  restmaster,
SCIP_VAR **  restmastervars,
SCIP_HEUR *  heur,
SCIP_SOL *  restmastersol,
SCIP_Bool *  success 
)
static

creates a new solution for the original problem by translating the solution of the restricted master problem

Parameters
origproboriginal SCIP data structure
scipSCIP data structure of master problem
restmasterSCIP structure of restricted master problem
restmastervarsthe variables of the restricted master problem
heurRestricted Master heuristic structure
restmastersolsolution of the restricted master problem
successused to store whether new solution was found or not

Definition at line 221 of file heur_restmaster.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeRestmaster  )
static

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

Definition at line 279 of file heur_restmaster.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitRestmaster  )
static

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

Definition at line 300 of file heur_restmaster.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecRestmaster  )
static

execution method of primal heuristic

Definition at line 341 of file heur_restmaster.c.

References createNewSol(), GCGmasterGetOrigprob(), and setupSubproblem().

◆ SCIPincludeHeurRestmaster()

SCIP_RETCODE SCIPincludeHeurRestmaster ( SCIP *  scip)