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

B>>Эээ... к кому вопрос?

I>в основном топикстартеру. Можете и вы, интересны задачи из практики (можно [a]tsp, cvrp)

Попробуй посмотреть здесь.
Сам я пока не смотрел, но скоро буду обязательно. Тут нашего шефа профессор один из этого fernUni осаждает — предлагает свои услуги. Тоже говорит, что лучше ни у кого нет

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

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

B>>>Эээ... к кому вопрос?

I>>в основном топикстартеру. Можете и вы, интересны задачи из практики (можно [a]tsp, cvrp)

B>Попробуй посмотреть здесь.
B>Сам я пока не смотрел, но скоро буду обязательно. Тут нашего шефа профессор один из этого fernUni осаждает — предлагает свои услуги. Тоже говорит, что лучше ни у кого нет

эээ, может у меня с русским не то, но я не понял фразу "Тут нашего шефа профессор один из этого fernUni осаждает — предлагает свои услуги."
мог бы попроще перефразировать?

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

B>>Попробуй посмотреть здесь.
B>>Сам я пока не смотрел, но скоро буду обязательно. Тут нашего шефа профессор один из этого fernUni осаждает — предлагает свои услуги. Тоже говорит, что лучше ни у кого нет

I>эээ, может у меня с русским не то
А мож у меня

I>..., но я не понял фразу "Тут нашего шефа профессор один из этого fernUni осаждает — предлагает свои услуги."
I>мог бы попроще перефразировать?

Фирма наша занимается логистикой — в том числе VRP.
На днях с шефом связался профессор из университета fernUni, и сказал примерно следующее: "я мол знаю, что вы заниметесь решением VRP, и готов предложить вам свои услуги, потому как алгоритмы, которые я разаработал, самые что ни на есть лучшие."

Поскольку решением VRP занимяюсь я, то мне нужно будет все тестовые модели, которые этот проф. упомянул, прорешивать. Вот и можно будет сравнить результаты
Только о методе расчета времен и расстояний нужно будет договориться

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

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

I>...

S>>Выслали они сам фреймворк, а тесты уже на сайте есть тут.
S>>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?

I>мой точный алгоритм типа метода ветвей и границ их задачу размерности 53 (как они сказали, это ft53) решил за 212 сек 3.5мин, а у них судя по второму графику далеко от решения, даже эвристики не дошли до оптимального

На то он и точный алгоритм ) а что будет при размерности 100? 200?

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

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

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

I>>...

S>>>Выслали они сам фреймворк, а тесты уже на сайте есть тут.
S>>>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?

I>>мой точный алгоритм типа метода ветвей и границ их задачу размерности 53 (как они сказали, это ft53) решил за 212 сек 3.5мин, а у них судя по второму графику далеко от решения, даже эвристики не дошли до оптимального

А>На то он и точный алгоритм ) а что будет при размерности 100? 200?

пустил вчера на стандартные тесты, отсчитаюсь вечером или завтра.
вообще решает.

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


А>>Народ а не подскажите vrptw -шечки по 50-70 пунктов, где можно достать?
А>>Я разработал метод для их точного решения (в т.ч. CVRP), сейчас пока програмлю, но предварительные результаты впечатляют, быстрая нижняя граница — ~97%, это без дополнительных модификаций

I>не заню даже. а ты cvrp уже пробовал? и большие тоже?
Пока тестирую нижнюю границу, рещение задач в целом тоже делал, но на другой "псевдо"границе.
I>какие результаты по времени?
Двумя словами не скажешь, но быстрая.
Кажется точность важнее времени (а качество количества . Пусть мы имеем две оценки быструю и медленную: A~96% и B~97%.
Если сравнивать два дерева порожденные этими оценками (при прочи равных), то разница по количеству узлов в деревьях будет показательно возрастать с ростом n. Поэтому при больших n медленная полиномиальная оценка зарулит быструю. Другой вопрос, что число n, может быть довольно большим.
Разумеется немало зависит от сторонних факторов, но в целом это утверждение кажется верным.

Когда появятся результаты проинформирую.

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

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

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

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

I>>>...

S>>>>Выслали они сам фреймворк, а тесты уже на сайте есть тут.
S>>>>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?

I>>>мой точный алгоритм типа метода ветвей и границ их задачу размерности 53 (как они сказали, это ft53) решил за 212 сек 3.5мин, а у них судя по второму графику далеко от решения, даже эвристики не дошли до оптимального

А>>На то он и точный алгоритм ) а что будет при размерности 100? 200?

I>пустил вчера на стандартные тесты, отсчитаюсь вечером или завтра.
I>вообще решает.

Насколько я знаю точные методы, на то они и точные, что гаранитуют анализ всего пространства решений,
и отбрасывают заведомо плохие. Для задачи размерности 53, пространство решений 8 * 10^67
пусть точный метод будет отбрасывать 99 и смотреть лишь 1 (а часто бы вает и хуже), то надо перебрать
~10^65 решений, если не секрет на каком проце это можно сделать за 212 сек, у меня такое не получаеться.

Пространство решений растет факториально (експоненциально — есть оценка роста через exp).
То для 100 и 200 цифры будут еще более впечатляющие.

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

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

