TOPIC 4: OPTIMIZATION MODELS
LAN JIANG
MIS 665 Prescriptive Analytics and Advanced Topics
Chapter 14 Optimization Models
Business Analytics
Data Analysis and Decision
Making (7e)
S. Christian Albright
Wayne L. Winston
© 2020 Cengage. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a license distributed with a certain product or service or
otherwise on a password-protected website or school-approved learning management system for classroom use.
Agenda
• More LP Examples
– 14.3 Blending Models
– 14.6 Financial Models
• Fundamentals of Integer Programming
– 14.2 Employee Scheduling Problems
– 14.7 Integer Optimization Models
• Assignment Overview
– P14_89
– P14_80
• Week 4 Assignment Discussion
BLENDING MODELS (EXAMPLE 14.2)
Blending Models
• In many situations, various inputs must be blended to produce
desired outputs.
• In many of these situations, blending models can be used to
find the optimal combination of outputs as well as the mix of
inputs used to produce desired outputs.
• Examples of blending problems:

Example 14.2: Blending Oil Products
• Objective: To develop an optimization model for finding the
revenue-maximizing plan that meets quality constraints and stays
within limits on crude oil availabilities.
• Solution: Chandler Oil has 5000 barrels of crude oil 1 and 10,000
barrels of crude oil 2 available.
– Chandler sells gasoline and heating oil, which are produced by blending the
two crude oils together.
– Each barrel of crude oil 1 has a quality level of 10, and each barrel of crude
oil 2 has a quality level of 5.
– Gasoline must have an average quality level of at least 8, whereas heating
oil must have an average quality level of at least 6.
– Gasoline sells for $75 per barrel, and heating oil sells for $60 per barrel.
– If any barrels of the crude oils are left over, they can be sold for $65 and $50
per barrel, respectively.
Problem Formulation 1
NONLINEAR INEQUALITY
Problem Formulation 2
Excel Demonstration
• Example14_2_lanDemo.xlsx
14.6 FINANCIAL MODELS (EXAMPLE 14.6)

Example 14.6
• Objective: To develop an optimization model that relates investment decisions to total
ending cash, and to use Solver to find the strategy that maximizes ending cash and
invests no more than a given amount in any one investment.
• Solution: At the beginning of year 1, Barney-Jones Investment Corporation has $100,000
to invest for the next four years. It wants to limit the amount put into any investment to
$75,000.
• There are five possible investments, labeled A through E.
– Investment A: Invest at the beginning of year 1, and for every dollar invested, receive
returns of $0.50 and $1.00 at the beginnings of years 2 and 3.
– Investment B: Invest at the beginning of year 2, receive returns of $0.50 and $1.00 at
the beginnings of years 3 and 4.
– Investment C: Invest at the beginning of year 1, receive return of $1.20 at the
beginning of year 2.
– Investment D: Invest at the beginning of year 4, receive return of $1.90 at the
beginning of year 5.
– Investment E: Invest at the beginning of year 3, receive return of $1.50 at the
beginning of year 4.
Problem Formulation
Excel Demonstration
• Example14_6_lanDemo.xlsx
FUNDAMENTALS OF INTEGER PROGRAMMING
Integer Programming
• An integer programming (IP) in which all variables are required
to be integers is called a pure IP problem.
• An integer programming (IP) in which some of variables are
required to be integers is called a mixed IP problem.
• An IP problem in which all the variables must be 0 or 1 is called
a 0-1 IP or binary IP.
• The linear programming (LP) obtained by omitting all integer
or binary constraints on variables is called LP relaxation of the
IP.
Examples
Reference: Yong Wang (2017) Operations Research 09A: Integer Programming vs Linear Programming Relaxation
https://www.binghamton.edu/centers/seorl/
Fundamental Questions
• Q1: feasible region of IP is (<=, =, >=) the feasible region of LP
relaxation?
• Q2: optimal function value of IP is (<=, =, >=) optimal function
value of LP relaxation? (Max obj)
• Q3: Which is more difficult to solve? The IP or the LP
relaxation?
• Can we use the rounding method of LP relaxation to solve the
IP?
Fundamental Questions
• Q1: feasible region of IP is (<=, =, >=) the feasible region of LP relaxation?
Answer: LP relaxation has greater feasible region since in LP relaxation variables
can take both integers and real numbers
• Q2: optimal function value of IP is (<=, =, >=) optimal function value of LP
relaxation? (Max obj)
Answer: In general, LP relaxation will have a greater optimal function value since it
has a greater feasible region
• Q3: Which is more difficult to solve? The IP or the LP relaxation?
Answer LP is easier to solve since we can use the simplex method to only check
for the extreme points and it will lead us to find the optimal solution whereas in IP
theoretically we need to enumerate all possible combinations of x values in the
feasible region and check for the optimal function value.
• Can we use the rounding method of LP relaxation to solve the IP?
Answer: NO! refer to the example in the next slide!
Solution Algorithms
• An LP with several thousand continuous variables can be solved
with a number of commercial linear programming solvers.
However, an all-integer linear programming problem with less
than 100 variables can be extremely difficult to solve.
• Experienced scientists can help identify the types of integer linear
programs that are easy, or at least reasonable, to solve.
• Commercial computer software packages, such as MPSX-MIP ®,
OSL ®, CPLEX ® and LINDO, have extensive integer programming
capability. Spreadsheet packages, such as Excel, have the
capability for solving smaller integer linear programs.
Reference: Yong Wang (2017) Operations Research 09A: Integer Programming vs Linear Programming Relaxation
https://www.binghamton.edu/centers/seorl/
14.2 EMPLOYEE SCHEDULING MODELS
(EXAMPLE 14.1)

