Integer Programming_2 管理科学英文版教学课件.pptVIP

Lecture Lecture Management Science:Operations Research(OR) Chapter 4 Integer Programming (4.3) * * Lecture 4.3 Solution Methods for IP Cutting plane methods Branch-and-Bound Methods Heuristic Methods * Lecture * 4.3.2 Branch-and-Bound Methods These methods are very flexible are applicable to AILP MILPs. Idea: Starting with the LP relaxation, subdivide the problem into subproblems, whose union includes all integer solutions that are not worse than the best known integer solution. * Lecture * For instance, if presently y3 = 5.2, we subdivide the problem (the “parent”) by adding the constraint y3 ≤ 5 y3 ≥ 6, respectively (thus creating “children”). * Lecture * Example: P: Max z = 400x1 + 900x2 s.t. 9x1 + 7x2 ? 56 7x1 + 20x2 ? 70 x1, x2 ? ?0. * Lecture * * Lecture * Example: Max z = 5y1 + 9y2 s.t. 5y1 + 11y2 ? 94 Constraint I 10y1 + 6y2 ? 87 Constraint II y1 , y2 ≥ 0 and integer. * Lecture * * Lecture * Solution Tree * Lecture * Each node of the solution tree represents one linear program. ? The constraints at a node are all original constraints plus all additional constraints between the root of the tree the node in question. ? As we move down the tree, the problems get to be more constrained thus their objective values cannot improve. * Lecture * Alternative Solution * Lecture * * * * * * * * * * * * * * * * * * * * * * * Lecture Lecture * * * * * * * * * * * * * * * * * * * * * *