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 .
The lines are numbered, using the syntax: lib(apply_macros). solve(PocketCoins,Min) : PocketCoins=[P,Tw,Fv,Te,Twe,Ff], %1 applist(range(0,99),[MinPocketCoins]), %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). %9Conceptual Model for the Coins Problem
%N
, as %
is a
comment symbol in ECLiPSe.
We describe this program line by line.

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.=
P+Tw+Fv+Te+Twe+Ff.=
P1+ 2*Tw1 + 5*Fv1 + 10*Te1 + 20*Twe1 + 50*Ff1.<=
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),[MinPocketCoins]), 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),[MinPocketCoins]), 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..Maxfd 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.