OperationsResearch

Unit7

Unit7

IntegerProgrammingProblem

Structure

7.1.Introduction
7.2.AllandmixedI.P.P
7.3GomorysallI.P.Pmethod
7.3.1ConstructionofGomorysConstraints
7.4.AllI.P.Palgorithm
7.5.BranchandBoundtechnique
7.5.1Branchandboundalgorithm
7.6.Summary
TerminalQuestions
.AnswerstoSAQsandTQs

7.1 Introduction
TheIntegerProgrammingProblemIPPisaspecialcaseofLPPwhereallorsomevariables
are constrained to assume nonnegative integer values. This type of problem has lot of
applicationsinbusinessandindustrywherequiteoftendiscretenatureofthevariablesisinvolved
inmanydecisionmakingsituations.
Eg.Inmanufacturingtheproductionisfrequentlyscheduledintermsofbatches,lotsorrunsIn
distribution,ashipmentmustinvolveadiscretenumberoftrucksoraircraftsorfreightcars
LearningObjectives
Afterstudyingthisunit,youshouldbeabletounderstandthefollowing

1. Attheendofthisunitastudent:
2. FramesaI.P.P.
3. SolvesaI.P.P.duringGomorysmethod.
4. Appliesthebranchandlandtechnique.

SikkimManipalUniversity

112

OperationsResearch

Unit7

7.2 AllAndMixedIPP
Anintegerprogrammingproblemcanbedescribedasfollows:
Determinethevalueofunknownsx1,x2,,xn
soastooptimizez=c1x1 +c2x2 +...+cnxn
subjecttotheconstraints
ai1 x1 +ai2 x2 +...+ain xn =bi, i=1,2,,m
andxj 0j=1,2,,n
wherexj beinganintegralvalueforj=1,2,,k n.
Ifallthevariablesareconstrainedtotakeonlyintegralvaluei.e.k=n,itiscalledanall(orpure)
integerprogrammingproblem.Incase only someof thevariablesare restricted to takeintegral
value and rest (n k) variables are free to take any non negativevalues, then the problem is
knownasmixedintegerprogrammingproblem.
SelfAssessmentQuestions1
StateTrue/False

1. Integerprogrammingisappliedtoproblemsthatinvolvediscretevariables.
2. IfsomevariablescantakenonnegativevaluesthenitisknownaspureI.P.P
7.3Gomorys All IPPMethod
AnoptimumsolutiontoanI.P.P.isfirstobtainedbyusingsimplexmethodignoringtherestriction
of integral values. In the optimum solution if all the variables have integer values, the current
solution will be the desired optimum integer solution. Otherwise the given IPP is modified by
insertinganewconstraintcalledGomorysorsecondaryconstraintwhichrepresentsnecessary
condition for integrability and eliminates some non integer solution without losing any integral
solution. After adding the secondary constraint, the problem is then solved by dual simplex
methodtogetanoptimumintegralsolution.Ifallthevaluesofthevariablesinthissolutionare
integers, an optimum intersolution is obtained, otherwise another new constrained is addedto
themodifiedLPPandtheprocedureisrepeated.Anoptimum integersolutionwillbereached
eventually after introducing enough new constraints to eliminate all the superior non integer
solutions.Theconstructionofadditionalconstraints,calledsecondaryorGomorysconstraints,
issoveryimportantthatitneedsspecialattention.

7.3.1.ConstructionOfGomorysConstraints
ConsideraLPPforwhichanoptimumnonintegerbasicfeasiblesolutionhasbeenattained.
SikkimManipalUniversity

113

OperationsResearch

Unit7

Withusualnotations,letthissolutionbedisplayedinthefollowingsimplextable.

Clearly

the

optimum

givenby xB = [x2, x3] =

Since xB

yB

xB

y1

y2

y3

y4

y2

y10

y11

y12

y13

y14

y3

y20

y21

y22

y23

y24

y00

y01

y02

y03

y04

is a non

assume that

y10 is

