Integer Programming Poblem

Gomorys All-Integer Cutting Plane
Method
Gomorys All-Integer Cutting Plane

Method Contd
The iterative procedure for the solution of

an all-integer programming problem may
be summarized as follows:
Write the given LPP with objective as
maximization with all the constraints as
type.
Solve the problem by the simplex method
If the solution obtained is integer, the
problem has obtained optimal solution. If
all XBi0, but some of them are not
integer then go to next step.
Choose the largest fraction of XBis say fk. Express each

of the negative fraction (if any) in the kth-row of the
optimal simplex table as a sum of a negative integer and
non-negative fraction.
Construct the fractional cut (Gomorian constraint) as:
n
(-fkj) xj - fk
j=1
Add the cutting plane generated in the previous step at
the bottom of the optimum simplex table and find the
solution using dual simplex method.
Repeat the procedure until all XBi0 and are integers.
8/29/2016
Example
8/29/2016
Example Contd
Find the optimum integer solution to

the
following
allinteger
programming problem.
Max Z = X1+ 2X2
S.t. 2X27
X1+X27
2X111
X1, X20 and are integers
8/29/2016
Introducing the slack variables S1 0, S2 0

S30. we get an initial basic feasible
solution S1=7, S2=7 and S3=11
Initial Table:
CB
1
X1
2
x2
0
S1
0
S2
0
S3
Sol
XB
Ratio
B.V.
S1
S2
S3
0
0
0
0
1
2
2
1
0
1
0
0
0
1
0
0
0
1
7
7
11
7/2
7/1
-
Cj - Zj
8/29/2016
Example Contd
Example Contd
First Iteration:X2 will enter and S1 will depart
Second Iteration:X1 will enter and S2 will depart
CB
1
X1
2
x2
0
S1
0
S2
0
S3
Sol
XB
Ratio
B.V.
X2
S2
S3
2
0
0
0
1
2
1
0
0
1/2
-1/2
0
0
1
0
0
0
1
7/2
7/2
11
7/2
11/2
-1
Cj - Zj
8/29/2016
B.V.
CB
1
X1
2
x2
0
S1
0
S2
0
S3
Sol
XB
X2
X1
S3
2
1
0
0
1
0
1
0
0
1/2
-1/2
1
0
1
-2
0
0
1
7/2
7/2
4
-1/2
-1
Cj - Zj
Since all Cj-Zj0, but this basic feasible solution

violates the integer restriction. Therefore we introduce a
Fractional Cut.
5
8/29/2016
Example Contd
Example Contd
Optimum Iteration:
B.V.
CB
1
X1
2
x2
0
S1
0
S2
0
S3
Sol
XB
X2
X1
S3
2
1
0
0
1
0
1
0
0
1/2
-1/2
1
0
1
-2
0
0
1
7/2=3+1/2
7/2=3+1/2
4+0
-1/2
-1
Cj - Zj
8/29/2016
Example Contd
The above table shows fractional parts of bis are

{1/2, , 0}. We take maximize of it i.e. fraction is
same for b1 and b2. So we select randomly any of
these. Let us consider b1=1/2.
Apply Fractional cut as
-1/2 S1 -1/2
Now we introduce Gomorian slack variable G1 0, so
that the above constraint becomes
-1/2 S1 + G1 = -1/2
Now, inserting this constraint into the optimum table
obtained above, the modified optimum simplex table
becomes
8/29/2016
Example Contd
Modified Simplex Table:
Modified Simplex Table:
B.V.
CB
1
X1
2
x2
0
S1
0
S2
0
S3
0
G1
Sol
XB
B.V.
CB
1
X1
2
x2
0
S1
0
S2
0
S3
0
G1
Sol
XB
X2
X1
S3
G1
2
1
0
0
0
1
0
0
1
0
0
0
1/2
-1/2
1
-1/2
0
1
-2
0
0
0
1
0
0
0
0
1
7/2
7/2
4
-1/2
X2
X1
S3
G1
2
1
0
0
0
1
0
0
1
0
0
0
1/2
-1/2
1
-1/2
0
1
-2
0
0
0
1
0
0
0
0
1
7/2
7/2
4
-1/2
-1/2
-1
0
-
0
-
-1/2
1
-1
-
0
-
0
-
Cj Zj
Cj Zj
Ratio
Since, all Cj-Zj 0. Therefore optimality is satisfied but

the feasibility is disturbed. Thus, here we apply dual
Simplex method.
8/29/2016
Example Contd
B.V.
CB
1
X1
2
x2
0
S1
0
S2
0
S3
0
G1
Sol
XB
X2
X1
S3
S1
2
1
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
1
-2
0
0
0
1
0
1
-1
2
-2
3
4
3
1
-1
-1
Here all Cj-Zj 0 and the feasibility is also attained. This

