# Linear programming constraint with uncertainty

 3 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... asked 27 Jan '14, 05:09 gecko 41●1●4 accept rate: 0% fbahr ♦ 4.6k●7●17 @gecko: "Inline math" = \$$... \$$, "display math" = \$... \$ ...and: backslashes must be doubled. [OR-X FAQ: Hey, how do I get that fancy math stuff?] (27 Jan '14, 05:27) fbahr ♦ @gecko: What do you mean by "$$a$$ also appears with a different coefficient"? (27 Jan '14, 05:52) Ehsan ♦ @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. (27 Jan '14, 06:24) gecko

 1 I would replace the decision variables xi by yi where yi = xi +1 Your problem becomes sum_i ai yi < M no uncertainty on the right hand side answered 01 Feb '14, 09:18 jfpuget 2.5k●3●10 accept rate: 8%
 0 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 01 Feb '14, 18:03 Iain Dunning 917●1●4●18 accept rate: 33%
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 27 Jan '14, 05:09

Seen: 1,515 times

Last updated: 01 Feb '14, 18:03

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.