Topics in exact precision mathematical programming

Linear programming;Mixed-integer programming;Exact computation;Symbolic computation;Linear algebra

Steffy, Daniel E. ; Algorithms, Combinatorics, and Optimization

University:Georgia Institute of Technology

Department:Algorithms, Combinatorics, and Optimization

关键词: Linear programming;    Mixed-integer programming;    Exact computation;    Symbolic computation;    Linear algebra;   

Others  :  https://smartech.gatech.edu/bitstream/1853/39639/1/steffy_daniel_e_201105_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming.Optimization software based on floating-point arithmetic can return suboptimal or incorrect resulting because of round-off errors or the use of numerical tolerances.Exact or correct results are necessary for some applications.Implementing software entirely in rational arithmetic can be prohibitively slow.A viable alternative is the use of hybrid methods that use fast numerical computation to obtain approximate results that are then verified or corrected with safe or exact computation.We study fast methods for sparse exact rational linear algebra, which arises as a bottleneck when solving linear programming problems exactly.Output sensitive methods for exact linear algebra are studied.Finally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer linear programming problems exactly.Extensive computational results are presented for each topic.