In this paper, we present a new linear programming (LP) formulation of the Traveling Salesman Problem (TSP). The proposed model has O(n^8) variables and O(n^7) constraints, where n is the number of cities. Our numerical experimentation shows that com
putational times for the proposed linear program are several orders of magnitude smaller than those for the existing model [3].
In this paper, we present a new, graph-based modeling approach and a polynomial-sized linear programming (LP) formulation of the Boolean satisfiability problem (SAT). The approach is illustrated with a numerical example.
This paper has been withdrawn because Theorem 21 and Corollary 22 are in error; The modeling idea is OK, but it needs 9-dimensional variables instead of the 8-dimensional variables defined in notations 6.9. Examples of the correct model (with 9-ind
ex variables) are: (1) Diaby, M., Linear Programming Formulation of the Set Partitioning Problem, International Journal of Operational Research 8:4 (August 2010) pp. 399-427; (2) Diaby, M., Linear Programming Formulation of the Vertex Coloring Problem, International Journal of Mathematics in Operational Research 2:3 (May 2010) pp. 259-289; (3) Diaby, M., The Traveling Salesman Problem: A Linear Programming Formulation, WSEAS Transactions on Mathematics, 6:6 (June 2007) pp. 745-754.
