A Parallel Algebraic Approach Towards Discrete Optimisation
Date: July 19th (Friday)
Time: 11:35-12:00
Abstract
An extremely important subject of operational research
consists of integer programming (IP) problems,
also called discrete optimization problems, in which some or
all of the variables are required to assume integer values. The
acceptable integer values are sometimes further restricted to a finite
set or to nonnegative integers. Many combinatorial and graph problems can
be expressed in this form. Discrete-variable problems are usually more
complex and difficult to solve than continuous optimisation problems
since conventional numerical methods do not work anymore. Conventional
methods for solving integer programming are based on search where some
heuristics such as the Branch and Bound mechanism can be applied to reduce
the huge search space. Recently, the tools of commutative algebra and
algebraic geometry have brought new insights to integer programming via
the theory of Gr\"obner bases developed by Bruno Buchberger in the 1960s.
The key idea is to encode IP problems into a special ideal associated
with the constraint matrix $C$ and the cost (object) function $F$. An
important property of the ideal is that its Gr\"obner bases correspond
directly to the test sets of the IP problem. Thus, by employing an
algebraic package such as Macaulay and Maple, the test sets of IP can be
directly computed. Using a proper test set
(such as the minimal test set which
corresponts directly to the reduced Gr\"obner base of the ideal), the
optimal value of the cost function can be computed by constructing a
monotone path from the initial non-optimal solution of the problem to the
optimal solution. Thus, integer programming can be solved in a similar
fashion to the simplex method for linear programming without intensively
using heuristical search. This approach is particular interesting from
the point of parallelsation due to the inherent paralelism of the
Buchberger algorithm.
In this talk, I will present in detail this algeraic method of solving
integer programming. In particular, I will discuss the parallelsation of
the method and its practical impacts.
