1
00:00:00,008 --> 00:00:03,610
Discrete optimization MIP part three. 
Okay? 

2
00:00:03,610 --> 00:00:06,440
So what we going to see today is cutting 
planes. 

3
00:00:06,440 --> 00:00:08,560
Okay? 
So the basic idea is like in constraint 

4
00:00:08,560 --> 00:00:11,230
programming. 
What you want to do, is you want to add 

5
00:00:11,230 --> 00:00:15,240
new constraints to the system that 
going to make the system easier to solve. 

6
00:00:15,240 --> 00:00:19,400
Now, in constraint programming, you would 
do that for actually improving constraint 

7
00:00:19,400 --> 00:00:22,360
propagation and reusing the search space, 
okay? 

8
00:00:22,360 --> 00:00:25,150
So, here what we're going to do is add 
new constraints. 

9
00:00:25,150 --> 00:00:29,990
But these new constraints, the goal, is 
to actually improve the linear 

10
00:00:29,990 --> 00:00:32,820
relaxation. 
Make it, you know, move up as much as you 

11
00:00:32,820 --> 00:00:35,890
can, okay. 
And so these, so, these are cutting 

12
00:00:35,890 --> 00:00:37,920
planes okay. 
I'm going to talk about them this lecture 

13
00:00:37,920 --> 00:00:41,630
and the next lecture, okay. 
And, this lecture is going to be focused 

14
00:00:41,630 --> 00:00:44,630
on Gomory cuts, which are very 
interesting cuts as you will see in a 

15
00:00:44,630 --> 00:00:47,810
moment. 
Okay, so, the basic key idea here, of 

16
00:00:47,810 --> 00:00:52,030
this lecture, very simple. 
We want to find a new linear constraint 

17
00:00:52,030 --> 00:00:55,172
okay that is valid. 
That means it doesn't remove any integer 

18
00:00:55,172 --> 00:00:59,840
solution okay any feasible solution. 
And it also, it helps, okay which 

19
00:00:59,840 --> 00:01:02,260
basically means that when you are at a 
particular point. 

20
00:01:02,260 --> 00:01:06,100
Okay, it's going to remove the value of 
the linear relaxation, the current, well, 

21
00:01:06,100 --> 00:01:07,780
the current basic feasible solution. 
Okay. 

22
00:01:07,780 --> 00:01:10,765
So it's going to improve the value of the 
linear relaxation. 

23
00:01:10,765 --> 00:01:14,670
Okay, so this is what we want, this is 
what we want to do, okay. 

24
00:01:14,670 --> 00:01:17,790
So in terms of constraint programming, 
this would be, okay I want something 

25
00:01:17,790 --> 00:01:21,180
that, you know, a new constraint that, 
which is valid, same definition. 

26
00:01:21,180 --> 00:01:24,740
And which improve propagation. 
Here is going to be improving the linear 

27
00:01:24,740 --> 00:01:27,440
relaxation. 
Which means removing the current value of 

28
00:01:27,440 --> 00:01:31,945
removing the current optimal solution of 
the linear relaxation. 

29
00:01:31,945 --> 00:01:36,520
Okay so let me first illustrate that 
geometrically and then we'll move to the 

30
00:01:36,520 --> 00:01:39,710
algebraic part and come back to the 
geometry at the same time okay. 

31
00:01:39,710 --> 00:01:42,275
So this is a very simple MIP. 
Actually its pretty boring. 

32
00:01:42,275 --> 00:01:46,430
Okay you'll see but it's going to be 
simple enough that we can actually show 

33
00:01:46,430 --> 00:01:50,500
these things in practice, okay. 
So we are maximizing x2 subject to these 

34
00:01:50,500 --> 00:01:54,140
two constraints, so 3x1 plus 2x2 is 
smaller than 6. 

35
00:01:54,140 --> 00:01:58,530
Sorry, equal. 
And then minus 3x1 plus 2x2 is smaller 

36
00:01:58,530 --> 00:02:01,350
than 0. 
Okay, both variables are integers. 

37
00:02:01,350 --> 00:02:03,890
Okay. 
So this is the linear relaxation. 

38
00:02:03,890 --> 00:02:06,360
There. 
Right, so, obviously it's fractional, you 

39
00:02:06,360 --> 00:02:11,910
know, x, x 2 is 1.5, x 1 is 1, okay, so x 
1 is fine. 

40
00:02:11,910 --> 00:02:14,130
Okay? 
But this is the relaxation. 

41
00:02:14,130 --> 00:02:17,380
Okay? 
Now, when we are actually trying to solve 

42
00:02:17,380 --> 00:02:21,440
this as a MIP, you know, the feasible 
point of this guy, that guy, and that 

43
00:02:21,440 --> 00:02:23,620
guy. 
So essentially, the linear relaxation, 

44
00:02:23,620 --> 00:02:27,830
you know, is actually I think a larger 
space than the space of all the interior 

45
00:02:27,830 --> 00:02:29,880
points and that's where the problems come 
from okay. 

46
00:02:29,880 --> 00:02:34,090
And so what we want to do is to say oh 
can I improve these relaxation to get 

