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