Добрый день!
Идея данной ветки родилась после того, как обнаружилось, что некоторые участники форума испытывают интерес к решениям задач комбинаторной оптимизации!
И даже имеют свои алгоритмы.
Напомню, что мы тоже разработали компонент, позволяющий решать задачи комбинаторной оптимизации, включающий в себя множество продвинутых алгоритмов: как точных, так и евристических.
Поэтому родилась идея совместного обсуждения рекордов, полученных при решении задач TSPLib.

Мы запустили серии тестов для многих задач из этой библиотеки. Каждая задача решается несколькими алгоритмами с разными конфигурациями. Для каждого теста — делается серия из 10 подтестов и результаты усредняются. Именно результаты усреднений являются записями нашей таблицы результатов.
С нашими результатами можно ознакомиться здесь.

Интересно будет увидеть и сравнить аналогичные результаты других алгоритмов от других авторов!

То есть смысл ветки научно-соревновательный

Здравствуйте, Divosoft, Вы писали:

D>С нашими результатами можно ознакомиться здесь.

а можете там дать описание колонок? что-то интуитивно понятно, но лучше уж точно.

D>Интересно будет увидеть и сравнить аналогичные результаты других алгоритмов от других авторов!

предлагаете выводить также за минуту и 15 минут или как? тогда непонятно на каком компьютере запускать. у меня нет такого среднего, есть совсем дохлый ноут и довольно производительный.
и еще, не совсем понял почему было 10 запусков? у вас алгоритмы не детерменированный, т.е. имеются случайные переходы? у меня детерменированный и я использую GetThreadTimes для получения чистого времени работы алгоритма --- достаточно одного запуска, проверено.

D>То есть смысл ветки научно-соревновательный

заничаит предлагаете помериться ?

Здравствуйте, ilnar, Вы писали:

I>Здравствуйте, Divosoft, Вы писали:

D>>С нашими результатами можно ознакомиться здесь.

I>а можете там дать описание колонок? что-то интуитивно понятно, но лучше уж точно.

D>>Интересно будет увидеть и сравнить аналогичные результаты других алгоритмов от других авторов!

I>предлагаете выводить также за минуту и 15 минут или как? тогда непонятно на каком компьютере запускать. у меня нет такого среднего, есть совсем дохлый ноут и довольно производительный.
I>и еще, не совсем понял почему было 10 запусков? у вас алгоритмы не детерменированный, т.е. имеются случайные переходы? у меня детерменированный и я использую GetThreadTimes для получения чистого времени работы алгоритма --- достаточно одного запуска, проверено.

Для подобного класса задач разница между Core Duo и Pentium III особо может быть и не заметна,
так как что один и что другой не способны перебрать все пространство решений, и необходимо
использолвать евристики. На сайте указаны скромные конфигурации компов и времени, только для демонстрации
чего может добиться алгоритм.

Если у вас получилось найти лучшее решение за пол часа и на Core Dou (класстерные системы и супер-компьютеры не в счет), то присылайте результат опубликуем и время и конфигурацию и результат.

Для соревнований главное результат, за разумное время, до 12 часов к примеру.
Так как для все не точных алгоритмов есть "область насыщения" к которой они скатываються
(для каждой задачи она может быть своя) и там находиться достаточно долго, и вопрос в том, чья
евристика глубже сможет копнуть к рекорду.

D>>То есть смысл ветки научно-соревновательный

I>заничаит предлагаете помериться ?

Здравствуйте, Divosoft, Вы писали:

D>Здравствуйте, ilnar, Вы писали:

I>>Здравствуйте, Divosoft, Вы писали:

D>Если у вас получилось найти лучшее решение за пол часа и на Core Dou (класстерные системы и супер-компьютеры не в счет), то присылайте результат опубликуем и время и конфигурацию и результат.
куда присылать?

D>Для соревнований главное результат, за разумное время, до 12 часов к примеру.
D>Так как для все не точных алгоритмов есть "область насыщения" к которой они скатываються
D>(для каждой задачи она может быть своя) и там находиться достаточно долго, и вопрос в том, чья
D>евристика глубже сможет копнуть к рекорду.

у меня точный метод (дополнения к методу Литтла). вот пустил на минуту и на 15 минут, результаты есть, только во внутреннем формате, сегодня вечером скину в эксель.
сейчас думаю что может правильным было бы пустить на половину вашего времени, у меня реально 2 раза быстрый комп (не для хвастовства будет сказано)

пока результаты будут проверенного метода, задачи ATSP.

есть более прогрессивный алгоритм (работаю над ним), который решает ft53 очень быстро, тогда как предыдущий не решает. К сожалению, когда захотел его использовать для сравнения, на некоторых задачах выявился уход в себя, планирую отладку, а со временем как всегда, плоховато (работаю над диссертацией, куда этот метод, видимо, уже не войдет, предыдущий включен).

