branch_generic.c File Reference

Detailed Description

branching rule based on vanderbeck's generic branching scheme

Author
Marcel Schmickerath
Martin Bergner
Jonas Witt

Definition in file branch_generic.c.

#include "branch_generic.h"
#include "relax_gcg.h"
#include "cons_masterbranch.h"
#include "cons_origbranch.h"
#include "pricer_gcg.h"
#include "scip/cons_linear.h"
#include "type_branchgcg.h"
#include "gcg.h"
#include "cons_integralorig.h"
#include "gcgsort.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 <assert.h>
#include <string.h>

Go to the source code of this file.

Macros

#define BRANCHRULE_NAME   "generic"
 
#define BRANCHRULE_DESC   "generic branching rule by Vanderbeck"
 
#define BRANCHRULE_PRIORITY   -100
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define EVENTHDLR_NAME   "genericbranchvaradd"
 
#define EVENTHDLR_DESC   "event handler for adding a new generated mastervar into the right branching constraints by using Vanderbecks generic branching scheme"
 
#define branchFreeGeneric   NULL
 
#define branchExitGeneric   NULL
 
#define branchInitsolGeneric   NULL
 
#define branchExitsolGeneric   NULL
 

Typedefs

typedef struct GCG_Record GCG_RECORD
 

Functions

static SCIP_Real getGeneratorEntry (SCIP_VAR *mastervar, SCIP_VAR *origvar)
 
static SCIP_RETCODE addVarToMasterbranch (SCIP *scip, SCIP_VAR *mastervar, GCG_BRANCHDATA *branchdata, SCIP_Bool *added)
 
static SCIP_RETCODE createDirectBranchingCons (SCIP *scip, SCIP_NODE *node, GCG_BRANCHDATA *branchdata)
 
static SCIP_RETCODE createBranchingCons (SCIP *scip, SCIP_NODE *node, GCG_BRANCHDATA *branchdata)
 
static SCIP_DECL_EVENTINITSOL (eventInitsolGenericbranchvaradd)
 
static SCIP_DECL_EVENTEXITSOL (eventExitsolGenericbranchvaradd)
 
static SCIP_DECL_EVENTEXEC (eventExecGenericbranchvaradd)
 
static SCIP_RETCODE InitIndexSet (SCIP *scip, SCIP_VAR **F, int Fsize, SCIP_VAR ***IndexSet, int *IndexSetSize)
 
static SCIP_Real GetMedian (SCIP *scip, SCIP_Real *array, int arraysize, SCIP_Real min)
 
static GCG_DECL_SORTPTRCOMP (ptrcomp)
 
static SCIP_RETCODE LexicographicSort (SCIP *scip, GCG_STRIP **array, int arraysize)
 
static int ILOcomp (SCIP *scip, SCIP_VAR *mastervar1, SCIP_VAR *mastervar2, GCG_COMPSEQUENCE **C, int NBoundsequences, int *sequencesizes, int p)
 
static SCIP_DECL_SORTPTRCOMP (ptrilocomp)
 
static SCIP_RETCODE InducedLexicographicSort (SCIP *scip, GCG_STRIP **array, int arraysize, GCG_COMPSEQUENCE **C, int NBoundsequences, int *sequencesizes)
 
static SCIP_RETCODE partition (SCIP *scip, SCIP_VAR **J, int *Jsize, SCIP_Longint *priority, SCIP_VAR **F, int Fsize, SCIP_VAR **origvar, SCIP_Real *median)
 
static SCIP_RETCODE addToRecord (SCIP *scip, GCG_RECORD *record, GCG_COMPSEQUENCE *S, int Ssize)
 
static SCIP_RETCODE Separate (SCIP *scip, SCIP_VAR **F, int Fsize, SCIP_VAR **IndexSet, int IndexSetSize, GCG_COMPSEQUENCE *S, int Ssize, GCG_RECORD *record)
 
static SCIP_RETCODE ChoseS (SCIP *scip, GCG_RECORD **record, GCG_COMPSEQUENCE **S, int *Ssize)
 
static int computeNewSequence (int Csize, int p, SCIP_VAR *origvar, int *sequencesizes, GCG_COMPSEQUENCE **C, GCG_COMPSEQUENCE **CopyC, int *newsequencesizes, GCG_COMPSENSE sense)
 
