## Description

1 Malfoy Catering

Lucius and Narcissa Malfoy didn’t get to be rich, pureblood, dark wizards without lots of galleons.

Their family made their money in the Wizard catering business. As part of the business, their son

Draco is responsible for ensuring that they have enough clean napkins to meet demand over a period

of n days. The number dj of napkins required on the jth day is known in advance. To satisfy this

requirement, Draco can either buy new napkins for α galleons each, or he can have the napkins laundered. The laundry provides both fast and slow magical cleaning services, In fast service, napkins

are returned q days later for a cost of β galleons per napkin, and in slow service, napkins are returned

p days laters at a cost of γ dollars per napkin. Natrually, p > q, and α > β > γ. Suppose that Draco

must plan for a period of n = 10 days, and the number of required napkins is given as

set T /1*10/ ;

parameter d(T) / 1 50, 2 60, 3 80, 4 70, 5 50, 6 60, 7 90, 8 80, 9 50,

10 100 / ;

Finally, for Draco’s instance, we have p = 4, q = 2, α = 200, β = 75, and γ = 25.

1.1 Problem

Formulate Draco’s problem as a min cost network flow problem and solve it using GAMS. In order to

get full credit, you must model the problem as a min-cost network flow problem. Hint: Your network

should have 22 nodes in it for Draco’s instance. After solving the instance, you should display the

following information, using GAMS parameters named as specified.

Display Item GAMS Parameter Name

Minimum cost required to meet demand Cost

Number of equations in your GAMS model NumEqu

Total number of napkins purchased NumBought

2 Least “Squares.”

2.1 Dynamic Sets Background

This problem is also designed to test our ability to use dynamic sets. We will use the sets

Problem 2 Page 1

ISyE/CS635 Problem Set #4

sets

ALLI /c1*c400/

ALLJ /x1*x100/

;

sets

I(ALLI) /c1*c6/

J(ALLJ) /x1*x4/

;

You only need to declare your equations once. You will re-define the equations for the second

model by dynamically adjusting the sets I and J to include all of the elements from ALLI and ALLJ

for the second part of the problem. Remember, when writing your equations, you declare them over

the full domain (larger set), but you define them (write them) only for those elements you want—the

subset. All of this problem can be done in a single GAMS file.

2.2 The Small Problem

The set of six equations in four variables (1)—(6) does not have a unique solution.1

8×1 − 2×2 + 4×3 − 9×4 = 17 (1)

x1 + 6×2 − x3 − 5×4 = −16 (2)

x1 − x2 + x3 = 7 (3)

x1 + 2×2 − 7×3 + 4×4 = −15 (4)

x3 − x4 = 6 (5)

x1 + x3 − x4 = 0 (6)

For each equation i, and values of variables x = (x1, x2, x3, x4), let ei be the absolute difference

(error) between the left hand side and the right hand side. For example, for i = 2 and x = (−5, 3, 1, 4),

the error is

e2 = |(1)(−5) + 6(3) − (1)(1) − 5(4) − (−16)| = |8| = 8.

2.1 Problem

Write a linear programming instance that will minimize the total absolute error:

e1 + e2 + e3 + e4 + e5 + e6.

