DIMACS TR: 2004-41

The Controlled Linear Programming Problem



Authors: Henrik Bjorklund, Olle Nilsson, Ola Svensson and Sergei Vorobyov

ABSTRACT
We introduce and investigate the new Controlled Linear Programming Problem. In a system of linear constraints of the form $x_i\leq p_i^j(\bar x)+w_i^j$, where $p_i^j$ are linear homogeneous polynomials with nonnegative coefficients, some variables are controlled and the controller wants to select exactly one constraint for each controlled variable in a way that makes $\max\sum x_i$ subject to the remaining constraints as large as possible (over all selections). We suggest several iterative strategy improvement policies (simplex-like and interior-point), prove optimality conditions in several important cases, describe subexponential algorithms, %, including single-, multiple-switch, and interior point ones, and show that the decision version of the problem is a member of NP $\cap$ coNP whenever stability yields optimality, and also when all coefficients are nonnegative integers.

It turns out that the well known mean payoff, discounted payoff, and simple stochastic games are easily reducible to the Controlled LP-Problem. This suggests a simple unifying view of all these games as particular restricted instances of the problem.

We show that a slight generalization of the problem allowing for negative coefficients in the constraint polynomials $p_i^j$ leads to NP-hardness.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-41.ps.gz

DIMACS Home Page