Shows that the optimum feasible solution has been obtained
in integers. Hence the sol. to the give I.P.P. is X1=4, X2 =3
8/29/2016
10
Problem- All I.P.P.
G1 will depart and S1 will enter
Cj - Zj
8/29/2016
11
Obtain optimal solution to

following problem:
Max Z = 2X1+ 2X2
S.t. 5X1+3X28
X1+2X24
X1, X20 and are integers
8/29/2016
the
12
Problem Contd
Problem Contd
Introducing the slack variables S10, S20.

we get an initial basic feasible solution
S1=8, S2=4
Initial Table:
CB
2
X1
2
X2
0
S1
0
S2
Sol
XB
Ratio
B.V.
S1
S2
0
0
5
1
3
2
1
0
0
1
8
4
8/5
4/1
Cj - Zj
8/29/2016
CB
2
X1
2
X2
0
S1
0
S2
Sol
XB
Ratio
B.V.
X1
S2
2
0
1
0
3/5
7/5
1/5
-1/5
0
1
8/5
12/5
8/3
12/7
4/5
-2/5
Cj - Zj
13
Problem Contd
8/29/2016
14
Problem Contd
Second Iteration:X2 will enter and S2 will depart

B.V.
CB
2
X1
X1
X2
2
2
1
0
0
1
2/7
-1/7
-3/7
5/7
-2/7
-4/7
Cj - Zj
First Iteration:X1 will enter and S1 will depart
Optimum Iteration:
2
X2
0
S1
0
S2
Sol
XB
B.V.
CB
2
X1
2
X2
0
S1
0
S2
Sol
XB
4/7
12/7
X1
X2
2
2
1
0
0
1
2/7
-1+6/7
-3/7
5/7
4/7=0+ 4/7
12/7=1+5/7
-2/7
-4/7
Cj - Zj
Since all Cj - Zj 0, but this basic feasible solution

Violates the integer restriction. Therefore we introduce a
Fractional Cut.
8/29/2016
15
Problem Contd
8/29/2016
16
Problem Contd
bis
The above table shows fractional parts of

are {4/7, 5/7}. We take maximize of it i.e.
fraction 5/7 corresponding to b2.
Apply Fractional cut, we have
-6/7 S1 -5/7 S2 -5/7
Now we introduce Gomorian slack variable
G1 0, so that the above constraint becomes
-6/7 S1 -5/7 S2 +G1 = -5/7
Now, inserting this constraint into the
optimum table obtained above, the modified
optimum simplex table becomes
8/29/2016
17
B.V.
CB
2
X1
2
X2
0
S1
0
S2
0
G1
Sol
XB
X1
X2
G1
2
2
0
1
0
0
0
1
0
2/7
-1/7
-6/7
-3/7
5/7
-5/7
0
0
1
4/7
12/7
-5/7
-2/7
-4/7
Cj Zj

The feasibility is disturbed. Thus, here we apply dual
Simplex method.
8/29/2016
18
Problem Contd
Problem Contd
B.V.
CB
2
X1
2
X2
0
S1
0
S2
0
G1
Sol
XB
X1
X2
G1
2
2
0
1
0
0
0
1
0
2/7
-1/7
-6/7
-3/7
5/7
-5/7
0
0
1
4/7
12/7
-5/7
0
-
0
-
-2/7
1/3
-4/7
4/5
0
-
Cj Zj
Ratio
G1 will depart and X3 will enter

B.V.
CB
2
X1
2
X2
0
S1
0
S2
0
G1
Sol
XB
X1
X2
S1
2
2
0
1
0
0
0
1
0
0
0
1
-2/3
5/6
5/6
1/3
-1/6
-7/6
1/3
11/6
5/6
-1/3
Cj - Zj
8/29/2016
19
Problem Contd
8/29/2016
20
Problem Contd
G1 will depart and X3 will enter

B.V.
CB
2
X1
2
X2
0
S1
0
S2
0
G1
Sol
XB
X1
X2
S1
2
2
0
1
0
0
0
1
0
0
0
1
-2/3
5/6
5/6
1/3
-1+5/6
-7/6
1/3
1+5/6
5/6
-1/3
Cj - Zj
Gomorys Mixed-Integer
Plane Method
2
X1
2
X2
0
S1
0
S2
0
G1
0
G2
Sol
XB
X1
X2
S1
G2
2
2
0
0
1
0
0
0
0
1
0
0
0
0
1
0
-2/3
5/6
5/6
-5/6
1/3
-1/6
-7/6
-5/6
0
0
0
1
1/3
11/6
5/6
-5/6
-1/3
-1/3

the feasibility is disturbed. Thus, here we apply dual
Simplex method.
21
Cutting
Gomorys mixed-integer cutting plan method can