47
00:02:34,090 --> 00:02:38,000
closer to these you know integer points. 
Okay so this is one of the cut that we 

48
00:02:38,000 --> 00:02:43,680
will generate okay. 
So this cut is basically saying that x 2 

49
00:02:43,680 --> 00:02:47,090
is smaller or equal to one okay. 
And so what this cut is basically doing 

50
00:02:47,090 --> 00:02:51,520
is cutting this big part of the top of 
the linear relaxation and it can do that 

51
00:02:51,520 --> 00:02:55,550
because we are not removing any integer 
solution to that particular, to that set 

52
00:02:55,550 --> 00:02:58,780
constraints okay. 
And then we get this smaller poly top now 

53
00:02:58,780 --> 00:03:02,110
and we can re optimize over it. 
The linear relaxation is going to do it's 

54
00:03:02,110 --> 00:03:05,640
work and get to one of these vertices 
okay which is going to be which is 

55
00:03:05,640 --> 00:03:08,520
going to be optimal for the linear 
relaxation at this point okay. 

56
00:03:08,520 --> 00:03:13,647
Find vertices, okay the value of x2 is 
equal to 1 but the value of x1 in this 

57
00:03:13,647 --> 00:03:18,743
particular case is 2/3 so it's still not 
you know it's still fractional. 

58
00:03:18,743 --> 00:03:20,540
Okay, so we going to generate the new 
cut. 

59
00:03:20,540 --> 00:03:23,890
So this is a beautiful cut, right so, 
look at this cut, you know, all rad. 

60
00:03:23,890 --> 00:03:28,600
Okay, and now the value of the objective 
function, yeah well, well, we are cutting 

61
00:03:28,600 --> 00:03:32,860
another part of this, you know, linear, 
linear programing space here, infeasible 

62
00:03:32,860 --> 00:03:35,510
solution, the feasible solution to the 
linear program. 

63
00:03:35,510 --> 00:03:39,450
Okay, and we get, we obtain a smaller 
parting top, and now the optimal 

64
00:03:39,450 --> 00:03:43,480
solution, one of the optimal solution to 
this linear program is also integral. 

65
00:03:43,480 --> 00:03:47,190
Okay, and if we are lucky now, the linear 
relaxation is going to get to this, okay? 

66
00:03:47,190 --> 00:03:50,440
And then we can stop, because at this 
point we are optimal for linear 

67
00:03:50,440 --> 00:03:54,295
relaxation, and both variables have 
integer value, okay, one and one. 

68
00:03:54,295 --> 00:03:59,007
Okay? 
So this is essentially the essense of. 

69
00:03:59,007 --> 00:04:03,370
you know, this cutting plane algorithm. 
You start from the beginning, you start 

70
00:04:03,370 --> 00:04:06,660
adding these cuts, re-optimizing. 
Adding these cuts, re-optimizing. 

71
00:04:06,660 --> 00:04:10,855
And you have the optimal solution to the 
linear relaxation which is now on a on a 

72
00:04:10,855 --> 00:04:14,181
on a on a vertex, which is all integral. 
Okay? 

73
00:04:14,181 --> 00:04:16,940
So, so today, so there are many ways of 
generating these cuts. 

74
00:04:16,940 --> 00:04:18,580
Okay? 
So and, and what are we going to do today 

75
00:04:18,580 --> 00:04:21,400
is look at one way, which are these 
Gomery cuts, okay? 

76
00:04:21,400 --> 00:04:25,010
And they are syntactic in the sense that 
the only thing we're going to do is look 

77
00:04:25,010 --> 00:04:29,170
at the tableau and derive the cut from 
the tableau, the simplex tableau, okay? 

78
00:04:29,170 --> 00:04:33,020
The assumption that I'm going to make 
here, okay, so I make a very simple 

79
00:04:33,020 --> 00:04:35,790
assumption here is that all variables 
take integer values. 

80
00:04:35,790 --> 00:04:40,120
This, of course, has been generalized by 
Lawrence Wolsey, and others, for, you 

81
00:04:40,120 --> 00:04:42,800
know, the case where this is not only 
integer values, they are beautiful 

82
00:04:42,800 --> 00:04:45,070
results in that area, but I want to talk 
about this, okay? 

83
00:04:45,070 --> 00:04:47,345
But they are in, you know, most software 
these days. 

84
00:04:47,345 --> 00:04:49,140
Okay? 
So what I'm going to show you is only, 

85
00:04:49,140 --> 00:04:52,730
make these assumptions, because that 
allows me to, you know, present the cut 

86
00:04:52,730 --> 00:04:54,310
in a simpler fashion. 
Okay. 

87
00:04:54,310 --> 00:04:58,230
So now, remember, the simpler algorithm 
is only, you know, dealing with this you 

88
00:04:58,230 --> 00:05:02,150
know basic feasible solution and remember 
while a basic feasible solution is your 

89
00:05:02,150 --> 00:05:06,662
express some of the basic variables in 
terms of the non-basic variables okay. 

90
00:05:06,662 --> 00:05:11,240
And so and obviously these b's here have 
to be greater or equal to 0. 

