SEPARABLE PROGRAMMING
MA7391 Seminar
Separable Programming
By
VIYASAR MOULY
(M190659MA)
Under the guidance of
Dr. Sushama C M
Department of Mathematics
National Institute of Technology Calicut
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 1 / 33
SEPARABLE PROGRAMMING
OVERVIEW
• INTRODUCTION
• SEPARABLE PROGRAMMING
• SEPARABLE CONVEX PROGRAMMING
• POINTWISE LINEAR APPROXIMATION
• CONVERT TO LINEAR FUNCTION
• STEPS TO SOLVING PROBLEM
• REFERNCE
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 2 / 33
SEPARABLE PROGRAMMING
Introduction
•The method of separable programming was first formulated by Miller
(1963).
•Separable programming is a modification to the normal simplex method.
•Seprable programming(SP) is one of the indirect method to solve non-
linear programming problems
•This method is used to obtain, atleast approximately optimal solution for a
relatively large class of non-linear programming problem(NLPP).
•The linear approximation function involved is a piecewise linear function.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 3 / 33
SEPARABLE PROGRAMMING
Separable function
Definition 1.1
A function f (x1 , x2 , ....xn ) is said to be separable if it can be
expressed as the sum of n single valued functions f1 (x1 ), f2 (x2 ), ....f1 (xn ), i.e.
f (x1 , x2 , ....xn )=f1 (x1 ), f2 (x2 ), ....fn (xn ).
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 4 / 33
SEPARABLE PROGRAMMING
Separable programming
Definition 1.2
If the objective function of NLPP problem can be expressed as a
linear combination of several different one-variable functions,of which same
or all are non-linear,Then such an NLPP problem is called a Separable
programming.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 5 / 33
SEPARABLE PROGRAMMING
Consider,
Max/Min f(x)=f1 (x1 ) + f2 (x2 ) + ..... + fj (xj )
subject to
g11 (x1 ) + g12 (x2 ) + ..... + g1j (xj ) ≤=≥ b1
g21 (x1 ) + g22 (x2 ) + ..... + g2j (xj ) ≤=≥ b2
. . . .
. . . .
gi1 (x1 ) + gi2 (x2 ) + ..... + gij (xj ) ≤=≥ bj
xi ≥ 0 i,j=0,1,2,...n
Since the objective functions as well as all the constraints are separable.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 6 / 33
SEPARABLE PROGRAMMING
EXAMPLES
• The linear function
f (x1 , x2 ) = x12 − 2x1 + x23 − 3x2
f (x1 , x2 ) = (x12 − 2x1 ) + (x23 − 3x2 )
f (x1 , x2 ) = f (x1 ) + f (x2 )
is separable fumction.
• The function
f (x1 , x2 , x3 ) = x12 + x1 sin(x2 + x3 ) + x2 ex3
f (x1 , x2 , x3 ) 6= f (x1 ) + f (x2 ) + f (x3 )
is not separable function.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 7 / 33
SEPARABLE PROGRAMMING
Reducible to Separable Form
• Some non linear functions are not directly separable but can be made
separable by appropriate substitutions.
Max Z=x1 .x2
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 8 / 33
SEPARABLE PROGRAMMING
Case I
Take y=x1 .x2 ,
Here x1 and x2 are positive variables.
Then,
ln y=ln x1 +ln x2
Hence,the problem become
Max Z=y
subject to
ln y=lnx1 +lnx2
Which is separable.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 9 / 33
SEPARABLE PROGRAMMING
Case II
This case, where x2 and x3 assume zero values,(i.e x1 , x2 = 0).
let ∂1 and ∂2 be positive constant,
Define,
w1 = x1 + ∂1
w2 = x2 + ∂2
w1 , w2 > 0
Now,
x1 x2 = (w1 − ∂1 )(w2 − ∂2 )
x1 x2 =w1 w2 − w2 ∂1 − w1 ∂1 + ∂1 ∂2
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 10 / 33
SEPARABLE PROGRAMMING
continued..
Let y=w1 w2 ,
Maximize Z=y-∂1 w2 − ∂2 w1 + ∂1 ∂2
subject to
ln y=ln w1 +ln w2
Which is separable.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 11 / 33
SEPARABLE PROGRAMMING
Separable convex programming
Definition
It is the special case of Separable programming in which the
separable objective function(in minimizing form) all separable constraints
(≤ type) are convex.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 12 / 33
SEPARABLE PROGRAMMING
Separable convex programming problem can be represented as follows:
Max/Min f(x)=f(x1 , x2 , ....xn )
n
X
= fj (xj )
j=1
subject to
gi (x) ≤ b
n
X
= gij (xj ) ≤ bi
j=1
i=1,2,...m. xj > 0,
j=1,2,...n.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 13 / 33
SEPARABLE PROGRAMMING
Pointwise linear approximation
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 14 / 33
SEPARABLE PROGRAMMING
Convert NLPP to LPP
• Here [L,U] is lower limit and upper limit.
•[L, U] → [r + 1]gridpoints.
• We express the grid points,
L = x0 < x1 < x2 ......... < xr−1 < xr = U
• letr we consider (k + 1)th is sub interval of [xk , xk+1 ].
xk < x < xk+1
any x can be express the linear combination of,
x=λk xk + λk+1 + xk+1 0 ≤ λk , λk+1 ≤ 1
Here,λk + λk+1 = 1
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 15 / 33
SEPARABLE PROGRAMMING
continued
•Let we take x is sub interval[xk , xk+1 ] and [xk+1 , xk+2 ]
•Any x can be express the linear combination of the ,
x=λk xk + λk+1 xk+1 + λk+2 xk+2 0 ≤ λk , λk+1 , λk+2 ≤ 1
•Here mmust be λk + λk+1 + λk+2 = 1
continuing the proceding,x0 < x < xr
Xr
x= λ k xk 0 ≤ λk ≤ 1
k=0
k
X
λk = 1
r=0
0 0
• Atleast one or no more than two λks are positive.Two λks positive ,they must
be concecutive.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 16 / 33
SEPARABLE PROGRAMMING
conitnued...
(k+1)th sub interval [xk , xk + 1] in to (xk , f (xk )), (xk+ 1, f (xK +1 ))
Equation of the straight line,
f (x) − f (xk ) f (xk+1 ) − f (xk )
=
(x − xk ) (xk+1 − xk )
(x − xk )
f(x)=f (xk ) + f (xk+1 ) − f (xk )
(xk+1 − xk )
f(x)=λf (xk ) + (1 − λ)f (xk+1 )
(x − xk )
above,(1 − λ) = ,
(xk+1 − xk )
f(x)=λk f (xk ) + λk+1 f (xk+1 ) whereλk + λk+ 1 = 1
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 17 / 33
SEPARABLE PROGRAMMING
Adjacent criteria
We consider (r+1) grid points,
r
X
f(x)= λ k xk 0 ≤ λk ≤ 1
k=0
where,
k
X
λk = 1
r=0
0
Atmost two λks are greater than zero.
they must be concecutive.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 18 / 33
SEPARABLE PROGRAMMING
Objective function
Xn
Max/min z= fi (xi )
i=1
subject to
Xn
gij (xij ) ≤ bj i,j=12,..n.
i=1
xi ≥ 0 i=1,2,...,n.
li ≤ xi ≤ xi
fi (xi ) and gij (xi ) expressed summation of linear function,
Xn X r
max/Min z= λik fik
i=1 k=0
r
X
fi (xi ) = xik fik
k=0
Where, fik = f (xik )
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 19 / 33
SEPARABLE PROGRAMMING
Constraints
The constraints can be expressed th linear combination of
ri
X
gij (xij ) = λik gijk (xik )
k=0
subject to
ri
n X
X
(λik )(gijk ) ≤ bj j=1,2,3....n.
i=1 k=0
Xri
λik = 1 0 ≤ λik ≤ 1
i=1
k=0,1,2,....ri
i=1,2,3....n.
fj andgij are also separable functions.
Adjacents critria λ-form equivalent to LPP.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 20 / 33
SEPARABLE PROGRAMMING
Algorithm
Step 1
If the objective function is of minimization form, convert it into maximization.
Step 2
Test whether the functions fj (xj )andgij (xj ) satisfy the concavity (convexity)
conditions required for the maximization(minimization) of non-linear
programming problem. If the condition are not satisfied, the method is not
applicable, otherwise go to next step.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 21 / 33
SEPARABLE PROGRAMMING
Algorithm
Step 3
Divide the interval 0 ≤ xj ≤ tj (j = 1, 2, ..., n) into a number of mesh points
ajk (k = 1, 2, ..., Kj ) such that aj1 = 0,aj1 < aj2 < ... < ajk = tj
Step 4
For each point xjk , compute piecewise linear approximation for each fj (xj ) and
gij (xj ) (j = 1,2,..., n; i = 1,2,...,m) .
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 22 / 33
SEPARABLE PROGRAMMING
Algorithm
Step 5
Using the computations ofstep - 4, write down the piecewise linear
approximation ofthe given NLPP.
Step 6
Solve the resulting LPP by two phase Simplex method. In this method, treat
λj0 (j = 1,2,...,ri) as the artificial variables and since the costs associated with
them are not there, these are assumed to be zeroes, the phase -1 of the two -
phase method is automatically completed. Thus the initial simplex table of
phase -1 becomes optimum and hence represents the starting simplex table for
phase - II
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 23 / 33
SEPARABLE PROGRAMMING
Algorithm
Step 7
Obtain the optimum solution x0 ofthe given NLPP by using the relations
X m
0
x = λjk (xjk ) i, j = 12, ..n.
k=0
and find optimum value ofthe objective function as follows
Xn
0
f (x) = f j (xj0 ) i,j=12,..n.
j=1
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 24 / 33
SEPARABLE PROGRAMMING
PROBLEM
Solve minimize x12 − 4x1 − x2
Subjext to 2x12 + 8x2 ≤ 30
0≤ x1 ≤ 2
0≤ x2 ≤ 2
here
f (x1 ) = x12 − 4x1 f (x2 ) = −x2
g(x1 ) = 2x12 g(x2 ) = 8x2
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 25 / 33
SEPARABLE PROGRAMMING
problem
Minimize
n X
X n
λij fij =−3λ11 − 4λ12 − λ21 λ22
i=1 j=1
Subject to
2λ11 + 8λ12 + 8λ21 + 32λ22 ≤ 30
λ10 + λ11 + λ12 = 1
λ20 + λ21 + λ22 = 1
λ11 , λ12 , λ21 , λ22 , λ10 , λ20 ≥ 0
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 26 / 33
SEPARABLE PROGRAMMING
Phase I
• In this method
λ11 , λ12 , λ21 , λ22 , λ10 , λ20
as the artificial variables and since the costs associated with them are not
there, these are assumed to be zeroes, the phase -1 of the two - phase method
is automatically completed.
•The initial simplex table of phase-I become optimal.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 27 / 33
SEPARABLE PROGRAMMING
Phase II
Table 1
Pivot elemet 1,The non basic variableλ12 enter the basic and the basic
variable λ10 leaves the basis.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 28 / 33
SEPARABLE PROGRAMMING
Table 2
Pivot elemet 1,The non basic variableλ21 enter the basic and the basic
variable λ20 leaves the basis.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 29 / 33
SEPARABLE PROGRAMMING
Table 3
Pivot elemet 32,The non basic variableλ22 enter the basic and the basic
variable x3 leaves the basis.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 30 / 33
SEPARABLE PROGRAMMING
Table 4
Since all (zj − cj ) ≥ 0, the current fesible solution is optimal.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 31 / 33
SEPARABLE PROGRAMMING
The optimal solutio is given by,
λ10 = 0, λ11 = 0, λ12 = 1, λ20 = 0, λ21 = 9/16, λ22 = 7/16
x1 = 2
x2 = 1.4375
Optimal value of objective function
Min f(x)=-5.4375.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 32 / 33
SEPARABLE PROGRAMMING
Reference
[1] RK.Sharma:Operations Research:Theory and Applications,Macmillan
Publishers India Limited·2009
[2] C.E.Miller:Recent Advances in Mathematical
Programming,McGraw-Hill publishers,1963
[3] S. Hiller,G.J. Lieberman:Introduction to Operations Research, 7th edition
McGraw-Hill publishers.1967.
[4] Dimitri Bertsekas:Nonlinear Programming,3rd edition Academic Press,
1978
[5] K.Rajagopal:Operation Research,PHI Learning Pvt. Ltd.
Viyasar Mouly(M190659MA) (NIT Calicut) Separable programming 16:20, December 3, 2020 33 / 33
