CO 353 – Homework assignment 4 Winter ’20 Page 1
CO 353 – Winter ’20
Homework assignment #4: (Due on Tuesday, Mar 24th, at the beginning of class) Instructions:
You may use any result proved in class directly, but you should be explicit about which result you are using.
You may collaborate with your classmates, but please acknowledge your collaborators by writing their names in your homework.
Any source of help other than the ones stated above are considered cheating. Question 1 (20 points)
Solve the following IP by branch-and-bound:
max 3×1+5×2
s.t. −4×1 + 3×2 ≤ 6
3×1 + 2×2 ≤ 6
x1, x2 ≥ 0 and integer
Instructions:
Start with zbest = −∞ and xbest undefined.
Include a drawing of the branch-and-bound tree, clearly identifying on each node the corresponding subproblem IPo, IP1, etc.
The numbering of the subproblems must correspond to the order in which the branch-and-bound nodes were explored, i.e. the order must be IPo, IP1, IP2, . . ..
For each node of the branch-and-bound tree, solve the LP relaxation using Python/Gurobi. There is no need to provide the code, just write down the optimal solution to the LP relaxation and the optimal value
For each node of the branch-and-bound tree, also write down the current value of zbest after the node has been explored (i.e. LP relaxation solved and any branching/fathoming decision made)
For each pruned node, provide the reason why it was pruned
NOTE: You can obviously use Python/Gurobi to solve the IP directly. Any such answer will not
be accepted.
(a) Provide the branch-and-bound tree for the following choices:
Whenever you have a choice of branching variable, choose the one with smallest index
Whenever you have a choice of which subproblem to choose to process next, choose the one that was most recently created. If you must choose between two nodes just created by branching,
choose to process first the one that imposes the ≤ constraint. (b) Provide the branch-and-bound tree for the following choices:
Whenever you have a choice of branching variable, choose the one with smallest value of max{Lk,Rk}, where Lk is the value of the LP relaxation after branching on xk ≤ ⌊x∗k⌋ and Rk is the value of the LP relaxation after branching on xk ≤ ⌈x∗k⌉.
Whenever you have a choice of which subproblem to choose to process next, choose the BFS approach.
CO 353 – Homework assignment 4 Winter ’20 Page 2
Question 2 (20 points)
Consider three matroids Mi = (S, Ii ) for i = 1, 2, 3 over the same ground set. Also, consider ce > 0, ∀e ∈ S.
The maximum weight common independent set problem asks one to determine the set J ⊆ S of maximum totalweightsuchthatJ∈I1,J∈I2 andJ∈I3 (thatis,J∈I1∩I2∩I3).
It is known that computing the maximum weight subset J of S that is independent in both M1 and M2 is solvable in polynomial time on |S| (provided independence can be checked in polynomial-time).
Show that computing the maximum weight J ⊆ S such that J ∈ I1 ∩ I2 ∩ I3 is NP-hard.
Hint: Consider a reduction from the NP-complete problem called the directed hamiltonian cycle problem
ongraphD=(V,A),andletM1 =(A,I1)whereB⊆A∈I1 ifandonlyif:
The underlying undirected graph is a forest. The underlying undirected graph is what you get when
you convert directed edges (u, v) into undirected ones {u, v}.
and there are no two arcs in B of the form (u,v) and (v,u).
Question 3 (20 points)
Consider the following problem:
b−ST: Inputs:
Undirected simple connected graph G = (V, E) Integersbv ≥0,forallv∈V
Output:
YESifandonlyifthereexistsaspanningtreeT ofGsuchthat|δ(v)∩T|≤bv,∀v∈V.
Show that b − ST is NP-complete.
Hint: Consider a reduction from Hamiltonian Cycle (undirected version)
Question 4 (20 points)
The purpose of this question is for you to provide an optimal solution to the knapsack problem:
Input and output:
n
c1 c2 c3 … cn
a1 a2 a3 … an b
n
max cjxj
s.t.
j=1 n
ajxj ≤b j=1
x ∈ {0, 1}n
(1)
The input is n and the positive integer coefficients c ∈ Zn, a ∈ Zn, b ∈ Z. They are given in a file of the form:
A complete example is given by: . . . and corresponds to the knapsack instance: max 7×1 +9×2 +2×3 +15×4
st 3×1 +4×2 +1×3 +7×4 ≤10 x ∈ { 0 , 1 } 4+ .
The output file must describe an optimal solution to the given knapsack problem instance. It consists of a single line of the form:
In our example, a correct solution file could be:
4
7 9 2 15
3 4 1 7 10
x ∗1 x ∗2 . . . x ∗n
Page 2
CO 353 – Homework assignment 4 Winter ’20 Page 3
1001
More example input and output files will be posted online.
Filename
You must implement your code in a file called knapbb{userid}.py, where {userid} must be replaced by your uwaterloo numeric ID. For instance, if your id is 12345, your file must be called knapbb12345.py.
Running the code
Your code must take exactly two arguments. The first argument is the name of a file containing the input instance. The second argument is the name of a file where the output is to be written.
Your code must be implemented in Python 3 and must run by executing the command (obviously re- placing the .py file name by the above specified file name):
Submitting the code
Please submit the code via Dropbox on learn.uwaterloo.ca by the homework deadline.
Libraries and code writing
You must implement all your code. You may use import sys and the sort functionality of python, and import gurobipy. Any other import is not allowed. You may consult with other sources regarding basic python syntax, but not how to code your homework.
Also, your code should be understandable, so please add comments on your code to make sure the graders understand what is the purpose of each part of the code. Marks may be deducted for a code that is not understandable.
Your code MUST use the Python/Gurobi interface. It cannot just try and enumerate solutions, use dynamic programming or any other alternative method.
Caution regarding grading
Please stick to the above guidelines. If you deviate from these guidelines, you will get marks deducted, even if your implementation is perfect.
python knapbb12345.py input.txt output.txt
Page 3