代写MA4254、代写Java/C++编程

日期：2022-10-10 09:39

MA4254/AY22-23 – Discrete Optimization

Computational Assignment

August 2, 2022

Instructions

1. This project assignment accounts for 20% of your total grade.

2. It is due 28th October 2022, 11:59pm (Friday, Week 11). Please submit early – exten-

sions will *not* be granted.

3. You are to submit a report and your code. In addition to responses to all questions in

this assignment, your report should also include a write-up that

(a) Explain the steps you did when performing this computational project

(b) Explain implementation details

(c) Your results as well as your interpretations and conclusions from these results

Graphs and figures are an excellent way to present your solutions. In all, an appropriate

length of your report is about 3 pages per question.

4. Follow the submission guidelines strictly: Include all files into a single ZIP file. You

should only have a single report answering all questions. Name your file with your

matriculation number (e.g. A01234.zip).

5. You are required to include your code in your submission. The code does not count

into the page length of your report. You are permitted to code in any language you

wish.

6. Please strive to write your report as neatly as possible. LATEX is the recommended

(and simplest) option, but not strictly required. If you need help, please write to me

or consult your classmates.

7. You are allowed to verbally discuss the assignment with your coursemates. You are

not allowed to read each other’s written answers.

1

8. You must write your own code. You can, however, discuss coding techniques or diffi-

culties with your classmates.

9. Cite all references clearly. This include Internet references.

10. You are not allowed to consult external solutions; e.g., you cannot consult a piece of

code that directly solves a question in the assignment. If in doubt, check with me.

You are not allowed to consult students or solutions from previous years – doing so

will result in a zero grade for the assignment.

1. Facility Location Problem

Recall the facility location problem: Suppose that there are n facilities and m customers

who require a service from one of these facilities. For a facility to be able to provide the

service, the facility needs to be “switched on”, for a cost of cj. The customers selects, among

all the facility that are “switched on”, to be serviced by a single facility at a cost of di,j. The

objective is to minimize the total cost comprising switching on facilities and travel costs,

subject to the constraint that every customer is serviced.

This problem can be modeled as a MILP. In the following, the decision variables are yj,

which models whether facility j is “switched on”, and xi,j, which models whether customer

i selects facility j for servicing.

An alternative and equivalent MILP formulation is to replace the constraint xi,j ≤ yj

with the constraint

The latter formulation (AFL) is known as the aggregate facility location problem.

2

(a) Count the number of linear inequalities in (FLP) and (AFL). Which formulation has

fewer number of inequalities?

(b) Show that the set of feasible solutions to (FLP) and (AFL) are equal. Conclude that

these two formulations are equivalent.

(c) Derive the linear relaxation to (FLP) by replacing the binary constraints yj ∈ {0, 1}

with the box constraint 0 ≤ yj ≤ 1. Denote the linear relaxations by (FLP-LR).

(d) Derive the linear relaxation to (AFL) by replacing the binary constraints yj ∈ {0, 1}

with the box constraint 0 ≤ yj ≤ 1. Denote the linear relaxations by (AFL-LR).

(e) Denote the optimal value to (FLP) and (AFL) by (FLP-Val) and (AFL-Val) respec-

tively. Denote the optimal value to (FLP-LR) and (AFL-LR) by (FLP-LR-Val) and (AFL-

LR-Val) respectively. Arrange the optimal values of (FLP-Val), (AFL-Val), (FLP-LR-Val),

and (AFL-LR-Val) in increasing order wherever possible, and where it is not possible, provide

justification.

(f) Next, we generate random instances of the facility location problem. For this, it

is recommended that you pick n = 15 and m = 20 (m should be larger than n). Pick n

locations uniformly at random from the square [0, 1] × [0, 1] to model the locations of the

facilities. Draw n random variables from the Unif[0, 1] distribution to model the cost. Draw

an additional m locations uniformly at random from the square [0, 1] × [0, 1] to model the

locations of the customers. The distance di,j is the Euclidean distance between the i-th

customer and the j-th facility. Calculate the distance matrix between every customer and

facility.

(g) Using the generated dataset, solve the facility location problem using (FLP) and

(AFL). Solve the linear relaxations (FLP-LR) and (AFL-LR) corresponding to these formu-

