A review of computation of mathematically rigorous bounds on optima of linear programs

Jared T. Guilbeau (), Md. Istiaq Hossain (), Sam D. Karhbet (), Ralph Baker Kearfott (), Temitope S. Sanusi () and Lihong Zhao ()
Additional contact information
Jared T. Guilbeau: University of Louisiana
Md. Istiaq Hossain: University of Louisiana
Sam D. Karhbet: University of Louisiana
Ralph Baker Kearfott: University of Louisiana
Temitope S. Sanusi: University of Louisiana
Lihong Zhao: University of Louisiana

Journal of Global Optimization, 2017, vol. 68, issue 3, No 10, 677-683

Abstract: Abstract Linear program solvers sometimes fail to find a good approximation to the optimum value, without indicating possible failure. However, it may be important to know how close the value such solvers return is to an actual optimum, or even to obtain mathematically rigorous bounds on the optimum. In a seminal 2004 paper, Neumaier and Shcherbina, propose a method by which such rigorous lower bounds can be computed; we now have significant experience with this method. Here, we review the technique. We point out typographical errors in two formulas in the original publication, and illustrate their impact. Separately, implementers and practitioners can also easily make errors. To help implementers avoid such problems, we cite a technical report where we explain things to mind and where we present rigorous bounds corresponding to alternative formulations of the linear program.

Keywords: Linear program; Interval computations; Mathematically rigorous lower bounds; Branch and bound; Relaxation; Global optimization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0489-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:68:y:2017:i:3:d:10.1007_s10898-016-0489-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0489-2

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().