вот и моя лепта на задачах atsp
задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

результаты здесь

Здравствуйте, ilnar, Вы писали:

I>задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

вдогонку: использовалось только одно ядро проца, ибо алгоритм не параллельный

Здравствуйте, ilnar, Вы писали:

I>вот и моя лепта на задачах atsp
I>задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

I>результаты здесь
Результаты неожиданные честно говоря. Очень впечатляет как для точного алгоритма.

У меня вопросы:
1) а почему результаты за 1 мин совпадают с результатами за 15 мин в 100% случаев?
Там где Е=0 ответ понятен. Но там где точное решение не найдено, должно же быть улучшение за 14 мин работы?!

2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.

D>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
Вот собственно сгеренили. Данные здесь.
Также запустили и наш компонент для этой задачи.

Здравствуйте, Divosoft, Вы писали:

D>Здравствуйте, ilnar, Вы писали:

I>>вот и моя лепта на задачах atsp
I>>задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

I>>результаты здесь
D>Результаты неожиданные честно говоря. Очень впечатляет как для точного алгоритма.

D>У меня вопросы:
D>1) а почему результаты за 1 мин совпадают с результатами за 15 мин в 100% случаев?
D>Там где Е=0 ответ понятен. Но там где точное решение не найдено, должно же быть улучшение за 14 мин работы?!

метод типа ветвей и границ, он даже может найти оптимальное решение в первые минуты, а потом сутками ходить по оставшенму дереву перебора решений доказывая оптимальность (это и есть проблема точных методов. оптимальное решение найдет, но не будет знать что это оптимальное). Там где Е=0, не во всех случаях алгоритм указывал, что найденное решение -- оптимальное (просто, видимо, задачи попались такие что в большинстве случаев доходил быстро до оптимального решения, но только в части из них смог сказать что найденный рекорд оптимален).
т.е. в большинстве случаев, особенно на больших задачах очередные рекорды (я так называю очередное улучшение решения, не путать с оптимальным решением) чем дальше в лес, тем реже появляются.
могу показать лог появления рекордов (улучшения решения) для разных задач, будет видно что они появляются очень неравномерно (((

D>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
не вопрос, на какое время пускать? 1 и 15 минут? сразу скажу, что как уже писал, разница результатов на 15 мин и 6 часов может не отличаться, т.к. алгоритм агрессивно идет в "хороших" направлениях, а потом смотрит и остальное.

Здравствуйте, Divosoft, Вы писали:

D>>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
D>Вот собственно сгеренили. Данные здесь.
D>Также запустили и наш компонент для этой задачи.

ок, запущу как дойду домой.
на время 1 и 15 минут. к сожалению пока в программе нет возможности фиксировать рекорды в промежуточных временах, но это надо бы сделать, хорошо было бы. Хотя есть логирование нахождений новых рекордов, но там время пока не вывожу.

на будущее, если будете слать много задач, пожалуйста, генерируйте в формате (у меня так считывает, только задачи VRP в формате tsplib):
<Размерность N>
<x_11> <x_12> <x_13> ... <x_1N>
<x_21> <x_22> <x_23> ... <x_2N>
....
<x_N1> <x_N2> <x_N3> ... <x_NN>

строки не обязательно переводить, <> не нужны, просто разделенные числа (пробелом, табуляцией или переносом строки)

пример:

5
11 22 33 44 55
11 22 33 44 55
11 22 33 44 55
11 22 33 44 55
11 22 33 44 55

диагональные числа все равно пропускаю, все равно какое число (обязательно д.б. число), я сам генерирую с -1 там. да, -1 в других местах будет интерпретироваться как бесконечность
вот так:

5
-1 22 33 44 -1
11 -1 33 44 55
11 22 -1 44 55
11 22 33 -1 55
11 22 33 44 -1

Здравствуйте, Divosoft, Вы писали:

D>>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
D>Вот собственно сгеренили. Данные здесь.
D>Также запустили и наш компонент для этой задачи.

не знаю что это у вас за странная задача, но она решилась за 3,5 секунд ))
решение 4808

Здравствуйте, ilnar, Вы писали:

I>Здравствуйте, Divosoft, Вы писали:

D>>>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
D>>Вот собственно сгеренили. Данные здесь.
D>>Также запустили и наш компонент для этой задачи.

I>не знаю что это у вас за странная задача, но она решилась за 3,5 секунд ))
I>решение 4808
Да задачка была сгенерена случайным образом, чтобы проверить просто насколько "честно" решает вам алгоритм!
Она не была сложной, а просто для проверки задачи без известного результата конечного.

