Дискретна оптимізація

Дискретна оптимізація — розділ оптимізації в прикладній математиці та інформатиці. На відміну від неперервної оптимізації, деякі або всі змінні, що використовуються в задачі дискретної оптимізації, діскретні(інші мови), тобто, можуть набувати значень лише з дискретного набору, наприклад, цілих[1].

Галузі

Три основні гілки дискретної оптимізації:[2]

• комбінаторна оптимізація, що розглядає задачі на графах, матроїдах та інших дискретних структурах;
• цілочисельне програмування;
• програмування в обмеженнях.

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

Див. також

• Діофантові рівняння
• Неперервна оптимізація

Примітки

1. Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, т. 36, Cambridge University Press, с. 1, ISBN 9780521010122.
2. Hammer, P. L.; Johnson, E. L.; Korte, B. H. (2000), Conclusive remarks, Discrete Optimization II, Annals of Discrete Mathematics, т. 5, Elsevier, с. 427—453.