PREFACE

  During the past decade, linear programming has gone
through a dramatic
change. The catalyst for this change is the path
breaking work of Narinder K.
Karmarkar who, in 1984, presented a polynomial time
algorithm generating a
sequence of points in the interior of the polyhedron.
This method contrasts with
the earlier state-of-the art methods that generate a
sequence of points on the
boundary of the polyhedron. The most notable, and the
earliest of these is the
simplex method of George B. Dantzig, produced in 1947.
The new methods that
proceed through the interior of the polyhedron avoid
the combinatorial structure
of the boundary, which the boundary methods must
necessarily contend with. A
consequence of this is that even though many of the
interior point methods are
shown to be polynomial, an example produced in 1971 by
Victor L. Klee and George J. Minty demonstrates that in
the worst case, simplex method can take an
effort which grows exponentially in the data of the
problem. Thus, for large
problems, the interior point methods may be
advantageous. A growing body of computational
experience appears to support this conclusion.

  Interior point methods trace their roots to the work
of I. I. Dikin in 1967. His method is called the
(primal) affine scaling method, and was re-discovered
by researchers at A. T. \& T. Bell Telephone
Laboratories while implementing the ideas of Karmarkar
in a system called KORBX. Several variants of this
method, like the dual and the primal-dual were also
generated in the process. Since then, many new methods
like the sliding objective function methods, the path-
following barrier methods, and potential reduction
methods have been generated. Several successful
implements of these also exist in the public domain.

  This book presents both the boundary and the interior
point methods in a unified manner. Approach taken here
involves the use of duality theory,  in particular the
complementary slackness conditions, to derive both the
boundary and interior point methods. Most text books on
linear programming derive the duality theorems after
presenting the computational aspects of the simplex
method. And the theorems of the alternative (like
Farkas' lemma) are then derived as corollaries to the
duality theorems. This approach is unsatisfactory for
our purpose. The approach taken here is to prove
Farkas' lemma and other theorems of the alternative as
convex separation theorems, and then derive the duality
theorems directly from this lemma. Thus the tedium of
the simplex method is avoided. In addition several
concepts like the existence of strict complementary
solutions are generally derogated to an exercise at the
end of the duality chapter. These results play an
important role in interior point methods, and are thus
proved explicitly in the duality chapter of this book.

  The author has been teaching and developing the
methodology for presenting these ideas in several
courses taught at the University of Michigan in Ann
Arbor, Michigan and the Naval Postgraduate School in
Monterey, California and has paid special attention to
the mathematical background required for the study of
interior point methods. To study the boundary methods,
it is sufficient to have a good background in linear
algebra, numerical linear algebra and polyhedral
convexity. The study of recent methods, in addition,
requires sufficient background in real analysis,
convexity and separation theorems as well as an
understanding of the methodology for solving nonlinear
systems of equations, specially Newton's method and
homotopy or global Newtons' methods and their
implementations. Thus a chapter presenting this
background material has been
included in this manuscript.

  This book is organized into six chapters.  Chapter 1
introduces the problem and some standard formulations
to orient the reader to linear programming. In the
second chapter, careful attention is paid to the
necessary mathematical background required for the
study of these methods. The third chapter presents the
duality theorem and also the important results on
complementary slackness conditions. The fourth chapter
presents the three important variants of the simplex
method, the primal, the dual and the primal dual
methods. The fifth chapter presents the interior point
methods. It covers the affine scaling methods, the
projective transformation methods, the barrier methods
as well as the primal-dual homotopy or global Newton
methods. Finally the chapter six is devoted to the
implementation of both the interior and the boundary
methods. Sparsity preserving and stable methods for the
boundary and interior methods are also discussed in
this chapter.


  This book can be used as a text in a one or two
semester advanced graduate course in linear
programming. A good two semester sequence could cover
sections 2.4 - 2.6, terminating with the proof of
Farkas' Lemma. Then after proving the duality theorems
of Chapter 3, establish the primal simplex method. Then
cover Chapter 5 and establish the primal and dual
affine scaling method, and the path following method.
During the first semester, cover only the convergence
of boundary and interior methods with the non-
degeneracy assumption. During the second semester,
prove the convergence of these methods under
degeneracy, establish the dual simplex method, primal-
dual boundary methods; and the power affine scaling
method. During this semester, also cover the
implementations of Chapter 6.

  The writing of this book would never have been
completed without encouragement, help and comments from
several people. This is gratefully acknowledged from
John R. Birge, Steve Chen, S.-C. Fang, Hans Kremers,
Masakazu Kojima,  Prashant M.  Kulkarni, Masakazu
Muramatsu, Shinji Mizuno, Sarat Puthenpura,
Krishnamachari S. Ramprasad, Lakshman P. Sinha,
Manmohan S. Sodhi,  Samer Takriti, Takashi Tsuchiya and
Terrance C. Wagner. I am also grateful to the editor
Gary Folven of Kluwer Academic Publishers, for his kind
words and constant encouragement. Some of the research
presented in this book was supported by the grant
number CCR 9321550 from the National Science
Foundation. I thank NSF (and the project director S.
Kamal Abdali) for this support.

  Romesh Saigal
  Ann Arbor, Michigan.
  June 1, 1995