Здравствуйте, Divosoft, Вы писали:

D>Да задачка была сгенерена случайным образом, чтобы проверить просто насколько "честно" решает вам алгоритм!
я тоже так подумал, что вы усомнились в честности

D>Она не была сложной, а просто для проверки задачи без известного результата конечного.
тогда давайте сложные, если хотите конечно ))

Здравствуйте, ilnar, Вы писали:

I>Здравствуйте, Divosoft, Вы писали:

D>>Здравствуйте, ilnar, Вы писали:

I>>>вот и моя лепта на задачах atsp
I>>>задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

I>>>результаты здесь
D>>Результаты неожиданные честно говоря. Очень впечатляет как для точного алгоритма.

D>>У меня вопросы:
D>>1) а почему результаты за 1 мин совпадают с результатами за 15 мин в 100% случаев?
D>>Там где Е=0 ответ понятен. Но там где точное решение не найдено, должно же быть улучшение за 14 мин работы?!

I>метод типа ветвей и границ, он даже может найти оптимальное решение в первые минуты, а потом сутками ходить по оставшенму дереву перебора решений доказывая оптимальность (это и есть проблема точных методов. оптимальное решение найдет, но не будет знать что это оптимальное). Там где Е=0, не во всех случаях алгоритм указывал, что найденное решение -- оптимальное (просто, видимо, задачи попались такие что в большинстве случаев доходил быстро до оптимального решения, но только в части из них смог сказать что найденный рекорд оптимален).
I>т.е. в большинстве случаев, особенно на больших задачах очередные рекорды (я так называю очередное улучшение решения, не путать с оптимальным решением) чем дальше в лес, тем реже появляются.
I>могу показать лог появления рекордов (улучшения решения) для разных задач, будет видно что они появляются очень неравномерно (((

D>>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
I>не вопрос, на какое время пускать? 1 и 15 минут? сразу скажу, что как уже писал, разница результатов на 15 мин и 6 часов может не отличаться, т.к. алгоритм агрессивно идет в "хороших" направлениях, а потом смотрит и остальное.

Мы недооценили метод ветвей и границ. Действительно, если подобрать хорошие евристики, то можно получать хорошие результаты и очень быстро.
Мы будем исследовать и улучшать наш метод ветвей и границ тоже как только появится свободное время, поскольку пока основными нашими доходами являются доходы от аутсорсинга, поэтому пока все на энтузиазме и в свободное время.

А вы занимаетесь комбинаторной оптимизацией профессионально?
Учились и работаете в этом направлении?

Здравствуйте, Divosoft, Вы писали:

D>А вы занимаетесь комбинаторной оптимизацией профессионально?
можно это назвать профессионально? сами решите

D>Учились и работаете в этом направлении?
учусь в аспирантуре (последний год), занимаюсь комбинаторной оптимизацией задач TSP и VRP. И некоторыми вспомогательными (только столько, сколько надо для целей TSP и VRP).
в рамках учебы, это наверно профессионально, т.к. есть статьи с обоснованием применяемых подходов.
работаю совсем в другой сфере, с этой стороны это просто хобби.

пишу диссертацию. после него это станет хобби, если никто не пожелает купить и финансировать дальнейшее исследование. )))

Здравствуйте, ilnar, Вы писали:

I>вот и моя лепта на задачах atsp
I>задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

I>результаты здесь

Классные результаты, для приближенного алгоритма и задач n<500.
На таких задачах усеченный МВГ это отличный приближенный метод.
Интересно знать среднее отклонение на задачах n>500 (на однородных, и на случайных распределениях), лучшие приближенные методы (Helsgаun LK) для произвольно-больших STSP показывают 0.6-0.9% см замечательный обзор: здесь , тесты -здесь и резюме

http://www.research.att.com/~dsj/papers/stspchap.pdf

А доказывает точное решение STSP eil101, eil76 за склько мин?
Да и какие результаты для CVRP?
Неподскажешь ли ты на сколько хорошо TSP приближает однородные CVRP? Если размножить центральный склад, и решить TSP на задачах типа En76k-10 и Pxx?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, ilnar, Вы писали:

I>>вот и моя лепта на задачах atsp
I>>задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

I>>результаты здесь

А>Классные результаты, для приближенного алгоритма и задач n<500.
А>На таких задачах усеченный МВГ это отличный приближенный метод.
А>Интересно знать среднее отклонение на задачах n>500 (на однородных, и на случайных распределениях), лучшие приближенные методы (Helsgаun LK) для произвольно-больших STSP показывают 0.6-0.9% см замечательный обзор: здесь , тесты -здесь и резюме
А>

