BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Moustapha Diaby appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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 computational 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.
We provide a numerical refutation of the developments of Fiorini et al. (2015)* for models with disjoint sets of descriptive variables. We also provide an insight into the meaning of the existence of a one-to-one linear map between solutions of such models. *: Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2015). Exponential Lower Bounds for Polytopes in Combinatorial Optimization. Journal of the ACM 62:2, Article No. 17.
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-index 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.
We show that new definitions of the notion of "projection" on which some of the recent "extended formulations" works (such as Kaibel (2011); Fiorini et al. (2011; 2012); Kaibel and Walter (2013); Kaibel and Weltge (2013) for example) have been based can cause those works to over-reach in their conclusions in relating polytopes to one another when the sets of the descriptive variables for those polytopes are disjoint.
In this paper, we present a polynomial-sized linear programming formulation of the Traveling Salesman Problem (TSP). The proposed linear program is a network flow-based model. Numerical implementation issues and results are discussed. (The exposition and proofs are much more detailed in an edition which I wrote in collaboration with Dr. M.H. Karwan in 2012-2014 . That edition is available at http://users.business.uconn.edu/mdiaby/P=NPProofPapers/tspPaper.pdf)
In this paper, we introduce the notion of augmentation for polytopes and use it to show the error in two presumptions that have been key in arriving at over-reaching/over-scoped claims of "impossibility" in recent extended formulations (EF) developments. One of these presumptions is that: "If Polytopes P and Q are described in the spaces of variables x and y respectively, and there exists a linear map x=Ay between the feasible sets of P and Q, then Q is an EF of P". The other is: "(An augmentation of Polytope A projects to Polytope B) ==> (The external descriptions of A and B are related)". We provide counter-examples to these presumptions, and show that in general: (1) If polytopes can always be arbitrarily augmented for the purpose of establishing EF relations, then the notion of EF becomes degenerate/meaningless in some cases, and that: (2) The statement: "(Polytope B is the projection of an augmentation of Polytope A) ==> (Polytope B is the projection of Polytope A)" is not true in general (although, as we show, the converse statement, "(B is the projection of A) ==> (B is the projection of every augmentation of A)", is true in general). We illustrate some of the ideas using the minimum spanning tree problem, as well as the "lower bounds" developments in Fiorini et al. (2011; 2012), in particular.