Аннотация:
Для асимметричной задачи о коммивояжере на основе конуса обобщенных матриц Супника описан релаксационный политоп в пространстве минимальной размерности. Описание этого политопа получено с помощью предложенного в работе [6] общего метода построения релаксаций подстановочных политопов, порождаемых подгруппами симметрической группы. Число неравенств в предложенном описании факториально зависит от размера задачи.
Полный текст:
PDF файл (266 kB)