91
00:05:11,240 --> 00:05:13,100
Okay. 
And in a basic feasible solution the 

92
00:05:13,100 --> 00:05:16,740
value of the non-basic variables are 
going to be all 0. 

93
00:05:16,740 --> 00:05:19,975
And the value of the basic variables are 
going to be these b's. 

94
00:05:19,975 --> 00:05:23,880
Okay, so this is the basic feasible 
solution, this is the basic feasible 

95
00:05:23,880 --> 00:05:29,160
solution corresponding to this selection 
of basic variables and non-basic 

96
00:05:29,160 --> 00:05:30,910
variables. 
Okay, so we have this basic solution. 

97
00:05:30,910 --> 00:05:36,070
Obviously, if all the b's, you know, all 
the b's are integral, okay, are integer 

98
00:05:36,070 --> 00:05:40,110
values, then we are great, okay, so we 
have a solution, okay, to the myth. 

99
00:05:40,110 --> 00:05:43,700
Okay, but in practice, in general, it's 
not, it's not going to be the case, some 

100
00:05:43,700 --> 00:05:46,710
of these variables are going to be 
assigned fractional values okay, so we 

101
00:05:46,710 --> 00:05:49,840
have seen in the previous lecture that 
this linear programming reaction is 

102
00:05:49,840 --> 00:05:53,120
always trying to be cute, right? 
And making your life as miserable as 

103
00:05:53,120 --> 00:05:55,760
possible. 
Okay, and so in a sense here, what the 

104
00:05:55,760 --> 00:05:58,970
linear, so some of these values are 
going to be, some of these, some of these 

105
00:05:58,970 --> 00:06:00,920
b's are going to be fractional. 
Okay. 

106
00:06:00,920 --> 00:06:04,150
So let's assume for simplicity that b1 is 
fractional. 

107
00:06:04,150 --> 00:06:07,780
Which basically means that the value 
assigned to x1 is fractional. 

108
00:06:07,780 --> 00:06:10,460
Okay. 
So this is all that we can deduce a cut. 

109
00:06:10,460 --> 00:06:11,890
Which is a gomory cut. 
Okay. 

110
00:06:11,890 --> 00:06:14,170
So we'll talk about gomory later on. 
Okay? 

111
00:06:14,170 --> 00:06:17,240
So what we going to do is, we going to 
take, you know, we going to take this row 

112
00:06:17,240 --> 00:06:18,510
of the tableau. 
Okay? 

113
00:06:18,510 --> 00:06:21,680
And the first thing we going to do is, we 
going to take these coefficients there 

114
00:06:21,680 --> 00:06:23,490
and round them downwards. 
Okay? 

115
00:06:23,490 --> 00:06:26,590
The largest integer which is smaller 
than, which is large, wh, which, the 

116
00:06:26,590 --> 00:06:28,515
largest integer which is smaller than 
that value. 

117
00:06:28,515 --> 00:06:32,730
Okay, and so what we have now. 
We know that if run all these coefficent 

118
00:06:32,730 --> 00:06:36,760
downward that value is going to be 
smaller than the value that we have here 

119
00:06:36,760 --> 00:06:41,270
okay so we can rewrite that constraint as 
an equality now which is smaller than. 

120
00:06:41,270 --> 00:06:45,100
We are smaller or equal to be 1 now. 
But we have rounded all the coefficent 

121
00:06:45,100 --> 00:06:47,700
downward. 
And so all these coefficients now are 

122
00:06:47,700 --> 00:06:52,210
integer values right okay. 
So I haven't done anything right. 

123
00:06:52,210 --> 00:06:54,180
So this is like. 
Self evident truth. 

124
00:06:54,180 --> 00:06:57,350
Right? 
So, so what you see here is essentially a 

125
00:06:57,350 --> 00:06:59,950
valid inequality that I have. 
Okay? 

126
00:06:59,950 --> 00:07:02,270
And there is a very interesting property 
about this. 

127
00:07:02,270 --> 00:07:04,550
Right? 
So if you look at x1, it is feasible 

128
00:07:04,550 --> 00:07:07,390
solution, x1 is an integer value. 
[INAUDIBLE] This will be an integer. 

129
00:07:07,390 --> 00:07:09,340
Okay? 
Now this expression here has to be an 

130
00:07:09,340 --> 00:07:10,290
integer too. 
Why? 

131
00:07:10,290 --> 00:07:13,378
Because all these coefficients are 
integers okay and all the xi's are 

132
00:07:13,378 --> 00:07:16,206
integers so the whole thing has to be an 
integer okay? 

133
00:07:16,206 --> 00:07:22,730
So now since you know that this value 
here is an int okay so what do you no b1 

134
00:07:22,730 --> 00:07:27,614
is a fraction right but since this is an 
int you can strengthen that constraint 

135
00:07:27,614 --> 00:07:31,970
and make sure that, and this is still 
valid in the, you know, in the integer 

136
00:07:31,970 --> 00:07:34,620
solution to the, to the, to the MIP. 
Okay. 

137
00:07:34,620 --> 00:07:38,430
Okay, but in the feasible solution to the 
MIP, we now have that, essentially this 

