How to solve a knapsack problem in CLP(B)

Question

I wonder if there is a way to solve a knapsack problem in CLP(B). CLP(B) seems to be suitable, since packing an item can be modelled as a Boolean variable.

Example:
x1,x2,x3,x4,x5 e {0,1}
x1*12+x2*2+x3*1+x4*1+x5*4 =< 15
maximize x1*4+x2*2+x3*2+x4*1+x5*10

I am little bit at loss how to formulate the side condition of the limited capacity of the knappsack. It seems that SWI-Prolog has weighted_maximum/3 which would allow the optimization.

Picture from https://en.wikipedia.org/wiki/Knapsack_problem

Answer 1

You can model size(weight) constraints by issuing new variables to account for the weight, then use card constraint to model capacity of the backpack and finally using weighted_maximum/2 to maximize objective:

:- use_module(library(clpb)).

knapsack_sample([X1,X2,X3,X4,X5], Maximum):-
  knapsack([X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10], 15, Maximum).

% Data is a list of BucketVar-Value/Weight
knapsack(Data, Capacity, Maximum):-
  buckets(Data, [], [], Buckets, AndEqAll, Weights, Xs),
  sat(card([0-Capacity], Buckets)),
  sat(AndEqAll),
  weighted_maximum(Weights, Xs, Maximum).

buckets([], [EqAll|LEqAll], LBuckets, Buckets, AndEqAll, [], []):-
  foldl(andall, LEqAll, EqAll, AndEqAll),
  append(LBuckets, Buckets).
buckets([X-Count/Weight|Counts], LEqAll, LBuckets, Buckets, AndEqAll, [Weight|Weights], [X|Xs]):-
  length([B|Bs], Count),
  foldl(eqall(X), Bs, (X=:=B), EqAll),
  buckets(Counts, [EqAll|LEqAll], [[B|Bs]|LBuckets], Buckets, AndEqAll, Weights, Xs).

eqall(B, X, Y, (B=:=X)*Y).

andall(X, Y, X*Y).

So in your example you would call knapsack with Data=[X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10] and 15 as capacity:

?- knapsack([X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10], 15, Maximum).
X1 = 0,
X2 = X3, X3 = X4, X4 = X5, X5 = 1,
Maximum = 15.

---

UPDATE:

Actually card constraints handle repetitions fine so there's no need to add new variables, and the solution gets simpler:

knapsack2(Data, Capacity, Maximum):-
  maplist(knap, Data, LBuckets, Weights, Xs),
  append(LBuckets, Buckets),
  sat(card([0-Capacity], Buckets)),
  weighted_maximum(Weights, Xs, Maximum).

knap(X-Value/Weight, Ws, Weight, X):-
  length(Ws, Value),
  maplist(=(X), Ws).

Sample run:

?- knapsack2([X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10], 15, Maximum).
X1 = 0,
X2 = X3, X3 = X4, X4 = X5, X5 = 1,
Maximum = 15.

Answer 2

I have recently added a constraint pseudo/4 in my CLP(B), similar to the constraint scalar_product/4 from CLP(FD), which will not create a circuit, but instead maintain the constraint in a more traditional way. The code reads then:

knapsack([X1,X2,X3,X4,X5], M) :-
   pseudo([12,2,1,1,4], [X1,X2,X3,X4,X5], =<, 15),
   weighted_maximum([4,2,2,1,10], [X1,X2,X3,X4,X5], M).

I compared with the card/2 formulation. Unlike the pseudo/4 formulation, the card/2 formulation will created a circuit under the hood. This is both the case for my system, as well as for SWI-Proilog:

knapsack3([X1,X2,X3,X4,X5], M) :-
   sat(card([0-15],[X1,X1,X1,X1,X1,X1,X1,X1,X1,X1,X1,X1,X2,X2,X3,X4,X5,X5,X5,X5])),
   weighted_maximum([4,2,2,1,10], [X1,X2,X3,X4,X5], M).

I did some tests, also measuring the model set-up time. The new pseudo/4 constraint seems to be the winner for this example. Here are the results in my system:

Jekejeke Prolog 3, Runtime Library 1.3.8 (May 23, 2019)

?- time((between(1,100,_), knapsack(_,_), fail; true)).
% Up 95 ms, GC 3 ms, Thread Cpu 93 ms (Current 07/05/19 20:03:05)
Yes

?- time((between(1,100,_), knapsack3(_,_), fail; true)).
% Up 229 ms, GC 5 ms, Thread Cpu 219 ms (Current 07/05/19 20:02:58)
Yes

And here is the result in SWI-Prolog:

?- time((between(1,100,_), knapsack3(_,_), fail; true)).
% 8,229,000 inferences, 0.656 CPU in 0.656 seconds (100% CPU, 12539429 Lips)