A possible way to reduce degeneracy in integer programming computations (Q1104240)

A branch and bound algorithm to solve integer programming problems using linear programming relaxations as lower bounds is often used in commercial mathematical programming packages. The search in the branch and bound tree is often guided by so-called shadow prices. The author discusses the influence fixed variables and redundant rows have on shadow price calculations. A method for improving shadow price calculations based on forcing fixed variables out of the LP-basis and attempting to force non-basic slacks at zero activity on redundant rows into the basis, is presented. Computational results based on two problems show an improvement over existing methods.