Practical Python AI Projects Mathematical Models of Optimization Problems with Google OR-Tools Serge Kruk Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools Serge Kruk Rochester, Michigan, USA ISBN-13 (pbk): 978-1-4842-3422-8 ISBN-13 (electronic): 978-1-4842-3423-5 https://doi.org/10.1007/978-1-4842-3423-5 Library of Congress Control Number: 2018934677 Copyright © 2018 by Serge Kruk Any source code or other supplementary material referenced by the author in this book is available to readers on GitHub via the book's product page, located at www.apress.com/9781484234228. For more detailed information, please visit www.apress.com/source-code. Contents Chapter 1: Introduction�������������������������������������������������������������������������1 1.1 What Is This Book About? ................................................................................1 1.2 Features of the Text ........................................................................................3 1.2.1 Running the Models ................................................................................5 1.2.2 A Note on Notation ..................................................................................6 1.3 Getting Our Feet Wet: Amphibian Coexistence ................................................6 Chapter 2: Linear Continuous Models �������������������������������������������������19 2.1 Mixing ...........................................................................................................20 2.1.1 Constructing a Model ...........................................................................22 2.1.2 Variations ..............................................................................................26 2.1.3 Structure of the Problems Under Consideration ...................................28 2.2 Blending ........................................................................................................30 2.2.1 Constructing a Model ...........................................................................32 2.2.2 Variations ..............................................................................................36 2.3 Project Management .....................................................................................38 2.3.1 Constructing a Model ...........................................................................40 2.3.2 Variations ..............................................................................................43 2.4 Multi-Stage Models .......................................................................................45 2.4.1 Problem Instance ..................................................................................46 2.4.2 Constructing a Model ...........................................................................48 2.4.3 Variations ..............................................................................................54 2.5 Pattern Classification ....................................................................................57 2.5.1 Constructing a Model ...........................................................................58 2.5.2 Executable Model .................................................................................60 Chapter 3: Hidden Linear Continuous Models �������������������������������������63 3.1 Piecewise Linear ...........................................................................................65 3.1.1 Constructing a Model ...........................................................................66 3.1.2 Variations ..............................................................................................70 3.2 Curve Fitting ..................................................................................................76 3.2.1 Constructing a Model ...........................................................................78 3.2.2 Variations ..............................................................................................84 3.3 Pattern Classification Revisited ....................................................................85 3.3.1 Executable Model .................................................................................87 Chapter 4: Linear Network Models �����������������������������������������������������89 4.1 Maximum Flow..............................................................................................90 4.1.1 Constructing a Model ...........................................................................91 4.1.2 Decision Variables ................................................................................92 4.1.3 Variations ..............................................................................................98 4.2 Minimum Cost Flow ......................................................................................99 4.2.1 Constructing a Model .........................................................................100 4.2.2 Variations ............................................................................................105 4.3 Transshipment .............................................................................................106 4.3.1 Constructing a Model .........................................................................107 4.3.2 Variations ............................................................................................112 4.4 Shortest Paths .............................................................................................113 4.4.1 Constructing a Model .........................................................................114 4.4.2 Alternate Algorithms ...........................................................................118 4.4.3 Variations ............................................................................................118 Chapter 5: Classic Discrete Models ��������������������������������������������������125 5.1 Minimum Set Cover .....................................................................................126 5.1.1 Constructing a Model .........................................................................128 5.1.2 Variations ............................................................................................133 5.2 Set Packing .................................................................................................134 5.2.1 Constructing a Model .........................................................................135 5.2.2 Variations ............................................................................................137 5.3 Bin Packing .................................................................................................137 5.3.1 Constructing a Model .........................................................................139 5.4 TSP ..............................................................................................................150 5.4.1 Constructing a Model .........................................................................151 5.4.2 Variations ............................................................................................157 Chapter 6: Classic Mixed Models �����������������������������������������������������161 6.1 Facility Location ..........................................................................................161 6.1.1 Constructing a Model .........................................................................163 6.1.2 Variations ............................................................................................167 6.2 Multi-Commodity Flow ................................................................................168 6.2.1 Constructing a Model .........................................................................169 6.2.2 Variations ............................................................................................173 6.2.3 Instances ............................................................................................176 6.3 Staffing Level ..............................................................................................176 6.3.1 Constructing a Model .........................................................................179 6.3.2 Variations ............................................................................................184 6.4 Job Shop Scheduling ..................................................................................184 6.4.1 Constructing a Model .........................................................................185 Chapter 7: Advanced Techniques ������������������������������������������������������191 7.1 Cutting Stock...............................................................................................191 7.1.1 Constructing a Model .........................................................................193 7.1.2 Pre-Allocate Cutting Patterns .............................................................200 7.2 Non-Convex Trickery ...................................................................................205 7.2.1 Selecting k Variables Out of n to Be Non-Zero ....................................208 7.2.2 Selecting k Adjacent Variables Out of n to Be Non-Zero .....................210 7.2.3 Selecting k Constraints Out of n .........................................................215 7.2.4 Maximax and Minimin ........................................................................221 7.3 Staff Scheduling ..........................................................................................224 7.3.1 Constructing a Model .........................................................................227 7.3.2 Variations ............................................................................................233 7.4 Sports Timetabling ......................................................................................234 7.4.1 Constructing a Model .........................................................................234 7.4.2 Variations ............................................................................................245 7.5 Puzzles ........................................................................................................245 7.5.1 Pseudo-Chess Problems .....................................................................246 7.5.2 Sudoku ...............................................................................................251 7.5.3 Send More Money! .............................................................................254 7.5.4 Ladies and Tigers ...............................................................................257 7.6 Quick Reference for OR-Tools MPSolver in Python .....................................263 Index �������������������������������������������������������������������������������������������������271 Introduction 1.1 What Is This Book About? Artificial intelligence is a wide field covering diverse techniques, objectives, and measures of success. One branch is concerned with finding provably optimal solutions to some well-defined problems. This book is an introduction to the art and science of implementing mathematical models of optimization problems. An optimization problem is almost any problem that is, or can be, formulated as a question starting with “What is the best … ?” For instance, • What is the best route to get from home to work? • What is the best way to produce cars to maximize profit? • What is the best way to carry groceries home: paper or plastic? • Which is the best school for my kid? • Which is the best fuel to use in rocket boosters? • What is the best placement of transistors on a chip? • What is the best NBA schedule? Chapter 1 IntroduCtIon These questions are rather vague and can be interpreted in a multitude of ways. Consider the first: by “best” do we mean fastest, shortest, most pleasant to ride, least bumpy, or least fuel-guzzling? Besides, the question is incomplete. Are we walking, riding, driving, or snowboarding? Are we alone or accompanied by a screaming toddler? To help us formulate solutions to optimization problems, optimizers1 have established a frame into which we mould the questions; it’s called a model. The most crucial aspect of a model is that it has an objective and it has constraints. Roughly, the objective is what we want and the constraints are the obstacles in our way. If we can reformulate the question to clearly identify both the objective and the constraints, we are closer to a model. Let’s consider in more detail the “best route” problem but with an eye to clarify objective and constraints. We could formulate it as Given a map of the city, my home address, and the address of the daycare of my two-year-old son, what is the best route to take on my bike to bring him to daycare as fast as possible? The goal is to find among all the solutions that satisfy the requirements (that is, paths following either streets or bike lanes, also known as the constraints) one path that minimizes the time it takes to get there (the objective). Objectives are always quantities we want to maximize or minimize (time, distance, money, surface area, etc.), although you will see examples where we want to maximize something and minimize something else; this is easily accommodated. Sometimes there are no objectives. We say 1 I use the term “optimizers” to name the mathematicians, theoreticians, and practitioners, who, since the nineteen-fifties, have worked in the fields of linear programming (LP) and integer programming (IP). There are others who could make valid claims to the moniker, chiefly among them researchers in constraint programming, but my focus will be mostly in LP and IP models, hence my restricted definition. 2 Chapter 1 IntroduCtIon that the problem is one of feasibility (i.e. we are looking for any solution satisfying the requirements). From the point of view of the modeler, the difference is minimal. Especially since, in most practical cases, a feasibility model is usually a first step. After noticing a solution, one usually wants to optimize something and the model is modified to include an objective function. 1.2 Features of the Text As this text is an introduction, I do not expect the reader to be already well versed in the art of modeling. I will start at the beginning, assuming only that the reader understands the definition of a variable (both in the mathematical sense and in the programming sense), an equation, an inequality, and a function. I will also assume that the reader knows some programming language, preferably Python, although knowing any other imperative language is enough to be able to read the Python code displayed in the text. Note that the code in this book is an essential component. To get the full value, the reader must, slowly and attentively, read the code. This book is not a text of recipes described from a birds-eye view, using mathematical notation, with all the nitty-gritty details “left as an exercise for the reader.” This is implemented, functional, tested, optimization code that the reader can use and moreover is encouraged to modify to fully understand. The mathematics in the book has been reviewed by mathematicians, like any mathematical paper. But the code has been subjected to a much more stringent set of reviewers with names Intel, AMD, Motorola, and IBM.2 2 My doctoral advisor used to say “There are error-free mathematical papers.” But we only have found an existence proof of that theorem. I will not claim that the code is error-free, but I am certain that it has fewer errors than any mathematical paper I ever wrote. 3 Chapter 1 IntroduCtIon The book is the fruit of decades of consulting and of years teaching both an introductory modeling class (MOR242 Intro to Operation Research Models) and a graduate class (APM568 Mathematical Modeling in Industry) at Oakland University. I start at the undergraduate level and proceed up to the graduate level in terms of modeling itself, without delving much into the attendant theory. • Every model is expressed in Python using Google OR-Tools3 and can be executed as stated. In fact, the code presented in the book is automatically extracted, executed, and the output inserted into the text without manual intervention; even the graphs are produced automatically (thanks to Emacs4 and org-mode5). • My intention is to help the reader become a proficient modeler, not a theoretician. Therefore, little of the fascinating mathematical theory related to optimization is covered. It is nevertheless used profitably to create simple yet efficient models. • The associated web site provides all the code presented in the book along with a random generator for many of the problems and variations. The author uses this as a personalized homework generator. It can also be used as a self-guided learning tool. https://github.com/sgkruk/Apress-AI 3 https://github.com/google/or-tools 4 The one and only editor: http://emacs.org 5 http://orgmode.org/ 4