Scippy

SCIP

Solving Constraint Integer Programs

Macros | Functions
branch_multaggr.c File Reference

Detailed Description

fullstrong branching on fractional and multi-aggregated variables

Author
Anna Melchiori
Gerald Gamrath

This branching rule uses all fractional binary and integer variables as candidates, as well as fractional multiaggregated binary and integer variables. Although not directly contained in the presolved problem anymore, the multi-aggregation provides an affine linear sum of integer variables, on which branching can be performed.

For more details, see G.Gamrath, A.Melchiori, T.Berthold, A.M.Gleixner, D.Salvagnin: Branching on Multi-aggregated Variables (http://dx.doi.org/10.1007/978-3-319-18008-3_10)

Definition in file branch_multaggr.c.

#include <assert.h>
#include <string.h>
#include "scip/branch_multaggr.h"
#include "scip/branch_fullstrong.h"
#include "scip/cons_linear.h"
#include "scip/var.h"
#include "scip/set.h"
#include "scip/pub_tree.h"
#include "scip/struct_scip.h"
#include "scip/clock.h"

Go to the source code of this file.

Macros

#define BRANCHRULE_NAME   "multaggr"
 
#define BRANCHRULE_DESC   "fullstrong branching on fractional and multi-aggregated variables"
 
#define BRANCHRULE_PRIORITY   0
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define DEFAULT_REEVALAGE   0LL
 
#define DEFAULT_MAXPROPROUNDS   0
 
#define DEFAULT_PROBINGBOUNDS   TRUE
 

Functions

static SCIP_RETCODE selectVarMultAggrBranching (SCIP *scip, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestsol, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_Real *estimatedown, SCIP_Real *estimateup, SCIP_RESULT *result)
 
static SCIP_DECL_BRANCHCOPY (branchCopyMultAggr)
 
static SCIP_DECL_BRANCHFREE (branchFreeMultAggr)
 
static SCIP_DECL_BRANCHINIT (branchInitMultAggr)
 
static SCIP_DECL_BRANCHEXIT (branchExitMultAggr)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpMultAggr)
 
SCIP_RETCODE SCIPincludeBranchruleMultAggr (SCIP *scip)
 

Macro Definition Documentation

#define BRANCHRULE_NAME   "multaggr"

Definition at line 43 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr(), and selectVarMultAggrBranching().

#define BRANCHRULE_DESC   "fullstrong branching on fractional and multi-aggregated variables"

Definition at line 44 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr().

#define BRANCHRULE_PRIORITY   0

Definition at line 45 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr().

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 46 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr().

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 47 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr().

#define DEFAULT_REEVALAGE   0LL

number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node

Definition at line 50 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr().

#define DEFAULT_MAXPROPROUNDS   0

maximum number of propagation rounds to be performed during multaggr branching before solving the LP (-1: no limit, -2: parameter settings)

Definition at line 53 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr().

#define DEFAULT_PROBINGBOUNDS   TRUE

should valid bounds be identified in a probing-like fashion during multi-aggr branching (only with propagation)?

Definition at line 56 of file branch_multaggr.c.

Referenced by SCIPincludeBranchruleMultAggr().

Function Documentation

static SCIP_RETCODE selectVarMultAggrBranching ( SCIP *  scip,
SCIP_VAR **  bestcand,
SCIP_Real *  bestscore,
SCIP_Real *  bestsol,
SCIP_Real *  bestdown,
SCIP_Real *  bestup,
SCIP_Bool *  bestdownvalid,
SCIP_Bool *  bestupvalid,
SCIP_Real *  provedbound,
SCIP_Real *  estimatedown,
SCIP_Real *  estimateup,
SCIP_RESULT *  result 
)
static
Parameters
sciporiginal SCIP data structure
bestcandthe best candidate variable selected by strong branching
bestscorescore of the best branching candidate
bestsolsolution value of the best branching candidate
bestdownobjective value of the down node when branching on bestcand
bestupobjective value of the up node when branching on bestcand
bestdownvalidis bestdown a valid dual bound for the down branch?
bestupvalidis bestup a valid dual bound for the up branch?
provedboundproved dual bound for the current subtree
estimatedownpointer to store the down child nodes estimate
estimateuppointer to store the up child nodes estimate
resultpointer to store results of branching

Definition at line 142 of file branch_multaggr.c.

References BRANCHRULE_NAME, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DECL_BRANCHCOPY(), SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPaddConsNode(), SCIPallColsInLP(), SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPbranchruleGetData(), SCIPconsGetName(), SCIPcreateConsLinear(), SCIPdebugMessage, SCIPendProbing(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfindBranchrule(), SCIPfreeBufferArray, SCIPgetBranchScore(), SCIPgetCurrentNode(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetDepthLimit(), SCIPgetFixedVars(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNFixedVars(), SCIPinfinity(), SCIPinfoMessage(), SCIPisExactSolve(), SCIPisFeasIntegral(), SCIPisGE(), SCIPnewProbingNode(), SCIPnodeGetLowerbound(), SCIPprintCons(), SCIPreleaseCons(), SCIPsetFeasCeil(), SCIPsetFeasFloor(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPstatistic, SCIPvarGetLPSol(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetName(), SCIPvarGetPseudocost(), SCIPvarGetStatus(), SCIPvarGetType(), Scip::set, Scip::stat, and TRUE.

static SCIP_DECL_BRANCHCOPY ( branchCopyMultAggr  )
static

copy method for branchrule plugins (called when SCIP copies plugins)

Definition at line 549 of file branch_multaggr.c.

Referenced by selectVarMultAggrBranching().

static SCIP_DECL_BRANCHFREE ( branchFreeMultAggr  )
static

destructor of branching rule to free user data (called when SCIP is exiting)

Definition at line 563 of file branch_multaggr.c.

static SCIP_DECL_BRANCHINIT ( branchInitMultAggr  )
static

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

Definition at line 583 of file branch_multaggr.c.

static SCIP_DECL_BRANCHEXIT ( branchExitMultAggr  )
static

deinitialization method of branching rule (called before transformed problem is freed)

Definition at line 620 of file branch_multaggr.c.

static SCIP_DECL_BRANCHEXECLP ( branchExeclpMultAggr  )
static

branching execution method for fractional LP solutions

Definition at line 720 of file branch_multaggr.c.

SCIP_RETCODE SCIPincludeBranchruleMultAggr ( SCIP *  scip)

creates the multi-aggregated branching rule and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 1045 of file branch_multaggr.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_MAXPROPROUNDS, DEFAULT_PROBINGBOUNDS, DEFAULT_REEVALAGE, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddLongintParam(), SCIPallocMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExit(), SCIPsetBranchruleFree(), SCIPsetBranchruleInit(), SCIPstatistic, and TRUE.

Referenced by SCIPincludeDefaultPlugins().