2023年11月25日

Java代写 | SWEN30006 Software Modelling and Design Project 1: Snakes and Ladders

本次加拿大作业是一个算法代写相关的assignment

Q1 [20 Points] Travel Planning is Hard

Anu is making holiday travel plans. There are 6 cities that she is interested in visiting. For each
k 2 f1; : : : ; 6g, it would cost ck to incorporate city k into the itinerary but she would gain hk
units of happiness from visiting city k (both amounts are regardless of which other cities are on the
itinerary). Unfortunately, she has a limited budget of B, so she may not be able to visit all the cities.

There are also other considerations. Cities 3 and 5 are too similar to each other, so Anu prefers to
visit at most one of them. The same is true for cities 1, 5, and 6. Some cities can only be enjoyed in
the fullest if visited together with some other cities. Anu doesn’t want to visit cities 5 or 6, unless
at least one of cities 3 and 4 is also on the itinerary. Finally, she wants to visit at least one and at
most three among the cities 1; 2; 4; 5; 6.

Anu obviously wants to nd an itinerary (a subset of cities to visit) that will maximize her happiness,
given the constraints listed above.

(a) [10 Points] Formulate this problem as a binary integer linear program. Here, binary means
that every variable xk in your program should be in f0; 1g.

(b) [10 Points] Imagine a relaxation of the program from part (a), where you allow each variable
xk to take any non-negative real value (i.e., xk ≥ 0). This relaxation becomes a linear program.

Write the dual of this linear program.

Q2 [20 Points] Tricky Transportation

Anu has begun her much awaited journey. While she planned a bit before leaving, she didn’t work
out all the details in advance. She now faces the problem of planning her transportation.

There are n buses running along a road (think of it as the real axis). Each bus i starts at location
si and goes to location ti (where ti > si). If she decides to use bus i, she can board at any point
x 2 [si; ti], drop o at any later point y 2 [x; ti], and must pay a xed cost ci regardless of where
she boards and drops o. Anu wants to get from point a to point b on the road (where b > a).

(a) [15 Points] Write a binary integer linear program that helps Anu achieve this goal while mini
mizing her total cost. Your program only needs to nd the minimum total cost. It is OK if it does
not nd the locations at which Anu should board and drop o buses. Your program must have a
nite (and ideally, a polynomial) number of constraints. Prove that your program is correct.

(b) [5 Points] Suppose each bus is operated by one of two companies. Let T1 and T2 be the indices
of buses operated by companies 1 and 2, respectively (T1 \ T2 = ; and T1 [ T2 = f1; : : : ; ng). For
some reason, Anu wants to make sure that she don’t spend more than 70% of the total cost on any
single company. Note that this constraint might raise the minimum total cost she needs to pay in
order to get from point a to point b. How would you add this constraint to the program in part (a)?

Q3 [20 Points] Similar Cities

As Anu was thinking more about her dilemma of avoiding similar cities from Q1, she realizes that
she perhaps modeled the problem too simply. The actual problem is a bit more involved and graph
theoretic.

There is an undirected graph G = (V; E), where every node in V is a city and every edge in E is a
road connecting two cities. Anu wants to travel from source city s to destination city t. Anu has
made a list L containing pairs of similar cities: for every (u; v) 2 L, cities u and v are too similar
to each other, so Anu would prefer to avoid visiting them both. Anu is interested in solving the
following decision problem.

AvoidSimilar:

Input: Undirected graph G = (V; E), list L containing pairs of similar cities, source city s, desti
nation city t.

Question: Does there exist a path from s to t such that for every (u; v) 2 L, it visits at most one
of cities u and v?

(a) [10 Points] Prove that AvoidSimilar is NP-complete. For hardness, provide a reduction from
the Exact 3SAT problem we saw in class.

Exact 3SAT:

Input: An exact 3CNF formula ’ with n variables x1; : : : ; xn and m clauses C1; : : : ; Cm.

Question: Does ’ admit a satisfying assignment?

[Hint: The gadgets shown below may be useful. In the variable gadget on the left, going from node
a to node b requires making a binary choice, similar to setting a variable to true or false. In the
clause gadget on the right, going from node a to node b requires making a ternary choice, similar
to choosing a literal of the clause to set to true. Think about combining these gadgets.]