Python 2.7: Using randomLAP.py, generate five problem instances (cost matrices) with dimension 200 and values in the range 100 to 500. Store the problem instances in files named r1.csv r5.csv. Run each of the four heuristics and the optimal provided on Canvas (lap_h1.py, lap_h2.py, lap_h3.py, lap_h4.py, and lap_optimal) with each of the five problem instances. This will result in 25 different results. Display your results in a table on your Word document similar to the one below. (You can choose any sufficiently large number for maxreps in lap_h4 and nreps in lap_h3.py. Suggested value for maxreps and nreps: 10000).

*Lap.py

import sys import copy # need to update this to point to the location of parseCSV.py # sys.path.append('c:\\svns\\code\\python') from parseCSV import parseCSV

# # initialize the problem - fname is the csv file with the cost matrix # def initialize(fname, show): # read the costs matrix from the csv file costs = parseCSV(fname) # people[i] is the index of the task assigned to person i # or -1 if the person does not have an assigned task people = [] # tasks[j] is the index of the person assigned to task j # or -1 if the task is unassigned tasks = [] # create the people and tasks lists for k in range(len(costs)): people.append(-1) tasks.append(-1) if show: print '{} people, {} tasks, {}x{} costs, lb = {:.2f}'.format( len(people), len(tasks), len(costs), len(costs), simple_lb(costs)) return costs, people, tasks # # show_solution - displays the current solution # def show_solution(costs, people, tasks): for k in range(len(people)): if people[k] > -1: task = 'T{}'.format(people[k]) cost = costs[k][people[k]] else: task = 'n/a' cost = 0.0 print '\tP{}, {}, {:.2f} '.format(k, task, cost) print ' Total cost: {:.2f} (lower bound: {:.2f})'.format( calc_cost(costs, people)[0], simple_lb(costs) )

# # calc_cost - calculates the current solution cost # def calc_cost(costs, people): total_cost = 0 num_assigned = 0 # for each person for k in range(len(people)): # make sure the person has an assigned task if people[k] != -1: total_cost += costs[k][people[k]] num_assigned += 1 return total_cost, num_assigned

# # low_cost_task - finds the lowest cost available task for the # specified person # def low_cost_task(costs, person, tasks): # initialize with the biggest possible number min_cost = 1e308 # index of the low-cost task min_idx = -1 # loop through all tasks for k in range(len(tasks)): # if the task is currently unassigned if tasks[k] == -1: # is the task lower cost than the current minimum? if costs[person][k]

# # simple_lb - calculates a simple lower bound based on low-cost assignment # def simple_lb(costs): # min cost task for each person total_cost1 = 0; for k in range(len(costs)) : total_cost1 += min(costs[k]) # min cost person for each task total_cost2 = 0; for k in range(len(costs)): total_cost2 += min([c[k] for c in costs]) # return the better of the two bounds return max(total_cost1, total_cost2)

# # clear_solution - clears the incumbent solution # def clear_solution(people, tasks): for k in range(len(people)): people[k] = -1 for k in range(len(tasks)): tasks[k] = -1

# # store_solution # def store_solution(people, tasks, cost, seq): # create the dictonary solution = {} # need to use copy since the lists are mutable solution['people'] = copy.copy(people) solution['tasks'] = copy.copy(tasks) solution['obj_val'] = cost solution['seq'] = copy.copy(seq) return solution

# # main # def main(): # default values fname = 'r.csv' # argv[0] - file name if len(sys.argv) > 1: fname = sys.argv[1] # initialize costs, people, tasks = initialize(fname, 1) # Simple assignment - person k gets task k for all k for k in range(len(people)): people[k] = k; tasks[k] = k; print ' Solution:' show_solution(costs, people, tasks)

# if cmd line, execute main if __name__ == '__main__' : main()

*lap._h0.py

import sys

# # read_csv_matrix(fname) - parameter is the file name. Assumes # that the values are floats and that the matrix is square. # # error codes: 0 - success # 1 - file open error # 2 - matrix size error def read_csv_matrix(fname = 'r.csv'): # init the cost matrix, people and tasks lists and error code matrix = [] people = [] tasks = [] err_code = 0 # try to open the file try: f = open(fname, 'r') except Exception, e: err_code = 1 else: # read and process one line at a time line = f.readline() while line : # split and float the values if line.rstrip(): vals = line.rstrip().split(',') # append the row to the matrix matrix.append([float(num) for num in vals]) line = f.readline() msize = len(matrix) # Add the people and task elements and # verify that the matrix is square for row in matrix: # initialize the assignment to -1 (none) people.append(-1) tasks.append(-1) if len(row) != msize: err_code = 2 return matrix, people, tasks, err_code

