Decision Analysis

Lecture 3 Integer Linear Programming
• Types of Integer Linear Programming Models

• Graphical and Computer Solutions for an All-Integer Linear
Program
• Applications Involving 0-1 Variables
• Modeling Flexibility Provided by 0-1 Variables
• An LP in which all the variables are restricted to be integers is

called an all-integer linear program (ILP).
• The LP that results from dropping the integer requirements is
called the LP Relaxation of the ILP.
• If only a subset of the variables are restricted to be integers, the
problem is called a mixed-integer linear program (MILP).
• Binary variables are variables whose values are restricted to be
0 or 1. If all variables are restricted to be 0 or 1, the problem is
called a 0-1 or binary integer linear program.
Example (Sect 7.2)
Eastborne Realty has $2m available for the purchase of new rental
property. The alternatives are townhouses and apartment buildings. Each
townhouse cost $282,000, and five are available. Each apartment building
cost $400,000 and there is no limit in supply.
Eastborne’s property manager can devote up to 140 hrs per month to
these new properties. Each townhouse requires 4 hrs per month whereas
each apartment building 40 hrs per month. The net annual cash flow, after
deducting expenses, is $10,000 per townhouse and $15,000 per
apartment. Eastborne’s owner would like to determine the number of
townhouses and the number of apartment buildings to purchase to
maximise annual cash flow.
Solution: First, construct the LP model:
Let T = number of townhouse
A = number of apartment buildings.
Example (Sect 7.2)
LP model:
The objective function for cash flow is (in $1000) is:
s.t.
Graphical Solution of the LP Relaxation
If we relax the non-negative constraints to T,A ≥0, we will have the

optimal solutions T=2.479, A= 3.252, with Max cash flow = 10(2.479) +
15(3.252) = $73.574K. Is that valid?
Example (Sect 7.2)
If we round to the nearest number, T=2.479≈ 2., A= 3.252 ≈3,
a. Is this point still in the feasible region?
b. The Max cash flow = 10(2) + 15(3) = $65K. Is this the max cash flow
with integer solution?
Lets check by graphical means:
The optimal solution is

T=
A=
Max cash flow =

10( ) + 15 ( )=$
Hence, we cannot use rounding off solution for non integer LP solutions.
Formulation and solution of Integer LP model
Eastborne’s Max
of cash flow
problem
The MS Solution tells us that:

Max cash flow =
happens when _____ townhouses and
_________ apartment buildings are
purchased.
For C1, ___________ are unused.
___________________ are used.
For C2: ________ hrs are still available.

_______________ hrs are used.
6
For C3. __ townhouses are not purchased.
Applications involving 0-1 variables
Section 7.3 Capital Budgeting
In a capital budget problem, the company’s objective is to maximise the

net present value (NPV) of the projects.
The LP model (with dollars in thousands) is:
Part of the MS solution is:
Interpretation:
The maximum NPV is ___________.
The company shall fund the _____________, _____________ & _________.
The values of slacks shows that the company will have remaining $5K in Yr1,
$15K in Yr 2 and $11K in year 4. Check the available fund again.
Which year can Research project be funded? _____________
Which year cannot? What is the shortage? ________________________
Fixed Cost
In many cases, the cost of production has two components: a setup cost,
which is a fixed cost, and a variable cost which is directly related to the
production quantity. The use of 1-0 variables makes including the setup
cost possible in a model for a production application.
Example (Pg 328): RMC is a manufacturer. Three raw materials are
used to produce three products: A fuel additive, a solvent base, and a
carpet cleaning fluid.
10
Fixed Cost Example using 1-0 Variable
Without considering fixed cost, a LP model would be:
The solution
from MS is:
The maximum profit is $1850, achieved by an optimal solution of 27.5 tons

of fuel additive, 0 tons of solvent base and 15 tons of carpet cleaning fluid.
For S to be part of the solution, its profit must be:___________________
11
If there are fixed costs in the production setup and maximum
production quantity constraints are imposed as follow:
Using these variables, the setup cost is:
The net profit: Gross profit – total set up cost=

Production capacity constraint for fuel additive:
Production capacity constraint for solvent:
Production capacity constraint for carpet cleaning product:
The complete LP model with setup cost:
The MS solution is shown:

