Scribd
Upload
13 views13 pages

Integer Programming & Sensitivity Analysis Guide

The document provides an overview of Integer Programming, explaining concepts such as integer linear programs, types of integer programming, and algorithms used to solve these problems. It also discusses sensitivity analysis, which examines how changes in model coefficients impact optimal solutions. Key methods for solving integer programming include the Branch-and-Bound algorithm and the Cutting-Plan Method.

Uploaded by

aabkrino12
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views13 pages

Integer Programming & Sensitivity Analysis Guide

The document provides an overview of Integer Programming, explaining concepts such as integer linear programs, types of integer programming, and algorithms used to solve these problems. It also discusses sensitivity analysis, which examines how changes in model coefficients impact optimal solutions. Key methods for solving integer programming include the Branch-and-Bound algorithm and the Cutting-Plan Method.

Uploaded by

aabkrino12
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Integer Programming &

Sensitivity analysis
Dr. Ghada Maher
Integer Programming an Introduction
Integer linear program A linear program with the additional requirement
that one or more of the variables must be integer.

All-integer linear program An integer linear program in which all variables


are required to be integer.

Solving an integer programming problem is much more difficult than solving


an linear programming problem

LP Relaxation The linear program that results from dropping the integer
requirements for the variables in an integer linear program.
Types of Integer Linear Programming (ILP)
PURE-integer programming all decision variables have integer solutions

Mixed-integer linear programming An integer linear program in which


some, but not necessarily all, variables are required to be integer.

0-1 integer linear programming An all-integer or mixed-integer linear


program in which the integer variables are only permitted to assume
the values 0 or 1. Also called binary integer
program.
Integer programming algorithms
The ILP algorithms are used on exploiting the tremendous computational
success of LP. The strategy of these algorithms involves three steps.
Step 1: relax the solution space of the ILP by deleting the integer restriction
on all integer variables and replacing any binary variable Y with the
continuous range 0≤y ≤ 1. The result of the relaxation is regular LP.
Step 2: solve the LP, and identify its continuous optimum.
Step 3: starting from the continuous optimum point, add special constraints
that iteratively modify the LP solution space in a manner that will eventually
render an optimum extreme point satisfying the integer requirements.
Two general methods have been developed
for generating the special constraints in step 3
1- Branch-and-Bound (B&B) algorithm
2- Cutting-Plan Method
Example :Branch-and-Bound
Sensitivity analysis
Sensitivity analysis is the study of how the changes in the coefficients
of an optimization model affect the optimal solution. Using sensitivity
analysis, we can answer questions such as the following:
[Link] will a change in the right-hand-side value for a constraint affect
the optimal solution?
2. How will a change in a coefficient of the objective function affect the
optimal solution?
3. How will a change in a coefficient of the decision variable affect the
optimal solution?
Sensitivity analysis
change in the right-
hand-side value of
constraint
Changes in RHS of constraints

You might also like