Optimization Example




Pay Notebook Creator: Roy Hyunjin Han0
Set Container: Numerical CPU with TINY Memory for 10 Minutes 0
Total0
In [8]:
url = 'https://data.cityofnewyork.us/api/views/sv6e-j8t9/rows.csv?accessType=DOWNLOAD'
In [9]:
import pandas
t = pandas.read_csv(url)
In [10]:
t[:10]
Out[10]:
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; } .dataframe tbody tr th { vertical-align: top; } .dataframe thead th { text-align: right; } </style>
TIMES SQUARE Dimensions Sq Ft DEC Impressions Pricing Model Unit (All One Month) Total Minutes Rate Full Motion Video Onsite Audio Advance Interactive CPM Cost Per Minute Cost Per SF
0 American Eagle NaN 15000.0 1500000 NaN Duration 1 month 2 minutes/hour (19 hrs/day) 1140.0 69600.0 yes no NaN 1.546667 61.05 4.63
1 NaN NaN NaN NaN NaN NaN 4 minutes/hour (19 hrs/day) 2280.0 129600.0 yes no NaN 2.880000 56.84 8.64
2 NaN NaN NaN NaN NaN NaN 6 minutes/hour (19 hrs/day) 3420.0 180000.0 yes no NaN 4.000000 52.63 12.00
3 Sony/Fox Screen (Times Square 1) 35 x 40 1400.0 1600000 NaN Duration 1 month 2 minutes/hour (18 hrs/day) 1080.0 22500.0 yes no no 0.468750 20.83 16.07
4 ABC Supersign NaN 4630.0 1600000 NaN Duration 1 month 2 minutes/hour (15 hrs/day) 900.0 53000.0 yes no no 1.104167 58.88 11.44
5 Times Square 2 NaN 17754.0 1600000 NaN Duration 1 month 3 min/hour (19 hrs/day) plus blackout below 1710.0 103250.0 yes no NaN 2.151042 60.38 5.81
6 Nasdaq 120 x 84 10080.0 NaN NaN NaN Blackout periods 9-10am and 3:30 - 4:30 pm plu... NaN NaN NaN NaN NaN NaN NaN NaN
7 Reuters 7 boards various sizes 7674.0 NaN NaN NaN 3 min/hour (19 hrs/day) NaN NaN NaN NaN NaN NaN NaN NaN
8 W Hotel (Broadway and 47th Street) 30 x 40 1200.0 1600000 NaN Duration 1 month 4 min/hour x 19 Hours/day 2280.0 70000.0 yes no NaN 1.458333 30.70 58.33
9 NaN NaN NaN NaN NaN NaN 8 min/hour x 19 Hours/day 4560.0 125000.0 yes NaN NaN 2.604167 27.41 104.16
In [11]:
t[['Total Minutes', 'Rate']]
Out[11]:
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; } .dataframe tbody tr th { vertical-align: top; } .dataframe thead th { text-align: right; } </style>
Total Minutes Rate
0 1140.0 69600.0
1 2280.0 129600.0
2 3420.0 180000.0
3 1080.0 22500.0
4 900.0 53000.0
5 1710.0 103250.0
6 NaN NaN
7 NaN NaN
8 2280.0 70000.0
9 4560.0 125000.0
10 NaN NaN
11 NaN NaN
In [12]:
t[['Total Minutes', 'Rate']].dropna()
Out[12]:
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; } .dataframe tbody tr th { vertical-align: top; } .dataframe thead th { text-align: right; } </style>
Total Minutes Rate
0 1140.0 69600.0
1 2280.0 129600.0
2 3420.0 180000.0
3 1080.0 22500.0
4 900.0 53000.0
5 1710.0 103250.0
8 2280.0 70000.0
9 4560.0 125000.0
In [13]:
filtered_t = t[['Total Minutes', 'Rate']].dropna()
filtered_t
Out[13]:
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; } .dataframe tbody tr th { vertical-align: top; } .dataframe thead th { text-align: right; } </style>
Total Minutes Rate
0 1140.0 69600.0
1 2280.0 129600.0
2 3420.0 180000.0
3 1080.0 22500.0
4 900.0 53000.0
5 1710.0 103250.0
8 2280.0 70000.0
9 4560.0 125000.0
In [14]:
values = []
weights = []
for index, row in filtered_t.iterrows():
    values.append(int(row['Total Minutes']))
    weights.append(int(row['Rate']))
weights = [weights]
In [15]:
values
Out[15]:
[1140, 2280, 3420, 1080, 900, 1710, 2280, 4560]
In [16]:
weights
Out[16]:
[[69600, 129600, 180000, 22500, 53000, 103250, 70000, 125000]]
In [17]:
budget = 250000
In [18]:
import subprocess
subprocess.call('pip install ortools'.split())
Out[18]:
0
In [19]:
from ortools.algorithms import pywrapknapsack_solver

solver = pywrapknapsack_solver.KnapsackSolver(
    pywrapknapsack_solver.KnapsackSolver.
    KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    'KnapsackExample')
In [20]:
'''
values = [
    360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
    78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
    87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
    312]
weights = [[
    7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
    42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
    3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13]]
capacities = [850]
'''
capacities = [budget]
In [21]:
capacities
Out[21]:
[250000]
In [22]:
solver.Init(values, weights, capacities)
computed_value = solver.Solve()
In [23]:
packed_items = []
packed_weights = []
total_weight = 0
print('Total value =', computed_value)
for i in range(len(values)):
    if solver.BestSolutionContains(i):
        packed_items.append(i)
        packed_weights.append(weights[0][i])
        total_weight += weights[0][i]
print('Total weight:', total_weight)
print('Packed items:', packed_items)
print('Packed_weights:', packed_weights)

Total value = 7920
Total weight: 217500
Packed items: [3, 6, 7]
Packed_weights: [22500, 70000, 125000]
In [24]:
t.dropna(subset=['Total Minutes', 'Rate']).iloc[packed_items]
Out[24]:
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; } .dataframe tbody tr th { vertical-align: top; } .dataframe thead th { text-align: right; } </style>
TIMES SQUARE Dimensions Sq Ft DEC Impressions Pricing Model Unit (All One Month) Total Minutes Rate Full Motion Video Onsite Audio Advance Interactive CPM Cost Per Minute Cost Per SF
3 Sony/Fox Screen (Times Square 1) 35 x 40 1400.0 1600000 NaN Duration 1 month 2 minutes/hour (18 hrs/day) 1080.0 22500.0 yes no no 0.468750 20.83 16.07
8 W Hotel (Broadway and 47th Street) 30 x 40 1200.0 1600000 NaN Duration 1 month 4 min/hour x 19 Hours/day 2280.0 70000.0 yes no NaN 1.458333 30.70 58.33
9 NaN NaN NaN NaN NaN NaN 8 min/hour x 19 Hours/day 4560.0 125000.0 yes NaN NaN 2.604167 27.41 104.16
Notebook Creator Notebook Created Notebook Modified Notebook Contents Recent Tools