138
00:07:38,430 --> 00:07:45,020
expression, that we have the beginning, 
okay, has to be smaller or equal to the 

139
00:07:45,020 --> 00:07:49,690
floor of b1, which is essentially the, 
you know rounding b1 downwards, okay. 

140
00:07:49,690 --> 00:07:53,720
So now, this is the Gomory Cut, okay, so 
what we are doing here is that we are 

141
00:07:53,720 --> 00:07:57,180
basically taking the coefficients here, 
okay, replace you know, rounding them 

142
00:07:57,180 --> 00:08:00,860
downwards we are taking the b, rounding 
it downwards and of course, this becomes 

143
00:08:00,860 --> 00:08:02,530
an inequality. 
Okay? 

144
00:08:02,530 --> 00:08:06,050
And so this is a cut okay. 
Now this cut, is varying obtusely. 

145
00:08:06,050 --> 00:08:09,780
The only thing that I have done are basic 
you know algebraic manipulations and then 

146
00:08:09,780 --> 00:08:13,260
exploiting the fact that these values are 
integers in the, in the. 

147
00:08:13,260 --> 00:08:15,650
In the solutions to the MIP. 
Okay? 

148
00:08:15,650 --> 00:08:19,485
So, it's valid and then it has this also 
beautiful property that it removes the 

149
00:08:19,485 --> 00:08:22,522
value. 
It prunes the basic feasible solutions of 

150
00:08:22,522 --> 00:08:26,896
the basic feasible solution which is the 
optimal value of the linear relaxation. 

151
00:08:26,896 --> 00:08:30,137
Okay. 
So why what but look at this thing right. 

152
00:08:30,137 --> 00:08:34,697
So in the basic feasible solution okay. 
So what we know okay is basically all 

153
00:08:34,697 --> 00:08:38,020
these non-basic variables have to be zero 
okay. 

154
00:08:38,020 --> 00:08:40,707
So if the non-basic variables have to be 
zero okay. 

155
00:08:40,707 --> 00:08:44,787
So x1 is going to be assigned to b1 and 
then the value here you know, this b1 is 

156
00:08:44,787 --> 00:08:49,071
going to be obviously greater than the 
floor of b1 because we assume that b1 was 

157
00:08:49,071 --> 00:08:54,393
fractional, okay? 
So essentially we have this beautiful 

158
00:08:54,393 --> 00:08:57,874
cut, okay, which is looking at the, 
looking at the you know, the optimal 

159
00:08:57,874 --> 00:09:01,945
solution to the linear program, finding a 
row which is fractional and then adding a 

160
00:09:01,945 --> 00:09:07,585
new constraint which removes that basic 
feasible solution. 

161
00:09:07,585 --> 00:09:10,505
Now if I remove that basic feasible 
solution without constraints, if I 

162
00:09:10,505 --> 00:09:14,360
re-optimize what's going to happen, if I 
put that constraint in, well good things 

163
00:09:14,360 --> 00:09:17,670
are going to happen. 
So,but before we do that I want to 

164
00:09:17,670 --> 00:09:19,180
reformulate this cut. 
Okay? 

165
00:09:19,180 --> 00:09:23,080
This is not typically what you do. 
So this is the, this is, this is the cut 

166
00:09:23,080 --> 00:09:26,430
but we going to reformulate it. 
In such a way that, you know, it's 

167
00:09:26,430 --> 00:09:29,360
actually better for, you know, numerical 
stability. 

168
00:09:29,360 --> 00:09:33,740
And so what we going to do, and so in a, 
in a, in a in a linear program, it's, 

169
00:09:33,740 --> 00:09:36,590
it's very nice if the variables are 
between zero and one, because we 

170
00:09:36,590 --> 00:09:39,480
typically deal with these things as 
floating points, and there are as many 

171
00:09:39,480 --> 00:09:43,430
floating points between zero and one as, 
outside, and so, outside zero and one. 

172
00:09:43,430 --> 00:09:46,780
So what we are going to do is we're 
going to take this constraint, okay, we, 

173
00:09:46,780 --> 00:09:50,200
so this is the original constraints, we 
are going to take the cut here and we are 

174
00:09:50,200 --> 00:09:52,330
going to subtract one from the other. 
Okay? 

175
00:09:52,330 --> 00:09:56,000
And so when we subtract one from the 
other, you'll see that the x1 is going to 

176
00:09:56,000 --> 00:10:01,140
disappear, obviously and then, then, you 
know, this value is going to be smaller 

177
00:10:01,140 --> 00:10:05,290
than the other one so what we get is that 
we get an inequality in the other 

178
00:10:05,290 --> 00:10:09,200
direction. 
Where you see here, basically the sum of 

179
00:10:09,200 --> 00:10:13,820
the fractional part of the coefficient 
times the axis and then the fractional 

180
00:10:13,820 --> 00:10:19,050
part of the right inside the b. 
Okay so in a sense think of the gomory 

181
00:10:19,050 --> 00:10:23,870
cut now as oh I take the tableau and I 
take the fractional part of all the 

182
00:10:23,870 --> 00:10:27,376
values, say the basic variables. 
Okay I take the fractional part here 

