MPEN 584E – Optimization and Simulation
Lesson 2: Optimization – The Basics
As a rule, when many options are available, man's actions are
guided by the need to choose the best possible way. Human
activity, indeed, implicates solving (consciously or unconsciously)
optimization problems.
Broadly speaking, optimization is the problem of
minimizing or maximizing a function subject to a
number of constraints..
Introduction – Example Problems
(i). Minimize the number of trucks required to pick up garbage by finding
the most efficient route for each truck.
(ii). City planners may need to decide where to build new fire stations in
order to efficiently serve their citizens.
(iii). How to construct an investment portfolio that maximizes its expected
return while limiting volatility;
(iv). how to build a resilient tele-communication network as cheaply as
possible;
(v). how to schedule flights in a cost-effective way while meeting the
demand for passengers;
(vi). or how to schedule final exams using as few classrooms as possible.
Solving an optimization (minimization/maximization) problem is a
two-step process:
• find a formulation of the optimization problem
• use a suitable algorithm to solve the formulation
A formulation is a mathematical representation of the
optimization problem. Needed to be determined are variables
(unknowns) in your formulations. The objective function will
represent the quantity that needs to be maximized. Finally,
every constraint to the problem is expressed as a mathematical
constraint.
With a mathematical formulation of an appropriate form, you need
to develop (or use an existing) algorithm to solve the formulation.
The algorithm represents a finite procedure (something that can be
coded as a computer program) that will take as input the
formulation, and return an assignment of values to each of the
variables such that all constraints are satisfied, and, subject to these
conditions, maximizes the objective function.
Example 1:
Suita Inc manufactures four products, requiring time on two machines and two
types of labor (skilled and unskilled). The amount of machine time and labor (in
hours) needed to produce a unit of each product and the sales prices in dollars per
unit of each product are given in the following table:
Each month, 700 hours are available on machine 1 and 500 hours on machine 2.
Each month, Suita Inc can purchase up to 600 hours of skilled labor at $8 per hour
and up to 650 hours of unskilled labor at $6 per hour. Determine how much of each
product it should produce each month and how much labor to purchase in order to
maximize its profit (i.e. revenue from sales minus labor costs).
Formulation: variables, objective function, constraints
How much of each product to manufacture
xi for each i ∈ {1, 2, 3, 4} for the number of units of product i to
manufacture.
ys and yu for the number of purchased hours of skilled and unskilled
labor, respectively
Sales revenue Labor cost
Objective Function
Constraints
each unit of product 1 requires 11 hours on machine 1: 11x1
each unit of product 2 requires 7 hours on machine 1: 7x2
each unit of product 3 requires 6 hours on machine 1: 6x3
each unit of product 4 requires 5 hours on machine 1: 5x4
each unit of product 1 requires 4 hours on machine 2: 4x1
each unit of product 2 requires 6 hours on machine 2: 6x2
each unit of product 3 requires 5 hours on machine 2: 5x3
each unit of product 4 requires 4 hours on machine 2: 4x4
Constraints
Total labor hours, skilled:
Total labor hours: unskilled:
Variables should have only nonnegative values;
Limit the number of hours of skilled and unskilled labor purchased.
Formulation
Does this formulation capture exactly the Suita Inc problem? If it does, then
it has correctness. How do you verify that a formulation is correct?
Description of the optimization problem = a description of the optimization
problem in plain English.
Formulation = mathematical formulation
Solution = assignment of values to each of the variables of the formulation
Feasible Solution = one where all the constraints are satisfied
Optimal Solution = feasible solution that maximizes the objective function
(or minimizes it if the optimization problem is a minimization problem).
Solution to the word description of the optimization problem = a choice for
the unknowns
(1) Every feasible solution of the word description gives a
feasible solution of the mathematical formulation, and
(2) Every feasible solution of the mathematical formulation gives
a feasible solution of the word description.
If (2) does not hold, feasible solutions to the formulation
may violate constraints of the word description, and if (1)
does not hold, then the formulation is more restrictive than
the word description.
Optimization problems on graphs
Observe that different drawings may correspond to the same graph
G = (V, E) with V = {1, 2, 3, 4, 5}
E = {12, 23, 34, 14, 15, 25, 35, 45}
Elements of V are called vertices
Elements of E are called edges
Bellman Ford Algorithm
Initialization
Relaxation
Example
Consider the following graph, and find the shortest
path using the bellman ford algorithm.
Solution:
Initially, the distance of each vertex will be
infinity from the source vertex and source-
to-source distance value would be zero. So,
considering A to be source vertex
