Math Models of Operations Research, MATP 4700/ DSES 4770.

Third Exam, Friday, December 6, 2002.

You may use any result from your notes or a homework that is clearly stated. You may use one sheet of handwritten notes, but no other sources. The exam consists of six questions, and lasts one hundred minutes. You can collect the graded exam from me next week. Grades should be available early next week.

1.

(15 points) Determine the best bound on the optimal solution value of an ILP with each of the following objective functions that is available from the specified LP relaxation optima $\tilde{x}$.

(a)

$\min \; x_1 -4x_2 + 70x_3$, $\tilde{x}=(1,0,\frac{2}{7})$.

(b)

$\min \; 60x_1 - 16x_2 + 10x_3$, $\tilde{x}=(\frac{1}{2},1,\frac{1}{2})$.

(c)

$\max \; 90x_1 + 11x_2 + 30x_3$, $\tilde{x}=(0,\frac{1}{2},5)$.

2.

(20 points) Jane is applying to graduate school. There are five schools she is interested in attending, but she can only afford to send application fees to three of them. She has put a value on the education at each of the schools, and she has also decided what her chances of being accepted are. She wants to maximize the sum of the values of the three chosen schools, but she wants to choose the three in such a way that the sum of the probabilities of rejection is no greater than 1.5. The values are as follows:

School n	1	2	3	4	5
Value vn	90	150	80	100	120
Probability of rejection pn	0.4	0.7	0.4	0.5	0.6

(a)

(4 point) Formulate Jane's problem as an integer programming problem, with one constraint for the number of applications and one constraint for the probabilities.

(b)

(8 points) How would you solve this integer program using dynamic programming and backward recursion equations? Describe the states, stages and recursion equations. State f₅(s) explicitly. (Hint: You will probably need two state variables.)

(c)

(8 points) Illustrate your solution method by solving the following subproblem: There are two schools 4 and 5 left, Jane has one application left, and she only has 0.5 of slack remaining in her probability constraint.

3.

(10 points) The point x=(1,3,2) is an interior point for the linear program

$$\begin{array}{lrcrcrcll} \min & 10x_1 & + & 7x_2 & + & 6x_2 ... ... + & x_3 & = & 6 \\ &&&&& x_i & \geq & 0 & i=1,2,3 \end{array}$$

Let $\mu=6$. Show there exists a dual feasible solution y with dual slacks s satisfying $x_is_i=\mu$ for i=1,2,3. (Hint: The dual of $\min\{c^Tx:Ax=b,x \geq 0\}$ is $\max\{b^Ty:A^Ty \leq c\}$.)

4.

(20 points) The following integer programming problem is being solved using branch and bound:

$$\begin{array}{ll} \min & x_1 + 3x_2 + 2x_3 + 7x_4 \\ \mb... ...i=1,...,4 \\ & x_i \mbox{ integer, } i=1,...,4, \end{array}$$

where Ax=b is a given set of linear constraints. The progress so far is shown here. Here, xⁱ is the solution to the LP relaxation at node $\mbox{IP}^i$ and zⁱ is the value of xⁱ.

(a)

(5 points) What is the best solution found so far to the integer program?

(b)

(8 points) Which node(s) of the branch and bound tree can be fathomed?

(c)

(7 points) What subproblems would you create next?

5.

(15 points) In the graph below, we want to find the shortest path from vertex s to vertex t. Using Dijkstra's algorithm, so far we have labeled vertices s, 1, 2, 3, and 4. For each labeled vertex, the first label gives the length of the shortest path to that vertex from s going via labeled vertices only, and the second label gives the index of the previous vertex on this shortest path. The edge length is indicated next to each edge. Note that the edges between labeled vertices have not been drawn in the picture. What is the shortest path from s to t and what is its length?

6.

(20 points) In this problem, we are considering a standard form primal-dual pair,

$$\begin{array}{lrclrlrcrclr} \min & c^Tx &&&& \max & b^Ty \\ ... ... & \qquad (D) \\ & x & \geq & 0 &&&&& s & \geq & 0 \end{array}$$

(a)

(10 points) The diagonal scaling matrix that we use for primal-dual interior methods is D, where the ith diagonal entry is $D_{ii}=\sqrt{\frac{x_i}{s_i}}$. Some interior point methods use a diagonal matrix X with X_ii=x_i. Other methods use a diagonal matrix S with $S_{ii}=\frac{1}{s_i}$. Show that $D_{ii}=\sqrt{\frac{1}{\mu}} X_{ii}=\sqrt{\mu} S_{ii}$ if $x_is_i=\mu$ for all i for some $\mu>0$.

(b)

(10 points) Show that if $\bar{x}>0$ and $\left( \frac{x_i-\bar{x}_i}{\bar{x}_i} \right)^2 \leq 1$ then $x_i \geq 0$.