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?
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:
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. 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.
