Question

assignment2 June 14, 2024 1 Assignment 2 - Facility-Location Set-Covering Problem 1.1 Objective Want to learn how to locate as fewer fire stations as possible but provide sufficient coverages for the possible emergency responses within 15 minutes to six neighborhood cities? In this assignment, you'll learn how to solve this set-covering problem. We'll construct a mixed-integer programming (MIP) model of the problem, implement this model in the Gurobi Python API, and find an optimal solution using the Gurobi Optimizer. 1.2 Problem Description There are six cities (cities 1–6) in a County. The county must determine where to build fire stations. The county wants to build the minimum number of fire stations needed to ensure that at least one fire station is within 15 minutes (driving time) of each city. The times (in minutes) required to drive between the cities in a County are shown in below Table. We will formulate an IP that will tell the County how many fire stations should be built and where they should be located. This problem considers a 6 cities for potential fire stations. The following table illustrates the travel times (assuming the travel times are symmetric) among these 6 cities in the County. City 0 City 1 City 2 City 3 City 4 City 5 City 0 0 10 City 1 10 0 City 2 20 25 City 3 30 35 City 4 30 20 City 5 20 10 2012 20 25 15 30 20 30 BROFE 30 35 15 15 22212 30 20 20 10 30 20 15 30 25 25 0 1.3 Solution Approach Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex decision problem. A mathematical optimization model has 4 components, namely: Data (Sets and indices, Param- eters) Decision variables. - Objective function(s). - Constraints. - 1 1.4 Math model Minimize: $ z = x_1 + x_2 + x_3 + x_4 + x_5 + x_6 $ Subject to: $\begin{aligned} &x_1 + x_2 & & & & & & & & & & & 1 \ &x_1 + x_2 & & & & & & & & & & &+x_6 & 1 \ & & & &x_3 & & + x_4 & & & & & & & 1 \ & & & &x_3 & & + x_4 & & + x_5 & & & & 1 \ & & & & & &x_4 & & + x_5 & & & + x_6 & 1 \ & &x_2 & & & & & & + x_5 & & + x_6 & 1 \ \end{aligned} $ $ x_i {0, 1} for i = 1, 2, 3, 4, 5, 6 $ [3] %pip install -qq gurobipy import gurobipy as gp from gurobipy import GRB 34.9 MB/s eta 0:00:00 13.4/13.4 MB [15] # Parameters : city, coverage }) = 0: [{0, 1}], gp.multidict({ 1: [{0, 1, 5}], 2: [{2, 3}], 3: [{2, 3, 4}], 4: [{3, 4, 5}], 5: [{1, 4, 5}] [5]: model = gp. Model("set-covering-problem") Restricted license for non-production use only - expires 2025-11-24 [] # decision variables build = ### WRITE SOLUTION HERE ### [ ] # constraints ### WRITE SOLUTION HERE ### [] # objective function : ### WRITE SOLUTION HERE ### [ ] model.optimize() : [9] print (f "Number of fire stations built: {model.obj Val}") Number of fire stations built: 2.0 2 [10] for city in build.keys(): : if build[city].x == 1: print (f "Build a fire station in city {city}") Build a fire station in city 1 Build a fire station in city 3 3

Get Instant Homework HelpOn Your Mobile

Get Instant Homework HelpOn Your Mobile

Get Instant Homework HelpOn Your Mobile