basicfeasiblesolutionis

[y10 ,y20]maxz=y00
integer

solution.

We

fractional.

Theconstraintequationis
y10=y11 x1 +y12 x2 +y13 x3+y14 x4

(x1 =x4 = 0)

reducesto
y10=y11 x1 +x2 +y14 x4

(x1 =x4 = 0) (1)

because x2and x3 arebasicvariables(whichimpliesthat y12=1 andy13=0)

Theaboveequationcanberewrittenas
x2=y10y11 x1y14 x4
Whichisalinearcombinationofnonbasicvariables.
Now,sincey10 0thefractionalpartofy10mustalsobenonnegative.Wesplitovereachofyij in
(1)intoanintegralpartIij ,andanonnegativefractionalpart,f1j forj=0,1,2,3,4.Afterthisbreak
up(1)maybewrittenas
I10+ f10=(I11+f11)x2 +(I14 +f14)x4
Or
f10 f11 x2 f14 x4 =x2 +I11 x1+I14x4 I10 (2)
Comparing(1)and(2)wecometoknowthatifweaddanadditionalconstraintinsuchawaythat
the L.H.S. of (2) isan integer, then we shall be forcing the noninteger y10 towards an integer.
Thisiswhatisneeded.
ThedesiredGomorysconstraintisf10 f11 x1 f11x4 0.
Letitbepossibletohavef10 f11 x1 f11 x4 =h whereh>0isaninteger.Then f10 =h+f11 x1 +
f14 x4 isgreaterthanone.Thiscontradictsthat0<fij<1forj=0,1,2,3,4.
ThusGomorysconstraintis

SikkimManipalUniversity

114

OperationsResearch

j = 1,4

or -

f ig xj f10 or

Unit7

fij. xj - f10

j = 1,4

fij xj + Gsla (1) = - f10

j = 1,4

WhenGsla (1)isslackvariableintheabovefirstGomoryconstraint.
Thisadditional constraintistobeincludedin the givenL.P.P. inorder to movefurther towards
obtaining an optimum all integer solution. After the addition of this constraint, the optimum
simplextablelookslikeasgivenbelow
yB

xB

y1

y2

y3

y4

Gsla(1)

y1

y10

y11

y12

y13

y14

y2

y20

y21

y22

y23

y24

f10

f11

f14

y00

y01

y02

y03

y04

y05

Gsla(1)

Sincef10 isnegative.Theoptimalsolutionisinfeasibleandthusthedualsimplexmethodisto
be applied for obtaining an optimum feasible solution. After obtaining this solution, the above
referredprocedureisappliedforconstructingsecond Gomorysconstraint.Theprocessistobe
continuedsolongasanallintegersolutionhasnotbeenobtained.

SelfAssessmentQuestions2
Fillintheblanks

1. AnoptimumsolutiontoI.P.Pisfirstobtainedbyusing_________________.
2. With the addition of Gomorys constraint the problem is solved by _______ _________
_________.

7.4 AllI.P.P.Algorithm
Theiterativeprocedureforthesolutionofanallintegerprogrammingproblemisasfollows:
Step1:ConverttheminimizationI.P.P.intothatofmaximization,ifitisintheminimizationform.
Theintegralityconditionshouldbeignored.
Step2:Introducetheslackorsurplusvariables,wherevernecessarytoconverttheinequations
intoequationsandobtaintheoptimumsolutionofthegivenL.P.P.byusingsimplexalgorithm.
Step3:Testtheintegralityoftheoptimumsolution
SikkimManipalUniversity

115

OperationsResearch

Unit7

a) Iftheoptimumsolutioncontainsallintegervalues,anoptimumbasicfeasibleintegersolution
hasbeenobtained.
b) Iftheoptimumsolutiondoesnotincludeallintegervaluesthenproceedontonextstep.
Step 4: Examine the constraint equations corresponding to the current optimum solution. Let
theseequationsberepresentedby
n1

j = 0

