1
00:00:03,520 --> 00:00:10,199
So, well finish off by taking a brief look
at reductions to linear programming

2
00:00:10,199 --> 00:00:17,317
problems. So, first, first of all, is the
idea of re, reducing to the standard form.

3
00:00:17,535 --> 00:00:24,612
when we first proposed the problem, we did
it in terms of inequalities. And there's

4
00:00:24,831 --> 00:00:31,032
all sorts of different versions that you
might imagine are more convenient for

5
00:00:31,032 --> 00:00:37,120
different types of problems with fewer
restrictions. so as we've talked about

6
00:00:37,341 --> 00:00:43,303
there's easy ways to deal with each of
them the, the standard form is not that

7
00:00:43,303 --> 00:00:49,487
different than the types of things people
might want to do. So, one thing, if maybe

8
00:00:49,707 --> 00:00:55,007
somebody wants to minimize. So, if
somebody wants to minimize, you replace

9
00:00:55,007 --> 00:01:00,675
that minimization with the standard form
says maximize. So, you just negate

10
00:01:00,675 --> 00:01:07,080
everything so that's equivalent. if you
have inequalities, add a slack variable.

11
00:01:07,262 --> 00:01:12,507
subtract the slack variable, it's going to
be positive. That converts a greater than

12
00:01:12,507 --> 00:01:17,935
or equal to constraint to an equality just
by adding a variable. and if you have

13
00:01:17,935 --> 00:01:22,387
variables that are supposed to
unrestricted, just replace it as the

14
00:01:22,387 --> 00:01:29,254
difference between two variables that both
have to be positive. so, so those are just

15
00:01:29,590 --> 00:01:40,119
examples of taking nonstandard form and
reducing it to a problem that's in the

16
00:01:40,119 --> 00:01:47,448
standard form. so for any particular
problem that we might want to come up,

17
00:01:47,448 --> 00:01:52,393
then we can use the less restricted
nonstandard knowing, knowing that, you

18
00:01:52,393 --> 00:01:58,541
know, it's easy to for the LP solver to do
the reduction from our nonstandard form to

19
00:01:58,541 --> 00:02:04,690
the standard form. And certainly that's
something that the solver can do for us.

20
00:02:04,690 --> 00:02:10,343
So actually, I didn't mention at the
beginning is why is it called linear

21
00:02:10,343 --> 00:02:15,377
programming? We're, we're used to
programming that's, say, write Java code

22
00:02:15,377 --> 00:02:21,031
to solve a problem. but you have to
remember, this is 1947 that's actually

23
00:02:21,031 --> 00:02:26,840
well before computers came into use and
people were write, were writing programs

24
00:02:26,840 --> 00:02:32,726
to do this stuff. And actually, for
smaller variables, you can basically solve

25
00:02:32,726 --> 00:02:38,302
it by hand. So, what they meant by
programming was more, there was another

26
00:02:38,302 --> 00:02:44,003
term, it's called planning. And, and so
that was more take your probl 'em and put

27
00:02:44,003 --> 00:02:49,349
it into a form that we can solve.
Nowadays, we call that reduction. redu,

28
00:02:49,349 --> 00:02:54,709
collect reduction to the linear
programming problem. So, it's the process

29
00:02:54,709 --> 00:03:00,549
of formulating your problem at the linear
programming problem. and so, and again,

30
00:03:00,549 --> 00:03:05,098
it's reduction solution to the linear
program gives the solution to your

31
00:03:05,098 --> 00:03:09,785
problem. so what do you have to do? You
have to identify what are the variables,

32
00:03:09,785 --> 00:03:14,355
you have to define the constraints, the
inequalities and equations, and you have

33
00:03:14,355 --> 00:03:18,463
to identify and define an objective
function. That's all you have to do,

34
00:03:18,463 --> 00:03:23,497
though. once you have those things, and
pretty much you have a linear programming

35
00:03:23,497 --> 00:03:28,099
problem. and you do have to convert to the
standard form. But usually, you can count

36
00:03:28,099 --> 00:03:33,528
on the software to go ahead and do that.
so, let's look at some examples that I

37
00:03:33,528 --> 00:03:39,604
have said, reduce to linear programming
problems or can be modeled as linear

38
00:03:39,604 --> 00:03:45,361
programming problems. and, you know, we'll
just use the modern term of reduction. So,

39
00:03:45,361 --> 00:03:52,817
for example, Maxflow problem. so this is
the Maxflow problem that we consider. and

