# Uncertaint linear program

I have a linear programming problem such that its set of constraints can be divided into two parts. The first part are general linear constraints and the second part are uncertain constraints. It means that some of coefficients are uncertain but given in an interval. A small example of the problem is as follows:

Min $f_{12} + f_{23} + f_{24} + f_{45} + f_{35}$

s.t: $f_{12}=1$
$f_{23} + f_{24} - f_{12} = 0$

$f_{35} - f_{23} = 0$

$f_{45} - f_{24} = 0$

$f_{45} + f_{35} = -1$

$f_{24} - p_{24} f_{12} = 0$

$f_{23} - p_{23} f_{12} =0$

$p_{23} + p_{24} =1$

$p_{23} \in [0, 1/6]$

$p_{24} \in [1/6, 1]$

$f_{ij} \geq 0$ for all ij

Can this problem be solved in polynomial time?

-
Never mind polynomial, your problem solves in constant time. Its solution is not any dependent on its parameter values. –  ashley Feb 6 '13 at 10:38
why? I think it is dependent. –  Star Feb 6 '13 at 10:41