Lockbox Problem

A major credit card company (call it MasterDebt) receives checks from all different regions in the country on a daily basis. Once these checks are mailed, the time a check spends in the mail (called float) creates loss for MasterDebt, for as soon as they receive the checks they can cash them and collect interest on the funds. MasterDebt can make 15% annual interest on their cash holdings (since thats what they charge their customers in credit card interest).

In order to reduce the amount of float loss for these checks, MasterDebt is considering opening Lockbox locations across the country where the checks can be received and processed. The locations and the projected annual cost of operations (labor and overhead) at each location are as follows:

ANNUAL COSTS (X$1000)
Sacramento	Denver	Chicago	Dallas	New York	Atlanta
25	60	35	35	30	35

The average number of days that a check would float between each region and each lockbox location is shown in the following chart.

	AVERAGE FLOAT DAYS
REGION	Sacramento	Denver	Chicago	Dallas	New York	Atlanta
Central	4	2	2	2	3	3
Mid-Atlantic	6	4	3	4	2	2
Midwest	3	2	3	2	5	4
Northeast	6	4	2	5	2	3
Northwest	2	3	5	4	6	7
Southeast	7	4	3	2	4	2
Southwest	2	3	6	2	7	6

The average daily payments received from each region are shown in the following chart (in thousands of dollars).

REGION	Payments
Central	45
Mid-Atlantic	65
Midwest	50
Northeast	90
Northwest	70
Southeast	80
Southwest	60

The annual interest lost can be computed for each region-lockbox location by taking the average daily payments times the float time and multiplying by fifteen percent. For example, if payments from the Central region are sent to New York, then on any given day there is an average of $135,000 of undeposited checks, which costs MasterDebt $20,250 annually in interest.

Where should MasterDebt open lockbox locations in order to save the most money each year?

Which regions should be assigned to those lockbox locations? (This will be implemented by providing different return addresses on the payment envelopes that are sent to the different regions.)

Please explain the constraints and show how to solve using solver