Optimization with Recourse Tutorial
A quick guide with numerical examples
We’ll start by introducing a preview of what optimization is and some of its special forms including optimization with recourse. We’ll then have a quick formulation and a numerical example. By the end of the tutorial, hopefully you’ll get a sense of why optimization with recourse can be a useful tool for stochastic use cases and how optimization with recourse is different from the usual averaging methods like mean and weighted average.
Optimization Basics
Optimization has been a key tool for efficiently allocating limited resources for a given problem scenario. The standard mathematical program provides a set of decisions usually for a single objective made by a single decision maker. In practice, many optimization problems are modelled considering multiple-decision makers and multiple stages. Multilevel programming involves multiple levels or stages where each stage can have multiple objectives that can be made by multiple decision makers.
Two-stage stochastic optimization programs are a subset of multilevel programming. Stochastic programs usually model uncertain parameters based on probability distributions. Uncertainties occur in two stages based on the decisions when the uncertainties are made known such as the case of the optimization with recourse.
Why Recourse?
Two-stage optimization with recourse occurs when a single decision maker may need to optimize the objective at a different stage. In cases where the decisions x of the feasible set X must be made before the realization of a scenario ω from the probable set Ω, a stochastic optimization with recourse is suited to solve such problems.
Recourse programs refer to stochastic optimizations with recourse actions y from a feasible set Y that is taken after the uncertainty is disclosed. Decisions then can be divided into two stages. The recourse actions y are known as the second-stage decisions. Decisions x made before ω is disclosed are called first-stage decisions. In this framework, the uncertain constraints are treated as soft constraints that could be violated but have penalty costs influencing the choice of x. The second stage must consider the expectation from the probable scenarios. Penalizing the deviations promotes feasibility in the first stage decisions and becomes robust to uncommon extreme anomalies. If the sample space can be countable or approximated into scenarios ω in the set Ω with the probability φ, the expected minimum recourse 𝔼 can be represented using a summation based on φ.
Sample Problem Formulation
We’ll start of with formulation with first stage and second stage decisions as below:
Sample Numerical Solution
Noticed that the first stage decision changed when the two scenarios are considered in the two-stage optimization with recourse. The resulting first stage decision is not necessarily the mean or the weighted average of the two scenarios in the second stage. Table 1 presents the resulting first decisions and their associated value.
Summary
If we are given a use case where a decision has to be made before the scenarios are made known, instead of just using the mean, weighted recourse, or single-level optimizations, it may be a good idea to try optimization with recourse. Such a tool becomes essential especially when we want to get the most out of the given info and risks.
