Python: 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).

randomLap.py

import sys from random import random

# default parameter values in case they aren't specified # on the command line fname = 'r.csv' num = 25 min_val = 100 max_val = 500 # command line parameters if len(sys.argv) > 1: # asking for help? if sys.argv[1] == '--help': print 'Syntax: randomLAP [fname] [num min_val max_val]' exit() fname = sys.argv[1] if len(sys.argv) == 5 : try: num = int(sys.argv[2]) min_val = float(sys.argv[3]) max_val = float(sys.argv[4]) except: print 'Invalid parameters. Syntax: randomLP.py fname num min_val max_val' exit() val_range = max_val - min_val matrix = [] # generate the random values - use U(min_val, max_val) for k in range(num): matrix.append([]) for j in range(num): matrix[k].append(min_val + (random() * val_range)) # write the file with open(fname, 'w') as outfile: for k in range(num): row = ['{:.2f}'.format(x) for x in matrix[k]] outfile.write('{} '.format(', '.join(row))) # print information print ' Created a {}x{} cost matrix with values in the range {} - {}. File: {} '.format( num, num, min_val, max_val, fname )

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_02.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_03.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_04.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