## 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