Example 1: Capital BudgetingA telecommunication company wants to build switching centers at certaingiven sites. The sites should be selected so that the total profit is maximized,under the constraint that the total cost remains within the available budget.The following information is available to formulate the problem:• There are N available sites.• The cost of building a switching center at site i is ci.• If a center is built at site i, then it generates a profit pi(say, per year).• The total available budget that can be used for building the centers isC.• Objective: select which of the N sites will be used for building switchingcenters, so that the total profit is maximized, while keeping the totalcost within the budget. (Any number of sites can be selected out ofthe N.)Let us formulate the problem as a mathematical program!Variables: one variable, xi, for each site i. The meaning of xiis:xi=1 if site i is selected as a center0 if site i is not selected as a centerIn other words, xiis the indicator variable of the fact that site i is selected/notselected as a center.Such indicator variables are frequently used in network planning formulationswhen one has to express yes/no choices.Objective functionGoal: maximize the total profit.How can we express it? The profit from site i is piif the site is selected as acenter, otherwise 0. The definition of xisuggests that this can be convenientlyexpressed as pixi. Then the total profit is:NXi=1pixi.Thus, the objective function is:max Z =NXi=1pixi.Constraints:The total cost cannot be more than the budget C:NXi=1cixi≤ CThe variables can only take 0-1 values:xi∈ {0, 1}, i = 1, . . . , N.Collecting the parts, the complete formulation is this:max Z =NXi=1pixiSubject toNXi=1cixi≤ Cxi∈ {0, 1}, i = 1, . . . , NComment: Though we have not mentioned it, one can easily recognize thatthis problem is exactly identical to the well known Knapsack Problem.How can we find a solution?It is well known from the study of algorithms that the Knapsack Problem isNP-complete, so we cannot reasonably hope to find the exact optimum for alarge problem via an efficient algorithm. A good approximation, however, isstill possible:Principle of the heuristics: Sort the sites according to their profit/cost ratio.(Clearly, a higher profit/cost ratio is more preferable.) Select the sites oneby one in this order, thus, always trying the most preferable first, among theyet unselected ones. (Preference = profit/cost). If the considered site stillfits in the remaining budget, then select it, otherwise proceed to the nextone in the preference order.This is a natural variant of the so called Greedy Algorithm.Trying the sites according to the profit/cost preference order is so natural,that one may wonder: why it does not guarantee an optimum solution?Exercise (to test your understanding for yourself): Find a specific examplewhen the above greedy algorithm does not yield the optimum.A simple example is on the next page, but try to find one yourself, beforeproceeding to the next page.Solution to the exerciseConsider the following data:p1= 90, c1= 10p2= 20, c2= 2p3= 8, c3= 1Budget: C = 11Then the profit/cost ratios are:p1/c1= 9, p2/c2= 10, p3/c3= 8.The Greedy Algorithm would select i = 2 first, since p2/c2is the largest.This choice uses c2= 2 units from the budget. The next largest ratio isp1/c1, but c1= 10 already does not fit in the remaining budget of 11 −2 = 9.So the algorithm proceeds to i = 3, which still fits in the budget.Thus, the Greedy Algorithm selects sites 2 and 3, achieving a total profitof 20 + 8 = 28. On the other hand, if we select sites 1 and 3, then we canachieve a profit of 90 + 8 = 98, while the cost still fits in the budget.CommentAs we have seen, the Greedy Algorithm does not necessarily find the optimumfor this problem. A natural question is:How far is it from the optimum? In other words, can we prove some perfor-mance guarantee for the greedy solution?The answer is yes. We present the preformance guarantee below.Theorem:Let Toptbe the optimum solution to the considered problem, that is, the max-imum achievable total profit under the budget constraints. Let Tgreedybe theprofit achieved by the Greedy Algorithm. Further, denote by pmaxthe largestprofit coefficient, that is, pmax= maxipi. ThenTgreedy≥ Topt− pmaxalways holds.Proof: See the Appendix at the end of this note. The proof is included onlyfor showing how can one possibly analyze the result of the greedy heuristicin this situation, you do not have to learn the proof details.Exercises1. Assume that we execute the Greedy Algorithm on a specific CapitalBudgeting problem and we find that Tgreedy= 1000 (in some appropriateunits). Further, we also know that the largest profit coefficient is pmax= 5.Give an estimate on the optimum profit Topt.SolutionFrom the preceding Theorem we know thatTgreedy≥ Topt− pmaxalways holds. Rearranging, we getTgreedyTopt≥ 1 −pmaxTopt.Since Topt≥ Tgreedyby definition, therefore, if we replace Toptby Tgreedyonthe righthand-side, then pmax/Toptcan only grow. This means, we can onlysubtract more from 1, so1 −pmaxTopt≥ 1 −pmaxTgreedymust hold. As a result, we getTgreedyTopt≥ 1 −pmaxTgreedy.Substituting the given numerical values on the righthand-side yieldsTgreedyTopt≥ 1 −51000= 0.995 = 99.5%.This means, in this case we can argue that the Greedy Algorithm will give aresult that is within 0.5% of the optimum, even if we do not know what theoptimum is.Rearranging the above formula, and using Topt≥ Tgreedy= 1000, we get1000 ≤ Topt≤10000.995= 1005.2512. In the example which showed that the Greedy Algorithm can produce anon-optimal solution, the greedy solution was less than half of the optimum.Can we modify the Greedy Algorithm such that it always guarantees at leasthalf of the optimum profit?SolutionTo exlude trivial cases, let us assume that ci≤ C for every i. (If ci> C forsome i, then it can be excluded, since it never fits in the budget).If Topt≥ 2pmax, then we haveTgreedy≥ Topt− pmax≥Topt2,since the first inequality follows from the Theorem and the second inequality,after rearranging, is equivalent to Topt≥ 2pmax.Thus, if Topt≥ 2pmax, then the greedy solution satisfies the requirement.What if Topt< 2pmax? This means pmax> Topt/2, so then simply selectingthe site with maximum profit already achieves more than half of Topt. Letus call this latter choice 1-site heuristic. Clearly, the profit achieved by
View Full Document
Unlocking...