Scippy

GCG

Branch-and-Price & Column Generation for Everyone

branch_ryanfoster.c File Reference

Detailed Description

branching rule for original problem in GCG implementing the Ryan and Foster branching scheme

Author
Gerald Gamrath
Oliver Gaul

Definition in file branch_ryanfoster.c.

#include <assert.h>
#include <string.h>
#include "branch_ryanfoster.h"
#include "branch_bpstrong.h"
#include "gcg.h"
#include "relax_gcg.h"
#include "cons_masterbranch.h"
#include "cons_origbranch.h"
#include "scip/nodesel_bfs.h"
#include "scip/nodesel_dfs.h"
#include "scip/nodesel_estimate.h"
#include "scip/nodesel_hybridestim.h"
#include "scip/nodesel_restartdfs.h"
#include "scip/branch_allfullstrong.h"
#include "scip/branch_fullstrong.h"
#include "scip/branch_inference.h"
#include "scip/branch_mostinf.h"
#include "scip/branch_leastinf.h"
#include "scip/branch_pscost.h"
#include "scip/branch_random.h"
#include "scip/branch_relpscost.h"
#include "pricer_gcg.h"
#include "scip/cons_varbound.h"
#include "type_branchgcg.h"

Go to the source code of this file.

Data Structures

struct  GCG_BranchData
 

Macros

#define BRANCHRULE_NAME   "ryanfoster"
 
#define BRANCHRULE_DESC   "ryan and foster branching in generic column generation"
 
#define BRANCHRULE_PRIORITY   10
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define DEFAULT_USESTRONG   FALSE
 
#define DEFAULT_MINPHASE0OUTCANDS   10
 
#define DEFAULT_MAXPHASE0OUTCANDS   50
 
#define DEFAULT_MAXPHASE0OUTCANDSFRAC   0.7
 
#define DEFAULT_PHASE1GAPWEIGHT   0.25
 
#define DEFAULT_MINPHASE1OUTCANDS   3
 
#define DEFAULT_MAXPHASE1OUTCANDS   20
 
#define DEFAULT_MAXPHASE1OUTCANDSFRAC   0.7
 
#define DEFAULT_PHASE2GAPWEIGHT   1
 
#define branchFreeRyanfoster   NULL
 
#define branchExitRyanfoster   NULL
 
#define branchInitsolRyanfoster   NULL
 
#define branchExitsolRyanfoster   NULL
 

Functions

static SCIP_DECL_BRANCHCOPY (branchCopyRyanfoster)
 
static GCG_DECL_BRANCHACTIVEMASTER (branchActiveMasterRyanfoster)
 
static GCG_DECL_BRANCHDEACTIVEMASTER (branchDeactiveMasterRyanfoster)
 
static GCG_DECL_BRANCHPROPMASTER (branchPropMasterRyanfoster)
 
static GCG_DECL_BRANCHDATADELETE (branchDataDeleteRyanfoster)
 
static SCIP_RETCODE createChildNodesRyanfoster (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *ovar1, SCIP_VAR *ovar2, int blocknr, SCIP_Bool sameinf, SCIP_Bool differinf)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpRyanfoster)
 
static SCIP_DECL_BRANCHEXECEXT (branchExecextRyanfoster)
 
static SCIP_DECL_BRANCHEXECPS (branchExecpsRyanfoster)
 
static SCIP_DECL_BRANCHINIT (branchInitRyanfoster)
 
SCIP_RETCODE SCIPincludeBranchruleRyanfoster (SCIP *scip)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "ryanfoster"

Definition at line 62 of file branch_ryanfoster.c.

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "ryan and foster branching in generic column generation"

Definition at line 63 of file branch_ryanfoster.c.

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   10

Definition at line 64 of file branch_ryanfoster.c.

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 65 of file branch_ryanfoster.c.

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 66 of file branch_ryanfoster.c.

◆ DEFAULT_USESTRONG

#define DEFAULT_USESTRONG   FALSE

Definition at line 69 of file branch_ryanfoster.c.

◆ DEFAULT_MINPHASE0OUTCANDS

#define DEFAULT_MINPHASE0OUTCANDS   10

Definition at line 71 of file branch_ryanfoster.c.

◆ DEFAULT_MAXPHASE0OUTCANDS

#define DEFAULT_MAXPHASE0OUTCANDS   50

Definition at line 72 of file branch_ryanfoster.c.

◆ DEFAULT_MAXPHASE0OUTCANDSFRAC

#define DEFAULT_MAXPHASE0OUTCANDSFRAC   0.7

