I need help in formulating an optimization problem. I have done a linear programming course but I am not familiar with stochastic programming. Any ideas and links for further reading in solving the problem would be really helpful. The description of the problem is as follows:

There are ( n ) independent random variables ( X_{1}, ldots, X_{n} ) following a known normal distribution.

$$ X_{i} sim mathcal{N}(mu_{i}, sigma_{i}^2) $$

There is another set of ( n ) (not independent) random variables ( Y_{1}, ldots, Y_{n} ) also following a known normal distribution. Assume the covariance matrix ( Sigma_{Y} ) is known.

$$ Y_{j} sim mathcal{N}(mu_{j}, sigma_{j}^2) $$

It also has a restriction that the realized values of ( Y_{j} = y_{j} ) should sum to a constant ( c ):

$$ sum_{j=1}^{n} y_{j} = c $$

Before stating the optimization problem, we need one more expression. Pair ( X_{i} ) with realized values of ( Y_{j} = y_{j} ). This is described by a function ( Z_{i} = y_{j} ) if ( X_{i} ) is paired up with the ( y_{j} ). (I am not sure how to write the pairing; this is the best I could come up with. This is sort of an indicator function)

Now the optimization problem can be stated. Consider the sum $$S = sum_{i=1}^{n} Z_{i} X_{i}$$

The optimization objective is to maximize ( mathbb{E}(S) ) as well as minimizing ( mathrm{Var}(S) ).

asked 03 Aug '11, 09:59

Anand's gravatar image

accept rate: 0%

edited 03 Aug '11, 12:14

Hi, @Anand: MathJax uses double-$ or backslash-squarebracket delimiters for displayed mathematics, and backslash-roundbracket for in-line mathematics. - http://www.mathjax.org/docs/1.1/start.html

(03 Aug '11, 12:00) fbahr ♦

@fbahr Thanks for the tip. I have edited the question to reflect that.

(03 Aug '11, 12:15) Anand

I might have understood your question wrongly, but I believe your optimization problem is not defined correctly as it has no decision variable and just consists of random parameters X and Y. I think you have misunderstood the concept of "random variable" in stochastic programming. In stochastic programming, "random variables" are parameters associated with random variables, therefore you cannot solely optimize them.

Regarding the multiple objectives of your stochastic programming model, you might try maximizing E(S) - k.Var(S) where k is a constant reflecting the importance of reducing the variance. Also, you should definitely consult "Solution approaches for the multiobjective stochastic programming" for a very good recent survey of other relevant solution methods.


answered 04 Aug '11, 08:45

Ehsan's gravatar image

Ehsan ♦
accept rate: 16%

edited 04 Aug '11, 08:46

@Ehsan Thank you for pointing out my misunderstanding regarding RV. I will definitely check out the link.

(05 Aug '11, 07:21) Anand

@Ehsan Is there a copy which is not behind the paywall?

(08 Aug '11, 12:41) Anand

@Anand Sorry, but you might try contacting Prof. Ben Abdelaziz directly at his email address. In addition, your uinversity library might have some kind of program or account for obtaining single copy of such articles with no charge.

(08 Aug '11, 12:53) Ehsan ♦

Just a little more elaboration. You could define a binary decision variable ( a_{ij} ) for this problem, equal to one if random parameter ( X_i ) is assigned to random parameter ( Y_j ). Your optimization problem would then have "assignment problem" constraints that ensure that each row and column of the n by n matrix of ( a_{ij} ) values sums to one.

Then, you can think more about expressions for the expectation and variance of the following sum: ( sum_{ij} X_i Y_j a_{ij} ).

P.S. I would appreciate any help using MathJax in this answer...


answered 05 Aug '11, 07:35

Alan%20Erera's gravatar image

Alan Erera
accept rate: 12%

edited 05 Aug '11, 09:27


For in-line math just use backslash + round-bracket delimiters like: ( your math expression here )

(05 Aug '11, 09:12) fbahr ♦

Thanks for the help... I needed to put in one more backslash to make things go!

(05 Aug '11, 09:28) Alan Erera
(05 Aug '11, 10:53) fbahr ♦

@Alan Thanks for that elaboration. That was real helpful.

(05 Aug '11, 16:27) Anand
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 03 Aug '11, 09:59

Seen: 5,256 times

Last updated: 08 Aug '11, 12:53

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