Investigación de operaciones: ¿Cómo puedo minimizar [matemáticas] f (x_1, x_2, \ ldots, x_n) [/ matemáticas], donde todas las [matemáticas] x_ {i} [/ matemáticas] se eligen de un conjunto finito sin repetición?

Answer 1

Como otros ya han mencionado, es difícil resolver este problema en general. Aquí hay un enfoque codicioso. Sea [math] x_i ^ t [/ math] el valor de las variables de decisión [math] x_i [/ ​​math] en iteración [math] t [/ math]. En iterar [math] t [/ math], genere un entero aleatorio [math] 1 \ leq k_t \ leq n [/ math], establezca [math] x_ {k_t} [/ math] para ser [math] \ arg \ min_ {x_ {k_t} \ en S} f [/ math], es decir, arregle cualquier otra coordenada de su variable de decisión y simplemente elija [math] x_ {k_t} [/ math]. Ahora actualice [math] S \ leftarrow S \ backslash S – \ {\ arg \ min_ {x_ {k_t} \ in S} f \} [/ math]. Repita este proceso para [math] n [/ math] iteraciones. Por supuesto, esto no nos da ninguna garantía en general.

Entonces, lo que más puede hacer ahora es repetir todo este algoritmo muchas veces y anotar el valor de [math] f [/ math] después de las iteraciones [math] n [/ math]. Si no le gusta la aleatoriedad en cada paso, puede elegir una pernutación aleatoria antes de comenzar su algoritmo y actualizar la coordenada en consecuencia.

Answer 2

Para convex [math] f [/ math], creo que es posible hacer un buen trabajo.

Uno puede resolver el problema sin restricciones ([matemáticas] x \ in \ mathbb {R} ^ n [/ matemáticas]) y utilizar el hecho de que los puntos más cercanos a la solución sin restricciones son mejores que los puntos más alejados de él.

Alguna forma de rama y límite debería reducir considerablemente el espacio de búsqueda, aunque espero que el problema siga siendo NP-hard.

Answer 3

Es un problema de optimización, de hecho, un problema de optimización de enteros, aunque sea extraño.

Las restricciones en los valores que x_i puede tomar son restricciones en el soporte de la función.

Si la función tiene simetrías como, en el caso 2d, para simplificarla:
f (x, y) = f (y, x)
Entonces quizás haya otra esperanza que no sea la enumeración

Answer 4

Para una función general, no hay forma de hacerlo sin una búsqueda exhaustiva. ¡No hay! diferentes permutaciones para verificar, por lo que, obviamente, este enfoque no se escala bien a medida que n crece.