183
00:10:27,376 --> 00:10:30,329
Okay. 
So the value is you basically take and 

184
00:10:30,329 --> 00:10:34,850
the fractional part is simply the 
variable the coefficient minus you know, 

185
00:10:34,850 --> 00:10:38,680
the, the largest integer which is smaller 
than the floor of that particular 

186
00:10:38,680 --> 00:10:41,345
coefficient. 
And that has to be greater or equal, 

187
00:10:41,345 --> 00:10:45,090
okay, to the fractional part of the 
right-hand side, okay? 

188
00:10:45,090 --> 00:10:47,520
And that's typically the cut that we're 
going to use, okay? 

189
00:10:47,520 --> 00:10:49,650
And so, what are we going to do with this 
cut? 

190
00:10:49,650 --> 00:10:51,366
Well, we're going to put it inside the 
tableau now. 

191
00:10:51,366 --> 00:10:54,490
Okay, if you want to put it inside the 
tableau, you have to transform it into an 

192
00:10:54,490 --> 00:10:56,780
inequality. 
You take these slack variables that you 

193
00:10:56,780 --> 00:10:57,670
add. 
Okay? 

194
00:10:57,670 --> 00:11:01,990
You re express that as an inequality. 
You get s is equal to minus the 

195
00:11:01,990 --> 00:11:05,810
fractional part of the b1 of the, in that 
ta-, of in that tableau. 

196
00:11:05,810 --> 00:11:08,100
Okay? 
And then the fractional part of all the 

197
00:11:08,100 --> 00:11:10,650
other coefficients multiplying the 
non-basic variables. 

198
00:11:10,650 --> 00:11:13,760
And obviously when you look at these 
constraints you say okay? 

199
00:11:13,760 --> 00:11:16,430
It's not feasible but that's good. 
That's what you wanted. 

200
00:11:16,430 --> 00:11:19,250
You wanted that constraints which is not 
feasible otherwise you would stay at the 

201
00:11:19,250 --> 00:11:21,840
same place. 
You would still have the same, you know, 

202
00:11:21,840 --> 00:11:26,480
objective value for the linear, you know, 
relaxation but now, so you know that this 

203
00:11:26,480 --> 00:11:29,910
is not primal feasible, but obviously you 
turn your head and this is dual feasible. 

204
00:11:29,910 --> 00:11:32,810
Yes! 
You re-optimize the dual, and now you get 

205
00:11:32,810 --> 00:11:34,180
another relaxation. 
Right? 

206
00:11:34,180 --> 00:11:37,190
And it's the stronger relaxation because 
you have removed at least one of the 

207
00:11:37,190 --> 00:11:38,360
bases. 
Right? 

208
00:11:38,360 --> 00:11:41,440
And so the basically, that's what you do 
when you have Gomory cuts. 

209
00:11:44,830 --> 00:11:47,300
Okay, so you look at the tableau, you 
optimize the linear relaxation, okay. 

210
00:11:47,300 --> 00:11:49,230
So you get this linear relaxation, okay. 
Then you choose a row where the basic 

211
00:11:49,230 --> 00:11:51,830
variable is fractional, okay. 
So you know that. 

212
00:11:51,830 --> 00:11:55,770
That's not what you want. 
So you generate the Gomory cut, okay? 

213
00:11:55,770 --> 00:11:59,480
The Gomory cut generates this constraint 
which is primal and feasible, but is dual 

214
00:11:59,480 --> 00:12:02,195
feasible. 
You use a dual algorithm to re optimize, 

215
00:12:02,195 --> 00:12:04,800
okay? 
And you have a new value of the 

216
00:12:04,800 --> 00:12:07,630
relaxation. 
And you integrate this until, you know, 

217
00:12:07,630 --> 00:12:10,034
you basically form a solution which is 
all integral. 

218
00:12:10,034 --> 00:12:13,500
You know, all the integral values, you 
know all the values have integer values. 

219
00:12:13,500 --> 00:12:15,355
Or you can show that there are no 
feasible solution. 

220
00:12:15,355 --> 00:12:21,880
Okay, so that's the algorithm here, for 
solving MIP integer program using Gomory 

221
00:12:21,880 --> 00:12:24,960
cut, okay? 
Now, I want to illustrate that which as 

222
00:12:24,960 --> 00:12:28,320
you can see what it does on the simple 
example that I've shown you, okay? 

223
00:12:28,320 --> 00:12:32,620
So once again we start with this model 
you know, with, with the model over 

224
00:12:32,620 --> 00:12:35,140
there. 
Okay, I have my feet completely tangled 

225
00:12:35,140 --> 00:12:38,950
in you know, wires here, okay, so this is 
the basic, this is the model that I've 

226
00:12:38,950 --> 00:12:42,250
shown you. 
We re-express it in terms of equalities 

227
00:12:42,250 --> 00:12:46,260
and, of course, we transform the max into 
a min, okay, so we get these, these, 

228
00:12:46,260 --> 00:12:50,010
these constraints over there. 
So we have two new variable, x3 and x4, 

229
00:12:50,010 --> 00:12:53,540
okay, very important x3 and x4 because, 
you know, you, you, you see why in a 

