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's gravatar image

gecko
4114
accept rate: 0%

edited 01 Feb '14, 15:54

fbahr's gravatar image

fbahr ♦
4.6k716

@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

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

link

answered 01 Feb '14, 09:18

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

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.

link

answered 01 Feb '14, 18:03

Iain%20Dunning's gravatar image

Iain Dunning
9171418
accept rate: 33%

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×27
×16
×5

Asked: 27 Jan '14, 05:09

Seen: 1,334 times

Last updated: 01 Feb '14, 18:03

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