Encontrar un conjunto de soluciones máximamente diferentes usando programación lineal u otra técnica de optimización

Tradicionalmente, la programación lineal se utiliza para encontrar la solución óptima para un conjunto de restricciones, variables y un objetivo (todos descritos como relaciones lineales). A veces, cuando el objetivo es paralelo a una restricción, hay infinitas o muchas soluciones óptimas igualmente buenas. No estoy preguntando sobre este último caso.

Estoy más interesado en encontrar muchas soluciones que están en la región factible generada por mi conjunto de restricciones. Pero me gustaría que las soluciones que encuentro estén 'dispersas' alrededor de la región factible en el sentido de que están muy lejos una de la otra. ¿Existe una manera conocida de, sin ejecutar un solucionador varias veces, generar múltiples soluciones y utilizar la función objetivo para garantizar que las soluciones se separen?

Por ejemplo, cualquier programa lineal con decisiones a y by restricciones w <= a <= x e y <= b <= z puede 'duplicarse' para encontrar dos soluciones. Nuestro nuevo programa lineal tiene variables a1, a2, b1 y b2 y las restricciones w <= a1 <= x y w <= a2 <= x y similares para b1, b2. Sin embargo, cuando se trata de formar una función objetivo, nos encontramos con problemas, ya que no podemos usar otras normas que no sean la norma L1 sin descartar la linealidad y ni siquiera podemos usar la norma L1 porque no es posible (hasta donde yo sé ) para codificar valores absolutos.

¿Quizás debería considerar la optimización convexa o la programación semidefinida o algo así?

¿Existe una forma conocida de generar un conjunto de soluciones para un programa lineal y utilizando un objetivo que imponga la "distancia" entre las soluciones?

Una heurística, utilizando programación lineal.

Un enfoque podría ser elegir una función objetivo aleatoria y maximizarla. Luego repita, con un conjunto diferente de funciones objetivas cada vez.

En otras palabras, suponga que las incógnitas son , y tiene algunas restricciones . En cada iteración, elige al azar, luego busca una solución que maximice sujeto a las restricciones .$x_1,x_2,\dots,x_n$$\mathcal{C}$$c_1,c_2,\dots,c_n \in \mathbb{R}$$c_1 x_1 + \dots + c_n x_n$$\mathcal{C}$

Esperaría que esta heurística a menudo encuentre un conjunto de soluciones algo dispersas, no necesariamente dispersas al máximo (lo más lejos posible una de la otra), pero probablemente tampoco demasiado cerca una de la otra.

Maximizar la distancia promedio de L2 por pares, usando programación cuadrática

Alternativamente, use la programación cuadrática. Para simplificar, veamos el problema de encontrar dos soluciones. Suponga que desea dos soluciones que estén tan separadas entre sí como sea posible, bajo la norma (distancia euclidiana). Entonces esto puede formularse como un problema de programación cuadrática .$x,y$$L_2$

Básicamente, desea maximizar la distancia al cuadrado entre e , sujeto al requisito de que tanto como deben Satisfacer las limitaciones. Este es el problema de maximizar una función objetivo cuadrática, con restricciones lineales, es decir, programación cuadrática.$d(x,y)^2 = (x_1-y_1)^2+\cdots+(x_n-y_n)^2$$x$$y$$x$$y$

Si desea puntos que están dispersos al máximo, esto también es posible. Digamos que los puntos son . Entonces podrías maximizar la función objetivo$k$$x^1,\dots,x^k \in \mathbb{R}^n$

es decir, la función

Esta es una función cuadrática, y tiene restricciones lineales en cada uno de los puntos , por lo que esta es una instancia de programación cuadrática. Encuentra puntos que están dispersos al máximo en el sentido de que la distancia promedio por pares se maximiza.$\mathcal{C}$$x^i$

También puede formular una variante codiciosa de este algoritmo, donde ya tiene soluciones, y desea encontrar una solución que satisfaga todas las desigualdades lineales y también maximice la distancia promedio de L2 a las otras soluciones. Eso también puede formularse como un problema de programación cuadrática.$k$$k+1$$k$

La programación cuadrática es más difícil que la programación lineal, pero hay solucionadores que resolverán los problemas de programación cuadrática por usted.

Maximizando la distancia mínima de L2 por pares, usando QCQP

Finalmente, supongamos que desea que sus puntos se dispersen en el sentido de que desea maximizar la distancia mínima por pares. En otras palabras, supongamos que desea encontrar el umbral más grande posible, de modo que sea posible encontrar puntos que satisfagan las restricciones lineales, y de manera que cada par de puntos esté a una distancia uno del otro: para todo . Entonces esto puede formularse como un programa de optimización cuadrática con restricciones cuadráticas, es decir, QCQP . QCQP es aún más difícil, pero también hay soluciones disponibles para QCQP que también puedes probar.$k$$t$$k$$x^1,\dots,x^k \in \mathbb{R}^n$$t$$d(x^i,x^j) \ge t$$i<j$

Encontré un enfoque para generar valores absolutos.

Supongamos que tenemos las variables , , y y un montón de restricciones. Nuestras funciones objetivas se parecen a: maximizar; La idea es que queremos maximizar la norma L1 de estas dos soluciones (según la pregunta original).$a_1$$a_2$$b_1$$b_2$$|a_1 - a_2| + |b_1 - b_2|$

Podemos introducir "variables de holgura" abs_a y abs_b y las restricciones:

y de manera similar para y . Estas restricciones obligan a a ser como máximo la diferencia entre y , y posiblemente menos. En otras palabras, no puede ser mayor que la diferencia máxima entre y .$b_1$$b_2$$\mathrm{abs_a}$$a_1$$a_2$$\mathrm{abs_a}$$a_1$$a_2$

Entonces lo que queda es reemplazar la función objetivo: maximizar .$\mathrm{abs_a} + \mathrm{abs_b}$