230
00:12:53,540 --> 00:12:56,200
moment. 
Okay, but see that we have x3 and x4 and 

231
00:12:56,200 --> 00:13:00,330
you can express x3 in terms of x1 and x2, 
and x4 in terms of X1 and x2 as well, 

232
00:13:00,330 --> 00:13:03,870
okay and now we are trying to do the 
tableau of this thing, okay. 

233
00:13:03,870 --> 00:13:08,380
So this is the tableau, okay, so we see 
that at the beginning I put x3 and x4 in 

234
00:13:08,380 --> 00:13:14,710
bases, okay. 
So you see you see the value one over 

235
00:13:14,710 --> 00:13:16,860
there, is one over there. 
You see the b side on this side. 

236
00:13:16,860 --> 00:13:21,200
You see minus z over there. 
Okay, and you see, you know, the, the, 

237
00:13:21,200 --> 00:13:23,940
the objective function over there. 
Okay? 

238
00:13:23,940 --> 00:13:26,930
So, now what we are going to do is solve 
the linear relaxation. 

239
00:13:26,930 --> 00:13:29,710
We are going to take this tableau and do 
the simplex algorithm, this tableau. 

240
00:13:29,710 --> 00:13:32,040
And where we want to get is this point 
obviously. 

241
00:13:32,040 --> 00:13:35,870
That's geometrically where we want to go. 
Algebraically, this is what it's giving 

242
00:13:35,870 --> 00:13:38,520
you, okay? 
So value 3 over 2 okay? 

243
00:13:38,520 --> 00:13:42,104
That's what we wanted to find. 
The two variables which are in bases are 

244
00:13:42,104 --> 00:13:47,910
x1 and x2 okay? 
So x1 is equal to 1, x2 is equal to 3.5 

245
00:13:47,910 --> 00:13:50,580
okay? 
Which is exactly the point. 

246
00:13:50,580 --> 00:13:53,560
The algebra you know, is the same as the 
geometry, okay? 

247
00:13:53,560 --> 00:13:57,560
We are happy okay, and then you look at 
this tableau which is the tableau the 

248
00:13:57,560 --> 00:14:00,530
optimal value of the linear program 
right, okay. 

249
00:14:00,530 --> 00:14:03,760
Now, you look at this tableau when you 
see that the variable x2 is actually 

250
00:14:03,760 --> 00:14:06,550
given a fractional value, that's not good 
okay. 

251
00:14:06,550 --> 00:14:10,550
So, what you are going to do is take a 
cut okay, a Gomory Cut for that 

252
00:14:10,550 --> 00:14:14,840
particular row of the tableau okay. 
So, what the cut does, take the 

253
00:14:14,840 --> 00:14:18,720
fractional part of everyone of the 
coefficient okay, and multiply that by 

254
00:14:18,720 --> 00:14:22,800
the variables, the non basic variables. 
And I take the fractional part of the b 

255
00:14:22,800 --> 00:14:26,330
side and so the fractional part of the 
the sum of the fractional part of the 

256
00:14:26,330 --> 00:14:30,175
coefficients have to be greater than the 
fractional part of the b side. 

257
00:14:30,175 --> 00:14:33,720
Okay and you get this beautiful 
constraint which is a quarter of x3 plus 

258
00:14:33,720 --> 00:14:39,000
a quarter of x4 which is greater than or 
equal to one half okay and you look at 

259
00:14:39,000 --> 00:14:42,990
that chart and you say wow what does it 
mean, okay? 

260
00:14:42,990 --> 00:14:46,882
And of course, that's when I told you, 
you know, that it's easy to re express x3 

261
00:14:46,882 --> 00:14:51,920
and x4 in terms of x1 and x2, so we can 
take this cut and try to see what it 

262
00:14:51,920 --> 00:14:55,330
means in the original space. 
So you're going to take the value of x3, 

263
00:14:55,330 --> 00:14:59,960
which is in that system of equations, the 
value of x4, which is inside, which can 

264
00:14:59,960 --> 00:15:03,300
be re expressed in terms of that system 
of equation, you know, you re-express 

265
00:15:03,300 --> 00:15:07,740
these things here, and what you get is x2 
is smaller or equal to 1. 

266
00:15:07,740 --> 00:15:10,420
Okay. 
Just massage this thing, okay, and you 

267
00:15:10,420 --> 00:15:13,920
get x2 is smaller or equal to 1. 
Which is what? 

268
00:15:13,920 --> 00:15:16,255
Which is the first cut that I've shown 
you before. 

269
00:15:16,255 --> 00:15:21,860
Okay, wow, that's great, right? 
So, what I do, is that essentially, you 

270
00:15:21,860 --> 00:15:24,690
know when you do this Gomory, you know, 
cut algorithm. 

271
00:15:24,690 --> 00:15:27,945
You basically add these new constraints, 
okay, with the slack variables. 

272
00:15:27,945 --> 00:15:30,630
Okay? 
So you see the slack variables, now, 

273
00:15:30,630 --> 00:15:36,500
which is which is in the basis okay. 
And you see of usually that value here is 

