English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present an O(n^6 ) linear programming model for the traveling salesman(TSP) and quadratic assignment (QAP) problems. The basic model is developedwithin the framework of the TSP. It does not involve the city-to-cityvariables-based, traditional TSP polytope referred to in the literature as "theTSP polytope." We do not model explicit Hamiltonian cycles of the cities.Instead, we use a time-dependent abstraction of TSP tours and develop a directextended formulation of the linear assignment problem (LAP) polytope. The modelis exact in the sense that it has integral extreme points which are inone-to-one correspondence with TSP tours. It can be solved optimally using anylinear programming (LP) solver, hence offering a new (incidental) proof of theequality of the computational complexity classes "P" and "NP." The extensionsof the model to the time-dependent traveling salesman problem (TDTSP) as wellas the quadratic assignment problem (QAP) are straightforward. The reasons forthe non-applicability of existing negative extended formulations results for"the TSP polytope" to the model in this paper as well as our softwareimplementation and the computational experimentation we conducted are brieflydiscussed.

Exact extended formulation of the linear assignment problem (LAP) polytope for solving the traveling salesman and quadratic assignment problems