yij ,xj = bi ,(i = 0,1,2,........,m1)

Where n denotesthenumberofvariablesand m thenumberofequations.

{ }

Choosethelargestfractionof bi s ietofind max bi i

i
Letitbe b 1 orwriteisas fk
k i
o
Step5:Expresseachofthenegativefractionsifany,inthekth rowoftheoptimumsimplextable
asthesumofanegativeintegerandanonnegativefraction.
Step6: FindtheGomorianconstraint
n1

j= 0

fkj ,xj fko

andaddtheequation
n1

Gsla (1) = - fko +

j = 0

fkj . xj

tothecurrentsetofequationconstraints.
Step7:Startingwiththisnewsetofequationconstraints,findthenewoptimumsolutionbydual
simplexalgorithm.
(SothatGsla (1)istheinitialleavingbasicvariable).
Step 8: If this new optimum solution for the modified L.P.P. is an integer solution. It is also
feasibleandoptimumforthegivenI.P.P.otherwisereturntostep4andrepeattheprocessuntil
anoptimumfeasibleintegersolutionisobtained.

SikkimManipalUniversity

116

OperationsResearch

Unit7

Example:
FindtheoptimumintegersolutiontothefollowingallI.P.P.
Maximize

z=x1 +2x2

Subjecttotheconstraints
x1 +x2 7
2x1

11

2x2 7
x1,x2 >0 andareintegers
Solution:
Step1:Introducingtheslackvariables,weget
2x2 +x3 =7
x1 +x2 +x4 =7
2x1 +x5 =11
x1,x2,x3,x4,x5>0.
Step2:Ignoringtheintegercondition,wegettheinitialsimplextableasfollows:
Cj

0
Miniratio

Basic
variabl
e

CB

XB

X1

x3

x4

x5

11

Z=0

SikkimManipalUniversity

X2

xB
x2

X3

X4

X5

7
1

D j

117

OperationsResearch

Unit7

Introducingx2 andleavingx3 fromthebasis,weget

Cj

0
Miniratio

Basic
variabl
e

CB

XB

X1

X2

X3

X4

X5

xB
x1

x2

1
3
2

1
2

x4

1
3
2

1
2

1
3
2
1

x5

11

11
2

D j

Z=CB XB =7

D1 = CB X1 - C1 = (2,0,0) (0,1,2)- 1= -1
1
1
D3 = CBX3 - C3 = (2,0,0) , - , 0 - 0= 1
2
2
IntroducingX1 andleavingX4 wegetthefollowingoptimumtable.
Optimumtable
Cj
Basic
variabl CB
e

XB

X1

X 2

X3

X4

X5

x2

1
2

1
2

x1

1
2

x5

Z=10

1
2

1
2

1
2

Dj

1
1
D3 = CB X3 - C3 = 2,1,0 ,- ,1 - 0
2
2

SikkimManipalUniversity

118

OperationsResearch

Unit7

1 1
= 1 - + 0 =
2 2

)(

D4 = CB X4 - C4 = 2,1,0 0,1,- 2 - 0 = 1

1
2

1
1
, z = 10 .
2
2

Theoptimumsolutionthesegotis: x1 =3 , x2 = 3

Step3:Sincetheoptimumsolutionobtainedaboveisnotanintegersolution,wemustgotonext
step.
Step4:Nowweselecttheconstraintcorrespondingtothecriterion
maxi(fBi)=max(fB1,fB2,fB3)

1 1 1
, 0 =
2 2 2

=max ,

Sinceinthisproblem,thex2 equationandx1equationbothhavethesamevalueoffBi ie

1
,
2

eitheroneofthetwoequationscanbeused.
Now consider the first row of the optimum table . The Gomorys constraint to be added is

- f1j xj + g1 = - fB1 or - f13 x3 - f14 x4 + g1 = - fB1

j= 3,4

1
1
- x3 - 0x4 + g1 = 2
2

or

1
1
x3 + g1 = 2
2

(x3 = x4 = 0)

Addingthisnewconstrainttotheoptimumtableweget
Cj

1 2

Basic
variable

CB

XB

X X

X2

1
3
2

0 1

X1

1
3
2

1 0

X5

0 0

G1

X3

X4

X5

G1

1
2

0
1

1
2

1
2

0 0

1
2

Z=CB XB =

0 0

SikkimManipalUniversity

D j

119

OperationsResearch

Unit7

1
10
2
Step5:Toapplydualsimplexmethod.Now,inordertoremovetheinfeasibilityoftheoptimum
solution:

1
1
1
x1 =3 , x2 = 3 , x5 = 4, g1 = - ,weusethedualsimplexmethod.
2
2
2
i) leavingvectorisG1 (i.e. b 4 )

