Генерация интересных комбинаторных задач оптимизации

9

Я преподаю курс метаэвристики, и мне нужно создать интересные примеры классических комбинаторных задач для термина «проект». Давайте сосредоточимся на TSP. Мы занимаемся графиками размерности200и больше. Я попытался, конечно, сгенерировать график с матрицей затрат со значениями, взятыми из случайногоU(0,1)и обнаружил, что (как и ожидалось) гистограмма для стоимости пути (нарисованная путем выборки множества случайных путей) имеет очень узкое нормальное распределение (μ является  100 но σ вокруг 4). Это означает, на мой взгляд, что проблема очень проста, так как большинство случайных путей будет ниже среднего, а путь минимальной стоимости очень близок к случайному пути.

Поэтому я попробовал следующий подход: после генерации U(0,1)-матрица, сделайте длинный случайный обход по графику и случайно (Бернулли с p=0.5) удвоить или уменьшить вдвое значение ребра. Это имеет тенденцию понижать все значения, в конечном итоге достигая нуля, но если я сделаю только правильное количество шагов, я могу получить распределение сμ около 2 а также σ около 1,

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

Алехандро Пиад
источник
3
Ищите библиотеки тестов TSP, изученных в OR (например, ищите работы по TSP по Applegate et al., Например, здесь )?
Нил Янг
2
Существует TSPLIB со многими экземплярами.
adrianN
Спасибо, я проверил ссылку, и она полезна, но мой вопрос касается генерации экземпляров не потому, что я хочу решить конкретный экземпляр, а скорее потому, что я ищу понимание того, что делает хорошие комбинаторные проблемы, понимание, которое позже может быть расширено до другие проблемы, кроме TSP.
Алехандро Пиад
похожие посты: cstheory.stackexchange.com/questions/739/…
Нил Янг
1
@ Alejandro, скрытая проблема клика может быть примером того, что вы ищете. Кроме того, вы можете искать исследования о том, какие случайные случаи удовлетворенности считаются трудными.
Нил Янг

Ответы:

6

Один общий подход к созданию более сложных экземпляров заключается в следующем:

  • Начните со случайного экземпляра задачи.
  • Вставьте «скрытый бэкдор»: случайным образом выберите хорошее решение (которое, вероятно, будет намного лучше, чем любое уже существующее решение) и измените экземпляр проблемы, чтобы принудительно внедрить это решение в экземпляр проблемы.

Например, для TSP вы можете сделать что-то вроде следующего. Создать случайный экземпляр задачи, выбрав случайныйU(0,1)матрица затрат. Затем настройте экземпляр задачи, чтобы скрыть в нем гораздо лучшее решение: случайным образом выбрать маршрут, который посещает каждую вершину ровно один раз, и уменьшить вес ребер в этом цикле (например, сгенерировать его случайным образом изU(0,c) где c<1; уменьшить существующий вес; или изменить существующее ребро с некоторой фиксированной вероятностью). Эта процедура корректировки гарантирует, что оптимальным решением, с большой вероятностью, будет тот специальный тур, который вы выбрали. Если вам повезет, и вы выберете разумное вложение, также будет не так легко узнать, где вы спрятали специальное решение.

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

Получающиеся в результате проблемы могут быть сложными , но будут ли они интересны с какой-либо практической точки зрения? Я не знаю. Бьет меня Они выглядят довольно искусственно для меня, но что я знаю?

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

DW
источник
Мне очень нравится этот подход, он очень близок к тому, что я пытался придумать, и, кажется, в значительной степени адаптируется к различным проблемам. Моя первоначальная мотивация заключалась в том, чтобы создавать тестовые задачи для студентов, поэтому, несмотря на то, что у меня возникают проблемы с реальными словами, я хорошо справляюсь с этой довольно искусственной ситуацией (пытаясь оценивать алгоритмы студентов). В любом случае, я постараюсь адаптировать его также для моих потребностей в исследованиях, но, как вы говорите, для этого потребуется более внимательный взгляд, чтобы определить, достаточно ли репрезентативны созданные экземпляры. Большое спасибо, вы получили мой +1 и принятие.
Алехандро Пиад
3

подход, который часто дает вам высокий контроль над природой решений, - это преобразование одной полной задачи NP в другую. теперь вы определяете «интересный» в своем вопросе статистическим способом, но другой аккуратный подход заключается в использовании классических задач из области. мой любимый это факторинг / сат. тривиально найти либо «гладкие» числа с множеством факторов, либо простые числа только с двумя «факторами» (один и простое число). создайте экземпляр SAT для решения факторинга, а решения являются факторами (фактически перестановками факторов, но также не трудно рассчитать заранее).

при таком подходе существует естественное определение «интересных» - трудных случаев, которые не могут быть решены за время P. и этот подход гарантированно приведет к сложным случаям для факторизации негладких чисел, в противном случае он решит главный открытый вопрос в теории сложности, т. е. сложность факторинга .

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

если вам не нравится факторинг, все же может быть предпочтительнее сначала создать экземпляры в SAT по ряду причин. Вы могли бы начать со случайных экземпляров SAT, настроенных по центру в точке перехода легко-трудно-легко, и так далее. или вы можете работать с жесткими экземплярами DIMACS , созданными сообществом. или создавать другие логические "программы" в SAT.

ВЗН
источник
1
Мне нравится подход конверсии, хотя вы не предоставляете дальнейшие ссылки, конкретно относящиеся к TSP, но в любом случае спасибо за идею, я исследую ее более подробно. Вы получили мой +1.
Алехандро Пиад
1
@alejandro спасибо, вот ссылка на это. см., например, начиная со слайда 28 здесь [класс бакалавриата!], CMSC 451: SAT, раскраска, гамильтонов цикл, слайды TSP Автор: Карл Кингсфорд . преобразование SAT → гамильтонов цикл (TSP). могут быть более эффективные (с меньшими накладными расходами) подходы к конверсии или другие специализированные аспекты в литературе, если это то, что нужно. надеюсь услышать больше о вашей работе, возможно, ответьте здесь или в моем блоге, если хотите
vzn
1
Я проверил PDF, очень высокий уровень, но достаточно понятно. Хотя в настоящее время я получил то, что мне нужно, с ответом @DW, ваш подход кажется мне очень интересным. Я должен попробовать это самостоятельно. Раньше я видел это сокращение (на курсе для студентов старших курсов по сложности), но не думал о его реальной реализации специально для создания сложных экземпляров. У меня есть долгосрочный интерес к оптимизации и метаэвристике, и одна из моих сфер интересов - создание интересных тестовых задач. Кстати, только что проверил ваш блог, обязательно вернусь !!!
Алехандро Пиад