Example 14.1: Employee Scheduling
• Objective: To develop an optimization model that relates five-day shift
schedules to daily numbers of employees available, and to use Solver on
this model to find a schedule that uses the fewest number of employees
and meets all daily workforce requirements.
• Solution: The number of full-time employees required each day is given in
the table at the bottom left.
– Union rules state that each full-time employee must work five
consecutive days and then receive two days off.
– The business wants to meet its daily requirements using only full-time
employees, with the objective of minimizing the number of full-time
employees.
Problem Formulation
Excel Demonstration
• Example14_1_lanDemo.xlsx
Modeling Issues
• The employee scheduling example is called a static scheduling
model because we assume that the business faces the same
situation each week.
– In reality, demands change over time. A dynamic scheduling model is
necessary for such problems.
• A scheduling model for a more complex organization has a
larger number of decision variables, and optimization software
such as Solver will have difficulty finding a solution.
– Heuristic methods have been used to find solutions to these
problems.
• The scheduling model can be expanded to handle part-time
employees, the use of overtime, and alternative objectives
such as maximizing the number of weekend days off.
14.7 INTEGER OPTIMIZATION MODELS
(EXAMPLE 14.8)

Example 14.8
• Objective: To use a binary IP model to find the set of investments that stays
within budget and maximizes total NPV.
• Solution: Tatham Company is considering seven investments.
• The cash required for each investment and the net present value (NPV)
each investment adds to the firm are listed in the table below.
• Partial investments are not allowed.
• The cash available for investment is $15,000,000.
Problem Formulation
Excel Demonstration
• Example14_8_lanDemo.xlsx
CENGAGE HOMEWORK REVIEW
Topic 4: Chapter 14
MC 14.038
MC 14-043
Problem 14-50
Useful Tutorial:
https://college.cengage.com/geyser/albright/winston_9780357109953/video/video.html?as
set=chapter_14_problem_14_50
Hint: Mathematical Formulation
Problem 14-50
Note: Cengage Error, the optimal NPV (215757)
solved by your Excel is the correct one however,
please enter 75757 in Cengage to obtain the full
score!!!
P14.80
Hint: Mathematical Formulation
S14_80_lanDemo.xlsx
Problem 14.86
Hint: Mathematical Formulation
Excel Setup
Problem 14.86
Note: Cengage Error, the optimal NPV
(324,000,000) solved by your Excel is the correct
one however, please enter 324,000 in Cengage to
obtain the full score!!!
GIANT MOTOR COMPANY
Week 4 Case Study
Case 14.1
Hints: Thinking about Math Formulation
• Decision Variables: two binary (if retool Lyra and/or Libra), 15
integer (non-negative) variables
• Constraints:
– Number of Vehicles of each model to be produced should be less
than or equal to the actual demand (with consideration of demand
diversion)
– Number of Vehicles of each model to be produced should be less
than or equal to capacity of each plant
• Objective Function: maximize profit
– Update profit margin based on the decision of retooling
– Update fixed cost based on the decision of retooling
Hints: decision variables
• Two major decisions to make:
– If we want to retool Lyra and/or Libra manufacturing plants
– How many vehicles of each model (Lyra, Libra and Hydra) to be
produced by each of the manufacturing plants next year
Hints: decision variables
• Two major decisions to make:
– If we want to retool Lyra and/or Libra manufacturing plants
– How many vehicles of each model (Lyra, Libra and Hydra) to be
produced by each of the manufacturing plants next year
Talking About Constraints
• Demand: take into consideration of Demand Diversion!
• Based on the decision of retooling the following components
need to be updated:
– Production Capacity
– Fix Cost
– Profit Margin
Mathematical Formulation
This is a Linear Integer
Programming problem (LIP). Use
Simplex method in Excel Solver
Excel: Requiremnts
• Download Case14.1_student.xlsx
• Complete the constraint formula (of demand and capacity) and
objective function cells highlighted in Dark Red
• Setup Solver (define objective function, setup decision variables and
constraints)
• Solve the problem and discuss (in the WORD document) if Excel
provides the optimal solution (why and why not?)
• Rename the Excel file with your first name and submit on Halo. I will
grade your work based on if you correctly calculate the constraints
and objective function and setup the solver with all required items!
Further Thoughts
• For some reasons, current Excel Solver fails to find optimal
solution for this LIP?! Why the solution provided by Excel is not
optimal?
• Review my sample R script (case14_1_lanDemo.R) to see how
to solve exactly the same question in R
• Original problem’s optimal solution solved by R is shown below:
Report: Requirements
• Start with MIS-665-RS-CaseStudy.docx (download it
from Halo→ Class Resource)
• Include the following items in your report:
–Background
–Problem Statement
–Questions
–Solution and Recommendation
• Explicitly state the optimal solution found by the Excel solver.
• Is Excel solution optimal? Why and why not?
• Explicitly state the optimal solution found by R (GIVEN to you in the
previous slide!!!) and discuss the solution and recommendation!
–References
Deliverables
• Upload:
–The completed Excel file
–The completed Word file
• Please rename both of your files with
your FirstName before submission!