,Preface
⋆ This course is intended primarily for upper-level undergraduate mathematics majors, although
math education, economics, computer science, and other majors regularly frequent my course,
including some graduate students (in fact, many of the challenges and projects are aimed at
graduate students). But the focus, as you will read about, is centered more on the understanding
of the mathematics itself (and mathematical applications) than on the industrial applications
and use of relevant software to solve large problems. That doesn’t mean one can’t use this text
for such other purposes, and I hope you’ll see that you can, but instead that we want to do
mathematics first and foremost. There are plenty of books that follow the applied model for
teaching this subject, and too few that follow the path we outline below. We do assume that
students have passed the usual introductory courses in linear algebra, computer algorithms, and
proof writing — typical requirements of all math majors.
The Subject
A little explanation is in order for our choice of the title Linear Optimization1 (and corresponding
terminology) for what has traditionally been called Linear Programming. The word programming in this
context can be confusing and/or misleading to students. Linear programming problems are referred to as
optimization problems but the general term linear programming remains. This can cause people unfamiliar
with the subject to think that it is about programming in the sense of writing computer code. It isn’t. This
workbook is about the beautiful mathematics underlying the ideas of optimizing linear functions subject
to linear constraints and the algorithms to solve such problems. In particular, much of what we discuss is
the mathematics of Simplex Algorithm for solving such problems, developed by George Dantzig in the late
1940s.
The word program in linear programming is a historical artifact. When Dantzig first developed the
Simplex Algorithm to solve what are now called linear programming problems, his initial model was a class
of resource allocation problems to be solved for the U.S. Air Force. The decisions about the allocations were
called ‘Programs’ by the Air Force, and hence the term. Dantzig’s article2 is a fascinating description of the
origins of this subject written by the person who originated many of the ideas. Included is a description of
how Tjalling Koopmans (who won a Nobel Prize in economics for his work in decision science) suggested
shortening Dantzig’s description ‘programming in a linear structure’ to ‘linear programming’ during a walk
on the beach with Dantzig. Also included is a note that, at the time, ‘code’ was the word used for computer
instructions and not ‘program’.
To be clear to potential and current students that this is a mathematics course requiring a background
in writing proofs and not a computer coding class, we prefer the terminology linear optimization. We do
look at computer algorithms but focus on the underlying mathematics. A small amount of computer coding
(for example, simple MAPLE) programs will be very useful, but writing code is not the central purpose of the
course. The shorthand LP has been used to refer to both the general subject of linear programming as well
as specific instances of linear programs. To distinguish, in our notation, LO (linear optimization) refers to
1 I’m not that original — there are at least a dozen books that use this terminology.
2 G. Dantzig, Linear Programming, Operations Research 50 (2002), 42–47.
,viii Preface
the general class of optimizing linear functions subject to linear constraints while LOP (linear optimization
problem) refers to specific instances of such problems. Furthermore, using the optimization term brings
the subject in line with other, closely related fields that are increasingly called Optimization (Nonlinear,
Quadratic, Convex, Integer, Combinatorial).
⋆ Of course, if you are more inclined to maintain the status quo, feel free to continue verbalizing
“ell-pee” in place of “lop”; beware, however, that the extra syllable spoken repeatedly over the
course of an entire semester can take its toll on your energy.
The Simplex Algorithm is the focus of study in this book. In particular, we do not discuss Karmarkar’s
Algorithm or Khachian’s Ellipsoid Algorithm or more general interior-point approaches to solving LOPs. The
main reason for this is that, as I hope you’ll experience, the Simplex Algorithm leads to richer connections
with linear algebra, geometry, combinatorics, game theory, probability, and graph theory. Furthermore, in
the post-optimality analysis that occurs in economic modeling and in Integer Optimization, the Simplex
Algorithm plays a central role.
⋆ For a superb and extensive treatment of interior methods, let me suggest [14]].
Why Teach This?
This is a reasonable question, and there are better answers than, “Why not?” and, “Because it’s
cool!”
One of the areas in which Mathematics departments lag behind those of, say, Physics and, most
notably these days, Biology, is in the delivery of up-to-date discoveries in the subject (galaxies, big
bang, genomics, medicine, etc.). Today’s college mathematics curriculum is virtually unchanged from
50 years ago — go into your library and look at the degree requirements from 1960, or 1940, for
that matter — and, in order to compete for majors, departments need to be perceived by students as
far more relevant to the modern world. One of the main recommendations of the CUPM Guide,3 in
fact, is awareness of connections to other subjects and introducing contemporary topics to enhance
student perceptions of the vitality and importance of mathematics in the modern world.
For example, the Simplex Algorithm is widely recognized4 as one of the top ten algorithms of the 20th
century for its widespread use, its powerful applications to industry and to mathematics, it’s elegant
simplicity, and it’s fascinating mathematical underpinnings, and yet, the percentage of departments
offering LO in 2000–01 was only 13%.5 Given the revolution that the subject has brought to the
business world alone, it is difficult to argue against having the subject available to math majors at
virtually every school in the country.
The case for LO increases when we realize that most of the students in mathematics programs do
not go on to graduate school, but instead to jobs in a wide range of industries. In fact, 92% of
students earning bachelor’s degrees in the mathematical sciences from 1994–96 went directly into the
workforce, many of whom ended up in management.6 How nice it would be for them to have such a
tool as Simplex, or at least to know of the benefits of optimization to their enterprise. In addition, a
significant portion (26% in 20007 ) of students taking upper division courses are preservice secondary
mathematics teachers. This is relevant because Discrete Mathematics is now in state curriculum
3 Undergraduate Programs and Courses in the Mathematical Sciences: CUPM Guide 2004, www.maa.org/cupm.
4 J. Dongarra and F. Sullivan, Top ten algorithms of the century, Computing Science and Engineering, January/February
2000.
5 D. J. Lutzer, J. W. Maxwell and S. R. Rodi, Statistical Abstract of Undergraduate Programs in the Mathematical Sciences
in the United States: Fall 2000 CBMS Survey, AMS, 2002.
6 National Survey of Recent College Graduates, National Science Foundation, 1997, www.nsf.gov/sbe/srs/nsf01337.
7 Statistical Abstract, op. cit.
,Preface ix
standards throughout the country, and LO is listed in that category in many states.8 How nice it
would be for our high school teachers to understand more of the applicability of the algebra they
teach.
Moreover, our undergraduate curricula compartmentalizes topics. Consequently, most math majors
graduate with a sense that many of their courses have little or nothing to do with each other. A class
in LO can do much to counter this misimpression, blending linear algebra, geometry, modeling, prob-
ability, game theory, algorithms, combinatorics, graph theory, computer programming, and theoretical
computer science into one big, tasty LOG.9
Finally, why not teach it? It’s cool!
Terminology
Besides the usage of LOP and ILOP, we introduce other quirks into the language, mostly for handiness
and consistency and occasionally for fun. For example, we discuss four kinds of linear combinations, based
on whether or not the extra affine and conic conditions hold, so it makes sense to use the similar notations
lspan, aspan, nspan, and vspan for linear, affine, conic, and convex (both affine and conic) combinations,
respectively. In particular, lspan makes more sense in this scheme than does span, the more common term
found in linear algebra texts. Geometric hulls get the same treatment, with lhull, ahull, nhull, and vhull,
respectively. For fun we use the term FLOP (Fractional LOP) when we need to distinguish a LOP from
being an ILOP. Indeed, the first step in solving an ILOP is to relax the integer constraints to allow for
rationals and find the resulting floptimal solution, which is used as a first approximation to the iloptimal
solution. The term BLOP refers to an ILOP whose variables are binary (either 0 or 1).10 Also, when we
discuss game theory, we talk about the GLOP (Game LOP) derived from a game. We don’t go too much
farther down the self-parody road — hopefully there is no SLOP in the book.
I think we’re also the first LO book to use the term parameter in place of nonbasic variable. That must
be worth some kind of award, right? Actually, I stole it from virtually every linear algebra text ever written.
Chapter Flow
Outlandish as it may seem, someone studying from this text will need to start with Chapter 1, followed
by Chapter 2. After that, there are many directions of travel.
⋆ Each chapter includes an initial commentary that elaborates further on the following — which
parts of the chapter need what prerequisites and which are prerequisites for others.
If and when you wish to study geometry, you’ll want to learn Chapter 3 before Chapter 8, but you can
pretty much learn them whenever you want. No other chapter uses Chapter 3 explicitly, although it does
offer very beneficial intuition that permeates almost every other chapter. This is why it is placed so early.
Chapter 8, however, isn’t necessary for much (unless one continues on to study graduate level optimization),
but does use material from Chapter 7 (and Section 8.4 needs Chapter 6) — and is kind of fun.
⋆ Chapter 3 can be replaced by Chapter 0 for those who like to develop students’ theorem-proving
abilities right off the bat. I sometimes enjoy using Chapter 0 as a theoretical, rather than
industrial motivation for developing the Fundamental Theorem of Linear Optimization 2.9.1.
8 In fact, this course covers 8 of the 10 NCTM standards (Algebra, Geometry, Data Analysis and Probability, Problem
Solving, Reasoning and Proof, Communication, Connections, and Representation) — one summer I taught a special section of
the course to high school teachers who benefitted greatly from such breadth.
9 Linear Optimization Goulash.
10 Thus it is quite natural for many academics to be interested in BO.
,x Preface
Chapter 4 is really the heart of the course. Everything feeds off of duality. This is why we derive the
dual immediately in Section 1.1. Spending extra time here pays dividends later, as everything thereafter
depends critically upon it.
The material of Chapter 5 is useful for learning the tip of the how-this-is-done-in-the-real-world iceberg.
The ability to state and work with everything in matrix form is a very useful skill in general, and in particular
comes in handy in Chapter 12. Thus it does not need to be studied before any other chapter (if at all, as it
is not essential material otherwise — in fact, Chapter 5 is only crucial to proving Theorem 12.1.4).
Chapter 6 puts Chapter 4 in general context, and is required for all subsequent chapters.
⋆ It is possible, however, to cover the material of Chapter 6 more informally, as needed. In fact, as
with most chapters, one can decide to present only its first two sections (maybe plus its Section
3 Practice) in an effort to cover a broader spectrum of material. This text is designed for such
a degree of flexibility.
Chapter 7 contains material that is necessary for Chapter 8. Chapter 9 is not needed by anyone who
doesn’t want to have a good time. Chapter 10 is required by Chapter 11, and Section 12.4 is key for Chapter
13. Chapters 7–13 offer the greatest flexibility for studying your favorite topics within a semester’s time.
Of course, you could slow down, spend extra time on the exercises, and complete the whole book in two
semesters. Have at it!
A visual description of the above dependencies is given below.
Book Format and Usage
It is not difficult to notice that this text is different from most, and not just because I can’t resist even
the lamest of jokes,11 so it may be worth some discussion on why this is so, what benefits this may have for
you, and how best to take advantage of the new format.
First and foremost, a great deal of information is missing, information that typically is included in
mathematics texts.
⋆ Most texts prohibit discovery style learning by explaining everything in sight on the page, leaving
little room for instructor influence, whereas the premise of the discovery method is to withhold
information! The commonly reported benefits of the approach (increased understanding, reten-
tion, enjoyment, motivation, confidence, etc.) motivate this format, from which you can decide
how much more you wish to share with your students.
Having spent most of your life reading from such texts, you may be used to being fed facts and algorithms,
and well used to memorizing them in order to reproduce them on exams. But I believe that you are capable
of much more: of deriving results, in fact, discovering them through experimentation, of making conjectures,
of proving theorems, of solving problems and checking them yourself, and of asking creative questions.
11 Most of these require my age to understand anyway.
,Preface xi
That’s what this format is all about, giving your professor the opportunity to lead you through the kinds of
experiences that will develop your skills in each of these areas, helping you become a highly critical thinking
machine,12 able to wrestle with complex problems in all areas of society, rather than just someone who went
to college and remembers a few math facts.
⋆ There is often a big gap between the typical 2–3 line proofs that students are asked to master
in the usual Introduction to Proofs course that math majors take as Sophomores or Juniors, and
the 3–4 paragraph proofs that they are asked to understand in most Senior level courses. The
intention of some of the workouts is to bridge this gap. You’ll notice that most of the main
theorems are followed by a sequence of workouts that form the outline of proof. Students can
be expected both to understand that such an outline will prove the theorem, and to prove the
individual parts. By interacting with the proof in this way they may come to understand the
proof at hand better and be more able to construct their own proofs of other theorems. It could
be said that our approach to discovery learning is halfway to the Moore Method. While we
typically will not divulge the full proof, students are not left on their own either. It’s as if we
give them the road map but they still have to drive the car.
You may find that your classroom environment may also differ from the norm. Many professors who use
this will ask their students to participate more in discussion, rather than simply listen to lectures. Some
may even ask their students to make daily presentations of the theorems they’ve proven, the exercises and
workouts they’ve solved, and the algorithms they’ve written, in order to create an environment in which
the students become responsible for their own learning, questioning each other for understanding, while the
professor acts as a facilitator. Such an environment may be upsettingly abnormal to you initially, but I
promise you will warm to it (indeed, embrace it) in time.
⋆ Not that you have to teach like this, but many who do know that you usually have to sell the
students a little on using methods so contrary to their 12–15 years of experience with being
lectured to. Natural resistence to change, coupled with difficulty adjusting to new expectations,
can turn into revolt and blame if not handled carefully in advance. When things go well for a
student, they will have every right to take all the credit, but when things don’t they will most
certainly look at you as their scapegoat, so this kind of preparation and a great amount of
conviction can be critical.
This form of discourse centers more on the learning than the teaching, and those who engage in it deeply
are affected (infected?) for life. My hope is that you are enticed enough, not only by the material, but
by the interesting problems, challenging questions, and your professor’s invitation to question, challenge,
wonder, experiment, guess, and argue, to throw your energies in this new direction so as to be stirred to the
point that it transforms the way you think about everything, from mathematics and science, to politics and
religion, to sports and fine arts. Be inquisitive, be skeptical, be critical, be creative, and keep thinking.
⋆ Make note of the many exercises such as 1.5.6 in the book that are meant to develop students’
habits, abilities, and confidence to investigate their own questions, find their own patterns,
and check their own work. LO is unique in this latter respect — duality and other forms of
certification give students the power to know when they are right or wrong.
Keep in mind, this isn’t some crazy, new, experimental pedagogy. This approach is as old as it gets,
predating all forms of formal classroom teaching. It has come to be known by many names through the
years: the Socratic Method, Discovery-Based Teaching, the Moore Method, and Inquiry-Based Learning,
among others. There are maybe two central tenets that identify the philosophy.
• A thing isn’t true because someone says so or because it’s written in a book, but because it is reasoned
to be true.
12 You can even wear a cape: leap tall buildings, etc.
,xii Preface
• One doesn’t master something by hearing or seeing it, but by doing it.
⋆ Parker says that13 it is less a method than “a commitment to teaching by letting students
discover the power their own minds have.” With that in mind, what I’m trying to provide here
are materials to help you teach your students that they don’t need you! When I hand out a
syllabus at the beginning of the semester I include in it a few sales pitches for what they are
about to encounter. Quotes such as the following have proven useful.
– That student learns the most who is told the least. — R. L. Moore
– I hear, I forget; I see, I remember; I do, I understand. — Chinese proverb
– Problems worthy of attack prove their worth by fighting back. — Piet Hein
– Mathematics is not a careful march down a well-cleared highway, but a journey into a strange
wilderness, where the explorers often get lost. — W. S. Anglin
– To imagine is everything; to know is nothing at all. — Anatole France
Feel free to steal these or find others that work best for you. An excellent resource for all things
Moore-ish is the recent book by Coppin et al.14
So what else can you do outside of the classroom in order to master this material? Some students find
that keeping a journal, separate from their class notes, that holds all their proofs and solutions, can be quite
useful. This is especially true if one uses a word processor (LATEX is certainly best, whether using AMSTeX
on Linux, MiKTeX through WinEdt or Scientific Word on Windows, or even with TeXShop on MacOS,
although Microsoft Word, with its Equation Editor should suffice), since the work can continue to be edited
and organized to follow the text. Also, do the workouts as you read along, such as the very first one:
Workout 0 What pattern is there regarding Section 3 of each chapter?
The headings of such sections use Latin-based alphabets precisely in composite-numbered chapters.
⋆ You see now how material for teachers’ eyes only is indented in sans serif font, with solutions
to problems unstarred and comments like this distinguished by a star and further indented. The
comments will sometimes point to further ideas, references, activities, or connections with prior
and subsequent material, workouts, theorems, or exercises.
The point of doing them as you go is partly to help you learn the material by making sure you read the
stuff (I can remember undergraduate books that I wouldn’t read at all, instead just solving the exercises
required for homework by mimicking the examples — what kind of comprehension does that foster?), and
partly to help you learn the process of experimenting, conjecturing, clarifying, strategizing, proof writing,
and generalizing. That will serve you long after you forget the Complementary Slackness Theorem.
⋆ Regarding end of chapter Exercises, they are split into three levels. Practices are meant to
directly apply the lessons of the chapter, mostly in the form of calculating answers and proving
simple statements. Challenges offer interesting questions and problems that require deeper
thought and more demanding proof. Projects are longer term suggestions for term papers,
group presentations, senior theses, capstone experiences, research, and so on. Maybe some
exercises are miscategorized here and there — just let me know.
On the other hand, you can simply distract yourself with the trivia contest that floats throughout the
book, signified by the ◦ in the margins. Of course, you have to swear not to Google anything if you want to
win.
13 G.E. Parker, Getting more From Moore, Primus 2 (1992), 235–246.
14 C.A. Coppin, E. L. May, W. T. Mahavier, and G. E. Parker, The Moore Method: A Pathway to Student-Centered
Instruction, in press, MAA, Notes Series.
,Preface xiii
Why Teach Like This?
Well, of course, you don’t have to. I intended to write something flexible enough to be used by
practitioners of all methods. You be the judge of the extent to which I have succeeded. In particular,
during the several years of development, I have used a variety of approaches, including
• lecturing to a large class (in which students took good notes to fill in the solutions to workouts),
• going Full Moore15 with a small class (in which students presented their solutions to workouts
all day, every day),
• using various combinations of these two extremes, as well as in-class group work and other
interactive activities.
Sometimes, if the proof of a theorem has, say, three steps set up as workouts, I might do somthing
like lecture through the first workout, have students work in pairs to figure out the second in class,
and assign the third as individual homework to be presented the following day. It may be that a
student began the class by presenting MAPLE results from a workout I assigned for homework that
facilitated discovery of the theorem. The point is, do what you feel comfortable doing, and try new
ideas if you like. Hopefully this format will help you be successful whichever way you choose. Maybe,
like me, you’ll want to use it differently each time you teach from it (which in and of itself can keep
your teaching fresh).
That being said, there are reasonable apologies for more Socratic approaches. I find it difficult not
to be influenced by the writings of Schoenfeld16 and Smith,17 for example. And as suggested above,
there are few references better than Coppin et al.18 for suggestions on fostering a productive classroom
environment, handling the different rates at which students absorb material, grading, and so on.
References
Many practitioners of discovery-based methods make informal agreements with their students not to
refer to any outside sources. Surprisingly, especially how trivial it is these days to locate and access
such materials, students tend to respect such agreements very well. That being said, not every book
has the same target audience, so it may be useful for me to attempt a rough characterization of a
small sampling of excellent references, revealed, as usual, only to you.19 This should also help to
point out the niche that the present treatise is trying to serve. Texts covering LO (and in particular
the Simplex Algorithm) can be placed into the following six groups.
1 Finite mathematics texts. These have elementary treatment of the Simplex Algorithm, duality
and modeling with no mathematical proofs. Such texts assume little or no mathematical so-
phistication and in particular students need not have had calculus. There are very many such
standard finite mathematics texts, for example [10]].
2 Linear algebra texts that include a very brief treatment of linear optimization as a topics chapter
at the end. These are numerous.
3 Texts aimed at engineering or business users of linear optimization, with more sophisticated
mathematics than those in group 1 but with the goal of being able to model and solve linear
optimization problems as a tool in engineering or business applications. These typically assume
15 Really only Near Moore — Full Moore doesn’t allow texts of any kind.
16 A. H. Schoenfeld, When good teaching leads to bad results: The disasters of “well taught” mathematics courses, Educational
Psychologist 23 (2), Spring 1988.
17 J. C. Smith, A sense-making approach to proof: Strategies of students in traditional and problem-based number theory
courses, Journal of Mathematical Behavior 25 (2006), 73–90.
18 C. A. Coppin, op. cit.
19 Because I like you, I give you such a deal.
,xiv Preface
the mathematical sophistication of sophomore/junior engineering or senior/graduate business
student and do not include many proofs. Classic texts of this type are [8, 19]], two of the market
leaders.
4 More mathematically sophisticated versions of those in group 3. See [6, 12, 17]].
5 Books appropriate for graduate level study either in mathematics or industrial engineering/oper-
ations research/computer science ( [2, 5, 9, 11, 13–15]]).
6 Texts such as the famous classic20 aimed primarily at upper level mathematics majors, with
varying degrees of focus on proofs and mathematical development (see [16, 18]]).
Technology
Another of the recommendations of the CUPM Guide21 is to incorporate technology as a tool for
solving problems and as an aid to understanding mathematical ideas. Most texts aim for software
that solves moderately large LOPs (such as CPLEX, LINDO, etc.). Instead, I developed a web
browser application (WebSim) for pedagogical use in order to facilitate conceptual understanding of
the subject. Students can use it to explore and discover, as well as solve small problems.
One of the things that distinguishes this text from all others is that it uses integer arithmetic always.
This greatly simplifies exposition and calculation, and highlights the role of basic determinants, espe-
cially in relation to combinatorial applications that rely on total unimodularity. WebSim follows suit
by using integer arithmetic as well.
I also encourage use of MAPLE software for three purposes. First, its geometric visualization tools,
both static and dynamic, are very useful in bridging between geometry and linear algebra, as well as
in motivating algorithms and problem solutions. I provide many instances of code for illustrative use
in class. Second, its programming environment is very flexible and simple to learn, with excellent
help menus, and one can build up programs from individual executable lines quite easily. I find that
most students can write their own Simplex code over the course of a semester, building upon a pivot
procedure within the first few weeks. Third, it contains an LO solver that can be used when you need
it.
I include descriptions of how to use each of these in Appendix D. Of course it isn’t necessary to use
MAPLE, although I believe typical mathematics and math education majors could use a whole lot
more programming experience than they are required to have, in order to be more successful in their
chosen careers. Most of my students end up buying the student version of it at a reasonable price,
discounted more than normal by the program MAPLE has for students whose course requires it.
Index
Just a small note about the Index. I believe that index entries should signify what’s memorable, not
important — importance should be indicated by the page references instead. So in this era of inclusivity,
I’ve thrown in the kitchen sink. The main reason for this is that I don’t know how your memory works.
It doesn’t help you if you can’t find tractor pull because it’s only listed under theological tractor pull and
you couldn’t remember the obvious connection to theology. So the index is fattened by including various
permutations of words. Also, even though tractor pull is not central to the theory of linear optimization,
in 25 years when you’re trying to show your kids a nice example of how the theory works and all you can
remember is that awesome example with the tractor pull, you’ll thank me. Plus, this adds an extra page
to the book, which increases its cost by .037c/. With about 2.7 million readers annually, my 1% commission
generates an extra deluxe cheeseburger per year, which in turn helps me satisfy the requirements of Problem
20 Um, you’re reading it.
21 CUPM Guide, op. cit.
, Preface xv
1.1.1 for that day. While the entries are many, I did make an effort to restrict the page references of the
most common terms to their most important instances.
With regard to the fonts you’ll encounter, theorems (in their full names) are in italics, and page numbers
that refer to definitions are in bold. (You’ll notice that theorems and definitions find their way into the
margins for easy location.) Italicized page numbers denote appearances in theorems, while sans serif numbers
signal inclusion in workouts and exercises, and roman fonts cite regular occurrences of the term. With regard
to the order of terms, mathematical symbols come first (numbers, then capital letters, then lower case letters),
followed by As,22 and then standard words.
Thanks
I wish to express my gratitude to many people who have helped bring this project to fruition. First
and foremost is Garth Isaak, who really helped me get the ball rolling in many ways and contributed a
number of great ideas at the start. Rob Hochberg and Nate Dean were excellent sounding boards for crazy
ideas, some of which found their way onto these pages and some of which didn’t. The National Science
Foundation was instrumental for funding the time for me to get the bulk of it up and going. Several
semesters worth of students tested early versions of the material, and Josh Maximoff and Ben Hester in
particular combed through many exercises carefully. Other students, Sriram Penumatcha, Jake Hawkes,
and Josh Wolfe, developed WebSim with me, and Jennifer Broatch organized the assessment of the book’s
methods for the NSF. Much appreciation goes to Harry Lucas and the Educational Advancement Foundation
for supporting conferences and workshops dedicated to the pedagogical approach of R.L. Moore, in particular,
the Legacy of Moore Conferences at the University of Texas, and the Inquiry-Based Learning Workshops
run by Stan Yoshinobu, Ed Parker, Carl Leinart, and Jenny Smith. I will even thank Mike Starbird for
many a conversation more fruitful to me than he might imagine. Francis Su’s MAA PREP Workshop
on Combinatorial Geometry and Mike Jones’s MAA Short Course on Game Theory were quite beneficial
as well. Several colleagues piloted versions of the course at various stages of development and offered
significant feedback, including Dan Biebighauser, Nancy Childress, Steven Dunbar, Mark Ellingham, Gary
Gordon, Donovan Hare, and Attila Sali. Many thanks are due to those who helped me with foreign language
translations: Hélène Barcelo, Airat Bekmetjev, Anthony Chambers, Gil Kalai, Vikram Kamat, Irina Long,
Rose Sau Lugano, Mkamburi Lyabaya, Faris Odish, Andrea Richa, Derar Serhan, Nandor Sieben, and
Jennifer Tom, and especially to Klaus Lagally, Dominik Wujastyk, and Rajiv Monsurate for their assistance
with LATEX language packages (and to Renate Mittelmann for loading things for me). Of course, I really
also need to thank Don, not only for creating TEX in the first place, but also for the excellent sense of taste ◦
and humor displayed in his own texts, not that I stole any ideas or anything. The Coffee Buzz, Lilo’s Coffee
Haus, The Harem, Bunna Coffee & Tea Market, Steve’s Espresso, Extreme Bean Coffee Co., and Gold Bar
Espresso deserve much credit for comfortable and creative writing environments (sorry if your copy has any
coffee stains on it). Finally, the tremendous group at Springer deserves a raise for putting up with me:
Vaishali Damle, Frank Ganz, Marcia Bunda, Frank McGuckin, and players to be named later.23
Feedback
Thanks to the many students and professors and editors (in particular, Christopher Curioli) who combed
through this book before its printing, the text would have been perfect if not for me. Any errors in typography
or content that remain are clearly the fault of some guy I met on the bus one day who distracted me, scattering
errors of varying types throughout the book. If you tell me about them I’ll be sure to let him know if I ever
happen to see him again. I will also try to correct them before the 7th edition. From my web site (search
for Hurlbert math homepage), click on the LinOpt logo and scroll down to the Submit Feedback link. You
can search to see if your idea has already been posted, and otherwise post it by Chapter, Section, and Type
of Error for others to see, and it will be on queue for the next revision.
22 Short for Acronyms.
23 I might trade for some draft picks.
⋆ This course is intended primarily for upper-level undergraduate mathematics majors, although
math education, economics, computer science, and other majors regularly frequent my course,
including some graduate students (in fact, many of the challenges and projects are aimed at
graduate students). But the focus, as you will read about, is centered more on the understanding
of the mathematics itself (and mathematical applications) than on the industrial applications
and use of relevant software to solve large problems. That doesn’t mean one can’t use this text
for such other purposes, and I hope you’ll see that you can, but instead that we want to do
mathematics first and foremost. There are plenty of books that follow the applied model for
teaching this subject, and too few that follow the path we outline below. We do assume that
students have passed the usual introductory courses in linear algebra, computer algorithms, and
proof writing — typical requirements of all math majors.
The Subject
A little explanation is in order for our choice of the title Linear Optimization1 (and corresponding
terminology) for what has traditionally been called Linear Programming. The word programming in this
context can be confusing and/or misleading to students. Linear programming problems are referred to as
optimization problems but the general term linear programming remains. This can cause people unfamiliar
with the subject to think that it is about programming in the sense of writing computer code. It isn’t. This
workbook is about the beautiful mathematics underlying the ideas of optimizing linear functions subject
to linear constraints and the algorithms to solve such problems. In particular, much of what we discuss is
the mathematics of Simplex Algorithm for solving such problems, developed by George Dantzig in the late
1940s.
The word program in linear programming is a historical artifact. When Dantzig first developed the
Simplex Algorithm to solve what are now called linear programming problems, his initial model was a class
of resource allocation problems to be solved for the U.S. Air Force. The decisions about the allocations were
called ‘Programs’ by the Air Force, and hence the term. Dantzig’s article2 is a fascinating description of the
origins of this subject written by the person who originated many of the ideas. Included is a description of
how Tjalling Koopmans (who won a Nobel Prize in economics for his work in decision science) suggested
shortening Dantzig’s description ‘programming in a linear structure’ to ‘linear programming’ during a walk
on the beach with Dantzig. Also included is a note that, at the time, ‘code’ was the word used for computer
instructions and not ‘program’.
To be clear to potential and current students that this is a mathematics course requiring a background
in writing proofs and not a computer coding class, we prefer the terminology linear optimization. We do
look at computer algorithms but focus on the underlying mathematics. A small amount of computer coding
(for example, simple MAPLE) programs will be very useful, but writing code is not the central purpose of the
course. The shorthand LP has been used to refer to both the general subject of linear programming as well
as specific instances of linear programs. To distinguish, in our notation, LO (linear optimization) refers to
1 I’m not that original — there are at least a dozen books that use this terminology.
2 G. Dantzig, Linear Programming, Operations Research 50 (2002), 42–47.
,viii Preface
the general class of optimizing linear functions subject to linear constraints while LOP (linear optimization
problem) refers to specific instances of such problems. Furthermore, using the optimization term brings
the subject in line with other, closely related fields that are increasingly called Optimization (Nonlinear,
Quadratic, Convex, Integer, Combinatorial).
⋆ Of course, if you are more inclined to maintain the status quo, feel free to continue verbalizing
“ell-pee” in place of “lop”; beware, however, that the extra syllable spoken repeatedly over the
course of an entire semester can take its toll on your energy.
The Simplex Algorithm is the focus of study in this book. In particular, we do not discuss Karmarkar’s
Algorithm or Khachian’s Ellipsoid Algorithm or more general interior-point approaches to solving LOPs. The
main reason for this is that, as I hope you’ll experience, the Simplex Algorithm leads to richer connections
with linear algebra, geometry, combinatorics, game theory, probability, and graph theory. Furthermore, in
the post-optimality analysis that occurs in economic modeling and in Integer Optimization, the Simplex
Algorithm plays a central role.
⋆ For a superb and extensive treatment of interior methods, let me suggest [14]].
Why Teach This?
This is a reasonable question, and there are better answers than, “Why not?” and, “Because it’s
cool!”
One of the areas in which Mathematics departments lag behind those of, say, Physics and, most
notably these days, Biology, is in the delivery of up-to-date discoveries in the subject (galaxies, big
bang, genomics, medicine, etc.). Today’s college mathematics curriculum is virtually unchanged from
50 years ago — go into your library and look at the degree requirements from 1960, or 1940, for
that matter — and, in order to compete for majors, departments need to be perceived by students as
far more relevant to the modern world. One of the main recommendations of the CUPM Guide,3 in
fact, is awareness of connections to other subjects and introducing contemporary topics to enhance
student perceptions of the vitality and importance of mathematics in the modern world.
For example, the Simplex Algorithm is widely recognized4 as one of the top ten algorithms of the 20th
century for its widespread use, its powerful applications to industry and to mathematics, it’s elegant
simplicity, and it’s fascinating mathematical underpinnings, and yet, the percentage of departments
offering LO in 2000–01 was only 13%.5 Given the revolution that the subject has brought to the
business world alone, it is difficult to argue against having the subject available to math majors at
virtually every school in the country.
The case for LO increases when we realize that most of the students in mathematics programs do
not go on to graduate school, but instead to jobs in a wide range of industries. In fact, 92% of
students earning bachelor’s degrees in the mathematical sciences from 1994–96 went directly into the
workforce, many of whom ended up in management.6 How nice it would be for them to have such a
tool as Simplex, or at least to know of the benefits of optimization to their enterprise. In addition, a
significant portion (26% in 20007 ) of students taking upper division courses are preservice secondary
mathematics teachers. This is relevant because Discrete Mathematics is now in state curriculum
3 Undergraduate Programs and Courses in the Mathematical Sciences: CUPM Guide 2004, www.maa.org/cupm.
4 J. Dongarra and F. Sullivan, Top ten algorithms of the century, Computing Science and Engineering, January/February
2000.
5 D. J. Lutzer, J. W. Maxwell and S. R. Rodi, Statistical Abstract of Undergraduate Programs in the Mathematical Sciences
in the United States: Fall 2000 CBMS Survey, AMS, 2002.
6 National Survey of Recent College Graduates, National Science Foundation, 1997, www.nsf.gov/sbe/srs/nsf01337.
7 Statistical Abstract, op. cit.
,Preface ix
standards throughout the country, and LO is listed in that category in many states.8 How nice it
would be for our high school teachers to understand more of the applicability of the algebra they
teach.
Moreover, our undergraduate curricula compartmentalizes topics. Consequently, most math majors
graduate with a sense that many of their courses have little or nothing to do with each other. A class
in LO can do much to counter this misimpression, blending linear algebra, geometry, modeling, prob-
ability, game theory, algorithms, combinatorics, graph theory, computer programming, and theoretical
computer science into one big, tasty LOG.9
Finally, why not teach it? It’s cool!
Terminology
Besides the usage of LOP and ILOP, we introduce other quirks into the language, mostly for handiness
and consistency and occasionally for fun. For example, we discuss four kinds of linear combinations, based
on whether or not the extra affine and conic conditions hold, so it makes sense to use the similar notations
lspan, aspan, nspan, and vspan for linear, affine, conic, and convex (both affine and conic) combinations,
respectively. In particular, lspan makes more sense in this scheme than does span, the more common term
found in linear algebra texts. Geometric hulls get the same treatment, with lhull, ahull, nhull, and vhull,
respectively. For fun we use the term FLOP (Fractional LOP) when we need to distinguish a LOP from
being an ILOP. Indeed, the first step in solving an ILOP is to relax the integer constraints to allow for
rationals and find the resulting floptimal solution, which is used as a first approximation to the iloptimal
solution. The term BLOP refers to an ILOP whose variables are binary (either 0 or 1).10 Also, when we
discuss game theory, we talk about the GLOP (Game LOP) derived from a game. We don’t go too much
farther down the self-parody road — hopefully there is no SLOP in the book.
I think we’re also the first LO book to use the term parameter in place of nonbasic variable. That must
be worth some kind of award, right? Actually, I stole it from virtually every linear algebra text ever written.
Chapter Flow
Outlandish as it may seem, someone studying from this text will need to start with Chapter 1, followed
by Chapter 2. After that, there are many directions of travel.
⋆ Each chapter includes an initial commentary that elaborates further on the following — which
parts of the chapter need what prerequisites and which are prerequisites for others.
If and when you wish to study geometry, you’ll want to learn Chapter 3 before Chapter 8, but you can
pretty much learn them whenever you want. No other chapter uses Chapter 3 explicitly, although it does
offer very beneficial intuition that permeates almost every other chapter. This is why it is placed so early.
Chapter 8, however, isn’t necessary for much (unless one continues on to study graduate level optimization),
but does use material from Chapter 7 (and Section 8.4 needs Chapter 6) — and is kind of fun.
⋆ Chapter 3 can be replaced by Chapter 0 for those who like to develop students’ theorem-proving
abilities right off the bat. I sometimes enjoy using Chapter 0 as a theoretical, rather than
industrial motivation for developing the Fundamental Theorem of Linear Optimization 2.9.1.
8 In fact, this course covers 8 of the 10 NCTM standards (Algebra, Geometry, Data Analysis and Probability, Problem
Solving, Reasoning and Proof, Communication, Connections, and Representation) — one summer I taught a special section of
the course to high school teachers who benefitted greatly from such breadth.
9 Linear Optimization Goulash.
10 Thus it is quite natural for many academics to be interested in BO.
,x Preface
Chapter 4 is really the heart of the course. Everything feeds off of duality. This is why we derive the
dual immediately in Section 1.1. Spending extra time here pays dividends later, as everything thereafter
depends critically upon it.
The material of Chapter 5 is useful for learning the tip of the how-this-is-done-in-the-real-world iceberg.
The ability to state and work with everything in matrix form is a very useful skill in general, and in particular
comes in handy in Chapter 12. Thus it does not need to be studied before any other chapter (if at all, as it
is not essential material otherwise — in fact, Chapter 5 is only crucial to proving Theorem 12.1.4).
Chapter 6 puts Chapter 4 in general context, and is required for all subsequent chapters.
⋆ It is possible, however, to cover the material of Chapter 6 more informally, as needed. In fact, as
with most chapters, one can decide to present only its first two sections (maybe plus its Section
3 Practice) in an effort to cover a broader spectrum of material. This text is designed for such
a degree of flexibility.
Chapter 7 contains material that is necessary for Chapter 8. Chapter 9 is not needed by anyone who
doesn’t want to have a good time. Chapter 10 is required by Chapter 11, and Section 12.4 is key for Chapter
13. Chapters 7–13 offer the greatest flexibility for studying your favorite topics within a semester’s time.
Of course, you could slow down, spend extra time on the exercises, and complete the whole book in two
semesters. Have at it!
A visual description of the above dependencies is given below.
Book Format and Usage
It is not difficult to notice that this text is different from most, and not just because I can’t resist even
the lamest of jokes,11 so it may be worth some discussion on why this is so, what benefits this may have for
you, and how best to take advantage of the new format.
First and foremost, a great deal of information is missing, information that typically is included in
mathematics texts.
⋆ Most texts prohibit discovery style learning by explaining everything in sight on the page, leaving
little room for instructor influence, whereas the premise of the discovery method is to withhold
information! The commonly reported benefits of the approach (increased understanding, reten-
tion, enjoyment, motivation, confidence, etc.) motivate this format, from which you can decide
how much more you wish to share with your students.
Having spent most of your life reading from such texts, you may be used to being fed facts and algorithms,
and well used to memorizing them in order to reproduce them on exams. But I believe that you are capable
of much more: of deriving results, in fact, discovering them through experimentation, of making conjectures,
of proving theorems, of solving problems and checking them yourself, and of asking creative questions.
11 Most of these require my age to understand anyway.
,Preface xi
That’s what this format is all about, giving your professor the opportunity to lead you through the kinds of
experiences that will develop your skills in each of these areas, helping you become a highly critical thinking
machine,12 able to wrestle with complex problems in all areas of society, rather than just someone who went
to college and remembers a few math facts.
⋆ There is often a big gap between the typical 2–3 line proofs that students are asked to master
in the usual Introduction to Proofs course that math majors take as Sophomores or Juniors, and
the 3–4 paragraph proofs that they are asked to understand in most Senior level courses. The
intention of some of the workouts is to bridge this gap. You’ll notice that most of the main
theorems are followed by a sequence of workouts that form the outline of proof. Students can
be expected both to understand that such an outline will prove the theorem, and to prove the
individual parts. By interacting with the proof in this way they may come to understand the
proof at hand better and be more able to construct their own proofs of other theorems. It could
be said that our approach to discovery learning is halfway to the Moore Method. While we
typically will not divulge the full proof, students are not left on their own either. It’s as if we
give them the road map but they still have to drive the car.
You may find that your classroom environment may also differ from the norm. Many professors who use
this will ask their students to participate more in discussion, rather than simply listen to lectures. Some
may even ask their students to make daily presentations of the theorems they’ve proven, the exercises and
workouts they’ve solved, and the algorithms they’ve written, in order to create an environment in which
the students become responsible for their own learning, questioning each other for understanding, while the
professor acts as a facilitator. Such an environment may be upsettingly abnormal to you initially, but I
promise you will warm to it (indeed, embrace it) in time.
⋆ Not that you have to teach like this, but many who do know that you usually have to sell the
students a little on using methods so contrary to their 12–15 years of experience with being
lectured to. Natural resistence to change, coupled with difficulty adjusting to new expectations,
can turn into revolt and blame if not handled carefully in advance. When things go well for a
student, they will have every right to take all the credit, but when things don’t they will most
certainly look at you as their scapegoat, so this kind of preparation and a great amount of
conviction can be critical.
This form of discourse centers more on the learning than the teaching, and those who engage in it deeply
are affected (infected?) for life. My hope is that you are enticed enough, not only by the material, but
by the interesting problems, challenging questions, and your professor’s invitation to question, challenge,
wonder, experiment, guess, and argue, to throw your energies in this new direction so as to be stirred to the
point that it transforms the way you think about everything, from mathematics and science, to politics and
religion, to sports and fine arts. Be inquisitive, be skeptical, be critical, be creative, and keep thinking.
⋆ Make note of the many exercises such as 1.5.6 in the book that are meant to develop students’
habits, abilities, and confidence to investigate their own questions, find their own patterns,
and check their own work. LO is unique in this latter respect — duality and other forms of
certification give students the power to know when they are right or wrong.
Keep in mind, this isn’t some crazy, new, experimental pedagogy. This approach is as old as it gets,
predating all forms of formal classroom teaching. It has come to be known by many names through the
years: the Socratic Method, Discovery-Based Teaching, the Moore Method, and Inquiry-Based Learning,
among others. There are maybe two central tenets that identify the philosophy.
• A thing isn’t true because someone says so or because it’s written in a book, but because it is reasoned
to be true.
12 You can even wear a cape: leap tall buildings, etc.
,xii Preface
• One doesn’t master something by hearing or seeing it, but by doing it.
⋆ Parker says that13 it is less a method than “a commitment to teaching by letting students
discover the power their own minds have.” With that in mind, what I’m trying to provide here
are materials to help you teach your students that they don’t need you! When I hand out a
syllabus at the beginning of the semester I include in it a few sales pitches for what they are
about to encounter. Quotes such as the following have proven useful.
– That student learns the most who is told the least. — R. L. Moore
– I hear, I forget; I see, I remember; I do, I understand. — Chinese proverb
– Problems worthy of attack prove their worth by fighting back. — Piet Hein
– Mathematics is not a careful march down a well-cleared highway, but a journey into a strange
wilderness, where the explorers often get lost. — W. S. Anglin
– To imagine is everything; to know is nothing at all. — Anatole France
Feel free to steal these or find others that work best for you. An excellent resource for all things
Moore-ish is the recent book by Coppin et al.14
So what else can you do outside of the classroom in order to master this material? Some students find
that keeping a journal, separate from their class notes, that holds all their proofs and solutions, can be quite
useful. This is especially true if one uses a word processor (LATEX is certainly best, whether using AMSTeX
on Linux, MiKTeX through WinEdt or Scientific Word on Windows, or even with TeXShop on MacOS,
although Microsoft Word, with its Equation Editor should suffice), since the work can continue to be edited
and organized to follow the text. Also, do the workouts as you read along, such as the very first one:
Workout 0 What pattern is there regarding Section 3 of each chapter?
The headings of such sections use Latin-based alphabets precisely in composite-numbered chapters.
⋆ You see now how material for teachers’ eyes only is indented in sans serif font, with solutions
to problems unstarred and comments like this distinguished by a star and further indented. The
comments will sometimes point to further ideas, references, activities, or connections with prior
and subsequent material, workouts, theorems, or exercises.
The point of doing them as you go is partly to help you learn the material by making sure you read the
stuff (I can remember undergraduate books that I wouldn’t read at all, instead just solving the exercises
required for homework by mimicking the examples — what kind of comprehension does that foster?), and
partly to help you learn the process of experimenting, conjecturing, clarifying, strategizing, proof writing,
and generalizing. That will serve you long after you forget the Complementary Slackness Theorem.
⋆ Regarding end of chapter Exercises, they are split into three levels. Practices are meant to
directly apply the lessons of the chapter, mostly in the form of calculating answers and proving
simple statements. Challenges offer interesting questions and problems that require deeper
thought and more demanding proof. Projects are longer term suggestions for term papers,
group presentations, senior theses, capstone experiences, research, and so on. Maybe some
exercises are miscategorized here and there — just let me know.
On the other hand, you can simply distract yourself with the trivia contest that floats throughout the
book, signified by the ◦ in the margins. Of course, you have to swear not to Google anything if you want to
win.
13 G.E. Parker, Getting more From Moore, Primus 2 (1992), 235–246.
14 C.A. Coppin, E. L. May, W. T. Mahavier, and G. E. Parker, The Moore Method: A Pathway to Student-Centered
Instruction, in press, MAA, Notes Series.
,Preface xiii
Why Teach Like This?
Well, of course, you don’t have to. I intended to write something flexible enough to be used by
practitioners of all methods. You be the judge of the extent to which I have succeeded. In particular,
during the several years of development, I have used a variety of approaches, including
• lecturing to a large class (in which students took good notes to fill in the solutions to workouts),
• going Full Moore15 with a small class (in which students presented their solutions to workouts
all day, every day),
• using various combinations of these two extremes, as well as in-class group work and other
interactive activities.
Sometimes, if the proof of a theorem has, say, three steps set up as workouts, I might do somthing
like lecture through the first workout, have students work in pairs to figure out the second in class,
and assign the third as individual homework to be presented the following day. It may be that a
student began the class by presenting MAPLE results from a workout I assigned for homework that
facilitated discovery of the theorem. The point is, do what you feel comfortable doing, and try new
ideas if you like. Hopefully this format will help you be successful whichever way you choose. Maybe,
like me, you’ll want to use it differently each time you teach from it (which in and of itself can keep
your teaching fresh).
That being said, there are reasonable apologies for more Socratic approaches. I find it difficult not
to be influenced by the writings of Schoenfeld16 and Smith,17 for example. And as suggested above,
there are few references better than Coppin et al.18 for suggestions on fostering a productive classroom
environment, handling the different rates at which students absorb material, grading, and so on.
References
Many practitioners of discovery-based methods make informal agreements with their students not to
refer to any outside sources. Surprisingly, especially how trivial it is these days to locate and access
such materials, students tend to respect such agreements very well. That being said, not every book
has the same target audience, so it may be useful for me to attempt a rough characterization of a
small sampling of excellent references, revealed, as usual, only to you.19 This should also help to
point out the niche that the present treatise is trying to serve. Texts covering LO (and in particular
the Simplex Algorithm) can be placed into the following six groups.
1 Finite mathematics texts. These have elementary treatment of the Simplex Algorithm, duality
and modeling with no mathematical proofs. Such texts assume little or no mathematical so-
phistication and in particular students need not have had calculus. There are very many such
standard finite mathematics texts, for example [10]].
2 Linear algebra texts that include a very brief treatment of linear optimization as a topics chapter
at the end. These are numerous.
3 Texts aimed at engineering or business users of linear optimization, with more sophisticated
mathematics than those in group 1 but with the goal of being able to model and solve linear
optimization problems as a tool in engineering or business applications. These typically assume
15 Really only Near Moore — Full Moore doesn’t allow texts of any kind.
16 A. H. Schoenfeld, When good teaching leads to bad results: The disasters of “well taught” mathematics courses, Educational
Psychologist 23 (2), Spring 1988.
17 J. C. Smith, A sense-making approach to proof: Strategies of students in traditional and problem-based number theory
courses, Journal of Mathematical Behavior 25 (2006), 73–90.
18 C. A. Coppin, op. cit.
19 Because I like you, I give you such a deal.
,xiv Preface
the mathematical sophistication of sophomore/junior engineering or senior/graduate business
student and do not include many proofs. Classic texts of this type are [8, 19]], two of the market
leaders.
4 More mathematically sophisticated versions of those in group 3. See [6, 12, 17]].
5 Books appropriate for graduate level study either in mathematics or industrial engineering/oper-
ations research/computer science ( [2, 5, 9, 11, 13–15]]).
6 Texts such as the famous classic20 aimed primarily at upper level mathematics majors, with
varying degrees of focus on proofs and mathematical development (see [16, 18]]).
Technology
Another of the recommendations of the CUPM Guide21 is to incorporate technology as a tool for
solving problems and as an aid to understanding mathematical ideas. Most texts aim for software
that solves moderately large LOPs (such as CPLEX, LINDO, etc.). Instead, I developed a web
browser application (WebSim) for pedagogical use in order to facilitate conceptual understanding of
the subject. Students can use it to explore and discover, as well as solve small problems.
One of the things that distinguishes this text from all others is that it uses integer arithmetic always.
This greatly simplifies exposition and calculation, and highlights the role of basic determinants, espe-
cially in relation to combinatorial applications that rely on total unimodularity. WebSim follows suit
by using integer arithmetic as well.
I also encourage use of MAPLE software for three purposes. First, its geometric visualization tools,
both static and dynamic, are very useful in bridging between geometry and linear algebra, as well as
in motivating algorithms and problem solutions. I provide many instances of code for illustrative use
in class. Second, its programming environment is very flexible and simple to learn, with excellent
help menus, and one can build up programs from individual executable lines quite easily. I find that
most students can write their own Simplex code over the course of a semester, building upon a pivot
procedure within the first few weeks. Third, it contains an LO solver that can be used when you need
it.
I include descriptions of how to use each of these in Appendix D. Of course it isn’t necessary to use
MAPLE, although I believe typical mathematics and math education majors could use a whole lot
more programming experience than they are required to have, in order to be more successful in their
chosen careers. Most of my students end up buying the student version of it at a reasonable price,
discounted more than normal by the program MAPLE has for students whose course requires it.
Index
Just a small note about the Index. I believe that index entries should signify what’s memorable, not
important — importance should be indicated by the page references instead. So in this era of inclusivity,
I’ve thrown in the kitchen sink. The main reason for this is that I don’t know how your memory works.
It doesn’t help you if you can’t find tractor pull because it’s only listed under theological tractor pull and
you couldn’t remember the obvious connection to theology. So the index is fattened by including various
permutations of words. Also, even though tractor pull is not central to the theory of linear optimization,
in 25 years when you’re trying to show your kids a nice example of how the theory works and all you can
remember is that awesome example with the tractor pull, you’ll thank me. Plus, this adds an extra page
to the book, which increases its cost by .037c/. With about 2.7 million readers annually, my 1% commission
generates an extra deluxe cheeseburger per year, which in turn helps me satisfy the requirements of Problem
20 Um, you’re reading it.
21 CUPM Guide, op. cit.
, Preface xv
1.1.1 for that day. While the entries are many, I did make an effort to restrict the page references of the
most common terms to their most important instances.
With regard to the fonts you’ll encounter, theorems (in their full names) are in italics, and page numbers
that refer to definitions are in bold. (You’ll notice that theorems and definitions find their way into the
margins for easy location.) Italicized page numbers denote appearances in theorems, while sans serif numbers
signal inclusion in workouts and exercises, and roman fonts cite regular occurrences of the term. With regard
to the order of terms, mathematical symbols come first (numbers, then capital letters, then lower case letters),
followed by As,22 and then standard words.
Thanks
I wish to express my gratitude to many people who have helped bring this project to fruition. First
and foremost is Garth Isaak, who really helped me get the ball rolling in many ways and contributed a
number of great ideas at the start. Rob Hochberg and Nate Dean were excellent sounding boards for crazy
ideas, some of which found their way onto these pages and some of which didn’t. The National Science
Foundation was instrumental for funding the time for me to get the bulk of it up and going. Several
semesters worth of students tested early versions of the material, and Josh Maximoff and Ben Hester in
particular combed through many exercises carefully. Other students, Sriram Penumatcha, Jake Hawkes,
and Josh Wolfe, developed WebSim with me, and Jennifer Broatch organized the assessment of the book’s
methods for the NSF. Much appreciation goes to Harry Lucas and the Educational Advancement Foundation
for supporting conferences and workshops dedicated to the pedagogical approach of R.L. Moore, in particular,
the Legacy of Moore Conferences at the University of Texas, and the Inquiry-Based Learning Workshops
run by Stan Yoshinobu, Ed Parker, Carl Leinart, and Jenny Smith. I will even thank Mike Starbird for
many a conversation more fruitful to me than he might imagine. Francis Su’s MAA PREP Workshop
on Combinatorial Geometry and Mike Jones’s MAA Short Course on Game Theory were quite beneficial
as well. Several colleagues piloted versions of the course at various stages of development and offered
significant feedback, including Dan Biebighauser, Nancy Childress, Steven Dunbar, Mark Ellingham, Gary
Gordon, Donovan Hare, and Attila Sali. Many thanks are due to those who helped me with foreign language
translations: Hélène Barcelo, Airat Bekmetjev, Anthony Chambers, Gil Kalai, Vikram Kamat, Irina Long,
Rose Sau Lugano, Mkamburi Lyabaya, Faris Odish, Andrea Richa, Derar Serhan, Nandor Sieben, and
Jennifer Tom, and especially to Klaus Lagally, Dominik Wujastyk, and Rajiv Monsurate for their assistance
with LATEX language packages (and to Renate Mittelmann for loading things for me). Of course, I really
also need to thank Don, not only for creating TEX in the first place, but also for the excellent sense of taste ◦
and humor displayed in his own texts, not that I stole any ideas or anything. The Coffee Buzz, Lilo’s Coffee
Haus, The Harem, Bunna Coffee & Tea Market, Steve’s Espresso, Extreme Bean Coffee Co., and Gold Bar
Espresso deserve much credit for comfortable and creative writing environments (sorry if your copy has any
coffee stains on it). Finally, the tremendous group at Springer deserves a raise for putting up with me:
Vaishali Damle, Frank Ganz, Marcia Bunda, Frank McGuckin, and players to be named later.23
Feedback
Thanks to the many students and professors and editors (in particular, Christopher Curioli) who combed
through this book before its printing, the text would have been perfect if not for me. Any errors in typography
or content that remain are clearly the fault of some guy I met on the bus one day who distracted me, scattering
errors of varying types throughout the book. If you tell me about them I’ll be sure to let him know if I ever
happen to see him again. I will also try to correct them before the 7th edition. From my web site (search
for Hurlbert math homepage), click on the LinOpt logo and scroll down to the Submit Feedback link. You
can search to see if your idea has already been posted, and otherwise post it by Chapter, Section, and Type
of Error for others to see, and it will be on queue for the next revision.
22 Short for Acronyms.
23 I might trade for some draft picks.
