In [1]:
import pulp as p

Shopping with a Data Scientist


In [2]:
model_a = p.LpProblem("Albon Shopping Problem", p.LpMinimize)

We define four cable types: Lightning, Micro-USB, USB, and USB-C (encoded below as $L$, $U^m$, $U$, and $U^c$ respectively). Each is available in 1 foot, 3 feet, and 6 feet lengths (encoded below as subscripts of 1, 3, and 6 respectively).


In [3]:
lightning_1 = p.LpVariable('lightning_1', lowBound=0, cat='Integer')
lightning_3 = p.LpVariable('lightning_3', lowBound=0, cat='Integer')
lightning_6 = p.LpVariable('lightning_6', lowBound=0, cat='Integer')

microusb_1 = p.LpVariable('microusb_1', lowBound=0, cat='Integer')
microusb_3 = p.LpVariable('microusb_3', lowBound=0, cat='Integer')
microusb_6 = p.LpVariable('microusb_6', lowBound=0, cat='Integer')

usb_1 = p.LpVariable('usb_1', lowBound=0, cat='Integer')
usb_3 = p.LpVariable('usb_3', lowBound=0, cat='Integer')
usb_6 = p.LpVariable('usb_6', lowBound=0, cat='Integer')

usbc_1 = p.LpVariable('usbc_1', lowBound=0, cat='Integer')
usbc_3 = p.LpVariable('usbc_3', lowBound=0, cat='Integer')
usbc_6 = p.LpVariable('usbc_6', lowBound=0, cat='Integer')

Our objective function is expressed a bit tersely in math but is perhaps more readable in code. The cost of each cord we make related to length. 1 foot cords cost \$10, 3 feet cords cost \$15, and 6 feet cords cost \$20. Ideally, we want to minimize our costs subject to the constraints.

$$ F = 10 * (L_1 + U^{m}_1 + U_1 + U^{c}_1) + 15 * (L_3 + U^{m}_3 + U_3 + U^{c}_3) + 20 * (L_6 + U^{m}_6 + U_6 + U^{c}_6)$$

In [4]:
model_a +=   10 * (lightning_1 + microusb_1 + usb_1 + usbc_1) \
         + 15 * (lightning_3 + microusb_3 + usb_3 + usbc_3) \
         + 20 * (lightning_6 + microusb_6 + usb_6 + usbc_6), "Cost"

Next we need a way to identify which cables can be used with which devices. The below code codifies this. The mathematical expressions are left as an exercise for the reader.


In [5]:
power_supply_connectors = usbc_6
ipad_connectors = lightning_1 + lightning_3 + lightning_6
iphone_connectors = ipad_connectors
android_connectors = microusb_1 + microusb_3 + microusb_6
camera_connectors = microusb_3 + microusb_6
battery_usb_connectors = usb_3 + usb_6
battery_usbc_connectors = usbc_3 + usbc_6
battery_connectors = battery_usb_connectors + battery_usbc_connectors
hd_connectors = usbc_3 + usbc_6

Now that we've associated all of the concepts in our model, it's time to add some constraints! The below basically defines that every device (not every cable!) requires at least one cable. Notice that if we have a single lightning cable, that will satisfy both the iPhone and iPad constraints.


In [6]:
model_a += power_supply_connectors >= 1
model_a += ipad_connectors >= 1
model_a += iphone_connectors >= 1
model_a += android_connectors >= 1
model_a += camera_connectors >= 1
model_a += battery_connectors >= 1
model_a += hd_connectors >= 1

Lastly we solve the optimization problem.


In [7]:
model_a.solve()
p.LpStatus[model_a.status]


Out[7]:
'Optimal'

In [8]:
variables = [
    lightning_1,
    lightning_3,
    lightning_6,
    microusb_1,
    microusb_3,
    microusb_6,
    usb_1,
    usb_3,
    usb_6,
    usbc_1,
    usbc_3,
    usbc_6
]

for variable in variables:
    if variable.varValue > 0:
        print("{0} = {1}".format(variable.getName(), variable.varValue))


lightning_1 = 1.0
microusb_3 = 1.0
usbc_6 = 1.0

And finally we can print out the cost of the solution that was found.


In [9]:
print(p.value(model_a.objective))


