Integer Programming and

Nonlinear Programming
Introduction
• There are other mathematical programming models that
can be used when the assumptions of LP are not met
• A large number of business problems require variables
have integer values
• Many business problems have multiple objectives
• Goal programming permits multiple objectives
• Nonlinear programming allows objectives and constraints
to be nonlinear
Max profit = 25X1 − 0.4X12 + 30X2 − 0.5X22
Integer Programming (1 of 2)
• An integer programming model is one where one or more
of the decision variables has to take on an integer value in
the final solution
• Three types of integer programming problems
1. Pure integer programming – all variables have integer
values
2. Mixed-integer programming – some but not all of the
variables will have integer values
3. Zero-one integer programming – special cases in
which all the decision variables must have integer
solution values of 0 or 1
Integer Programming (2 of 2)

• Solving an integer programming

problem is much more difficult than
solving an LP problem
• Solution time required may be
excessive
Electric Company Example of Integer
Programming (1 of 6)
• Company produces two products, old-fashioned
chandeliers and ceiling fans
• Both require a two-step production process involving wiring
and assembly
– It takes about 2 hours to wire each chandelier and 3
hours to wire a ceiling fan
– Final assembly of the chandeliers and fans requires 6
and 5 hours, respectively
– Only 12 hours of wiring time and 30 hours of assembly
time are available
– Each chandelier produced nets the firm $7 and each
fan $6
Electric Company Example of Integer
Programming (2 of 6)
Production mix LP formulation

Maximize profit = $7X1 +$6X2

subject to 2X1 + 3X2 ≤ 12 (wiring hours)

6X1 + 5X2 ≤ 30 (assembly hours)

X1, X2 ≥ 0

where
X1 = number of chandeliers produced

X2 = number of ceiling fans produced

Electric Company Example of Integer
Programming (3 of 6)
Electric Company Example of Integer
Programming (4 of 6)
• Production planner recognizes this is an integer problem
– First attempt at solving it is to round the values to
X1 = 4 and X2 = 2
– However, this is not feasible
– Rounding X2 down to 1 gives a feasible solution, but it
may not be optimal
• This could be solved using the enumeration method
– Generally not possible for large problems
Electric Company Example of Integer
Programming (5 of 6)
Integer CHANDELIERS (X1) CEILING FANS (X2) PROFIT ($7X1 + $6X2)
solutions to the 0 0 $0
1 0 7
Electric
2 0 14
Company 3 0 21
Problem 4 0 28
Optimal solution to
5 0 35
integer
0 1 6 programming
problem
1 1 13
2 1 20
3 1 27
4 1 34 Solution if
0 2 12 rounding is used

1 2 19
2 2 26
3 2 33
0 3 18
1 3 25
0 4 24
Electric Company Example of Integer
Programming (6 of 6)

• The optimal integer solution is less

than the optimal LP solution of
$35.25
• An integer solution can never be
better than the LP solution and is
usually a lesser value
Using Software
Add constraint for each decision variable, restricting each
one to an integer
Mixed-Integer Programming Problem
Example (1 of 3)
• Many situations in which only some of the variables are
restricted to integers
– ABC Chemical Company produces two industrial
chemicals
 Xyline must be produced in 50-pound bags
 Hexall is sold by the pound and can be produced in
any quantity
 Both xyline and hexall are composed of three
ingredients – A, B, and C
 Chemical company sells xyline for $85 a bag and
hexall for $1.50 per pound
Mixed-Integer Programming Problem
Example (2 of 3)

AMOUNT PER 50- AMOUNT PER AMOUNT OF

POUND BAG OF POUND OF HEXALL INGREDIENTS
INGREDIENTS XYLINE (LB) (LB) AVAILABLE
A 30 0.5 2,000 lb

B 18 0.4 800 lb

C 2 0.1 200 lb

• Objective is to maximize profit

Mixed-Integer Programming Problem
Example (3 of 3)
Let X = number of 50-pound bags of xyline
Let Y = number of pounds of hexall
A mixed-integer programming problem as Y is not
required to be an integer

Maximize profit = $85X + $1.50Y Blank

Blank

subject to 30X + 0.5Y ≤ 2,000

Blank 18X + 0.4Y ≤ 800

Blank 2X + 0.1Y ≤ 200
Blank Blank X, Y ≥ 0 and X integer
Modeling With 0-1 (Binary) Variables
• Demonstrate how 0-1 variables can be used to model
several diverse situations
• Typically a 0-1 variable is assigned a value of 0 if a certain
condition is not met and a 1 if the condition is met
• This is also called a binary variable
Capital Budgeting Example (1 of 3)
• Common capital budgeting problem – select from a set of
possible projects when budget limitations make it
impossible to select them all
– A 0-1 variable is defined for each project
• XYZ Chemical Company is considering three possible
improvement projects for its plant
– A new catalytic converter
– A new software program for controlling operations
– Expanding the storage warehouse
• It cannot do them all
Capital Budgeting Example (2 of 3)
• Objective is to maximize net present value of projects
undertaken
subject to Total funds used in year 1 ≤ $20,000
Total funds used in year 2 ≤ $16,000

PROJECT NET PRESENT VALUE YEAR 1 YEAR 2

Catalytic Converter $25,000

$8,000 $7,000
Software $18,000
$6,000 $4,000
Warehouse expansion $32,000
$12,000 $8,000
Available funds Blank
$20,000 $16,000
Capital Budgeting Example (3 of 3)
Decision variables
1 if catalytic converter project is funded
X1  
0 otherwise
1 if software project is funded
X2  
0 otherwise
1 if warehouse expansion project is funded
X3  
0 otherwise
Blank

