I have a linear programming problem with uncertainty in the parameters: Here a minimal snippet of it: \[-a + ax < M, \qquad a \in U=[-a_l,a_u], ~M \in \mathbf{R}^{+}\] The problem is that \(a\) appears with a positive and a negative coefficient, so worst-case analysis will underestimate the feasible region. In the problem at hand, it can also be understood as having uncertainty on both the lhs and the rhs. What is a proper way of tackling such constraints and how would it generalize to constraints as: \[-\sum_i a_i + \sum_i a_i x_i < M\] Edit: It is my first question here, and I am probably doing something wrong when typing Latex... |

No transformation is going to change the properties of the statement. Basically, if x >= 1 always then a_u is "active", if x < 1 then a_l is "active", and if it can be either then "both" are active - which is what you are worried about, I believe. This generalizes to your sum as well, but you can do something more interesting there: constrain the uncertainties so that only a certain number of them are away from their "mean" value. This gives an averaging sort of effect which will make it less pessimistic.
answered
Iain Dunning |

@gecko: "Inline math" =

`\\( ... \\)`

, "display math" =`\\[ ... \\]`

...and: backslashes must be doubled. [OR-X FAQ: Hey, how do I get that fancy math stuff?]@gecko: What do you mean by "\(a\) also appears with a different coefficient"?

@Ehsan It appears with a minus sign. If all all 'a' where positive, it would be easy to find the worst case. But I can not seem a LP formulation that does not shrink the feasible space.