lations. Record the optimal value to all four instances. Repeat this process 100 times with

different realizations of all random variables (in other words, repeat steps (f) and (g) 100

times).

(h) Compare and comment on the difference between the optimal values of all four opti-

mization instances. How often is (FLP-Val) equal to (FLP-LR-Val)? How often is (AFL-Val)

equal to (AFL-LR-Val)?

2. Traveling Salesman Problem

The Traveling Salesman Problem seeks the shortest possible tour while visiting every location

exactly once, and returning to the starting location.

Concretely, suppose that there are n locations indexed by {1, 2, . . . , n}. Let dij be the

matrix whose (i, j)-th entry denotes the distance between location i and j. A tour is repre-

sented by a permutation {a1, a2, . . . , an} of the sequence {1, 2, . . . , n}. As such, a tour visits

all locations in the following order:

a1 → a2 → . . . an?1 → an → a1.

In this problem, we will be implementing the Simulated Annealing algorithm for solving

the Traveling Salesman Problem.

(a) Create a function that takes as input a tour and outputs the total distance

f({a1, a2, . . . , an}) = da1,a2 + da2,a3 + . . .+ dan?1,an + dan,a1 .

3

Remember to return to the starting location!

(b) We need to create a function that takes as input a tour, and outputs a perturbed

tour. These perturbed tours are candidate tours that the algorithm will evaluate and decide

to accept or reject. We generate a candidate tour as follows. Suppose the input tour is the

following sequence:

{a1, a2, . . . , ai?1, ai, ai+1, . . . , aj?1, aj, aj+1, . . . , an}

Pick indices 1 ≤ i < j ≤ n uniformly at random. The candidate tour is the following:

{a1, a2, . . . , ai?1, aj, aj?1, . . . , ai+1, ai, aj+1, . . . , an}.

(c) Implement the following: Initialize with a random tour. Initialize with some choice of

temperature parameter T > 0. Initialize with some choice of temperature update parameter

0 < η < 1. At every iteration, you should perform the following sequence of steps:

1. Let fcurr denote the length of the current tour.

2. Propose a randomly chosen new candidate tour. Let fcand denote the length of the new

tour.

3. Draw a random variable u ～ Unif[0, 1]. If the following condition holds

exp

(

?fcand ? fcurr

T

)

≥ u,

replace the current tour with the candidate tour. If the condition does not hold, simply

proceed.

4. Update the choice of temperature with

T ← ηT.

An instance of the simulated annealing algorithm for solving the TSP problem performs

multiple loops of the above sequence of steps.

(d) Generate a random instance to test your implementation. Pick n = 100. Generate

n cities uniformly at random over the [0, 1]× [0, 1] grid. Let the pairwise distances between

cities be the Euclidean distance.

Implement the Simulated Annealing algorithm described above to find the shortest tour.

Do note that the Simulated Annealing algorithm is a heuristic – while it is very effective

at finding high quality solutions, it is not able to certify optimality of any solution. So,

generally speaking, you will not be able to tell if your solution is globally optimal.

Suggestions: Try η = 0.99. Run for about 10000 loops. Experiment with a few choices

of initial temperature T .

(e) Plot the cities with the tour to show your results. An optimal tour does not edges

that intersect. Does your tour have such edges?

(f) Experiment with a different proposal rule in which we pick a pair of indices i < j,

and we swap the indices i and j while leaving all other indices (including those between i

and j) intact. How does this choice of proposal rule compare with the previous one?

4

(g) Download the file busstops.csv from LumiNUS. Use these locations as the cities.

Report the shortest tour you are able to find (xloc and yloc). You are permitted to use any

method or heuristic you find appropriate. Submit the sequence you found according to the

posted format (see submitTSPbusstop.csv as a guide). Post your distance (distance only!)

on the LumiNUS forum as a challenge to your classmates.

Submission guideline. You are to submit a csv file with the sequence of id’s that your

tour visits. Do not use an internal naming system. I will use your files to verify the distance

of your tour. Check with the posted file submitTSPbusstop.csv as a guide.

Thanks. The dataset is the location of all Bus Stops in Singapore, and is obtained from

LTA DataMall: