  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.

Data Structures and Algorithms