ILP Solution TechniquesSlide 2Brute Force MethodsSlide 4Slide 5Brute Force - RoundingSlide 7Slide 8Slide 9Slide 10Cutting plane algorithmPowerPoint PresentationSlide 13Slide 14ILP Solution TechniquesConsider an arbitrary ILP problem:Maximize: cTxj = zSubject to: Axj ≤ bxj ≥ 0Xj is integer j = 1, 2, . . . , nNotice that if we drop (or “relax”) the integrality constraint, we are left with an LP problem. This is called the LP relaxation of the ILP. An important result to notice is every feasible solution of an ILP is also a solution of its LP relaxation. That is,FILP F⊆LP1ILP Solution TechniquesOne might think that since there are fewer solutions for an ILP (finitely many, if the solution set is bounded) than for its relaxation, that it is easier to find a solution for the ILP; this is not the case. In fact, it is in general much more difficult to solve an ILP than to solve an LP of similar size. This is because LP solving algorithms take advantage of the fact that an optimal solution of an LP is a basic solution of the LP and a corner point of the feasible region. The feasible region for an ILP is not continuous, so these methods cannot be applied.2Brute Force MethodsEnumerationThe number of feasible solutions for an ILP is finite if the feasible region is bounded, so enumeration is a possible approach. In a Binary ILP problem with n variables, there are at most 2n solutions to be considered. Many of these solutions may not be feasible due to constraints, but the important thing to note here is that the number of solutions is exponential, and therefore enumeration may not be a desirable solution for problems with many variables3Brute Force MethodsGraphical ApproachAs with LP problems, if our ILP has only two variables, a graphical approach can be used to obtain the optimal solution to the problem.4Brute Force MethodsRoundingAnother natural thought is to run the simplex method on the LP relaxation of an ILP and then round the solution to an integer solution. First note that the nearest integer solution may not be in the feasible region, as in Figure 1 ([1]). Another method worth considering is rounding to the nearest feasible solution, but Figure 2 ([1])shows that this may not find the optimal solution for the ILP.5Brute Force - Rounding6Consider the following all-integer linear program: Max 3x1 + 2x2 s.t. 3x1 + x2 < 9 x1 + 3x2 < 7 -x1 + x2 < 1 x1, x2 > 0 and integerBrute Force - Rounding7LP RelaxationSolving the problem as a linear program ignoring the integer constraints, the optimal solution to the linear program gives fractional values for both x1 and x2. The optimal solution to the linear program is: x1 = 2.5, x2 = 1.5,Max 3x1 + 2x2 = 10.5If we round up the fractional solution (x1 = 2.5, x2 = 1.5) to the LP relaxation problem, we get x1 = 3 and x2 = 2. By checking the constraints, we see that this point lies outside the feasible region, making this solution infeasible.Brute Force - Rounding8Rounding DownBy rounding the optimal solution down to x1 = 2, x2 = 1, we see that this solution indeed is an integer solution within the feasible region, and substituting in the objective function, it gives 3x1 + 2x2 = 8.We have found a feasible all-integer solution, but have we found the OPTIMAL all-integer solution?---------------------The answer is NO! The optimal solution is x1 = 3 and x2 = 0 giving 3x1 + 2x2 = 9, as evidenced in the next slide.Brute Force - Rounding9Complete Enumeration of Feasible ILP SolutionsThere are eight feasible integer solutions to this problem: x1 x2 3x1 + 2x2 1. 0 0 0 2. 1 0 3 3. 2 0 6 4. 3 0 9 optimal solution 5. 0 1 2 6. 1 1 5 7. 2 1 8 8. 1 2 7ILP Solution TechniquesTo provide at least an idea how certain methods work we outline a few principles in the subsequent notes.Some general methods that we outline are:Cutting plane algorithmRandomized roundingBranch and boundBranch and cutDynamic programmingConstraint aggregationHeuristic search and optimization techniques10Cutting plane algorithmConsider an arbitrary ILP problem:Maximize: cTxj = zSubject to: Axj ≤ bxj ≥ 0Xj is integer j = 1, 2, . . . , nThe idea of cutting plane is as follows:Solve the problem by relaxing the integer constraint. This makes the problem a simple LP and can be solved.Let the solution be x0.Then any integer vector in the feasible solution o LP satisfies the equation:cx <= ⌊cx0⌋This is true as x0 is an optimal (maximum) solution of lp, socx < cx0for any fesible vector. Taking the integer part of the RHS cannot destroy the relationship for integer feasible vectors, since for them the LHS is already an integer.11Let us add the inequality cx ≤ ⌊cx0⌋ to the original system.(Note ⌊cx0⌋ is a numerical constant, since x0 is already known, it is not a variable). Then we have a new extended system:Maximize: cx = zSubject to: Ax ≤ bcx ≤ ⌊cx0⌋x ≥ 0The new inequality cuts down some part of the polyhedron, but guaranteed to keep the integer vectors.Then we repeat the procedure to cut down more non-integer vectors. The number of constraints keeps increasing. The iterations can be very large. But we are guaranteed to reach a result.12Consider the following example. Figure a shows a convex region of feasible solutions defined by several constraints. The grid indicates where inside the polygon the feasible integer solutions lie. The dot represents the optimal solution (for the linear programming problem) gained from maximizing x1 + x2. Note that although it is not an integer solution it is the upper bound for an optimum one.13If we could shave off some of the area, which contains noninteger solutions, we could possibly find an optimal integer solution. Examine the vertical line through x1 = 3 in figure a. Cutting the polygon on this line will not destroy any feasible integer solutions to the problem. In figure b we have done this and have a new polygon.The line we used to shave off part of the polygon is called a cut or a cutting plane since it pares off some of the noninteger area we do not care about. And, to do the carving, all we need do is to introduce this cut as an additional
View Full Document
Unlocking...