# 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.]