Hello everyone,

I am trying to solve a stochastic problem with SAA method. Indeed, I have written the code in R and I only need to solve a MIP problem like the following in my program:

\[ \begin{array}{l} % ---- \text{minimize} & \frac{1}{M'_1} \sum\limits_{t=1}^{M'_1} \sum\limits_{j=1}^{s} \left( {\max \left\{ \left( \hat{n}_\text{min} \right)_j - \sum\limits_{i=1}^k {r_i}{d_{ij}}^{(t)}, \, 0 \right\}} \right)^m \\ % ---- \text{subject to:} \, & \left\{ \begin{array}{l} % ---- \left({\sum\limits_{i=1}^{k} {r_i}{N_i}^{(t)} - K}\right) - L {z_t} \leq 0, \quad t=1, \ldots, M'_2 \\ % ---- \sum_{t=1}^{M'_2} \frac{z_t}{M'_2} \leq \alpha, \quad z_t \in \{0,1\}, \quad t=1, \ldots, M'_2 \\ % ---- 0 \leq r_i \leq 1, \quad i=1, \ldots, k % ---- \end{array} \right. \end{array} \]

where the vectors \(r_i\), \(i=1,2,...,k\) are the decision variables and the rest parameters are known.

I know that this problem is equivalent with the following MIP linear problem:

\[ \begin{array}{l} % ---- \text{minimize} & \frac{1}{M'_1}\sum\limits_{t=1}^{M'_1} \sum\limits_{j=1}^{s} ({\nu_j^{(t)})}^m\\ % ---- \text{subject to:} \, & \left\{ \begin{array}{l} % ---- \left( \sum\limits_{i=1}^{k} {r_i}{N_i}^{(t)} - K \right) - L {z_t} \leq 0, \quad t=1, \ldots, M'_2\\ % ---- \sum\limits_{t=1}^{M'_2} \frac{z_t}{M'_2} \leq \alpha \\ % ---- ( \hat{n}_\text{min} )_j - \sum\limits_{i=1}^k {r_i}{d_{ij}}^{(t)} \leq \nu_j^{(t)}, \quad t=1, \ldots, M'_1, \quad j=1, \ldots, s \\ % ---- z_t \in \{0,1\}, \quad t=1, \ldots, M'_2\\ % ---- \nu_j^{(t)} \geq 0, \quad t=1, \ldots, M'_1, \quad j=1, \ldots, s\\ % ---- 0 \leq r_i \leq 1, \quad i=1, \ldots, k % ---- \end{array} \right. \end{array} \]

As you see, the number of variables is \(s \times M'_1 + M'_2 + k\) and the number of constraint is \(s \times M'_1 + M'_2 + 1\).

I can not solve the problem for almost large values of \(M'_1\) and \(M'_2\).

I wonder if there is anyway to be able to solve the problem with larger number of variables and constraints with Rcplex and Can I solve the first problem in a way to make the speed higher?

How much large a problem similar to this can be approximately?

I really appreciate any kind of help in advance.

Best,
Shima.

asked 24 Jul '13, 12:03

shima's gravatar image

shima
111
accept rate: 0%

edited 26 Jul '13, 12:18

fbahr's gravatar image

fbahr ♦
4.6k716

Are you sure about your model formulation? Usually when using a scenario-based formulation in stochastic programming, we link some of the decision variables to scenarios to act as recourse actions. For example in a facility location problem, you consider one set of allocation variables per scenario to determine the best allocation strategy in case of realizing each scenario. Your formulation seems more like a robust optimization formulation where one set of decision variables has to perform well under all possible realizations.

(25 Jul '13, 12:25) Ehsan ♦

Hello Ehsan,

First of all thanks for your reply. Indeed, I do not know what you mean by linking the decision variables to scenarios. As far as I know, SAA is a Monte Carlo simulation-based approach and its basic idea is that a random sample is generated and the expected value objective function and the chance constraint are approximated by their corresponding sample average functions. The obtained problem is a deterministic problem which should be solved.

My initial optimization problem is as follows:

\[ \begin{array}{l} \text{minimize} & {\bf E} \left[ \sum\limits_{j=1}^{s} \left( \max \left\{ ( \hat{n}_{min} )_j - \sum\limits_{i=1}^k {r_i}{D_{ij}}, \, 0 \right\} \right)^m \right]\\ \text {subject to:} & \begin{array}{l} P\left({\sum\limits_{i=1}^k {{r_i}{N_i}} \leq K}\right) \geq 1-\alpha, \quad 0 \leq r_i \leq 1, \quad i=1,\ldots, k \end{array} \end{array} \]

I am using a sample approximation method not a scenario approximation method. My problem is almost similar to the first example in paper "A Sample Approximation Approach for Optimization with Probabilistic Constraints" by J. Luedtke, 2007. The difference is in the objective functions. Mine is an expected value function.

Finally, I think I have to solve a MIP problem (the one that I had asked before) several times with different Monte Carlo sample sizes and when I use a large sample size, the error is appeared.

Yours Sincerely,

Shima.

(26 Jul '13, 04:54) shima

Initially, I thought you're solving a two-stage SP model. Since you're not, there should not be any problem with your model as long as you're following the reference you mentioned.

(26 Jul '13, 12:56) Ehsan ♦
Be the first one to answer this question!
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:

×191
×58
×5
×4

Asked: 24 Jul '13, 12:03

Seen: 834 times

Last updated: 26 Jul '13, 12:56

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