CHAPTER 1-2

CLASSIFICATION OF OPTIMIZATION
PROBLEMS
Dr. Pramod Sreedharan
Department of Mechanical Engg.
Amrita Vishwa Vidyapeetham
CLASSIFICATION OF OPTIMIZATION
PROBLEMS

➢ Optimization problems can be classified in

several ways, as described below.

1. Classification Based on the Existence of

Constraints

➢ As indicated earlier, any optimization problem can

be classified as constrained or unconstrained,
depending on whether constraints exist in the
problem.
2. Classification Based on the Nature of the Design
Variables

➢ Based on the nature of design variables

encountered, optimization problems can be
classified into two broad categories.

➢ In the first category, the problem is to find values

to a set of design parameters that make some
prescribed function of these parameters minimum
subject to certain constraints.

➢ For example, the problem of minimum-weight

design of a prismatic beam shown in Fig. 1.8a
subject to a limitation on the maximum deflection
can be stated as follows:
➢ Here the design variables are functions of the
length parameter t.

➢ This type of problem, where each design variable

is a function of one or more parameters, is known
as a trajectory or dynamic optimization problem.

3. Classification Based on the Physical Structure of

the Problem

➢ Depending on the physical structure of the

problem, optimization problems can be classified as
optimal control and nonoptimal control problems.
3.1 Optimal Control Problem

➢ An optimal control (OC) problem is a

mathematical programming problem involving a
number of stages, where each stage evolves from
the preceding stage in a prescribed manner.

➢ It is usually described by two types of variables:

the control (design) and the state variables.

➢ The control variables define the system and

govern the evolution of the system from one stage
to the next, and the state variables describe the
behavior or status of the system in any stage.
➢ The problem is to find a set of control or design
variables such that the total objective function
(also known as the performance index, PI) over all
the stages is minimized subject to a set of
constraints on the control and state variables.

➢ An OC problem can be stated as follows:

Example 1.2 A rocket is designed to travel a distance
of 12s in a vertically upward direction. The thrust of
the rocket can be changed only at the discrete points
located at distances of 0, 1s, 2s, 3s, . . . , 12s. If the
maximum thrust that can be developed at point i
either in the positive or negative direction is
restricted to a value of Fi , formulate the problem of
minimizing the total time of travel under the
following assumptions:
1. The rocket travels against the gravitational force.
2. The mass of the rocket reduces in proportion to
the distance traveled.
3. The air resistance is proportional to the velocity
of the rocket.
SOLUTION

➢ Let points (or control points) on the path at which

the thrusts of the rocket are changed be numbered
as 1, 2, 3, . . . , 13 (Fig. 1.9).

➢ Denoting xi as the thrust, vi the velocity, ai the

acceleration, and mi the mass of the rocket at point i,
Newton’s second law of motion can be applied as:

Net force on the rocket = mass × acceleration.

➢ This can be written as:

Thrust − Gravitational force − Air resistance =

mass × acceleration
4. Classification Based on the Nature of the
Equations Involved

➢ Another important classification of optimization

problems is based on the nature of expressions for
the objective function and the constraints.

➢ According to this classification, optimization

problems can be classified as:

Linear,
Nonlinear,
Geometric, and
Quadratic programming problems.
➢ This classification is extremely useful from the
computational point of view since there are many
special methods available for the efficient solution
of a particular class of problems.

➢ Thus, the first task of a designer would be to

investigate the class of problem encountered.

➢ This will, in many cases, dictate the types of

solution procedures to be adopted in solving the
problem.
Nonlinear Programming Problem

➢ If any of the functions among the objective and

constraint functions in Eq. (1.1) is nonlinear, the
problem is called a nonlinear programming (NLP)
problem.

➢ This is the most general programming problem

and all other problems can be considered as special
cases of the NLP problem.
Example 1.3 The step-cone pulley shown in Fig. 1.10
is to be designed for transmitting a power of at least
0.75 hp. The speed of the input shaft is 350 rpm and
the output speed requirements are 750, 450, 250, and
150 rpm for a fixed center distance of ‘a’ between the
input and output shafts. The tension on the tight
side of the belt is to be kept more than twice that on
the slack side. The thickness of the belt is t and the
coefficient of friction between the belt and the
pulleys is µ. The stress induced in the belt due to
tension on the tight side is s. Formulate the problem
of finding the width and diameters of the steps for
minimum weight.
Geometric Programming Problem
Example 1.4 Four identical helical springs are used
to support a milling machine weighing 5000 lb.
Formulate the problem of finding the wire diameter
(d), coil diameter (D), and the number of turns (N) of
each spring (Fig. 1.11) for minimum weight by
limiting the deflection to 0.1 in. and the shear stress
to 10,000 psi in the spring. In addition, the natural
frequency of vibration of the spring is to be greater
than 100 Hz. The stiffness of the spring (k), the shear
stress in the spring (τ ), and the natural frequency of
vibration of the spring (fn) are given by
where G is the shear modulus, F the compressive
load on the spring, w the weight of the spring, ρ the
weight density of the spring, and Ks the shear stress
correction factor. Assume that the material is spring
steel with G = 12 × 10^6 psi and ρ = 0.3 lb/in^3 , and
the shear stress correction factor is Ks ≈ 1.05.
Quadratic Programming Problem

➢ A quadratic programming problem is a nonlinear

programming problem with a quadratic objective
function and linear constraints.

➢ It is usually formulated as follows:

