Create constraint only for a recourse problem in stochastic linear programming

Question

Question1: Northam Airlines is trying to decide how to partition a new plane for its Chicago– Detroit route. The plane can seat $200$ economy class, passengers. A section can be partitioned off for first-class seats, but each of these seats takes the space of $2$ economy class seats. A business class section can also be included, but each of these seats takes as much space as $1.5$ economy class seats. The profit on a first-class ticket is, however, three times the profit of an economy ticket. A business class ticket has a profit of two times an economy ticket’s profit. Once the plane is partitioned into these seating classes, it cannot be changed. Northam knows, however, that the plane will not always be full in each section. They have decided that three scenarios will occur with about the same frequency:

• scenario $1$: weekday morning and evening traffic,
• scenario $2$: weekend traffic, and
• scenario $3$: weekday midday traffic.

Under Scenario $1$, they think they can sell as many as $20$ first-class tickets, $50$ business-class tickets, and $200$ economy tickets. Under Scenario $2$, these figures are $10, 25,$ and $175$. Under Scenario $3$, they are $5, 10,$ and $150$. You can assume they cannot sell more tickets than seats in each of the sections.

(a) Assume that the data in Question1 correspond to the demand for seat reservations. Assume that there is a $50\%$ probability that all clients with a reservation effectively show up and that $10$ or $20\%$ no-shows occur with equal probability. Model this situation as a three-stage program, with first-stage decisions as before, second-stage decisions corresponding to the number of accepted reservations, and third-stage decisions corresponding to effective seat occupation. Show that the third stage is a simple recourse program with a reward for each occupied seat and a penalty for each denied reservation.

---

I couldn't understand how to solve this exercise (Introduction to Stochastic Programming, 2nd edition. John R. Birge and Francois Louveaux. Springer, page: 83, Section: 2.8). In fact, and I am facing a hard time doing any exercise of that book.

Is there any book where many examples were given before the exercises?

Update

I need just the concept to tackle this problem (construct the constraints). I know this is a lengthy problem; you can skip the complete solution and cite the central conceptual part. It will be a great help if you can help me to construct those constraints for the first stage (I will try to write other stage by my own).

Update 2

I can construct the constraints of first 2 stage but could not understand what they mean by,

...Show that the third stage is a simple recourse program with a reward for each occupied seat and a penalty for each denied reservation.

Answer 1

I know this is a lengthy problem; you can skip the complete solution and cite the central conceptual part

This too is a hard challenge. Stochastic programming is difficult to explain, and I find the classical way of formulating problems non-intuitive.

My general approach is:

1. What are the decisions. In this case, we need to decide how many seats to build, how may to sell, and then work out profit/loss depending on who turns up.
2. When does the uncertainty get revealed. In this case, after we build the seats we learn the demand, and then after we've sold the seats we learn who turns up.
3. With the decisions and the uncertainty, you can figure out the staging in the form of decision-uncertainty-decision-uncertainty-etc. In this case, we have three main decisions and two sources of uncertainty, so it's a three stage problem.
4. What's the first stage? It's to choose how many seats of each type to build, subject to the constraint that we can only have 200 seat equivalents. The number of seats built in the first stage are needed in later stages, so they are a state variable.
5. What's the next stage? In stage 2, we need as input the seats from the first stage, and also a realization of demand. Our decision is how many seats to sell. We can oversubscribe, because there's a chance of no-shows. The number of seats we well is needed in stage 3, so that's also a state variable.
6. And so on to the remaining stages. In this case, there's only one more stage. We need the number of seats built and the number of seats sold as input, as well as a realization of no-shows. Then we can compute our profit/loss.

If you're interested in multistage (i.e., t > 2) problems, you might like to read https://odow.github.io/SDDP.jl/stable/tutorial/basic/01_first_steps

There are a bunch of ways to solve this problem. SDDP isn't really intended for such small problems with diverse stage structures, but it works anyway. Here's some code if that helps:

using SDDP
import HiGHS

