The Lockbox Problem

 

Consider a national firm that receives checks from all over the United States. Due to the vagaries of the U.S. Postal Service, as well as the banking system, there is a variable delay from when the check is postmarked (and hence the customer has met her obligation) and when the check clears (and when the firm can use the money). For instance, a check mailed in Pittsburgh sent to a Pittsburgh address might clear in just two days. A similar check sent to Los Angeles might take eight days to clear. It is in the firm's interest to have the check clear as quickly as possible since then the firm can use the money. In order to speed up this clearing, firms open offices (called lockboxes) in different cities to handle the checks.

For example, suppose we receive payments from four regions (West, Midwest, East, and South). The average daily value from each region is as follows: $70,000 from the West, $50,000 from the Midwest, $60,000 from the East, and $40,000 from the South. We are considering opening lockboxes in L.A., Chicago, New York, and/or Atlanta. Operating a lockbox costs $50,000 per year. The average days from mailing to clearing is given in the table. Which lockboxes should we open?

  
Table 1: Clearing Times

First we must calculate the losses due to lost interest for each possible assignment. For example, if the West sends to New York, then on average there will be $560,000 (= ) in process on any given day. Assuming an investment rate of 20%, this corresponds to a yearly loss of $112,000. We can calculate the losses for the other possibilities in a similar fashion to get table 2.

  
Table 2: Lost Interest ($1000)

The formulation takes a bit of thought. Let be a 0-1 variable that is 1 if lockbox j is opened and 0 if it is not. Let be 1 if region i sends to lockbox j.

Our objective is to minimize our total yearly costs. This is:

One set of constraints is as follows:

(each region must be assigned to one lockbox).

A more difficult set of constraints is that a region can only be assigned to an open lockbox. For lockbox 1 (L.A.), this can be written

(There is nothing special about 100; any number at least 4 would do.) Suppose we do not open L.A. Then is 0, so all of , , and must also be. If is 1 then there is no restriction on the x values.

We can create constraints for the other lockboxes to finish off the integer program. For this problem, we would have twenty variables (four y variables, sixteen x variables) and eight constraints. This gives the following 0-1 linear program:

A possible LINGO model is

model:
  sets:
    Region /West, Midwest, East, South/;
    Box /LA, Chi, NY, Atl/: open, cost;
    Link (Region, Box): assign, loss;
  endsets

  min = @sum(Link: loss * assign) + @sum(Box: cost * open);
  @for (Region(i):
    @sum(Box(j): assign(i,j)) = 1
  );
  @for (Box(j):
    @sum(Region(i): assign(i,j)) < big * open(j);
  );
  @for(Link: @bin(assign));
  @for(Box: @bin(open));

  data:
    big = 100;
    cost = 50 50 50 50;
    loss = 28 84 112 112
           60 20 50 50
           96 60 24 60
           64 40 40 16;
  enddata
end

If we ignore integrality, we get the solution , and the rest equal to 0. Note that we get no useful information out of this linear programming solution.

The above is a perfectly reasonable 0-1 programming formulation of the lockbox problem. Note that many variations are possible (New York costs more to operate in than other cities, South won't send to L.A., and so on).

There are other formulations, however. For instance, consider the sixteen constraints of the form

These constraints also force a region to only use open lockboxes (check this!). It might seem that a larger formulation is less efficient and therefore should be avoided. This is not the case! If we solve the linear program with the above constraints, we get the solution with the rest equal to zero. In fact, we have an integer solution, which must therefore be optimal! Different formulations can have very different properties with respect to their associated linear program. One very active research area is to take common problems and find good reformulations.

The above is an example of a fixed charge problem. There is a fixed charge for opening a lockbox, but then it can be used as much as desired. There are many other types of fixed charge problems, including the plant location problems described in Winston. Similar techniques also apply for a variety of constraints, such as batch size constraints (where if an activity is engaged in at all, it must have a minimum level, i.e., or ) and other types of ``either-or'' or disjunctive constraints.