DSA/ISE 5113 Advanced Analytics and Metaheuristics Homework #2 (Solved)

Question 1: Team-building! and Summer camp (20 points)



    (a) (10 points) Recently a summer camp was organized for an equal number of English and French children. After a few days, the children had to participate in an orienteering competition in pairs. Each pair was made up of one French and one English child. To allocate pairs, each potential pair was asked to give a weight from 1 to 10 representing their willingess to form a pair, i.e, their compatibility. For example, Rick (English) and Negan (French) have a very low compatiblity score of 2, but Rick (English) and Michonne (French) have a very high compatibility score of 10. The goal is make valid pair assignments that maximize the total compatibility.

In general, is it possible to formulate this problem type as a MCNFP?

If yes, please demonstrate by creating and solving a small example instance (draw a picture, create a data file, solve in AMPL, show the solution). To demonstrate that this problem is

        ◦ generalizable, it should work for any compatibility scores! If no, please explain why.

    (b) (10 points) For their annual work retreat, the 16 staff members of Grapes of Wrath, Inc. were invited/obliged to spend the weekend at a hotel listening to motivational speakers and participating in team-building exercises.





1
For one event, they were required to work in pairs. Erin, the administrative assistant, was tasked with creating the pairs. Knowing the likes and dislikes of everyone, she created com-patibility scores for the pairs, e.g., Michael and Jim are com-patible, Michael and Dwight are compatible, Michael and Holly are highly compatible, Jim and Dwight are compatible, Dwight and Andy are not compatible, etc...


In general, is it possible to formulate this problem type as a MCNFP?ˆ

If yes, please demonstrate by creating and solving a small example instance (draw a picture, create a data file, solve

in AMPL, show the solution). To demonstrate that this problem is generalizable, it should

    • work for any compatibility scores! If no, please explain why.

Question 2: Outdoor grilling (20 points)


“Immerse yourself in the pleasures of unique flavor creations and the gratification of outdoor cooking” says the salesman of a particular brand of high-end open-air culinary system. The proposition is simply too good, your passion has been ignited, and as visions of lazy Summer afternoons grilling delicious meats and veggies in your backyard with your friends, colleagues, and Advanced Analytics professor, you simply cannot resist purchasing this amazing piece of equipment. And thus, the following homework problem is motivated...


As equipment ages, it typically degrades, resulting in rising maintenance costs and decreasing salvage values. These conditions provide ample reasons to periodically replace such equipment.

Consider the specific case described above concerning a new gas griller you purchased to host parties at your home during the next five years. The cost of the grill is $7,600. The cost of maintaining such a high-end item per year is significant if you wish to keep it in the best condition as possible (which, of course, you do). Assume the maintenance costs during a year depend on its age at the beginning of the year, as given in Table 1.

Table 1: Open-air culinary system costs and resale values


Project




Age (years)
Maintenance costs
eBay value



0
800
.
1
1250
5000
2
2000
4100
3
2900
1500
4
4800
950
5
.
0




To avoid the high maintenance costs associated with an older grill, you may sell the grill on eBay and purchase a new grill. The price you receive on eBay depends on the age of the grill at the time of sale (see Table 1). Assume that at any time, it costs $7,600 to purchase a new grill.

The goal is to minimize the net cost (purchasing costs + maintenance costs - money received from eBay) for the next five years. Note: there is no option to simply sell the grill and not replace it: remember,


Page 2

your passion has been ignited and you must grill! Also, to simplify things, you will only make decisions at the beginning of each year..
For instance, when you first purchase the grill, it costs you $7600. You will keep the grill for at least one year, so you would incur $800 of maintenance costs. Now, at the beginning of the second year, you can either decide to keep it for another year (and incur the additional maintenance costs) or sell it on eBay for $5,000 and buy a new grill for $7,600. Then you would need to make the same decision the next year, etc.

Formulate this problem as a shortest-path network flow problem and solve.

Question 3: Racecar tires (20 points)

An automobile association is organizing a series of car races that will last four days. The organizers know that rj ≥ 0 special race tires in good condition will be required on each of the four successive days, j = 1, 2, 3, 4. They can meet these needs either by buying new tires at P dollars apiece or by reshaping1 used tires2 after the day’s race or some combination of both. Two kinds of reshaping service are available: normal service, which takes one full day at N dollars per tire, and quick service, which is an overnight service and costs Q dollars per tire. How should the association, which starts out with no special tires, meet the daily requirements at minimal cost?

Formulate a network flow model help the organizers minimize their cost.    Use the following values:
    • = $600, N = $95, Q = $250; and rj  for j = 1, 2, 3, 4 is 320, 240, 400, and 520, respectively.

Question 4: MUD-bGone (40 points)

A biochemical company manufactures and sells MUD-bGone, a chemical concentrate which when mixed with water, creates a protective coating to prevent mud and dirt from sticking to surfaces. MUD-bGone is safe to use on metal, plastic, rubber and painted surfaces. The manufacturing process requires a particular chemical base agent, obtained from a supplier, to produce MUD-bGone. Each gallon of the chemical base is able to produce only a fraction of a gallon of the final product. For example, it takes 500 gallons of the base to produce 225 gallons of the final product.

Since several stages of processing are required, the raw chemical base must be obtained a full period ahead of the time when the MUD-bGone product is to be delivered to meet demand. Additionally, due to the presence of certain additives, MUD-bGone is perishable and deteriorates over time, so that 6% of the volume kept on hand from any period to the next becomes a useless residue, unavailable for sale.

Supplies of the chemical base agent and demands of MUD-bGone over the next 4 periods, expressed in gallons, are given in Table 2, along with associated costs and prices.

Table 2: MUD-bGone Data




Periods







1
2
3
4





Maximum available chemical base
7500
9000
8500
9200
Minimum required MUD-bGone
2000
2500
2800
2500
Maximum required MUD-bGone
3000
3000
5000
5000
Cost/gallon of chemical base ($)
2.50
2.50
3.00
3.50
Price/gallon of MUD-bGone ($)
38.00
40.00
42.00
42.00







    • Reshaping is a technique by which the grooves on the tire are deepened, using a special profile-shaped tool.

2You can safely assume that after a day of racing any used tire is no longer in “good” condition.



Page 3
The cost of processing each gallon of the raw chemical base to make the final product is $11.00, and the cost to store a gallon of MUD-bGone for one period is $1.30. There is a maximum of 3000 gallons of storage capacity for the final product. The residue is removed at the end of each period so that the volume is correspondingly reduced. The storage cost includes an allocation to cover the cost of removal.

Assume that no facilities are available to store the raw chemical base; and, that the company begins with 2500 gallons of MUD-bGone on-hand and requires an inventory in period 4 of the same amount.

    (a) (20 points) Formulate the MUD-bGone problem using a network flow to maximize profits. Solve using AMPL and clearly explain the optimal solution.

    (b) (5 points) What is the per-gallon value of having additional supply of raw chemical base available in period 2? This marginal value is valid in what range (i.e., for what upper and lower limits of period 2 supply)?

    (c) (5 points) How sensitive is the optimal solution to the price/gallon of MUD-bGone in period 2?


















































Page 4