A Clustering Approach to Solving Large Stochastic Matching Problems

Milos Hauskrecht, Eli Upfal

TL;DR

This paper tackles the "curse of dimensionality" in large-scale stochastic contract matching problems, where the number of potential asset failure scenarios grows exponentially. By introducing a novel cluster-based approximation framework that groups similar failure configurations, the authors achieve near-optimal portfolio allocations with massive computational speedups compared to exact stochastic programming.

What Problem Does This Paper Address?

Consider a trader in a volatile market—such as electricity, gas, or telecommunications bandwidth. To maximize profit, the trader sells highly reliable, expensive contracts to clients and attempts to cover these obligations by purchasing cheaper, less reliable supply contracts. However, if these cheap supply contracts fail, the trader faces steep financial penalties.

To find the most profitable mix of buy and sell contracts, the problem is modeled as a two-stage stochastic linear program with recourse:

  1. Stage 1 (Allocation): Decide which portfolio of contracts to buy and sell.
  2. Stage 2 (Matching): After observing which supply contracts actually failed, optimally match the surviving buy contracts to the sell obligations to minimize penalty costs.

The core challenge is that if there are $q$ different buy contracts, there are $2^q$ possible failure combinations. For large-scale real-world applications, evaluating this exponential scenario space becomes completely intractable.

Figure 1: An example of contract asset matching. Nodes

Methods

To bypass the exponential complexity, the authors propose a cluster-based approximation approach alongside two simple greedy baselines (pairwise and diversified greedy).

Instead of optimizing over all $2^q$ failure configurations, the clustering method restricts the optimization to a small, manageable set of representative "cluster seeds." The key components include:

  • Scenario Dominance for Bounds: The authors define failure-dominance. If scenario A has a subset of the failures of scenario B, then scenario A failure-dominates B. Replacing scenarios with failure-dominating ones yields a mathematically guaranteed lower bound on expected profit. Conversely, replacing them with non-failure-dominating scenarios yields an upper bound.
  • Seed Ordering Heuristic: The order in which scenarios are assigned to clusters matters. The authors prove that sorting cluster seeds based on their subproblem objective values ($Q$-values) iteratively improves the tightness of the bound.
  • Incremental Seed Selection: To build a good set of clusters, the algorithm incrementally adds seeds by identifying the cluster with the largest remaining probability mass and randomly sampling a new seed configuration from within it.

Datasets

The paper does not use standard public benchmarks, as none existed for this specific problem formulation. Instead, the authors evaluate their approach on a synthetic but realistic problem instance representing a network with 6 buy contract types and 4 sell contract types, defining a complex web of admissible matchings.

Figure 2: Admissible matching for the problem with 6 buy

Key Insights and Ideas

  • Exploiting Monotonicity: The physics of the problem inherently helps. Because more failures can only ever decrease (or keep equal) the net profit, the scenario space possesses a monotonic structure that makes failure-dominance aggregation mathematically rigorous.
  • Dynamic Reordering via Subproblems: Rather than treating clustering as a separate, hard combinatorial preprocessing step, the authors realize that the second-stage optimization outputs ($Q$-values) provide the exact signal needed to optimize the cluster definitions on the fly.
  • Decision Convergence vs. Value Convergence: A crucial practical takeaway is that the optimal decision variables (how many contracts to buy/sell) converge to the true optimum much faster than the estimated expected profit value. You don't need a perfect approximation of your exact future returns to make the perfect choice today.

Key Results

The experimental results highlight a massive divide in computational efficiency:

  • Exact Solution: Finding the true mathematical optimum using standard linear programming packages took 352 minutes (nearly 6 hours).
  • Clustering Solution: By combining probability-based seed selection with $Q$-value reordering, the proposed method identified the exact optimal portfolio allocation using an average of just 22 clusters, reducing the runtime to a matter of seconds.

As shown in the evaluation plots, the probability-based selection with reordering tightly tracks the true optimal profit line well before reaching 30 clusters, vastly outperforming random cluster selection and basic greedy heuristics.

Figure 3: Average (lower) bound values (over 10 trials) and
Figure 4: Average running times of approximations for dif­ ferent number of clusters.

Limitations and Future Work

  • Unexploited Allocation Data: The current heuristics solely look at value estimates ($Q$-values) to refine clusters. They do not yet exploit the specific structural allocation differences between upper and lower bound clusterings.
  • Pruning Theory: The authors note that it remains an open theoretical question whether comparing upper and lower bound allocations can allow them to safely "prune" or eliminate sub-optimal contract options early in the calculation.
  • Integrality Proof: While all of their experiments naturally yielded integer solutions (which is ideal for discrete contracts), a formal mathematical proof for the integrality of this specific two-stage stochastic formulation remains an open issue.

Summary updated

Abstract

In this work we focus on efficient heuristics for solving a class of stochastic planning problems that arise in a variety of business, investment, and industrial applications. The problem is best described in terms of future buy and sell contracts. By buying less reliable, but less expensive, buy (supply) contracts, a company or a trader can cover a position of more reliable and more expensive sell contracts. The goal is to maximize the expected net gain (profit) by constructing a dose to optimum portfolio out of the available buy and sell contracts. This stochastic planning problem can be formulated as a two-stage stochastic linear programming problem with recourse. However, this formalization leads to solutions that are exponential in the number of possible failure combinations. Thus, this approach is not feasible for large scale problems. In this work we investigate heuristic approximation techniques alleviating the efficiency problem. We primarily focus on the clustering approach and devise heuristics for finding clusterings leading to good approximations. We illustrate the quality and feasibility of the approach through experimental data.
BibTeX
@inproceedings{hauskrecht2001clustering,
  author = {Milos Hauskrecht and Eli Upfal},
  title = {{A Clustering Approach to Solving Large Stochastic Matching Problems}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2001},
}
Figure