be summarized in the following steps:
Write the given LPP into the standard maximization
form and get optimum solution using the simplex
method.
If all XBi0 and are integers, the obtained solution
is the optimum solution. If all XBi0 but the integer
restricted variables are not integer, then go to next
step.
Pick up the kth-row having the largest fractional
value corresponding to the basic variable which are
suppose to take integer value and construct the
Gomorian constraint as
8/29/2016
CB
Cj - Zj
Again apply fractional cut

-5/6 S2 -5/6 G1 -5/6
-5/6 S2 -5/6 G1+G2 = -5/6
8/29/2016
B.V.
23
8/29/2016
Gomorys Mixed-Integer
Plane Method Contd
22
Cutting
(-fij) xj + [fk/ (fk-1)] (-fij)xj -fk

jR+
jRwhere 0<fk<1, R+={j:fij0}, R-={j:fij<0}
corresponding to non-basic variables.
Add the cutting plane generated in the
previous step at the bottom of the optimum
simplex table and find the solution using dual
simplex method.
Repeat the procedure until all XBi0 and all
restricted variables are integers.
8/29/2016
24
Example-Mixed I.P.P.
Example Contd

the
following
Mixed-integer
Max Z = 7X1+9X2
S.t. X1 +3X26
7X1+X235
X1, X20 and X1 is an integer
8/29/2016
25
Introducing the slack variables S1 0, S20. we get

an initial basic feasible solution S1=6, S2=35. Solve
the problem ignoring the integer restriction.
Initial Table:
B.V.
CB
7
X1
9
X2
0
S1
0
S2
Sol
XB
Sol
XB
S1
S2
0
0
-1
7
3
1
1
0
0
1
6
35
6/3
35/1
Cj Zj
8/29/2016
26
Example Contd
Example Contd
First iteration:X2 will enter and S1 will depart
Second iteration:X1 will enter and S2 will depart
CB
7
X1
9
X2
0
S1
0
S2
Sol
XB
Ratio
B.V.
X2
S2
9
0
-1/3
22/3
1
0
1/3
-1/3
0
1
2
33
9/2
10
-3
Cj Zj
B.V.
CB
7
X1
9
X2
0
S1
0
S2
Sol
XB
X2
X1
9
7
0
1
1
0
7/22
-1/22
1/22
3/22
7/2
9/2=4+1/2
-28/11
-15/11
Cj - Zj
Here Cj - Zj 0 but X1 is not an integer, therefore from

the second row
-3/22 S2+[1/2 / (1/2 1)] (1/22) S1 -
i.e. -1/22 S1 -3/22 S2 -1/2
8/29/2016
27
Example Contd
28
Example Contd
Now we introduce Gomorian slack

variable G10, so that the above
constraint becomes
-1/22 S1 - 3/22 S2 + G1= -1/2
optimum table obtained above, the
modified
optimum
simplex
table
becomes
8/29/2016
8/29/2016
29
Modified Simplex Table

B.V.
CB
7
X1
9
X2
0
S1
0
S2
0
G1
Sol
XB
X2
X1
G1
9
7
0
0
1
0
1
0
0
7/22
-1/22
-1/22
1/22
3/22
-3/22
0
0
1
7/2
9/2
-1/2
-28/11
-15/11
Cj Zj

Simplex method.
8/29/2016
30
Example Contd
Example Contd
Modified Simplex Table

9
X2
0
S1
0
S2
0
G1
Sol
XB
B.V.
CB
7
X1
9
X2
0
S1
0
S2
0
G1
Sol
XB
7/2
9/2
-1/2
X2
X1
S2
9
7
0
0
1
0
1
0
0
10/33
-1/11
1/3
0
0
1
1/3
1
-22/3
10/3
4
11/3
-23/11
-10
B.V.
CB
7
X1
X2
X1
G1
9
7
0
0
1
0
1
0
0
7/22
-1/22
-1/22
1/22
3/22
-3/22
0
0
1
-28/11
56
-15/11
10
Cj Zj
Ratio
Cj - Zj

Hence the sol. to the give mixed I.P.P. is X1=4, X2 =10/3
8/29/2016
31
Problem-Mixed I.P.P.
8/29/2016
32
Problem Contd

the
following
Mixed-integer
Max Z = 3X1+4X2
S.t. 3X1-X212
3X1+11X266
X1, X20 and X2 is an integer
8/29/2016
33
Introducing the slack variables S1 0, S20. we get

an initial basic feasible solution S1=12, S2=66.
Solve the problem ignoring the integer restriction.
Initial Table:
CB
3
X1
4
X2
0
S1
0
S2
Sol
XB
Ratio
B.V.
S1
S2
0
0
3
3
-1
11
1
0
0
1
12
66
66/11
Cj - Zj
8/29/2016
34
Problem Contd
Problem Contd
First iteration:X2 will enter and S2 will depart
Second iteration:X1 will enter and S1 will depart
CB
3
X1
4
X2
0
S1
0
S2
Sol
XB
Ratio
B.V.
S1
X2
0
4
36/11
3/11
0
1
1
0
1/11
1/11
18
6
11/2
22
21/11
-4/11
Cj - Zj
B.V.
CB
3
X1
4
X2
0
S1
0
S2
Sol
XB
X1
X2
3
4
1
0
0
1
11/36
-1/12
1/36
1/12
11/2
9/2=4+1/2
-7/12
-5/12
Cj - Zj
Here Cj-Zj 0 but X2 is not an integer, therefore from

the second row
-1/12 S2+[1/2 / (1/2 1)] (1/12) S1 -
i.e. -1/12 S1 -1/12 S2 -1/2
8/29/2016
35
8/29/2016
36
Problem Contd
Problem Contd
Now we introduce Gomorian slack

variable G10, so that the above
constraint becomes
-1/12 S1 -1/12 S2+ G1 = -1/2
optimum table obtained above, the
modified
optimum
simplex
table
becomes
8/29/2016
37
Problem Contd
CB
3
X1
4
X2
0
S1
0
S1
0
G1
Sol
XB
X1
X2
G1
3
4
0
1
0
0
0
1
0
11/36
-1/12
-1/12
1/36
1/12
-1/12
0
0
1
11/2
9/2
-1/2
-7/12
-5/12
Cj Zj

Simplex method.
8/29/2016
38
Problem Contd
B.V.
CB
3
X1
4
X2
0
S1
0
S2
0
G1
Sol
XB
X1
X2
G1
3
4
0
1
0
0
0
1
0
11/36
-1/12
-1/12
1/36
1/12
-1/12
0
0
1
11/2
9/2
-1/2
-7/12
7
-5/12
5
Cj Zj
Ratio
B.V.

B.V.
CB
3
X1
4
X2
0
S1
0
S2
0
G1
Sol
XB
X1
X2
S2
3
4
0
1
0
0
0
1
0
5/18
-1/6
1
0
0
1
1/3
1
-12
16/3
4
6
-1/6
-5
Cj - Zj

Hence the sol. to the give mixed I.P.P. is X1=16/3, X2= 4
8/29/2016
39
8/29/2016
40

Integer Programming Poblem

Uploaded by

Copyright:

Available Formats

Integer Programming Poblem

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Integer Programming Poblem

Uploaded by

Copyright:

Available Formats

Gomorys All-Integer Cutting Plane

Gomorys All-Integer Cutting Plane

The iterative procedure for the solution of

Choose the largest fraction of XBis say fk. Express each

Find the optimum integer solution to

Introducing the slack variables S1 0, S2 0

First Iteration:X2 will enter and S1 will depart

Second Iteration:X1 will enter and S2 will depart

Since all Cj-Zj0, but this basic feasible solution

The above table shows fractional parts of bis are

Modified Simplex Table:

Modified Simplex Table:

Since, all Cj-Zj 0. Therefore optimality is satisfied but

Here all Cj-Zj 0 and the feasibility is also attained. This

Problem- All I.P.P.

G1 will depart and S1 will enter

Obtain optimal solution to

Introducing the slack variables S10, S20.

Second Iteration:X2 will enter and S2 will depart

First Iteration:X1 will enter and S1 will depart

Since all Cj - Zj 0, but this basic feasible solution

The above table shows fractional parts of

Since, all Cj-Zj 0. Therefore optimality is satisfied but

G1 will depart and X3 will enter

G1 will depart and X3 will enter

Since, all Cj-Zj 0. Therefore optimality is satisfied but

Gomorys mixed-integer cutting plan method can

Again apply fractional cut

(-fij) xj + [fk/ (fk-1)] (-fij)xj -fk

restricted variables are integers.

Find the optimum integer solution to

Introducing the slack variables S1 0, S20. we get

First iteration:X2 will enter and S1 will depart

Second iteration:X1 will enter and S2 will depart

Here Cj - Zj 0 but X1 is not an integer, therefore from

Now we introduce Gomorian slack

Modified Simplex Table

Since, all Cj-Zj 0. Therefore optimality is satisfied but

Modified Simplex Table

Here all Cj-Zj 0 and the feasibility is also attained. This

Find the optimum integer solution to

Introducing the slack variables S1 0, S20. we get

First iteration:X2 will enter and S2 will depart

Second iteration:X1 will enter and S1 will depart

Here Cj-Zj 0 but X2 is not an integer, therefore from

Now we introduce Gomorian slack

Since, all Cj-Zj 0. Therefore optimality is satisfied but

G1 will depart and S2 will enter

Here all Cj-Zj 0 and the feasibility is also attained. This

You might also like