274
00:15:36,500 --> 00:15:40,000
minus 1/2 okay so that's not good. 
That's not primary feasible. 

275
00:15:40,000 --> 00:15:43,550
So you gotta re optimize using the dual 
simplex okay. 

276
00:15:43,550 --> 00:15:46,650
And then essentially what you will get, 
you will get to this spot. 

277
00:15:46,650 --> 00:15:50,143
Of course okay. 
And so this point corresponds to what? 

278
00:15:50,143 --> 00:15:54,090
X1 is about 2/3 right? 
And X2 is equal to 1. 

279
00:15:54,090 --> 00:15:58,370
Hopefully we get that in the tableau, and 
that's what we get, 2 3rds for x1, and 

280
00:15:58,370 --> 00:16:01,040
you know, x2 is equal to 1. 
Okay? 

281
00:16:01,040 --> 00:16:04,480
And we see once again the table, and the 
table is fine, except that when you look 

282
00:16:04,480 --> 00:16:07,990
at the row for x1, you know, x1 received 
the value 2 3rds. 

283
00:16:07,990 --> 00:16:10,400
Okay? 
So we have to generate a new cut. 

284
00:16:10,400 --> 00:16:12,670
Okay? 
So, we generate a new Gomory cut, and 

285
00:16:12,670 --> 00:16:17,480
this is going to be the cut, 2 3rd of x4 
plus 2 3rd of s1 is greater than or equal 

286
00:16:17,480 --> 00:16:18,714
to 2 3rd. 
Okay? 

287
00:16:18,714 --> 00:16:23,356
Now, you look at this thing, and say, 
How did he get the value 2/3 for x1? 

288
00:16:23,356 --> 00:16:27,085
Okay, so look at this, because this is a 
1 minus 1/3 of it. 

289
00:16:27,085 --> 00:16:29,180
Okay? 
Now, this is very simple, right? 

290
00:16:29,180 --> 00:16:33,890
So, -1/3, you run downwards. 
What is the largest integer value which 

291
00:16:33,890 --> 00:16:38,142
is you know smaller than this? 
This is minus 1, so you take minus 1/3 

292
00:16:38,142 --> 00:16:42,070
minus minus 1, which is plus 1, and that 
gives you 2/3, okay? 

293
00:16:42,070 --> 00:16:45,790
So that's how you get 2/3 for this 
particular constraint, okay? 

294
00:16:45,790 --> 00:16:48,430
Now, once again, you have these beautiful 
constraints, you have no clue what it 

295
00:16:48,430 --> 00:16:54,020
means, okay, it's 2/3 of x4 plus 2/3 of 
s1, these are two, one variables where 

296
00:16:54,020 --> 00:16:56,970
the slack introduced at the beginning, 
the other one with the slack introduced 

297
00:16:56,970 --> 00:17:01,260
by the cut, okay? 
the first, you know, the first cut. 

298
00:17:01,260 --> 00:17:04,010
So what do they mean? 
Essentially what do they mean when you 

299
00:17:04,010 --> 00:17:07,550
basically transform you know, using the 
definition of these variables you know, 

300
00:17:07,550 --> 00:17:11,686
when they were introduced, okay. 
It basically gives you the cut x1 minus 

301
00:17:11,686 --> 00:17:16,010
x2 is greater than 0, okay? 
Which is this beautiful cut here that we 

302
00:17:16,010 --> 00:17:19,760
saw before, okay? 
Now we re optimize and we get the optimal 

303
00:17:19,760 --> 00:17:21,950
solution. 
To this MIP, which is going to be this 

304
00:17:21,950 --> 00:17:25,210
beautiful point over here. 
It's an integer and we stop okay. 

305
00:17:25,210 --> 00:17:28,850
Now, this algorithm was invented in 1958 
by Gomory, okay. 

306
00:17:28,850 --> 00:17:34,230
And obviously, at that point, it was 
considered as, you know, an amazing 

307
00:17:34,230 --> 00:17:36,280
achievement. 
Because essentially, you know, people 

308
00:17:36,280 --> 00:17:39,820
think, you know, people had solved linear 
program and that algorithm was telling 

309
00:17:39,820 --> 00:17:44,230
them, no, you can essentially generalize 
that to integer program, just by using 

310
00:17:44,230 --> 00:17:45,970
these beautiful cuts. 
Okay. 

311
00:17:45,970 --> 00:17:50,170
Now one other thing that you have to see 
here is that this is 1958, right. 

312
00:17:50,170 --> 00:17:53,620
So this is before, you know, complexity 
theory was invented. 

313
00:17:53,620 --> 00:17:59,540
Cook invented, you know, complexity 
theory, and p completeness in '70, or '70 

314
00:17:59,540 --> 00:18:04,810
was, I think 1970 or '72 okay, so 
essentially, what we don't know is that 

315
00:18:04,810 --> 00:18:08,570
the difference between linear programs 
and mixed integer program is a big gap, 

316
00:18:08,570 --> 00:18:10,816
right. 
So this is the gap between polynomial 

317
00:18:10,816 --> 00:18:14,680
time and then np completeness. 
So when you run this algorithm, what is 

