代写CO 353、代做Python程序设计、代写Python语言

日期：2020-03-17 11:22

CO 353 - Homework assignment 4 Winter ’20 Page 1

CO 353 - Winter ’20

Homework assignment #4:

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 3x1 + 5x2

s.t. ?4x1 + 3x2 ≤ 6

3x1 + 2x2 ≤ 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 ≤ bx

?

k

c and Rk

is the value of the LP relaxation after branching on xk ≤ dx

?

k

e.

? 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

total weight such that J ∈ I1, J ∈ I2 and J ∈ I3 (that is, 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

on graph D = (V, A), and let M1 = (A, I1) where B ? A ∈ I1 if and only if:

? 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)

? Integers bv ≥ 0, for all v ∈ V

Output:

? YES if and only if there exists a spanning tree T of G such that |δ(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:

max Pn

j=1

cjxj

s.t. Pn

j=1

ajxj ≤ b

x ∈ {0, 1}

n

(1)

Input and output:

The input is n and the positive integer coefficients c ∈ Z

n, a ∈ Z

n, b ∈ Z. They are given in a file of the

form:

n

c1 c2 c3 . . . cn

a1 a2 a3 . . . an b

A complete example is given by: . . . and corresponds to the knapsack instance:

4

7 9 2 15

3 4 1 7 10

max 7x1 + 9x2 + 2x3 + 15x4

st 3x1 + 4x2 + 1x3 + 7x4 ≤ 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:

x

?

1 x

?

2

. . . x

?

n

In our example, a correct solution file could be:

Page 2

CO 353 - Homework assignment 4 Winter ’20 Page 3

1 0 0 1

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 replacing

the .py file name by the above specified file name):

python knapbb12345.py input.txt output.txt

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.

Page 3