Search code examples
prologbranch-and-bound

Branch and bound without assert / retract

This exercise asked me to find the best combination of three products, given the prices and specific combinations to avoid. The textbook employs assertz and retractall to emulate a state variable.


price(a1, 1900).
price(a2,  750).
price(a3,  900).
price(b1,  300).
price(b2,  500).
price(b3,  450).
price(b4,  600).
price(c1,  700).
price(c2,  850).

incompatible(a2, c1).
incompatible(b2, c2).
incompatible(b3, c2).
incompatible(a2, b4).
incompatible(a1, b3).
incompatible(a3, b3).

:- dynamic bound/1.
bound(5000).

solution(A, B, C, P) :-
  member(A, [a1, a2, a3]), 
  price(A, PA),
  member(B, [b1, b2, b3, b4]),
  \+ incompatible(A, B),
  price(B, PB),
  P0 is PA + PB,
  bound(Bound),
  write('Current bound: '), writeln(Bound),
  P0 =< Bound,
  member(C, [c1, c2]),
  \+ incompatible(A, C),
  \+ incompatible(B, C),
  price(C, PC),
  P is PA + PB + PC,
  P =< Bound,
  retractall(bound(_)),
  assertz(bound(P)).
  1. Is it possible to use branch and bound in Prolog without resorting to dynamic predicates?
  2. Is there a consensus on state variables in Prolog?
  3. Is there a way to restrict the scope of a state variable (or whatever the proxy would be) to a single rule?
Solution

  • Your solution is not always using the proper Bound upon backtracking. The problem is that the variable gets bound too soon and then even if the fact gets updated with assertz/retract the variable will still be bound to the previous value. You can see the effects by letting the toplevel backtrack through all the solutions. There are some solutions intersped that have higher cost than a previous one.

    Here goes an iterative solution customized to your problem, though you could probably make it more general by using call/N instead of the fixed calls to price/2 and any_incompatible/2

    solution2(Bound, Best):-
  branch_and_bound([[a1,a2,a3],[b1,b2,b3,b4],[c1,c2]], Bound, [], Best).

branch_and_bound([[]|_], _, Best, Best).
branch_and_bound([[Item|Layer]|Layers], Bound, CurrentBest, Best):-
  price(Item, ItemPrice),
  (  ItemPrice >= Bound
  ->  Bound1-CurrentBest1=Bound-CurrentBest
  ;   branch_and_bound(Layers, Bound, Bound1, current(ItemPrice, [Item]), CurrentBest, CurrentBest1)
  ),
  branch_and_bound([Layer|Layers], Bound1, CurrentBest1, Best).

branch_and_bound([], Bound, CurrentPrice, current(CurrentPrice, Items), PreviousBest, [best(CurrentPrice, RItems)|OtherBest]):-
  reverse(Items, RItems),
  ( CurrentPrice==Bound -> OtherBest=PreviousBest ; OtherBest=[] ).
branch_and_bound([[]|_], Bound, Bound, _, Best, Best).
branch_and_bound([[Item|Layer]|Layers], Bound, Bound2, current(CurrentPrice, Items), CurrentBest, Best):-
  price(Item, ItemPrice),
  NewPrice is CurrentPrice + ItemPrice,
  (
     ( NewPrice > Bound ; any_incompatible(Items, Item) )
  ->   Bound1-CurrentBest1=Bound-CurrentBest
  ;    branch_and_bound(Layers, Bound, Bound1, current(NewPrice, [Item|Items]), CurrentBest, CurrentBest1)
  ),
  branch_and_bound([Layer|Layers], Bound1, Bound2, current(CurrentPrice, Items), CurrentBest1, Best).

any_incompatible([OneItem|Items], Item):-
  incompatible(OneItem, Item) -> true ; any_incompatible(Items, Item).

    It will list all the best solutions, trimming the search space with the current Bound defined by the currently found best solution.

    Sample run:

    ?- solution2(5000, Best).
Best = [best(1900, [a3, b1, c1]), best(1900, [a2, b1, c2])].