Branch and Bound Method of Solving Integer Programming Problems

Chapter 7 SupplementBranch and Bound Method of Solving Integer Programming ProblemsPart 2 Deterministic Decision ModelsLearning ObjectivesUse the branch and bound method to solve integer programming problems.Use the enumeration method to solve 0–1 integer programming problems.After completing this chapter, you should be able to:2Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Integer Programming ProblemsBoundAn upper or lower limit on the value of the objective function at a given stage of the analysis of an integer programming problem.BranchSelection of an integer value of a decision variable to examine for a possible integer solution to a problem.3Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Solving Integer ProgrammingBranch and Bound methodCreates and solves a sequence of subproblems to the original problem that are increasingly more restrictive until an optimal solution is found.Enumeration MethodA method used with 0–1 problems that involves listing every possible outcome in order to identify the optimal solution.4Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Integer Programming ProblemsMixed-Integer ProblemRequires that some, but not all, decision variables have integer values.Pure-Integer Problemrequires that all decision variables have integer values.Mixed-Integer Problemrequires that some, but not all, decision variables have integer values.5Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–1 Graph of an Integer Programming Problem6Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 7S-1 All-Integer Problem7Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–2 The LP Relaxation Solution8Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–3 Node I Summarizes the LP Relaxation SolutionFigure 7S–4 Branching from the First Node9Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–5 Subproblems and Solution Points for Nodes 2 and 310Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–6 Solutions for Nodes 2 and 311Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–7 Subproblem and Solution Point for Node 412Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–8 Solutions for Nodes 4 and 513Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–9 Subproblems and Solutions for the Next Two Nodes14Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–10 Solutions for Nodes 6 and 715Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–11 The LP Relaxation Solution Point16Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–12 Solution at Node 1 for Example 2 and Branches to Nodes 2 and 317Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–13 Subproblems and Solution Points for Nodes 2 and 318Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–14 Solutions for Nodes 2 and 319Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–15 The LP Relaxation Solution Point20Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–16 Node 1 Solution and Branches21Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–17 Subproblems and Solution Points for Nodes 2 and 322Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–18 Solutions for Nodes 2 and 3 (Node 3 Contains the Optimal)23Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–19 Tree Diagram for Example 424Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–20 Tree for Example 525Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7S–21 Node Diagram for Example 7S-626Copyright © 2007 The McGraw-Hill Companies. All rights reserved.