Every home Opendoor buys needs a renovation decision made in hours: replace the carpet, update the kitchen, repaint, fix the HVAC — or some subset of those. Each upgrade costs money, takes time, and generates value. But the upgrades interact. You can't paint before the drywall is done. You can't install flooring before the subfloor is repaired. And every extra day the home sits in inventory costs money.
The naive approach — estimate ROI per upgrade, pick the top ones — is mathematically wrong. And at 10,000 active homes it's also computationally impossible.
Three Things That Make This Hard
1. Dependencies create a critical path
Upgrades form a DAG — directed acyclic graph — where some must finish before others can start. The total project duration isn't the sum of all upgrades; it's the longest chain through whatever subset you select. Pick two upgrades that happen to be sequential, and your timeline doubles. Pick two that are parallel, and it stays the same. Which upgrades you choose directly determines how long you hold the asset.
2. Diminishing returns
The second bathroom adds more value than the third. A fresh coat of paint lifts the listing; a second coat doesn't. This is submodularity — the marginal value of any upgrade shrinks when more upgrades have already been done. Plus, you can never exceed the local market price ceiling no matter how much you renovate.
3. Holding cost compounds against you
While the renovation runs, the asset accrues capital costs, insurance, property taxes, and market risk. Modeled as continuous compounding at rate , this means the resale value you actually capture is — discounted by every day you hold it.
The Objective
The net yield from choosing upgrade set :
Time-discounted resale value, minus total capex, minus acquisition cost. Maximizing this subject to dependency closure and budget constraints is a Mixed-Integer Non-Linear Program — NP-hard with three interlocking sources of complexity. Exact solvers tap out around 30–40 upgrades per home.
The Three-Phase Heuristic That Ships
Phase 1: Prune the obvious losers
For each upgrade, compute the standalone marginal yield rate — net value per unit time, accounting for its full prerequisite chain. Any upgrade that's net-negative gets pruned, and anything that only existed to enable a pruned upgrade gets pruned transitively. Iterate until stable. This typically eliminates 40–70% of the DAG before the main algorithm runs.
Phase 2: Greedy forward selection on the DAG
On the pruned graph, greedily add upgrades in order of marginal yield gain. Only upgrades whose predecessors are already selected are eligible. The critical path is updated incrementally. Stop when nothing improves the yield.
Phase 3: Local search refinement
For each selected upgrade and each unselected one, test whether swapping improves yield. Run for 100 iterations. This catches cases where the greedy ordering was suboptimal due to interactions between upgrades.
Total complexity per home: sub-millisecond after pruning (typically fewer than 50 upgrades remain).
Scaling to 10,000 Homes
Each home's optimization is completely independent — embarrassingly parallel. Fan out across a worker pool, then aggregate with a portfolio-level knapsack: given each home's optimal yield and cost, select which homes to invest in subject to total portfolio budget.
Asset Queue (10,000 homes)
│ Fan-out
┌────┼────┐
▼ ▼ ▼
Worker 1 Worker 2 ... (64 workers)
Phase 1 Phase 1
Phase 2 Phase 2
Phase 3 Phase 3
└────┼────┘
▼
Portfolio Budget Knapsack
→ Which homes to invest in at all,
given total portfolio budget B_total| Problem size | Recommended method |
|---|---|
| ≤ 30 upgrades | Exact MINLP solver (BARON / SCIP) |
| 30–100 upgrades | Branch-and-bound with Lagrangian decomposition |
| 100–500 upgrades | Metaheuristic (GA or Simulated Annealing) |
| 500+ or 10,000-home batch | Three-phase greedy pipeline (this post) |
Benchmarked against exact solutions on instances where exact is feasible (≤ 40 upgrades), the heuristic lands within 5–15% of optimal.
The counterintuitive result: reducing holding cost rate has a larger impact on net yield than increasing the upgrade value estimates. Speed of execution — not renovation quality — is the dominant variable.