LP Models

The modeling approach used in the research that is the subject of the website dates back to the mid-2000’s (Diaby (2006; 2007)). For the purpose of simplicity in exposition, we have generally presented our developments within the framework of the traveling salesman problem (TSP). However, the modeling approach is directly applicable to many of the other NP-Complete problems (Diaby (2010a; 2010b)), as well as the quadratic assignment problem (QAP; Diaby (2006)). For the TSP, the model does not involve the city-to-city variables-based, traditional TSP polytope referred to in the literature as “the TSP polytope.” We do not model Hamiltonian cycles of the cities explicitly. Instead, we use a time-dependent representation in order to abstract TSP tours.

The early models were O(n9) models. These are regrouped and discussed in detail in Diaby and Karwan (2016). The current model is a O(n6) “analog” of those O(n9) models. It is a more direct extended formulation (EF) of the linear assignment problem (LAP) polytope in which arcs are not explicitly modeled. It is an exact LP formulation of the TSP (as are our O(n9) models also)  in the sense that it has integral extreme points which are in one-to-one correspondence with TSP tours. It also applies very straightforwardly to the Quadratic Assignment Problem (QAP).

Latest Developments

Manuscript:

Diaby, M., M.H. Karwan, and L. Sun (January 2022). Exact extended formulation of the linear assignment problem (LAP) polytope for solving the traveling salesman and quadratic assignment problems.

C# Executables:

Basic LP Generator/Solver and Extended LP Generator/Solver (Source codes are available from the authors upon request.)