Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.