318
00:18:14,680 --> 00:18:15,940
happening? 
Okay? 

319
00:18:15,940 --> 00:18:20,790
So what is happening is that you may 
generate potentially, an exponential 

320
00:18:20,790 --> 00:18:23,960
number of these cuts, right, otherwise, 
you know, these problems would be 

321
00:18:23,960 --> 00:18:27,260
polynomial. 
Okay, and so essentially at that point 

322
00:18:27,260 --> 00:18:30,870
when people realize that and also did a 
lot of computer experiment using this 

323
00:18:30,870 --> 00:18:34,950
algorithm, so that the conversion of this 
algorithm can be really, really slow, and 

324
00:18:34,950 --> 00:18:36,580
there were, you know, some other issues 
as well. 

325
00:18:36,580 --> 00:18:41,420
So, so that point this algorithm was 
mostly consider as a beautiful 

326
00:18:41,420 --> 00:18:44,330
theoretical result but not practical. 
Okay? 

327
00:18:44,330 --> 00:18:47,875
But science is like the linear 
relaxation, it has, you know, it's very 

328
00:18:47,875 --> 00:18:48,900
unpredicatable. 
Okay? 

329
00:18:48,900 --> 00:18:53,896
And so what happen is that these cuts 
were actually completely revived in the 

330
00:18:53,896 --> 00:18:59,542
90's by, you know, these people, so 
[UNKNOWN] and [UNKNOWN] Ceria, Cornuejol, 

331
00:18:59,542 --> 00:19:02,740
okay? 
In the, and, and what the, what this show 

332
00:19:02,740 --> 00:19:06,580
is that you can actually use this Gomory 
cut inside the branch and bound 

333
00:19:06,580 --> 00:19:08,140
algorithm. 
You have to be a little bit clever. 

334
00:19:08,140 --> 00:19:09,910
You don't want to introduce them one at a 
time. 

335
00:19:09,910 --> 00:19:12,910
You want to introduce them, you want to 
introduce all of them for the tableau at 

336
00:19:12,910 --> 00:19:15,390
the same time. 
You also don't want to introduce them at 

337
00:19:15,390 --> 00:19:17,510
every node. 
You skip some nodes and so on and so 

338
00:19:17,510 --> 00:19:19,740
forth. 
And they showed that they actually were 

339
00:19:19,740 --> 00:19:24,570
the best, that they were all perfect for 
every existing algorithm at that point. 

340
00:19:24,570 --> 00:19:26,930
Okay? 
That was part of the thesis of Sebastian. 

341
00:19:26,930 --> 00:19:29,680
And if you want to read more about this, 
it's very interesting, just, you know, 

342
00:19:29,680 --> 00:19:32,690
look at the article that Gerard 
Cornuejols has written on that. 

343
00:19:32,690 --> 00:19:36,454
So this is very interesting right. 
So Gomory Cuts were basically a really 

344
00:19:36,454 --> 00:19:40,632
you know a major breakthrough and then 
they become an essentially a tiny 

345
00:19:40,632 --> 00:19:46,420
[UNKNOWN] interesting feature and then 
they become essentially completely. 

346
00:19:46,420 --> 00:19:50,530
You know practical again and they are 
essentially integrated in all the 

347
00:19:50,530 --> 00:19:52,870
commercial software now for MIP solvers 
okay. 

348
00:19:52,870 --> 00:19:54,940
Of course you don't generate them all of 
them. 

349
00:19:54,940 --> 00:19:58,460
You only generate a sub set of them but 
they essentially are a big part of every 

350
00:19:58,460 --> 00:20:04,100
commercial MIP system since you know 
Sebastian, Edgar, Cornuejols and and I, I 

351
00:20:04,100 --> 00:20:09,240
don't know the first name of, of Natraj 
but these people actually did this 

352
00:20:09,240 --> 00:20:13,020
computational experiment. 
So, once again this is an interesting 

353
00:20:13,020 --> 00:20:15,320
story here. 
The science is beautiful, but there is 

354
00:20:15,320 --> 00:20:18,150
also a very interesting story personally 
and the story of 

355
00:20:18,150 --> 00:20:20,170
Of, you know, of Gomory is very 
interesting. 

356
00:20:20,170 --> 00:20:23,861
He, you know, after, after having doing a 
lot of science, he went to IBM, became an 

357
00:20:23,861 --> 00:20:26,550
IBM fellow. 
He revolutionized the way IBM did, you 

358
00:20:26,550 --> 00:20:29,960
know, research, you know, and then when 
he was, you know, at the mandatory age 

359
00:20:29,960 --> 00:20:34,480
for retirement he went to the Sloan 
Foundation and, you know, revised, you 

360
00:20:34,480 --> 00:20:36,670
know, and revolutionized the Sloan 
Foundation as well. 

361
00:20:36,670 --> 00:20:38,860
So you should read about him. 
It's very interesting. 

362
00:20:38,860 --> 00:20:42,840
And once again, you know, what you saw 
today is very interesting science and a 

363
00:20:42,840 --> 00:20:45,210
very interesting personal story at the 
same time. 

364
00:20:45,210 --> 00:20:46,730
Thank you.