Quantified Linear Programming is the problem of checking whether a polyhedron specified by a linear system of inequalities is non-empty, with respect to a specified quantifier string. Quantified Linear Programming subsumes traditional Linear Programming, since in traditional Linear Programming, all the program variables are existentially quantified (implicitly), whereas, in Quantified Linear Programming, a program variable may be existentially quantified or universally quantified over a continuous range. On account of the alternation of quantifiers in the specification of a Quantified Linear Program (QLP), this problem is non-trivial. QLPs represent a class of Declarative Constraint Logic Programs (CLPs) that are extremely rich in their expressive power. The complexity of Quantified Linear Programming for arbitrary constraint matrices is unknown. In this paper, we show that polynomial time decision procedures exist for the case in which the constraint matrix is Totally Unimodular (TUM). We also provide a taxonomy of Quantified Linear Programs, based on the structure of the quantifier string and discuss the computational complexities of the constituent classes.
Host: Frank Pfenning
Appointments: Jennifer Landefeld Principles
of Programming Seminars
Friday, February 7, 2003
3:30 p.m.
Wean Hall 8220