Problem Pizza Voucher
From the Intelligent Systems CMPT 417 course at Simon Fraser University. The problem arises in the University College Cork student dorms. There is a large order of pizzas for a party, and many of the students have vouchers for acquiring discounts in purchasing pizzas. A voucher is a pair of numbers e.g. (2,4), which means if you pay for 2 pizzas then you can obtain for free up to 4 pizzas as long as they each cost no more than the cheapest of the $2$ pizzas you paid for. Similarly a voucher (3,2) means that if you pay for 3 pizzas you can get up to 2 pizzas for free as long as they each cost no more than the cheapest of the 3 pizzas you paid for. The aim is to obtain all the ordered pizzas for the least possible cost. Note that not all vouchers need to be used.
A Nice Pizza Slice. Image from freesvg.org 
To build a COP (Constraint Optimization Problem) model, we need first to import the library PyCSP$^3$:
from pycsp3 import *
Then, we need some data. For vouchers, we use named tuples.
prices = [50, 60, 90, 70, 80, 100, 20, 30, 40, 10] # prices of pizzas
Voucher = namedtuple('Voucher', 'pay free')
vouchers = [
Voucher(1,2), Voucher(2,3), Voucher(1,1), Voucher(0,1), Voucher(2,1),
Voucher(2,2), Voucher(3,3), Voucher(1,0), Voucher(3,2)
]
nPizzas, nVouchers = len(prices), len(vouchers)
We can check the vouchers.
print(vouchers)
[Voucher(pay=1, free=2), Voucher(pay=2, free=3), Voucher(pay=1, free=1), Voucher(pay=0, free=1), Voucher(pay=2, free=1), Voucher(pay=2, free=2), Voucher(pay=3, free=3), Voucher(pay=1, free=0), Voucher(pay=3, free=2)]
We start our COP model with an array $v$ of 10 variables (one per pizza).
# v[i] is the voucher used for the ith pizza. 0 means that no voucher is used.
# A negative (resp., positive) value i means that the ith pizza contributes
# to the the pay (resp., free) part of voucher |i|.
v = VarArray(size=nPizzas, dom=range(-nVouchers, nVouchers + 1))
We can display (the structure of) the array as well as the domain of the first variable.
print("Array of variable v ", v)
print("Domain of any variable: ", v[0].dom)
Array of variable v [v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]]
Domain of any variable: -9..9
To control the way vouchers are used, we need to be able to count for each voucher the number of times a pizza corrsponds to the pay or free part of this voucher. This is the reason why we introduce the two following arrays:
# p[i] is the number of paid pizzas wrt the ith voucher
p = VarArray(size=nVouchers, dom=lambda i: {0, vouchers[i].pay})
# f[i] is the number of free pizzas wrt the ith voucher
f = VarArray(size=nVouchers, dom=lambda i: range(vouchers[i].free + 1))
We can post two groups of constraints Count for computing the value of these variables.
satisfy(
# counting paid pizzas
[Count(v, value=-i - 1) == p[i] for i in range(nVouchers)],
# counting free pizzas
[Count(v, value=i + 1) == f[i] for i in range(nVouchers)]
);
We can display the internal representation of the posted constraints; this way, although a little bit technical, we can see that the constraints are correctly formed (note that ‘eq’ stands for ‘equal to’).
print(posted())
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-1], condition:(eq,p[0]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-2], condition:(eq,p[1]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-3], condition:(eq,p[2]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-4], condition:(eq,p[3]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-5], condition:(eq,p[4]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-6], condition:(eq,p[5]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-7], condition:(eq,p[6]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-8], condition:(eq,p[7]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[-9], condition:(eq,p[8]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[1], condition:(eq,f[0]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[2], condition:(eq,f[1]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[3], condition:(eq,f[2]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[4], condition:(eq,f[3]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[5], condition:(eq,f[4]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[6], condition:(eq,f[5]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[7], condition:(eq,f[6]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[8], condition:(eq,f[7]))
count(list:[v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9]], values:[9], condition:(eq,f[8]))
By calling the function solve(), we can check that the problem is satisfiable (SAT). We can also display the values assigned to the variables in the found solution by calling the function value().
if solve() is SAT:
print(values(v))
[-9, -9, -9, -8, -7, -7, -7, -6, -6, -3]
In this solution, we only pay for pizzas while never benefiting from free ones. This is the moment to post the following objective:
minimize(
# minimizing summed up costs of pizzas
Sum((v[i] <= 0) * prices[i] for i in range(nPizzas))
);
We can run again the solver, with this optimization task. Note that we need to check that the status returned by the solver is now OPTIMUM.
if solve() is OPTIMUM:
print("Used vouchers: ", values(v))
print("Overall cost: ", bound())
for i in range(nVouchers):
print(f" voucher {i}: paid={p[i].value} free={f[i].value}")
Used vouchers: [3, 4, 5, 6, 6, 1, 2, 2, 2, 1]
Overall cost: 0
voucher 0: paid=0 free=2
voucher 1: paid=0 free=3
voucher 2: paid=0 free=1
voucher 3: paid=0 free=1
voucher 4: paid=0 free=1
voucher 5: paid=0 free=2
voucher 6: paid=0 free=0
voucher 7: paid=0 free=0
voucher 8: paid=0 free=0
We have a new problem: all pizzas are considered to be free. We need to control the fact that a pizza can only be free when some pizzas have been paid. We post a group of constraints Intension:
satisfy(
# a voucher, if used, must contribute to have at least one free pizza.
(f[i] == 0) == (p[i] != vouchers[i].pay) for i in range(nVouchers)
);
We can display these last posted constraints:
print(posted(-1))
intension(function:iff(eq(f[0],0),ne(p[0],1)))
intension(function:iff(eq(f[1],0),ne(p[1],2)))
intension(function:iff(eq(f[2],0),ne(p[2],1)))
intension(function:iff(eq(f[3],0),ne(p[3],0)))
intension(function:iff(eq(f[4],0),ne(p[4],2)))
intension(function:iff(eq(f[5],0),ne(p[5],2)))
intension(function:iff(eq(f[6],0),ne(p[6],3)))
intension(function:iff(eq(f[7],0),ne(p[7],1)))
intension(function:iff(eq(f[8],0),ne(p[8],3)))
After introducing the following auxiliary functions:
def paid(i):
return [prices[j] for j in range(nPizzas) if v[j].value == -i-1]
def free(i):
return [prices[j] for j in range(nPizzas) if v[j].value == i+1]
we run the solver as follows:
if solve() is OPTIMUM:
print("Used vouchers: ", values(v))
print("Overall cost: ", bound())
for i in range(nVouchers):
print(f" voucher {i}: paid={paid(i)} free={free(i)}")
Used vouchers: [1, 6, 4, 1, 6, 3, -1, -6, -6, -3]
Overall cost: 100
voucher 0: paid=[20] free=[50, 70]
voucher 1: paid=[] free=[]
voucher 2: paid=[10] free=[100]
voucher 3: paid=[] free=[90]
voucher 4: paid=[] free=[]
voucher 5: paid=[30, 40] free=[60, 80]
voucher 6: paid=[] free=[]
voucher 7: paid=[] free=[]
voucher 8: paid=[] free=[]
One can see that the prizes of the free pizzas is greater than the prize of the paid pizzas. This is a problem we fix with a group of constraints Intension, built with the structure If:
satisfy(
# a free pizza obtained with a voucher must be cheaper than any pizza paid wrt this voucher
If(
v[i] < 0,
Then=v[i] != -v[j]
) for i in range(nPizzas) for j in range(nPizzas) if prices[i] < prices[j]
);
With this last attempt, we obtain a valid optimal solution:
if solve() is OPTIMUM:
print("Used vouchers: ", values(v))
print("Overall cost: ", bound())
for i in range(nVouchers):
print(f" voucher {i}: paid={paid(i)} free={free(i)}")
Used vouchers: [-2, -2, -1, 1, 1, 4, 2, 2, 2, 0]
Overall cost: 210
voucher 0: paid=[90] free=[70, 80]
voucher 1: paid=[50, 60] free=[20, 30, 40]
voucher 2: paid=[] free=[]
voucher 3: paid=[] free=[100]
voucher 4: paid=[] free=[]
voucher 5: paid=[] free=[]
voucher 6: paid=[] free=[]
voucher 7: paid=[] free=[]
voucher 8: paid=[] free=[]
Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line).
from pycsp3 import *
prices, vouchers = data
nPizzas, nVouchers = len(prices), len(vouchers)
# v[i] is the voucher used for the ith pizza. 0 means that no voucher is used.
# A negative (resp., positive) value i means that the ith pizza contributes
# to the the pay (resp., free) part of voucher |i|.
v = VarArray(size=nPizzas, dom=range(-nVouchers, nVouchers + 1))
# p[i] is the number of paid pizzas wrt the ith voucher
p = VarArray(size=nVouchers, dom=lambda i: {0, vouchers[i].pay})
# f[i] is the number of free pizzas wrt the ith voucher
f = VarArray(size=nVouchers, dom=lambda i: range(vouchers[i].free + 1))
satisfy(
# counting paid pizzas
[Count(v, value=-i - 1) == p[i] for i in range(nVouchers)],
# counting free pizzas
[Count(v, value=i + 1) == f[i] for i in range(nVouchers)],
# a voucher, if used, must contribute to have at least one free pizza.
[(f[i] == 0) == (p[i] != vouchers[i].pay) for i in range(nVouchers)],
# a free pizza obtained with a voucher must be cheaper than any pizza paid wrt this voucher
[
If(
v[i] < 0,
Then=v[i] != -v[j]
) for i in range(nPizzas) for j in range(nPizzas) if prices[i] < prices[j]
]
)
minimize(
# minimizing summed up costs of pizzas
Sum((v[i] <= 0) * prices[i] for i in range(nPizzas))
)