### Integer Programming - McGraw Hill Higher Education

```Introduction to
Management Science
Stevenson and Ozgur
First Edition
Part 2 Deterministic Decision Models
Chapter 7
Integer Programming
McGraw-Hill/Irwin
Learning Objectives
After completing this chapter, you should be able to:
1. Tell how integer programming problems differ from
general linear programming problems.
2. Explain the difference among pure, mixed, and 0–1
integer programming problems.
3. Formulate and use Excel to solve integer
programming problems.
4. Formulate and use Excel to solve 0–1 integer
programming problems.
5. Formulate specialized integer programming
problems including knapsack, set covering, fixed
charge, and facility location problems.
McGraw-Hill/Irwin 7–2
Types of Integer Programming Problems
• Pure-Integer Problems
–require that all decision variables have integer
solutions.
• Mixed-Integer Problems
–Require 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 Problems
–Require integer variables to have value of 0 or 1,
such as situations in which decision variables are of
the yes-no type.
McGraw-Hill/Irwin 7–3
Figure 7–1
Graph of an Integer Programming Problem
McGraw-Hill/Irwin 7–4
Example 7-1
McGraw-Hill/Irwin 7–5
Example 7-1 (cont’d)
McGraw-Hill/Irwin 7–6
Exhibit 7-1
Input and Output Worksheet for the Boat-Manufacturing Example
McGraw-Hill/Irwin 7–7
Exhibit 7-2
Solver Parameters Screen for the Boat-Manufacturing
Problem
McGraw-Hill/Irwin 7–8
Exhibit 7–3
Integer Requirement Specification
Exhibit 7–4
Solver Results Screen
McGraw-Hill/Irwin 7–9
Exhibit 7–4
Solver Results Screen
McGraw-Hill/Irwin 7–10
Integer Programming Problems and
Sensitivity Analysis
• Integer 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.
McGraw-Hill/Irwin 7–11
Formulating Integer Programming
Problems with 0–1 Constraints
• Either-Or Alternatives
• k-Out-of-n Alternatives
• If-Then Alternatives
• Either-Or Constraints
• Variables That Have Minimum Level
Requirements
McGraw-Hill/Irwin 7–12
Specialized Integer Programming Problems
• Integer programming problems with 0–1
decision variables
–Fixed-charge problem: minimize total costs
–Set covering problem: minimize coverage costs
–Knapsack problem: capacity-profit maximization
–Facility location problem: multiple facility locations with
capacity considerations
–Traveling salesperson problem: minimize total costs of
departing and returning the same location.
McGraw-Hill/Irwin 7–13
Exhibit 7–5
Worksheet for the 0–1 Integer Programming Set Covering
Problem
McGraw-Hill/Irwin 7–14
Exhibit 7–6
Solver Parameters Screen for the Set Covering Problem
McGraw-Hill/Irwin 7–15
Exhibit 7–7
Binary Requirement Specification
McGraw-Hill/Irwin 7–16
Exhibit 7–8
Excel Worksheet for Example 7-7 (Traveling Salesperson
Problem)
McGraw-Hill/Irwin 7–17
Exhibit 7–9
Solver Parameters Screen for the Traveling Salesperson
Problem
Exhibit 7–10
Specification of the Binary Variables
McGraw-Hill/Irwin 7–18
Exhibit 7–11
Excel Worksheet for Solved Problem 1, Part a (Shopping Mall
Problem)
McGraw-Hill/Irwin 7–19
Exhibit 7–12
Solver Parameters Screen for Solved Problem 1 (Shopping
Mall Problem)
Exhibit 7–13
Specification of the Binary Variables
McGraw-Hill/Irwin 7–20
Exhibit 7–14
Excel Worksheet for Solved Problem 1, Part b (Shopping Mall
Problem)
McGraw-Hill/Irwin 7–21
Exhibit 7–15
Excel Worksheet for Solved Problem 2 (Cargo Plane Problem)