Exact Computation of Basic Solutions for Linear Programming
Introduction
Exact linear programming has many applications such as finding provably
optimal
solutions in standard application areas, computer assisted proofs and
subroutines
for exact integer programming. The recent proof of the Kepler Conjecture by
Thomas Hales relies on solving thousands of linear programs exactly.
The fastest known technique for solving linear programs exactly is performing
the
simplex algorithm with floating point arithmetic , then computing, verifying and
correcting the final solution with symbolic computation. This leaves solving
sparse
rational systems of equations as the major bottleneck. We investigate methods to
solve sparse rational systems of linear equations exactly, and study their
behavior
computationally on a large test set arising from linear programming problems.
Exact Linear Programming
Linear programming is a technique for
optimizing a linear objective function
over a set of linear inequalities. Geometrically,
the inequalities represent a convex
polyhedron.
Standard form LP
Simplex Method
The most commonly used technique for linear programming is the simplex
method.
A simplified geometric description is:
•Start at a vertex of the polyhedron
•Follow edges of the polyhedron to better vertices
•Terminate at locally optimal vertex
At each vertex of the polyhedron the corresponding solution vector x can be
determined
by solving a system of linear equations. This is called a basic solution, and
the subsystem of A defining this solution is called a basis.
If the simplex method is performed using floating point computation, the
basis of
the final solution provides a structural description of the solution as the
solution to
a system of equations. The coefficients of these equations come from the
original
problem description, so the final solution can be computed exactly.
Optimality Verification
Linear programming duality theory provides a tool to certify optimality of an
exact
solution. Every linear programming problem has a related dual problem and if
either is feasible they share the same optimal objective value.
Linear Program (Primal)
Dual Problem
If x and y are feasible, then they are optimal if and only if cTx = bTy. An
optimal
basis of the primal problem (vertex of the polyhedron) structurally describes
both
the primal optimal solution, and the dual optimal solution y. Given the optimal
basis, calculating and certifying the exact optimal solution involves solving
two
systems of linear equations.
QSopt ex: A Rational LP Solver
The QSopt ex software [1] (by Applegate, et al.) does the following.
•Apply simplex in floating point arithmetic
•Compute basic solution exactly from final basis
•If solution is not optimal, increase precision
•Repeat procedure in higher precision, starting at current basis
This strategy proves very effective. Much of the simplex algorithm is done in
floating
point. Even when a suboptimal basis is returned due to floating point errors,
it is often close to the optimal basis, reducing the extended precision
computation .
The final output includes the optimal solution and an exact certificate of
optimality.
Solving Sparse Rational Systems
Several methods are known for solving sparse systems of rational equations Ax
= b
exactly, beyond applying standard techniques using rational arithmetic [3, 4].
If an
accurate enough approximate solution is calculated, the exact rational solution
can
be reconstructed using diophantine approximation. If the problem is scaled to
have
integer coefficients and solved modulo a large enough integer, the exact
rational solution
can be calculated using rational number reconstruction . Diophantine
approximation
and rational number reconstruction are performed by calculating continued
fraction convergents using the Extended Euclidean Algorithm.
Exact LU Decomposition
•Solve system directly using an LU decomposition over Q
Sparse decomposition algorithms focus on permuting rows and columns of the
system
to avoid fill-in and arithmetic operations .
Iterative Refinement
•Compute floating point LU decomposition of A
•Iteratively refine approximate solution
•Use rational number reconstruction to find exact solution
Using mixed precision iterative refinement an approximate solution is
computed,
suitable for rational reconstruction/diophantine approximation to be applied.
Wiedemann
•Use Wiedemann’s method to solve Ax = b over finite field
•Use p-adic lifting to find solution modulo large number
•Use rational number reconstruction to find exact solution
Wiedemann’s method [5] for solving systems of equations over a finite field
is a
black box algorithm, it only accesses the matrix for matrix-vector
multiplication.
Dixon
Compute LU decomposition of A over Zp
Use p-adic lifting to find solution modulo large number
Use rational number reconstruction to find exact solution
The finite field solves are done using a sparse LU
factorization, designed to minimize
fill-in.
Computations
Implementation
We implemented the four methods in C. We rely on the GNU
Multiple Precision
Library to store rational numbers and large integers. The codes for LU
factorization
over the rational numbers, finite fields and double precision floating point
numbers
all share a common structure and were adapted from the QSopt software, which is
designed for very sparse matrices. The rational reconstruction codes employ
output
sensitive lifting, Lehmer’s algorithm and other techniques to increase speed.
Test Problems
The linear-programming research community is fortunate to
have several publicly-available
libraries of test instances. We collected instances from several test libraries,
including NETLIB, MIPLIB 3.0 and many others. These collections are
comprised of instances gathered from business and industrial applications, and
from
academic studies. The instances were were given to QSopt ex and the optimal
basis
matrix, or the last basis encountered after 24 hours was recorded. After some
preprocessing and reduction the final set contains 276 instances, with
dimensions
ranging from 100 to over 50,000. For each instance we have both the square basis
matrix and the corresponding right-hand-side vector.
Results
We have given a performance profile comparing the
relationships. A performance
profile plots the number of instances solved within a factor x of the fastest
solve
time among the methods. The vertical axis represents the number of instances.
The horizontal axis gives the solve-time ratios. Ratios are compared instead of
averaging solution times , which ranged from hours to seconds.
This table gives the solve time ratios on subsets of the
problems partitioned by dimension,
solution size and density (nonzero entries per row). The solution bitsize
is the largest number of bits required to represent a component of the solution
vector.
We consider the ratio with respect to the Dixon method, and give the geometric
average of the ratios. This table allows us to observe the effect of various
problem
characteristics on the relative performance of the methods.
Conclusions
We evaluated several methods for symbolically solving
large sparse rational systems
of linear equations arising from a wide range of linear programming problems.
Dixon’s method and iterative refinement had similar performance, beating
the other methods. Iterative refinement was slightly faster in our experience,
but
Dixon’s method avoids numerical difficulties by using finite field arithmetic.
We
found Wiedemann’s algorithm to be much slower than the other methods tested on
this problem set. This set of real world problems also provides a useful test
set for
future studies. Further computational results and analysis are contained in [2].
| Prev | Next |