1
18.415/6.854
Advanced
Algorithms
October
1994
Linear
Programming
Lecturer:
Michel
X.
Goemans
An
Intro duction
to
Linear
Programming
Linear
programming
is
a
very
important
class
of
problems,
both
algorithmically
and
combinatorially.
Linear
programming
has
many
applications.
From
an
algorithmic
point-of-view,
the
simplex
was
proposed
in
the
forties
(soon
after
the
war,
and
was
motivated
by
military
applications)
and,
although
it
has
performed
very
well
in
prac
-
tice,
is
known
to
run
in
exponential
time
in
the
worst-case.
On
the
other
hand,
since
the
early
seventies
when
the
classes
P
and
NP
were
dened,
it
was
observed
that
linear
programming
is
in
NP
\
co-NP
although
no
polynomial-time
algorithm
was
known
at
that
time.
The
rst
polynomial-time
algorithm,
the
ellipsoid
algorithm,
was
only
dis
-
covered
at
the
end
of
the
seventies.
Karmarkar's
algorithm
in
the
mid-eighties
lead
to
very
active
research
in
the
area
of
interior-point
methods
for
linear
programming.
We
shall
present
one
of
the
numerous
variations
of
interior-point
methods
in
class.
From
a
combinatorial
persp ective,
systems
of
linear
inequalities
were
already
studied
at
the
end
of
the
last
century
by
F
arkas
and
Minkovsky.
Linear
programming,
and
especially
the
notion
of
duality,
i
s
v
ery
important
as
a
proof
technique.
We
shall
illustrate
its
po
wer
when
discussing
approximation
algorithms.
We
shall
also
talk
about
network
ow
algorithms
where
linear
programming
plays
a
crucial
role
both
algorithmically
and
combinatorially.
F
or
a
more
in-depth
coverage
of
linear
programming,
we
r
e
f
e
r
the
reader
to
1,
4,
7,
8,
5].
A
linear
program
is
the
problem
of
optimizing
a
linear
ob jective
function
in
the
decision
variables,
x
1
: : : x
n
,
sub ject
to
linear
equality
or
inequality
constraints
on
the
x
i
's.
In
standard
form,
it
is
expressed
as:
n
X
Min
c
j
x
j
(ob jective
function)
j
=1
sub ject
to:
n
X
a
ij
x
j
=
b
i
i
=
1
:
:
:
m
(constraints)
j
=1
x
j
0
j
=
1
:
:
:
n
(non-negativity
constraints)
where
f
a
ij
b
i
c
j
g
are
given.
A
linear
program
is
expressed
more
conveniently
using
matrices:
(
Ax
=
b
min
c
T
x
sub ject
to
x
0
LP-1
评论0