Detailed Description
branching rule for the original problem in GCG
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 |
Definition at line 120 of file branch_orig.c.
References GCGgetNIdenticalBlocks(), GCGlinkingVarGetBlocks(), GCGlinkingVarGetNBlocks(), GCGoriginalVarIsLinking(), GCGvarGetBlock(), and GCGvarIsOriginal().
Referenced by branchExtern().
◆ branchVar()
|
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
-
scip SCIP data structure branchrule pointer to the original variable branching rule branchvar variable to branch on solval value of the variable in the current solution upinf have we seen during strong branching that the upbranch is infeasible? downinf have 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 |
Definition at line 472 of file branch_orig.c.
Referenced by branchExtern().
◆ branchExtern()
|
static |
branching method for relaxation solutions
- Parameters
-
scip SCIP data structure branchrule pointer to the original variable branching rule result pointer 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 |
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 |
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 |
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 |
Definition at line 731 of file branch_orig.c.
◆ SCIP_DECL_BRANCHEXECLP()
|
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 |
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 |
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 |
branching execution method for not completely fixed pseudo solutions
Definition at line 832 of file branch_orig.c.
References BRANCHRULE_NAME, branchVar(), GCGcurrentNodeIsGeneric(), GCGgetNIdenticalBlocks(), GCGlinkingVarGetBlocks(), GCGlinkingVarGetNBlocks(), GCGmasterGetOrigprob(), GCGoriginalVarIsLinking(), GCGvarGetBlock(), and GCGvarIsOriginal().
◆ SCIPincludeBranchruleOrig()
SCIP_RETCODE SCIPincludeBranchruleOrig | ( | SCIP * | scip | ) |
creates the branching on original variable branching rule and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 993 of file branch_orig.c.
References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_ENFORCEBYCONS, DEFAULT_MAXPHASE0OUTCANDS, DEFAULT_MAXPHASE0OUTCANDSFRAC, DEFAULT_MAXPHASE1OUTCANDS, DEFAULT_MAXPHASE1OUTCANDSFRAC, DEFAULT_MINPHASE0OUTCANDS, DEFAULT_MINPHASE1OUTCANDS, DEFAULT_MOSTFRAC, DEFAULT_PHASE1GAPWEIGHT, DEFAULT_PHASE2GAPWEIGHT, DEFAULT_USEPSEUDO, DEFAULT_USEPSSTRONG, DEFAULT_USESTRONG, GCGconsIntegralorigAddBranchrule(), and GCGmasterGetOrigprob().
Referenced by GCGincludeMasterPlugins().
◆ GCGbranchOrigGetOrigvar()
SCIP_VAR* GCGbranchOrigGetOrigvar | ( | GCG_BRANCHDATA * | branchdata | ) |
get the original variable on which the branching was performed
- Parameters
-
branchdata branching 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
-
branchdata branching 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
-
branchdata branching 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
-
scip SCIP data structure
Definition at line 1118 of file branch_orig.c.
References GCGisOriginal().