Adjustable Robust Optimization

Adjustable Robust Optimization#

Static robust optimization protects against uncertainty by requiring feasibility for every realization before the uncertain parameters are revealed. This is often too conservative: in many practical settings some decisions can be deferred until after part of the uncertainty is observed.

Adjustable robust optimization (ARO) [Ben-Tal et al., 2004] models this two-stage structure explicitly:

Stage	Variables	When decided	Must satisfy
1 (here-and-now)	$x$	Before observing $\xi$	Constraints for all $\xi \in \mathcal{U}$
2 (wait-and-see)	$y(\xi)$	After observing $\xi$	Constraints for the actual $\xi$

The two-stage minimax problem is:

\[ \min_{x} \max_{\xi \in \mathcal{U}} \min_{y} \; f(x, y) \quad \text{s.t.}\; g(x, y, \xi) \le 0 \]

Affine Decision Rules#

Optimizing over arbitrary functions $y(\xi)$ is generally intractable. The affine decision rule (ADR) approximation [Ben-Tal et al., 2004] restricts recourse to affine functions of the uncertainty:

\[ y(\xi) = y_0 + \sum_{j=1}^{n_\xi} Y_j \cdot \xi_j, \qquad \xi_j = p_j - \bar{p}_j \]

where $y_0$ (intercept) and $Y_j$ (policy columns) become ordinary decision variables. The ADR is optimal for problems where the feasible set is convex and uncertainty enters linearly [Ben-Tal et al., 2004]. For general nonlinear recourse it is an inner approximation.

The power of affine rules over static robust optimization was studied by Bertsimas and Goyal [2012]: they show that for LP problems with uncertain right-hand sides, affine rules are optimal; for uncertain constraint matrices they can be suboptimal.

discopt Pipeline#

Nominal model  →  AffineDecisionRule.apply()  →  RobustCounterpart.formulate()
(has y, ξ)        (y → y₀ + ΣYⱼξⱼ;              (ξ → worst-case constant;
                   y retired from variables)        model is deterministic)
                        ↓
                  Deterministic model: optimize over (x, y₀, Y_cols)

import os

os.environ["JAX_PLATFORMS"] = "cpu"
os.environ["JAX_ENABLE_X64"] = "1"

import discopt.modeling as dm
from discopt.ro import AffineDecisionRule, BoxUncertaintySet, RobustCounterpart

Example 1 — Two-Stage Inventory Management#

A retailer places a first-stage order $x$ before observing demand, then can place a second-stage emergency order $y$ once demand $d$ is known. The emergency order is more expensive ($c_2 = 8$ vs $c_1 = 2$). Demand is uncertain: $d \in [60, 100]$ with nominal $\bar{d} = 80$.

\[ \min_{x, y(d)}\; 2x + 8y \quad \text{s.t.}\; x + y \ge d,\; 0 \le x \le 200,\; 0 \le y \le 100 \]

We compare three approaches: nominal (ignore uncertainty), static robust (worst-case $d=100$), and adjustable robust (recourse adapts to realized demand).

c1, c2 = 2.0, 8.0
d_bar, delta = 80.0, 20.0


def build(name):
    m = dm.Model(name)
    x = m.continuous("order", lb=0, ub=200)
    y = m.continuous("emergency", lb=0, ub=100)
    d = m.parameter("d", value=d_bar)
    m.minimize(c1 * x + c2 * y)
    m.subject_to(x + y >= d, name="demand")
    return m, x, y, d


# --- Nominal ---
m_nom, _, _, _ = build("nominal")
r_nom = m_nom.solve()
print(f"Nominal (d=80):    obj = {r_nom.objective:.2f},  {r_nom.x}")

# --- Static robust ---
m_stat, _, _, d_stat = build("static")
RobustCounterpart(m_stat, BoxUncertaintySet(d_stat, delta=delta)).formulate()
r_stat = m_stat.solve()
print(f"Static  (d<=100):  obj = {r_stat.objective:.2f},  {r_stat.x}")

# --- Adjustable robust ---
m_adj, x_adj, y_adj, d_adj = build("adjustable")
adr = AffineDecisionRule(y_adj, uncertain_params=d_adj)
adr.apply()
RobustCounterpart(m_adj, BoxUncertaintySet(d_adj, delta=delta)).formulate()
r_adj = m_adj.solve()
print(f"ADR     (d<=100):  obj = {r_adj.objective:.2f},  {r_adj.x}")
print(f"\nADR policy: Y0 = {r_adj.x['adr_Y0']:.4f}")
print("  Y0~0 means no adaptation (same as static)")
print("  Y0~1 would mean full adaptation to demand")

Nominal (d=80):    obj = 160.00,  {'order': array(80.), 'emergency': array(0.)}
Static  (d<=100):  obj = 200.00,  {'order': array(100.), 'emergency': array(0.)}
ADR     (d<=100):  obj = 200.00,  {'order': array(100.), 'adr_intercept': array(-0.), 'adr_Y0': array(-0.), 'ro_abs0': array(1.), 'ro_abs1': array(-0.), 'ro_abs2': array(0.), 'ro_abs3': array(0.)}

ADR policy: Y0 = -0.0000
  Y0~0 means no adaptation (same as static)
  Y0~1 would mean full adaptation to demand

In this example, the here-and-now order $x$ is cheap ($2) while the emergency recourse $y$ is expensive ($8). The ADR recovers the static robust solution because the optimal strategy is to order everything upfront at the cheap price rather than wait. The ADR correctly sets $Y_0 \approx 0$ (no adaptation), confirming that recourse has no value when the first-stage option dominates on cost.

