Homework 7: Integer programs

CS/ECE/ISyE 524 Introduction to Optimization 
Homework 7: Integer programs

See the course website for instructions and submission details.
1. [5 pts] Thrift store. How should you make change for 99 cents if the goal is to minimize the total
weight of the coins used? The following table shows the weight of each type of coin. You may use any
number of each type of coin.
Type of coin penny nickel dime quarter
Weight (grams) 2.500 5.000 2.268 5.670
2. [15 pts] 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. [15 pts] ABC Investments. ABC Inc. is considering several investment options. Each option has
a minimum investment required as well as a maximum investment allowed. 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. [15 pts] Lights Out. In Tiger Electronic’s handheld solitaire game Lights Out, the player strives to
turn out all 25 lights that make up a 5 × 5 grid of cells. On each turn, the player is allowed to click
on any one cell. Clicking on a cell activates a switch that causes the states of the cell and its (edge)
neighbors to change from on to off, or from off to on. Corner cells are considered to have 2 neighbors,
edge cells to have three, and interior cells to have four. Find a way to turn out all the lights in as few
turns as possible (starting from the state where all lights are on).
Hints: The order in which the cells are clicked doesn’t matter (think about it!), and there is no need
to click any cell more than once.
1 of 1