7.1.3 Estrategia para usar Máquinas de Boltzmann en problemas de optimización combinatoria

Para utilizar una máquina de Boltzmann para resolver un problema de optimización combinatoria, se define una función bijectiva $m : {\cal R} \rightarrow {\cal S}$ que mapea el conjunto de configuraciones $\cal R$ al conjunto de soluciones $\cal S$, siguiendo la siguiente estrategia general:

1. Formula el problema de optimización como un problema de programación de 0 y 1 (formula el problema tal que $X_i = \{0,1\}$, para $i = 1, \ldots, n$).
2. Define una máquina de Boltzmann tal que el estado en cada unidad determine el valor de una variable.
3. Define el conjunto de conecciones y las fuerzas tal que la función de consenso sea factible y preserve el orden.

Una función de consenso es factible si todos los máximos locales de la función de consenso corresponden a soluciones factibles.

Factibilidad implica que siempre se encuentra una solución factible.

Una función de consenso se dice que preserva el orden si $\forall k, l \in \cal R$, con $m(k), m(l) \in \cal S'$, tenemos que:

$$f(m(k)) > f(m(l)) \Rightarrow C(k) > C(l)$$

.

Para un problema de minimización sería:

$$f(m(k)) < f(m(l)) \Rightarrow C(k) > C(l)$$