BAS: Basic Course on Stochastic Programming¶

* Send questions on the class to svanprog@impa.br, Subject: BAS date-of-the-class¶

* Grading system:¶

### - two lists with exercises (theory and computational practice)
### - one exam on theory on April 21st (yes, on Tiradentes holiday)
### - one Matlab/Octave project at the end of June
### - plus a 3rd list for PhD students

* 2 or 3 out-of-schedule special classes (aulão) reviewing exercises¶

* YouTube communication via chat might be an option for 'live' questions (we'll try)¶

The impact of uncertainty in optimization¶

An illustrative example from [Sec. 1.3 in KW]¶

Using national and imported oil, $oil_1$ and $oil_2$, the company produces standard and premium gasoline, $prod_1$ and $prod_2$.

Oil cost is $(c_1,c_2)^T=(2,3)^T$

Variable for input oil is $(x_1,x_2)^T$ so that production cost is $f(x):=c^Tx$

Demand for standard and premium gasoline is $(h_1,h_2)^T$

Each oil has a specific quality, different amounts needed to produce each type of gas ("productivity").

Need 2 units of national oil or 6 units of imported oil to make one unit of standard gasoline $$\hspace{5cm}2x_1+6x_2\geq h_1$$
Likewise for premium gas, $$\hspace{5cm}3x_1+3x_2\geq h_2$$

Refineries can process no more oil than their capacity: $x_1+x_2\leq 100\iff\hspace{1cm} -x_1-x_2\geq-100$.

We obtain the linear program

$$\left\{\begin{array}{ll}\min&2x_1+3x_2\\ \mbox{s.t.}&2x_1+6x_2\geq h_1\\ &3x_1+3x_2\geq h_2\\ &x_1+x_2\leq 100\\ &x_1\,,x_2\geq 0\,,\end{array}\right.$$

a particular instance of the linear programming problem $$\left\{\begin{array}{ll}\min&c^Tx\\ \mbox{s.t.}&Ax\geq b\\ &x\geq 0\,.\end{array}\right.$$

%Let's use OCTAVE glpk to solve the LP
%type help glpk to see the input/output arguments 
%[XOPT, FMIN, ERRNUM, EXTRA] = glpk (C, A, B, LB, UB,CTYPE, VARTYPE, SENSE, PARAM)
VARTYPE='CC';%continuous variables
LB=[0;0];UB=[];%bounds
c=[2;3];%cost function
h=[180;162];%demand of gasoline
b=[h;-100];%right hand side 
A=[2 6;3 3;-1 -1];CTYPE='LLL';%all constraints given as >=

[XOPT, FMIN, ERRNUM, EXTRA] = glpk (c, A, b, LB, UB,CTYPE, VARTYPE)

XOPT =

   36
   18

FMIN =  126
ERRNUM = 0
EXTRA =

  scalar structure containing the fields:

    lambda =

       0.25000
       0.50000
       0.00000

    redcosts =

       0
       0

    time = 0
    status =  5

The feasible production plans satisfy the constraints on capacity and productivity for standard and premium gas:¶

x=0:100;y1=100-x;y2=30-x/3;y3=54-x;
    X1=[x' x' x'];YMatrix1=[y1' y2' y3'];
    % Create figure
    figure1 = figure('XVisual',...
        '0x7a (TrueColor, depth 32, RGB mask 0xff0000 0xff00 0x00ff)');
    
    % Create axes
    axes1 = axes('Parent',figure1,'FontSize',8);
     ylim(axes1,[0 100]); xlim(axes1,[0 100]);
    box(axes1,'on');hold(axes1,'all');
    
    % Create multiple lines using matrix input to plot
    plot1 = plot(X1,YMatrix1,'Parent',axes1,'LineWidth',4);
    set(plot1(1),'DisplayName','   Capacity');
    set(plot1(2),'DisplayName','   Std Gas');
    set(plot1(3),'DisplayName','   Prem Gas'); 
    
        % Create legend
    legend1 = legend(axes1,'show');

the feasible set is¶

and the solution can be found graphically¶

$\bar x_1=36$ and $\bar x_2=18$, so $f(\bar x)=126$ is the minimum.¶

Our LP is well defined because¶

we assumed the cost $c$, the demand $h$, the productivity and the capacity are all KNOWN¶

BUT¶

decisions must be made before knowing exact data!¶

Premises¶

* model for weekly production process of one refinery relying on national and imported oil to supply gas stations with both types of gasoline¶

* the availability of national crude oil used for standard gas can change randomly: in¶

$$\hspace{5cm}2x_1+6x_2\geq h_1$$

the number $2$ is NOT deterministic data, and is replaced by $2+\eta_1$ for $\eta_1$ a random variable¶

* likewise for the availability of imported oil that can be used to produce premium gasoline. In¶

$$\hspace{5cm}3x_1+3x_2\geq h_2$$

the number $3$ is NOT deterministic data, and is replaced by $3.4-\eta_2$ for $\eta_2$ a random variable¶

* the demand for gasoline is also uncertain¶

$$h_1=180+\zeta_1\quad\mbox{and}\quad h_1=163+\zeta_2$$

Goals¶

* the weekly plan $(\bar x_1,\bar x_2)$ needs to be fixed in advance and cannot be changed¶

* the actual available oil ("productivity") is only known during the production process¶

* clients expect their demand to be satisfied during the week¶

Uncertainty modelling¶

Assume $ \eta_1\,,\eta_2\,, \zeta_1\,,\zeta_2$ are independent, with¶

* $\eta_1\sim\mathcal{N}(0,12)$¶

* $\eta_2\sim\mathcal{N}(0,9)$¶

* $\zeta_1\sim\mathcal{U}[-0.8,0.8]$¶

* $\zeta_2\sim\mathop{exp}(\lambda=2.5)$¶

Only $\zeta_1$ is bounded.¶

We constrain $\eta_{1,2}$ and $\zeta_2$ to their respective 99% confidence intervals:¶

* $\eta_1\in[-30.91,30.91]\qquad\hspace{4cm}\qquad\mbox{cdf}(x)=\displaystyle\frac12\left(1+\mathop{erf}\left(\frac{x-\mu}{\sigma\sqrt2}\right)\right)$¶

* $\eta_2\in[-23.18,23.18]$¶

* $\zeta_1\in[-0.8,0.8]$¶

* $\zeta_2\in[0,1.84]\qquad\hspace{6cm}\qquad\mbox{cdf}(x)=1-e^{\lambda x}$¶

we now have a stochastic LP¶

$$\left\{\begin{array}{ll}\min&2x_1+3x_2\\ \mbox{s.t.}&(2+\eta_1)x_1+6x_2\geq h_1+\zeta_1\\ &3x_1+(3.4-\eta_2)x_2\geq h_2+\zeta_2\\ &x_1+x_2\leq 100\\ &x_1\,,x_2\geq 0\,,\end{array}\right.$$

This is an undefined linear programming problem!¶

Giving a meaning to "min"¶

Changes in demand: // translations¶

Changes in availability: $\neq$ slopes¶

Which one is the feasible set of our optimization problem?¶

None? All? A specific one?¶

Answering to this question is called 'handling uncertainty' in the stochastic problem¶