40
00:03:53,095 --> 00:04:02,585
it's input is a weighted digraph. and
there's a source vertex s in a sync vertex

41
00:04:02,585 --> 00:04:11,383
t. and the, the weights indicate capacity.
and we're, we're supposed to find out is

42
00:04:11,576 --> 00:04:16,839
what's the maximum flow from s to t. It
doesn't seem to be that much related to

43
00:04:16,839 --> 00:04:22,738
linear programming. But, if you just look
at the idea, well what are the variables

44
00:04:22,738 --> 00:04:27,791
going to be? the that's going to be and
what are the constraints going to be and

45
00:04:27,791 --> 00:04:32,937
what are the variable flow, the variables
are the amount of flow along each edge.

46
00:04:32,937 --> 00:04:38,595
And the constraints is going to be a
positive flow and it's constrained by the

47
00:04:38,595 --> 00:04:44,183
capacity. So, this is just a mathematical
formulation of the problem. from zero to

48
00:04:44,183 --> 00:04:49,841
one, you have to flow this between zero
and one. from zero to two you have to flow

49
00:04:49,841 --> 00:04:55,638
through zero and three, like that. That is
what I am saying, that's what the capacity

50
00:04:55,638 --> 00:05:01,366
constraints are. And the other thing about
the flow is that we said, the inflow has

51
00:05:01,366 --> 00:05:07,550
to equal the outflow at every vertex. so
we have a variable corresponding to the

52
00:05:07,550 --> 00:05:13,696
flow in each edge and then we can just
express the flow conservation constraints,

53
00:05:13,696 --> 00:05:19,349
the amount that comes into vertex one,
which is X01, has to equal the amount that

54
00:05:19,349 --> 00:05:25,354
comes out which is X13 + fourteen.
And you have one of those constraints for

55
00:05:25,566 --> 00:05:31,501
each one of the vertices. and then, what's
the objective function? Well, you want to

56
00:05:31,501 --> 00:05:39,040
maximize the amount of flow that goes into
number five which is X35 + X45. That's an

57
00:05:39,040 --> 00:05:47,999
LP formulation of the Maxflow problem.
It's really and it illustrates how really

58
00:05:47,999 --> 00:05:54,745
easy it is to represent a maximization
problem as an LP problem. And again, you

59
00:05:54,745 --> 00:06:00,806
have an LP solver you just put in those,
those constraints. so, the variables are

60
00:06:00,806 --> 00:06:06,534
positive, it's just all inequalities and a
couple of equations. then the software

61
00:06:06,534 --> 00:06:12,319
converts it to the standard form and gives
you the solution. Now, it might take

62
00:06:12,319 --> 00:06:20,144
longer than our specialized algorithm that
we looked at based on searching in the

63
00:06:20,144 --> 00:06:25,751
graph and so forth which is a very
wonderful algorithm and very useful and

64
00:06:25,751 --> 00:06:32,005
lots of applications. but the advantage of
the LP formulation is that if the problem

65
00:06:32,005 --> 00:06:37,611
gets more complicated, say, we also want
to insist may be there's cost assigned

66
00:06:37,611 --> 00:06:43,362
with each flow. so you want to maximize
it, but you also want to keep the cost

67
00:06:43,362 --> 00:06:49,831
under control. or any kind of specialized
constraints that might come up. In the LP

68
00:06:49,831 --> 00:06:54,970
formulation, you just add those
constraints you know, in other formulation

69
00:06:54,970 --> 00:07:01,008
it might completely ruin our approach to
the problem. That's the advantage of LP

70
00:07:01,008 --> 00:07:06,973
and why it's so widely used. here's
another example, this doesn't seem at all

71
00:07:06,973 --> 00:07:13,466
to have that much to do with linear
programming but it's the bi-part, maximum

72
00:07:13,466 --> 00:07:19,310
cardinality bipartite matching problem
that we considered, and that's matching

73
00:07:19,310 --> 00:07:26,595
students to jobs. and so this is for we've
got a bipartite graph one set of nodes

74
00:07:26,595 --> 00:07:32,743
corresponds to students, the other set of
nodes corresponds to jobs, we have edges

75
00:07:32,743 --> 00:07:38,511
corresponding to job offers. And if we
want to know the maximum set of edges

76
00:07:38,511 --> 00:07:46,904
connecting one to another the matches a
student to a job. and we did that one by

