% Jeremy Schiff - 8/6/2018
% COMP 150 - Algos
% This file contains a pair of toy problems to show the L shaped method 
% (from https://perso.uclouvain.be/anthony.papavasiliou/public_html/LShaped.pdf)
% which solves a two-stage linear programming problem with fixed recourse.
% The algorithm gives a more explicit description of such problems, but
% the idea is that you need to allocate some number of things - let's call
% them (x_1, x_2, ..., x_i). There is some initial cost to each that we
% allocate as with a one-stage linear program, but there is also a second
% stage cost that depends on some random outcome that is yet to happen. For
% example, we are growing crops and need to divy up our land in the
% Spring among various crops. We know the approximate yields and general prices.
% However, depending on the weather conditions, certain crops might produce
% a different yield than expected. Two-stage linear programming allows us
% to model this randomness and find an optimal solution up to expected
% value.

fprintf('Problem 1: feasible, but non-optimal initial solution\n')
eps = 1e-8;

c = [100, 150];
A = [1, 1; -1, 0; 0, -1 ];
b = [120; -40; -20];
W = [6, 10; 8, 5; 1, 0; 0, 1; -1, 0; 0, -1];
T = [];
h = [];
q = [];
T(:, :, 1) = [-60, 0; 0, -80; 0, 0; 0, 0; 0, 0; 0, 0];
h(:, 1) = [0; 0; 500; 100; 0; 0];
T(:, :, 2) = [-60, 0; 0, -80; 0, 0; 0, 0; 0, 0; 0, 0];
h(:, 2) = [0; 0; 300; 300; 0; 0];
q(:, 1) = [-24, -28];
q(:, 2) = [-28, -32];
p = [.4, .6];

L_shaped_method(A, b, c, T, q, h, W, p, eps);

fprintf('\nProblem 2: non-feasible intial solution\n')
c = [3, 2];
A = [-1, 0; 0, -1];
b = [0; 0];
W = [3, 2; 2, 5; 1, 0; -1, 0; 0, 1; 0, -1];
T = [];
h = [];
q = [];
y_bounds = [4,4; 4,8; 6,4; 6,8];
for e = 1:4
    e_bound = y_bounds(e, :);
    y_1_bound = e_bound(1);
    y_2_bound = e_bound(2);
    T(:, :, e) = [-1, 0; 0, -1; 0, 0; 0, 0; 0, 0; 0, 0];
    h(:, e) = [0; 0; y_1_bound; -y_1_bound * .8; y_2_bound; -y_2_bound * .8];
    q(:, e) = [15, 12];
end
p = [.25, .25, .25, .25];
eps = 1e-8;

L_shaped_method(A, b, c, T, q, h, W, p, eps);

