Dyadic linear programming and extensions

A rational number is <i>dyadic</i> if it has a finite binary representation <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi> <mml:mo>/</mml:mo> <mml:msup><mml:mn>2</mml:mn> <mml:mi>k</mml:mi></mml:msup> </mml:mrow> </mml:math> , where <i>p</i> is an integer and <i>k</i> is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-point arithmetic on a computer. A vector is <i>dyadic</i> if all its entries are dyadic rationals. We study the problem of finding a dyadic optimal solution to a linear program, if one exists. We show how to solve dyadic linear programs in polynomial time. We give bounds on the size of the support of a solution as well as on the size of the denominators. We identify properties that make the solution of dyadic linear programs possible: closure under addition and negation, and density, and we extend the algorithmic framework beyond the dyadic case.