# Applying Predicate Detection to the Constrained Optimization Problems

Source: [Applying Predicate Detection to the Constrained Optimization Problems](<https://www.sota2.com/research/paper/68fa65381e209131cea0918d>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T21:21:52.901Z

Authors: Vijay K. Garg

Published: 2018-12-26T17:57:02.000Z

## Abstract

We present a method to design parallel algorithms for constrained combinatorial optimization problems. Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path problem and the market clearing price problem. These three problems are solved in the literature using Gale-Shapley algorithm, Dijkstra's algorithm, and Demange, Gale, Sotomayor algorithm. Our method solves all these problems by casting them as searching for an element that satisfies an appropriate predicate in a distributive lattice. Moreover, it solves generalizations of all these problems - namely finding the optimal solution satisfying additional constraints called {\\em lattice-linear} predicates. For stable marriage problems, an example of such a constraint is that Peter's regret is less than that of Paul. For shortest path problems, an example of such a constraint is that cost of reaching vertex $v\_1$ is at least the cost of reaching vertex $v\_2$. For the market clearing price problem, an example of such a constraint is that $item\_1$ is priced at least as much as $item\_2$. In addition to finding the optimal solution, our method is useful in enumerating all constrained stable matchings, and all constrained market clearing price vectors.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1812.10431>)

[PDF](<https://arxiv.org/pdf/1812.10431.pdf>)
