Problema de optimización

Por convención, la forma estándar define un problema de minimización.

Un problema de maximización puede tratarse negando la función objetivo.

Formalmente, un problema de optimización combinatoria A es un cuádruple (I, f, m, g), donde El objetivo es entonces encontrar para algún caso x una solución óptima, es decir, una solución factible y con Para cada problema de optimización combinatoria, hay un problema de decisión correspondiente que pregunta si existe una solución factible para alguna medida particular m0.

Por ejemplo, si hay un gráfico G que contiene los vértices u y v, un problema de optimización podría ser "encontrar una ruta de u a v que use la menor cantidad de aristas".

La versión de decisión habitual es entonces una definición inadecuada del problema, ya que solo especifica soluciones aceptables.