А>http://www.research.att.com/~dsj/papers/stspchap.pdf
А>

бегло посмотрел здесь, не понял где там брать тесты? или самому сгенерировать? пробовать симметричном или ассиметричном (он поддается лучше)?

А>А доказывает точное решение STSP eil101, eil76 за склько мин?
таких не пробовал. с вас ссылки на задачи, и попробую, но уже вечером. пишите на сколько минут пускать.

А>Да и какие результаты для CVRP?
А>Неподскажешь ли ты на сколько хорошо TSP приближает однородные CVRP? Если размножить центральный склад, и решить TSP на задачах типа En76k-10 и Pxx?
у меня чуть иное сведение задачи CVRP к коммивояжеру. результаты лучше (пробовал и сравнивал с размножением).
точно решить с доказательством удавалось только до Е23к3 и Е22к4. а при к>4 и n>30 (это стандартные задачи побольше) доказать оптимальность не удавалось. при этом задачи Е30к3 и Е30к4 удалось получить оптимальное решение, но без доказательства.
к сожалению улучшать времени пока нет, хотя есть идеи. занят диссертацией.
вот есть старые оформленные результаты по решению CVRP на Pentium III 850Mhz (ноут мой, служивший правдой ) с ограничением времени в 1 минуту. http://files.rsdn.ru/982/cvrp1min_p3-850Mhz.xls
есть неоформленные результаты, полученные на Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15, запущенные на 5 минут. может вечером подхотовлю и выложу.

Здравствуйте, ilnar, Вы писали:

I>бегло посмотрел здесь, не понял где там брать тесты? или самому сгенерировать? пробовать симметричном или ассиметричном (он поддается лучше)?
У них там и случайные данные и TSPLIB Instances здесь
А>>А доказывает точное решение STSP eil101, eil76 за склько мин?
I>таких не пробовал. с вас ссылки на задачи, и попробую, но уже вечером. пишите на сколько минут пускать.
Так это TSPLIbовские аналоги CVRP E76 и E101. Пускать до упора — пока не докажет (если это не долго).

А>>Да и какие результаты для CVRP?
А>>Неподскажешь ли ты на сколько хорошо TSP приближает однородные CVRP? Если размножить центральный склад, и решить TSP на задачах типа En76k-10 и Pxx?
I>у меня чуть иное сведение задачи CVRP к коммивояжеру. результаты лучше (пробовал и сравнивал с размножением).
I>точно решить с доказательством удавалось только до Е23к3 и Е22к4. а при к>4 и n>30 (это стандартные задачи побольше) доказать оптимальность не удавалось. при этом задачи Е30к3 и Е30к4 удалось получить оптимальное решение, но без доказательства.
А статистика по нижней границе не делалась? Сейчас делаю обзор по нижним границам, тоже дисертация ... не знаю прокатит или нет

I>к сожалению улучшать времени пока нет, хотя есть идеи. занят диссертацией.
I>вот есть старые оформленные результаты по решению CVRP на Pentium III 850Mhz (ноут мой, служивший правдой ) с ограничением времени в 1 минуту. http://files.rsdn.ru/982/cvrp1min_p3-850Mhz.xls
Ну в среднем там 8% превышения это много
I>есть неоформленные результаты, полученные на Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15, запущенные на 5 минут. может вечером подхотовлю и выложу.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, ilnar, Вы писали:

I>>таких не пробовал. с вас ссылки на задачи, и попробую, но уже вечером. пишите на сколько минут пускать.
А>Так это TSPLIbовские аналоги CVRP E76 и E101. Пускать до упора — пока не докажет (если это не долго).
все же, ссылки в студию! а про пускать до упора, спонсором будете? ресурсов не хватет ))

А>>>Да и какие результаты для CVRP?
А>>>Неподскажешь ли ты на сколько хорошо TSP приближает однородные CVRP? Если размножить центральный склад, и решить TSP на задачах типа En76k-10 и Pxx?
I>>у меня чуть иное сведение задачи CVRP к коммивояжеру. результаты лучше (пробовал и сравнивал с размножением).
I>>точно решить с доказательством удавалось только до Е23к3 и Е22к4. а при к>4 и n>30 (это стандартные задачи побольше) доказать оптимальность не удавалось. при этом задачи Е30к3 и Е30к4 удалось получить оптимальное решение, но без доказательства.
А>А статистика по нижней границе не делалась? Сейчас делаю обзор по нижним границам, тоже дисертация ... не знаю прокатит или нет
не понял про нижнюю границу. проясните термин плиз.

А>Ну в среднем там 8% превышения это много
какие есть, на то и точные методы. не ставлю цели всех обскакать, за это не платят, я не фанатик.