Abstract

This work presents two rules of branching variables for the Branch and Bound algorithm; one is based on the flatness polyhedron and the other one is an hybrid rule that uses this rule in combination with the pseudocost rule. The flatness rule is more time consuming because it requires solving two linear programming problems for each fractional variable, but the search tree displayed is about 50% smaller. The hybrid rule proposed uses the flatness rule on the first iterations of the algorithm and then uses pseudocost rule until it finds the optimum solution. Time savings are about 30% of the CPU time and about 50% from the total number of nodes.