ISE 530 Optimization Methods for Analytics

Final examination

Question 1

Each hour from 10AM to 7PM, Bank of America receives checks and must process them. Its goal is to process all the checks the same day they are received.  The bank has 13 check-processing machines, each of which can process up to 500 checks per hour.   It takes one worker to operate each machine.  The bank hires both full-time and part-time workers. Full -time workers work 10AM-6PM, 11AM-7PM or Noon-8PM shifts and are paid $200 per day.  Part-time workers work either 2PM-7PM or 3PM-8PM shifts and are paid $95 per day.  The number of checks received each day is given in the table below. In the interest of maintaining continuity, the bank must have at least three full-time workers under contract.  Formulate a linear program that finds a cost-minimizing work schedule that processes all checks by 8PM.

Question 2

Consider the following list of points.

The goal is to find a centroid (x* , y* ) that summarizes the data.  In particular, we want to find the centroid and a radius ϵ such that all points in the table are within a distance of at most ϵ of the centroid.

1. Formulate a problem that finds (x* , y* ) and ϵ so that all points are at distance at most ϵ of (x* , y* ), and the radius ϵ is minimized.

2. Formulate a problem that finds (x* , y* ) and ϵ so that 6 points are at distance at most ϵ of (x* , y* ) (while the remaining two points can be arbitrarily far), and the radius ϵ is minimized.

Question 3

1.  Consider the optimization problem

min 47x1 + 93x2  + 17x3  − 93x4

s.t.  − x1  − 6x2  + x3 + 3x4  ≤ −3

− x1  − 2x2  + 7x3 + x4  ≤ 5

3x2  − 10x3  − x4   ≤ −8

− 6x1  − 11x2 − 2x3 + 12x4  ≤ −7

x1 + 6x2  − x3 − 3x4  ≤ 4.

Compute its dual.

2.  Consider the following linear optimization problem

max 2x1 + 3x2  + 2x3  + 3x4

s.t. 2x1 + x2  + 3x3  + 2x4  ≤ 8

3x1 + 2x2 + 2x3 + x4  ≤ 7

x1,x2,x3,x4  ≥ 0,

and its dual

min 8y1 + 7y2

s.t. 2y1 + 3y2  ≥ 2

y1 + 2y2  ≥ 3

3y1 + 2y2  ≥ 2

2y1 + y2  ≥ 3

y1 , y2  ≥ 0.

a) Write the optimality conditions

b)  The solution (y1 , y2 ) = (1, 1) is optimal for the dual.  Using the optimality conditions, find a corresponding primal solution.

Question 4

Consider the optimization problem

min x1(2) + 2x2(2) − 2x1x2 − 2x2 .

x1,x2∈R

1.  Starting from point (x1,x2) = (0.5, 0.5), compute an iteration of steepest descent. Is the resulting point stationary? Is it optimal?

2.  Starting from point (x1,x2) = (0.5, 0.5), compute an iteration of Newton method. Is the resulting point stationary? Is it optimal?

3.  Consider the change of variables x3  = x1  − x2, and note that the problem can be rewritten as

min   x3(2) + x2(2) − 2x2.

x2,x3∈R

Starting from point (x2,x3) = (0.5, 0), compute an iteration of steepest descent. Is the resulting point stationary? Is it optimal?