Constraint AggregationIn the constraint aggregation method we replace several constraints by asingle one. Let us show the technique trough the example of the knapsackproblem. The original knapsack problem is formulated as follows.max Z =NXi=1pixiSubject toNXi=1cixi≤ Cxi∈ {0, 1}, i = 1, . . . , NLet us assume now that instead of a single inequality constraint we have two.Assume further that all constants are nonnegative integers. Thus, the taskbecomes this:max Z =NXi=1pixiSubject toNXi=1aixi≤ ANXi=1bixi≤ Bxi∈ {0, 1}, i = 1, . . . , NA possible motivation is, refering to the Capital Budgeting problem, thatthere are two kinds of costs associated with each item, and the budgetsfor the different types come from different sources, so they may have to beobeyed separately. Or, in the knapsack terminology, each item has a size anda weight parameter, and the knapsack can carry only a certain total size anda certain total weight, so we have to satisfy both constraints.Let us first convert the inequality constraints into equations, by introducingslack variables. Let xN +1be the slack variable in the first inquality, andxN +2in the second. Further, let aN +1= 1, bN +1= 0, bN +2= 1. In this waywe can simply include the slack variables in the summation, without extraterms. Moreover, we can observe that the size of the “gap” the slack variablehas to fill can be at most A in the first constraint, and at most B in thesecond.max Z =NXi=1pixiSubject toN +2Xi=1aixi= AN +2Xi=1bixi= Bxi∈ {0, 1}, i = 1, . . . , NxN +1∈ {0, 1, . . . , A}xN +2∈ {0, 1, . . . , B}Now the question is this: can we replace the two equality constraints aboveby a single one, so that this single constraint is equivalent to the joint effectof the two? By equivalence we mean that they generate the same set offeasible solutions.The answer to the above question is yes, even though it may seem counter-intuitive at first. Let us define the parameters of the new constraint byci= ai+ Mbifor every i, andC = A + MBwhere M is a constant that we are going to choose later.It is clear that the two constraintsN +1Xi=1aixi= A (1)N +2Xi=1bixi= B (2)imply the new oneN +2Xi=1(ai+ Mbi)xi= A + MB (3)(taking aN +2= 0), since (3) is just a linear combination of (1) and (2). Thequestion, however, is this: can we choose M such that the implication alsoholds in the opposite direction, that is, such that the aggregated constraint(3) implies (1) and (2)?The answer is yes. To see it, let us rearrange (3) in the following form:N +1Xi=1aixi− A| {z }Y+ MÃN +2Xi=1bixi− B!| {z }Z= 0 (4)Now observe that the value ofY =N +1Xi=1aixi− Amust be at least − A, and cannot be more thanPNi=1ai+ A − A =PNi=1ai.So we have the bound|Y | ≤ A0= max{A,NXi=1ai}.Using Z =PN +2i=1bixi− B, we can rewrite (4) asY + MZ = 0. (5)How can this equality hold? One possibility is that Y = Z = 0. In that case,(1) and (2) are both satisfied, sinceY =N +1Xi=1aixi− A and Z =N +2Xi=1bixi− B.On the other hand, if Z 6= 0, then |Z| ≥ 1, b eing an integer. In this case Ymust make the left hand side 0 in (5). If, however, we choose M = A0+ 1,then it becomes imp ossible, since with this choice we have M|Z| ≥ A0+ 1,and we already know |Y | ≤ A0.Thus, with the choice of M = A0+ 1, we can achieve that whenever theaggregated constraint (3) is satisfiable, both original constraints (1) and (2)will also be satisfiable. Of course, this is only guaranteed when the variablestake their values from the allowed ranges.Remark: We can assume that A <PNi=1ai, since otherwise the originalconstraintPNi=1aixi≤ A would always be satisfied, so we could simply leaveit out. With this assumption the choice for the constant M becomesM = 1
View Full Document
Unlocking...