Career Development

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