B>>>Попробуй посмотреть здесь.
B>>>Сам я пока не смотрел, но скоро буду обязательно. Тут нашего шефа профессор один из этого fernUni осаждает — предлагает свои услуги. Тоже говорит, что лучше ни у кого нет

I>>эээ, может у меня с русским не то
B>А мож у меня

I>>..., но я не понял фразу "Тут нашего шефа профессор один из этого fernUni осаждает — предлагает свои услуги."
I>>мог бы попроще перефразировать?

B>Фирма наша занимается логистикой — в том числе VRP.
B>На днях с шефом связался профессор из университета fernUni, и сказал примерно следующее: "я мол знаю, что вы заниметесь решением VRP, и готов предложить вам свои услуги, потому как алгоритмы, которые я разаработал, самые что ни на есть лучшие."

B>Поскольку решением VRP занимяюсь я, то мне нужно будет все тестовые модели, которые этот проф. упомянул, прорешивать. Вот и можно будет сравнить результаты
B>Только о методе расчета времен и расстояний нужно будет договориться

Я сам заканчивал магистратуру в Институте Кибернетики на Глушкова, где одни академы тусуються,
зазывали к себе в аспирантуру, но если честно, вывел один вывод, профессора много знают, но уж больно теоритеческие,
или я ошибаюсь?

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

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

I>...

S>>Выслали они сам фреймворк, а тесты уже на сайте есть тут.
S>>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?

I>мой точный алгоритм типа метода ветвей и границ их задачу размерности 53 (как они сказали, это ft53) решил за 212 сек 3.5мин, а у них судя по второму графику далеко от решения, даже эвристики не дошли до оптимального

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

По многочисленным просьбам мы решили создать настоящую страницу тестов и уже начали тестирование. Вот она здесь.

Результаты постоянно обновляются, как для новых задач так и для старых с улучшением параметров самих алгоритмов.

Интересно будет узнать, какие результаты получаться у других участников форума.

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

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

S>>Вот порылся в сетях нашел компонент, который в принципе решает подобные задачи.
S>>http://www.divosoft.com/Products/Eol/Combinatory/Overview.aspx?lang=RU

S>>Компонент специфический насколько я понял — только мат-алгоритмы, при этом у них можно купить и готовое решение для конкретной задачи.
S>>Может кто знаком с ним?

B>Работать не приходилось. Но вроде как там есть Getting Started лицензия — попробуй посмотреть.

B>ЗЫ
B>Немного настораживает раздел "Тестирование", а вернее отсутствие каких-либо результатов тестирования

Уже такой раздел появился. Под тесты выделили отдельную машинку средней мощности и создали страничку здесь.
Страничка постоянно обновляется по мере поступления результатов тестов.

Здравствуйте, maxim.in.ua, Вы писали:

MIU>Насколько я знаю точные методы, на то они и точные, что гаранитуют анализ всего пространства решений,
MIU>и отбрасывают заведомо плохие. Для задачи размерности 53, пространство решений 8 * 10^67
MIU>пусть точный метод будет отбрасывать 99 и смотреть лишь 1 (а часто бы вает и хуже), то надо перебрать
MIU>~10^65 решений, если не секрет на каком проце это можно сделать за 212 сек, у меня такое не получаеться.

MIU>Пространство решений растет факториально (експоненциально — есть оценка роста через exp).
MIU>То для 100 и 200 цифры будут еще более впечатляющие.

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

в частности эта задача с 53 пунктами у меня решилось за 8114 просмотров узлов дерева решений.
весь остальной экспоненциальный набор вершин был отброшен по нижней оценке.

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

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

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

I>>...

S>>>Выслали они сам фреймворк, а тесты уже на сайте есть тут.
S>>>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?

I>>мой точный алгоритм типа метода ветвей и границ их задачу размерности 53 (как они сказали, это ft53) решил за 212 сек 3.5мин, а у них судя по второму графику далеко от решения, даже эвристики не дошли до оптимального

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

D>По многочисленным просьбам мы решили создать настоящую страницу тестов и уже начали тестирование. Вот она здесь.

D>Результаты постоянно обновляются, как для новых задач так и для старых с улучшением параметров самих алгоритмов.

D>Интересно будет узнать, какие результаты получаться у других участников форума.

посмотрим ))

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

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

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

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

I>>>...

S>>>>Выслали они сам фреймворк, а тесты уже на сайте есть тут.
S>>>>Кто оценит качество тестов? То ли это что надо для определения качества алгоритмов?

I>>>мой точный алгоритм типа метода ветвей и границ их задачу размерности 53 (как они сказали, это ft53) решил за 212 сек 3.5мин, а у них судя по второму графику далеко от решения, даже эвристики не дошли до оптимального

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

D>>По многочисленным просьбам мы решили создать настоящую страницу тестов и уже начали тестирование. Вот она здесь.

D>>Результаты постоянно обновляются, как для новых задач так и для старых с улучшением параметров самих алгоритмов.

D>>Интересно будет узнать, какие результаты получаться у других участников форума.

I>посмотрим ))

Давайте я создам отдельную ветку, где участники форума будут делиться рекордами своих алгоритмов.

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

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

.....

I>>посмотрим ))

D>Давайте я создам отдельную ветку, где участники форума будут делиться рекордами своих алгоритмов.

посмотрим -- значит смотреть результаты тестов.
а вы в гонку втягиваете )))