Probability that a chance-constrained linear program has feasible solution

niklas · science forum beginner Joined: 27 Mar 2005 Posts: 2

Hi,

I have the following question:

What is the probability that a linear program with a stochastic
right-hand side in the inequalities has a feasible solution?

Consider this LP:

minimize c*x
subject to
A*x <= b + D*w, where the N elements in the w vector are IID
N(0,sigma^2) (normally distributed)

I know that for a general LP, answering whether there is a feasible
solution or not has the same complexity as the original problem
formulation.

Does anybody have an opinion about the problem above? Note that I am
not interested in finding the best value of x such that the objective
function is minimized; I want to get a grasp about if I can tell
anything about the feasibility based on A, b and D. Or is this a very
hard problem?

Thank you!

//Niklas

PS.

My problem is a special case of the above problem:
Here "1" is an all-ones column vector, "I" the identity matrix, and "b"
is a scalar.
"Q" is a N*m-size matrix with orthogonal column vectors.

I start with an expression on the form
w + Q*x <= 1 * b
w + Q*x >= -1 * b

which can be written according to the form of the first equation:

[ Q ] [ 1 ] [ -I ]
[ ] <= [ ] * b + [ ] * w
[ -Q ] [ 1 ] [ I ]

Google