static double computeAlpha (SCIP *scip, int Fsize, GCG_COMPSENSE isense, double ivalue, SCIP_VAR *origvar, SCIP_VAR **F)
 
static SCIP_RETCODE Explore (SCIP *scip, GCG_COMPSEQUENCE **C, int Csize, int *sequencesizes, int p, SCIP_VAR **F, int Fsize, SCIP_VAR **IndexSet, int IndexSetSize, GCG_COMPSEQUENCE **S, int *Ssize, GCG_RECORD *record)
 
static SCIP_RETCODE ChooseSeparateMethod (SCIP *scip, SCIP_VAR **F, int Fsize, GCG_COMPSEQUENCE **S, int *Ssize, GCG_COMPSEQUENCE **C, int Csize, int *CompSizes, int blocknr, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result, int **checkedblocks, int *ncheckedblocks, GCG_STRIP ****checkedblockssortstrips, int **checkedblocksnsortstrips)
 
static GCG_DECL_BRANCHDATADELETE (branchDataDeleteGeneric)
 
static SCIP_Bool checkchildconsS (SCIP *scip, SCIP_Real lhs, GCG_COMPSEQUENCE *childS, int childSsize, SCIP_CONS *parentcons, int childBlocknr)
 
static SCIP_Bool pruneChildNodeByDominanceGeneric (SCIP *scip, SCIP_Real lhs, GCG_COMPSEQUENCE *childS, int childSsize, SCIP_CONS *masterbranchcons, int childBlocknr)
 
static SCIP_RETCODE initNodeBranchdata (SCIP *scip, GCG_BRANCHDATA **nodebranchdata, int blocknr)
 
static SCIP_RETCODE createChildNodesGeneric (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_COMPSEQUENCE *S, int Ssize, int blocknr, SCIP_CONS *masterbranchcons, SCIP_RESULT *result)
 
static SCIP_RETCODE branchDirectlyOnMastervar (SCIP *scip, SCIP_VAR *mastervar, SCIP_BRANCHRULE *branchrule)
 
SCIP_RETCODE GCGbranchGenericInitbranch (SCIP *masterscip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result, int **checkedblocks, int *ncheckedblocks, GCG_STRIP ****checkedblockssortstrips, int **checkedblocksnsortstrips)
 
static SCIP_RETCODE GCGincludeMasterCopyPlugins (SCIP *scip)
 
static SCIP_DECL_BRANCHCOPY (branchCopyGeneric)
 
static GCG_DECL_BRANCHACTIVEMASTER (branchActiveMasterGeneric)
 
static GCG_DECL_BRANCHDEACTIVEMASTER (branchDeactiveMasterGeneric)
 
static GCG_DECL_BRANCHPROPMASTER (branchPropMasterGeneric)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpGeneric)
 
static SCIP_DECL_BRANCHEXECEXT (branchExecextGeneric)
 
static SCIP_DECL_BRANCHEXECPS (branchExecpsGeneric)
 
static SCIP_DECL_BRANCHINIT (branchInitGeneric)
 
SCIP_RETCODE SCIPincludeBranchruleGeneric (SCIP *scip)
 
SCIP_RETCODE GCGbranchGenericCreateBranchdata (SCIP *scip, GCG_BRANCHDATA **branchdata)
 
GCG_COMPSEQUENCEGCGbranchGenericBranchdataGetConsS (GCG_BRANCHDATA *branchdata)
 
int GCGbranchGenericBranchdataGetConsSsize (GCG_BRANCHDATA *branchdata)
 
int GCGbranchGenericBranchdataGetConsblocknr (GCG_BRANCHDATA *branchdata)
 
SCIP_CONS * GCGbranchGenericBranchdataGetMastercons (GCG_BRANCHDATA *branchdata)
 
SCIP_Bool GCGisBranchruleGeneric (SCIP_BRANCHRULE *branchrule)
 

Macro Definition Documentation

#define branchExitGeneric   NULL

Definition at line 108 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define branchExitsolGeneric   NULL

Definition at line 110 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define branchFreeGeneric   NULL

Definition at line 107 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define branchInitsolGeneric   NULL

