Integer Programming in
Advanced OR
By
Anirudha Kotgire 2009024
Manoj Raghuwanshi 2009093
Sujeet Biradar 2009255
Vinay Srivastava 2009262
Agenda
What is Integer Programming?
IP modeling Techniques
Why IP?
IP Illustration
Case: Application in Residential lighting
What is Integer
Programming?
Programming means making decisions
Special case of linear programming.
§ Deals in 0 or 1 (binary)
History
Mathematical model developed during World War
II
The founders of the subject are Leonid
Kantorovich,
a Russian mathematician who developed linear
programming
problems in 1939
Linear programming is a considerable field of
optimization for several reasons. Many practical
problems
in operations research can be expressed as linear
programming problems.
IP around us
Programming = Planning in this context
In a survey of Fortune 500 firms,
85% of those responding said that they have
used linear or integer programming.
Why is it so popular?
Many different real-life situations can be modeled as IPs.
There are efficient algorithms to solve IPs.
IP modeling techniques
Using binary variables
Restrictions on number of options
Contingent decisions
Variables (functions) with k possible values
Either-Or Constraints
Big M method
Balance constraints
Fixed Charges
Making choices with non-binary variables
Piecewise linear functions
IP applications
Ø Facility Location Problem
Ø Knapsack Problem
Ø Multi-period production planning
Ø Inventory management
Ø Fair representation in electoral systems
Ø Consultant hiring
Ø Bin Packing Problem
Ø Pairing Problem
Ø Traveling Salesman Problem
Why integer programs?
Advantages of taking on integer values
§ More realistic
§ More flexible
Disadvantages
§ Difficult to model
§ Can be much difficult to solve
On 0-1 variables
Integer programs: linear equalities and inequalities
plus
constraints that say a variable must be integer valued.
We also permit “xj {0,1}.” This is equivalent to
0 xj 1 and xj integer.
The Mystery of integer
programming
Some integer programs are easy
(we can solve problems with millions of variables)
Some integer programs are hard
(even 100 variables can be challenging)
It takes expertise and experience to know which is
which
It’s an active area of research.
Types of integer programs
All integer programs have linear equalities and
inequalities and some or all of the variables
are
required to be integer.
If all variables are required to be integer, then it
is usually called a pure integer program.
If all variables are required to be 0 or 1, it is
called a binary integer program, or
a 0-1 integer program.
if some variables can be fractional and others
are required to be integers, it is called a
mixed linear integer program (MILP)
Stockco Example
Stockco is considering 6 investments. The cash required
from each investment as well as the NPV of the
investment is given. The cash available for the
investments is $14,000. Stockco wants to maximize its
NPV. What is the optimal strategy?
An investment can be selected or not. One cannot select a
fraction of an investment.
Data for the Stockco Problem
Investment budget = $14,000
Integer Programming
Formulation
What are the decision variables?
Objective and Constraints?
Max 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6
5x1+ 7x2+ 4x3+ 3x4+ 4x5+ 6x6 14
x ε {0,1} for each j = 1 to
Possible constraints
The previous constraints represent “economic
indivisibilities”, either a project is selected, or it
is not. There is no selecting of a fraction of a
project.
Similarly, integer variables can model logical
requirements (e.g., if stock 2 is selected, then so
is stock 1.)
The Application
Residential lighting problem
in Maharashtra: A case of
Integer Programming
The Problem
To develop an optimal portfolio for meeting
the lighting requirement of a typical household
in Maharashtra State in India.
Fact sheet
Maharashtra has (in 2001-2002)an installed
capacity of 15,148 MW.
Total generation is 64,430 GWh of
electricity.
Total consumption (2001-02) is 46,338
GWh.
Residential consumption is 11,901 GWh
accounts about 25.68% of total
consumption.
Lighting accounts for about 40% of
residential
The Assumptions
The number of lighting points in a typical
household is 10.
Average hours of usage per day 3 hours.
Portfolio posses same amount of light
output.
Differences are only in energy input and
the cost of these devices.
Lighting devices/ level
requirements
Feasible lighting alternatives
Relative Risk Return
Expected Annual Return
Annual cost of utilization for
different usage hours (Rs.)
Annual rates of return for feasible
alternatives of IB replacements
(%)
Integer Programming Problem
Objective function to maximize saving:
Subject to constraints
1. No of lighting devices required for given usage
hour
Subject to constraints
2. Total no of lighting devices for a household
3. Demand for the level of lighting
4. Opportunity cost of using inappropriate device
5. Non-negativity constraint
All variables >= 0
Optimum portfolio of lighting
devices
The Outcome
Thank you