LinearDecisionRules.jl Documentation

LinearDecisionRules.jl is a Julia package for solving stochastic optimization problems using linear decision rules (LDRs).

Overview

LinearDecisionRules.jl provides a simple JuMP abstraction to represent decision rules as linear functions of random variables. It handles two-stage stochastic optimization problems where:

  • First-stage decisions are made before uncertainty is revealed
  • Second-stage decisions can adapt (linearly) to the realized uncertainty

This package implements tractable reformulations of both primal and dual linear decision rules, inspired by the paper Primal and dual linear decision rules in stochastic and robust optimization. Those reformulations result in finite optimization problems and provide both primal and dual bounds. The primal decision rule is feasible over the entire uncertainty set.

Problem formulation

The problems the package deals with are of the form:

\[\begin{array}{rl} \min \ & \mathbb{E}_\xi [ c(\xi)^\top x(\xi) + x(\xi)^\top Q x(\xi) + r ] \\[0.5ex] \text{s.t.} & A_e x(\xi) = b_e(\xi) \\ & b_l(\xi) \leq A x(\xi) \leq b_u(\xi) \\ & x_l \leq x(\xi) \leq x_u \\ & x_i(\xi) \text{ is non-anticipative, for } i \in I \\ & \forall \xi \in \Xi \end{array}\]

where $\Xi \subset \mathbb{R}^m$ is a polytope described by:

\[\begin{aligned} \Xi & = \{\, \xi = (1, \eta) \in \mathbb{R}^m \mid W_u \eta \leq h_u, W_l \eta \geq h_l, lb \leq \eta \leq ub \,\} \\ & = \{\, \xi \in \mathbb{R}^m \mid W \xi \geq h \,\}. \end{aligned}\]

Non-anticipative variables cannot depend on the random variable $\xi$. This is equivalent to fixing their decision rules to have coefficient equal to zero, except for the constant term.

Note

For duality arguments underlying the reformulations, the uncertainty set $\Xi$ is assumed to span the entire space $\mathbb{R}^m$. In practice, this implies that uncertain variables $\eta$ do not appear in equality constraints.

Installation

import Pkg
Pkg.add("LinearDecisionRules")

Quick example

Here's a simple "Newsvendor" problem:

using JuMP
using LinearDecisionRules
using HiGHS
using Distributions

ldr = LinearDecisionRules.LDRModel(HiGHS.Optimizer)
set_silent(ldr)

@variable(ldr, buy >= 0, LinearDecisionRules.FirstStage)
@variable(ldr, sell >= 0)
@variable(ldr, demand in LinearDecisionRules.Uncertainty(distribution = Uniform(80, 120)))

@constraint(ldr, sell <= buy)
@constraint(ldr, sell <= demand)

@objective(ldr, Max, -10 * buy + 15 * sell)

optimize!(ldr)

objective_value(ldr)                              # Primal bound
objective_value(ldr; dual = true)                 # Dual bound
LinearDecisionRules.get_decision(ldr, buy)        # First-stage decision
LinearDecisionRules.get_decision(ldr, sell)       # Decision rule coefficients

For a detailed walkthrough, see Getting started with LinearDecisionRules.

Learn more

  • Tutorials: Step-by-step guides to learn LinearDecisionRules
  • Manual: Technical details and mathematical formulations
  • API Reference: Complete reference for all exported functions and types

Other Julia packages for stochastic programming include:

  • SDDP.jl: Stochastic Dual Dynamic Programming for multi-stage stochastic optimization problems
  • StochasticPrograms.jl: A framework for modeling and solving stochastic programs