Hello, I need help with this project.
I need the codes and the documentation done.
Please attach the screenshots. Thank you so much!!!
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 for 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 referred 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 0123456789, then after repetition it becomes 012345678901234567890. Let d1, d2, . . . , d21 denote the indi- vidual digits in this 21-digit number. Then the value of bij is computed by the formula bij = |di − dj|. For example, using the above sample ID, the value of b3,7 will be 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. Carry out this independently for every i. Remark: The effect of this is that for every node i there will be 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 number 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: carries 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 brief (1-2 paragraph) verbal 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” behavior, that is, your program that carries out the network design is likely correct. 7. Also include a section in the project document 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. 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 for 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 referred 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 0123456789, then after repetition it becomes 012345678901234567890. Let d1, d2, . . . , d21 denote the indi- vidual digits in this 21-digit number. Then the value of bij is computed by the formula bij = |di − dj|. For example, using the above sample ID, the value of b3,7 will be 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. Carry out this independently for every i. Remark: The effect of this is that for every node i there will be 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 number 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: carries 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 brief (1-2 paragraph) verbal 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” behavior, that is, your program that carries out the network design is likely correct. 7. Also include a section in the project document 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. 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 for 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