Definition at line 109 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define BRANCHRULE_DESC   "generic branching rule by Vanderbeck"

Definition at line 70 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 73 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 72 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define BRANCHRULE_NAME   "generic"
#define BRANCHRULE_PRIORITY   -100

Definition at line 71 of file branch_generic.c.

Referenced by SCIPincludeBranchruleGeneric().

#define EVENTHDLR_DESC   "event handler for adding a new generated mastervar into the right branching constraints by using Vanderbecks generic branching scheme"

Typedef Documentation

typedef struct GCG_Record GCG_RECORD

Definition at line 100 of file branch_generic.c.

Function Documentation

static SCIP_RETCODE addToRecord ( SCIP *  scip,
GCG_RECORD record,
GCG_COMPSEQUENCE S,
int  Ssize 
)
static

add identified sequence to record

Parameters
scipSCIP data structure
recordrecord of identified sequences
Sbound restriction sequence
Ssizesize of bound restriction sequence

Definition at line 907 of file branch_generic.c.

References ComponentBoundSequence::bound, ComponentBoundSequence::component, GCG_Record::record, GCG_Record::recordsize, ComponentBoundSequence::sense, and GCG_Record::sequencesizes.

Referenced by Explore(), and Separate().

static SCIP_RETCODE addVarToMasterbranch ( SCIP *  scip,
SCIP_VAR *  mastervar,
GCG_BRANCHDATA branchdata,
SCIP_Bool *  added 
)
static

adds a variable to a branching constraint

Parameters
scipSCIP data structure
mastervarthe variable to add
branchdatabranching data structure where the variable should be added
addedwhether the variable was added

Definition at line 146 of file branch_generic.c.

References GCG_COMPSENSE_GE, GCGbranchGenericBranchdataGetConsblocknr(), GCGbranchGenericBranchdataGetConsS(), GCGbranchGenericBranchdataGetConsSsize(), GCGbranchGenericBranchdataGetMastercons(), GCGisMasterVarInBlock(), GCGvarGetBlock(), and getGeneratorEntry().

Referenced by GCG_DECL_BRANCHACTIVEMASTER(), and SCIP_DECL_EVENTEXEC().

static SCIP_RETCODE branchDirectlyOnMastervar ( SCIP *  scip,
SCIP_VAR *  mastervar,
SCIP_BRANCHRULE *  branchrule 
)
static
static SCIP_Bool checkchildconsS ( SCIP *  scip,
SCIP_Real  lhs,
GCG_COMPSEQUENCE childS,
int  childSsize,
SCIP_CONS *  parentcons,
int  childBlocknr 
)
static

check method for pruning ChildS directly on childnodes retrun TRUE if node is pruned

Parameters
scipSCIP data structure
lhslhs for childnode which is checkes to be pruned
childScomponent bound sequence defining the childnode
childSsizesize of component bound sequence
parentconsconstraint of parent node in B&B tree
childBlocknrnumber of the block for the child node

Definition at line 1926 of file branch_generic.c.

References ComponentBoundSequence::bound, ComponentBoundSequence::component, GCG_BranchData::consblocknr, GCG_BranchData::consS, GCG_BranchData::consSsize, GCGconsMasterbranchGetBranchdata(), GCGconsMasterbranchGetBranchrule(), GCGconsMasterbranchGetChildcons(), GCGconsMasterbranchGetNChildconss(), GCG_BranchData::lhs, GCG_BranchData::same, and ComponentBoundSequence::sense.

Referenced by pruneChildNodeByDominanceGeneric().

static SCIP_RETCODE ChooseSeparateMethod ( SCIP *  scip,
SCIP_VAR **  F,
int  Fsize,
GCG_COMPSEQUENCE **  S,
int *  Ssize,
GCG_COMPSEQUENCE **  C,
int  Csize,
int *  CompSizes,
int  blocknr,
SCIP_BRANCHRULE *  branchrule,
SCIP_RESULT *  result,
int **  checkedblocks,
int *  ncheckedblocks,
GCG_STRIP ****  checkedblockssortstrips,
int **  checkedblocksnsortstrips 
)
static

callup method for seperate decides whether Separate or Explore should be done