Max profit = $1350, optimal solution is 25 tons of fuel additive and 20 tons of
solvent base. No carpet cleaning fluid produce. Total set up cost=
The dropping of carpet cleaning compare to earlier solution (w/o setup cost) is
because ___________________
Modeling Flexibility Provided by 0-1 Variables
• When xi and xj represent binary variables designating whether
projects i and j have been completed, the following special
constraints may be formulated:
– At most k out of n projects will be completed: xj < k
j
E.g Multiple choice question, choose 1 out of 5, then k=1
x1+x2+x3+x4+x5=1
– : (xj can when xi =1, i.e. if xi =0 then xj =0; if xi =1 then xj
=0 or 1)
xj < xi => xj - xi < 0, e.g. _____________
– Project i is a corequisite for project j (i.e. both i & j have same

state): xj - xi => xj - xi = 0, e.g._____________
– Projects i and j are mutually exclusive (either, but not both one
exit): xi + xj < 1 e.g. ______________________
Modeling Flexibility Provided by 0-1 Variables
Project z conditional on project i or project j
Project z conditional on project i and project j
Another application: Product Design and Market

Share Optimisation
• Conjoint analysis
• Part-worth
• Refer Textbook Pg 338 to 342
Slide 15
When do you use Integer Linear Programming
• What is more real? ILP or LP?

• Which is preferred? ILP or LP?
• Why?
• So when do you use ILP?

• When solution is large/small?
• When coefficient is large/small?
Slide 16
Cautionary Note About Sensitivity Analysis
• Sensitivity analysis often is more crucial for ILP problems
than for LP problems.
• A small change in a constraint coefficient can cause a
relatively large change in the optimal solution.
• Recommendation: Resolve the ILP problem several
times with slight variations in the coefficients before
choosing the “best” solution for implementation.
• How do you do sensitivity analysis if your variables are

integer? Any suggestion?
Class Activity 1: Tina’s Tailoring
Tina's Tailoring has five idle tailors and four

custom garments to make. The estimated time (in
hours) it would take each tailor to make each garment
is shown in the next slide. (An 'X' in the table indicates
an unacceptable tailor-garment assignment.)
Tailor
Garment 1 2 3 4 5
Wedding gown 19 23 20 21 18
Clown costume 11 14 X 12 10
Admiral's uniform 12 8 11 X 9
Bullfighter's outfit X 20 20 18 21
Note: use xij, where xij =1 if garment i is assigned to tailor j ;
0 otherwise
Example: Tina’s Tailoring
Formulate an integer program for determining
the tailor-garment assignments that minimize
the total estimated time spent making the four
garments. No tailor is to be assigned more than one
garment and each garment is to be worked on by only
one tailor.
--------------------
This problem can be formulated as a 0-1 integer
program. The LP solution to this problem will
automatically be integer (0-1).
Procedure:
Define variables
Define Objective Function
Define constraints
Construct
Class Activity 2: Metropolitan Microwaves
Metropolitan Microwaves, Inc. is planning to
expand its sales operation by offering other electronic
appliances. The company has identified
seven new product lines it can carry.
Relevant information about each line
follows on the next slide.
Initial Floor Space Exp. Rate
Product Line Invest. (Sq.Ft.) of Return
1. TV/VCRs $ 6,000 125 8.1%

2. TVs 12,000 150 9.0 %
3. Projection TVs 20,000 200 11.0 %
4. VCRs 14,000 40 10.2 %
5. DVD Players 15,000 40 10.5 %
6. Video Games 2,000 20 14.1 %
7. Home Computers 32,000 100 13.2 %
Metropolitan Microwaves
Metropolitan has decided that they should not stock projection
TVs unless they stock either TV/VCRs or TVs. Also, they will
not stock both VCRs and DVD players, and they will stock video
games if they stock TVs. Finally, the company wishes to
introduce at least three new product lines.
If the company has $45,000 to invest and 420 sq. ft. of floor
space available, formulate an integer linear program for
Metropolitan to maximize its overall expected return.
Procedure:
• Define variables
• Define Objective Function
• Define constraints
• Construct the LP model
• Use Software to solve the model
• Interpret the results

Decision Analysis

Uploaded by

Copyright:

Available Formats

Decision Analysis

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Decision Analysis

Uploaded by

Copyright:

Available Formats

Lecture 3 Integer Linear Programming

• Types of Integer Linear Programming Models

• An LP in which all the variables are restricted to be integers is

If we relax the non-negative constraints to T,A ≥0, we will have the

Lets check by graphical means:

The optimal solution is

Max cash flow =

The MS Solution tells us that:

For C2: ________ hrs are still available.

In a capital budget problem, the company’s objective is to maximise the

The maximum profit is $1850, achieved by an optimal solution of 27.5 tons

Using these variables, the setup cost is:

The net profit: Gross profit – total set up cost=

The MS solution is shown:

– Project i is a corequisite for project j (i.e. both i & j have same

Project z conditional on project i or project j

Project z conditional on project i and project j

Another application: Product Design and Market

• What is more real? ILP or LP?

• So when do you use ILP?

• How do you do sensitivity analysis if your variables are

Tina's Tailoring has five idle tailors and four

1. TV/VCRs $ 6,000 125 8.1%

You might also like