---
title: "Beyond Prediction: Solving the Multiple Knapsack Problem at Scale: How Uber Optimizes Incentives"
description: "Uber’s Tarot platform frames incentive allocation as a Multiple Knapsack Problem (MKP), replacing FIFO contention handling and reactive budget management. It combines segmentation, budget pacing, uplift predictions, multi-objective value scoring, and a plug-and-play optimizer coordinated by an orchestrator. For each run, Tarot forms user-lever opportunities, predicts incremental ROI and cost, reconciles available budget, and selects assignments under team, business, and concurrency constraints before publishing them to domain services. The initial HiGHS linear programming approach took more than 24 hours to find a feasible solution for 100,000 users and one lever, while CP-SAT solved the same dataset in minutes and handled millions of users across multiple levers within stated SLA timeframes. The result is a production architecture that moves beyond heuristics by combining constraint programming with budget pacing, while future work targets automated exploration and model feedback."
---

# Beyond Prediction: Solving the Multiple Knapsack Problem at Scale: How Uber Optimizes Incentives

[Uber](https://yomu.fyi/company/uber) · May 14, 2026

**Type:** Explainer

## Summary

Uber’s Tarot platform frames incentive allocation as a Multiple Knapsack Problem (MKP), replacing FIFO contention handling and reactive budget management. It combines segmentation, budget pacing, uplift predictions, multi-objective value scoring, and a plug-and-play optimizer coordinated by an orchestrator. For each run, Tarot forms user-lever opportunities, predicts incremental ROI and cost, reconciles available budget, and selects assignments under team, business, and concurrency constraints before publishing them to domain services. The initial HiGHS linear programming approach took more than 24 hours to find a feasible solution for 100,000 users and one lever, while CP-SAT solved the same dataset in minutes and handled millions of users across multiple levers within stated SLA timeframes. The result is a production architecture that moves beyond heuristics by combining constraint programming with budget pacing, while future work targets automated exploration and model feedback.

## Context

Tarot addresses Uber’s incentive-allocation problem across multiple teams, lines of business, geographies, users, and concurrent treatments. The system must maximize incremental marketplace value while respecting separate quarterly budgets, limited concurrent offers, and interactions such as cross-vertical cannibalization.

## Approach / What changed

The orchestrator runs configurable workflows that ingest eligible users, generate user-lever opportunities, obtain uplift and cost predictions, calculate the available budget cap, and formulate an MKP optimization. A budget pacer controls spend velocity, while a multi-lever optimizer uses Google OR-Tools CP-SAT to select assignments that maximize value under the configured constraints before sending them to domain services.

## Takeaways

- Tarot replaces FIFO contention handling and manual targeting heuristics with optimization across eligible users, incentive levers, budgets, and predicted incremental value.
- The system moved from HiGHS linear programming to CP-SAT after HiGHS took more than 24 hours to find a feasible solution for 100,000 users and one lever; CP-SAT solved that dataset in minutes.
- Budget pacing reconciles configured, realized, and projected spend to calculate each run’s available cap, while the optimizer accounts for competing objectives such as Mobility and Delivery impact.

## FAQ

### Why did Tarot move from linear programming to CP-SAT?

The incentive-allocation problem was discrete and combinatorial, and HiGHS struggled as the search space grew. CP-SAT solved the 100,000-user, single-lever dataset in minutes instead of more than 24 hours and returned allocations for larger multi-lever tests within stated SLA timeframes.

### How does Tarot account for competing business objectives?

Tarot treats ROI as a multi-objective optimization problem rather than relying on one metric. Its prediction layer forecasts raw uplift across metrics such as Rides trips, Uber Eats orders, and driver utilization, allowing the optimization to account for interactions such as cross-vertical cannibalization.

### What role does budget pacing play in the workflow?

The Budget Pacer analyzes configured, realized, and projected spend to calculate the cap available for the current run. This cap is passed into optimization so selected assignments stay within the relevant budget constraints.

**Tags:** [Architecture](https://yomu.fyi/topic/architecture), [Machine Learning](https://yomu.fyi/topic/machine-learning), [Optimization](https://yomu.fyi/topic/optimization)

- Source: [Uber](https://www.uber.com/us/en/blog/solving-multiple-knapsack)
- Source URL: https://www.uber.com/us/en/blog/solving-multiple-knapsack
- Ingested by Yomu: 2026-09-14T08:01:22.666Z

[Read original post](https://www.uber.com/us/en/blog/solving-multiple-knapsack)