Ищите "простой" целочисленный линейный программный исходный код / псевдокод
Мне может понадобиться реализовать целочисленное линейное программирование сегодня, и мне интересно, есть ли какие-нибудь псевдокоды или относительно безболезненные (хорошо прокомментированные) исходные коды, объясняющие, как это реализовать? С сильным предпочтением псевдо-кода.
Обратите внимание, я не ищу серьезного законченного проекта со всеми "точными настройками", чтобы получить максимально оптимальную производительность. Я ищу самый простой решатель, который демонстрирует, как работает целочисленное линейное программирование, а не пробует все варианты один за другим.
Благодарю.
1 ответ
Это большой вопрос, поэтому позвольте мне попробовать его шаг за шагом:
Когда вы говорите Integer Linear Program, я предполагаю, что вы имеете в виду IP с линейными ограничениями и целевой функцией.
1. Начните с Симплексного алгоритма. (Даже при том, что это НЕ будет работать для IP, за исключением "счастливых" случаев, когда ваша линейная программа обладает свойством "целостности".) Но Simplex всегда является хорошим местом для запуска, особенно так как вы заинтересованы в подходе первых принципов
Удивительно, но найти псевдокод не так просто, хотя раскрытых примеров достаточно. Вот один из примеров шагов в симплексном алгоритме. (Не код Псуэдо)
В разделе 3.1.4 Краткое изложение процедуры вычисления есть нечто похожее на псевдокод.
Этот документ также содержит краткое описание Симплексного алгоритма, который может быть реализован, особенно если вы будете следовать примеру в предыдущих разделах.
Обратите внимание, что Simplex является одним из тех алгоритмов, который относительно прост для понимания (особенно шаг за шагом), но общеизвестно труден для реализации. Действительно хорошее обсуждение того, почему это так, можно найти здесь.
2. Целочисленное программирование - "самый простой" случай. Многие люди склонны начинать с проблемы "рюкзака".
Здесь вы можете найти как псевдокод, так и реализацию Java.
3. IP-адреса возрастающей сложности / сложности.
- Капитальное бюджетирование
- Проблемы с назначением
- Транспортные проблемы
4. Общая и специализированная. Теперь у вас есть выбор:
- 4а. Вы можете создать универсальный IP Solver (но его запуск займет очень много времени)
- 4b. Создание специальных IP-решений для специальных задач.
Для 4a: Вы можете принять переменные 0/1 и продемонстрировать методы ветвления и ограничения. Вы можете найти реализации деревьев и изменить их для своих собственных целей. (По сути, умные реализации исчерпывающих поисков.)
Для 4b: Вы можете взять один случай, скажем, Задача назначения, для которого часто используется венгерский алгоритм, так как он прост для понимания и может преподаваться за один присест группе студентов. Этот урок по topcoder довольно подробно описывает математический, псевдо-и реальный код.
Длинный ответ, но я надеюсь, что это соответствует тому, на что вы надеетесь.