Chicken Wing Problem.ipynb

Kernel: SageMath 8.3

The Chicken Wing Problem

Original Twitter Post

Business Insider Link

Problem: Determine the minimal cost for ordering $n$ wings using this restaurant's prices.

Below is a script for solving a generic integer programming problem.

from sage.numerical.backends.generic_backend import get_solver
import sage.numerical.backends.glpk_backend as backend
from tabulate import tabulate
import numpy as np
import pandas as pd

def lpInt(var, con, ob, M, inq, bnd, mx=True):
    # loads the solver
    q = get_solver(solver = 'GLPK')
    # sets solver to min, max otherwise
    if not mx:
        q.set_sense(-1)
    # adds all variables
    for v in var:
        q.add_variable(integer=True, name=v)
    # adds all constraints
    for i in range(len(M)):
        if inq[i] == 1:
            q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), None, bnd[i], con[i])
        elif inq[i] == -1:
            q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], None, con[i])
        else:
            q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], bnd[i], con[i])
    # sets objective
    q.set_objective(ob)    
    q.solver_parameter(backend.glp_simplex_then_intopt)
    # solves the problem
    q.solve()
    # The following lines all produce an output report
    if mx:
        st = ' (max) '
    else:
        st = ' (min) '
    sol = [q.get_variable_value(i) for i in range(q.ncols())]
    print 'Optimal'+st+'value: ', q.get_objective_value()
    print ''
    results = [[a,b] for a,b in zip(var,sol) if b]
    print tabulate(results, headers=['Order Size', 'Count'])

Importing the price data.

df = pd.read_csv('chickenWings.csv')

Function that computes a minimal solution (there could be many).

def wingOp(N):
    var = [str(count)+' wings' for count in df.Count]
    con = [str(count)+' wings cost' for count in df.Count] + ['Total wing count']
    ob = [cost for cost in df.Cost]
    M = [map(int,list(k)) for k in np.identity(df.shape[0])] + [[count for count in df.Count]]
    inq = [-1 for k in df.index] + [0]
    bnd = [0 for k in df.index] + [N]
    print("Total wing count: " + str(N))
    lpInt(var,con,ob,M,inq,bnd,mx=False)

An example.

wingOp(74)

Total wing count: 74
Optimal (min) value:  82.8

Order Size      Count
------------  -------
6 wings             4
50 wings            1

wingOp(75)

Total wing count: 75
Optimal (min) value:  83.4

Order Size      Count
------------  -------
25 wings            3