Parameters
scipSCIP data structure
Fstrip of fractional columns
Fsizesize of the strips
Sarray of existing bound sequences
Ssizesize of existing bound sequences
Carray of component bounds sequences
Csizenumber of component bounds sequences
CompSizesarray of sizes of component bounds sequences
blocknrid of the pricing problem (or block) in which we want to branch
branchrulebranching rule
resultpointer to store the result of the branching call
checkedblocksarray to store which blocks have been checked
ncheckedblocksnumber of blocks that have beend checked
checkedblockssortstripssorted strips of checked blocks
checkedblocksnsortstripssize of the strips

Definition at line 1703 of file branch_generic.c.

References GCG_BranchData::blocknr, GCG_Strip::C, ChoseS(), GCG_Strip::Csize, Explore(), GCGbranchGenericInitbranch(), GCGgetMasterprob(), GCGgetNPricingprobs(), GCGisMasterVarInBlock(), InducedLexicographicSort(), InitIndexSet(), GCG_Strip::mastervar, GCG_Record::record, GCG_Record::recordsize, GCG_Strip::scip, Separate(), GCG_Strip::sequencesizes, and GCG_Record::sequencesizes.

Referenced by GCGbranchGenericInitbranch().

static SCIP_RETCODE ChoseS ( SCIP *  scip,
GCG_RECORD **  record,
GCG_COMPSEQUENCE **  S,
int *  Ssize 
)
static

choose a component bound sequence to create branching

Parameters
scipSCIP data structure
recordcandidate of bound sequences
Spointer to return chosen bound sequence
Ssizesize of the chosen bound sequence

Definition at line 1254 of file branch_generic.c.

Referenced by ChooseSeparateMethod().

static double computeAlpha ( SCIP *  scip,
int  Fsize,
GCG_COMPSENSE  isense,
double  ivalue,
SCIP_VAR *  origvar,
SCIP_VAR **  F 
)
static

auxilary function to compute alpha for given index

Parameters
scipSCIP data structure
Fsizesize of F
isensesense of the bound for origvar
ivaluevalue of the bound for origvar
origvarindex of the variable
Fcurrent fractional mastervars

Definition at line 1358 of file branch_generic.c.

References GCG_COMPSENSE_GE, GCG_COMPSENSE_LT, GCGgetMasterprob(), and getGeneratorEntry().

Referenced by Explore().

static int computeNewSequence ( int  Csize,
int  p,
SCIP_VAR *  origvar,
int *  sequencesizes,
GCG_COMPSEQUENCE **  C,
GCG_COMPSEQUENCE **  CopyC,
int *  newsequencesizes,
GCG_COMPSENSE  sense 
)
static

updates the new set of sequences C in CopyC and the corresponding size array newsequencesizes returns the size of CopyC

Parameters
Csizesize of the sequence
pindex of node
origvaranother index generatorentry
sequencesizessize of the sequences
Coriginal sequence
CopyCnew sequence
newsequencesizesoutput parameter for the new sequence
sensesense of the comparison

Definition at line 1326 of file branch_generic.c.

References GCG_BranchData::Csize.

Referenced by Explore().

static SCIP_RETCODE createBranchingCons ( SCIP *  scip,
SCIP_NODE *  node,
GCG_BRANCHDATA branchdata 
)
static

creates the constraint for branching directly on a master variable

Parameters
scipSCIP data structure
nodenode to add constraint
branchdatabranching data structure

Definition at line 239 of file branch_generic.c.

References GCG_BranchData::consSsize, GCG_BranchData::lhs, and GCG_BranchData::mastercons.

Referenced by createChildNodesGeneric().

static SCIP_RETCODE createChildNodesGeneric ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_COMPSEQUENCE S,
int  Ssize,
int  blocknr,
SCIP_CONS *  masterbranchcons,
SCIP_RESULT *  result 
)
static

for given component bound sequence S, create |S|+1 Vanderbeck branching nodes

Parameters
scipSCIP data structure
branchrulebranching rule
SComponent Bound Sequence defining the nodes
Ssizesize of S
blocknrnumber of the block
masterbranchconscurrent masterbranchcons
resultpointer to store the result of the branching call

Definition at line 2058 of file branch_generic.c.

References ComponentBoundSequence::bound, ComponentBoundSequence::component, GCG_BranchData::consS, GCG_BranchData::consSsize, createBranchingCons(), GCG_COMPSENSE_GE, GCG_COMPSENSE_LT, GCGconsMasterbranchGetActiveCons(), GCGcreateConsMasterbranch(), GCGgetMasterprob(), GCGgetNIdenticalBlocks(), GCGisMasterVarInBlock(), getGeneratorEntry(), initNodeBranchdata(), GCG_BranchData::lhs, pruneChildNodeByDominanceGeneric(), and ComponentBoundSequence::sense.

Referenced by GCGbranchGenericInitbranch().

static SCIP_RETCODE createDirectBranchingCons ( SCIP *  scip,
SCIP_NODE *  node,
GCG_BRANCHDATA branchdata 
)
static

creates the constraint for branching directly on a master variable

Parameters
scipSCIP data structure
nodenode to add constraint
branchdatabranching data structure

Definition at line 205 of file branch_generic.c.

References ComponentBoundSequence::bound, ComponentBoundSequence::component, GCG_BranchData::consblocknr, GCG_BranchData::consS, GCG_BranchData::consSsize, GCG_COMPSENSE_GE, GCGvarIsMaster(), GCG_BranchData::mastercons, and ComponentBoundSequence::sense.

Referenced by branchDirectlyOnMastervar().

static SCIP_RETCODE Explore ( SCIP *  scip,
GCG_COMPSEQUENCE **  C,
int  Csize,
int *  sequencesizes,
int  p,
SCIP_VAR **  F,
int  Fsize,
SCIP_VAR **  IndexSet,
int  IndexSetSize,
GCG_COMPSEQUENCE **  S,
int *  Ssize,
GCG_RECORD record 
)
static

separation at a node other than the root node

Parameters
scipSCIP data structure
Carray of component bounds sequences
Csizenumber of component bounds sequences
sequencesizesarray of sizes of component bounds sequences
pdepth of recursive call
Fstrip of fractional columns
Fsizesize of the strips
IndexSetarray of original variables which belong to the fractional master columns
IndexSetSizenumber of original variables which belong to fractional master columns. Note that IndexSetSize >= Fsize
Scomponent sequences
Ssizelength of component sequences
recordarray of sets of component bounds which we might use for separation

Definition at line 1388 of file branch_generic.c.

References addToRecord(), ComponentBoundSequence::bound, ComponentBoundSequence::component, computeAlpha(), computeNewSequence(), GCG_BranchData::Csize, GCG_COMPSENSE_GE, GCG_COMPSENSE_LT, GCGgetMasterprob(), getGeneratorEntry(), GCG_BranchData::origvar, ComponentBoundSequence::sense, and Separate().

Referenced by ChooseSeparateMethod().

static GCG_DECL_BRANCHACTIVEMASTER ( branchActiveMasterGeneric  )
static

callback activation method

Definition at line 2772 of file branch_generic.c.

References addVarToMasterbranch(), GCGisMaster(), and GCGvarIsMaster().

static GCG_DECL_BRANCHDATADELETE ( branchDataDeleteGeneric  )
static

callback deletion method for branching data

Definition at line 1881 of file branch_generic.c.

References GCGgetMasterprob().

static GCG_DECL_BRANCHDEACTIVEMASTER ( branchDeactiveMasterGeneric  )
static

callback deactivation method

Definition at line 2813 of file branch_generic.c.

References GCGisMaster().

static GCG_DECL_BRANCHPROPMASTER ( branchPropMasterGeneric  )
static

callback propagation method

Definition at line 2831 of file branch_generic.c.

static GCG_DECL_SORTPTRCOMP ( ptrcomp  )
static

comparefunction for lexicographical sort

Definition at line 526 of file branch_generic.c.

References GCGmasterVarIsLinking(), GCGvarGetBlock(), getGeneratorEntry(), and GCG_Strip::mastervar.

int GCGbranchGenericBranchdataGetConsblocknr ( GCG_BRANCHDATA branchdata)

get id of pricing problem (or block) to which the constraint belongs

Parameters
branchdatabranching data

Definition at line 3035 of file branch_generic.c.

References GCG_BranchData::consblocknr.

