DNSC6308: Assignment 1 Spring 2022
Submission: Please upload your solution in Word or PDF file via Blackboard. Screenshots of Python code and outputs should also be attached with the computational results.
1. (4 points) Let x1,x2,…,xn be n binary variables and let z be some other binary variable. Formulate the logical operator by using integer linear programming, i.e., write linear constraints so that
(a) z takes the value of 1 if at least one of the xi¡¯s takes the value of 1. (b) If all the xi¡¯s take the value of zero, then z takes a value of 0.
Copyright By PowCoder代写 加微信 powcoder
(c) z takes the value of 1 if all the xi¡¯s take the value of 1. (d) If any xi takes the value of zero, then z takes a value of 0.
2. (4 points) Suppose we want to send Q items from the warehouse to a retail store. The items can be delivered by trucks of capacity q. The logistics provider provides a full-truckload (FTL) option and a less-than-truckload (LTL) option. In FTL, we have to rent the entire container of a truck, and need to pay a fixed cost per truck K and a moving cost per item c0. In LTL, we are not required to use the entire container, and we simply pay a moving cost per item c1 > c0. Formulate a mixed-integer program that determines the optimal shipping plan and the minimum shipping cost.
3. (6 points.) Solve the project selection problem discussed in class using Gurobi.
(a) Solve the project selection problem that maximizes the total return given in the file Project.csv. Report the optimal objective.
(b) Solve the ¡°relaxed¡± problem. That is, replace the binary constraint xj ¡Ê {0, 1} with xj ¡Ý0andxj ¡Ü1,
for j = 1, . . . , 100, and then solving the problem as a linear programming problem. Report the objective value of the LP relaxation. Compare the objective with the optimal one from part (a).
(c) Clearly the relaxed solution can contain fractional values, which is meaningless in the context of project selection. Round down the fractional values and obtain the total return given by the rounded down solution. (Can we round up?). Compare the objective with the optimal one from part (a).
4. (8 points) During the war with Iraq in 1991, the Terraco Motor Company produced a lightweight, all terrain vehicle code-named ¡°J99 Terra¡± for the military. The company is now planning to sell the Tera to the public.
It has five plants that manufacture the vehicle and four regional distributional centers. The company is unsure of public demand for the Terra, so it is considering reducing its fixed operating costs by closing one or more plants, even though it would incur an increase in transportation costs. The relevant costs for the problem are provided in Figure 1. For example, the cost of shipping 1,000 vehicles from plant 1 to warehouse C is $32,000.
Figure 1: Data for Question 3
Formulate an integer programming model for this problem that will assist the company in determining which plants should remain open and which plants should be closed and the number of vehicles that should be shipped from each plant to each warehouse to minimize the cost. Solve the model in Gurobi. Report the optimal objective value and the optimal solution.
5. (8 points) CVS and UPS are collaborating to allow customers to pick up and drop off UPS packages at many CVS stores. Suppose a UPS courier is responsible to collect outgoing packages from the 7 CVS stores shown in the map below:
Figure 2: CVS Stores near GW (www.cvs.com/store-locator/)
To support UPS¡¯s sustainability initiative, the courier is equipped with a bike for urban pickup and delivery. Based on Google map, we find the pairwise cycling time (in minute) between CVS stores in Table 1. Suppose now the courier is already at Store 1 to pick up the packages. The courier needs to visit all other stores and then return back to Store 1 to sort the collected packages before returning to UPS¡¯s depot. Please plan routes for the courier by solving TSP in Gurobi.
Table 1: Pairwise Cycling Time between Stores StoreNo. 1 2 3 4 5 6 7
(a) What is the minimum cycling time and route to visit all CVS stores (only once) and returning to Store 1? (the route may not be unique)
(b) The UPS courier can also help delivery CVS¡¯s internal packages between stores. Currently, there are internal packages sending from Store 4 to Store 2 and Store 3, respectively. Thus, the courier needs to visit Store 4 to collect the internal packages before visting Stores 2 & 3. In this case, what is the minimum cycling time and route?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com