A problem in solid waste management. A new and strict state law is forcing most cities and...

A problem in solid waste management. A new and strict state law is forcing most cities and towns in the state 10 upgrade their solid waste facilities from dumps to lined landfills-unless, of course. their facilities already meet the standards, A group of four towns in one of the counties of the state is investigating cooperative approaches and has formed a compact in which the towns have agreed to share costs in a regional partnership. Their partnership, according to the agreement, must undertake the least-cost alternative.

That doesn't necessarily mean that one grand solid waste facility will be buill. Several may be built and operated, hut the total cost will be divided among the towns in proportion to their population. The compact calls in your consulting firm to do the analyses lo see what arrangements or groupings produce the least-cost alternativeThe consulting firm studies all possible physical arrangements of groupings of towns that make sense. Each grouping of two or more towns implies thai a landfill site has been identified for that grouping and the arrangement has been "costed out" so that the annual costs or the facility and of hauling are known. Single-town alternatives are also cos ted out. TIle map of the towns and the listing of groupings with their costs are provided below.

COST OF VARIOUS GROUPINGS

Your job as consultant to the compact is tel advise on the arrangements that cost the towns, in total, the least money. Perhaps that is (A, B) and (C D) or perhaps some other arrangement. There are t\VO ways to deal with the problem. One way is to enumerate all alternatives. This will work in this case because the problem is small. but it will be very difficult in larger problems, Hence, enumeration is not the methodology you are asked to discuss. What is desired here is a zero-one programming approach. Your programming approach should seck the least-cost arrangement of towns subject to the constraint that each town is included in exactly one coalition, even if that coalition is just itself. Here are some variables and definitions to start you off.

j = index of coalitions of which there are 14:

Xj = 1, 0: it is 1 if grouping j (say, A, B) is included in the least-cost solution, and 0 otherwise: and

Ni = the set of coalitions to which town i could belong (it can only belong to one, though).

More explicitly,

NA = {1, 2, 6, 7, 8, 10, 11}

NB = {1, 3, 4, 6, 7, 9, 10, 12}

Nc = {2, 3, 5, 6, 8, 9, 10, 13}

ND = {4, 5, 7, 8, 9, 10, 14}

Where the number in brakets are the numbers identifying conditions.

Write a zero-one programming problem that minimizes cost subject to the constraint that each town helongs to precisely one coalition (which could be a grouping of just itself). This problem is called the set partitioning problem (because of the sets or partitions NA. NB. etc.), and it typically is very integer-friendly when solved by linear programming.