Scippy

GCG

Branch-and-Price & Column Generation for Everyone

branch_orig.c File Reference

Detailed Description

branching rule for the original problem in GCG

Author
Gerald Gamrath
Marcel Schmickerath
Christian Puchert
Jonas Witt
Oliver Gaul

Definition in file branch_orig.c.

#include <assert.h>
#include <string.h>
#include "branch_orig.h"
#include "gcg.h"
#include "branch_relpsprob.h"
#include "branch_bpstrong.h"
#include "cons_integralorig.h"
#include "cons_masterbranch.h"
#include "cons_origbranch.h"
#include "relax_gcg.h"
#include "pricer_gcg.h"
#include "type_branchgcg.h"
#include "scip/cons_linear.h"

Go to the source code of this file.

Data Structures

struct  SCIP_BranchruleData
 
struct  GCG_BranchData
 

Macros

#define BRANCHRULE_NAME   "orig"
 
#define BRANCHRULE_DESC   "branching for the original program in generic column generation"
 
#define BRANCHRULE_PRIORITY   100
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define DEFAULT_ENFORCEBYCONS   FALSE
 
#define DEFAULT_USEPSEUDO   TRUE
 
#define DEFAULT_MOSTFRAC   FALSE
 
#define DEFAULT_USERANDOM   FALSE
 
#define DEFAULT_USEPSSTRONG   FALSE
 
#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 branchDeactiveMasterOrig   NULL
 
#define branchPropMasterOrig   NULL
 

Functions

static SCIP_Bool getUniqueBlockFlagForIter (SCIP *scip, SCIP_VAR *branchcand, int iter)
 
static SCIP_RETCODE branchVar (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *branchvar, SCIP_Real solval, SCIP_Bool upinf, SCIP_Bool downinf)
 
static SCIP_Real score_function (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *var, SCIP_Real solval, SCIP_Real *score)
 
static SCIP_RETCODE branchExtern (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
 
static GCG_DECL_BRANCHACTIVEMASTER (branchActiveMasterOrig)
 
static GCG_DECL_BRANCHMASTERSOLVED (branchMasterSolvedOrig)
 
static GCG_DECL_BRANCHDATADELETE (branchDataDeleteOrig)
 
static SCIP_DECL_BRANCHFREE (branchFreeOrig)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpOrig)
 
static SCIP_DECL_BRANCHEXECEXT (branchExecextOrig)
 
static SCIP_DECL_BRANCHINIT (branchInitOrig)
 
static SCIP_DECL_BRANCHEXECPS (branchExecpsOrig)
 
SCIP_RETCODE SCIPincludeBranchruleOrig (SCIP *scip)
 
SCIP_VAR * GCGbranchOrigGetOrigvar (GCG_BRANCHDATA *branchdata)
 
GCG_BOUNDTYPE GCGbranchOrigGetBoundtype (GCG_BRANCHDATA *branchdata)
 
SCIP_Real GCGbranchOrigGetNewbound (GCG_BRANCHDATA *branchdata)
 
SCIP_RETCODE GCGbranchOrigUpdateExternBranchcands (SCIP *scip)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "orig"

Definition at line 56 of file branch_orig.c.

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "branching for the original program in generic column generation"

Definition at line 57 of file branch_orig.c.

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   100

Definition at line 58 of file branch_orig.c.

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 59 of file branch_orig.c.

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 60 of file branch_orig.c.

◆ DEFAULT_ENFORCEBYCONS

#define DEFAULT_ENFORCEBYCONS   FALSE

Definition at line 62 of file branch_orig.c.

◆ DEFAULT_USEPSEUDO

#define DEFAULT_USEPSEUDO   TRUE

Definition at line 63 of file branch_orig.c.

◆ DEFAULT_MOSTFRAC

#define DEFAULT_MOSTFRAC   FALSE

Definition at line 64 of file branch_orig.c.

◆ DEFAULT_USERANDOM

#define DEFAULT_USERANDOM   FALSE

Definition at line 65 of file branch_orig.c.

◆ DEFAULT_USEPSSTRONG

#define DEFAULT_USEPSSTRONG   FALSE

Definition at line 66 of file branch_orig.c.

