Geodesic
Relaxation of the polytope of the asymmetric traveling salesman problem on the basis of the cone of generalized Supnick's matrices
Trudy Instituta matematiki, Tome 16 (2008) no. 2, pp. 23-36 
V. M. Demidenko. Relaxation of the polytope of the asymmetric traveling salesman problem on the basis of the cone of generalized Supnick's matrices. Trudy Instituta matematiki, Tome 16 (2008) no. 2, pp. 23-36. http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a2/
@article{TIMB_2008_16_2_a2,
     author = {V. M. Demidenko},
     title = {Relaxation of the polytope of the asymmetric traveling salesman problem on the basis of the cone of generalized {Supnick's} matrices},
     journal = {Trudy Instituta matematiki},
     pages = {23--36},
     year = {2008},
     volume = {16},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a2/}
}
TY  - JOUR
AU  - V. M. Demidenko
TI  - Relaxation of the polytope of the asymmetric traveling salesman problem on the basis of the cone of generalized Supnick's matrices
JO  - Trudy Instituta matematiki
PY  - 2008
SP  - 23
EP  - 36
VL  - 16
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a2/
LA  - ru
ID  - TIMB_2008_16_2_a2
ER  - 
%0 Journal Article
%A V. M. Demidenko
%T Relaxation of the polytope of the asymmetric traveling salesman problem on the basis of the cone of generalized Supnick's matrices
%J Trudy Instituta matematiki
%D 2008
%P 23-36
%V 16
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a2/
%G ru
%F TIMB_2008_16_2_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

For the asymmetric traveling salesman problem, we describe a relaxation polytope that is based on the cone of generalized Supnick matrices and belongs to the space of minimal dimension. The description of the relaxation polytope is obtained by means of the earlier proposed general method [6] to construct relaxations for the permutation polytopes generated by subgroups of the symmetric group. The number of inequalities in the description is of factorial order of the size of the problem.

[1] Lawler E.L., Lenstra J.K., Rinnoy Kan A.H.G., Shmoys D.B., The Traveling salesman Problem, Wiley, Chichester, 1985 | MR | Zbl

[2] Gutin G., Punnen A.P., The traveling salesman problem and its variations, Kluver Academic Publishers, Dordrecht, 2002 | MR

[3] Emelichev V.A., Kovalev M.M., Kravtsov M.K., Mnogogranniki, grafy, optimizatsiya (kombinatornaya teoriya mnogogrannikov), Nauka, M., 1981 | MR

[4] Burkard R.E., Deĭneko V.G., van Dal R., van der Veen J.A.A., Woeginger G.J., “Well-solvable special cases of the TSP: a survey”, SIAM Review, 40:3 (1998), 496–546 | DOI | MR | Zbl

[5] Burkard R.E., Klinz B., Rudolf R., “Perspectives of Monge properties in optimization”, Discrete Applied Mathematics, 70:2 (1996), 95–161 | DOI | MR | Zbl

[6] Demidenko V.M., “Obschii metod postroeniya relaksatsii politopov, porozhdaemykh podgruppami simmetricheskoi gruppy”, Dokl. NAN Belarusi, 49:6 (2005), 20–24 | MR | Zbl

[7] Demidenko V.M., “An extension of Supnick conditions for the asymmetric traveling salesman problem and its application”, ECCO VIII. Abstractes, Poznan (Poland), 1995, 26

[8] Burkard R.E., Demidenko V.M., Rudolf R., “Obobschennye usloviya Supnika i Kalmansona i ikh primenenie k simmetricheskoi i nesimmetricheskoi zadache o kommivoyazhere”, Vestsi AN Belarusi. Ser. fiz.-mat. navuk, 1996, no. 3, 69–74 | MR | Zbl

[9] Burkard R.E., Demidenko V.M., Rudolf R., “A general approach for identifying special cases of the traveling salesman problem with a fixed optimal tour”, OR Transactions of China, 1:1 (1997), 41–53

[10] Demidenko V.M., “Opisanie minimalnykh granei konusa obobschennykh matrits Supnika”, Tr. In-ta matematiki NAN Belarusi, 8 (2001), 21–34

[11] Kalmancon K., “Edgeconvex circuits and the traveling salesman problem”, Can. J. of Math., 27 (1975), 1000–1010 | DOI | MR

[12] Supnick F., “Extreme hamiltonian lines”, Annals of Mathematics, 66 (1957), 179–201 | DOI | MR | Zbl

[13] Suprunenko D.A., Gruppy podstanovok, Navuka i tekhnika, Minsk, 1996 | Zbl

[14] Demidenko V.M., “Postroenie relaksatsii politopa simmetricheskoi zadachi o kommivoyazhere na osnove silno razreshimogo sluchaya Kalmansona”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 11:2 (2004), 3–24 | MR

[15] Demidenko V.M., “Relaksatsionnyi politop simmetricheskoi zadachi o kommivoyazhere, porozhdaemyi konusom matrits Cupnika”, Vestsi NAN Belarusi. Ser. fiz.-mat. navuk, 2007, no. 2, 109–115 | MR

[16] Chernikov S.N., Lineinye neravenstva, Nauka, M., 1968 | MR | Zbl

[17] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, v. 1, M., 1991