У математици и рачунарству, оптимизациони проблем је проблем проналажења најбољег од свих могућих решења. Формално речено, оптимизациони проблем ${\displaystyle A}$ је четворка ${\displaystyle (I,f,m,g)}$, где је

• ${\displaystyle I}$ скуп инстанци;
• за дату инстанцу ${\displaystyle x\in I}$, ${\displaystyle f(x)}$ је скуп свих могућих решења;
• за дату инстанцу ${\displaystyle x}$ и могуће решење ${\displaystyle y}$ за ${\displaystyle x}$, ${\displaystyle m(x,y)}$ означава меру за ${\displaystyle y}$, која је обично позитиван реални број.
• ${\displaystyle g}$ је циљна функција, и то обично ${\displaystyle \min }$ или ${\displaystyle \max }$.

Тада је циљ за неку инстанцу ${\displaystyle x}$ пронаћи оптимално решење, то јест могуће решење ${\displaystyle y}$ за које је

${\displaystyle m(x,y)=g\{m(x,y')\mid y'\in f(x)\}.}$

За сваки оптимизациони проблем постоји одговарајући проблем одлучивања, који поставља питање да ли постоји могуће решење за неку конкретну меру ${\displaystyle m_{0}}$. На пример, ако је дат граф ${\displaystyle G}$ који садржи чворове ${\displaystyle u}$ и ${\displaystyle v}$, оптимизациони проблем би могао да буде наћи пут од ${\displaystyle u}$ до ${\displaystyle v}$ који пролази кроз најмање грана. Одговор на овај проблем би могао да буде на пример 4. Одговарајући проблем одлучивања би био да ли постоји путања од ${\displaystyle u}$ до ${\displaystyle v}$ која пролази кроз 10 или мање грана? Одговор на овај проблем је једноставно да или не.

• Оптимизација (математика)
• Проблем одлучивања