# # show_solution(costs, people, tasks) # def show_solution(costs, people, tasks, show_costs = 0): if show_costs: print "Costs :", costs print "People :", people print "Tasks :", tasks # compute the total assignment cost and number assigned. total_cost, num_assigned = calc_cost(costs, people) print "Cost :", total_cost print "Num Assigned :", num_assigned

# # calc_cost() # def calc_cost(costs, people): total_cost = 0 num_assigned = 0 # for each person for k in range(len(people)): # make sure the person has an assigned task if people[k] != -1: total_cost = total_cost + costs[k][people[k]] num_assigned = num_assigned + 1 return total_cost, num_assigned

# # main() # def main(): # Set the default filename fname = 'r.csv' # check to see if the user included a filename if len(sys.argv) > 1: fname = sys.argv[1] # read cost matrix from file. Exit on error costs, people, tasks, err_code = read_csv_matrix(fname) if err_code: print "Error {}".format(err_code) exit() else: print " Initial solution:" show_solution(costs, people, tasks, 1) # Make a simple assignment for i in range(len(costs)): people[i] = i tasks[i] = i print " Final solution:" show_solution(costs, people, tasks)

# This line causes main() to be executed if this module # is executed without an import (i.e., from the command line). # If the module is imported, the condition will fail. if __name__ == "__main__": main()

*lap_h1.py

import sys import lap

# initialize parameters then check for command line changes show_intermediate = 1 fname = 'r.csv' if len(sys.argv) > 1: fname = sys.argv[1] if len(sys.argv) > 2: show_intermediate = int(sys.argv[2]) # initialize the data structures using the cost matrix file costs, people, tasks = lap.initialize(fname, 1) # for each person, assign their low-cost task for k in range(len(people)): # find the low cost task for this person task, min_cost = lap.low_cost_task(costs, k, tasks) # assign task to person and person to task people[k] = task tasks[task] = k # show current assignment if show_intermediate: if people[k] != -1: print 'Assigned P{} task T{} at cost {:.2f}'.format( k, people[k], min_cost ) # show solution print ' Final solution:' lap.show_solution(costs, people, tasks)

*lap_h2.py

import sys from random import sample import lap

# # solve - solves the problem for a given assignment sequence # def solve(costs, people, tasks, seq): total_cost = 0 for k in seq: # find the low cost task for this person task, min_cost = lap.low_cost_task(costs, k, tasks) # assign task to person and person to task people[k] = task tasks[task] = k total_cost += min_cost return total_cost

# # main # def main(): # default values nreps = 100 fname = 'r.csv' # argv[0] - file name # argv[1] - number of replications if len(sys.argv) > 1: fname = sys.argv[1] if len(sys.argv) > 2: try: nreps = int(sys.argv[2]) except: print 'Invalid parameters. Syntax: lab_h2.py fname nreps' exit() # initialize costs, people, tasks = lap.initialize(fname, 1) # initial solution with the "natural" sequence cost = solve(costs, people, tasks, range(len(people))) # store the solution -- need to use deepcopy so the best # incumbent solution is not overwritten solution = lap.store_solution(people, tasks, cost, range(len(people))) print 'Iteration {:3d} Cost: {:.2f}'.format(-1, solution['obj_val']) # iterate for k in range(nreps): # clear the current assignments lap.clear_solution(people, tasks) # sample a random sequence seq = sample(range(len(people)), len(people)) # solve with the random sequence cost = solve(costs, people, tasks, seq) print 'Iteration {:3d} Cost: {:.2f}'.format(k, cost) # if this solution is better than the best incumbent, # make it the best incumbent. if cost

# if cmd line, execute main if __name__ == '__main__' : main()

*lap_h3.py

import sys import random import lap

def swap(people, tasks, i, j): tmp = people[i] people[i] = people[j] people[j] = tmp tasks[people[i]] = i tasks[people[j]] = j

def swap_adjust(costs, people, i, j): # remove the previous costs adjust = -costs[i][people[i]] - costs[j][people[j]] # add the new costs adjust = adjust + costs[i][people[j]] + costs[j][people[i]] return adjust

