Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.