ALGORITHMIC ASPECTS OF TELECOMMUNICATION NETWORKS TE 6385 Project 4 Implementation of Randomized Rounding By, Gurudutt Narasimha Net Id: gxn120830SYNOPSIS: The goal of this project is to implement the heuristic algorithm Randomized Rounding which is presented in the lecture note entitled “A Case Study for the Use of Randomized Rounding" and provide an ILP formulation of the problem. Compare it with a Greedy Heuristic. PROJECT DESCRIPTION Given the location of N nodes in the plane by their coordinates, a network is designed with the following constraints: 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 5. 4. The total cost of the network topology is as low as possible. The total number of nodes N and number of subnets M are taken as an input from the user. Generate a random graph to represent whether a node belongs to a subnet or not. A randomized array is generated for the cost of upgrade of different nodes. Then it relaxes the problem to a Linear Programming problem which is solved by readily available software. Then we use the Randomized Rounding algorithm to get the solution for the original Integer Linear Programming problem. Finally, the solution is compared with a solution obtained by using a Greedy heuristic to show which algorithm gives better performance under various situations.An Evaluation of Randomized Rounding Algorithm Approximation algorithms are algorithms which are used to find approximate solutions to optimization problems. Approximation algorithms are most often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact algorithms solving NP-hard problems, one settles for polynomial time sub-optimal solutions. Unlike heuristics, which usually only find reasonably good solutions reasonably fast, one wants provable solution quality and provable run time bounds. Ideally, the approximation is optimal up to a small constant factor (for instance within 5% of the optimal solution). Approximation algorithms are increasingly being used for problems where exact polynomial-time algorithms are known but are too expensive due to the input size. Randomized Rounding (Raghavan & Tompson 1987) is a widely used approach for designing and analyzing such approximation algorithms. The basic idea is to use the probabilistic method to convert an optimal solution of a relaxation of the problem into an approximately optimal solution to the original problem. ALGORITHMS Greedy Heuristic: Select the nodes one by one for upgrade in the order of increasing cost, starting with the least expensive, until in each subnetwork at least half of the nodes are selected for upgrade. The following formulations give us an ILP problem for the given case study. Let xi represent whether a node is chosen for upgrade or not. Let A be the matrix of all aij values, A = aij Where,The constraint equation making sure at least half of the nodes in a subnet are upgraded is as follows, Where the number of nodes in a subnet is given by, Where si is the size of subnet i. The final ILP formulation with objective function and the constraints is given by: Subject to Randomized Rounding: The randomized rounding technique works the best when the ILP is of combinatorial nature, that is, a 0-1 programming problem. The principle is shown via the following example. Consider the problem max Z = cx subject to Ax = b xi E {0,1} i = 1,….,n Replace the last constraint with 0 ≤ xi ≤1. The new problem is already an LP, called the LP relaxation of the 0-1 program. We can solve the LP relaxation by any LP algorithm, which generally results in variable assignments that are between 0 and 1. The next step is to round the variables to 0/1 values. This could be done deterministically as usual rounding, but then in a pessimistic case too much violation of the constraints can occur.For example, assume the problem contains the following constraint: x1 + x2 + . . . . + x1000 = 510 and the LP solution is x1 = . . . = x1000 = 0:51; which satisfes the constraint. If we round the variables in the usual way, then they all will be rounded to one, so the lefthand-side becomes 1000. One the other hand, we can have much smaller violation of the constraints by rounding randomly, according to the following rule. The randomly rounded value xi of xi will be: This can be easily implemented by drawing a uniformly distributed random number yi E [0; 1] and setting xi = 1 if xi ¸ yi; otherwise xi = 0. The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program. There are 2 kinds of constraints: hard constraints and soft constraints. Hard Constraints: These constraints must be obeyed. For example, they may rep-resent some physical law which is impossible to violate. Soft Constraints: These constraints can possibly be violated if there is no other way to solve the problem, but then we have to pay a penalty, so we would like to minimize the violation. For example, budget constraints often behave this way. Randomized Rounding is an algorithm that is useful for problems with soft constraints, since it may potentially violate the constraints.PSEUDOCODE: Step1: Consider the two major variables i.e the nodes and the subnets as totalnodes and subnets. Step2: Let us now define the number of total nodes and the number of subnetworks. Step3: Generate a random matrix Network that defines which totalnode is present in which subnets. Step4: Define the variables x for each node restricting it between [0,1] Step5: Define the objective function and constraints Step6: Feed the system to a linear programming solver Step7: Round the x values obtained after solving to 0 or 1 Step8: Compute the objective function and this value is the output of randomized rounding procedure Step9: For solving the greedy function, sort the nodes in the order of increasing cost Step10: Pick the least non upgraded node and upgrade it if any of the subnets existing is not yet upgraded Step11: Calculate the objective
View Full Document
Unlocking...