A BRICS Mini-Course
August 12 and 13, 2003
Lectures by
K. Subramani, ksmani@csee.wvu.edu
Computer Science and Electrical Engineering, West Virginia University
In this mini-course, I will give a broad review of topics in Polyhedral programming. We will first describe the Linear Programming problem and some methods to solve it. This will be followed by Integer Programming.
I will then introduce an extension to Linear Programming called Quantified Linear Programming. We will analyze strategies for this problem and the complexity of various special cases. Finally, we will extend our ideas to Quantified Integer Programming, which is an extension of Quantified Boolean Formulae. We will show that total unimodularity is very powerful property in that Quantified Integer Programs with TUM structure can be relaxed to Quantified Linear Programs in exactly the same way as Integer Programs with TUM structure can be relaxed to linear programs.
The focus will be on developing concepts and strategies, rather than on the details of correctness proofs. No prerequisites other than an exposure to Linear Algebra is expected.