SYS6001 Case 33 Bridge Knapsack Solver

README.md

Knapsack Solver Script for SYS6001 Case 33 Bridge Data

Create virtual environment with dependencies

Works on linux, macOS, and possibly windows if you have Python set up "right". (INSTALL GUIDE) Open up Terminal if you have linux/MacOS, or CMD if you have Windows.

python3 -m venv bridges
source bridges/bin/activate
pip install pandas ortools openpyxl xlrd

Run script

At this point it is assumed you have run the commands from the previous step. Navigate (cd) to the directory which contains bridges.py and run the following command:

python -m bridges

Leaving the venv

deactivate

or

source deactivate

bridges.py

# Import dependencies
import pandas as pd # https://pandas.pydata.org/docs/user_guide/index.html#user-guide
from ortools.algorithms.python import knapsack_solver # https://developers.google.com/optimization/pack/knapsack

# Load data into a pandas dataframe
# You will likely need to change your file path to point to the excel file.
# On Windows it will look something like this: 
#   r"C:\Users\<USERNAME>\Documents\...\SYS6001_33_NBIva_data.xls" 
#   (the r-prefix on the string is required for unescaped backslashes `\` )
df = pd.read_excel(r'~/Documents/SYS6001_33_NBIva_data.xls')

# create some new columns on the data to be used for filtering the dataset
df['INCLUDE_BRIDGE_OWNER'] = (df['ITEM22'] != 26) & (df['ITEM22'] <= 32) # state-managed bridges
df['INCLUDE_BRIDGE_PCT'] = df['ITEM98B'] <= 50 # bridges majority-owned by virginia
df['INCLUDE_BRIDGE_COST'] = df['ITEM94'] > 0 # bridges for which costs are known

# define the value and cost 
# (this is unnecessary to define new columns for, really just for consistency and clarity)
df['VALUE'] = df['ADT']
df['WEIGHTS'] = df['ITEM94'] * 0.1

# filter the dataframe rows: all three conditions described above must be true
inscope = df[df['INCLUDE_BRIDGE_OWNER'] & df['INCLUDE_BRIDGE_PCT'] & df['INCLUDE_BRIDGE_COST']]

# create a knapsack solver from google's ortools libray
# https://developers.google.com/optimization/pack/knapsack
solver = knapsack_solver.KnapsackSolver(
    knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "KnapsackExample",
)

# define the problem
# 	values must be a list of integers
values = inscope['VALUE'].astype(int).tolist()
#	weights must be a list of lists of integers (can be a list of a single list of integers)
weights = [
    inscope['WEIGHTS'].astype(int).tolist(), # actual weights
    [1 for _ in inscope['WEIGHTS']], # creates a list of 1 for each bridge (to constrain the total bridges to 30 below)
]

# one constraint value per list of weights above
constraints = [
	100, # weights constraint (thousands of dollars or whatever)
	30, # total count constraint
]

# actually solve the problem
solver.init(values, weights, constraints)
computed_value = solver.solve()

# describe the solution
# the solution comes out as a list of integers, representing the indices of the bridges selected for the knapsack
packed_items = []
packed_weights = []
total_weight = 0

for i in range(len(values)):
    if solver.best_solution_contains(i):
        packed_items.append(i)
        packed_weights.append(weights[0][i])
        total_weight += weights[0][i]

print("Total value =", computed_value)
print("Total weight:", total_weight)
print("Packed items:", packed_items)
print("Packed_weights:", packed_weights)

# now show the solution in terms of the bridges
print(inscope.iloc[packed_items]['ITEM6A'])