\ r = 4
ii) Enteringvectorisgivenby
D j

D
= max
, x4j < 0 = max 3
x 4k
x4j

x43

Dk

D
= max 2 = 3
1
x
43
-
2
Thereforek=3.Sowemustentera3 correspondingtowhichx3 isgivenintheabovetable.Thus
droppingG1 andintroducingx3. Wegetthefollowingdualsimplextable.
Cj

Basic
variable

CB

XB

X 1

X2

X3

X 4

X5

G1

X2

X1

X5

X3

Z=CB XB =10

D j

)(
)
= CB G1 - C6 = (2,1,0,0) (1, - 1, 2, - 2) - 0 = 1

D4 = CB X4 - C4 = 2,1,0,0 0,1,- 2,0 - 0 = 1

D6

Thusclearlytheoptimumfeasiblesolutionisobtainedinintegers.

SikkimManipalUniversity

120

OperationsResearch

Unit7

FinallywegettheintegeroptimumsolutiontothegivenIPPasx1 =4,x2 =3andmax z=10.

SelfAssessmentQuestions3
IdentifywhetherthefollowingstatementsareTrueorFalse

1. WeselectthatvariableforGomorysconstraintwhosefractionalvalueismore.
2. OptimumvaluesinanpureI.P.Pcanbex=2andy=3.5.

7.5TheBranchAndBoundTechnique
SometimesafeworallthevariablesofanIPPareconstrainedbytheirupperorlowerboundsor
byboth.Themostgeneraltechniqueforthesolutionofsuchconstrainedoptimizationproblemsis
the branch and bound technique. The technique is applicable to both all IPP as well as mixed
I.P.P.thetechniqueforamaximizationproblemisdiscussedbelow:
LettheI.P.P.be
n

Maximize

z =

cj xj (1)

j=1

Subjecttotheconstraints
n

aij

xj bi

i = 1,2,....,m (2)

j=1

xj isintegervalued, j=1,2,..,r(<n)(3)
xj >0.j=r+1,..,n(4)
Furtherletussupposethatforeachintegervaluedxj,wecanassignlowerandupperboundsfor
theoptimumvaluesofthevariableby
Lj xj Uj

j=1,2,.r

(5)

Thefollowingideaisbehindthebranchandboundtechnique
Consideranyvariablexj,andletIbesomeintegervaluesatisfyingLj I Uj 1.Thenclearlyan
optimumsolutionto(1)through(5)shallalsosatisfyeitherthelinearconstraint.
xj I+1

(6)

Orthelinearconstraintxj I...(7)
To explainhow this partitioning helps,letusassumethatthere were nointeger restrictions (3),
andsupposethatthisthenyieldsanoptimalsolutiontoL.P.P.(1),(2),(4)and(5).Indicatingx1
=1.66(forexample).Thenweformulateand solvetwoL.P.Pseachcontaining(1),(2)and (4).
SikkimManipalUniversity

121

OperationsResearch

Unit7

But(5)forj=1ismodifiedtobe2x1 U1 inoneproblemandL1 x1 1intheother.Further

