OPERATIONAL RESEARCH &
OPTIMISATION
Dr. Fang He
Email: hef@westminster.ac.uk
Office: N7.118
University of Westminster
6DATA005W Operational Research &Optimisation 2
Outline
• Integer Programming
• General Integer Programming model techniques
• Packing Optimisation Problems
• Capacity and Indicator Variables
• Knapsack Type Problems
• Generalised assignment problems
• Bin Packing Type Problems
• Routing and location problems
• Travelling Salesman Problem
• Facility location problem
6DATA005W Operational Research &Optimisation 3
Integer Programming
6DATA005W Operational Research &Optimisation 4
6DATA005W Operational Research &Optimisation 5
The advantages of integer programs
6DATA005W Operational Research &Optimisation 6
Examples of constraints
6DATA005W Operational Research &Optimisation 7
Nonlinear functions can be modeled using
integer programming
6DATA005W Operational Research &Optimisation 8
Integer Programs
6DATA005W Operational Research &Optimisation 9
Types of Integer Programs
6DATA005W Operational Research &Optimisation 10
Integer Programming
6DATA005W Operational Research &Optimisation 11
Integer Programming
6DATA005W Operational Research &Optimisation 12
A 2-Variable Integer program
6DATA005W Operational Research &Optimisation 13
The Feasible Region
6DATA005W Operational Research &Optimisation 14
A rounding technique that sometimes is useful,
and sometimes not.
6DATA005W Operational Research &Optimisation 15
How integer programs are solved
(and why they are hard to solve)
• Rely on solving LPs fast
• Branch and bound and cutting planes
• Out of scope of this module
6DATA005W Operational Research &Optimisation 16
Why integer programs?
6DATA005W Operational Research &Optimisation 17
Some Comments on IP models
• There are often multiple ways of modeling the same
integer program.
• Solvers for integer programs are extremely sensitive to
the formulation. (not true for LPs).
• Not as easy to model
• Not as easy to solve.
6DATA005W Operational Research &Optimisation 18
Some IP model techniques
• Modeling logical constraints that include only two binary
variables.
• Step 1. Graph the feasible region as restricted to the two variables.
• Step 2. Add linear equalities and or inequalities so that the feasible
region of the IP is the same as that given in Step 1.
6DATA005W Operational Research &Optimisation 19
Logical Constraints 1
6DATA005W Operational Research &Optimisation 20
Logical Constraints 2
6DATA005W Operational Research &Optimisation 21
Logical Constraints 3
6DATA005W Operational Research &Optimisation 22
Other logical constraints
• Modeling logical constraints that involve non-binary
variables is much harder.
• BIG M Method for IP Formulations.
6DATA005W Operational Research &Optimisation 23
BIG M Method for IP Formulations
6DATA005W Operational Research &Optimisation 24
The logical constraint “x ≤ 2 or x ≥ 6”
6DATA005W Operational Research &Optimisation 25
Modeling “or constraints”
6DATA005W Operational Research &Optimisation 26
Using Excel Solver to Solve Integer Programs
6DATA005W Operational Research &Optimisation 27
A general example 1
6DATA005W Operational Research &Optimisation 28
A general example-1
6DATA005W Operational Research &Optimisation 29
A general example 2-Level 7
6DATA005W Operational Research &Optimisation 30
A general example 2-Level 7
6DATA005W Operational Research &Optimisation 31
6DATA005W Operational Research &Optimisation 32
6DATA005W Operational Research &Optimisation 33
6DATA005W Operational Research &Optimisation 34
6DATA005W Operational Research &Optimisation 35
6DATA005W Operational Research &Optimisation 36
6DATA005W Operational Research &Optimisation 37
Packing optimisation problems
6DATA005W Operational Research &Optimisation 38
6DATA005W Operational Research &Optimisation 39
6DATA005W Operational Research &Optimisation 40
Some example applications of IP-1
6DATA005W Operational Research &Optimisation 41
Some example applications of IP-2
6DATA005W Operational Research &Optimisation 42
Some example applications of IP-3
6DATA005W Operational Research &Optimisation 43
Routing and location problems-Level 7
6DATA005W Operational Research &Optimisation 44
6DATA005W Operational Research &Optimisation 45
6DATA005W Operational Research &Optimisation 46
6DATA005W Operational Research &Optimisation 47
6DATA005W Operational Research &Optimisation 48
The complexity of TSP
• Note: sub-tour elimination constraints cause the difficulty
to the TSP .
• See http://www.tsp.gatech.edu/methods/cpapp/index.html
for using sub-tour elimination constraints.
6DATA005W Operational Research &Optimisation 49
6DATA005W Operational Research &Optimisation 50
6DATA005W Operational Research &Optimisation 51
• Rest of slides are all for Level 7!
6DATA005W Operational Research &Optimisation 52
Memory Card-1
6DATA005W Operational Research &Optimisation 53
Memory Card-2
6DATA005W Operational Research &Optimisation 54
Memory Card-3
6DATA005W Operational Research &Optimisation 55
Memory Card-4
6DATA005W Operational Research &Optimisation 56
Memory Card-5
6DATA005W Operational Research &Optimisation 57
• For more Integer programming formulation examples
see
• http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html
