## Description

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