eachoftheseproblemsprocessanoptimalsolutionsatisfyingintegerconstraints(3)
ThenthesolutionhavingthelargervalueforzisclearlyoptimumforthegivenI.P.P.However,it
usuallyhappensthatone(orboth)oftheseproblemshasnooptimalsolutionsatisfying(3),and
thus some more computations are necessary. We now discuss step wise the algorithm that
specifies how to apply the partitioning (6) and (7) ina systematic mannertofinally arrive at an
optimumsolution.
Westartwithaninitiallowerboundforz,sayz(0) atthefirstiterationwhichislessthanorequalto
theoptimalvaluez*,thislowerboundmaybetakenasthestartingLj forsomexj.
Inadditiontothelowerboundz(0),wealsohavealistofL.P.Ps(tobecalledmasterlist)differing
only in the bounds (5). To start with (the 0th iteration) the master list contains a single L.P.P.
consistingof(1),(2),(4)and(5).Wenowdiscussbelow,thestepbystepprocedurethatspecifies
how the partitioning (6) and (7) can be applied systematically to eventually get an optimum
integervaluedsolution.

7.5.1 BranchAndBoundAlgorithm
Atthetth iteration(t=0,1,2,)
Step0:Ifthemasterlistisnotempty,chooseanL.P.P.outofit.Otherwisestoptheprocess,Go
tostep1.
Step1:Obtaintheoptimumsolutiontothechosenproblem.Ifeither
i) Ithasnofeasiblesolutionor
ii) Theresultingoptimumvalueoftheobjectivefunctionzislessthanorequaltoz(t),thenletz(t+1) =
z(t) andreturntostep0otherwisegotostep2.
Step2:Ifthesoobtainedoptimumsolutionsatisfiestheintegerconstraints(3)thenrecordit.Let
z(t+1) beassociatedoptimumvalueofzreturntostep0.Otherwisemovetostep3.
Step3:Selectanyvariablexj,j=1,2,.,p.thatdoesnothaveanintegervalueintheobtained
optimumsolutiontotheL.P.P.choseninstep0.Let x*j denotethisoptimalvalueof xj.Addtwo
L.P.Pstothemasterlist:theseL.P.PsareidenticalwiththeL.P.P.choseninstep0,exceptthat

[ ]+1.Letz

inone,thelowerboundonxj isreplacedby x*j

SikkimManipalUniversity

(t+1)

=z(t)returntostep0.

122

OperationsResearch

Unit7

Note:Attheterminationofthealgorithm,ifafeasibleintegervaluedsolutionyieldingz(t) hasbeen
recordeditisoptimum,otherwisenointegervaluedfeasiblesolutionexists.
Example:
UsebranchandboundtechniquetosolvethefollowingI.P.P.
Maximize

z=7x1 +9x2 (1)

Subjecttotheconstraints
x1 +3x2 <6 (2)
7x1 +x2 <35
0<x1,x2 <7 (3)
x1,x2 areintegers(4).
Solution:
Atthestartingiterationwecanconsiderz(0) =0tobethelowerbound,forx,sinceallxj =0is
feasible.ThemasterlistcontainsonlytheL.P.P.(1)(2)and(3).whichisdesignatedasproblem
1.Chooseitinstep0,andinstep1determinetheoptimumsolution.
z0 =63 x1 =

9
7
(Solutiontoproblem1)
, x2 =
2
2

Sincethesolutionisnotintegervalued,proceedfromstep2tostep3,andselectx1.Thensince
x* = 9 = 4,placeonthemasterlistthefollowingtwoadditionalproblems.
1 2

Problem2:

(1)(2)and5x1 70x2 7

Problem3:

(1)(2)and0x1 40x2 7

Returningtostep0:withz(1) =z(0) =0,

Wechooseproblem2,Step1establishesthatproblem2hasthefeasiblesolution
z0 =35,x1 =5x2 =0 [solutiontoproblem(2)](5)
Since this satisfies the integer constraints, therefore at step 2 we record it by enclosing in a
rectangleandletz(2) =35.
Returning to step 0 with z(2) = 35, we find that problem 3 is available. Step 1 determines the
followingoptimumfeasiblesolutiontoit
Z0 =58,x1 =4, x2 =

