## Description

Consider the network topology design problem described below.

Given the location of n nodes in the plane by their coordinates. Create a

network topology (represented by an undirected graph), such that it has the

following properties:

1. It contains all the given nodes.

2. The degree of each vertex in the graph is at least 3, that is, each node

is connected to at least 3 other nodes.

3. The diameter of the graph is at most 4. By this we mean that any node

can be reached from any other node in at most 4 hops. (This can be

checked by any shortest path algorithm, or by running a breadth-first

search from every node.) That is, the diameter in our case refers to

the hop-distance, not to any kind of geometric distance. Note that this

diameter bound implies that the graph must be connected.

4. The total cost of the network topology is as low as possible, where the

cost is measured by the total geometric length of all links. This means,

you have compute how long each link is geometrically (that is, how far

apart are its end-nodes), and then sum it up for all links that exist in

the network. This sum represents the total cost that we would like to

minimize, under the constraints described above in items 1,2,3. Note:

do not confuse the geometric distance with the hop-distance, used in

the previous point.

The goal is to create and implement two different heuristic algorithms for this

network topology design problem, and experiment with them. By heuristic

algorithm we mean that it does not have to guarantee the exact optimum,

just a reasonable solution.

The algorithms are of your choice. For example, you may use any of the general purpose heuristic optimization algorithms from the course material, including, but not limited to, Branch and Bound, Simulated Annealing, Greedy

Local Search, Tabu Search, Genetic Algorithm etc. Or, you can use any other

algorithm that you may find by searching the literature, or you may create

your own heuristic algorithms. Creative ideas will be appreciated! The two

1

chosen algorithms should be sufficiently different, so that it makes sense to

let them compete in finding a good solution for this problem.

Tasks:

1. Describe the two algorithms you want to use for the problem. If something is from the literature, or from the Internet, provide reference to

the source. Describe how both algorithms work. First briefly explain

informally the ideas. Then provide pseudo code for the description of

both algorithms, with sufficient comments to make them readable and

understandable by a human.

Note: If you want to use a standard heuristic algorithm, such as Simulated Annealing, Tabu Search, Genetic Algorithm etc. and something

is not clear or not fully specified in the general description, do not get

stuck! It is a typical real life situation that some details are not clear

or not precise in a verbal description. In this case, take into account

that in a heuristic algorithm there is no unique “standard” version for a

specific application. In particular, the description of a general method

does not detail how to apply it to a specific problem. Finding it out

is part of your task! Therefore, do not hesitate to fill in the missing

details using your own creativity.

2. Write a computer program that implements the algorithms. You may

use any programming language under any operating system, this is

entirely of your choice.

3. Run the program on randomly generated examples (at least 5 examples), with both algorithms. The instances are created as follows. Pick

n random points in the plane. This can be done by generating random

numbers in some range and taking them as coordinates of the points.

The value of n should be chosen such that the problem is not trivially

small (say, n ≥ 15), but the running time is still reasonable (it does not

run for days). Show how the random input is generated and present

the actual data.

4. Represent the results of the experimental runs graphically. For each

run (or for a subset of them, to limit the document size), show in a

figure the positions of the nodes and the resulting network topology,

that is, the graph. The details of the actual graphical representation

2

are left to your choice, but the essential thing is that by looking at the

figure the reader can be convinced that the algorithms find reasonable

solutions. It is important that the figures need to be generated by

software. If you compute only numerical values and then draw “by

hand” from these numbers, that is not a professional solution and will

result in reduced score.

Remark: It might be helpful to think about the whole project that

your task is not only to solve the technical problem, but you also have

to “sell” the results. Try to look at your work from the viewpoint of

a potential “customer”: how convincing your presentation would look

for a customer? If you were in the customer’s shoes, would you buy

the software?

5. Draw some conclusion about how the two algorithms compare. Is one

of them always better? If so, how much better? If the algorithms

are iterative, then how does the cost change over the iterations? How

many iterations are needed to reach a solution that does not improve

significantly in further iterations? How does the experimental running

times in the algorithms depend on the size of the problem? (You may

run more experiments, if needed. The examples mentioned in item 3

represent only a minimum set of experiments.)

Notes:

1. Your project document should include a section that is often referred

to in a software package as ”ReadMe file.” The ReadMe file (or section)

provides instructions on how to run the program. Even though in the

default case we do not plan to actually run the program, we should be

able to do it, if we wanted. For example, if something does not seem

right, and we want to double check whether the program indeed works

correctly. Therefore, instructions should be included on how to run the

program, and it has to be sufficiently detailed, so that one can actually

run it, if necessary.

2. If there is anything that is not specified in this project description, that

means it is left to your choice.

3

Submission guidelines

Submission: Describe everything, including verbal description, pseudo code,

program, input/output data, experimental results, figures, conclusions, in a

single document. Preferred file format is pdf. Submit it through eLearning, do not send via e-mail. Do not submit executable code, but include

the source code in an appendix to the document. That is, your submission

will be read as a document and not run as a program (but there are two

exceptions, see them under Evaluation).

Evaluation

The evaluation will focus on how well each of the tasks have been carried out.

Even though the submission will not be run, only read as a document, but

there are two exceptions. You will be asked to demonstrate on a computer

how your program actually runs, if any of the following cases occur:

1. You do not agree with the score received and want to improve it. In

this case the demonstration should show that your work is actually

better than the received score.

2. There is suspicion that the work is not original or not individually done

or the results were not produced by your own correctly running program. In this case a demonstration is required to clarify the situation

and to receive any score.

Note:

The work should be fully individual and original. Any form of cheating is

a serious violation of University policies and can lead to very serious consequences.

4