🔢 mathematics

Learning Optimization Proxies for Sequential Contextual Stochastic Programs: An Order Fulfillment Application

This paper proposes a learning-based optimization proxy that combines a scenario-embedded neural network with a feasibility-enforcing decoder to solve sequential contextual stochastic programs for omnichannel order fulfillment, achieving sub-second decision latency while significantly reducing fulfillment costs and late-delivery rates compared to traditional solvers and established policies.

Original authors: Tinghan Ye, Shuaicheng Tong, Changkun Guan, Beste Basciftci, Pascal Van Hentenryck

Published 2026-06-25

📖 4 min read🧠 Deep dive

CC0 1.0

Original authors: Tinghan Ye, Shuaicheng Tong, Changkun Guan, Beste Basciftci, Pascal Van Hentenryck

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, super-fast online store (like JD.com). Every second, thousands of customers place orders. Your job is to decide immediately where to ship each item from and which delivery truck to use.

This isn't just a simple "pick the closest warehouse" game. It's a high-stakes puzzle with three big problems:

Uncertainty: You don't know exactly when the truck will arrive (traffic, weather) or how many more orders will come in the next hour.
Inventory: If you send a popular item from Warehouse A to a customer now, you might not have it left for a customer who orders it 10 minutes later.
Speed: You have less than a second to make this decision. If you wait too long to calculate the "perfect" answer, the customer gets angry, and the system crashes.

The Old Way: The "Super-Computer" That's Too Slow

Traditionally, to solve this, companies use a "Super-Computer" (an optimization solver). It looks at all the possible future scenarios (what if it rains? what if 1,000 more people order shoes?) and calculates the mathematically perfect plan.

The Good: It finds a very good plan.
The Bad: It takes seconds or even minutes to run. In a real-time system where you need an answer in milliseconds, this is useless. It's like trying to solve a Sudoku puzzle with a supercomputer while a race car is speeding past you.

The New Way: The "Smart Proxy" (The Paper's Solution)

The authors built a Learning-Based Optimization Proxy. Think of this as a super-smart intern who has studied the Super-Computer's answers for months.

Here is how the "intern" works:

The Training (Offline):
The intern sits in a quiet room (offline) and watches the Super-Computer solve thousands of fake order scenarios. It memorizes the patterns: "When it's raining and the customer is in New York, the Super-Computer usually picks Warehouse B." It learns to mimic the expert.
The "Scenario-Embedded" Brain:
Unlike a normal AI that just guesses, this intern is scenario-aware. It doesn't just look at the current order; it looks at a "crystal ball" of possible futures (scenarios) generated by the system. It asks, "If I pick Warehouse A now, what happens to my inventory for the next 100 orders?" It understands the ripple effects.
The "Decoder" (The Safety Net):
Sometimes the intern makes a mistake and suggests a plan that is impossible (like shipping 5 items when the warehouse only has 3). To fix this, the system has a Decoder.
- Analogy: Imagine the intern writes a shopping list. The Decoder is the store manager who checks the shelves. If the list says "5 apples" but the shelf only has "3," the manager instantly adjusts the list to "3 apples" and moves the rest to a different store. This happens in a split second, ensuring the plan is always legal and feasible.
The Result:
Instead of waiting minutes for the Super-Computer, the intern gives an answer in milliseconds (a single forward pass).

What Did They Find?

The team tested this system using real data from JD.com in a simulation. Here are the results:

Speed: The new system is 2,800 times faster than the old Super-Computer method. It goes from taking seconds to taking a fraction of a second.
Cost: Even though it's faster, it actually saved 3.3% more money than the slow Super-Computer method.
Customer Satisfaction: Compared to the standard rules companies use today, this new system cut late deliveries in half and saved over 10% in total costs.

The Big Picture

This paper proves that you don't have to choose between speed and quality. By training a neural network to act like an expert optimizer, and then adding a quick "safety check" (the decoder) to fix any impossible moves, you can make near-perfect decisions in real-time.

It's like replacing a slow, perfect chess grandmaster with a lightning-fast grandmaster who has memorized the best moves and has a referee to instantly correct any illegal moves. The result is a system that is both fast and smart, keeping customers happy and costs low.

Technical Summary: Learning Optimization Proxies for Sequential Contextual Stochastic Programs

Problem Formulation

The paper addresses the challenge of sequential contextual stochastic programs in real-time decision systems, specifically focusing on omnichannel order fulfillment in large-scale e-commerce. In this setting, a decision maker must assign arriving orders to distribution centers (DCs) and carrier services under uncertainty regarding delivery times and future demand.

The core difficulty lies in the latency constraint: while high-quality decisions can be generated offline using Contextual Sample Average Approximation (C-SAA) solved by commercial optimization solvers, these solvers typically require seconds to minutes per instance. This is insufficient for peak operational periods (e.g., holiday sales) where sub-second responses are required to handle hundreds of orders per minute. Consequently, operational systems often revert to simpler heuristics that ignore modeled uncertainty, leading to suboptimal costs and service levels.

The problem is formalized as a two-stage contextual stochastic program:

First Stage: Immediate assignment of an order's products to DCs and carriers based on current context (order attributes, inventory levels, carrier costs) and sampled scenarios of future uncertainty.
Second Stage: Aggregated recourse for future orders ( $t+1 \dots T$ ), representing the expected future shipping and stockout costs given the inventory consumed by the first-stage decision.

The objective is to minimize total expected costs, including shipping, asymmetric delivery-time penalties (late vs. early), consolidation discounts, and stockout penalties, while respecting inventory constraints.

Methodology

The authors propose a learning-based optimization proxy that replaces the per-epoch solver call with a single forward pass of a neural network, followed by a feasibility-enforcing decoder.

1. Architecture: Scenario-Embedded Hierarchical Neural Network
Unlike prior optimization proxies that rely on point forecasts, this model is scenario-aware. It takes as input:

Contextual Features: Order details, DC inventory states, and carrier cost matrices.
Scenario Sets: Sampled realizations of future demand and delivery-time deviations, generated by fitted forecasters (Multi-Horizon Quantile RNN for demand, Multi-Quantile MLP for delivery times).

The network employs a DeepSets-style encoder to process unordered scenario sets, averaging embeddings to approximate the expectation structure of the C-SAA objective. The architecture is hierarchical:

DC Head: Predicts a logit for each distribution center.
Carrier Head: Predicts a logit for each carrier service conditional on the selected DC.
This factorization ( $p(j) \cdot p(k|j)$ ) reduces the complexity of learning the full joint assignment space.

2. Training Strategy: Composite Loss Function
The proxy is trained offline on labels generated by the C-SAA solver. The training objective combines three terms:

Label Imitation (Selection Loss): Cross-entropy loss against the primary DC and carrier choices derived from the C-SAA solution.
Constraint Violation Penalty: A self-supervised term using Straight-Through Gumbel-Softmax to penalize assignments that exceed available inventory, ensuring the model learns to respect hard constraints.
Cost Alignment: A self-supervised regularizer that pulls probability mass toward low-cost (DC, carrier) pairs based on the immediate costs observed in the sampled scenarios.

3. Inference: Inventory-Weighted Decoding
At runtime, the neural network outputs logits which are converted to probabilities. A dedicated decoder then enforces feasibility:

It reweights the predicted probabilities by the fractional inventory coverage ( $min\{Inv/q, 1\}$ ) of each DC.
It performs a greedy scan of eligible DCs and carriers, assigning demand until the order is fulfilled or inventory is exhausted.
This process ensures the final decision is strictly feasible (respecting inventory caps and demand satisfaction) in $O(|J| \log |J| + |J||K|)$ time.

Key Contributions

The paper makes four primary contributions:

Scenario-Conditioned Proxy: A novel architecture that explicitly conditions on sampled scenario sets rather than point forecasts, capturing both immediate stochastic costs and the sequential impact of resource consumption.
Sequential Fulfillment Model: A two-stage contextual stochastic formulation that explicitly links immediate order assignments to the opportunity cost of inventory consumption for future orders.
Theoretical Guarantees: The authors prove that the inventory-weighted decoder yields a feasible decision with logarithmic-linear runtime complexity. They further establish that the proxy's expected cost upper-bounds the optimal two-stage objective and that its out-of-sample performance admits unbiased, consistent estimators.
Empirical Validation: A comprehensive computational study using a simulator calibrated with JD.com transactional records and proprietary carrier data.

Results

In the calibrated simulator, the proposed proxy demonstrates significant improvements over both solver-based baselines and established heuristic policies:

Latency: Decision latency is reduced by approximately 2,800× compared to the online finite-sample C-SAA reference, enabling sub-second responses.
Cost Efficiency: The proxy improves realized fulfillment costs by 3.3% relative to the C-SAA baseline (which is already high-quality but slow) and reduces total realized costs by at least 10.7% compared to established fulfillment policies.
Service Level: The proxy roughly halves the late-delivery rate of the strongest classical baselines, directly improving the on-time delivery metric that drives customer satisfaction.

Significance

The paper argues that for high-volume, latency-critical operations like e-commerce fulfillment, the trade-off between optimization quality and computational speed is a critical bottleneck. By developing a proxy that learns from solver-generated labels while explicitly modeling uncertainty through scenarios, the authors demonstrate that it is possible to achieve near-optimal decision quality with real-time inference speeds. This approach bridges the gap between the theoretical benefits of contextual stochastic optimization and the practical constraints of industrial-scale, real-time decision-making systems. The work suggests that such proxies can be a viable alternative to heuristics in settings where traditional solvers are too slow to be deployed online.