Solve this instance with GAMS. Display both the (minimum) total absolute deviation (in a parameter

named TotalDevSmall and the values of x that achieve this, in a parameter named xValSmall(ALLJ).

For example, your code may look like this:

parameters

TotalDevSmall,

xValSmall(ALLJ)

;

TotalDevSmall = ztotdev.L ;

1Most six equations with four variables don’t.

Problem 2 Page 2

ISyE/CS635 Problem Set #4 Prof Michael Ferris

xValSmall(J) = x.L(J);

display TotalDevSmall;

display xValSmall;

2.2 Problem

For the same instance, write a linear programming instance that will minimize the maximum error

in any one equation. Namely find values of x that will

min max{e1, e2, e3, e4, e5, e6}.

Create your instance in GAMS and solve it. What is the minimum max-error that can be achieved?

Display this value in a parameter called MinMaxDevSmall. For example, your code may look like

this:

parameters

MinMaxDevSmall

;

MinMaxDevSmall = zminmax.L;

display MinMaxDevSmall;

2.3 General Least “Squares.”

Let J = {1, 2, . . . , |J|}. For each j ∈ J you have a decision variable xj . You are given a set of equations

containing these decision variables as follows:

X

j∈J

aijxj = bi ∀i ∈ I

Define the absolute error of each equation i ∈ I as the quantity

ei(x) =

X

j∈J

(aijxj ) − bi

∀i ∈ I.

2.3 Problem

Write a linear program to solve the following optimization problem:

min

x∈R|J|

X

i∈I

ei(x).

Using the GAMS code below to create an instance with |N| = 100, |M| = 400 create and solve this

large random instance. Note the use of yes make the sets I and J contain all of the elements in

ALLI and ALLJ. Be sure to also include the option seed=666 line so that all of us create the same

random instance.

* Reset sets

I(ALLI) = yes;

J(ALLJ) = yes;

option seed = 666 ;

A(I,J) = uniform(-10,10) ;

b(I) = uniform(-100,100) ;

Problem 2 Page 3

ISyE/CS635 Problem Set #4 Prof Michael Ferris

Solve your instance and display the final total deviation in a parameter named TotalDevBig.

For example,

parameters TotalDevBig ;

TotalDevBig = ztotdev.L ;

display TotalDevBig;

2.4 Problem

Solve the same instance from Problem 2.3, but in this case to minimize the maximum error:

min

x∈R|J|

max

i∈I

ei(x)

Solve your instance and display the final minimum maximum deviation in a parameter named

MinMaxDevBig. For example,

parameters MinMaxDevBig;

MinMaxDevBig = zminmax.L;

display MinMaxDevBig;

3 Broom Rental

Oliver Wood retired from his career as keeper at Puddlemere United to start the Wood Broom Rental

Company WBC,

2 and he needs your help. There is a fleet of 94 brooms that are distributed among 10

different locations. The (x, y) coordinates of each broom rental agency (in a grid based on kilometers3

is given in Table 1, as are the number of brooms currently in each location and the number of brooms

required for tomorrow’s rentals. The cost of transporting a broom from one location to another is 0.5

galleon/km. Naturally brooms travel “as the crow flies,” so distances between agencies are Euclidean

distances.

Place x y Required Current

Coor. Coor. Brooms Brooms

Hogwarts 0 0 10 8

Godric’s Hollow 20 20 6 13

Little Whinging 18 10 8 4

Shell Cottage 30 12 11 8

The Leaky Cauldron 35 0 9 12

Ollivander’s 33 25 7 2

Zonko’s Joke Shop 5 27 15 14

Dervish and Banges 5 10 7 11

Little Hangleton 11 0 9 15

Weasley’s Wizard Wheezes 2 15 12 7

Table 1: Information About WBC

3.1 Problem

Write a linear program in GAMS that will determine the movement of all brooms to establish the

required number of brooms at all agencies in a minimum cost manner. Ensure your linear program is

2

In the Wizarding World, brooms may be rented and used, much like cars, in our normal Muggle world.

3Wizards use the metric system

Problem 3 Page 4

ISyE/CS635 Problem Set #4

in the form of a minimum cost network flow problem, and set up the GAMS file to use the appropriate

CPLEX options so it solves as such.

Wood would like to know two things. First, he would like to know the minimum broom tranportation cost (in a GAMS parameter transportCost), as follows:

parameter transportCost ;

transportCost = cost.L;

display transportCost;

Second, according to the optimal transportation plan, he would like to know the set of all locations requiring extra brooms that do not receive any brooms from their closest location (in a set

not from closest).

set not_from_closest(P);

option not_from_closest:0:0:1;

display not_from_closest;

hints:

• Be sure to put quotation marks around elements of sets when defining them if there are spaces

in the element names.

• GAMS has functions sqrt and sqr that may be useful.

• The second part will require a little bit of GAMS coding trickery.

4 Untied Airlines

Prof. Wright hates flying United airlines through O’Hare (ORD). This is a problem, as he is a soughtafter lecturer who frequently must make trips from his home base in Madison (MSN) to San Francisco

(SFO), Houston (IAH), Washington DC (DCA), and Orlando (MCO). If Prof. Wright flies United, he

must travel through ORD, if he travels Delta he can choose to go via Detriot (DTW) or Minneapolis

(MSP).

The travel times between various locations in minutes are:

MSN.ORD 22, MSN.DTW 65, MSN.MSP 46,

MSP.SFO 213, MSP.IAH 139, MSP.DCA 125, MSP.MCO 176,

ORD.SFO 247, ORD.IAH 124, ORD.DCA 82, ORD.MCO 135,

DTW.SFO 280, DTW.IAH 147, DTW.DCA 53, DTW.MCO 130

Delay times at ORD are approximately uniformly distributed between 0 and 3 hours, at DTW the

delay time are are between 0 and 1.5 hours and between 0 and 2 hours at MSP.

We will assume that Prof. Wright makes 3 trips to each location every year. Prof. Wright is a

notorious cheapskate, and lives for frequent flyer miles. So he would like to only fly one airline.

4.1 Problem

Should Prof. Wright switch to Delta? Justify your answer with a mathematical model and explain

what your model does to deal with the uncertainty.

4.2 Problem

What if you add a constraint that he must always use the same hub?

4.3 Problem

What if he forgoes frequent flyer miles – which route should he then use for which flight?

Problem 4 Page 5