Definition at line 73 of file branch_ryanfoster.c.

◆ DEFAULT_PHASE1GAPWEIGHT

#define DEFAULT_PHASE1GAPWEIGHT   0.25

Definition at line 74 of file branch_ryanfoster.c.

◆ DEFAULT_MINPHASE1OUTCANDS

#define DEFAULT_MINPHASE1OUTCANDS   3

Definition at line 76 of file branch_ryanfoster.c.

◆ DEFAULT_MAXPHASE1OUTCANDS

#define DEFAULT_MAXPHASE1OUTCANDS   20

Definition at line 77 of file branch_ryanfoster.c.

◆ DEFAULT_MAXPHASE1OUTCANDSFRAC

#define DEFAULT_MAXPHASE1OUTCANDSFRAC   0.7

Definition at line 78 of file branch_ryanfoster.c.

◆ DEFAULT_PHASE2GAPWEIGHT

#define DEFAULT_PHASE2GAPWEIGHT   1

Definition at line 79 of file branch_ryanfoster.c.

◆ branchFreeRyanfoster

#define branchFreeRyanfoster   NULL

Definition at line 947 of file branch_ryanfoster.c.

◆ branchExitRyanfoster

#define branchExitRyanfoster   NULL

Definition at line 948 of file branch_ryanfoster.c.

◆ branchInitsolRyanfoster

#define branchInitsolRyanfoster   NULL

Definition at line 949 of file branch_ryanfoster.c.

◆ branchExitsolRyanfoster

#define branchExitsolRyanfoster   NULL

Definition at line 950 of file branch_ryanfoster.c.

Function Documentation

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyRyanfoster  )
static

copy method for master branching rule

Definition at line 102 of file branch_ryanfoster.c.

◆ GCG_DECL_BRANCHACTIVEMASTER()

static GCG_DECL_BRANCHACTIVEMASTER ( branchActiveMasterRyanfoster  )
static

◆ GCG_DECL_BRANCHDEACTIVEMASTER()

static GCG_DECL_BRANCHDEACTIVEMASTER ( branchDeactiveMasterRyanfoster  )
static

callback deactivation method

Definition at line 172 of file branch_ryanfoster.c.

References GCGgetPricingprob(), and GCGmasterGetOrigprob().

◆ GCG_DECL_BRANCHPROPMASTER()

static GCG_DECL_BRANCHPROPMASTER ( branchPropMasterRyanfoster  )
static

◆ GCG_DECL_BRANCHDATADELETE()

static GCG_DECL_BRANCHDATADELETE ( branchDataDeleteRyanfoster  )
static

callback deletion method for branching data

Definition at line 295 of file branch_ryanfoster.c.

References GCGgetPricingprob().

◆ createChildNodesRyanfoster()

static SCIP_RETCODE createChildNodesRyanfoster ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
SCIP_VAR *  ovar1,
SCIP_VAR *  ovar2,
int  blocknr,
SCIP_Bool  sameinf,
SCIP_Bool  differinf 
)
static

for the two given original variables, create two Ryan&Foster branching nodes, one for same, one for differ

Parameters
scipSCIP data structure
branchrulebranching rule
ovar1first original variable
ovar2second original variable
blocknrnumber of the pricing block
sameinfis the samebranch known to be infeasible?
differinfis the differbranch known to be infeasible?

Definition at line 322 of file branch_ryanfoster.c.

References GCG_BranchData::blocknr, GCGconsMasterbranchGetActiveCons(), GCGcreateConsMasterbranch(), GCGgetMasterprob(), GCGoriginalVarGetPricingVar(), GCGpricingVarGetNOrigvars(), GCGpricingVarGetOrigvars(), GCGvarGetBlock(), GCGvarIsOriginal(), GCGvarIsPricing(), GCG_BranchData::pricecons, GCG_BranchData::same, GCG_BranchData::var1, and GCG_BranchData::var2.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

◆ SCIP_DECL_BRANCHEXECLP()

◆ SCIP_DECL_BRANCHEXECEXT()

static SCIP_DECL_BRANCHEXECEXT ( branchExecextRyanfoster  )
static

branching execution method for relaxation solutions

Definition at line 817 of file branch_ryanfoster.c.

◆ SCIP_DECL_BRANCHEXECPS()

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitRyanfoster  )
static

initialization method of branching rule (called after problem was transformed)

Definition at line 930 of file branch_ryanfoster.c.

References GCGmasterGetOrigprob(), and GCGrelaxIncludeBranchrule().

◆ SCIPincludeBranchruleRyanfoster()