Different results when using library(simplex) or R-package lpSolve / lpSolveAPI

Hi,

One of the exercises from the course material for the Linear Programming course, involved baking cakes. For chocolate, vanilla, and lemon cakes it is known how many eggs and how much flour are needed and what is the baking time. The question is to maximize the profit.

This is the model in lpSolveAPI:

library (lpSolveAPI)

result <- make.lp(3,3)
set.column(result, 1, c(4, 4, 20))
set.column(result, 2, c(2, 5, 40))
set.column(result, 3, c(6, 6, 50))
set.objfn(result, c(3, 5, 7))
set.constr.type(result, rep("<=", 3))
set.rhs(result, c(32, 40, 260))
lp.control(result, sense = "max")
set.type(result, 1, "integer")
set.type(result, 2, "integer")
set.type(result, 3, "integer")
dimnames(result) <- list(c("Ei", "Bloem", "Tijd"), c("Chocola", "Vanille", "Citroen"))

4 Chocolate, 2 vanilla and 2 lemmon cakes give a profit of 36

I have defined the same problem with library(simplex):

:- use_module(library(simplex)).

cakes_3(S) :-
        gen_state(S0),
        post_constraints_v3(S0, S1),
        maximize([3*chocola, 5*vanille, 7*citroen], S1, S).

post_constraints_v3 -->
        constraint([4*chocola, 2*vanille, 6*citroen] =< 32),
        constraint([4*chocola, 5*vanille, 6*citroen] =< 40),
        constraint([20*chocola, 40*vanille, 50*citroen] =< 260),
        constraint(integral(chocola)),
        constraint(integral(vanille)),
        constraint(integral(citroen)),
        constraint([chocola] >= 0),
        constraint([vanille] >= 0),
        constraint([citroen] >= 0).


test_cakes_v3 :- cakes_3(S),
        variable_value(S, chocola, Val1),
        variable_value(S, vanille, Val2),
        variable_value(S, citroen, Val3),
        writeln(Val1),
        writeln(Val2),
        writeln(Val3), nl,
        result(Val1, Val2, Val3), nl.

result(A, B, C) :-
        Ei    is A*4 +  B*2 +  C*6, writeln(Ei),
        Bloem is A*4 +  B*5 +  C*6, writeln(Bloem),
        Tijd  is A*20 + B*40 + C*50, writeln(Tijd),
        Winst is A*3 +  B*5 +  C*7, writeln(Winst).

Now 1 Chocolate, 1 vanilla and 4 lemmon cakes give a profit of 36

Both solutions are correct.

My question is why both environments produce diffent results? And since both solutions are correct, is it possible to have simplex return all the solutions?

Ben

They get different results because there are different methods to find the optimum. When an optimum is found, the algorithm stops.

In most cases, there is only one optimum, but in some cases there can be many, or when the integral constraint is gone, infinite numbers. For 3 variable problems, it’s reasonable to enumerate all the solutions, but for large integer problems, each possible solution could be very slow to find.

FWIW, when using pack(clpBNR) this is done in two steps for this reason. First find the global maximum, then the set of “maximizers” corresponding to that maximum. In general, the second step is non-deterministic.

?- [Choc,Van,Cit]::integer(0,_),
{4*Choc+2*Van+6*Cit=<32, 4*Choc+5*Van+6*Cit=<40, 20*Choc+40*Van+50*Cit=<260},
global_maximum(3*Choc+5*Van+7*Cit, Profit).
Profit = 36,
Choc::integer(0, 8),
Van::integer(0, 6),
Cit::integer(0, 5).

?- [Choc,Van,Cit]::integer(0,_),
{4*Choc+2*Van+6*Cit=<32, 4*Choc+5*Van+6*Cit=<40, 20*Choc+40*Van+50*Cit=<260},
global_maximum(3*Choc+5*Van+7*Cit, Profit),
enumerate([Choc,Van,Cit]).
Choc = Van, Van = 1,
Cit = 4,
Profit = 36 ;
Choc = 4,
Van = Cit, Cit = 2,
Profit = 36 ;
false.

Finding the global maximum partially narrows the domains, but a subsequent labelling step is required to separate the solutions.

2 Likes

Thaks for the hint. I have installed the package and start experimenting with it.

If the focus of the course is linear programming, just note that linear programming techniques are not used in in this clpBNR solution.

IMO, it’s a bit unfortunate that the simplex library chooses to bind (narrow) the “maximizer” values when determining the maximum value for the objective function. If it just treated it as another constraint to be applied, standard labelling could generate all the solutions.