45.0

So for $45 we can connect all of our devices to the laptop!

More Complex Model


In [33]:
model_b = p.LpProblem("Albon Shopping Problem (Use all USB-C ports)", p.LpMinimize)

In [34]:
lightning_1 = p.LpVariable('lightning_1', lowBound=0, cat='Integer')
lightning_3 = p.LpVariable('lightning_3', lowBound=0, cat='Integer')
lightning_6 = p.LpVariable('lightning_6', lowBound=0, cat='Integer')

microusb_1 = p.LpVariable('microusb_1', lowBound=0, cat='Integer')
microusb_3 = p.LpVariable('microusb_3', lowBound=0, cat='Integer')
microusb_6 = p.LpVariable('microusb_6', lowBound=0, cat='Integer')

usb_1 = p.LpVariable('usb_1', lowBound=0, cat='Integer')
usb_3 = p.LpVariable('usb_3', lowBound=0, cat='Integer')
usb_6 = p.LpVariable('usb_6', lowBound=0, cat='Integer')

usbc_1 = p.LpVariable('usbc_1', lowBound=0, cat='Integer')
usbc_3 = p.LpVariable('usbc_3', lowBound=0, cat='Integer')
usbc_6 = p.LpVariable('usbc_6', lowBound=0, cat='Integer')

In [35]:
model_b +=   10 * (lightning_1 + microusb_1 + usb_1 + usbc_1) \
         + 15 * (lightning_3 + microusb_3 + usb_3 + usbc_3)   \
         + 20 * (lightning_6 + microusb_6 + usb_6 + usbc_6),  "Cost"

In [36]:
power_supply_connectors = usbc_6
ipad_connectors = lightning_1 + lightning_3 + lightning_6
iphone_connectors = ipad_connectors
android_connectors = microusb_1 + microusb_3 + microusb_6
camera_connectors = microusb_3 + microusb_6
battery_usb_connectors = usb_3 + usb_6
battery_usbc_connectors = usbc_3 + usbc_6
battery_connectors = battery_usb_connectors + battery_usbc_connectors
hd_connectors = usbc_3 + usbc_6

Then our constraints again. The "model_b +=" portions are just how we associate the constraint with the model we're building. Our main change here is that we have constrained the problem such that we need to be able to connect our power supply and hard drive at the same time (two separate ports). See Constraint set 2 below.

On top of that, we want to be able to use the other two ports on our laptop so we can maximize the four available ports (see Constraint set 3 below).


In [45]:
# Same constraints as before
model_b += power_supply_connectors >= 1
model_b += ipad_connectors >= 1
model_b += iphone_connectors >= 1
model_b += android_connectors >= 1
model_b += camera_connectors >= 1
model_b += battery_connectors >= 1
model_b += hd_connectors >= 1

# Constraint set 2
# Plus hard drive and power supply must be able to be plugged
# in simultaneously
# Since hard drive cables are a superset of the power supply
# cables we can formulate this constraint as 
# "We should have at least one hard drive cable over and above
# what we have for our power supply"
model_b += hd_connectors - power_supply_connectors >= 1

# Constraint set 3
# Plus must have four cables to plug in and fill all four ports
model_b +=  (lightning_1 + lightning_3 + lightning_6 \
           + microusb_1  + microusb_3 + microusb_6 \
           + usb_1  + usb_3 + usb_6 \
           + usbc_1  + usbc_3 + usbc_6) == 4

Solve the model...


In [46]:
model_b.solve()
p.LpStatus[model_b.status]


Out[46]:
'Optimal'

In [47]:
variables = [
    lightning_1,
    lightning_3,
    lightning_6,
    microusb_1,
    microusb_3,
    microusb_6,
    usb_1,
    usb_3,
    usb_6,
    usbc_1,
    usbc_3,
    usbc_6
]

for variable in variables:
    if variable.varValue > 0:
        print("{0} = {1}".format(variable.getName(), variable.varValue))


lightning_1 = 1.0
microusb_3 = 1.0
usbc_3 = 1.0
usbc_6 = 1.0

And then print out the cost!


In [44]:
print(p.value(model_b.objective))


60.0

Our new constraints required us to increase the cost by $15.


In [ ]: