Assignment 3: Linear Programming

CSC373 
Assignment 3: Linear Programming

Instructions
1. Typed assignments are preferred (e.g., PDFs created using LaTeX or Word), especially if
your handwriting is possibly illegible or if you do not have access to a good quality scanner.
Either way, you need to submit a single PDF named “hwk3.pdf” on MarkUS at https:
//markus.teach.cs.toronto.edu/2022-05
2. You will receive 20% of the points for a (sub)question when you leave it blank (or cross o↵
any written solution) and write “I do not know how to approach this problem.” If you leave
it blank but do not write this or a similar statement, you will receive 10%. This does not
apply to any bonus (sub)questions.
3. You may receive partial credit for the work that is clearly on the right track. But if your
answer is largely irrelevant, you will receive 0 points.
Q1 [30 Points] Max Flow with Losses
The Maximum Flow with Losses problem is similar to the maximum flow problem: you are given
as input a directed graph G = (V,E) with source s and sink t, except here, in addition to the
graph, each vertex u 2 V  {s, t} has a real number called the loss coecient "u 2 [0, 1] such that
the total flow out of u must equal (1  "u) times the total flow into u. As before, we are looking
for an assignment of flow values to every edge that maximizes the total flow out of s.
(a) [15 Points] Show how to solve the maximum flow with losses problem using linear programming.
Give a detailed description of your linear program and justify clearly and carefully that it solves
the problem.
(b) [15 Points] Convert the linear program above into the standard form, and describe how a
solution to this modified linear program would lead you to a solution of your original linear program.
More precisely, specify these quantities: n, m, an n⇥1 coecient vector c, an m⇥n constraint matrix
A, and an m ⇥ 1 bound vector b (all numbers are real numbers) such that the linear program from
part (a) can be “converted” to the linear program which maximizes cT x subject to the constraints
Ax  b and x  0. Also, specify clearly which variable of your original linear program does each
xi (the i-th entry of x) play the role of.
Q2 [20 Points] Tasks and Tools
You have m di↵erent tasks to complete and to help you, n di↵erent software tools you could
purchase, each with a positive integer cost ci. You have no choice about which tasks to complete
(you must complete them all), but you get to choose which tools you will purchase.
Tools are not necessary to complete tasks; however, certain tasks have additional costs if they are
completed without the use of specific tools. Information about these additional costs is provided
through non-negative integer dependencies: for all pairs i, j, di,j is the additional cost of completing
1

task i without tool j – a dependency can be equal to zero to indicate that there is no additional
cost.
Finally, there are known incompatibilities between certain tools: for each tool i, you have a list
of all the other tools with which tool i is incompatible. Obviously, it is not possible to install
incompatible tools at the same time.
Formulate a linear program (or a binary integer program – i.e., an optimization problem with a
linear objective, linear constraints, but with each variable restricted to taking a value in {0, 1})
to determine which tools to purchase in order to minimize your total cost (from the purchase of
tools and the dependencies). Also, remember to justify the correctness of your solution – this is
important!
Q3 [10 Points] LP and IP Exercise
Consider the following linear program L in the standard form:
Maximize x2
Subject to 3x1 + 5x2  8
7x1 + 3x2  12
x1, x2  0
We define the corresponding integer program I as follows:
Maximize x2
Subject to 3x1 + 5x2  8
7x1 + 3x2  12
x1, x2 2 {0, 1}
Plot the feasible region of L. Note: You do not need to submit this with the assignment, but it will
be helpful to plot the feasible region. You can use any online graphing programs such as desmos,
fooplot, etc.
(a) [2.5 Points] What are the vertices of the feasible region of L? (No explanation is needed.)
(b) [2.5 Points] What are the optimal solutions of L and I? What are the corresponding optimal
objective values? (No explanation is needed.)
(c) [2.5 Points] Provide the dual linear program (which we will call L0
) of L. Clearly indicate which
dual variable in your formulation corresponds to which primal constraint.
(d) [2.5 Points] What are the optimal solutions of L0 and its corresponding integer program I0
(i.e., the program you obtain upon restricting all of the variables of L0 to {0, 1})? What are the
corresponding optimal objective values? Does strong duality hold for this particular pair of primal
and dual integer programs i.e., for I and I0
?
2