Referenced by addVarToMasterbranch(), and SCIP_DECL_EVENTEXEC().

GCG_COMPSEQUENCE* GCGbranchGenericBranchdataGetConsS ( GCG_BRANCHDATA branchdata)

get component bound sequence

Parameters
branchdatabranching data

Definition at line 3017 of file branch_generic.c.

References GCG_BranchData::consS.

Referenced by addVarToMasterbranch(), ObjPricerGcg::createNewMasterVarFromGcgCol(), and SCIP_DECL_EVENTEXEC().

int GCGbranchGenericBranchdataGetConsSsize ( GCG_BRANCHDATA branchdata)

get size of component bound sequence

Parameters
branchdatabranching data

Definition at line 3026 of file branch_generic.c.

References GCG_BranchData::consSsize.

Referenced by addVarToMasterbranch(), ObjPricerGcg::createNewMasterVarFromGcgCol(), and SCIP_DECL_EVENTEXEC().

SCIP_CONS* GCGbranchGenericBranchdataGetMastercons ( GCG_BRANCHDATA branchdata)

get master constraint

Parameters
branchdatabranching data

Definition at line 3044 of file branch_generic.c.

References GCG_BranchData::mastercons.

Referenced by addVarToMasterbranch().

SCIP_RETCODE GCGbranchGenericCreateBranchdata ( SCIP *  scip,
GCG_BRANCHDATA **  branchdata 
)

initializes branchdata

Parameters
scipSCIP data structure
branchdatabranching data to initialize

Definition at line 2997 of file branch_generic.c.

Referenced by GCGcreateConsOrigbranch().

SCIP_RETCODE GCGbranchGenericInitbranch ( SCIP *  masterscip,
SCIP_BRANCHRULE *  branchrule,
SCIP_RESULT *  result,
int **  checkedblocks,
int *  ncheckedblocks,
GCG_STRIP ****  checkedblockssortstrips,
int **  checkedblocksnsortstrips 
)
static SCIP_RETCODE GCGincludeMasterCopyPlugins ( SCIP *  scip)
static
Parameters
scipSCIP data structure

Definition at line 2741 of file branch_generic.c.

Referenced by SCIP_DECL_BRANCHCOPY().

SCIP_Bool GCGisBranchruleGeneric ( SCIP_BRANCHRULE *  branchrule)

returns true when the branch rule is the generic branchrule

Parameters
branchrulebranchrule to check

Definition at line 3053 of file branch_generic.c.

References BRANCHRULE_NAME.

Referenced by ObjPricerGcg::pricingLoop(), and SCIP_DECL_EVENTEXEC().

static SCIP_Real getGeneratorEntry ( SCIP_VAR *  mastervar,
SCIP_VAR *  origvar 
)
static

computes the generator of mastervar for the entry in origvar

Returns
entry of the generator corresponding to origvar
Parameters
mastervarcurrent mastervariable
origvarcorresponding origvar

Definition at line 116 of file branch_generic.c.

References GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), and GCGmasterVarGetOrigvars().

Referenced by addVarToMasterbranch(), computeAlpha(), createChildNodesGeneric(), Explore(), GCG_DECL_SORTPTRCOMP(), ILOcomp(), partition(), and Separate().

static SCIP_Real GetMedian ( SCIP *  scip,
SCIP_Real *  array,
int  arraysize,
SCIP_Real  min 
)
static

method for calculating the median over all fractional components values using the quickselect algorithm (or a variant of it)

This method will change the array

Returns
median or if the median is the minimum return ceil(arithm middle)
Parameters
scipSCIP data structure
arrayarray to find the median in (will be destroyed)
arraysizesize of the array
minminimum of array

Definition at line 457 of file branch_generic.c.

Referenced by partition(), and Separate().

static int ILOcomp ( SCIP *  scip,
SCIP_VAR *  mastervar1,
SCIP_VAR *  mastervar2,
GCG_COMPSEQUENCE **  C,
int  NBoundsequences,
int *  sequencesizes,
int  p 
)
static

compare function for ILO: returns 1 if bd1 < bd2 else -1 with respect to bound sequence

Parameters
scipSCIP data structure
mastervar1first strip
mastervar2second strip
Ccomponent bound sequence to compare with
NBoundsequencessize of the bound sequence
sequencesizessizes of the bound sequences
pcurrent depth in C

