Facility Location Problem - Discrete Optimization Assignment

Discrete Optimization Assignment Facility Location 1 Problem Statement In this assignment you will design an algorithm to solve a problem faced by distribution companies The Facility Location Problem A distribution company uses bulk storage facilities to provide goods to many different customers The goal of this problem is to determine which facilities will be the most cost effective for serving the customers The complexity of the problem comes from the fact that each facility has different costs and storage capabilities1 2 Assignment Write an algorithm to solve the facility location problem The problem is mathematically formulated in the following way there are N0n1 facilities to choose from and Mnnm1 customers that need to be served Each facility f N has a setup cost sf and a capacity capf Each customer c M has a demand dc Both the facilities and customers are located in a Euclidian space xi yi i N M The cost to deliver goods to a particular customer c from a facility f is the Euclidean distance between two locations distf c2 Lastly all customers must be served by exactly 1 facility Let af be a set variable denoting the customers assigned to facility f Then the facility location problem is formalized as the following optimization problem minimize fN af 0sf caf distf c subject to caf dc capf f N fN c af 1 c M 1Hint The facility location problem is closely related to the warehouse location problem discussed in the lectures 2disti j xi xj2 yi yj2 3 Data Format Specification The input consists of N M 1 lines The first line contains two numbers N followed by M The first line is followed by N lines where each line encodes the facilitys setup cost sf capacity capf and the location xf yf The remaining M lines capture the customer information where each line encodes the customers demand dc and location xc yc Input Format N M s0 cap0 x0 y0 s1 cap1 x1 y1 sN1 capN1 xN1 yN1 dN xN yN dN1 xN1 yN1 dNM1 xNM1 yNM1 The output has two lines The first line contains two values obj and opt obj is the cost of the customer to facility assignment ie the objective value as a real number opt should be 1 if your algorithm proved optimality and 0 otherwise The next line is a list of M values in N this is the mapping of customers to facilities Output Format obj opt c0 c1 c2 cM1 2 Examples Input Example 3 4 100 100 10650 10650 100 100 10620 10620 100 500 00 00 50 13970 13970 50 13980 13980 75 13990 13990 75 5860 5860 Output Example 2550013 0 1 1 0 2 This output represents the assignment of customers to facilities a0 2 a1 0 1 a2 3 That is customers 0 and 1 are assigned to facility 1 customer 2 is assigned to facility 0 and customers 3 is assigned to facility 2 4 Instructions Edit solverpy and modify the solve itinput data function to solve the optimization problem described above The function argument input data contains the problem data in the format described above The return value of solve it is a solution to the problem in the output format described above Your solve it implementation can be tested with the command python solverpy datainputFileName You should limit the solve it method to terminate within 5 hours otherwise the submission will not be eligible for full credit You may choose to implement your solver directly in python or modify the solve it function to call an external application Resources You will find several facility location problem instances in the data directory provided with the handout Handin Run submitpy with the command python submitpy Follow the instructions to apply your solve it method on the various assignment parts You can submit multiple times and your grade will be the best of all submissions However it may take several minutes before your assignment is graded please be patient You can track the status of your submission on the feedback section of the assignment website Grading Infeasible solutions ie those that do not conform to the output format or violate problem constraints will receive 0 points Feasible solutions will receive at least 3 points Feasible solutions passing a low quality bar will receive at least 7 points and solutions meeting a high quality bar will receive all 10 points The grading feedback indicates how much your solution must improve to receive a higher grade 3 Collaboration Rules In all assignments we encourage collaboration and the exchange of ideas on the discussion forums However please refrain from the following 1 Posting code or pseudocode related to the assignments 2 Using code which is not your own 3 Posting or sharing problem solutions Discussion of solution quality ie objective value and algorithm performance ie run time is allowed and the assignment leader board is designed to encourage such discussions Warnings 1 It is recommended you do not modify the data directory Modifying the files in the data directory risks making your assignment submissions incorrect 2 You cannot rename the solverpy file or the solve it method 3 Be careful when using global variables in your implementation The solve it method will be run repeatedly and it is your job to clear the global data between runs 4 solverpy must remain in the same directory as submitpy 5 Technical Requirements You will need to have python 279 or 35 at least installed on your system installation instruc tions httpwwwpythonorgdownloads 4