Project 1The theme of this project is to implement the basic network design mo delthat is presented in the lecture note entitled “An Application to NetworkDesign”, and experiment with it.Specific Tasks:1. Create software that is capable of doing the following:• As input, it receives the number of no des (N), the traffic demandvalues (bij) between pairs of nodes, and the unit cost values forthe potential links ( aij).• As output, the program generates a network topology, with capac-ities assigned to the links, according to the studied model, usingthe shortest path based fast solution method (see at theend of the cited lecture note). The program also computes thetotal cost of the designed network.Important notes:• Any programming language and operating system can be used, itis your choice.• For the shortest path algorithm you may download and utilize anyexisting software module from the Internet. If you use this oppor-tunity, then include in your documentation a precise reference thattells where the module comes from.2. Clearly explain how your program works. It is helpful to use flowchartsfor visualizing the explanation.3. Run your program on randomly generated examples, as explained be-low.• Let the number of nodes be N = 40 in each example.• For each example, generate the aij, bijvalues according to the rulesdescribed below. In these rules k is a parameter that will changein the experiments.1– For generating the bijvalues, pick independent random inte-gers from the range [0, 1, 2, 3, 4].– For generating the aijvalues, do the following. For any giveni, pick k random indices j1, j2, . . . , jk, all different from eachother and from i. Then setaij1= aij2= . . . = aijk= 1,and set aij= 400, whenever j 6= j1, . . . , jk. Carry out thisindependently for every i.Remark: The effect of this is that for every node i there willbe k low cost links going out of the node, the others willhave large cost. The shortest path algorithm will try to avoidthe high cost links, so it effectively means that we limit thenumber of links that go out of the node, thus limiting thenetwork density.• Run your program with k = 3, 4, 5 . . . , 15. For each run generatenew random aij, bijparameters 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? Herethe density is defined as the number of directed edges that areassigned nonzero capacity, divided by the total possible numb erof directed edges, which is N(N − 1).5. Provide a brief (1-2 paragraph) verbal justification that explains whythe obtained diagrams behave the way they do. In other words, try toconvince a reader that what your diagrams show is indeed the “right”behavior, that is, your program that carries out the network design islikely correct.Note 1: If there is anything that is not specified in this project description,that means it is left to your choice.2Questions? Refer to Note 1.Submission guidelinesDescribe everything, including algorithms, program, sources, results andfigures neatly and clearly in a study. Include everything in a single documentthat can be read as a report. It should have a professional appearence,scanned handwriting is not acceptable! The preferred file type is pdf.Submit the document through eLearning. (Do not send it via e-mail!)Do not include excutable code, but include the source code that you wrote,in an appendix to the study.Notes:• The work should be individual and original. Any form of cheating isa serious violation of University policies and can lead to serious con-sequences. Also note that while there were similar projects in earliersemesters, the exact same project has never been assigned. The minordifferences between this and earlier similar projects make it easy todetect if a submission is copied from an earlier one.• It may be helpful to think about the whole project presentation thatyour task is not only to solve a technical problem, but you also haveto “sell” the results. Try to look at your work from the viewpoint of apotential customer, to whom you want to sell such a software product.How convincing would your presentation look for a
View Full Document
Unlocking...