For ADR to strictly outperform static robust, the uncertainty must enter constraints in opposing directions so that static must over-hedge while the adaptive policy can compensate. The next example demonstrates this.

Example 2 — ADR Beats Static: Opposing Uncertainty (Ben-Tal et al. 2004)#

This minimal example, based on the structure in Ben-Tal et al. [2004], is the canonical case where ADR strictly outperforms static robust. The uncertain parameter $z$ enters two constraints with opposite signs:

\[ \min_x\; x \quad \text{s.t.}\; x + y \ge 1 + z, \quad x - y \ge 1 - z, \quad z \in [-1, 1] \]

The static solution must simultaneously hedge against $z = +1$ (constraint 1) and $z = -1$ (constraint 2), requiring $x = 2$. The ADR sets $y(z) = z$, which perfectly counteracts the uncertainty in both constraints, needing only $x = 1$. This is a 50% reduction in cost.

# --- Static robust ---
ms = dm.Model("static")
xs = ms.continuous("x", lb=0, ub=10)
ys = ms.continuous("y", lb=-10, ub=10)
zs = ms.parameter("z", value=0.0)
ms.minimize(xs)
ms.subject_to(xs + ys >= 1.0 + zs, name="c1")
ms.subject_to(xs - ys >= 1.0 - zs, name="c2")
RobustCounterpart(ms, BoxUncertaintySet(zs, delta=1.0)).formulate()
r_s = ms.solve()
print(f"Static:  obj = {r_s.objective:.2f},  x = {r_s.x['x']:.2f},  y = {r_s.x['y']:.2f}")

# --- Adjustable robust (ADR) ---
ma = dm.Model("adjustable")
xa = ma.continuous("x", lb=0, ub=10)
ya = ma.continuous("y", lb=-10, ub=10)
za = ma.parameter("z", value=0.0)
ma.minimize(xa)
ma.subject_to(xa + ya >= 1.0 + za, name="c1")
ma.subject_to(xa - ya >= 1.0 - za, name="c2")
adr = AffineDecisionRule(ya, uncertain_params=za)
adr.apply()
RobustCounterpart(ma, BoxUncertaintySet(za, delta=1.0)).formulate()
r_a = ma.solve()
Y0 = r_a.x["adr_Y0"]
y0 = r_a.x["adr_intercept"]
print(f"ADR:     obj = {r_a.objective:.2f},  x = {r_a.x['x']:.2f}")
print(f"         y(z) = {y0:.2f} + {Y0:.2f}*z")

saving = r_s.objective - r_a.objective
print(f"\nADR saves {saving:.0f} ({saving / r_s.objective * 100:.0f}%)")
print("\nVerification at extreme realizations:")
for z_val in [-1.0, 0.0, 1.0]:
    y_val = y0 + Y0 * z_val
    c1 = r_a.x["x"] + y_val - (1 + z_val)
    c2 = r_a.x["x"] - y_val - (1 - z_val)
    print(f"  z={z_val:+.0f}: y={y_val:+.2f}, c1={c1:.2f}, c2={c2:.2f}")

Static:  obj = 2.00,  x = 2.00,  y = -0.00
ADR:     obj = 1.00,  x = 1.00
         y(z) = -0.00 + 1.00*z

ADR saves 1 (50%)

Verification at extreme realizations:
  z=-1: y=-1.00, c1=0.00, c2=0.00
  z=+0: y=+0.00, c1=0.00, c2=0.00
  z=+1: y=+1.00, c1=0.00, c2=0.00

API Summary#

from discopt.ro import AffineDecisionRule, BoxUncertaintySet, RobustCounterpart

# 1. Build nominal two-stage model
m = dm.Model()
x = m.continuous("x", ...)                  # here-and-now
y = m.continuous("y", ...)                  # wait-and-see (recourse)
p = m.parameter("p", value=nominal)         # uncertain parameter
# ... build objective and constraints ...

# 2. Apply affine decision rule  y → y₀ + Y₀·(p - p̄)
adr = AffineDecisionRule(y, uncertain_params=p)   # or list of params
adr.apply()                                        # modifies m in-place

# 3. Apply static robust counterpart for remaining uncertainty
rc = RobustCounterpart(m, BoxUncertaintySet(p, delta=0.1 * nominal))
rc.formulate()                                     # modifies m in-place

# 4. Solve — decision variables are now (x, y₀, Y₀)
result = m.solve()

After apply():

adr.intercept — the $y_0$ variable
adr.policy_columns — list of $Y_j$ variables
adr.affine_expression — the full expression $y_0 + \sum_j Y_j \xi_j$
adr.perturbations — list of perturbation expressions $\xi_j = p_j - \bar{p}_j$
adr.n_policy_columns — total number of scalar uncertain components

Theoretical Guarantees and Limitations#

Optimality Ben-Tal et al. [2004]: For LP problems with uncertainty appearing only in the right-hand side, affine decision rules are optimal — no other measurable recourse policy achieves a lower cost.

Sub-optimality Bertsimas and Goyal [2012]: For uncertain constraint matrices (i.e., $A(\xi)x \le b(\xi)$), affine rules may be sub-optimal. In these cases they serve as a tractable inner approximation.

Current limitations in discopt’s implementation:

Recourse variables must be scalar or 1-D.
The policy matrix scales as $\dim(y) \times n_\xi$ new scalar variables, which can be large for high-dimensional problems.
Non-affine recourse (polynomial, piecewise-linear) is not yet supported.

Stage	Variables	When decided	Must satisfy
1 (here-and-now)	\(x\)	Before observing \(\xi\)	Constraints for all \(\xi \in \mathcal{U}\)
2 (wait-and-see)	\(y(\xi)\)	After observing \(\xi\)	Constraints for the actual \(\xi\)