Is Prolog the best language to solve this kind of problem?

Question

I have this problem containing some inequations and requirement to minimize a value. After doing some research on the Internet, I came to conclusion that using Prolog might be the easiest way to solve it. However, I never used Prolog before, and I would hate to waste my time learning it just to discover that it is not the right tool for this job.

Please, if you know Prolog, take a look at this problem and tell me if Prolog is the right one. Or, if you know of some other language that is really suited for this.

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 need to find the values for a, b, c, d, e, f, g and h that minimize w.

Please note that the above is only an example. In real program, I would use up to 10000 variables and up to 20 if..then clauses. This rules out linear programming as an alternative technique because it would take a prohibitive amount of RAM and time to test all LP problems.

I'm not really asking for code, although I'd be grateful for some hint how to tackle this if Prolog is really good for it. Thanks.

Answer 1

I haven't worked with similar problems before, so I can't give you any direct suggestions. However, I would not use Prolog for it. Prolog is really good for dealing with symbolic problems (a classic example would be the Einstein puzzle), but its math support is very awkward; it feels like math was tacked on as an afterthought.

Answer 2

You can solve this using linear programming (LP), but the problem needs some modification before you can chuck it into an LP solver. An LP problem basically involves maximising or minimising a function given some constraints.

First, split the problem into two problems (as LP does not support the two if conditions you have):

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

And

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

After you run both separately by the LP solver, the solution will come out with the values of a, b, c, d, e, f, g, h and w. Pick the smaller value of w and the corresponding values of a, b, c, d, e, f, g, h.

How does this work?

The two if conditions are effectively similar to the other constraints listed, just that they entail different values of x and y. Since the two conditions are mutually exclusive (given that both cannot be satisfied as x and y will hence have different values), you can split them into two separate LP problems. As a result, you solve the LP problems individually, and hence you will arrive at a minimised value of w.

For an LP solver, go to the linear programming Wikipedia article as linked above. There are tools like Excel and some others which are easier to use, but if you want a program, then there are numerical languages which are good at this, or general purpose languages like C that can do this with a library like glpk.

Hope this helps!

Answer 3

You could have a look at Constraint Logic Programming, either CLP(R), CLP(Q) or CLP(FD). Your problem can be encoded into CLP(R) as follows (I think):

:- 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