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 model which was initially the subject of this site is an O(n6) model, which we had erroneously believed to be an “analog” of those O(n9) models. Details on the counter-examples (to this O(n6) model) will be made available at a future time.
The increase insight gained through the study of the counter-examples and their “construction” method allowed us to develop a much more streamlined but also generic version of our earlier O(n9) models. Copies of both the erroneous O(n6) model and the generic O(n9) model are provided below, under “Latest Manuscripts.”
Latest Manuscripts
Streamlined, Generic O(n9) model :
Initial O(n6) model (Erroneous) :
Original Models
Diaby, M. and M.H. Karwan (2016). Advances in combinatorial optimization: linear programming formulations of the traveling salesman and other hard combinatorial optimization problems. World Scientific Publishing.