There is much good in that traditional development, but I undertook this new text on the deterministic (mathematical programming) half of OR because I believe students need something more. Emphasis should be on skills and intuitions they can carry away and apply in real settings or later courses. Modeling (or at least formulation) should be central. Students should be excited about the versatility and applicability of OR tools.
Most of the innovations of this book try to deliver on that vision. Numerous algorithms (including simplex) are developed in the context of a common improving search paradigm designed to prepare students for absorbing new material as they encounter it within the course and later. The full breadth of mathematical programming (including linear, integer, nonlinear, and multiobjective programming) is treated from the beginning to highlight the rich diversity of potential applications. Three entire chapters, and large portions of others, are devoted to describing and formulating examples, most of which are based on reports of real applications. The entire development is structured to facilitate its use in a variety of settings by making it as easy as possible to locate material and move around.
The book is intended for first undergraduate and graduate OR courses in engineering and mathematics, and undergraduate/graduate electives in management, as well as introductory courses in subtopics such as linear programming, integer and combinatorial optimization, network flows, and nonlinear programming. Its comprehensive and reentrant coverage should also make it a valuable reference for practitioners and researchers.
My rethinking of how to present mathematical programming begins with the conviction that you cannot do justice to the topic by teaching only linear programming and the simplex method. First of all, the overwhelming majority of optimization problems actually encountered in engineering and management practice cannot be modeled straightforwardly as linear programs. They involve discrete, nonlinear, and multiobjective elements that have to be confronted. Perhaps more importantly, OR practice has evolved to the point where integer, nonlinear, and multiobjective optimization models are dealt with every day. I was surprised myself, in researching the OR applications literature for this book, that accounts of discrete optimization significantly outnumber those using linear programming alone. Goal programs are everywhere. If students have never seen anything but classic LP, they will inevitably conclude OR is too narrow to deal with the complexities of real planning and design tasks.
Focusing heavily on the simplex algorithm also introduces a more subtle roadblock to learning. Regardless of whether simplex is taught as a combinatorial search for the right basic set or as a sequence of linear equation manipulations, decades of refinement on simplex development have almost totally obscured its relation to all the other tools of mathematical programming. A student who has learned only the simplex now carries away little insight around which to build any understanding of the wider field. Even the newer interior point algorithms for linear programming seem completely foreign.
I am not sugggesting that every introductory course must delve deeply into integer and nonlinear programming techniques, or that LP and the simplex should be discarded. What I believe we need is a development that treats LP as the best solved but far from the only form of mathematical program, and that equips students with the intuitions and paradigms to understand more advanced topics when they encounter them in later courses or practice. Where there is the time or the prerequisites to go more deeply into wider topics, that material should be there, developed as much as possible around the same concepts as those of basic LP.
This book tries to avoid equating linear programming with optimization by treating other cases from the very beginning. As in any introduction, the early priority is on formulating optimization problems in standard mathematical programming format. But by including integer, nonlinear, and multiobjective cases along with LPs, students are encouraged to get excited about how vast a range of applications can at least be modeled in this standard way. They can also begin early to recognize different model classes and to be alert to their relative tractability. My experience is that beginners will struggle with intracacies of subscripts, decision variables, constraints, and objectives --- just as they do if we treat only LPs --- but that the broader range of mathematical forms is well within their prior training. Binary variables are often the only new mathematical concept, and students find them quite intuitive.
Treatment of the improving search (hillclimbing) paradigm begins in Chapter 3 with basic notions of improving and feasible directions, step sizes, local and global solutions, and artificial starts. With the freedom to use nonlinear examples, this can be done in an intuitive and geometic way. Then the simplex algorithm is presented in Chapter 5 as an elegant specialization to linear programming. That improving search treatment of the simplex will seem unfamiliar even to many instructors, but very little is actually changed. Still, with the hillclimbing paradigm firmly established, it becomes much easier to develop interior point methods in Chapter 6, network algorithms in Chapter 10, nonlinear programming methods in Chapters 13-14, and even integer programming procedures in Chapter 12. Time probably will not permit covering all those topics in any single course, but my hope is that the paradigm prepares students for future learning, whether it comes in the current course, in later ones, or in professional practice.
Students can hardly be expected to get excited about using optimization methods if they have never seen them applied except on contrived examples small enough for hand computation. Also formulation skills, which I always find take the longest to develop, demand constant practice. These are why I have tried to make the book both an exposition of the rich diversity of OR applications and a continuing discourse on optimization modeling. Every algorithm and analytic principle is developed in the context of a brief story, and many computational exercises begin with a formulation step. The several whole or partial chapters devoted to formulation are full of realistic examples drawn from operations reseach practice, and exercises add many others. Time-short instructors will find both long enough to preserve a sense of the real application, yet sufficiently self-contained to be presented in 15 to 30 minutes of class time.
All serious mathematical programming computation requires computers, and I have tried to reflect that as well in my updated conceptualization of introductory OR. One way for students to judge whether their formulations are correct is to input them to optimization software and examine the results. That is why every formulation exercise with numerical constants also includes a computer solution step. Hand computation is still employed in numerous small exercises to develop student understanding of principles and algorithms, but here too the computer is exploited when possible. A few purely hand topics of traditional introductory courses have been dropped altogether because they provide neither tools for solving problems of practical size nor insights into the working of effective computer algorithms.
Realizing that few instructors will cover every topic in the book, and that even fewer students will read every page, I have tried the make the book as easy to move around in as possible. Dependencies between sections are minimized and clearly identified with explicit references. The entire development is broken into short and carefully labeled subsections addressing one topic each. Every major definition, principle and algorithm is set out for quick reference in an easy-to-spot box. One- or two-page ``Primers'' concisely review prerequisite material as it arises in the development. Computations and theoretical principles, which may be derived over several pages, are recapped in brief ``Sample Exercises'' also marked for easy identification. Icons in the exercises indicate which require computers or graphic calculators, and which have answers provided at the back of the book.
Instructors who consider adopting the book may have to spend some time aligning their lectures and other materials with my innovations. Still, the cost is much less than it might seem at first glance because the changes have less to do with what is taught than the sequence and conceptual framework within which it is developed. I have tried to help with sample syllabi, notes, software and other aids posted through Internet site http://comp.uark.edu/~rrardin/oorbook/.
I hope the effort to convert will prove justified for others. It has certainly been rewarded with improved learning and greater student motivation in my own classes at Purdue. I owe a great deal of thanks to the hundreds who have aided in its development as they studied from emerging drafts.
I also want to thank my wife Blanca and son Rob for their encouragement and patience through the long years this book has been underway, my two supportive department heads Ferd Leimkuhler and Marlin Thomas, and a sequence of helpful editors with Macmillan and Prentice-Hall. Special recognition is due editor David Johnstone, who launched me on this quest, and was senselessly murdered just as it began to take shape.
Ronald L. Rardin
John and Mary Lib White Distinguished Professor
Department of Industrial Engineering
University of Arkansas
Fayetteville, AR 72701
rrardin@uark.edu
http://comp.uark.edu/~rrardin/