A possible way to reduce degeneracy in integer programming computations

DOI10.1016/0167-6377(87)90009-5MaRDI QIDQ1104240zbMATH OpenOpenAlexFDO

Authors Bjørn Nygreen

Publication date 1987

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(87)90009-5

zbMATH Keywords

branch and bounddegeneracyrelaxations as lower boundsshadow prices

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Integer programming (90C10)

Review text

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.

Recommendations

• Branch and bound with estimation based on pseudo-shadow-prices
• Technical Note—An Improved Branch-and-Bound Method for Integer Programming
• Dual network bounds for integer programming problems of a special form
• Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information
• The reduced cost branch and bound algorithm for mixed integer programming

Cites work

• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Branch and Bound Methods for Mathematical Programming Systems
• Computer Codes for Problems of Integer Programming

Cited in

(5)

• Removing degeneracy in LP-type problems revisited
• Solving integer programs with a few important binary gub constraints
• Selected bibliography on degeneracy
• A note on reducing the number of variables in integer programming problems
• Branch and bound with estimation based on pseudo-shadow-prices

Describes a project that uses

Uses Software

• SCICONIC

This page was built for publication: A possible way to reduce degeneracy in integer programming computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104240)