Integer Programming
Megha Sharma
Example
XYZ tourism conducts one day sight seeing
tours in a small city. For these tours XYZ hires
buses from an agency which has two types of
buses, 6 small ones that can accommodate 60
tourists and 5 larger buses that can
accommodate 90 tourists. The agency charges
Rs. 500 per trip for a small bus and Rs. 700 per
trip for a large bus. XYZ needs to accommodate
500 tourists a day on average, and wants to
find out the number of buses of each type that
it should hire each day to meet the average
daily demand.
XYZ Tourism
Solving using MS Excel
Optimal value of Bs = 5/6, Bl = 5, Z = 3916.67
Number of buses = 5/6 ??
Should we round it up or round down??
So, Bs = 1, Bl = 5, Z = 4000.00
Would it also be the optimal solution to the
corresponding integer programme?
Integer Programming Formulation
Pure integer
linear programme
MS Excel solution
Optimal value of Bs = 1, Bl = 5, Z = 4000.00
Would it always be the case??
No, lets take an example.
Does LP relaxation always work?
Solution: Solution:
1. LP relaxation: 1. LP relaxation:
Bs = 5/6, Bl = 5, Z = 3916.67 Bs = 6, Bl = 1.56, Z = 3788.89
2. Rounded off solution: 2. Rounded off solution:
Bs = 1, Bl = 5, Z = 4000.00 Bs = 6, Bl = 2, Z = 4100.00
3. True optimal solution: 3. True optimal solution:
Bs = 1, Bl = 5, Z = 4000.00 Bs = 4, Bl = 3, Z = 3900.00
Solving Integer Programming Problems
(IPP)
Is it easier than linear programming
problems?
Number of feasible solutions is finite in IPP while it
is infinite in LPP
LPP has certain characteristics that reduces the
number of feasible solution to be evaluated to not
only to a finite number, but only to corner points
Therefore solving LPP is easier than solving IPP
Binary programming: Integer variables are
allowed to take only two values, 0 and 1 (also
called Zero-One integer programmes)
Is Binary programming easier than IPP?
Binary Programming: Example
CMC is considering expansion by building a new
factory in either LA or San Francisco, or in both
cities. It is also considering building at most one
warehouse which has to be located in a city
where the new factory is being built. Relevant
data for this problem is given in the following
table.
Find out the feasible combination of alternatives
that maximizes the total NPV.
CMC Expansion Project
Decision No. Yes or No NPV Capital Reqd
Question
1 Factory in LA 9 million 6 million
2 Factory in SF 5 million 3 million
3 Warehouse in 6 million 5 million
LA
4 Warehouse in 4 million 2 million
SF
Capital available 10 million
CMC Expansion Project
Decision Yes or No Binary NPV Capital
No. Question Variables Reqd
1 Factory in LA x1 9 million 6 million
2 Factory in SF x2 5 million 3 million
3 Warehouse in x3 6 million 5 million
LA
4 Warehouse in x4 4 million 2 million
SF
Capital available 10
million
Formulations using Binary Variables
Objective: Maximize profit
Maximize Z = 9x1 + 5x2 + 6x3 + 4x4
Constraints
Budget constraint
6x1 + 3x2 + 5x3 + 2x4 ≤ 10
At most one warehouse
x3 + x 4 ≤ 1
Warehouse can only be opened in a city where a
factory is
x3 ≤ x1 and x4 ≤ x2
Non-negativity and Binary
x1, x2, x3, x4 are Binary
Binary Variables: Either-or Constraints
ABC furniture produces two products, tables and
chairs. For its upcoming factory, it wants to decide
on which machine to buy. There are two options
available in the market namely Machine1 and
Machine 2, which differ in the number of hours that
they can work in a day as well as the processing
times that they require for a product. Data for
these two machines is given in the following table.
Table Chair Availability/
day
Machine 1 3 2 18
Machine 2 1 4 16
Raw material 6 3 30
reqd per unit
Profit margin 70 50
Formulation: ABC Furniture
Raw material constraint
Machine 1 availability
Machine 2 availability
Is the formulation correct ??
One of the two constraints must hold
Raw material constraint
Machine 1 availability
Only 1 machine
Machine 2 availability is bought
Machine 1 availability
Machine 2 availability
K out of N constraints must hold
There are N constraints, say
K of which should hold, K ≤ N
Modeling functions with N Possible
values
ABC Furniture decided and bought Machine 1
which is available for work 18 hours a day.
ABC knows that the current production plan
does not use the full capacity of Machine 1, to
be able to use the unused capacity of this
Machine for developing new products, ABC
wants to decide the optimal product mix of
tables and chairs such that either 6 hours of
Machine 1 are used, or 12 hours are used or the
full capacity (i.e. 18 hours ) is used.
Modeling functions with N Possible
values
Raw material constraint
Machine 1 availability
Fixed Cost/Charge Problem
Gandhi Cloth Company is capable of manufacturing three
types of clothing: shirts, shorts, and pants. The
manufacture of each type of clothing requires that Gandhi
have the appropriate type of machinery available.
The machinery needed to manufacture each type of
clothing must be rented at the following rates: shirt
machinery Rs. 2000 per week, shorts machinery Rs. 1500
per week, and pants machinery Rs. 1000 per week.
The manufacture of each type of clothing also requires
the amount of cloth and labour as shown in the table
below. Each week, 150 hours of labour and 160 sq. m. of
cloth are available. The variable unit cost and selling price
for each type of clothing are given below.
Fixed Cost/Charge Problem
Clothing Labour Cloth (sq.
Type (hours) m)
Shirts 3 4
Shorts 2 3
Pants 6 4
Clothing Sales Price Variable Cost
Type (Rs) (Rs)
Shirts 12 6
Shorts 8 4
Pants 15 8
Formulate this problem as an integer linear programming
problem so as to maximize GCC’s weekly profit.
Contingent Constraints in Continuous
Variables
A company produces two types of medicines, Ma
and Mb. Per unit profit contribution, raw material
and weekly labour requirements are given in the
table below. If the total weekly production is 30
units or more, Govt. regulations require that total
weekly pollutants generated by the production
does not exceed 70 units. However, there is no
such restriction is total weekly production is less
than 30 units. DetermineMa an optimal
Mb production
Availabl
plan that maximizes total weekly profit. e
Profit/unit 7 8
Raw Material 3 2 16
Labour Hours 5 7 15
Pollutants gen. per 0.3 0.5
unit
Formulation Examples
GPC has developed 3 new products. However,
to avoid undue diversification of the company’s
product line, management has imposed the
following restriction.
1. From the 3 possible new products, at most
two should be chosen to be produced.
2. Just one of the two plants of GPC should be
chosen to be the sole producer of the new
products.
Production and investment related data for
these products is given in the following table.
Which product(s) should the company produce
and in which plant so as to maximize total
Formulation Examples
Production time used for Production
each unit produced time
Product Product Product 3 available
1 2 per week
Plant 1 3 hours 4 hours 2 hours 30 hours
Plant 2 4 hours 6 hours 2 hours 40 hours
Unit profit (‘000) 5 7 3
Sales potential 7 5 9
(units/week)