Wilford owns a home on Martha's Vineyard that he plans to rent out during the summer, starting on Memorial Day (May 30, day 1) and ending on Labor Day (September 5, day m). Each rental party may not enter the house until 3:30 p.m. on the day of arrival, and they must leave the house by 11:00 a.m. on the day of departure, so a rental party may enter on the same day as another rental party departs. Wilford has received n bids, each of which has expressed the desired day of arrival, vj, desired day of departure, dj, and the total amount, rj, that the prospective tenant is willing to pay in rent for this desired dj - vj day time period.

Wilford must decide today which subset of the m bids he should accept. His objective is to maximize the total rental income.

a. Define the decision variables for Wilford's problem.

b. Formulate this problem as an integer linear programming model. You may wish to incorporate the matrix A into your formulation, where each row i represents a day (i = 1, 2, ...., m), and each column j represents a bid (j = 1, 2, ...., n), where

1 if the party in bid j plans to stay beyond day i

aij =

0 otherwise

For example, if the party in bid 22 desires to arrive on day 53 and depart on day 59, rows 53 through 58 in column 22 contain ones and all other elements in column 22 are zeroes.

c. Attempt to structure this problem as a network flow diagram. You may either describe it in words or model the network for an equivalent but smaller problem with, say, m = 20 and n = 8 with at least four overlaps.

d. Which network flow algorithm (or variation thereof) would be most helpful for solving this problem?