Polynomial Time Linear Programs for Hard Constraint Satisfaction Problems

A recent result shows that a LP model with 0/1 values is of polynomial complexity.

The paper reports a model for some important NP hard problems, such as the Propositional Satisfiability Problem, the Traveling Salesperson Problem, and the Minimal Set Covering Problem, by means of only two types of constraints: 'choice constraints'and 'exclusion constraints'.

The article presents a linear 0/1 Simplex for solving the obtained integer program. This algorithm always finds a 0-1 integer solution that corresponds to a solution of the Constraint Satisfaction Problem and vice versa.

The paper presents the results of experiments for solving a Conjunctive Normal Form hard cases by linear programming in polynomial time, confirming in practice the polynomial Acceleration of the Simplex SAT solver by means of intelligent pivot selection through neural networks is also decribed.

There are several practical application of our approach: Agriculture production planning; Industry manifacturing and service; Engineering; Financial management; and, of course, transportation.