¿Cómo representar las restricciones de los problemas de optimización en un modelo de datos?

Question

En este momento estoy escribiendo un programa centrado en la asignación de activos y estoy pensando en cómo debería representar mis restricciones en el modelo de datos.

El primer enfoque que se me ocurrió fue definir algunas categorías para clasificar las restricciones de modo que pudieran almacenarse en una tabla según su "categoría" (por ejemplo, restricciones unarias x>=y, restricciones binarias y

Entonces se me ocurrió otra idea que es definir mi propio "lenguaje de restricciones" con su propia gramática y almacenarlo como un string en la base de datos (como Sum("Equities")<Percent(20,Portfolio) ). Esto implicaría escribir un analizador sintáctico. También podría optar por utilizar una representación XML de las restricciones para utilizar uno de los muchos analizadores XML.

Quería saber si alguien tiene otra posible solución y si conocéis algún documento que hable de este tema.

Answer 1

Mucha gente utiliza lenguajes/formatos de modelización matemática como el propietario AMPL (véase http://en.wikipedia.org/wiki/AMPL ) o MPS (véase http://en.wikipedia.org/wiki/MPS_%28format%29 ) para definir los problemas de optimización. También existen alternativas de código abierto para un subconjunto de problemas (como por ejemplo el kit de programación lineal de GNU con su lenguaje).

Hans Mittelmann ha reunido una gran cantidad de información útil, incluyendo casos de prueba bajo http://plato.asu.edu/guide.html . Sin embargo, utilizar un optimizador que entienda, por ejemplo, AMPL puede no ser el mejor enfoque.

Answer 2

Esto parece que sería muy adecuado para la implementación en un Prolog. Esa familia de lenguajes está construida alrededor de un modelo de programación de restricciones. En concreto, echa un vistazo a ECLiPSe . Es maduro (desarrollado originalmente en los 90 por Cisco, creo) y tiene ganchos externos para, por ejemplo, Java y C++ si no quieres implementar todo tu sistema en prolog.

Los prologs son muy adecuados para los problemas de programación y distribución: distribuir esta suma de tiempo/dinero/puntos de alguna manera que satisfaga esta otra lista de restricciones.

Cabe destacar que las restricciones son declarativas, por lo que basta con añadir nuevas restricciones o eliminar las antiguas y volver a ejecutar el programa para obtener nuevos resultados sin tener que reconstruir o volver a compilar el código principal.