Name solutions isye 6669A, Deterministic Optimization

Download 87.69 Kb.

Date	26.11.2017
Size	87.69 Kb.
	#34850

Variables
Subject to x 1s + x 2s – x s1 – x s2 = – s (balance at stadium)

NAMESolutions______

ISYE 6669A, Deterministic Optimization

Exam II Solutions – Monday, November 19, 2001

60 minute time limit

INSTRUCTIONS

Work alone. Do not collaborate with or copy from anyone else.

You may NOT use a calculator for this exam; all computations should be easy enough to do by hand.

Answer all seven questions. The extra credit questions are optional. Show your work, so that I can give you partial credit if you don’t get the correct answer.

When asked to explain “why”, you may keep your answers brief – the questions are designed so that you do not need to provide long answers.

The exam is “closed-book”. You may not refer to any books, notes, or other materials during class, aside from the exam materials themselves.

Good luck!

1. (16 points) Match each network diagram (a) through (d) with the most specialized type of network problem (i) through (v) that it represents. Some network problems may not be used, and some may be used more than once.

This arc has cost –1;

all other arcs have cost 0

Assignment Problem
Maximum Flow Problem
Shortest Path Problem
Transportation Problem
None of the above (General Network Flow Problem)

(a)_____(iii)___ (b)______(i)_______

(c)_____(iv)______ (d)______(ii)______

(25 points) A new football stadium is being built. Each seat brings a profit of $5000 for the team. However, to avoid traffic after the games, the state will only allow the team to build as many seats as the roads leading from the stadium to the highway can handle in one hour. For example, if the roads can handle a maximum of 75,000 people per hour, then the stadium can have up to 75,000 seats.

A network of 5 access roads exists. Currently, each road has a certain traffic capacity in each direction. No new roads can be built; however, the state will allow the football team to widen at most 3 of the access roads. Each road i has a current capacity c_i, costs w_i dollars to widen, and would have a capacity k_i if widened.

Road 1 Road 4

Road 3

Road 2 Road 5

(25 points) Formulate an integer program that the team can use to decide how many seats to put in the stadium, and which access roads (if any) it will widen in order to accommodate all of the traffic, in order to maximize its profit.

Variables

y_i = 1 if road i is widened, and 0 if not

x_ij = amount of traffic flow on road (i,j)

s = number of seats in stadium

Maximize 5000 s – c₁y₁ – c₂y₂ – c₃y₃ – c₄y₄ – c₅y₅

Subject to x_1s + x_2s – x_s1 – x_s2 = – s (balance at stadium)

x_s1 + x₂₁ + x_h1 – x_1s – x₁₂ – x_1h = 0 (balance at intersection 1)

x_s2 + x₁₂ + x_h2 – x_2s – x₂₁ – x_2h = 0 (balance at intersection 2)

x_1h + x_2h – x_h1 – x_h2 = s (balance at highway)
x_1s  c₁ + (k₁ – c₁) y₁(capacity of each road)

x_s1  c₁ + (k₁ – c₁) y₁

x_2s  c₂ + (k₂ – c₂) y₂

x_1s  c₂ + (k₂ – c₂) y₂

x₁₂  c₃ + (k₃ – c₃) y₃

x₁₂  c₃ + (k₃ – c₃) y₃

x_1h  c₄ + (k₄ – c₄) y₄

x_h1  c₄ + (k₄ – c₄) y₄

x_2h  c₅ + (k₅ – c₅) y₅

x_h2  c₅ + (k₅ – c₅) y₅
y₁ + y₂ + y₃ + y₄ + y₅  3 (at most 3 roads widened)
all x_ij  0

all y_i binary (0 or 1)

(Extra Credit: 5 points) Suppose the decision of which roads will be widened has already been made and cannot be changed. What special type of network problem are we left with? Why?

Maximum flow – once all the y’s are defined, this is just a max flow problem.
3. (10 points) Model each of the following using integer programming constraints. Make your constraints as tight as possible.

