[SOLVED] Isye/cs635 – problem set #6

1 GlassCo
Glassco manufactures wine glasses, beer glasses, champagne glasses and whiskey glasses.
Each type of glass uses time in the molding shop, time in the packaging shop, and a certain
amount of glass. The resources required to make each type of glass are given in Table 1.
Table 1: GlassCo Resource Requirements
WINE
GLASS
BEER
GLASS
CHMPGNE
GLASS
WHISKEY
GLASS
Molding time 4 minutes 9 minutes 7 minutes 10 minutes
Packaging time 1 minute 1 minute 3 minutes 40 minutes
Glass 3 oz 4 oz 2 oz 1 oz
Selling price $6 $10 $9 $20
At present, 600 minutes of molding time, 400 minutes of packaging time and 500 oz of
glass are available.
1.1 Problem
Write down and solve the LP (in GAMS) that Glassco should solve, assuming the company
wishes to maximize revenue. You should use appropriate sets to index both the variables
you choose and the constraints that you formulate.
1.2 Problem
Write down (and solve) the dual of this LP problem, in the same GAMS file. You should set
up two separate models and include just those equations needed in each model in the model
statement.
Please also make note how the marginals of the constraints in Problem 1.1 are related
to the level of the variables in Problem 1.2. What about the marginals of the constraints in
Problem 1.2 and the variables in Problem 1.1?
Problem 1 Page 1
CS635 Problem Set #6 Prof. Michael Ferris‘
2 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 x 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) neighbours to change from on to off, or from off to on. Corner cells are considered to
have 2 neighbours, edge cells to have three, and interior cells to have four.
2.1 Problem
Formulate and solve an integer program for finding 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. A cell should not be clicked more than once.
2.2 Problem
What if each cell has a three-way bulb? (Repeatedly clicking on a single three way bulb
changes its state from off to low, from low to medium, from medium to high, from high to
off, and so on.) Which is easiest (a) turning off all the lights when they’re all on their high
setting, (b) turning them off when they’re all on medium, or (c) turning them off when they’re
all on low?
3 Probability Chains
Consider a network given by a set of nodes J and a set of pairs D(J, K) where K is the
predecessor (downstream) node of J. Implicitly, you may think about this as k = dj . Such
a network is called a forest since it is a collection of trees. Suppose this forest represents a
collection of rivers.
Suppose there is a barrier at each node J that can be removed at a price C(J). If it is removed, then the probability of a fish being able to pass the barrier increases by pi(J,0
remove0
)
from its current value pbar(J). The value of the habitat immediately above this barrier is
given by v(J).
3.1 Problem
The problem is to find the set of barriers to remove that maximizes the expected amount
of habitat available to the fish for a given budget b. The data is provided in a “gdx” file
(data.gdx) and can be loaded using the code
set J(*) ’barrier site’,
P / keep, remove /;
alias (J,K);
set D(J,K) ’downstream barriers from j (not including j)’,
ROOT(J) ’root nodes of forest’;
parameter
pi(J,P) ’increase in probability of passage due to P’,
v(J) ’net habitat between J and its upstream neighbors’,
c(J,P) ’cost of project P at J’,b ’available budget’,
pbar(J) ’current probability of passage at J’;
$gdxin data.gdx
$load J,D,ROOT
$load pi,v,c,b,pbar
$gdxin
Let xj,p be a binary variable determining if you remove the barrier at j or not. Let zj be
the probability of access to habitat immediately upstream of j. For root nodes, this is clearly
p¯j +
P
p
πj,pxj,p. For nodes further upstream, zj is (¯pj +
P
p
πj,pxj,p) ∗ zk where k is the node
downstream from j.
Solve this model as a linear mixed integer program by introducing a new variable yj,p
that represents xj,p ∗ zk = xj,p ∗ zdj
.
You may want to experiment first with the data that is provided in data-small.gdx for a
much smaller instance.
Problem 3 Page 3