Admissible Heuristics via Linear Programming

21 concepts13 papers1 proposal

In complex structured search and optimization problems—such as automated planning, weighted constraint satisfaction, and program analysis—finding a cost-optimal solution requires an admissible heuristic. An admissible heuristic is a function that provides a guaranteed lower bound on the remaining cost to reach a goal state. If the heuristic never overestimates the true cost, search algorithms like A* are mathematically guaranteed to find the cheapest possible sequence of actions.

However, calculating a tight lower bound is historically challenging. In discrete combinatorial spaces, computing the exact cost-to-go is often as computationally expensive as solving the original problem. If we try to simplify the problem by breaking it into smaller subproblems or identifying individual milestones ("landmarks"), we face a secondary challenge: how do we combine the cost estimates of these pieces without double-counting the actions that satisfy multiple subproblems simultaneously?

The core insight of this research direction is that we can frame the derivation and maximization of admissible heuristics as a continuous optimization problem solved via Linear Programming (LP). By relaxing discrete combinatorial constraints into continuous equations, solvers can efficiently compute the tightest possible lower bounds in polynomial time.


The Core Intuition: Cost Partitioning and Continuous Relaxation

To understand why this approach works, consider the concept of cost partitioning. Suppose a planning problem requires executing a set of actions, each with an associated cost. If we decompose the main problem into several simpler, overlapping abstractions or subproblems, we can distribute the cost of each action across these subproblems. As long as the sum of an action's partitioned costs does not exceed its original true cost, the sum of the optimal heuristic values derived from each subproblem will strictly maintain admissibility.

Finding the optimal way to split these costs to maximize the final heuristic value is itself an optimization problem. In A* Search via Approximate Factoring, Haghighi et al. framed this challenge as a linear programming problem. By minimizing the difference between the true cost and the sum of factored estimates across overlapping projections, the LP optimization ensures the resulting heuristic is as tight as possible while strictly maintaining the lower-bound constraint across all local configurations.

The reason this meta-optimization is computationally tractable lies in continuous relaxation. Finding optimal lower bounds using discrete "cost movements" is traditionally an NP-hard problem. However, as proven by Cooper et al. in Optimal Soft Arc Consistency, relaxing the requirement for integer cost movements to rational numbers transforms the search for a maximum lower bound in weighted constraint satisfaction problems (WCSPs) into a continuous optimization task. This shift allows solvers to use efficient polynomial-time algorithms (such as the simplex or interior-point methods) to find the absolute tightest cost distributions.

Discrete Problem (NP-Hard)         Continuous Relaxation (Polynomial Time)
  [Integer Action Counts]    ───►    [Rational/Real Flow Variables]
  [Discrete Cost Shifts]     ───►    [Linear Programming Optimization]
                                                │
                                                ▼
                                     Tightest Admissible Lower Bound

Unifying Heuristics through Linear Programming Duality

Beyond merely calculating bounds, the LP framework reveals deep mathematical connections between seemingly disparate heuristic techniques.

In cost-optimal classical planning, researchers historically used two distinct approaches to bound costs:

  1. Cost Partitioning: Distributing action costs across different problem abstractions.
  2. Operator Counting: Using linear constraints to reason about the minimum number of times an action (operator) must be executed.

In Heuristics for Cost-Optimal Classical Planning Based on Linear Programming, Pommerening et al. demonstrated a fundamental mathematical duality between these two concepts. They showed that the process of optimally partitioning action costs is formally equivalent to solving the dual of an operator-counting linear program. This duality allows researchers to combine multiple independent heuristic constraints—such as landmarks, state equations, and landmarks—into a single, unified LP. The resulting heuristic is more informed than the sum of its individual parts because the LP globally optimizes the interactions between all constraints.

The flexibility of this framework was expanded further by Pommerening et al. in From Non-Negative to General Operator Cost Partitioning. While intuition suggests that action costs should always be non-negative, the authors proved that allowing general (including negative) cost partitions still preserves admissibility. This generalization mathematically unified a wider family of LP-based heuristics, allowing for significantly more accurate cost-to-go estimates and faster planning times.


