A possible way to reduce degeneracy in integer programming computations (Q1104240)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4055374
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A possible way to reduce degeneracy in integer programming computations |
scientific article; zbMATH DE number 4055374 |
Statements
A possible way to reduce degeneracy in integer programming computations (English)
0 references
1987
0 references
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.
0 references
degeneracy
0 references
branch and bound
0 references
relaxations as lower bounds
0 references
shadow prices
0 references
0.8477810025215149
0 references
0.7688307166099548
0 references
0.7560145258903503
0 references
0.7554377913475037
0 references
0.7445126175880432
0 references
