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 3×1 + 5×2 8

7×1 + 3×2 12

x1, x2 0

We define the corresponding integer program I as follows:

Maximize x2

Subject to 3×1 + 5×2 8

7×1 + 3×2 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