Definition at line 599 of file branch_generic.c.

References ComponentBoundSequence::bound, GCG_Strip::C, ComponentBoundSequence::component, GCG_Strip::Csize, GCG_COMPSENSE_GE, getGeneratorEntry(), GCG_Strip::mastervar, GCG_BranchData::origvar, GCG_Strip::scip, and GCG_Strip::sequencesizes.

Referenced by SCIP_DECL_SORTPTRCOMP().

static SCIP_RETCODE InducedLexicographicSort ( SCIP *  scip,
GCG_STRIP **  array,
int  arraysize,
GCG_COMPSEQUENCE **  C,
int  NBoundsequences,
int *  sequencesizes 
)
static

induced lexicographical sort

Parameters
scipSCIP ptr
arrayarray of strips to sort in ILO
arraysizesize of the array
Ccurrent set o comp bound sequences
NBoundsequencessize of C
sequencesizessizes of the sequences in C

Definition at line 794 of file branch_generic.c.

References GCG_Strip::C, GCG_BranchData::C, GCG_Strip::Csize, LexicographicSort(), GCG_Strip::scip, GCG_Strip::sequencesizes, and GCG_BranchData::sequencesizes.

Referenced by ChooseSeparateMethod().

static SCIP_RETCODE InitIndexSet ( SCIP *  scip,
SCIP_VAR **  F,
int  Fsize,
SCIP_VAR ***  IndexSet,
int *  IndexSetSize 
)
static

method for initializing the set of respected indices

Parameters
scipSCIP data structure
Farray of fractional mastervars
Fsizenumber of fractional mastervars
IndexSetset to initialize
IndexSetSizesize of the index set

Definition at line 375 of file branch_generic.c.

References GCGmasterVarGetNOrigvars(), and GCGmasterVarGetOrigvars().

Referenced by ChooseSeparateMethod().

static SCIP_RETCODE initNodeBranchdata ( SCIP *  scip,
GCG_BRANCHDATA **  nodebranchdata,
int  blocknr 
)
static

initialize branchdata at the node

Parameters
scipSCIP data structure
nodebranchdatabranching data to set
blocknrblock we are branching in

Definition at line 2036 of file branch_generic.c.

References GCG_BranchData::blocknr.

Referenced by branchDirectlyOnMastervar(), and createChildNodesGeneric().

static SCIP_RETCODE LexicographicSort ( SCIP *  scip,
GCG_STRIP **  array,
int  arraysize 
)
static

lexicographical sort using scipsort This method will change the array

Parameters
scipSCIP data structure
arrayarray to sort (will be changed)
arraysizesize of the array

Definition at line 579 of file branch_generic.c.

References GCGsortPtr().

Referenced by InducedLexicographicSort().

static SCIP_RETCODE partition ( SCIP *  scip,
SCIP_VAR **  J,
int *  Jsize,
SCIP_Longint *  priority,
SCIP_VAR **  F,
int  Fsize,
SCIP_VAR **  origvar,
SCIP_Real *  median 
)
static

partitions the strip according to the priority

Parameters
scipSCIP data structure
Jarray of variables which belong to the discriminating components
Jsizepointer to the number of discriminating components
prioritybranching priorities
Fset of fractional solutions satisfying bounds
Fsizesize of list of fractional solutions satisfying bounds
origvarpointer to store the variable which belongs to a discriminating component with maximum priority
medianpointer to store the median of fractional solutions satisfying bounds

Definition at line 831 of file branch_generic.c.

References getGeneratorEntry(), and GetMedian().

Referenced by buildNewGraphs(), callMetis(), gcg::GraphAlgorithms< T >::computekMetric(), gcg::GraphAlgorithms< T >::computeMincut(), gcg::GraphAlgorithms< T >::computeSoed(), gcg::RowGraph< T >::createDecompFromPartition(), gcg::ColumnGraph< T >::createDecompFromPartition(), gcg::HyperrowcolGraph< T >::createDecompFromPartition(), gcg::HyperrowGraph< T >::createDecompFromPartition(), gcg::HypercolGraph< T >::createDecompFromPartition(), gcg::RowGraph< T >::createSeeedFromPartition(), gcg::HyperrowcolGraph< T >::createSeeedFromPartition(), gcg::HyperrowGraph< T >::createSeeedFromPartition(), gcg::HypercolGraph< T >::createSeeedFromPartition(), and Separate().