◆ DEFAULT_USESTRONG

#define DEFAULT_USESTRONG   FALSE

Definition at line 69 of file branch_orig.c.

◆ DEFAULT_MINPHASE0OUTCANDS

#define DEFAULT_MINPHASE0OUTCANDS   10

Definition at line 71 of file branch_orig.c.

◆ DEFAULT_MAXPHASE0OUTCANDS

#define DEFAULT_MAXPHASE0OUTCANDS   50

Definition at line 72 of file branch_orig.c.

◆ DEFAULT_MAXPHASE0OUTCANDSFRAC

#define DEFAULT_MAXPHASE0OUTCANDSFRAC   0.7

Definition at line 73 of file branch_orig.c.

◆ DEFAULT_PHASE1GAPWEIGHT

#define DEFAULT_PHASE1GAPWEIGHT   0.25

Definition at line 74 of file branch_orig.c.

◆ DEFAULT_MINPHASE1OUTCANDS

#define DEFAULT_MINPHASE1OUTCANDS   3

Definition at line 76 of file branch_orig.c.

◆ DEFAULT_MAXPHASE1OUTCANDS

#define DEFAULT_MAXPHASE1OUTCANDS   20

Definition at line 77 of file branch_orig.c.

◆ DEFAULT_MAXPHASE1OUTCANDSFRAC

#define DEFAULT_MAXPHASE1OUTCANDSFRAC   0.7

Definition at line 78 of file branch_orig.c.

◆ DEFAULT_PHASE2GAPWEIGHT

#define DEFAULT_PHASE2GAPWEIGHT   1

Definition at line 79 of file branch_orig.c.

◆ branchDeactiveMasterOrig

#define branchDeactiveMasterOrig   NULL

Definition at line 637 of file branch_orig.c.

◆ branchPropMasterOrig

#define branchPropMasterOrig   NULL

Definition at line 638 of file branch_orig.c.

Function Documentation

◆ getUniqueBlockFlagForIter()

static SCIP_Bool getUniqueBlockFlagForIter ( SCIP *  scip,
SCIP_VAR *  branchcand,
int  iter 
)
static

◆ branchVar()

static SCIP_RETCODE branchVar ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
SCIP_VAR *  branchvar,
SCIP_Real  solval,
SCIP_Bool  upinf,
SCIP_Bool  downinf 
)
static

branches on a integer variable x if solution value x' is fractional, two child nodes will be created (x <= floor(x'), x >= ceil(x')), if solution value is integral, the bounds of x are finite, then two child nodes will be created (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)), otherwise (up to) three child nodes will be created (x <= x'-1, x == x', x >= x'+1) if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes will be created (the third one would be infeasible anyway)

Parameters
scipSCIP data structure
branchrulepointer to the original variable branching rule
branchvarvariable to branch on
solvalvalue of the variable in the current solution
upinfhave we seen during strong branching that the upbranch is infeasible?
downinfhave we seen during strong branching that the downbranch is infeasible?

Definition at line 186 of file branch_orig.c.

References GCG_BranchData::boundtype, BRANCHRULE_NAME, GCG_BranchData::cons, GCG_BOUNDTYPE_FIXED, GCG_BOUNDTYPE_LOWER, GCG_BOUNDTYPE_UPPER, GCGconsMasterbranchGetActiveCons(), GCGcreateConsMasterbranch(), GCGgetMasterprob(), GCG_BranchData::newbound, GCG_BranchData::oldbound, GCG_BranchData::olddualbound, GCG_BranchData::oldvalue, and GCG_BranchData::origvar.

Referenced by branchExtern(), and SCIP_DECL_BRANCHEXECPS().

◆ score_function()

static SCIP_Real score_function ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
SCIP_VAR *  var,
SCIP_Real  solval,
SCIP_Real *  score 
)
static

Definition at line 472 of file branch_orig.c.

Referenced by branchExtern().

◆ branchExtern()

static SCIP_RETCODE branchExtern ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
SCIP_RESULT *  result 
)
static

branching method for relaxation solutions

Parameters
scipSCIP data structure
branchrulepointer to the original variable branching rule
resultpointer to store the result of the branching call