Formulation Blank Blank Blank Blank

Blank

Maximize NPV = 25,000X1 + 18,000X2 + 32,000X3 Blank

subject to 8,000X1 + 6,000X2 + 12,000X3 ≤ 20,000
Blank 7,000X1 + 4,000X2 + 8,000X3 ≤ 16,000
Blank Blank Blank X1, X2, X3 = 0 or 1
Using Software (2 of 3)

Optimal Solution
X1 = 1, X2 = 0, X3 = 1
Fund the catalytic converter and
warehouse projects but not the
software project
NPV = $57,000
Limiting the Number of Alternatives
Selected
• One common use of 0-1 variables involves limiting the
number of projects or items that are selected from a group
– Suppose XYZ Chemical is required to select no more
than two of the three projects regardless of the funds
available
– This would require adding a constraint
X1 + X2 + X3 ≤ 2
– If they had to fund exactly two projects the constraint
would be
X1 + X2 + X3 = 2
Dependent Selections
• At times the selection of one project depends on the
selection of another project
– Suppose XYZ catalytic converter could only be
purchased if the software was purchased
– The following constraint would force this to occur
X1 ≤ X2 or X1 − X2 ≤ 0
– If we wished for the catalytic converter and software
projects to either both be selected or both not be
selected, the constraint would be
X1 = X2 or X1 − X2 = 0
Nonlinear Programming
• The methods seen so far have assumed that the objective
function and constraints are linear
• However, there are many nonlinear relationships in the real
world that would require the objective function and/or
constraint equations to be nonlinear
• Computational procedures for nonlinear programming
(NLP) may only provide a local optimum solution rather
than a global optimum
Nonlinear Objective Function and Linear
Constraints (1 of 3)
• An Appliance Company sells two models of toaster ovens,
the Microtoaster (X1) and the Self-Clean Toaster Oven (X2)
• They earn a profit of $28 for each Microtoaster no matter
the number of units sold
• For the Self-Clean oven, profits increase as more units are
sold due to a fixed overhead
– The profit function for the Self-Clean oven
21X2 + 0.25X22
Nonlinear Objective Function and Linear
Constraints (2 of 3)
• The objective function is nonlinear and there are two linear
constraints on production capacity and sales time available

Maximize profit = 28X1 + 21X2 + 0.25X22

subject to

X1 + X2 ≤ 1,000 (units of production

capacity)
0.5X1 + 0.4X2 ≤ 500 (hours of sales time
available)
X1, X2 ≥ 0
Nonlinear Objective Function and Linear
Constraints (3 of 3)

When an objective function contains a

squared term and the problem
constraints are linear, it is called a
quadratic programming problem
Using Software (1 of 2)
Using Software (2 of 2)

Blank

Solver Parameter Inputs and Selections Key Formulas

Set Objective: E8 B
By Changing cells: B4:C4 l
a
To: Max n
Subject to the Constraints: k
E11:E12 <= G11:G12
Solving Method: GRG Nonlinear
 Make Variables Non-Negative
Blank

Blank Blank
Both Nonlinear Objective Function and
Nonlinear Constraints (1 of 2)
• The annual profit at a medium-sized (200-400 beds)
Hospicare Corporation hospital depends on
– The number of medical patients admitted (X1)
– The number of surgical patients admitted (X2)
• The objective function for the hospital is nonlinear
• There are three constraints, two of which are nonlinear
– Nursing capacity - nonlinear
– X-ray capacity - nonlinear
– Marketing budget required
Both Nonlinear Objective Function and
Nonlinear Constraints (2 of 2)
• Objective function and constraint equations

Maximize profit = $13X1 + $6X1X2 + $5X2 + $1÷X2

subject to

2X12 + 4X2 ≤ 90 (nursing capacity in thousands of

labor-days)

X1 + X23 ≤ 75 (x-ray capacity in thousands)

8X1 − 2X2 ≤ 61 (marketing budget required in

thousands of $)
Using Software (1 of 2)
Using Software (2 of 2)

Solver Parameter Inputs and Selections Key Formulas

Set Objective: H8
By Changing cells: B4:C4
To: Max Copy H8 to H11:H13
Subject to the Constraints:
H11:H13 <= J11:J13
Solving Method: GRG Nonlinear
 Make Variables Non-Negative
Linear Objective Function and Nonlinear
Constraints (1 of 2)
• Thermlock Corp. produces massive rubber washers and
gaskets like the type used to seal joints on the NASA
Space Shuttles
– It combines two ingredients, rubber (X1) and oil (X2)
– The cost of the industrial quality rubber is $5 per pound
and the cost of high viscosity oil is $7 per pound
– Two of the three constraints are nonlinear
Linear Objective Function and Nonlinear
Constraints (2 of 2)
• Objective function and constraints

Minimize costs = $5X1 + $7X2

subject to

3X1 + 0.25X12 + 4X2 + 0.3X22 ≥ 125

(hardness constraint)
13X1 + X13 ≥ 80 (tensile strength)
0.7X1 + X2 ≥ 17 (elasticity)
Using Software (1 of 2)
Using Software (2 of 2)

Solver Parameter Inputs and Selections Key Formulas

Set Objective: D5
By Changing cells: B4:C4
To: Min
Subject to the Constraints:
G10:G12 >= I10:I12 Copy G10 to G11:G12
Solving Method: GRG Nonlinear
 Make Variables Non-Negative