homework6 spring 2020 PDF

Preview

Summary

hw6...

Description

Spring 2020

Optimization II (ORIE 3310/5310)

Homework 6: Integer Linear Programming Due: Tuesday, March 17th at 4pm on Canvas. 1. (15 points) Solve the following ILP using Branch & Bound. maximize

9x1 + x2

subject to

2x1 + 2x2 ≤ 15 2x1 − 2x2 ≤ 5 x1 , x2 ≥ 0 integer.

You can solve the LP-relaxation of the subproblems using AMPL/Gurobi, or by using the graphical method. Clearly draw your B&B tree with, for each node, the objective value of the LP-relaxation of the subproblem, an optimal solution of the LP-relaxation of the subproblem (6 points for this). Also clearly mark in which order you considered the subproblems (4 points), and what you concluded at each subproblem (4 points). What is an optimal solution of the ILP above? (1 point) 2. (12 points) In the following problem, you are trying to solve an integer program via branch-andbound. You know that each coefficient of the objective function is an integer, and you know that there is an integer solution of value 24. All variables in the integer program must be integer in any feasible solution. Below is information about various nodes that you encounter during the course of your branchand-bound algorithm. You should assume that the nodes are encountered in the order given. Further assume that Node A given below is the root node of the branch-and-bound tree. • Node A. Objective function value: 19.43 • Node B. Objective function value: 20.35 • Node C. Objective function value: 24. Variables x3 and x5 are fractional. • Node D. Objective function value: 26. All variables are integer. • Node E. Objective function value: 23.5. (a) (2 points) Is the integer program being solved a maximization or a minimization problem? Why? (b) (10 points, 2 per node) For each of nodes A-E, state whether given the information, one should branch on the node (that is, choose a fractional variable and create new subproblems), the node has been fathomed (that is, given the information encountered so far, any integer solution to this problem would not have objective function value better than what we have so far encountered), or the node gives the current best integer solution (incumbent). For each node, also give a sentence or two of explanation. 3. (20 points) There are 5 warehouses, denoted W1 , W2 , W3 , W4 , W5 , and 10 customers, denoted C1 , . . . , C10 . For each warehouse Wi , there is a supply of si units of a commodity, and for each customer Cj , there is a demand of dj units of the commodity. 1

Spring 2020

Optimization II (ORIE 3310/5310)

The cost for sending one unit of commodity from warehouse Wi to customer Cj is cij . In addition, there is a fixed setup cost (for instance, the cost of having to send a truck to that warehouse) of fi if there is any nonzero quantity of the commodity being sent from warehouse Wi . We would like to satisfy all demand with minimum cost. (a) (10 points) Formulate an integer program to find out which warehouses should be used to satisfy demand, and the number of units to be sent from each warehouse to each customer. (b) (10 points) Suppose that we have the following values for si , dj , cij , fi . Warehouse Wi Supply si Fixed setup cost fi W1 120 100 W2 80 200 W3 75 50 W4 150 200 W5 75 100 Customer Cj Demand dj C1 20 C2 10 C3 30 C4 10 C5 5 C6 15 C7 20 C8 30 C9 40 C10 20

W1 W2 W3 W4 W5

Cost cij C1 C2 10 5 1 6 6 4 7 1 5 6

from warehouse Wi to customer Cj C3 C4 C5 C6 C7 C8 C9 C10 3 7 8 6 7 4 2 5 7 9 4 6 8 5 3 6 3 2 3 2 6 4 2 4 2 5 5 7 4 3 3 6 1 1 7 9 8 2 2 8

Based on your integer programming formulation in part (a), solve this problem using AMPL/Gurobi. (Include your model and data files, as well as your AMPL output.)

2...