Est-ce que Prolog est le meilleur langage pour résoudre ce genre de problème?

Question

J'ai ce problème contenant des inéquations et des exigences pour minimiser une valeur. Après avoir fait quelques recherches sur Internet, je suis arrivé à la conclusion que l'utilisation de Prolog pourrait être le moyen le plus simple de le résoudre. Cependant, je n'ai jamais utilisé Prolog auparavant, et je détesterais perdre mon temps à l'apprendre juste pour découvrir que ce n'est pas le bon outil pour ce travail. S'il vous plaît, si vous connaissez Prolog, jetez un oeil à ce problème et dites-moi si Prolog est le bon. Ou, si vous connaissez un autre langage qui est vraiment adapté pour cela.

a + b + c >= 100 
d + e + f >= 50 
g + h  >= 30 

if (8b + 2e + 7h > 620) then y = 0.8 else y = 1.0 
if (d > 35)    then x = 0.9 else x = 1.0 

5xa + 8yb + 5c + 3xd + 2ye + 2f + 6xg + 7yh = w. 

I besoin de trouver les valeurs pour a, b, c, d, e, f, g et h qui minimise w.

Veuillez noter que ce qui précède n'est qu'un exemple. En vrai programme, j'utiliserais jusqu'à 10000 variables et jusqu'à 20 si..then clauses. Ceci exclut la programmation linéaire comme technique alternative car il faudrait une quantité de RAM et un temps prohibitifs pour tester tous les problèmes de LP.

Je ne demande pas vraiment de code, bien que je vous serais reconnaissant de me donner quelques indices sur la façon de résoudre ce problème si Prolog est vraiment bon pour cela. Merci.

Answer 1

Je n'ai pas travaillé avec des problèmes similaires auparavant, donc je ne peux pas vous donner de suggestions directes. Cependant, je n'utiliserais pas Prolog pour cela. Prolog est vraiment bon pour traiter les problèmes symboliques (un exemple classique serait le Einstein puzzle), mais son support mathématique est très gênant; On a l'impression que les mathématiques ont été ajoutées après coup.

Answer 2

Vous pouvez résoudre ce problème en utilisant linear programming (LP), mais le problème doit être modifié avant de pouvoir le placer dans un solveur LP. Un problème de PL implique essentiellement de maximiser ou de minimiser une fonction avec certaines contraintes.

Tout d'abord, diviser le problème en deux problèmes (comme LP ne supporte pas les deux if conditions que vous avez):

Constraints: 
a + b + c >= 100 
d + e + f >= 50 
g + h  >= 30 
8b + 2e + 7h > 620 

Linear function: 
5 * 0.8a + 8 * 1.0b + 5c + 3 * 0.8d + 2 * 1.0e + 2f + 6 * 0.8g + 7 * 1.0h = w 

Et

Constraints: 
a + b + c >= 100 
d + e + f >= 50 
g + h  >= 30 
d > 35 

Linear function: 
5 * 1.0a + 8 * 0.9b + 5c + 3 * 1.0d + 2 * 0.9e + 2f + 6 * 1.0g + 7 * 0.9h = w 

Après avoir exécuté les deux séparément par le solveur LP , la solution sortira avec les valeurs de a, b, c, d, e, f, g, h et w. Choisissez la plus petite valeur de w et les valeurs correspondantes de a, b, c, d, e, f, g, h.

Comment ça marche?

Les deux conditions if sont effectivement similaires aux autres contraintes listées, mais elles impliquent des valeurs différentes de x et y. Puisque les deux conditions sont mutuellement exclusives (étant donné que les deux ne peuvent pas être satisfaites car x et y auront des valeurs différentes), vous pouvez les séparer en deux problèmes distincts. En conséquence, vous résolvez les problèmes de LP individuellement, et donc vous arriverez à une valeur minimisée de w.

Pour un solveur LP, accédez à l'article de programmation linéaire Wikipédia ci-dessus. Il y a des outils comme Excel et d'autres qui sont plus faciles à utiliser, mais si vous voulez un programme, il y a des langages numériques qui sont bons, ou des langages généraux comme C qui peuvent le faire avec une librairie comme glpk.

Espérons que cela aide!

Answer 3

Vous pourriez jeter un oeil à la programmation logique de contrainte, soit CLP (R), CLP (Q) ou CLP (FD). Votre problème peut être codé dans CLP (R) comme suit (je pense):

 
:- use_module(library(clpr)). 

test(sol([A,B,C,D,E,F,G,H], [X,Y,W])) :- 
    {A >=0, B >=0, C>=0, D>=0, E>=0, F>=0, G>=0, H>=0}, 
    {A + B + C >= 100}, 
    {D + E + F >= 50}, 
    {G + H  >= 30}, 
    {5*X*A + 8*Y*B + 5*C + 3*X*D + 2*Y*E + 2*F + 6*X*G + 7*Y*H = W}, 
    (({8*B + 2*E + 7*H > 620},{Y=0.8}) ; ({8*B + 2*E + 7*H =35},{X=0.9}) ; ({D= 

Using SICStus Prolog, I get the following answer:
 


| ?- test(A). 
A = sol([_A,0.0,_B,0.0,_C,_D,30.0,0.0],[1.0,1.0,780.0]), 
{_A=100.0-_B}, 
{_C=50.0-_D}, 
{_B==0.0}, 
{_D>=0.0} ? ; 
no