Homework 9: Integer programs

    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 xed cost of operating the plant for a year are given below. Determine how Comquat can maximize its yearly pro t from computer production.

Plant
Production
Plant  xed cost
Cost per

capacity
($ Million)
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 ( gures are in millions of dollars):

Option
Minimum
Maximum
Expected

investment
investment
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 ve 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
CS/ECE/ISyE 524    Introduction to Optimization    Steve Wright,    Spring 2021


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.
2
5
0
13
15
15
3









6
0
11
7
13
11
7
A =

9
13
5
0
3


6





7

6
13
15
0
23
11
7


3
7
7
7
0


6





7

4





5
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 rst 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 di ers according to the direction of travel.)
















































2 of 2