0% found this document useful (0 votes)
80 views29 pagesInteger Programming in Finance
Uploaded by
Debasish TuduCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
80 views29 pagesInteger Programming in Finance
Uploaded by
Debasish TuduCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 29
10
Integer Linear Programming
(Gomory’s Cutting Plane & Branch-and-Bound Methods)
10-4. INTRODUCTION
As ake name implied ‘Integer Linear Programming Problems’ are the special class of linear Programming
problems where all or some of the vatiables inthe optimal solution are resisted to non-negative integer values.
Such problems are called as ‘all nteger’ or ‘mixed integer’ problems depending, respectively, on whether all or
Some of the variables are restriced to integer values.
Jone might think it sufficient to obtain an integer solution to this special class of linear programming
problem by using regular simplex method and then rounding off the fiaetivel taloes ane occuring in the
real Solution, But in some eases, the deviation from the “exact” optimal inieger vies (as a result of
Founding) may become large enough to give an infeasible solution. Hence thee
clever idea of constructing “secondary” constraints which, when oat ‘non-integer) solution,
should geen ut the solution space towards the required result. Successive applicant nee
solution val fee the now-integer opium solution toward the desired "allimeger” or ace nae
solution
ed ineeemant approach, called the “branch-and:bound technique” for solving both the all-integer and
ener acitseer problems, has ongnaed the straight forward idea of nding al enabie me sens
SE Lan aan Cr NRE al integer” and ‘nixed integer" liner programming problems Nerden ke
Cp probes AG. Pei (1960), Also, Egon Balas (1963) troduced an ntrestng cromorafte nee ee
LE problem with the variables having the value zro or ona called the era one prose ehee
fer ne areas have been developed so fr for solving te integer programmring protien: eg, in this
Shaper, we shall discuss only two methods: (i) Gomory’s culting plone note nt Gi) Branch-and-bound
‘method.
102, IMPORTANCE OF INTEGER PROGRAMMING PROBLEMS
CGnRY? alteady pointed out earlier that most industrial applications of large scale programming models are
Mrduaty thang ROME decisions, There are several frequenly occurs; cane eae ng model and
industry that lead to planning models involving integertaluel, oaths eee example, in production,
frequently scheduled in terms of batches lots ot tune In allocation of sont a shipment must
be menace muee of trucks, freight cas o arerafs. In such cases, the formal eae of ee may
2 hana sos the contort ofthe actual dcisign problem, For sxarapes ts tor neat oe oe es NY
thermal power station, 10-4men in a project, or 5:6 lathes Ih awerken eal
ling
nods)
unming
values,
all or
mming
in the
‘sult of
velop a
tion to
case of
‘These
use of
ces the
slution,
straint
ueger’
rerand
ons. A
ped by
hm for
in this
hound
els are
ss and
sction,
tmust
smay
lers in
Unit 2: Integer Linear Programming 27
Many other decision problems can necessitate integer programming models. One category of such problems
deals with the sequencing, scheduling and routing decisions. An example is the travelling salesman problem
Jick aims at finding a least distance route for salesman who must visit each of n cites, starting and ending
his journey at home city. Larger expenditures of capital and resources are required in capital budgeting
decisions. This i the main reason why integer programming is so important for marginal decisions. An optimal
solution toa capital budgeting problem may yield considerably more profit to a firm than will an approximate or
guessed-at solution. For example, ferilizer manufacturing firm with 15 plants may be able to substantially
Increase profits by cutting back to 10 plants or less, provided this reduction is planned optimally.
10.3, WHY INTEGER PROGRAMMING IS NEEDED ?
We might think it sufficient to obtain an integer solution tothe given LP problem by frst obtaining the
non-integer optimal solution using regular simplex method (ot graphical method) and then rounding of the
fractional values ofthe variables. But, in some cases, the deviation from the “exact” optimal inleger soles
(obtained as a result of rounding) may become large enough to give an infeasible luton: Meee ee
acoessary to develop a systematic procedure to determine the optimal integer solution Io each protic en
following example will make the concept more cleat
The question “why integer programming is needed ?” can be more easily answered through the following
illustrative example.
Consider a simple problem : Max. z= 10x + 4x subject tothe constrains
3a, 4419S 8,21 20, 5320, and x, x2 a7e integers.
First, ignoring the integer valued restictions, we obtain the optimal solution
#.42=0,max.2=262, by using “graphical method. ‘Then, by
rounding of the fratonl valu of x)= 25, the optimum sluion becomes,
21=3,%=0 with max, z= 30, But this solution does not satisfy the
Constraint 3xy + 4x» <8 and thus this solution is not feasible. 3
Now, again, if we round off the solution to x, =2,x)=0 , obviously
this is the feasible solution and also integer valued. But, this solution gives
20 which is far away from the optimum value of z= 262. So, this is
another disadvantage of getting an integer valued solution by rounding
down the exact optimum solution, Still there is no guarantee that the
“rounding down” solution will be an optimal one because it may be far away
from the optimum solution,
‘Thus, a systematic procedure for obtaining an exact optimum integer
solution to integer programming problems is needed,
We shall now give the formal definitions of integer programming
problems,
104. DEFINITIONS
Definition 1. Integer Programming Problem (L.P.P.). The linear programming problem : Max 2 = CX , subject
{0 AX = bX 20 and some x; X are integers, where C,Xe K",be R” and a is an m x n real matrix, is
Calted an Integer Programming Problen. abbreviated as LP.
Definition 2. AU Integer Programming Problem (All LP.P.). An integer programming problem is said to be an
“All Integer Programming Problem” ifall se ¥ ae integer
Datfinition 3. Mixed Integer Programming Problem (Mixed L.P.P.). An integer programming problem is said to
be ‘Mixed Integer Programming Problem’ if not all x, = % are integers.
1. State me goneral fom of an integer programing probiem
[Meerut Se. (Math) 98; Madurai 8.Se. (Appl. Math, 85]
2. Distinguish between pure and mixed integer programming prosoms, [Madurai B.Se. (Appl. Math.) 83} « called
‘ut does
a. fall
aumber
straints
ted as
ations,
-m)
«this
01)
aye
tive
Unit 2: Integer Linear Programming
Now substituting above values inthe eqn. (10-1) for x;, we get
or Sa
Now for all the variables x, i= 1, 2,
wm) and xj (j=m-+1,
279
femch, ]
v7
2
0
aa ees ve
Gitta) 2 Metis 402)
Eten tay £ hay (103)
«n) to be integer valued, the right hand side
of the above equation must be an integer. This implies that lefchand site
‘must also be an integer. Since 0-
i (Cont)
ee Operations Research
eer ae 7
1 ove ae |
ar te]
} ‘The optimum solution thus obtained is: =4! x, =3! sp 63
pend
Step 3. Since the optimum solution obtained a above i not an integer slution becnuse of xy <4 Hand x»=3!,
we goto next step.
Step 4. We now select the constraint conesponding to max a) =max. fy fn)
Since sa1= dn vfnn=34+}.00d ny = len + fin = 441, weave fp
{he two equations can be used. Let us consider the equation, ie, fis-r0w of optimum rable
Step 5. Negative fraction does not exist
Step 6. To Construct the Gomorian Constraint.
Hence, max. (fp) fa) = max.
‘The Gomorian constraint is given by, =f) 528, fists:
Here m=2,2=4,i=1, ‘Thus above constraint becomes
win=~ 2, fyayte, © ~fn=~ fissures (ince x. xsare slack variables) ar
Substituting the values : fs = 742 , fi
V2 fa = V4. we got the required Gomorian Constraint as
37 0, being non-basic) |
ge-3 sete Gyeaxy
pbiously the cosfficints of remaining variables x, and x in the above Gomorian consiraint will be taken
0. Thus complete Gomorian Constraint can be written as
1,1 {
~ 720 +0y-25-Sate,
Adding this new constraint to the Optimal Table 103, we get the new Table 10-4. 1
Table 104
o> 7 so oo
[Basie Ce X[K i
VARIABLES
° 1 77 17a
>
1 0-122 sree
oo 77a] ~ 1728 | 1
° Oat ast
t
Step 7. To apply dual simplex method.
) leaving vector is Gy, ie, By. Therefore r=3
(ii) Entering vector is obtained by
‘Therefore, =3. Hence we must enter the vector ay corresponding to which X is given inthe above table, a OM
=, Unit 2 Jateger Linear Programming 283
‘Thus, we get the following transformed table.
Table 105
Soe 0 eee
BASIC Ce x | Xe Xs uy Gr
VARIABLES. pans
: Fs eso oe cea
Bb 0 08 ww laa
0 1 ov |e
[te Deesaeraiatieemal al
eof As= C361 —¢5= (9, 7,0) (1, -1,-2)-0= (9-140)
‘The non-integer optimum solution given by above table is: = 48 4y=3 .2y= 14
Step 8. The optimal solution as obtained above by dual simplex method is sill non-integer. Thus, a new
Gomery's constraint i wo be constructed again. Selecting r-equation (Le. nd row af above rable) o
generate the cuting plane (because largest fractional part can be fgz=fnr=8) , we get the Gomory's
constraint as
Es or $204, 409405 -! $e) 442
J Adding this constraint tothe above Table 10-5, we get Table 106
Table 106
go 7 § 6 0 0 96
BASIC Ce Xe | Xe XS Xe) Gr Ge
| variates |
aken % ap ag] ot
| os 7 1 0
x ° o 0
[ca or omaeteT
cas 7
‘We again apply dual simplex method,
() Leaving vector is G (ie. B,) . Therefore, r= 4
Gi) Entering vector will be obtained by
P A [& 4S) max I
max,
aes,
s be
me a7 rer a
Therefore, k=-4, Hens we mt xy conesponding which, given nthe above ee, Thus we ge
detente ihn BESSE
Table 107
7 gan fol Oil td ae un
SASIEVAR [Ga Xe
2 23 ot 0 Ta o |
ete taco fo ns
: woo 4 ia eo 2 ol 4
paisa |Get Woe ic to esi aloe
2= CeXe = 55 o o o 7 EEO
284 Operations Research
2.7,0,00,
= CyGz— C= (9, 7,0, 0) (0,1, 1-1
‘Thus, finally we get the optimal integer solution : x, =4, x2=3, max
‘Verification by graphical method :
It can be easily verified that the addition of the above Gomory’s constraints effectively ‘cut’ the solution
space as desired. Thus the Gomory’s first constraint
|, = 4,6) -0= (9 -74040)=2
0+7+040)=7
55.
can be expressed in terms of xy and zz only by
substituting
6s a $= T\—n3
from the original constrain equations treating g
asa slack variable in tep2
This gives g1¢-12=3 oF 23, wating fy
as astack variable.
Similarly, for the Gomory’s second
constaint—y~8 81482
Bay and x
ue
the equivalent constraint in terms of 1) and.x is
obtained as x, +4) $7.
Now plotting the Gomory's constraints
xpS3andx;+%S7 in addition to the aster
constraints of the given problem, we find that it
will result in the new (optimal) extreme point (4,3) as shown in Fig. 10-2 |
Example 2. Find she optimum integer solution to the following all LPP = |
Mae a=, +2xy subject to the constraints 2x £7.m+%2S7,2n $11.52 0.220, and ¥ 22 oe |
inmegere fudyosagar 97; Shiv M.Se (Math) B; Maas Se, (Math) Bt BY; Mada B.S. (APP: Math) 9]
‘Solution. Step 1. Introducing the slack variables, we get
2 #3 7 '
mem tu = 7 |
an +21
Hr 8514 SZO.
Step 2. Ignoring the integer condition, we get the initial simplex table as follows +
|
Table 108 |
Aeon ni | feiene) a Tone alo, |
ae oc as po im ee | MNTRATO f
VAR. ar) |
on) 7 °. (3? © o Tee |
a oe an eerie ge nem ce |
| s o 2 o o o 4 I
cee ‘i
fo 2
Introducing X; and leaving x, from the basis, we get i
areh
ation
1983)
Unit 2: Integer Linear Programming 28s
Tobie 108
_ 1 pie mech OE abo)
‘BASIC Xt xy %& Xe Xs MIN
VAR. - oe /%)
* ° 1 wo of}—| ‘
on M 0 -w 4 Die
zo oo 1 | 2
naa ane j
| 7 L J
(2,0,0) (0, 1,2)— 0,0) G 1
Introducing x, and leaving X,, we get the following optimum table.
Optimum Table 1010
ae qt 2 9 o_o
BASIE | Ce ua Xe
VaR.
” |
*
“4
“The optimum solution thus obtained is: x1 =34, xp
Step 3. Since the optimum solution obtained above is not an integer solution, we must go to next step.
Step 4. We now selec the constrain corresponding tothe criterion
‘maxi (fn) = max (py fen» fin) = max (3.5.0)
‘Sines in tis problem, the zy-equation and x,-equation both have the same value off. ether one
of the two equations can be used. Let us consider the first-row of the above optimum table.
‘The Gomory’s constraint tb be added is therefore
~ 3 fuse or fists fists 81 =— fn
ay Ore or -Laytgi=-20s=0=0)
‘Adding this new constraint to the optimal Table 10-10, we get the new Table 10-11 .
Table 10:11 . New table after adding Gomory constraint
om 1 2 o ° o °
BASIC ] Ce Xe mM NX OX)
VAR.
= eZ a ° 7 0 ° °
2
x 1 a i 0-1 4 ° °
L_« [04 o 01 2 fe
a o 7 Sa] Ea 5
| zecxe-10! [ © 0 ve 7 oma
2 i | a maeoes |
Step 5. To apply dual simplex method, Now. in order to remove the infeasibility of the optimum solution
l y=3), x= 3! 2524, g)=—3., we use the dual simplex method
| (i) Leaving vector is G, (@.e., By) . Therefore, r:
4 Gi) Entering vectors given by
Ay fy ;
max.
‘Therefore, k= 3 . So we must enter aj corresponding to which X; is given in the above table, Thus, dropping
and introducing X, we get the following dual simplex table
‘Table 1012
eee
i Ag=CyXe— €4= 2, 1,0, 0) (0, 1, -2,0)-0= 1, Ag= Cr
This shows that the optimum feasible solution has been obtained in integers. Thus, finally. we get the
integer optimum solution to the given LP.P. as :x; =4 x) =3 and max z= 10
105-4, Short-cut Method for Constructing the Gomory’s Constraint.
‘Afier obtaining the non-integer optimal solution by simplex method, we perform the following step-by-step
procedure to construct the Gomory's constraint
Step 1. In the optimal simplex table (vith all 20), frst select the row corresponding to such basic variable
1 ‘which has the maximum fractional value. If more than one basic variables have the same maximum
- factional value, then we can select the rove coresponding to ether of these basic varihles
F In Example 1, (se2 Table 103 with all A;20) bob te basic variables x3 and.x; have the same
fractional value (ke, 2.4 ). s0 we can select either xprow or xrrow, In ths case, we have
selected xz-row, Le.
fe oat 2 zl Te ee
Step 2. In the row selected above we express cath number in two pars Fit part faust bean integer and
i ‘Edna art mat be a non-negative ration, Thus applying thi stp to above selected row, We get
O40" 140" oraveey On a/aa"
e334 12)
Here non-negative fractional values are marked with **"
i Step 3. Then, we write the negative of the fractional values which ate marked with ‘*” in step 2. Thus, the new
row corresponding to Gomorian slack variable gy becomes
i Wee 18
ook s co
‘This row can be directly added to the optimal simplex table with Gomorian slack variable g1 as I
additional basic variable and immediately we increase the dimension of basis matrix by introducing one
‘more unit matrix column Gy
Obviously, above constructed new row will give us the Gormorian constraint atthe
v-step
riable
same
have
B08
agone
Unit 2 : Integer Linear Programming 287
1 2
22 OH On Fas— are or Oy +0 - Zs
B
After introducing the new row correspk
‘method to proceed further.
Above outlined prodcedure will be very
‘construct a Gomory's constraint
Example 3. Solve the foliowing integer programming problem
Max. 2= 2x + 20% — 10x, subject to the constraints +
2x) + 2Oey + 4x5 $15, Gry +20) + 445=20, and x, 2,252 0; and are integers.
Solve the problem ax a (continuous) linear program, then show that it is impossible to obtain feasible
integer solution by using simple rounding. Solve the problem using any integer program algorition.
[Sri Venkt. So. (Stat) 77)
Solution. Introducing the slack variable x20 and an artificial vatiable ay 20, an inital basic feasible
solution is ug= 15 and a) =20
Now computing the net-evaluations
table is obtained.
onding to the Gomorian constraint, we apply usual dual simplex
convenient 1o apply directly (orally) whenéver we need to
(4) and then using simplex method, the following optimum simplex
Optimal Simplex Table 10:13,
o> 2 20 -10 °
BASIC | Cs Xe x % % x]
VARIABLES | |
[os [= we . 7 oe
m | 2 5/4 1 o oO
(a Se ae + ea
a 2s ee
‘Thus the following non-integer optimum solution is obtained
4159/4, x)= 5/8 ,25=0,max2=15
The rounded solution will be x) =1,42=0,23=0
Since this solution satisfies the first constraint only, iis not possible to obtain a feasible solution by using
simple rounding, Soto abtan the integer-valued solution, we proteed es ollone +
31) 5
Max. (fa fn) =Max. & 3 5.
‘Therefore, from the fist ow of optimal table, ws have
aOhrmtintiny
or 04) =O+ 0) +1 40)5 +04) 54043
“The comresponding fractional cut will be —
F50n +06 -Fay- Fata
Now inserting the additional constraint in the optimum simplex table, the following modified table is
obtained.
Table 1014
2 20
ca %
° 7
1 °
bre---s7
° 288 Operations Research
First Iteration, Remove G, and insert x, by dual simplex method.
Table 105,
eo 2 20 =10 ° 0
BASIC] Ga % Xs oA % % | G |
\VARIABLES| i
[2 | = o | oO 7 e ° 7
x 2 wa | 1 ° 28 0 | -108
va o 25/8 o ° 33 1) -a07a
[20 0 0 3/3 0 Ae a
‘Again, since the solution is non-integer one, insert one move factional cut, From the third row of Table
1015,
25/32 8/3 x5 +44- 40/3 gy
or (84 1/9)=Q+2/3) xy + (140) x¢4 6 14+2/3) 8
‘The corresponding fractional cut will be ~ 1/3 = Ox, +0x ~2/3.x5+ Oxy 2/3 1+ 82
Inserting this constraint in Table 10-15, the following modified table is obtained.
Table 1016
q> 2 mo ° °
& % | & Me % | @ Ge
a3 7 common aed 3
ws | 4 nr a
mate os BA °
Sia] 0 a [Seay ot +
2008 g CT vem
* jaan
2 dual simplex method remove G, and introduce %-
Table 1047
2 » -0 o ° °
Re TY
0 T 0 or 7 0
1 ° ° re
° ° ° 1 fo 4
0 ° 1 o 1-32
3 ® @ a 2 ies
Still non-integer, a third fractional cut is required, From the last row of above table, we
‘can construct the Gomorian constraint—1/2=— 1/2.a2+ &s
Inserting this additional constraint in the above table, the modified simplex table becomes
Table 1018
q> 2 2% -0 o 0 °
BASIS | Ge XS |X OT Gs os earch
Table
bie, we
Unit 2 : Integer Linear Programming 289
Third I
ration. Using dual simplex method, remove G, and introduce G,
Table 1019
= a> wo o 0 °
BASIC] Ca Xe % | & G& G |
VAR.
= | 2 70 °
o 2
° e
eae
“4
Example 4. The owner of a ready-made garments store swo types of shirts known as Zee-shiris and
Butron-down shirts, He makes a profit of Re. I and Rs. 4 per shirt on Zee-shirts and Button-down shirts
respectively. He has two Tailors (A and B) at his disposal to stitch the shirts. Tailor A and Tailor B can devote at
the most 7 hours and 15 hours per-day respectively. Both these shirts are to be stitched by both the tailors
Tailor A and Tailor B spend two howrs and five hours respectively in stitching Zee-shirt, and four hours and
three hours respectively in stitching a Buttonsdown shirt. How many shiris of both the types should be stitched in
order to maximize daily profit ?
(a) Set-up and solve the linear programming problem.
(0) If the optimal solution is not integer-vatued, use Gomory's technique 10 derive the optimal integer
solution, {Delhi (MBA) 72]
Formulation of the problem. Suppose the owner of ready-made garments decide to make x, Zee-shirts
and x, Button-down shirts. Then the availability of time to tailors has the Following restrictions
Wy +4y <7, Sy+3qS15, and my 20
‘The problem of the owner is to find the values of x and x, to maximize the profit z=, + 4x2
Solution. Introducing the slack variables x;20 x4 20 in the constraints of the given problem, we have an
initial basic feasible solution : x; =7,x4= 15
Computing the net-evaluations 4, and using simplex method an optimun solution is obtained as given in the
following table.
Table 1020
oo 1 4 ° °
BASICVAR, | Ce Xe % % 8 Xe
7” 4 374] 12 1 vs °
xe o son | 72 oa ra
i ° i ° oy
‘Thus a non-integer solution is obtained as : x; =0 , x
‘To find the integer valued solution, adda fractional eut constant inthe optimum simplex table, Since the
fractional pats of % are [3,3], select the row abitaily. So fg:=2. Thon fom the frst row ofthe Table
10-20, we have
(4920+) 4140n+O+)n +040) x
‘The corresponding fractional cutis therefore given by
321
a0 =n +0042) |
ao Operations Research
‘Now inserting this additional constraint inthe optimum simplex table, the modified table becomes.
Table 1024
eee a }
[Basicvan [ce mT |
= 4 7 nn rr
Ps oT o we o 34 1 1
[ow 0S tae ay oe TT |
ZT ip) ae ipa ar |
t
|
First Iteration. Using dual simplex method, remove G, and insert Xy
! Table 1022
oem Ueal pee aioe a
| BSC | Gm | % % & | Gr
i VAR. i |
i = |e t,o 4 7. |
yr m | o 2 | 0 0 -s2 + |} |
a m 1 san 1 0 617 0 1 | |
Ee +- zz 2 ° 12 ° 2 | 4 |
} ‘Again, since the solution is non-ineger one, insert another fractional cu in Table 10:22 From the third row
of above table, we have (1+) =(1-+0)x, +0+0)x9+ (0+) x +040) +240) 81 |
“The corresponding fractional cut will be -!= 0x; + 0x —1x5 + 0x +081 +82
‘Now inserting this additional constraint, the modified table becomes Table 10.23.
Table 1028
et
BASIOVAR, %
= °
% 1
s ° i
} eee 5 |
lan 0 a |
I |
Second Iteration. Using dul simplex method, remove Gand inser X,
Table 10.28
oo 1 4 0 oe i
BASCVAR. | Cs Xe | MX iS
Ms = aoe te to
4 4 o 7]0 o o loz. 5
a 1 1 1 oO 0 | -2 1
2 0 Lo oa Vo -2
z5) o o ° ae teal search
ind row
Unit 2 : Integer Linear Programming 291
This gives us an optimum integer solution : x,= 1 .xq= 1, and max
‘Thus the owner of ready-made garments should produce one Zze-shirt and also one Button-down shirt in
order to get the maximum profit of Rs. 5
Example 5. A manufacturer of baby-dolls makes two types of dolls : Doll X and Doll ¥. Processing of these
‘vo dolls is done on two machines A and B. Doll X requires two hours on machine A and six hours on machine
B. Doll ¥ requires five hours on machine A and also five hours on machine B. There are sixteen hours of time
per day available on machine A and thirty hours on machine B. The profit gained on both the dolls is same, ie,
‘one rupee per doll. What should be daily produetion of each of the two dolls ?
(a) Set up and solve the linear programming problem.
(b) If the optimal solution isnot integer valued, use Gomory’s technique to derive the optimal solution.
[Bharathiar M.Sc. (Math) 8; Delhi (WLB.A) 73)
Formulation of the problem. Suppose the manufacturer decides to produce 2, dolls of type X and x» dolls
of type ¥.. Then availability of time on two machines has the following restrictions :
In +5516, 6x +5%S30, and x ,1220
‘The manufacturer wishes to determine the value of x, and x so as to maximize the profit <= Rs. (x; +2)
Solution. Introduce the slack variables x52 0 and x, 20 in the constraints of the given L.P. problem. An
initial basic feasible solution is x5 = 16 and x, = 30. Now using the simplex method, the optimum solution is
obtained as given in the following table :
‘Table 1025
>t
EASIOVAR [a Xe
” 1 388
x 1 12
zs 0 “a
‘haven elton ieg aon
Since he fractional pars of ar[$,1]andmax[ 3,
049 =040) 44040) n+ 0+D tC 142) x
‘The corresponding fractional cut is given by
=
2
1] a4, ebreforo from he frst of above abe,
0m, +0m— 2. ~ Satay
‘ow insrting th adtonal comer int ha optimum shplex table, the modified table Becomes,
Table 1028
eA
BASICVAR[G— Xe [Xe xa]
oe 1 5 0 1 ano 1/10; 0
x 10-4 vs to |
[9 fo 46 [0 70 7-80 Est 7)
zee [oe ia ago te) way
| eit
First Iteration, Using dual simplex method, remove G, and introduce X,
Table 1027
gee ea
([BASICVAR [Co __‘%e_]_& Xe e et Gr
2 1 We] 0] ,
x + sme] 1 0-18 0 | ene
xu o see] 0 0 a_i _! ow
f.. ut 2281/6 oO 0 o 0 ve | ea a |
$
tb
292 Operations Research
Since solution is still non-integer, insert one more fractional cut in the above table. From the third row of
above table, we have
“The comesponding factional cut becomes :~$
Inserting this additional constraint, the modified table becomes :
Table 1028
a> 4 1 °
BASIC | Gy Xe
VAR.
@ 7 7
x 1 8018
o 89
TP 7 tae
23178
ing dual simplex method, remove G, and insert X,
‘Table 1029,
1 oe 0 ©
Bee Xe Xs me T Gy G
[ 1 o o | -t 1
x po 0 0 tae 1
mu oo 1h ne 1
a ° 1 o jas -3
o Ce a
‘This solution i also nomintoger one, 50 insert one more fractional ext. The fractional parts of %Xy are
[fo] amt max [2] =2. Tereore, fom the last row ofthe above abe, we have
040) 4040) +140) OF A HD a +CO3 +082
y
jot OB +8
2204 +05 + 0% + 054—
‘Now inserting this constraint, the modified table becomes:
ae
rad *
" ;
:
1 » A
e 3
3 Ea
‘Third Iteration. Using dual simplex method, remove Gy and introduce G,
u search
row of
Unit 2: Integer Linear Programming 293
Tobie 1031
wed 4g ee
BASCVAR [Ge [x me ee
we 1 = of ° o | oO 1-3/2
* 1 3 1 0 o 0 ! 0 10%
» [oe ofo 0 + oj }0 -3 4
eMC eal NOEi 8 pala eae
za5 0 0 0 O10 0 w]e
‘This gives the optimum integer solution :%j=3,xy=2and max 2=5
Thus, the manufacturer should produce 3 dotls of type X, 2 dolls of type Y in order to got the maximum
profit of Rs. 5.
Note. Alterative soltion ae:
sn=Oiadn=4.n=1
10-6. GEOMETRICAL INTERPRETATION OF GOMORY’S CUTTING PLANE METHOD
The geometrical interpretation of cating plane method can be easily understood through a practical
example.
Lt us consider the problem of Example §
Max. 221 +25 61024 + 5t2 516, 6x1+ 8% $30.21. 20. x
‘The graphical solution of this problem is obtained in Fig.
103 with solution space represented by the convex region ABC.
Te optimum solution occurs a the exteme point Bie
5 a2= 1.8 max2=53
But, ths solution is not intoger-valued. While solving this
problem by Gomory's method, we introduced the frst Gomory's
constraint: ~3n-Sus-$
1m order to express this constraint in terms of x and x3
make use of the constaint equations : 25+45% +m
and 6x +582 += 30,
‘whore x and xq are slack variables. From these, we get
X3= 16 — 2x) — 5xz and x4=30-6x - 5x),
“The Gomory’s constraint (then becomes
26-2 ~Su) 8. G0-65—Sn)S-$ ie, ptm <5
‘This constraint cuts off the feasible region and now the feasible region is reduced to somewhat less than the
previous one as shown in Fig. 103
Similarly, the second Gomory's constraint is gy 21. But,
+81
a= patho
4 die
Substituting the values of x, and x, from the constraint equations of the given problem, we immediately get
815 31.8— Gr, ~ Gry. Therefore, 318-65 — 6,21 (v g21) or +x $5103.
‘This constraint also cuts off some space of the feasible region. Since this constraint very minutely cuts off
the solution space, so it has not been plotted on the graph. Because of such euttings, this method was named as
cutting plane method. 398 Operations Research
EXAMINATION PROBLEMS
san te optim integer solution ole tong al ious" PSOne problems :
4. Max zo xt 2, subjectte ee aemian 2 X\~ 2 - Sub}ect ©
gay -20055 an +205 15
x22 e2 0 and integers
Jez 0, 20. and are integers.
{Meerut M.Sc. (Math,) 94; Puniabi
{Meerut Wise, (ath) $2; Macursl B..
tans. 20-1
par)
W-Braneh ant
(wath) 741
{ded Engg,) 2, B.Sc. (Math) 78)
max
407, THE BRANCH-AND-BOUND METHOD
problem. ynont general ecinigue forthe solution 6 LPP.in
by their upper oF
‘The general
and then the original problem is
conditions on one
Hower bounds or by both. This
‘of ts integer variables
‘we shall have,
‘Any feasible integer value, therefore,
ay Stal
mutually exclusive and thus canpot
‘These two constraints are
‘This section deals with the algorithm given by 1
troblems. Why this method is given the nar “bran
Technique is now
‘einger constrained variable whose optimum consinuous ‘value 3 is
welsystylt}
rust satisfy one of the wo
or 32014).
te tue simultaneously and hence both cannes
{Madurai B.Sc. (Appl Math.) 2]
'3,m2=0,max 2=3]
fans. 4132222, max z=5]
3, Max 2=Sr, subject © Max 22 + 5ie, Subject
9x)420057 wat 10m S20
xy-m>-2 my 52
xi 2220 and integers yy ez 0nd integers.
Tine Simplex method gives he integer solution] Ane. x =2, 227 max z= 7]
fans. =0,22=2.maxz= 8)
Man z= 2x +20, subjeet othe consis 6. Max 224m +38, subjectto te constants
sx +9058 ns eesd
mtoes erase
iy 20 0 and are integers ie m2 2 0nd a9 integer:
aara 98 Macural W.Se. (Appl Math) 83) (agra 99)
taeeag a ao 1 andmax z=] (ane xn 9 e220, maxz= 12]
7, Man z=Sxi + 4, subjectio the constants fe Max Za11%1 447, subject to the constrains
ax +2058 aa toe sd
x4 4x22 10 sn +205 18
je ae 0 and are integers 2x4
Tana. 20,22>4 max 2=16) seo, 1g 2 0 and are integers
meer 50-83 Madras B.Se, 85; ITULTA=H) 9)
fans. m= 2 ,70=9,maxz= 38)
2. Max z= m ~ 22, subject the constnts go, ane zany 22+ 5x, subject tothe cones
meee. Bu 22k + 739528
Gx + 20059 fey +512 + 59530
2920 ,and are integers pe ne 1920 ard ave iogers.
{Medural BE. (Mech) 78)
Ait Gergios mata gvesthe eter soe
Teheran nO, 20,204 ax 2°20
.d Bound Method
rnd and Doig for solving the allinteger and mixed-integer
‘n-and-bound will
‘which a fev or all the variables
discussed below.
Gea of the method is to solve the problem (St sentinuous Linear programming PtOD}c
‘partitioned (branched
hat currently has a fractional
The made clear in the following sections
‘are constrained
gm otto. sub-problems by Imposing, the ‘integer
‘optimal
‘obtained in terms of
value. Let x) be an
‘a fraction. Then clearly
conditions:
te inmoduced in the integer programming proven ne ats necusly, BY introducing these CONSTR. by one
oe acontinuous linear programening problem,
‘we shall have ©¥O
Yb problems, botb being integer-valued
ee nts
hy eo}
strains
baton)
teger
tions.
ained
sblem
iteger
an
learly
annot
y one
Unit 2: Integer Linear Programming 295
‘After branching in this manner, two sub-problems are constructed by inserting j$ (xj) and 32 [x6] +1
‘one by one to the original set of constraints.
‘To be definite, lt the mixed LP-P. be :
Max.e= 3, gy, sett te consis: (106)
Bagh, for 121.2, (10
ié
wee syininoger valued forj=1,2,. ECE, (10%
ans 320 or fol. b keh yn (109)
In addition to above, Jet us assume that for each integer-valued variable xj lower and upper bounds ean be
‘assigned so that these bounds surely contain the optimal values
1,S3)S Uy for J=1,2,....k (10-10)
‘The following principal idea is behind the ‘branch-and-bound technique we are looking for
Let us consider any variable x; and let [be some integer value such that Lj $1 Uj~ 1 . Then an optimum
solution to the problem (10-6) through (10-9) also satisfies
either the linear constraint x2 1+ 1 ao)
or the linear constraint xj&1. 10-12)
‘To explain how this partitioning helps us, suppose we have overlooked the integer condition (10-8) and
obtained an optimal solution to the LPP. consisting of (106), (107), (108) and (109) indicating 2 = 13 (or
example) Obviously x= 13 gives the range I-<3y <2.Therefrc in an integersvelued solution, we must have
either) <1 or 422
‘Thus there will be no integer valued yet Noiiper veil xt nee
feasible solution inthe rogion x1=1 101=2 —leE—E
as shown in the following figure.
Now our problem is 0 search for the 1 2
optimum value of 2 either in the first region Fig. 104
(6:51) orin the second region (x, 22).
‘Thus we formulate and solve the following two sub-problems separately :
‘Sub-problem (1) : consisting of (10-6) (10-7) ,(108) and 2. In addition to a lower bound z; we also have 2 master list of linear 296 Operations Research
reer ne Problems to be solved differing oly in the revision of the hounds (10-10) Atte fist iteration, the
‘master list has only one problem consisting of (10-6), (10-7), (108) and (10-10).
‘The step-by-step procedure at this th (r= 0, 1, 2,..) iteration ean be outlined as follows :
Step 1. Two possibilities may arise at the 7h iteration
{2M the master list dees not contain any linear programming problem (i. empty), stop the computations e
(8) Otherwise, goto step 2 for removing a linear programming problem from the masts Her
Step. 2. Solve the chosen problem to obtain the optimum solution by using bounded variable technique. Again
‘two possibilities may arise
( Withas no feasible solution, or ifthe resulting optimal value of the objective function z is