Homework #4

SYS 6003

Problem 1:

Recall the Travelling Salesperson Problem (TSP) we discussed in lecture (given a list

of nodes and arcs for pairwise distances between each node, we must find the

shortest path or complete tour that visits each node exactly once). Try and

formulate the TSP problem without using the lecture notes or any other materials;

try and see how well you can formulate it now that we’ve gone over it in lecture.

a) Let variable xij = 1 if arc (i,j) is in the tour, 0 otherwise, and let variable yi be

a counter to track the order of nodes visited from 1 to the cardinality of N,

where N is the total number of nodes. Formulate (define any needed sets,

parameters, etc., and write all constraints, objective function, etc.) this

version of the TSP. You cannot add any additional variables; only use the ones

provided.

b) If the arc connecting node 6 and 9 cannot be in the final shortest path tour,

how would you ensure this is true in your TSP formulation?

Homework #4

SYS 6003

Problem 2:

Formulate (write all constraints, objective, etc.) a new version of the Traveling

Salesperson Problem (TSP) based on having decision variables of the form “xcn = 1

if city c is the nth city visited, else 0.” If necessary, you may define other variables as

well. Please make sure you clearly define any sets/parameters/variables/etc. used

in the formulation. Again, try to formulate without using any notes or outside

sources; we will go over this formulation in Lecture on 11/5.

Homework #4

SYS 6003

Problem 3:

It is your job to pick companies to attend the Career Fair. There are several different

types of companies (e.g. manufacturing, telecom, consulting) and you have an

upper and lower bound on how many companies can represent each industry. You

also have a space requirement for each company (e.g. some have large booths and

some have small booths) and you have a limit on the total amount of space for the

fair. Finally, each company has a value associated with how highly ranked it is by

the students.

a) Formulate a linear model to decide which companies to invite to the fair.

b) Suppose that you cannot invite Google unless you also invite Yahoo – how

would you incorporate this in your model?

c) Suppose that you can invite Google or Yahoo but not both – how would you

incorporate this in your model?

d) Supposed that you must invite exactly one of Google or Yahoo – how would

you incorporate this in your model?

Homework #4

SYS 6003

Problem 4:

For the network flow problem below, please explicitly write out the objective

function and constraints, and declare/define any variables, parameters, etc. Please

note that your objective function and constraints should be written algebraically

and NOT in set/generic notation. The values at each node is the supply/demand

required for that node, and the arcs have the cost per unit and the upper-bound

flow capacity written on them.

A

B

C

D

E

$4 / inf.

$2 / inf.

$3 / 10

$3 / 15

$3 / 20

$3 / 25

30

40

10 -60

-20

$1 / 15

Homework #4

SYS 6003

Problems from a Textbook (see the “SYS 6003_Homework #4 Scan”:

Exercise 7.1

Exercise 7.2

Exercise 10.6

Exercise 10.7