77
00:07:46,904 --> 00:07:56,666
reducing it to Maxflow, actually. but also
you can just specify it as a an LP,

78
00:07:56,666 --> 00:08:04,815
formulation of an LP problem. So, it's
kind of that's going to be, everything has

79
00:08:04,815 --> 00:08:10,890
got to be zero and it's just going to
maximize this is all the possible

80
00:08:10,890 --> 00:08:16,965
matchings. and then, the constraints are
there has to be at most one job per

81
00:08:16,965 --> 00:08:23,190
person. So, if A has three edges, just say
X0 plus X0 plus the two, less than or

82
00:08:23,190 --> 00:08:29,565
equal to one and do that for each person.
And then, at most one person per job, just

83
00:08:29,565 --> 00:08:36,540
do it that way. Now, these this is not a
trivial reduction. There was some math,

84
00:08:36,540 --> 00:08:43,622
quite a bit of math done early on,
including Von Neumann was involved. So, if

85
00:08:43,622 --> 00:08:51,268
you have a polyhedron like this that where
the right-hand sides of the inequalities

86
00:08:51,268 --> 00:08:57,132
are all one. all the extreme points of
this polyhedron have integer coordinates

87
00:08:57,132 --> 00:09:03,133
that are either zero or one so we need
that theorem. But and it's not always so

88
00:09:03,133 --> 00:09:08,861
lucky, but in this case, you can, you can
do it. and you can just use this linear

89
00:09:08,861 --> 00:09:14,111
programming linear program to solve the
matching problem. Again, no specialized

90
00:09:14,111 --> 00:09:20,398
algorithm, I just throw in your
constraints and you have the solution. use

91
00:09:20,398 --> 00:09:26,368
your LP solver. so that's just two
examples. and there's many, many more

92
00:09:26,368 --> 00:09:30,986
examples. And again, as I said, you can
take a problem like one that we solved and

93
00:09:31,159 --> 00:09:35,488
just add more things. So, I want the
shortest path that doesn't go through a

94
00:09:35,488 --> 00:09:40,337
certain node or that only has the certain
number of nodes on it, or whatever else.

95
00:09:40,395 --> 00:09:45,128
Any other kind of constraints that you
might think of you can just throw them in

96
00:09:45,128 --> 00:09:50,381
if you've got an optimization problem, one
thing you can do is definitely you know,

97
00:09:50,381 --> 00:09:54,941
use an algorithm that you learned and go
to the literature and try to find the

98
00:09:54,941 --> 00:09:59,580
solution. And that is certainly very
effective for many of the fundamental

99
00:09:59,580 --> 00:10:04,638
problems that we've considered. but if
things start to get complicated, it's

100
00:10:04,638 --> 00:10:09,946
really a good idea to think about using
linear programming cuz it's often easy to

101
00:10:09,946 --> 00:10:15,004
model your problem as a linear program.
And you can solve it with a commercial

102
00:10:15,004 --> 00:10:20,936
solver or available, if it's a small one,
a readily available solver. It might take

103
00:10:20,936 --> 00:10:25,931
a little longer than your sp ecialized
solution if you had one, but you might not

104
00:10:25,931 --> 00:10:32,557
care and you might not have one. And the
idea is, it really is a good idea to learn

105
00:10:32,557 --> 00:10:39,405
to use an LP solver. the really the
takeaway from this is there's a lot of

106
00:10:39,405 --> 00:10:46,896
problems that reduce right to linear
programming and we've got a fast way to

107
00:10:46,896 --> 00:10:54,400
solve it. so that's a powerful problem
solving model with broad scope. it's we

108
00:10:54,400 --> 00:11:00,944
can solve it. And we can reduce a lot of
important practical problems to it and

109
00:11:00,944 --> 00:11:06,882
that's why it's important. So, this leads
us to a really profound question that's

110
00:11:06,882 --> 00:11:12,991
called the P and P question. and that'll
tell us and we'll talk about this in

111
00:11:12,991 --> 00:11:18,722
detail in, in the next lecture that
there's condition that is very fundamental

112
00:11:18,722 --> 00:11:25,372
to the efficiency of computation that'll
tell us that people don't think that there

113
00:11:25,372 --> 00:11:31,315
is a universal problem-solving model. for
the time being, however, and for the last

114
00:11:31,315 --> 00:11:36,975
50 years, the closest thing that we have
to a universal problem-solving model is

115
00:11:36,975 --> 00:11:38,320
linear programming.