Project 4The goal of this project is to carry out some experiments with the methodof randomized rounding.Specific Tasks:1. Consider the task described in the lecture note “A Case Study for theUse of Randomized Rounding,” which we discussed in class at length.Provide an ILP formulation of the problem.2. Create software that implements the algorithm of randomized roundingfor this task.Note: The solution involves linear programming, since that is neededfor solving the LP relaxation. For this part you may use any availableLP software, but make reference to where it comes from. (There arenumerous freely downloadable versions on the Internet.) The rest ofthe program (other than the LP part) should be your own work. Theprogramming language and operating system are left to your choice.3. Clearly explain how your program works. It is helpful to use flowchartsfor visualizing the explanation.4. Create at least 5 specific examples of the case study task, by specifyingthe number of nodes, and that which nodes are contained in each sub-network, and all other parameters of the task. It is helpful to visuallyrepresent the examples.5. Run your program on all examples.Note: The choice of the examples is not restricted, but follow thesegeneral principles:• Choose a reasonable value for the size (number of nodes, subnet-works). By “reasonable” we mean that it should be large enoughto create nontrivial instances, where the statistical effects (such ascancellation of random errors) already show up. At the same time,the examples should not be excessively large, to avoid unrealisticrunning times.1• Make the examples noticeably different, that is, no two of themshould look “almost the same.”6. Competition. Create some heuristic algorithm for the same problem,and run it on the same examples. Compare the results with the onesobtained above. Can you beat the randomized rounding with yourheuristic?The heuristic can be anything. A simple example is a greedy algorithm:Greedy Algorithm: Select the nodes one by one for upgrade in theorder of increasing cost, starting with the least expensive, until in eachsubnetwork at least half of the nodes are selected for upgrade.Of course, this is a very simple heuristic. If you find a more sophisti-cated one, especially, if you can always beat the randomized roundingwith it, that will be appreciated. Do not shy away from bold ideas, tryto be creative.Clearly describe the principle of your heuristic algorithm. Show throughdiagrams how it compares with Randomized Rounding.Note: If there is anything that is not specified in this project description,that means it is left to your choice.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 rep ort. It should have a professional appearence,scanned handwriting is not acceptable!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. Your submission will be read as a report, butusually we do not run the program. On the other hand, if either there aresigns of cheating, or if you want to dispute the received score, then you willbe asked to demonstrate your program on a computer, show and explain itsdetails.2Notes:• The work should be individual and original. Any form of cheating isa serious violation of University policies and can lead to serious conse-quences.• 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 viewpointof a potential “customer”, assuming the customer considers buyingsuch a software product. How professional and convincing would yourpresentation look for a customer? Imagine yourself in the customer’sshoes. Would you buy the
View Full Document
Unlocking...