branch_pscost.h File Reference

Detailed Description

pseudo costs branching rule

Author

Tobias Achterberg

Krunal Patel

The pseudo costs branching rule selects the branching variable with respect to the so-called pseudo costs of the variables. Pseudo costs measure the average gain per unit in the objective function when the variable was branched on upwards or downwards, resp. The required information is updated at every node of the solving process.

The selected variable maximizes the expected gain of the dual bound in the created subtree.

Discounted pseudo costs are an extension of classic pseudo costs. If we interpret pseudo costs as the immediate reward for branching on a variable, then discounted pseudo costs can be considered to give the discounted total reward for branching on a variable, including gains of nodes a few level below branched node. In the current implementation, we consider discounted pseudo costs from one additional level according to the parameter discountfactor .

For a more mathematical description and a comparison between the pseudo costs branching rule and other branching rules in SCIP, we refer to

Tobias Achterberg
Constraint Integer Programming
PhD Thesis, Technische Universität Berlin, 2007

Definition in file branch_pscost.h.

#include "scip/def.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_var.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeBranchrulePscost (SCIP *scip)
SCIP_RETCODE	SCIPselectBranchVarPscost (SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsscore, int nbranchcands, SCIP_VAR **var, SCIP_Real *brpoint)