Definition at line 503 of file branch_orig.c.

References BRANCHRULE_NAME, branchVar(), GCGbranchSelectCandidateStrongBranchingOrig(), GCGgetMasterprob(), getUniqueBlockFlagForIter(), SCIPgetRelpsprobBranchVar(), and score_function().

Referenced by SCIP_DECL_BRANCHEXECEXT(), and SCIP_DECL_BRANCHEXECLP().

◆ GCG_DECL_BRANCHACTIVEMASTER()

static GCG_DECL_BRANCHACTIVEMASTER ( branchActiveMasterOrig  )
static

callback activation method

Definition at line 642 of file branch_orig.c.

References GCG_BOUNDTYPE_LOWER, GCG_BOUNDTYPE_UPPER, GCGmasterGetOrigprob(), and GCGrelaxTransOrigToMasterCons().

◆ GCG_DECL_BRANCHMASTERSOLVED()

static GCG_DECL_BRANCHMASTERSOLVED ( branchMasterSolvedOrig  )
static

callback solved method

Definition at line 680 of file branch_orig.c.

References GCG_BOUNDTYPE_LOWER, GCG_BOUNDTYPE_UPPER, GCGgetMasterprob(), and GCGisOriginal().

◆ GCG_DECL_BRANCHDATADELETE()

static GCG_DECL_BRANCHDATADELETE ( branchDataDeleteOrig  )
static

callback deletion method for branching data

Definition at line 704 of file branch_orig.c.

References GCG_BOUNDTYPE_LOWER, and GCG_BOUNDTYPE_UPPER.

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeOrig  )
static

Definition at line 731 of file branch_orig.c.

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpOrig  )
static

branching execution method for fractional LP solutions

Definition at line 749 of file branch_orig.c.

References branchExtern(), GCGcurrentNodeIsGeneric(), GCGmasterGetOrigprob(), and GCGrelaxIsOrigSolFeasible().

◆ SCIP_DECL_BRANCHEXECEXT()

static SCIP_DECL_BRANCHEXECEXT ( branchExecextOrig  )
static

branching execution method for relaxation solutions

Definition at line 784 of file branch_orig.c.

References branchExtern(), GCGcurrentNodeIsGeneric(), GCGmasterGetOrigprob(), and GCGrelaxIsOrigSolFeasible().

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitOrig  )
static

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

Definition at line 814 of file branch_orig.c.

References branchDeactiveMasterOrig, branchPropMasterOrig, GCGmasterGetOrigprob(), and GCGrelaxIncludeBranchrule().

◆ SCIP_DECL_BRANCHEXECPS()

static SCIP_DECL_BRANCHEXECPS ( branchExecpsOrig  )
static

◆ SCIPincludeBranchruleOrig()

◆ GCGbranchOrigGetOrigvar()

SCIP_VAR* GCGbranchOrigGetOrigvar ( GCG_BRANCHDATA branchdata)

get the original variable on which the branching was performed

Parameters
branchdatabranching data

Definition at line 1088 of file branch_orig.c.

References GCG_BranchData::origvar.

Referenced by applyOriginalBranching().

◆ GCGbranchOrigGetBoundtype()

GCG_BOUNDTYPE GCGbranchOrigGetBoundtype ( GCG_BRANCHDATA branchdata)

get the type of the new bound which resulted of the performed branching

Parameters
branchdatabranching data

Definition at line 1098 of file branch_orig.c.

References GCG_BranchData::boundtype.

Referenced by applyOriginalBranching().

◆ GCGbranchOrigGetNewbound()

SCIP_Real GCGbranchOrigGetNewbound ( GCG_BRANCHDATA branchdata)

get the new bound which resulted of the performed branching

Parameters
branchdatabranching data

Definition at line 1108 of file branch_orig.c.

References GCG_BranchData::newbound.

Referenced by applyOriginalBranching().

◆ GCGbranchOrigUpdateExternBranchcands()

SCIP_RETCODE GCGbranchOrigUpdateExternBranchcands ( SCIP *  scip)

updates extern branching candidates before branching

Parameters
scipSCIP data structure

Definition at line 1118 of file branch_orig.c.

References GCGisOriginal().