A connoisseur has m bottles of rare wine in his cellar. Bottle j is currently tj years old. Starting next year, he wishes to drink one bottle each year on his birthday, until his supply is exhausted. Suppose that his utility for drinking bottle j is given by Uj(t) (t is its age when consumed) and that utility is additive. The connoisseur wishes to know in what order to drink the wine to maximize his total utility of consumption.
a) Formulate his decision problem of which bottle to select each year as an integer linear program. What is the special structure of the formulation? How can this structure help in solving the problem?
b) Suppose that the utility for consuming each bottle of wine is the same, given by a convex function U(t). Show that it is optimal to select the youngest available bottle each year.