Integer Programming

Chapter 7Integer ProgrammingPart 2 Deterministic Decision ModelsLearning ObjectivesTell how integer programming problems differ from general linear programming problems.Explain the difference among pure, mixed, and 0–1 integer programming problems.Formulate and use Excel to solve integer programming problems.Formulate and use Excel to solve 0–1 integer programming problems.Formulate specialized integer programming problems including knapsack, set covering, fixed charge, and facility location problems.After completing this chapter, you should be able to:2Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Types of Integer Programming ProblemsPure-Integer Problemsrequire that all decision variables have integer solutions.Mixed-Integer ProblemsRequire some, but not all, of the decision variables to have integer values in the final solution, whereas others need not have integer values.0–1 Integer ProblemsRequire integer variables to have value of 0 or 1, such as situations in which decision variables are of the yes-no type.3Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 7–1 Graph of an Integer Programming Problem4Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 7-15Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 7-1 (cont’d)6Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7-1 Input and Output Worksheet for the Boat-Manufacturing Example7Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7-2 Solver Parameters Screen for the Boat-Manufacturing Problem8Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–3 Integer Requirement SpecificationExhibit 7–4 Solver Results Screen9Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–4 Solver Results Screen10Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Integer Programming Problems and Sensitivity AnalysisInteger programming problems do not readily lend themselves to sensitivity analysis as only a relatively few of the infinite solution possibilities in a feasible solution space will meet integer requirements.Trial-and-error examination of a range of reasonable alternatives involving completely solving each revised problem is required.11Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Formulating Integer Programming Problems with 0–1 ConstraintsEither-Or Alternativesk-Out-of-n AlternativesIf-Then AlternativesEither-Or ConstraintsVariables That Have Minimum Level Requirements12Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Specialized Integer Programming ProblemsInteger programming problems with 0–1 decision variablesFixed-charge problem: minimize total costsSet covering problem: minimize coverage costsKnapsack problem: capacity-profit maximizationFacility location problem: multiple facility locations with capacity considerationsTraveling salesperson problem: minimize total costs of departing and returning the same location.13Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–5 Worksheet for the 0–1 Integer Programming Set Covering Problem14Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–6 Solver Parameters Screen for the Set Covering Problem15Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–7 Binary Requirement Specification16Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–8 Excel Worksheet for Example 7-7 (Traveling SalespersonProblem)17Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–9 Solver Parameters Screen for the Traveling Salesperson ProblemExhibit 7–10 Specification of the Binary Variables18Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–11 Excel Worksheet for Solved Problem 1, Part a (Shopping MallProblem)19Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–12 Solver Parameters Screen for Solved Problem 1 (Shopping Mall Problem)Exhibit 7–13 Specification of the Binary Variables20Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–14 Excel Worksheet for Solved Problem 1, Part b (Shopping MallProblem)21Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–15 Excel Worksheet for Solved Problem 2 (Cargo Plane Problem)22Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 7–16 Solver Parameters Screen for Solved Problem 2 (Cargo Plane Problem)Exhibit 7–17 Specification of the Integer Variables23Copyright © 2007 The McGraw-Hill Companies. All rights reserved.