Дискретная оптимизация - Discrete optimization

Дискретная оптимизация это филиал оптимизация в Прикладная математика и Информатика.

Объем

В отличие от непрерывная оптимизация, некоторые или все переменные используется в дискретных математическая программа ограничены быть дискретные переменные - то есть допустить только дискретный набор значений, например целые числа.^[1]

ветви

Три важных направления дискретной оптимизации:^[2]

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

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

Смотрите также

• Диофантово уравнение

Рекомендации

1. Ли, Джон (2004), Первый курс комбинаторной оптимизации, Кембриджские тексты по прикладной математике, 36, Cambridge University Press, стр. 1, ISBN  9780521010122.
2. Hammer, P. L .; Johnson, E. L .; Корте, Б. Х. (2000), «Заключительные замечания», Дискретная оптимизация II, Анналы дискретной математики, 5, Elsevier, стр. 427–453..