10
3

(Problem3)

Since the solution is not integer valued, proceed from step 2 to step 3 and select x2. Then

SikkimManipalUniversity

123

OperationsResearch

Unit7

[x ] =10
=3.Weaddthefollowingadditionalproblemsonthemasterlist:
3
*
2

Problem4:(1)(2)and 0 x1 4 4 x2 7
Problem5:(1)(2)and0x1 40x2 3
Returningtostep0withz(3) =z(2) =35,chooseproblem4fromstep1weknowthatproblem4has
no feasible solution and so we again return to step 0 with z(4) = z(3) = 35. Only problem 5 is
availableinthemasterlist.Instep1wedeterminethefollowingoptimumsolutiontothisproblem.
z0 =55x1 =4x2 =3(solutiontoproblems)(6)
Sincethissatisfiestheintegerconstraints,thereforeatstep2.Werecorditbyenclosinginsidea
rectangleandletz(5) =55.
Returningtostep0,wefindthatthemasterlistisemptyandthusthealgorithmterminates.
Now,onterminatingwefindthatonlytwofeasibleintegersolutionnamely(5)and(6)havebeen
recorded. Thebestof these givestheoptimum solution to the given I.P.P. Hence the optimum
integersolutiontothegivenI.P.P.is
Z0 =55,x1 =4,x2 =3.
Treediagramofaboveexample
Z*=63

1
1
x1 = 4 , x2 = 3
2
2

x1 <4

x1 >5

Z*=58

1
x1 = 4, x2 = 3
3

x2 <3

Node(1)

Z*=35
Node(3)

Node(2)

(x1 =5,x2 =0)

x2 >4

Z*=55
(x1 =4,x2 =3)

Node(5) Node(4)

Nosolution

Optimalsolution

SikkimManipalUniversity

124

OperationsResearch

Unit7

Solution
x1

x2

z*

Additional
Constraints

(1)

9
2

7
2

63

__

(2)

35

x1 5

Integerz*(1)

(3)

10
3

58

x1 4

Noninteger

x1 4,x2 4

Nosolution

x1 4,x2 3

Integerz*(2) (Optimal)

Node

(4)
(5)

.. ..
4

55

Typeofsolution
Noninteger(Original
problem)

SelfAssessmentQuestions4
StateTrueorFalse

1. Branch and Bound Technique is applied when some variables have upper or lower
bounds.

2. Westartthetechniquewithlowerbound.

7.7 Summary
This chapter investigated the programming model in which the assumption of divisibility was
weakened. You learned two algorithms to determine the optimal solution for an integer
programmingproblem.OneofthesewasthecuttingplanealgorithmdevisedbyGomoryandthe
otherwasthebranchandboundalgorithmdevelopedbylandandDoig.

TerminalQuestions
1. UseBranchandBoundtechniquetosolvethefollowingproblem
Maxz=3x1 +3x2 +13x3
subjectto
3x1 +6x2 +7x38
6x1 3x2 +7x3 8
0xj 5
andxj areintegerj=1,2,3
2. Whatisintegerprogramming?

SikkimManipalUniversity

125

OperationsResearch

Unit7

3. ExplaintheGomoryscuttingplaneallintegeralgorithmofanI.P.P.?

AnswersToSelfAssessmentQuestions
SelfAssessmentQuestions1
1. True

2. False

SelfAssessmentQuestions2
1.Simplexmethod
2.Dualsimplexmethod
SelfAssessmentQuestions3
1.Correct
2.Wrong
SelfAssessmentQuestions4
1.True
2.False
Answer ToTerminalQuestions
1. Attheendofthe8th iterationwegettheoptionalsolutiontotheI.P.P.isx1 =x2 =0,x3 =1,z*
=13.
2. RefertoSection7.2
3. RefertoSection7.3

SikkimManipalUniversity

126