ILP Exercises 1.SolutionFirst we draw a map of the situation:zzzzzzzz123'&$%AB456'&$%SSSSSSSSSSSSSSSSSSSA potential layout of the transcontinental link.Let us now formulate the constraints.• Exactly one of the West coast cities is connected to one of the hubs:3Xi=1BXj=Axij= 1• Similarly, exactly one of the East coast cities is connected to one of thehubs:6Xi=4BXj=Axij= 1• The same hub is connected to both coasts:3Xi=1xiA=6Xi=4xiANote that this already implies the same equation for hub B.• The variables can only take 0-1 values:xij∈ {0, 1}, i = 1, . . . , 6; j = A, BThe objective function is the total cost:6Xi=1BXj=AcijxijThus, the entire mathematical program will be an ILP with 0-1 valued vari-ables:min Z =6Xi=1BXj=AcijxijSubject to:3Xi=1BXj=Axij= 16Xi=4BXj=Axij= 13Xi=1xiA=6Xi=4xiA3Xi=1xiB=6Xi=4xiBxij∈ {0, 1}, i = 1, . . . , 6; j = A, B2. Assume that in an integer linear programming problem we have n vari-ables. Each variable can only take the value 0 or 1. Express each of theconditions a.), b.), c.) given below, such that you can only use linear equa-tions or inequalities, nothing else.a) At least one variable must take the value 0.Answer:This means, they cannot be all 1, so their sum is at nost n − 1:x1+ x2+ . . . + xn≤ n − 1orx1+ x2+ . . . + xn< nb) At most one variable can take the value 0.Answer:This means, at least n − 1 of them is 1, so their sum is at least n − 1:x1+ x2+ . . . + xn≥ n − 1c) Either all variables are 0, or none of them.Answer:This means, they all must be equal:x1= x2= . . . = xnor, expressed via separate equations:x1= x2x2= x3...xn−1= xn3. Let x, y, z be 0-1 valued variables. Express the following constraint vialinear inequalities:z = xySolutionIf any of x, y is 0, then z must be 0, too. This can be expressed by twoinequalities:z ≤ xz ≤ yOn the other hand, if x, y are both 1, then we have to force z to be 1. It canbe done byz ≥ x + y − 1Note that if at least one of x, y is 0, then the right-hand side is ≤ 0, so thennothing is forced on z.Thus, the systemz ≤ xz ≤ yz ≥ x + y − 1is equivalent to the nonlinear constraintz = xyfor 0-1 valued variables. Note that the restriction x, y, z ∈ {0, 1} is essentialhere, without it the equivalence would not hold.4. Let us generalize the previous exercise to a longer product! Let x1, . . . , xnand z be 0-1 valued variables. Express the following constraint via linearinequalities:z = x1· . . . · xnSolutionSimilarly to the previous exercise, it is easy to check that the following systemof linear inequalities provides an equivalent expression for the case whenz, x1, . . . , xn∈ {0, 1}:z ≤ x1...z ≤ xnz ≥ x1+ . . . + xn− n +
View Full Document
Unlocking...