PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
The problem can be modelled as a minimum cost circulation problem. Create the following directed graph G with a capacity and a cost at each arc. We have one node for each time 0, 1, …, m. For each time 0 <= t < m, add an arc from node t to node t+1 with cost 0 and capacity equal to c _ t, the amount of available racks at time t. Finally, for each request s _ i,e _ i,v _ i, add an arc from e _ i to s _ i with cost -v _ i and capacity 1 (let’s call these ``back arcs’').
Recall that a circulation in a directed graph is an assignment of a value f _ a to each arc a in the graph. This assignment must satisfy f _ a <= c _ a (the capacity of arc a) and there must be flow conservation at each node v (the total flow into v equals the total flow out of v). The cost of a circulation is the sum of f _ a * p _ a over all arcs a where p _ a is the cost of the arc. Now, a solution to OVENTIME easily corresponds to a feasible circulation in graph G with the same cost. For each request is that is used in the OVENTIME solution, just add a cycle from s _ i to e _ i and back along the back arc for request i. Conversely, any circulation with integer values f _ a corresponds to a feasible OVENTIME solution with the same cost, just include each item i where f _ a = 1 where a is the arc from e _ i back to s _ i.
It is a fairly simple fact that there is an optimum solution that assigns integer values to the f _ a given that the capacities are integers. Thus, the problem reduces to solving the minimum cost circulation problem we just described so any of the standard algorithms that work in the presence of negative cost arcs will suffice (these also ensure f _ a is integer when the capacities are integer).
Alternatively, one could form the following linear program. Let x _ i be variables, one for each request i. Then we want to maximize the sum x _ i * v _ i over all requests i such that for any time t, the sum of the x _ i over requests that require time t is at most c _ t. Furthermore, each request i has 0 <= x _ i <= 1. Based on the discussion of maximum circulations having integer optimums, one can argue that this simple linear program assigns integers (namely 0 or 1) to each x _ i so the problem can be solved by simply invoking simplex. In fact, the implementation of simplex can be simplified based on the observation that all x _ i are either 0 or 1 in any basic feasible solution (e.g. we don’t need to divide by the pivot value).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.