Aggregating Landmarks and Subgoals

A practical application of this technique is the aggregation of "landmarks"—facts or milestones that must occur at least once in every valid plan.

If a problem has multiple landmarks, we cannot simply add their costs together, as a single action might satisfy multiple landmarks at once. To resolve this:

  • Karpas et al. introduced the LM-A* algorithm in Cost-Optimal Planning with Landmarks, employing linear programming to optimize the distribution of costs among multiple required landmarks. This framework identifies an allocation that maximizes the heuristic's informativeness while preventing overestimation.
  • Wang et al. extended this in Planning with Multi-Valued Landmarks by formulating heuristic cost estimation as an integer programming problem. By minimizing total plan cost subject to lower and upper bound constraints on action frequencies, their approach aggregates local landmark information into a globally consistent estimate of remaining effort.

Extending to Numeric and Continuous Domains

The power of LP-based heuristics becomes especially pronounced when moving from classical discrete planning to numeric planning, where states are defined by both discrete facts and continuous variables (such as fuel levels, resource capacities, or coordinates).

As noted by Scala et al. in Heuristics for Numeric Planning via Subgoaling, achieving cost-optimal solutions in numeric domains is notoriously difficult due to a severe scarcity of admissible heuristics. Because numeric variables can be satisfied through an infinite variety of action sequences and repetitions, calculating a guaranteed lower bound in these metric spaces is highly challenging.

To address this, Scala et al. leveraged linear programming in Landmarks for Numeric Planning Problems. By representing numeric requirements as regions in a metric space, they used an LP to aggregate the costs of multiple landmarks, calculating the minimum number of action repetitions needed to satisfy all numeric and logical requirements simultaneously.

As synthesized by Haslum et al. in Subgoaling Techniques for Satisficing and Optimal Numeric Planning, formulating numeric planning tasks as Linear Programming or Mixed Integer Programming (MIP) tasks allows the solver to capture complex interactions between continuous variables. This mathematical framework yields tight, admissible lower bounds that drastically reduce the state space a planner must explore to guarantee an optimal solution.


Cross-Domain Applications

The underlying principle—using linear programming to resolve cost-sharing equations or synthesize lower bounds—extends well beyond classical AI planning:

  • Probabilistic Inference: In Cost-Sharing in Bayesian Knowledge Bases, Shimony et al. demonstrated that solving cost-sharing equations via linear programming provides an efficient, admissible method for finding the most probable inferences in Bayesian Knowledge Bases (BKBs), successfully overcoming potential infinite loops caused by cyclic causal dependencies.
  • Program Verification: In Differential cost analysis with simultaneous potentials and anti-potentials, Žikelić et al. automated the synthesis of resource cost bounds (such as memory or runtime differences between program versions) by reducing the constraint satisfaction problem to a linear program.
  • Online Algorithms: In Optimal Competitive Ratio for Optimization Problems with Congestion Effects, Fischer et al. utilized modified cost functions derived from a specific linear program to design online resource allocation algorithms that achieve theoretically optimal competitive ratios under congestion effects.

By transitioning from discrete, combinatorial counting to continuous, optimized cost-sharing, linear programming serves as a foundational engine for generating powerful, admissible heuristics across diverse computer science domains.

Key Foundational Work

Optimal Soft Arc Consistency (2007) — contributed 3 concept elements to this direction.
Cost-Sharing in Bayesian Knowledge Bases (1997) — contributed 2 concept elements to this direction.
A* Search via Approximate Factoring (2007) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 13 papers
  2. Version 1 · 2026-10-04 · 18 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_admissible_numeric_heuristics_d77ca66d,
  title = {admissible numeric heuristics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/admissible-numeric-heuristics/rdr_d77ca66d438047e2aec3f0e28538d31f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_admissible_numeric_heuristics_d77ca66d_v2,
  title = {admissible numeric heuristics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/admissible-numeric-heuristics/rdr_d77ca66d438047e2aec3f0e28538d31f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake