CSE524 Homework 9- Integer programs Solution

See the course website for instructions and submission details.
1. Checked luggage. You’re trying to pack as many souvenirs as possible to bring home from your trip, but your suitcase has a limited capacity. It can hold a maximum of 30 pounds of weight and 15 gallons of volume. Which souvenirs should you pack? The weights and volumes are as follows:
Souvenir number 1 2 3 4 5 6 7 8 9 10
Weight (lbs) 5 6 7 6 4 6 7 3 8 5
Volume (gal) 2 4 5 3 3 2 3 1 2 4
2. Comquat Computers. Comquat owns four production plants at which personal computers are produced. Comquat can sell up to 20,000 computers per year at a price of $3,500 per computer. For each plant the production capacity, cost per computer, and fixed cost of operating the plant for a year are given below. Determine how Comquat can maximize its yearly profit from computer production.
Plant Production capacity Plant fixed cost ($ Million) Cost per computer ($)
1 10,000 9 1,000
2 8,000 5 1,700
3 9,000 3 2,300
4 6,000 1 2,900
3. ABC Investments. ABC Inc. is considering several investment options. Each option has a minimum and maximum investment allowed (only if the option is chosen). These restrictions, along with the expected return are summarized in the following table (figures are in millions of dollars):
Option Minimum
investment Maximum
investment Expected return (%)
1 3 27 13
2 2 12 9
3 9 35 17
4 5 15 10
5 12 46 22
6 4 18 12
Because of the high-risk nature of Option 5, company policy requires that the total amount invested in Option 5 be no more that the combined amount invested in Options 2, 4 and 6. In addition, if an investment is made in Option 3, it is required that at least a minimum investment be made in Option 6. ABC has $80 million to invest and obviously wants to maximize its total expected return on investment. Which options should ABC invest in, and how much should be invested?
4. Paint production. As part of its weekly production, a paint company produces five batches of paints, always the same, for some big clients who have a stable demand. Every paint batch is produced in a single production process, all in the same blender that needs to be cleaned between each batch. The durations of blending paint batches 1 to 5 are 40, 35, 45, 32 and 50 minutes respectively. The cleaning times depend of the colors and the paint types. For example, a long cleaning period is required if an oil-based paint is produced after a water-based paint, or to produce white paint after a dark color. The
1 of 2
times are given in minutes in the following matrix A where Aij denotes the cleaning time after batch
i if it is followed by batch j.
 0
 5
A = 13  9

3 11
0 15
13
7 7
13
0
5
7 13
15
23
0
7 11
15
11
3 
0
Since the company has other activities, it wishes to deal with this weekly production in the shortest possible time (blending and cleaning). What is the corresponding order of paint batches? The order will be applied every week, so the cleaning time between the last batch of one week and the first of the following week needs to be accounted for in the total duration of cleaning.
Note: Exhaustively looping through all possible orderings is not an acceptable solution!
(Hint: This problem is a nonsymmetric traveling salesman problem — “nonsymmetric” because the distance between nodes i and j differs according to the direction of travel.)
2 of 2