model = SDDP.LinearPolicyGraph(
    stages = 3,
    sense = :Max,
    optimizer = HiGHS.Optimizer,
    upper_bound = 800.0,
) do sp, stage
    cabins = [:first, :business, :economy]
    # State variables: because of SDDP.jl's quirks, we need to define them all
    # up front.
    #
    # First stage variables: Number of seats to choose
    @variable(sp, seats[cabins] >= 0, SDDP.State, initial_value = 0)
    # Second stage variables: Number of seats to sell
    @variable(sp, sell[cabins] >= 0, SDDP.State, initial_value = 0)
    if stage == 1
        # First stage: choose seat distribution
        scale = Dict(:first => 2.0, :business => 1.5, :economy => 1.0)
        @constraint(sp, sum(scale[c] * seats[c].out for c in cabins) <= 200.0)
        # We don't use `sell` in the first stage and there is no objective
        # contribution
        @constraint(sp, [c in cabins], sell[c].in == sell[c].out)
        @stageobjective(sp, 0.0)
    elseif stage == 2
        # Second stage: choose how many seats to sell
        Ω = [
            Dict(:first => 20, :business => 50, :economy => 200),
            Dict(:first => 10, :business => 25, :economy => 175),
            Dict(:first => 5, :business => 10, :economy => 150),
        ]
        SDDP.parameterize(sp, Ω) do ω
            for (cabin, demand) in ω
                set_upper_bound(sell[cabin].out, demand)
            end
        end
        # We can't change the number of seats, and there is no objective
        # contribution
        @constraint(sp, [c in cabins], seats[c].in == seats[c].out)
        @stageobjective(sp, 0.0)
    else
        # Third stage: Find out who turns up, and pay penalty for over-selling
        @assert stage == 3
        # Variable to compute oversold seats
        @variable(sp, Δ[cabins] >= 0)
        # Seat balance constraint to compute Δ
        @constraint(sp, bal[c in cabins], 1.0 * sell[c].in - Δ[c] <= seats[c].in)
        # 100, 90, and 80% of clients turn up with 50, 25, and 25% probability.
        SDDP.parameterize(sp, [1.0, 0.9, 0.8], [0.5, 0.25, 0.25]) do ω
            for c in cabins
                # Update the seat balance constraint with the true multiplier
                set_normalized_coefficient(bal[c], sell[c].in, ω)
            end
            scale = Dict(:first => 3.0, :business => 2.0, :economy => 1.0)
            @stageobjective(sp, sum(scale[c] * (sell[c].in - 2.5 * Δ[c]) for c in cabins))
        end
    end
end

SDDP.train(model, iteration_limit = 30)
simulations = SDDP.simulate(model, 10, Symbol[:seats, :sell]);

julia> getfield.(simulations[1][1][:seats], :out)
1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, [:first, :business, :economy]
And data, a 3-element Vector{Float64}:
  10.0
  20.000000000000018
 149.99999999999997
```

Answer 2

Ok, my last post for this Q perhaps: regarding: update 2, Stage 3, you can introduce a recourse variable, a random variable for each section to capture overbooking like:

S[s,c] - c >= O[c] where O[c] is overbooking for section c, c = [F,B,E], s=scenarios & S[s,c] is ticket sales for scenario s. Similar to Oscar's.

Or

Remove this constraint in stage 2: S[s,c] <= c, since the assumption of bookings limited to seat capacity will no longer exit, add Constraint

S[s,c] >= c and so for Stage 3:

Overbooking = S[s,c]-c

With no-show into account, add a Penalty like:

P[c](0.5S[s,c] - c), where P[c] is penalty for section c. Penalty for airline will be for ticket holders who are still in excess of capacity for each section even after no-shows. Also there's no assumption of excess passengers being upgraded.

Also, since its Stage 3 depending upon Stage 2 Joint probability for 50% no-show for Scenario 1 is: 0.33*0.5

So Total Penalty =

Sum of (0.33)(0.5)P[c](0.5S[s,c]-c) for all s & c

Objective = Total Ticket Price - Total Penalty

Answer 3

Ok, Stage=1: design Capacity=200 Vars: f, b, e #or set of section

Subject to:

stage:1 designing

2f+1.5b+e <= capacity

Stage:2 booking

Vars: sf1, sf2, sf3, sb1,...

S[s,c] <= demand[s,c] v c € section, s€scenarios

Linking stage 1 & stage 2 vars

Sf[s,c] <= f...

Stage 3: overbooking?

unclear if each no show have joint Probability, like 0.33*0.33 (probs for Each scenario & no show) Also if tickets sold limited by seats then where is overbooking?