static SCIP_Bool pruneChildNodeByDominanceGeneric ( SCIP *  scip,
SCIP_Real  lhs,
GCG_COMPSEQUENCE childS,
int  childSsize,
SCIP_CONS *  masterbranchcons,
int  childBlocknr 
)
static

check method for pruning ChildS indirectly by parentnodes retrun TRUE if node is pruned

Parameters
scipSCIP data structure
lhslhs for childnode which is checkes to be pruned
childSComponent Bound Sequence defining the childnode
childSsizesize of component bound sequence
masterbranchconsmaster branching constraint
childBlocknrnumber of the block for the childnode

Definition at line 1987 of file branch_generic.c.

References checkchildconsS(), GCG_BranchData::cons, GCGconsMasterbranchGetBranchdata(), GCGconsMasterbranchGetBranchrule(), and GCGconsMasterbranchGetParentcons().

Referenced by createChildNodesGeneric().

static SCIP_DECL_BRANCHCOPY ( branchCopyGeneric  )
static

copy method for master branching rule

Definition at line 2762 of file branch_generic.c.

References GCGincludeMasterCopyPlugins().

static SCIP_DECL_BRANCHEXECEXT ( branchExecextGeneric  )
static

branching execution method for relaxation solutions

Definition at line 2903 of file branch_generic.c.

static SCIP_DECL_BRANCHEXECLP ( branchExeclpGeneric  )
static
static SCIP_DECL_BRANCHEXECPS ( branchExecpsGeneric  )
static

branching execution method for not completely fixed pseudo solutions

Bug:
this needs to be implemented: #32

Definition at line 2917 of file branch_generic.c.

References BRANCHRULE_NAME.

static SCIP_DECL_BRANCHINIT ( branchInitGeneric  )
static

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

Definition at line 2946 of file branch_generic.c.

References GCGmasterGetOrigprob(), and GCGrelaxIncludeBranchrule().

static SCIP_DECL_EVENTEXITSOL ( eventExitsolGenericbranchvaradd  )
static

solving process deinitialization method of event handler (called before branch and bound process data is freed)

Definition at line 279 of file branch_generic.c.

References EVENTHDLR_NAME.

static SCIP_DECL_EVENTINITSOL ( eventInitsolGenericbranchvaradd  )
static

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

Definition at line 265 of file branch_generic.c.

References EVENTHDLR_NAME.

static SCIP_DECL_SORTPTRCOMP ( ptrilocomp  )
static

comparefunction for induced lexicographical sort

Definition at line 778 of file branch_generic.c.

References GCG_Strip::C, GCG_Strip::Csize, ILOcomp(), GCG_Strip::mastervar, GCG_Strip::scip, and GCG_Strip::sequencesizes.

SCIP_RETCODE SCIPincludeBranchruleGeneric ( SCIP *  scip)
static SCIP_RETCODE Separate ( SCIP *  scip,
SCIP_VAR **  F,
int  Fsize,
SCIP_VAR **  IndexSet,
int  IndexSetSize,
GCG_COMPSEQUENCE S,
int  Ssize,
GCG_RECORD record 
)
static

separation at the root node

Todo:
mb: this is a filter

this is a copy of S for the recursive call below

Parameters
scipSCIP data structure
Ffractional strips respecting bound restrictions
Fsizesize of the strips
IndexSetindex set
IndexSetSizesize of index set
Sordered set of bound restrictions
Ssizesize of the ordered set
recordidentified bound sequences

Definition at line 939 of file branch_generic.c.

References addToRecord(), ComponentBoundSequence::bound, ComponentBoundSequence::component, GCG_COMPSENSE_GE, GCG_COMPSENSE_LT, GCGgetMasterprob(), getGeneratorEntry(), GetMedian(), GCG_BranchData::origvar, partition(), GCG_Record::recordsize, ComponentBoundSequence::sense, and GCG_Record::sequencesizes.

Referenced by ChooseSeparateMethod(), and Explore().