Operation Research /Management

Science

Mr. Aayush Bhattarai

Assistant Professor
Pulchowk Campus, IOE
2075
Integer Linear Programming
Introduction
 Some or all Decision Variables are required to be Integers (
Whole Numbers)
 If all Decision Variables are Integer then we refer that as All
Integer Model also refer to as Pure Integer Model or Total
Integer Model
Integer Linear Programming
Introduction
 Consider this LP Model with its graph
Integer Linear Programming
Introduction
 The Feasible Solution
Integer Linear Programming
Introduction
 Moving the Objective Function Upwards the optimal solution
Integer Linear Programming
Introduction
 The optimal Solution point
Integer Linear Programming
Introduction
 The OFV of 28.65
Integer Linear Programming
Introduction
 Suppose if X is number of laptops and Y is number of
desktops to purchase for new office.
 So by definition X and Y can
assume only integer values.
 So, now mathematical model
has a new constraints
Integer Linear Programming
Introduction
 So now the feasible solution are now reduced only to the
points where X and Y integers simultaneously.
 It follows that feasible solution to all
Integer problem are collection of dots.
Integer Linear Programming
Introduction
 Now if we move the OF line upwards we can see that
optimal solution occurs at (0,4), with an OFV of 28.
 That is only purchase Desktops.
Integer Linear Programming
Introduction
 Now suppose we decide to ignore or relax the integer
requirement and use the best optimal solution satisfying the
constraint, which we calculated earlier i.e 28.65 we refer to
that as LP Relaxation.
Integer Linear Programming
Introduction
 So LP Relaxation simply means that we begin with an Integer
problem and later ignore the integer requirements when
finding the solution the problem.
 As a result LP relaxation always provides upper bound for the
optimal value in a maximization integer problem.
 In other words, the optimal value produced by an integer
cannot be better than of its corresponding LP relaxation.
Integer Linear Programming
Introduction
 Mixed Integer ( X= amount of laptops , Y= amount of time)
Integer Linear Programming
Introduction
 Mixed Integer ( X= amount of laptops , Y= amount of time)
Integer Linear Programming
Introduction
 Mixed Integer
Integer Linear Programming
Introduction
 Rounding LP Relaxation Problem
 Recall Optimal Solution, and Integer Optimal Solution
Integer Linear Programming
Introduction
 Rounding Down will result another solution in Feasible region.

 So as long as coefficents in Maximization problems are

positive rounding down the relaxation will always result in
Feasible Solution.
 Rounding Up gives Solution beyond feasible region
Integer Linear Programming
Introduction
 Minimization Problem ( Rounding Up), X= 1.5, Y= 2.5, Z= 19.

 Lower bound to Min IP Problem

Integer Linear Programming
Introduction
 Minimization Problem ( Rounding Up)
Integer Linear Programming
Introduction
 If a model has some integer variables and some continuous
variables it is still ILP. One integer variable makes the model
ILP. ILP Models are some times called mix integer linear
programming ( MILP)because some variables are integer
and some are continuous.
Integer Linear Programming
Solving ILP in Excel
 Implement objective function, variables and constraint as
previous.
 Add integer constraint, select INT for Integer and BIN for
binary
 In solver set integer optimality to 0 ( In older version its
tolerance)
 Non Zero tolerance means that solver can return a solution
worse than optimal by Tolerance Value
 If you have integer/binary constraint, but you still get
fractional optimal solution, make sure solver option “ Ignore
Integer Constraint” is unchecked.
 Select simplex LP method.
Integer Linear Programming
Branch and Bound Method ( B& B Method)
 Most common method in solving ILP
 It involves solving Multiple LP Relaxations, each using the
simplex method.
 Therefore, solving ILP models can take much longer than
solving equivalent LP models.
 This is why ILP models are considered much more difficult
than LP models.
 If possible, use LP models instead of ILP. Add INT or BIN only if
necessary.
Integer Linear Programming
An employee scheduling problem
Integer Linear Programming
An employee scheduling problem ( Decision Variables)
Integer Linear Programming
An employee scheduling problem ( Objective Function)
Integer Linear Programming
An employee scheduling problem ( Model)
Integer Linear Programming
An employee scheduling problem ( Excel Model)
Integer Linear Programming
An employee scheduling problem ( Solver Parameters)
Integer Linear Programming
An employee scheduling problem ( Solution)
Integer Linear Programming
An employee scheduling problem ( Better Solution)
Integer Linear Programming
Binary Variable
 Some LP problems naturally evolve into ILP problems when we realize that
we need to obtain integer solutions.
 We needed to determine the number of workers to assign to each of seven
shifts ( Air express problems)
 Because workers are discrete units, we needed to impose integrality
conditions on the decision variables in this model representing the number
of workers scheduled for each shift.
 To do so, we changed the continuous variables in the model into general
integer variables, or variables that could assume any integer value
(provided that the constraints of the problem are not violated).
 In many other situations, we might want to use binary integer variables (or
binary variables), which can assume only two integer values: 0 and 1.
 Binary variables can be useful in several practical modeling situations,
Integer Linear Programming
A Capital Budgeting Problem
Integer Linear Programming
A Capital Budgeting Problem ( Decision Variables)

 We will let X1, X2, . . . , X6 represent the six decision variables for this problem
and assume they operate as:

 Each decision variable in this problem is a binary variable that assumes the
value 1 if the associated project is selected, or the value 0 if the associated
project is not selected.
Integer Linear Programming
A Capital Budgeting Problem Objective Function)
Integer Linear Programming
A Capital Budgeting Problem (Constraints)
Integer Linear Programming
A Capital Budgeting Problem (Mathematical Model)
Integer Linear Programming
A Capital Budgeting Problem (Excel Model)
Integer Linear Programming
A Capital Budgeting Problem (Solver Parameters)
Integer Linear Programming
A Capital Budgeting Problem (Solver Result)
Integer Linear Programming
A Capital Budgeting Problem (Optimal Solution Vs Heuristic
Solution)
 Comparing the Optimal Solution with the Heuristic Solution technique.
 Heuristic Solution explained in class.
 Thumb Rule.
Integer Linear Programming
Binary Variables and Logical Conditions
 Binary variables can be used to model several logical conditions that
might apply in a variety of problems.
 For Example:- In the CRT Technologies problem, several of the projects
under consideration (for example, projects 1, 3, and 6) might represent
alternative approaches for producing a certain part for a product.
 If we want to ensure that the solution includes exactly one of alternatives,
we could include the following constraint in our model.
X1+X3+X6=1
 As an example of another type of logical condition, suppose that project
4 involves a cellular communications technology that will not be available
to the company unless it undertakes project 5. This type of relationship can
be imposed on the solution with the constraint:
X4-X5≤0
Integer Linear Programming
Fixed Charge Problems
Integer Linear Programming
Fixed Charge Problems

 We are going to need two types of decision variables here,

 One set for the number of units produced from each machine
 The another set to indicate whether the machine is being used or not
because of the fixed cost.
Integer Linear Programming
Fixed Charge Problems
Integer Linear Programming
Fixed Charge Problems

 Since fixed costs indicate that entire cost will be incurred if the
corresponding machines is used to produce at all,
 Then another set of variables is defined.
Integer Linear Programming
Fixed Charge Problems

 In another words,
Integer Linear Programming
Fixed Charge Problems

 The OFV
Integer Linear Programming
Fixed Charge Problems

 The Model