(5 points) Each week, a production manager can choose whether or not to schedule an inspector to work at his plant. Let x be the number of days the inspector works, and let y be a binary variable that is 1 if the inspector works that week, and 0 if not. Write a constraint or constraints to ensure that if the inspector is not scheduled to work, then he works zero days that week. (Note: The number of days worked can be fractional – the inspector might work 1½ days, for example.)

x  5 y (x  7 y is also okay – you could assume a 7-day work week instead of a 5-day work week)

(Extra Credit: 5 points) A group of friends are browsing through the local Blockbuster Video store, trying to decide which movies to rent. The friends, all ISyE professors, would like to plan their movie-watching schedule using integer programming. Let x_i = 1 if movie i is rented, and 0 if not. Write a constraint or constraints to say “If we rent both The Truman Show and Pleasantville, then we can only rent one of The Matrix, Jurassic Park, and Sixty One.”

2 (x_T + x_P) + x_M + x_J + x_S  5
As you might have noticed, this one was hard. (That’s why it was extra credit!)

(5 points) A hardware manufacturer is going to open a new plant. Let x_i = 1 if tool i will be produced there, and 0 if not. Let y_j = 1 if they will buy machine j for the plant, and 0 if not. As part of the integer program the plant manager is formulating to help decide which pieces of machinery to buy, the following restriction must be converted to mathematical form: “No tools of type i can be produced unless machines A, B, and D are all bought.”

x_i  y_A

x_i  y_B

x_i  y_D
This is the disaggregated form. I gave partial credit for the weaker aggregated form, 3 x_i  y_A + y_B + y_D.
4. (15 points) In the following branch-and-bound tree, answer the following questions:

(8 points) Which nodes do you still need to branch from? Why?

Fractional node 1700 is the only one. Of all the other unbranched nodes, two are integer, one is infeasible, and fractional 2000 has a worse objective than an integer node so we know the optimal solution could never be found by branching on it.

(7 points) What is the gap between the best solution and the best bound found so far? Show your calculations.

Absolute gap = best integer – best bound = 1825 – 1700 = 125.

5. (8 points) For the question below, select all of the correct answers from the choices given. You may need to select more than one answer per question.

Given that problem Y is NP-hard, to show that problem X is NP-hard you need to:

Transform problem Y into problem X in polynomial time.
Transform problem X into problem Y in polynomial time.
Show how to solve problem Y in polynomial time.
Show how to solve problem X in polynomial time.

(i) is the only correct answer.

(10 points) Answer EITHER question (a) OR question (b).

(10 points) Write the constraint corresponding to the LINGO statement

@FOR( origins( I):@SUM( sinks( J): x( I, J)) <= cap( I) * y ( I));

(10 points) Write the constraint corresponding to the AMPL statement

subject to Supply {i in origins}: sum {j in sinks} x[i,j] <= cap[i] * y[i];

_j x_ij  cap_i y_i for all origins i

(16 points) Consider the following network flow problem in which the dashed arcs are the basic arcs. (The numbers shown in the figure are the costs on each arc and the supplies/demands at each node.)

7 3

(5)

(1) (3)

(2) (8) 4

2
(7)

(4) (2)

(6)

(8 points) What are the flows on each arc at this basic solution?

(1,2)___2___ (1,3)___0___ (2,4)____3____ (2,5)___6____ (3,2)__0___

(3,5)___0___ (4,5)___0___ (4,6)____0____ (5,6)___4____
All nonbasic arcs ((1,3), (3,5), (4,5), and (4,6)) have zero flow by definition. The other flows can easily be calculated using the node balance constraints like we did in class.
(b) (8 points) What are the reduced costs of these two arcs? Show your work.

(1,2)____0_____ (3,5)____– 3 ____

Basic variables have reduced costs of zero, so (1,2) has zero reduced cost. For (3,5), find the cycle it creates among basic arcs when it is added: (3,5), (5,2), (2,3). Add costs of arcs pointing in the cycle direction (counterclockwise in this case) and subtract those in the opposite direction: 6 – 2 – 7 = – 3.