This is an introductory book for students to learn optimization theory, tools, and applications. The two main goals are (1) students are able to apply the tools of optimization in their future work or research, and (2) students understand the concepts underlying optimization solvers and use this knowledge to use solvers effectively.
This book was based on a sequence of courses at Virginia Tech in the Industrial and Systems Engineering Department. The courses are Deterministic Operations Research I and Deterministic Operations Research II. The first course focuses on linear programming, while the second course covers integer programming and nonlinear programming. As such, the content in this book is meant to cover 2 or more full courses in optimization.
The book is designed to be read in a linear fashion. That said, many of the chapters are mostly independent and could be rearranged, removed, or shortened as desired. This is an open source textbook, so use it as you like. You are encouraged to share adaptations and improvements so that this work can evolve over time.
On the simplex method. This book presents the simplex method three ways, in three chapters: the dictionary version, the algebraic (matrix) version, and the tableau version. As a teacher, you may choose to teach all of these, some of them, or even just one. I have always felt that the dictionary version is the clearest picture of what is actually happening; some of that understanding just doesn’t seem to translate to students when working through tableaus. On the other hand, students tend to like the simpler row operations of the tableau. The matrix version supplies the linear algebra underneath both and connects most directly to how solvers are implemented. Any one of the three is enough to continue through the rest of the book.
On software. Excel is a nice tool for solving simple linear programs, and it can be a comfortable place for students to set up and solve their first few models. But since the arrival of AI assistants, modeling and coding in Python has become so much easier, and AI is transforming modeling itself, toward communicating constraints in plain text. Unfortunately, it is difficult to use AI to build these models in Excel. So, candidly, it is unclear to me at this time what the most useful tool to teach is. The book provides examples in both, so you can weight them however suits your course.
This book is designed to be a resource for students interested in learning what optimization is, how it works, and how you can apply it in your future career. The main focus is being able to apply the techniques of optimization to problems using computer technology while understanding (at least at a high level) what the computer is doing and what you can claim about the output from the computer.
Quite importantly, keep in mind that when someone claims to have optimized a problem, we want to know what kind of guarantees they have about how good their solution is. Far too often, the solution that is provided is suboptimal by 10%, 20%, or even more. This can mean spending excess amounts of money, time, or energy that could have been saved. And when problems are at a large scale, this can easily result in millions of dollars in savings.
For this reason, we will learn the perspective of mathematical programming (a.k.a. mathematical optimization). The key to this study is that we provide guarantees on how good a solution is to a given problem. We will also study how difficult a problem is to solve. This will help us know (a) how long it might take to solve it and (b) how good of a solution we might expect to be able to find in a reasonable amount of time. We will later study heuristic methods - these methods typically do not come with guarantees, but tend to help find quality solutions.
Note: Although there is some computer programming required in this work, this is not a book on programming. Thanks to the fantastic modeling packages available these days, we are able to solve complicated problems with little programming effort. The key skill we will need to learn is mathematical modeling: converting words and ideas into numbers and variables in order to communicate problems to a computer so that it can solve a problem for you.
As a main element of this book, we would like to make the process of using code and software as easy as possible. Attached to most examples in the book, there will be links to code that implements and solves the problem using several different tools from Excel and Python. These examples should make it easy to solve a similar problem with different data, or more generally, can serve as a basis for solving related problems with similar structure.
Skim ahead. We recommend that before you come across a topic in lecture, you skim the relevant sections ahead of time to get a broad overview of what is to come. This may take only a fraction of the time that it may take for you to read it.
Read the expected outcomes. At the beginning of each section, there will be a list of expected outcomes from that section. Review these outcomes before reading the section to help guide you through what is most relevant for you to take away from the material. This will also provide a brief look into what is to follow in that section.
Read the text. Read carefully the text to understand the problems and techniques. We will try to provide many examples; depending on your understanding of a topic, you may need to go carefully over all of the examples.
Do the exercises. Each chapter ends with a graded exercise section: Warm-ups drill one skill and name the worked example they mirror, Core problems are full modeling and computation problems, Concepts and connections ask you to explain why things work, and Challenge problems stretch beyond the chapter. Difficulty is marked with stars ( to ), and each exercise ends with a small gray tag pointing to the section or example to review if you get stuck. Selected solutions appear at the end of each exercise section; try the problem before reading them.
Explore the resources. Lastly, we recognize that there are many alternative methods of learning given the massive amounts of information and resources online. Thus, at the end of each section, there will be a number of superb resources that are available on the internet in different formats. There are other free textbooks, informational websites, and also a number of fantastic videos posted to YouTube. We encourage you to explore the resources to get another perspective on the material or to hear/read it taught from a different point of view or in presentation style.
This book is divided into 3 Parts:
There are also a number of chapters of background material in the Appendix. Additional topics, including advanced integer programming and nonlinear programming, are covered in Book 2.