Having Enough Change in Your Pocket

Let us now take a more interesting problem, which has been set as a recent challenge within the MIP community. The problem is apparently rather simple: what is the minimum number of coins a purchaser needs in their pocket in order to be able to buy any one item costing less than one pound, and guarantee to be able to pay the exact amount?

The problem involves only six decision variables, one for the number of coins of each denomination held in the pocket (the denominations are 1,2,5,10,20,50).

The conceptual model for this problem is shown in figure .

:- lib(apply_macros).

solve(PocketCoins,Min) :-                                
        PocketCoins=[P,Tw,Fv,Te,Twe,Ff],                 %1
        applist(range(0,99),[Min|PocketCoins]),          %2
        Min = P+Tw+Fv+Te+Twe+Ff,                         %3
        fromto(1,99,genc(PocketCoins)),                 %4
        minimize(Min).                                   %5

genc(PocketCoins,Total) :-                               
        Coins=[P1,Tw1,Fv1,Te1,Twe1,Ff1],                 %6
        applist(range(0,99),Coins),                      %7
        Total = P1+2*Tw1+5*Fv1+10*Te1+20*Twe1+50*Ff1,    %8
        maplist( '<=',Coins,PocketCoins).                %9

Conceptual Model for the Coins Problem  

The lines are numbered, using the syntax %N, as % is a comment symbol in ECLiPSe. We describe this program line by line.

1. The variable PocketCoins is just a shorthand for the list of six variables, [P, Tw, Fv, Te, Twe, Ff] which denote the number of coins of each denomination held in the pocket.
2. [A,B,C] is a list, but ECLiPSe allows lists to be written in an alternative syntax [Head | Tail]. Thus [Min | PocketCoins] is simply another way of writing the list of seven variables, [Min, P, Tw, Fv, Te, Twe, Ff]. The command applist(range(0,99), [Min | PocketCoins]) associates a range (between 0 and 99) with each of the variables.
3. Min is the total number of coins in the pocket, as enforced by the equation Min = P+Tw+Fv+Te+Twe+Ff.
4. To ensure that these coins are enough to make up any total between 1 and 99, we now impose 99 further constraints, one for each total. genc(PocketCoins,Total) is called for each value of Total between 1 and 99.
5. minimize(Min) simply specifies that the best feasible solution to the problem is one which minimises the value of the variable Min.
6. genc(PocketCoins,Total) initialises another set of coins [P1, Tw1, Fv1, Te1, Twe1, Ff1] needed to make up the total Total.
7. This set of coins is also initialised to range between 0 and 99
8. Their total value is constrained to be equal to Total. This constraint is enforced by the equation Total = P1+ 2*Tw1 + 5*Fv1 + 10*Te1 + 20*Twe1 + 50*Ff1.
9. Finally the constraint that the required coins of each denomination must be less than, or equal to, the number of coins of that denomination in the pocket, is enforced by the constraints: P1 <= P, Tw1 <= Tw, Fv1 <= Fv, Te1 <= Te, Twe1 <= Twe, Ff1 <= Ff.

   These constraints are generated by the single command maplist( <=, Coins, PocketCoins).

Let's start by trying mixed integer programming on this problem. To do this we add integer declarations for each of the integer variables, and change the constraints to use the syntax recognised by the (external) MIP solver accessed via the ECLiPSe library eplex. For equations we use the syntax $=, and for inequalities we use $>=. The design model is shown below.

:- lib(apply_macros).
:- lib(eplex).

solve(PocketCoins,Cost) :-
        PocketCoins=[P,Tw,Fv,Te,Twe,Ff],
        applist(range(0,99),[Min|PocketCoins]),
        Min $= P+Tw+Fv+Te+Twe+Ff,
        fromto(1,99,genc(PocketCoins)),
        optimize(min(Min),Cost).

genc(PocketCoins,Total) :-
        Coins=[P1,Tw1,Fv1,Te1,Twe1,Ff1],
        applist(range(0,99),Coins),
        Total $= P1+2*Tw1+5*Fv1+10*Te1+20*Twe1+50*Ff1,
        maplist( '$=<',Coins,PocketCoins).

range(Min,Max,Var) :-
        integers(Var),
        Var $>= Min,
        Var $=< Max.

Conceptual Model for the Coins Problem  

This program passes all the {$= and $>= constraints to the CPLEX mixed integer programming package [CPL93], and invokes the CPLEX branch and bound solver, to minimise the value of the variable Min. This minimum is placed in the variable Cost.

As such this model can only solve the problem of producing the exact change up to 59 pence (replacing 99 with 59 in the above program). For the full problem the system runs out of memory. There are standard MIP solutions to the problem which run overnight, but it is a tough challenge to reduce this time from hours to minutes!

In figure we illustrate an ECLiPSe program for solving the ``Coins'' problem using the facilities of the ECLiPSe finite domain constraint solver implemented in the ECLiPSe library fd.

:- lib(apply_macros).
:- lib(fd).

solve(PocketCoins,Min) :-
        PocketCoins=[P,Tw,Fv,Te,Twe,Ff],
        applist(range(0,99),[Min|PocketCoins]),
        Min #= P+Tw+Fv+Te+Twe+Ff,
        fromto(1,99,genc(PocketCoins)),
        minimize(labeling(PocketCoins),Min).


genc(PocketCoins,Total) :-
        Coins=[P1,Tw1,Fv1,Te1,Twe1,Ff1],
        applist(range(0,99),Coins),
        Total #= P1+2*Tw1+5*Fv1+10*Te1+20*Twe1+50*Ff1,
        maplist( '#<=',Coins,PocketCoins).

range(Min,Max,Var) :-
        Var::Min..Max

fd Constraints for the Coins Problem  

In this case the #= and #>= constraints and the optimisation predicate minimize are implemented in the ECLiPSe finite domain library. This program proves within a few seconds that the minimum number of coins a purchaser needs in their pocket to make up any total between 1 and 99 is eight coins! One solution is: P=1, Tw=2, Fv=1, Te=1, Twe=2, Ff=1.

We have shown how the same underlying model for the ``Coins'' problem can be passed to different solvers so as to use the best one. However in ECLiPSe it is not a choice of either/or: the same constraints can easily be passed to several solvers at the same time! For instance we can define X $#= Y to be both X $= Y and X #= Y and replace = in the above model with $#=, and we can treat >= similarly.

Whilst for this problem the finite domain solver alone solves the problem most efficiently, we have encountered practical examples where the combination of both solvers outperforms each on its own.