Project 1
The theme of this project is to implement the basic network design model
that is presented in the lecture note entitled “An Application to Network
Design,” and experiment with it.
Specific Tasks:
1. Create a program that is capable of doing the following:
• As input, it receives the number of nodes (N), the traffic demand
values (bij) between pairs of nodes, and the unit cost values fo
the potential links (aij).
• As output, the program generates a network topology (directed
graph), with capacities assigned to the links (directed edges), ac-
cording to the studied model, using the shortest path based
fast solution method (see at the end of the refe
ed lecture
note). The program also computes the total cost of the designed
network.
Important notes:
• Any programming language and operating system can be used, it
is your choice.
• For the shortest path algorithm you may download and utilize any
existing software module from the Internet. If you use this oppor-
tunity, then include in your documentation a precise reference that
tells where the module comes from.
2. Clearly explain how your program works. It is helpful to use flowcharts
for visualizing the explanation.
3. Run your program on examples that are generated as explained below.
• Let the number of nodes be N = 21 in each example.
• For each example, generate the aij, bij values according to the rules
described below. In these rules k is a parameter that will change
in the experiments.
1
– For generating the bij values, take your 10-digit student ID,
and repeat it 2 times, and append the first digit again at the
end, to obtain a 21-digit number. For example, if the ID is
XXXXXXXXXX, then after repetition it becomes
0 XXXXXXXXXX. Let d1, d2, . . . , d21 denote the indi-
vidual digits in this 21-digit number. Then the value of bij is
computed by the formula
ij = |di − dj|.
For example, using the above sample ID, the value of b3,7 will
e b3,7 = |d3 − d7| = |2− 6| = 4.
– For generating the aij values, do the following. For any given
i, pick k random indices j1, j2, . . . , jk, all different from each
other and also from i. Then set
aij1 = aij2 = . . . = aijk = 1,
and set aij = 100, whenever j 6= j1, . . . , jk. Ca
y out this
independently for every i.
Remark: The effect of this is that for every node i there will
e k low cost links going out of the node, the others will have
large cost. The shortest path algorithm will try to avoid the
high cost links, if possible, so it effectively means that we limit
the number of links that go out of the node, thus limiting the
network density.
• Run your program with k = 3, 4, 5 . . . , 14. For each run generate
new random aij parameters independently.
4. Show graphically in diagrams the following:
• How does the total cost of the network depends on k?
• How does the density of the obtained network depends on k? Here
the density is defined as the number of directed edges that are
assigned nonzero capacity, divided by the total possible numbe
of directed edges, which is N(N − 1).
• Show some of the obtained network topologies graphically. Specif-
ically, draw three of them: one with k = 3, one with k = 8, and
one with k = 14.
2
5. Structure of the program: your entire program should contain three
well separated modules:
• Module 1: generates the parameters of the random examples,
These are passed on to Module 2.
• Module 2: ca
ies out the main algorithm (see Task 1.), and passes
on the result to Module 3.
• Module 3: creates the required presentation of the results (dia-
grams, figures, see Task 4.).
6. Provide a
ief (1-2 paragraph) ve
al justification that explains why
the obtained diagrams look the way they do. In other words, try to
convince a reader that what your diagrams show is indeed the “right”
ehavior, that is, your program that ca
ies out the network design is
likely co
ect.
7. Also include a section in the project document that is often refe
ed to
in a software package as ”ReadMe file.” The ReadMe file (or section)
provides instructions on how to run the program.
Submission guidelines:
There will be a separate posting about submission guidelines and
formatting requirements.
3
Project 1
The theme of this project is to implement the basic network design model
that is presented in the lecture note entitled “An Application to Network
Design,” and experiment with it.
Specific Tasks:
1. Create a program that is capable of doing the following:
• As input, it receives the number of nodes (N), the traffic demand
values (bij) between pairs of nodes, and the unit cost values fo
the potential links (aij).
• As output, the program generates a network topology (directed
graph), with capacities assigned to the links (directed edges), ac-
cording to the studied model, using the shortest path based
fast solution method (see at the end of the refe
ed lecture
note). The program also computes the total cost of the designed
network.
Important notes:
• Any programming language and operating system can be used, it
is your choice.
• For the shortest path algorithm you may download and utilize any
existing software module from the Internet. If you use this oppor-
tunity, then include in your documentation a precise reference that
tells where the module comes from.
2. Clearly explain how your program works. It is helpful to use flowcharts
for visualizing the explanation.
3. Run your program on examples that are generated as explained below.
• Let the number of nodes be N = 21 in each example.
• For each example, generate the aij, bij values according to the rules
described below. In these rules k is a parameter that will change
in the experiments.
1
– For generating the bij values, take your 10-digit student ID,
and repeat it 2 times, and append the first digit again at the
end, to obtain a 21-digit number. For example, if the ID is
XXXXXXXXXX, then after repetition it becomes
0 XXXXXXXXXX. Let d1, d2, . . . , d21 denote the indi-
vidual digits in this 21-digit number. Then the value of bij is
computed by the formula
ij = |di − dj|.
For example, using the above sample ID, the value of b3,7 will
e b3,7 = |d3 − d7| = |2− 6| = 4.
– For generating the aij values, do the following. For any given
i, pick k random indices j1, j2, . . . , jk, all different from each
other and also from i. Then set
aij1 = aij2 = . . . = aijk = 1,
and set aij = 100, whenever j 6= j1, . . . , jk. Ca
y out this
independently for every i.
Remark: The effect of this is that for every node i there will
e k low cost links going out of the node, the others will have
large cost. The shortest path algorithm will try to avoid the
high cost links, if possible, so it effectively means that we limit
the number of links that go out of the node, thus limiting the
network density.
• Run your program with k = 3, 4, 5 . . . , 14. For each run generate
new random aij parameters independently.
4. Show graphically in diagrams the following:
• How does the total cost of the network depends on k?
• How does the density of the obtained network depends on k? Here
the density is defined as the number of directed edges that are
assigned nonzero capacity, divided by the total possible numbe
of directed edges, which is N(N − 1).
• Show some of the obtained network topologies graphically. Specif-
ically, draw three of them: one with k = 3, one with k = 8, and
one with k = 14.
2
5. Structure of the program: your entire program should contain three
well separated modules:
• Module 1: generates the parameters of the random examples,
These are passed on to Module 2.
• Module 2: ca
ies out the main algorithm (see Task 1.), and passes
on the result to Module 3.
• Module 3: creates the required presentation of the results (dia-
grams, figures, see Task 4.).
6. Provide a
ief (1-2 paragraph) ve
al justification that explains why
the obtained diagrams look the way they do. In other words, try to
convince a reader that what your diagrams show is indeed the “right”
ehavior, that is, your program that ca
ies out the network design is
likely co
ect.
7. Also include a section in the project document that is often refe
ed to
in a software package as ”ReadMe file.” The ReadMe file (or section)
provides instructions on how to run the program.
Submission guidelines:
There will be a separate posting about submission guidelines and
formatting requirements.
3
An Application to Network Design
Consider the following network design problem. Given N nodes
and a demand of transporting data from node i to node j (i, j =
1, . . . , N, i 6= j) at a speed of bij Mbit/s.
We can build links between any pair of nodes. The cost fo
unit capacity (=1 Mbit/s) on a link from node i to j is aij.
Higher capacity costs proportionally more, lower capacity costs
proportionally less.
Set aii = 0, bii = 0 for all i so we do not have to take care of
the case when i = j in the formulas.
The goal is to design which links will be built and with how
much capacity, so that the given demand can be satisfied and
the overall cost is minimum.
Let us find an LP formulation of the problem!
Let zij be the capacity we implement on link (i, j). This is not
given, this is what we want to optimize. If the result is zij = 0
for some link, then that link will not be built.
With this notation the cost of link (i, j) is aijzij, so the objective
function to be minimized is
Z =
∑
i,j
aijzij
To