Example 2: Fixed Charge ProblemA telecom company wants to offer new services to its customers. Each servicecan be offered in different amounts (e.g., with different bandwidth). The goalis to decide how much of each service is to be offered to maximize the totalprofit, such that the total cost remains within a given budget.The following information is available to formulate the problem:• There are N potential services.• If service i is offered, then it incurs a cost of ciper unit amount ofservice, plus a fixed charge ki, which is independent of the amount.• Service i brings a profit of piper unit amount of offered service.• The total available budget is C.To formulate a mathematical program, let us introduce variables:xi= the amount of service i offeredNote that xiis a continuous variable. To handle the fixed charge we alsointroduce indicator variables for the services, to indicate which ones are ac-tually offered:yi=1 if xi> 00 if xi= 0How much is the cost of service i? The proportional cost is clearly cixi. Itwould be wrong, however, to say that the cost with fixed charge is cixi+ ki,since kiis incurred only if xi> 0. Thus, we have to distinguish the caseswhen xi> 0 and xi= 0. This is why we need the yivariables. Thus, thecorrect expression is cixi+ kiyiand the total cost is:NXi=1(cixi+ kiyi).The total profit is:NXi=1pixi.The complete formulation then can be expressed asmax Z =NXi=1pixiSubject toNXi=1(cixi+ kiyi) ≤ Cxi≥ 0, i = 1, . . . , Nyi∈ {0, 1}, i = 1, . . . , Nyi=1 if xi> 00 if xi= 0This is a mixed integer program, since some of the variables are continuous.On the other hand, this formulation is not linear, since the last constraint(the one that enforces the relationship between yiand xi) is not linear. Oftenit is desirable, however, to have a linear formulation which is useful when wewant to use commercial ILP software.Exercises1. Replace the last constraint with a linear formulation.Solution:Observe that the constraintNXi=1(cixi+ kiyi) ≤ Cimplies that cixi≤ C must hold for every x. Therefore, if we intro duce anew constant value byM = maxiCcithen xi≤ M holds for every xi. Then we may replace the nonlinear constraintby the following linear one:yi≥1Mxi.Why does the new (linear) formulation remains equivalent with the originalone? If xi> 0, then 0 <1Mxi≤ 1, so then yi≥1Mxiforces yi= 1. Thatis exactly what we want if xi> 0. If xi= 0, then, according to the newformulation, yican be both 0 or 1. In this case, however, whenever it is 1,changing it to 0 does not cause any new constraint violation and it also doesnot change the the objective function. Therefore, the new formulation servesthe purpose just as well as the original one, it does not change the result.It is, however, linear, which is useful when we want to use commercial ILPsoftware.2. What will be the optimal solution, if the company decides to offer onlya single service? (But we do not know in advance, which one will be theoffered service.)Solution:Let i be the service that the company offers. Then the total profit will bepixi, as for all j 6= i we have xj= 0. For any given i, the profit will bemaximum, if xiis as large as possible. Since there is no other service in theconsidered case, therefore, service i will use the entire available budget C.This meanscixi+ ki= C(Since obviously xi> 0 in this case, therefore, the fixed charge will be there.)From this we getxi=C − kiciand the profit will bepixi=pi(C − ki)ci.How do we know the value of i? We simply have to check which i makes theexpressionpi(C − ki)cithe largest. (Since the expression contains only known constants, we caneasily check which i makes it the largest.)3*. Show that the special case discussed in 2 is not as special as it looks:even in the general case the optimum is always attained by a solution inwhich only one xidiffers from 0. Using this, devise an algorithm that solvesthe problem optimally in the general case without ILP. This gives a clevershortcut, using the special features of the problem, making the task efficientlysolvable even in the general
View Full Document
Unlocking...