Logic constraint satisfaction problems (CSPs) are in general NP-hard, and no general deterministic polynomial-time algorithm is known. Several logic constraint problems can be reduced in polynomial time to the satisfaction of a conjunctive normal form (CNF-SAT). The paper presents a technique to transform a CNF-SAT problem into an integer optimization problem that can be solved by linear programming. The integer program grows polynomially in comparison to the size of the original problem.

The author notes that some CSPs can be reduced to maximal matching problems in bipartite graphs. For general CSPs, a similar statement can be made for hypergraphs. The key is to find those CSPs that have natural forms as bipartite hypergraphs. It is known that unimodular hypergraphs are a generalization of bipartite graphs. Thus the CNF-SAT can be solved. The paper shows the requisite transformations to transform the CNF-SAT problem to an integer linear program, which can be solved without worrying about integrality constraints.

A toy example illustrates the transformations. The 59 references are helpful. The paper is a good blend of graph theory, complexity theory, and a practical problem. Readers will find no program codes to allow them to attack large problems.