# # main # def main(): # initialize parameters then check for command line changes show_intermediate = 1 nreps = 100000 fname = 'r.csv' if len(sys.argv) > 1: fname = sys.argv[1] if len(sys.argv) > 2: show_intermediate = int(sys.argv[2]) # initialize the data structures using the cost matrix file costs, people, tasks = lap.initialize(fname, 1) # for each person, assign their low-cost task if show_intermediate: print 'Intial assignment:' for k in range(len(people)): # find the low cost task for this person task, min_cost = lap.low_cost_task(costs, k, tasks) # assign task to person and person to task people[k] = task tasks[task] = k # show current assignment if show_intermediate: if people[k] != -1: print '\tAssigned P{} task T{} at cost {:.2f}'.format( k, people[k], min_cost ) # show solution if show_intermediate: print 'Random swaps (checking {} random pairs)'.format(nreps) for j in range(nreps): tasks_to_swap = random.sample(range(len(people)), 2) adjust = swap_adjust(costs, people, tasks_to_swap[0], tasks_to_swap[1]) if adjust

# if cmd line, execute main if __name__ == '__main__' : main()

lap_h4.py

import sys import random import lap

def swap(people, tasks, i, j): tmp = people[i] people[i] = people[j] people[j] = tmp tasks[people[i]] = i tasks[people[j]] = j

def swap_adjust(costs, people, i, j): # remove the previous costs adjust = -costs[i][people[i]] - costs[j][people[j]] # add the new costs adjust = adjust + costs[i][people[j]] + costs[j][people[i]] return adjust

# # main # def main(): # initialize parameters then check for command line changes show_intermediate = 1 maxreps = 10000 fname = 'r.csv' if len(sys.argv) > 1: fname = sys.argv[1] if len(sys.argv) > 2: show_intermediate = int(sys.argv[2]) # initialize the data structures using the cost matrix file costs, people, tasks = lap.initialize(fname, 1) # for each person, assign their low-cost task if show_intermediate: print 'Intial assignment:' for k in range(len(people)): # find the low cost task for this person task, min_cost = lap.low_cost_task(costs, k, tasks) # assign task to person and person to task people[k] = task tasks[task] = k # show current assignment if show_intermediate: if people[k] != -1: print '\tAssigned P{} task T{} at cost {:.2f}'.format( k, people[k], min_cost ) # show solution if show_intermediate: print 'Steepest descent (max of {} swaps)'.format(maxreps) nreps = 0 while nreps

# if cmd line, execute main if __name__ == '__main__' : main()

lap.optimal.py

import sys import lap from gurobipy import *

# # main # def main(): show_intermediate = 0 fname = 'r.csv' if len(sys.argv) > 1: if sys.argv[1] == '--help': print 'Syntax: lap_optimal [fname] [0/1 - show gurobi details]' exit() fname = sys.argv[1] if len(sys.argv) > 2: show_intermediate = int(sys.argv[2]) # initialize costs, people, tasks = lap.initialize(fname,1)

# Define the model m = Model('LAP') # turn off intermediate output if show_intermediate == 0: m.setParam('OutputFlag',False) # Limit to 5 minutes m.setParam('TimeLimit', 360) num_people = len(people) num_tasks = len(tasks) # decvarx - x[i][j] = 1 if person i is assigned task j decvarx = [] for i in range(num_people): decvarx.append([]) for j in range(num_tasks): # Assign decvarx[i][j] to a Gruobi Variable Object decvarx[i].append(m.addVar(obj=costs[i][j],vtype=GRB.BINARY))

# The objective is to minimize the total cost. m.modelSense = GRB.MINIMIZE # Update model to integrate new variables m.update() # Each person is assigned exactly 1 task for i in range(num_people): # quicksum is a Gurobi method (faster than sum for these models) m.addConstr(quicksum(decvarx[i][j] for j in range(num_tasks)) == 1) # Each task is assigned to exactly 1 person for j in range(num_tasks): m.addConstr(quicksum(decvarx[i][j] for i in range(num_people)) == 1) m.optimize() if m.Status == GRB.OPTIMAL: print ' Gurobi reports the solution is optimal' else: print ' Solution might not be optimal (Gurobi optimal flag not set)' print ' Solution:' for i in range(num_people): for j in range(num_tasks): if decvarx[i][j].x == 1: print '\tP{}, T{}, {}'.format(i, j, costs[i][j]) print ' Total Cost: {:.2f}'.format(m.objVal)

# if cmd line, execute main if __name__ == '__main__' : main()

Problem Instances H1 H2 H3 H4 Optimal 3 4 5 Problem Instances H1 H2 H3 H4 Optimal 3 4 5