Example 1.5 A manufacturing firm produces two
products, A and B, using two limited resources. The
maximum amounts of resources 1 and 2 available per
day are 1000 and 250 units, respectively. The
production of 1 unit of product A requires 1 unit of
resource 1 and 0.2 unit of resource 2, and the
production of 1 unit of product B requires 0.5 unit of
resource 1 and 0.5 unit of resource 2. The unit costs
of resources 1 and 2 are given by the relations
(0.375 − 0.00005u1) and (0.75 − 0.0001u2), respectively,
where ui denotes the number of units of resource i
used (i = 1, 2). The selling prices per unit of products
A and B, pA and pB, are given by
pA = 2.00 − 0.0005xA − 0.00015xB
pB = 3.50 − 0.0002xA − 0.0015xB, where xA and xB
indicate, respectively, the number of units of products
A and B sold.
Formulate the problem of maximizing the profit
assuming that the firm can sell all the units it
manufactures.
As the objective function [Eq. (E5)] is a quadratic and
the constraints [Eqs. (E1) to (E4)] are linear, the
problem is a quadratic programming problem.
Linear Programming Problem

➢ If the objective function and all the constraints in

Eq. (1.1) are linear functions of the design variables,
the mathematical programming problem is called a
linear programming (LP) problem.

➢ A linear programming problem is often stated in

the following standard form:
Example 1.6 A scaffolding system consists of three
beams and six ropes as shown in Fig. 1.12. Each of
the top ropes A and B can carry a load of W1, each
of the middle ropes C and D can carry a load of W2,
and each of the bottom ropes E and F can carry a
load of W3. If the loads acting on beams 1, 2, and 3
are x1, x2, and x3, respectively, as shown in Fig. 1.12,
formulate the problem of finding the maximum
load (x1 + x2 + x3) that can be supported by the
system. Assume that the weights of the beams 1, 2,
and 3 are w1, w2, and w3, respectively, and the
weights of the ropes are negligible.
5. Classification Based on the Permissible Values of
the Design Variables

➢ Depending on the values permitted for the design

variables, optimization problems can be classified
as integer and real-valued programming problems.

Integer Programming Problem

➢ If some or all of the design variables x1, x2, . . . , xn

of an optimization problem are restricted to take on
only integer (or discrete) values, the problem is
called an integer programming problem.
➢ On the other hand, if all the design variables are
permitted to take any real value, the optimization
problem is called a real-valued programming
problem.

➢ According to this definition, the problems

considered in Examples 1.1 to 1.6 are real-valued
programming problems.
Example 1.7 A cargo load is to be prepared from
five types of articles. The weight wi , volume vi , and
monetary value ci of different articles are given
below.
Find the number of articles xi selected from the ith
type (i = 1, 2, 3, 4, 5), so that the total monetary value
of the cargo load is a maximum. The total weight
and volume of the cargo cannot exceed the limits of
2000 and 2500 units, respectively.
6. Classification Based on the Deterministic Nature
of the Variables

➢ Based on the deterministic nature of the variables

involved, optimization problems can be classified as
deterministic and stochastic programming problems.

Stochastic Programming Problem

➢ A stochastic programming problem is an

optimization problem in which some or all of the
parameters (design variables and/or preassigned
parameters) are probabilistic (nondeterministic or
stochastic).
➢ According to this definition, the problems
considered in Examples 1.1 to 1.7 are deterministic
programming problems.
Example 1.8 Formulate the problem of designing a
minimum-cost rectangular under-reinforced
concrete beam that can carry a bending moment
M with a probability of at least 0.95. The costs of
concrete, steel, and formwork are given by
Cc = $200/m^3 , Cs = $5000/m^3 , and Cf = $40/m^2 of
surface area. The bending moment M is a
probabilistic quantity and varies between 1 × 10^5
and 2 × 10^5 N-m with a uniform probability. The
strengths of concrete and steel are also uniformly
distributed probabilistic quantities whose lower and
upper limits are given by
fc = 25 and 35 MPa
fs = 500 and 550 MPa.
Assume that the area of the reinforcing steel and the
cross-sectional dimensions of the beam are
deterministic quantities.
7. Classification Based on the Separability of the
Functions

➢ Optimization problems can be classified as

separable and nonseparable programming problems
based on the separability of the objective and
constraint functions.

Separable Programming Problem

➢ Definition: A function f (X) is said to be separable

if it can be expressed as the sum of n single-variable
functions, f1(x1), f2(x2), . . . , fn(xn), that is,
Example 1.9 A retail store stocks and sells three
different models of TV sets. The store cannot afford
to have an inventory worth more than $45,000 at any
time. The TV sets are ordered in lots. It costs $aj for
the store whenever a lot of TV model j is ordered.
The cost of one TV set of model j is cj . The demand
rate of TV model j is dj units per year. The rate at
which the inventory costs accumulate is known to be
proportional to the investment in inventory at any
time, with qj = 0.5, denoting the constant of
proportionality for TV model j . Each TV set occupies
an area of sj = 0.40 m^2 and the maximum storage
space available is 90 m^2 . The data known from the
past experience are given below.
8. Classification Based on the Number of Objective
Functions

➢ Depending on the number of objective functions to

be minimized, optimization problems can be
classified as single- and multiobjective programming
problems.

➢ According to this classification, the problems

considered in Examples 1.1 to 1.9 are single objective
programming problems.

Multiobjective Programming Problem

➢ A multiobjective programming problem can be

stated as follows:
Example 1.10 A uniform column of rectangular
cross section is to be constructed for supporting a
water tank of mass M (Fig. 1.14). It is required
(1) to minimize the mass of the column for economy,
and
(2) to maximize the natural frequency of transverse
vibration of the system for avoiding possible
resonance due to wind. Formulate the problem of
designing the column to avoid failure due to direct
compression and buckling. Assume the permissible
compressive stress to be σmax.