111,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Discover the practical impacts of current methods of optimization with this approachable, one-stop resource Linear and Convex Optimization: A Mathematical Approach delivers a concise and unified treatment of optimization with a focus on developing insights in problem structure, modeling, and algorithms. Convex optimization problems are covered in detail because of their many applications and the fast algorithms that have been developed to solve them. Experienced researcher and undergraduate teacher Mike Veatch presents the main algorithms used in linear, integer, and convex optimization in a mathematical style with an emphasis on what makes a class of problems practically solvable and developing insight into algorithms geometrically. Principles of algorithm design and the speed of algorithms are discussed in detail, requiring no background in algorithms. The book offers a breadth of recent applications to demonstrate the many areas in which optimization is successfully and frequently used, while the process of formulating optimization problems is addressed throughout. Linear and Convex Optimization contains a wide variety of features, including: * Coverage of current methods in optimization in a style and level that remains appealing and accessible for mathematically trained undergraduates * Enhanced insights into a few algorithms, instead of presenting many algorithms in cursory fashion * An emphasis on the formulation of large, data-driven optimization problems * Inclusion of linear, integer, and convex optimization, covering many practically solvable problems using algorithms that share many of the same concepts * Presentation of a broad range of applications to fields like online marketing, disaster response, humanitarian development, public sector planning, health delivery, manufacturing, and supply chain management Ideal for upper level undergraduate mathematics majors with an interest in practical applications of mathematics, this book will also appeal to business, economics, computer science, and operations research majors with at least two years of mathematics training. Software to accompany the text can be found here: https://www.gordon.edu/michaelveatch/optimization
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 533
Veröffentlichungsjahr: 2020
Ähnliche
Table of Contents
Cover
Linear and Convex Optimization
Copyright
Preface
About the Companion Website
1 Introduction to Optimization Modeling
1.1 Who Uses Optimization?
1.2 Sending Aid to a Disaster
1.3 Optimization Terminology
1.4 Classes of Mathematical Programs
2 Linear Programming Models
2.1 Resource Allocation
2.2 Purchasing and Blending
2.3 Workforce Scheduling
2.4 Multiperiod Problems
2.5 Modeling Constraints
2.6 Network Flow
3 Linear Programming Formulations
3.1 Changing Form
3.2 Linearization of Piecewise Linear Functions
3.3 Dynamic Programming
4 Integer Programming Models
4.1 Quantitative Variables and Fixed Costs
4.2 Set Covering
4.3 Logical Constraints and Piecewise Linear Functions
4.4 Additional Applications
4.5 Traveling Salesperson and Cutting Stock Problems
5 Iterative Search Algorithms
5.1 Iterative Search and Constructive Algorithms
5.2 Improving Directions and Optimality
5.3 Computational Complexity and Correctness
6 Convexity
6.1 Convex Sets
6.2 Convex and Concave Functions
7 Geometry and Algebra of LPs
7.1 Extreme Points and Basic Feasible Solutions
7.2 Optimality of Extreme Points
7.3 Linear Programs in Canonical Form
7.4 Optimality Conditions
7.5 Optimality for General Polyhedra
8 Duality Theory
8.1 Dual of a Linear Program
8.2 Duality Theorems
8.3 Complementary Slackness
8.4 Lagrangian Duality
8.5 Farkas' Lemma and Optimality
9 Simplex Method
9.1 Simplex Method From a Known Feasible Solution
9.2 Degeneracy and Correctness
9.3 Finding an Initial Feasible Solution
9.4 Computational Strategies and Speed
10 Sensitivity Analysis
10.1 Graphical Sensitivity Analysis
10.2 Shadow Prices and Reduced Costs
10.3 Economic Interpretation of the Dual
11 Algorithmic Applications of Duality
11.1 Dual Simplex Method
11.2 Network Simplex Method
11.3 Primal‐Dual Interior Point Method
12 Integer Programming Theory
12.1 Linear Programming Relaxations
12.2 Strong Formulations
12.3 Unimodular Matrices
13 Integer Programming Algorithms
13.1 Branch and Bound Methods
13.2 Cutting Plane Methods
14 Convex Programming: Optimality Conditions
14.1 KKT Optimality Conditions
14.2 Lagrangian Duality
15 Convex Programming: Algorithms
15.1 Convex Optimization Models
15.2 Separable Programs
15.3 Unconstrained Optimization
15.4 Quadratic Programming
15.5 Primal‐dual Interior Point Method
A Linear Algebra and Calculus Review
A.1 Sets and Other Notation
A.2 Matrix and Vector Notation
A.3 Matrix Operations
A.4 Matrix Inverses
A.5 Systems of Linear Equations
A.6 Linear Independence and Rank
A.7 Quadratic Forms and Eigenvalues
A.8 Derivatives and Convexity
Bibliography
Index
End User License Agreement
List of Tables
Chapter 1
Table 1.1 Data for sending aid.
Chapter 2
Table 2.1 Data for Kan Jam production.
Table 2.2 Data for auto parts production.
Table 2.3 Data for Custom Tees ads.
Table 2.4 Data for producing steel.
Table 2.5 Solution for producing steel.
Table 2.6 Requirements and costs for police shifts.
Table 2.7 Demand and labor available for gift baskets
Table 2.8 Transmission costs, supply, and demand.
Table 2.9 Soybean shipping costs, supply, and demand.
Chapter 4
Table 4.1 Languages and costs for translators.
Table 4.2 Processing times for interventions against an intruder.
Table 4.3 Mileage between cities.
Chapter 7
Table 7.1 Basic solutions for Example 7.6.
Chapter 8
Table 8.1 Dual relationships.
Table 8.2 Possibilities when solving the primal and the dual.
Table 8.3 When Systems 1 and 2 have solutions.
Chapter 9
Table 9.1 Reduced costs and simplex directions for Example 9.5.
Chapter 10
Table 10.1 General terminology for a linear program.
Table 10.2 Sign of shadow prices.
Table 10.3 Data for Kan Jam production.
Table 10.4 Data for Custom Tees ads.
Chapter 11
Table 11.1 Dual relationships for corresponding basic solutions.
Table 11.2 Iterations of the path following algorithm.
Table 11.3 Points on central path.
List of Illustrations
Chapter 1
Figure 1.1 Region satisfying constraints for sending aid.
Figure 1.2 Optimal point and contour for sending aid.
Figure 1.3 Problem has optimal solution for dashed objective but is unbounde...
Figure 1.4 Feasible integer solutions for (1.5).
Chapter 2
Figure 2.1 Electricity transmission network.
Figure 2.2 Transportation network for soybeans.
Figure 2.3 Water pipe network for Exercise 2.25.
Chapter 3
Figure 3.1 Profit contribution (the negative of cost) for labor.
Figure 3.2 Street grid. Each block is labeled with its travel time and each ...
Figure 3.3 Travel times for Exercise 3.12.
Figure 3.4 Project costs for Exercise 3.13.
Chapter 4
Figure 4.1 A piecewise linear function.
Chapter 5
Figure 5.1 An improving direction for maximizing
.
Chapter 6
Figure 6.1 Feasible region and isocontours for Example 6.1.
Figure 6.2 The first set is convex. The second is not.
Figure 6.3 The point
is a convex combination of
,
,
.
Figure 6.4 Unbounded sets. Only the first two have unbounded directions.
Figure 6.5 A polyhedral cone.
Figure 6.6 The first function is convex. The second is concave.
Figure 6.7 The line
only intersects
at the point shown.
Figure 6.8 Epigraph of
.
Chapter 7
Figure 7.1 Basic solutions for Example 7.1.
Figure 7.2 The point
is a degenerate basic feasible solution.
Figure 7.3 Feasible region for Example 7.3.
Figure 7.4 Edge directions for the bfs
.
Figure 7.5 Cones and their extreme rays
.
Chapter 8
Figure 8.1 Gradient vectors and lines of constant
.
Figure 8.2 Gradient vectors and active constraint normal vectors.
Chapter 9
Figure 9.1 A polygon with
sides has diameter 4.
Chapter 10
Figure 10.1 Feasible region for (10.1) with constraint
.
Figure 10.2 Feasible region for 10.1 with
.
Figure 10.3 Optimal value as a function of
.
Figure 10.4 Feasible regions with right‐hand sides
.
Chapter 11
Figure 11.1 Heavy lines are a spanning tree of the directed graph.
Figure 11.2 A network flow problem for Figure 11.1.
Figure 11.3 Three spanning tree solutions. The dotted line is an entering ar...
Figure 11.4 An infeasible network flow problem.
Figure 11.5 A transportation problem with three supply nodes and two demand ...
Figure 11.6 Initial tree solution for Figure 11.5.
Figure 11.7 Final tree solution for Figure 11.5.
Figure 11.8 Progress of algorithm for Example 11.7.
Chapter 12
Figure 12.1 Feasible region for Example 12.1.
Figure 12.2 Feasible region and convex hull for Example 12.1.
Figure 12.3 Renumbering a spanning tree. Node and arc numbers in parentheses...
Chapter 13
Figure 13.1 A branch and bound tree.
Figure 13.2 Branch and bound tree for Example 13.1 after the first branching...
Figure 13.3 Branch and bound tree for Example 13.1.
Figure 13.4 Branch and bound tree for Example 13.2.
Figure 13.5 A cutting plane for
.
Figure 13.6 Feasible region for Example 13.4. The dashed line is a C–G inequ...
Chapter 14
Figure 14.1 Optimality condition with one constraint
.
Figure 14.2 Optimality condition with one constraint
.
Figure 14.3 Optimality condition with two inequality constraints.
Figure 14.4 Points
and
satisfy the KKT conditions but are not local maxi...
Figure 14.5 Primal and dual functions with a duality gap.
Figure 14.6 Primal function with no duality gap.
Figure 14.7 Primal function for Example 14.5 with no duality gap.
Chapter 15
Figure 15.1 Problems with optimal solutions in the interior and on an edge....
Figure 15.2 Gradient search.
Figure 15.3 Moving to the interior point
or the boundary point
.
Guide
Cover Page
Title Page
Copyright
Dedication
Preface
About the Companion Website
Table of Contents
Begin Reading
A Linear Algebra and Calculus Review
Bibliography
Index
WILEY END USER LICENSE AGREEMENT
Pages
iv
v
xi
xii
xiii
xiv
xv
xvii
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
343
344
345
346
347
348
349
350
351
352
353
355
356
357
358
359
361
362
363
364
365
366
367
Linear and Convex Optimization
A Mathematical Approach
Michael H. Veatch
Gordon College
This edition first published 2021
© 2021 by John Wiley and Sons, Inc.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.
The right of Michael H. Veatch to be identified as the author of this work has been asserted in accordance with law.
Registered Office
John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA
Editorial Office
111 River Street, Hoboken, NJ 07030, USA
For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.
Wiley also publishes its books in a variety of electronic formats and by print‐on‐demand. Some content that appears in standard print versions of this book may not be available in other formats.
Limit of Liability/Disclaimer of Warranty
While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
Library of Congress Cataloging‐in‐Publication Data
Names: Veatch, Michael H., author. | John Wiley and Sons, Inc., publisher.
Title: Linear and convex optimization : a mathematical approach / Michael
Veatch, Gordon College.
Description: Hoboken, NJ : Wiley, 2021. | Includes index.
Identifiers: LCCN 2020025965 (print) | LCCN 2020025966 (ebook) | ISBN
9781119664048 (cloth) | ISBN 9781119664024 (adobe pdf) | ISBN
9781119664055 (epub)
Subjects: LCSH: Mathematical optimization. | Nonlinear programming. |
Convex functions.
Classification: LCC QA402.5 .V395 2021 (print) | LCC QA402.5 (ebook) |
DDC 519.6–dc23
LC record available at https://lccn.loc.gov/2020025965
LC ebook record available at https://lccn.loc.gov/2020025966
Cover Design: Wiley
Cover Image: © Hybrid_Graphics/Shutterstock
To Dad, who introduced me to operations research, and Christian and Jackie, who were always curious how things worked
Preface
This book is about optimization problems that arise in the field of operations research, including linear optimization (continuous and discrete) and convex programming. Linear programming plays a central role because these problems can be solved very efficiently; it also has useful connections with discrete and convex optimization. Convex optimization is not included in many books at this level. However, in the past three decades new algorithms and many new applications have increased interest in convex optimization. Like linear programming, large applied problems can now be solved efficiently and reliably. Conceptually, convex programming fits better with linear programming than with general nonlinear programming.
These types of optimization are also appropriate for this book because they have a clear theory and unifying mathematical principles, much of which is included. The approach taken has three emphases.
Modeling is covered through a broad range of applications to fields such as on‐line marketing and inventory management, retail pricing, humanitarian response and rural development, public sector planning, health delivery, finance, manufacturing, service systems, and transportation. Many of these tell the story of successful applications of operations research.
A mathematical approach is used to communicate in a concise, unified manner. Matrix notation is introduced early and used extensively. Questions of correctness are not glossed over; the mathematical issues are described and, where the level is appropriate, proofs presented. Connections are made with some other topics in undergraduate mathematics. This approach grew out of my 30 years of teaching these topics to undergraduate mathematics students.
The reasoning behind algorithms is presented. Rather than introducing algorithms as arbitrary procedures, whenever possible reasons are given for why one might design such an algorithm. Enough analysis of algorithms is presented to give a basic understanding of complexity of algorithms and what makes an algorithm efficient. Algorithmic thinking is taught, not assumed.
Many introductory operations research textbooks emphasize models and algorithms without justifications and without making use of mathematical language; such books are ill‐suited for mathematics students. On the other hand, texts that treat the subject more mathematically tend to be too advanced and detailed, at the expense of applications. This book seeks a middle ground.
The intended audience is junior and senior mathematics students in a course on optimization or (deterministic) operations research. The background required is a good knowledge of linear algebra and, in a few places, some calculus. These are reviewed in the appendix. The coverage and approach is intentionally kept at an undergraduate level. Material is often organized by depth, so that more advanced topics or approaches appear at the end of sections and chapters and are not needed for continuity. For example, the many ways to speed up the simplex method are saved for the last section of Chapter 9.
In keeping with this audience, the number of different problem types and algorithms is kept to a minimum, emphasizing instead unified approaches and more general problems. In particular, heuristic algorithms are only mentioned briefly. They are used for hard problems and use many different approaches, while this book focuses on problems that have efficient algorithms or at least unified approaches. The goal is to introduce students to optimization, not to be a thorough reference, and to appeal to students who are curious about other uses of mathematics. The many applications in the early chapters make the case that optimization is useful. The latter chapters connect the solution of these problems to the linear algebra and other mathematics that this audience is familiar with.
The book is also specifically written for the instructor who is mathematically trained, not for a specialist in operations research and optimization. The careful treatment of algorithmic thinking and the introduction to complexity of algorithms are intended to assist these instructors. The mathematical style throughout the book should be more accommodating to mathematics professors. It is also intended to support learning objectives more likely to be found in a mathematics department, including why the algorithms are correct and how they use theoretical results such as convexity and duality. Being able to perform an algorithm by hand is not a primary objective; it plays a supporting role to understanding the notation and reasoning of the algorithm. Calculations that are well‐understood by mathematics students, such as solving a linear system or performing row operations, are not elaborated on. The somewhat more advanced material at the end of sections or chapters is also intended to support instructors who are not specialists, allowing them to extend their knowledge and explore the literature.
Chapters 1–4 are devoted to introducing optimization and optimization modeling. Convex models appear later with the other material on convex optimization. In my experience teaching mathematics students, they find modeling challenging. These chapters assume technology is available to solve problems, so that the focus can stay on formulation, as well as interpreting solutions. They build steadily in sophistication, starting with numerical instances but soon moving to algebraic formulations to make clear the distinction between model structure and data. The features of the models also build, particularly when using logical variables. In contrast with the business case study approach, each model has a limited number of features and focuses on some novel feature. I have found that mathematics students relate better to a succession of simpler models, from which they learn different modeling principles, than to a long case study.
Chapters 5–8 discuss iterative algorithms, giving some easily explained examples from discrete optimization, and the theoretical background for linear programming. This includes a little computational complexity, convexity and the study of polyhedra, optimality conditions for linear programming, and duality theory for linear programming. It is unorthodox to cover all of these before introducing the simplex method. However, conceptually these topics fit together and do not depend on the simplex method; putting them together emphasizes this fact. Chapter 8 on duality is independent of Chapter 9 on the simplex method, so that they can be covered them in either order. I typically skip the topics in Sections 5.3, 7.5, 8.4, and 8.5 to arrive at the simplex method about the middle of the semester.
Chapters 9–11 present the simplex method, including sensitivity analysis, and other algorithms for linear programming. A developmental approach is taken to presenting the simplex method. Starting with geometric reasoning about why it works, it is presented in the “naive” form first, where the so‐called inverse basis matrix is computed from scratch each iteration. While this form is computationally inefficient, it is very easy to explain to a mathematics student, both for computing and justifying that the algorithm works. When working examples, technology can be used to invert and multiply matrices. After completing the picture of why the method works (degeneracy, two‐phase simplex), Section 9.4 takes up the issue of making the simplex method more efficient, including the tableau form and revised simplex method. Instructors who wish to start with the tableau can use the material found here. Chapter 10 on sensitivity analysis, which depends Chapter 8, can be skipped without loss of continuity; however, the interpretation of dual variables as shadow prices and partial derivatives is enriching, even in an age when sensitivity analysis can be done quickly by solving modified linear programs. An interpretation of strong duality in terms of average costs is also given in Section 10.3. Chapter 11 presents three more algorithms for linear programming, all of which rely on duality: the dual simplex, transportation simplex, and a primal‐dual, or path following, interior point method. The transportation simplex method is presented first as a minimum cost flow problem, then specialized to transportation problems.
Chapters 12 and 13 present integer programming algorithms. These relate to the earlier material because of the importance of linear programming to establish bounds when solving an integer program. Integer programming also has greater modeling power, as demonstrated by the many applications in Chapter 14. Chapters 14 and 15 introduce convex programming, including some motivating applications. The earlier chapters are designed to prepare the reader to understand convex programming more readily. The KKT optimality conditions and duality theorems are a generalization of Lagrangian duality (Section 8.4). Necessary and sufficient conditions for a global optimum follow from convexity theory, already applied to linear programs in Chapter 6. Chapter 15 culminates in the primal‐dual interior point method, which was presented for linear programs in Section 11.3. Quadratic programming is also introduced and the connection between the primal‐dual interior point method and sequential quadratic programming is made.
Supplemental material will be available at the web site www.gordon.edu⁄michaelveatch⁄optimization for the book. A full solution manual will be made available to instructors.
The book contains the amount of material covered in a typical two‐semester sequence of undergraduate classes. A semester course focusing on linear programming could cover Chapters 1, 2, Sections 3.1–3.2, 5, 6, Sections 7.1–7.4 and 8.1–8.3, 9, 10 plus some other topics from these chapters and Chapter 11. A course on linear and integer programming could cover Chapters 1, 2, Sections 3.1–3.2, 4, 5, 6, Sections 7.1–7.4 and 8.1–8.3, 9, 12, and 13. A somewhat more advanced course on linear and convex programming could cover Chapters 1–3, 5–7.4, 8, 9, Sections 11.1–11.13, 14, and 15.
Several more advanced or specialized topics have been included at the end of chapters or sections that are optional and can be easily skipped. Section 3.3 shows that a dynamic program can be solved as a linear program, an approach that relates to machine learning. Section 5.3 on computational complexity, while not difficult, is only occasional mentioned in the later chapters. Section 7.5 extends the optimality conditions needed to solve linear programs to general polyhedra. Section 8.4 introduces Lagrangian duality for linear programs and shows that it is equivalent to the usual dual; it is only needed if convex programming (Chapter 14) is being covered. Farkas' lemma is presented in Section 8.5, providing another approach to duality theorems. The computational strategies in Section 9.4 are important to the simplex method but are not used in the sequel. The interior point algorithm in Section 11.4 is computationally more involved. It is closely related to Section 15.5.
I want to express my deep appreciation to the many people who helped make this book possible. First, I want to thank David Rader, Larry Leemis, and Susan Martonosi for encouraging me to undertake the project. I am grateful to my former and current students Isaac Bleecker, Mackenzie Hinds, Joe Iriana, Stephen Rizzo, and Michael Yee for reviewing portions of the draft. I also thank my friend John Sanderson for drawing the figures, my colleague Jonathan Senning for his technical advice, and students Isaac Bleecker, Jessica Guan, Seth McKinney, and Yi Zhou for their help with the exercises and figures.
Most of all, I am grateful for my wife Cindy's confidence in me and acceptance of my working odd hours on the project. Now we are both authors.
Michael H. Veatch
Wenham, MAMarch, 2020
About the Companion Website
This book is accompanied by a companion website:
www.wiley.com/go/veatch/convexandlinearoptimization
The website includes the instructor solutions manual.
1Introduction to Optimization Modeling
1.1 Who Uses Optimization?
Data‐driven decision‐making is on the rise. Many businesses, governmental organizations, and nonprofits collect large amounts of data and seek to use them to inform the decisions they make. In addition to data and statistical analysis, a mathematical model of the system is often needed to find the best or even a viable option. Examples include planning the flow of goods through a supply chain, scheduling personnel shifts, or choosing an investment portfolio. The approach of optimization is to develop a model describing which potential decisions could be taken, in light of physical, logical, financial, or other limitations, and assess them using a single objective. This objective could be profit or loss in a business setting, expected return on an investment, a physical measure such as minimizing time to complete a task, a health measure such as expected lives saved, or in the government and nonprofit sector, a measure of social welfare. The mathematical model is an optimization problem; the study of them is called optimization.
Once a system has been modeled, an algorithm is required to find the best, or nearly best, decision. Fortunately, there are general algorithms that can be used to solve broad classes of problems. Algorithms for several classes of problems will be the main topic of this book.
Optimization is a very broad concept. There are minimization principles in physics, such as Snell's law of diffraction, or surface tension minimizing the area of a surface. In statistics, the least squares principle is an easily‐solved minimization problem while new techniques involve challenging optimization problems to fit models to data. Control engineers use minimization principles to develop feedback controls for systems such as autopilots and robots. Many techniques in machine learning can also be described as optimization problems.
This book focuses on optimization to support decisions in businesses, government, and organizations. The models used in these applications tend to have many interrelated variables, require significant amounts of data, and often have a complex structure unique to the application. The field that addresses these problems is called operations research. The field had its origins during World War II, when British military leaders asked scientists to work on military problems, such as the deployment of radars and the management of antisubmarine operations. These efforts were called military operations research; after the war similar techniques were applied to industry. Operations research employs mathematical models, not all of which use optimization. The same approach and mathematical methods are used in engineering problems, but we focus on decision‐making applications. Today, operations research is a profession, an approach to applied problems, and a collection of mathematical techniques. It is sometimes called “the science of better” as it seeks to increase value and efficiency through better decision‐making.
Operations research is sometimes also called management science or operational research. Similar techniques are used in industrial engineering and operations engineering, with a somewhat narrower view of applications. There is a strong overlap with business analytics, which refers to any use of data to improve business processes, whether statistical methods or optimization.
While the use of optimization models for decision‐making has become common, most of the decisions to which they are applied are not fully automated; rather, the models provide guidelines or insights to managers for making decisions. For some problems, models can be fairly precise and identify good decisions. For many others, the model is enough of an approximation that the goal of modeling is insights, not numbers. We only briefly cover the modeling process, at the beginning of Chapter 2. However, the examples we present give some appreciation for how models can be useful for decisions.
A prime example of the use of optimization models is the airline industry (Barnhart et al., 2003). Starting in the late 1960s with American Airlines and United Airlines, flight schedules, routing, and crew assignment in the airline industry were based on large‐scale, discrete optimization models. By about 1990, airlines started using revenue management models to dynamically adjust prices and use overbooking, generating significant additional revenues. Optimization models have also been used more recently for air traffic flow management.
Optimization has also been of great value for e‐business and the sharing economy. For example, the Motivate bikeshare systems in New York City, Chicago, and San Francisco use optimization to reallocate the docking stations throughout the city (Freund et al., 2019). First they estimate the user dissatisfaction function, due to not having a bike or docking station available for potential users, as a function of the docking capacity and initial inventory at each location. Then a large optimization problem is solved to find the allocation of docking capacity that minimizes this user dissatisfaction. Optimization was also used in the design of an incentive scheme to crowdsource rebalancing, where users are given incentives to take trips that move bikes to locations where they are needed. The next section presents a question arising in disaster response to introduce the basic concepts of optimization modeling.
1.2 Sending Aid to a Disaster
International responses to rapid‐onset disasters are frequent and expensive. After a major disaster, such as the 2014 earthquake in Nepal, food, shelter, and other items are needed quickly in large quantities. Local supplies may be insufficient, in which case airlift to a nearby airport is an important part of a timely response. The number of flights in the first few days may be limited by cost and other factors, so the aid organizations seek to send priority items first.
To illustrate the decisions involved, consider an organization that is sending tents and nonperishable food from their stockpile to people whose homes were destroyed in a hurricane. Because they are delivering to a small airport, they are using a medium‐sized cargo aircraft, the C‐130. It has space for six pallets and a payload capacity of 40 000 lb for this length of flight. In the next week or so, the responding organizations will try to fly in enough supplies to meet all the high‐priority needs. But the first flights will be loaded before the needs assessment is even complete, just knowing that a large number of people need food and shelter. The organization has estimated the criticality of each item on a 10‐point scale (10 being the most critical). They are based on the deprivation likely to be experienced by recipients if the item is not delivered until later. However, for many reasons, not all aid meets high‐priority needs, so the organization also considers the cost (market value) of the aid, and defines expected benefit to be the average of criticality and cost. Their objective is to load the aircraft to have the greatest expected benefit. Table 1.1 lists the weight, cost, criticality, and expected benefit for both items. They have time to re‐pack one pallet with a mixture of tents and food, so the number of pallets of each item does not have to be an integer. However, only five pallets of food are immediately available – they do not stockpile large quantities of food because it eventually expires.
Table 1.1 Data for sending aid.
Tents
Food
Weight (1000 lbs)
7.5
5
Cost ($1000/pallet)
11
4
Criticality
5
8
Expected benefit
8
6
The first idea one might have is to load six pallets of tents, the item with the largest expected benefit. However, this load is not allowed because it exceeds the weight limit. Further, since the number of pallets does not have to be an integer, trying other loads may not find the best one. Instead, we formulate the problem mathematically. Let
Then the expected value of aid loaded is
and we want to maximize over a domain that contains the possible values of . First, we have the logical restrictions . The weight limit requires that
In this expression, 7.5 is the weight per pallet of tents, so is the weight of tents. Similarly, is the weight of food. The left‐hand side, then, is the total weight of the load, which must be less than or equal to the payload capacity of 40 (these quantities are in 1000s of lbs). The space limit requires that
The left‐hand side is the total number of pallets. This total does not have to be an integer; a total of 5.4 pallets would mean that one pallet is only loaded 40% full. Finally, only five pallets of food are ready, so
These inequalities define the domain of . We will call them constraints and the function to be maximized the objective function. Optimizing a function whose domain is defined by constraints is a constrained optimization problem. The complete problem is
We have abbreviated “subject to” as “s.t.”
Constrained optimization problems have three components:
Components of an Optimization Problem
1. The decision variables.
2. The objective function to be maximized or minimized, as a function of the decision variables.
3. The constraints that the decision variables are subject to.
The formulation of this problem consists of the Eqs. (1.1) and the definitions of the variables. It is essential to define the variables and also good practice to label or describe the objective function and each constraint. This problem is an example of a linear program because the variables are continuous and the objective function and all constraints are linear.
Now that we have formulated the loading decisions as a linear program, how do we solve it? For and to satisfy the constraints, they must lie in the intersection of the half planes defined by these inequalities, shown in Figure 1.1. Most linear inequalities can be conveniently graphed by finding the and intercept of the corresponding equation, drawing a line between them, and checking a point not on the line, such as , to see if it satisfies the inequality. If the point satisfies the inequality, then the half‐plane is on the same side of the line as that point; if the point does not satisfy the inequality, the half‐plane is on the other side of the line as that point. For the first constraint (weight), the intercept is , the intercept is 8, and (0,0) is on the correct side of the line. Other constraints, such as , have horizontal or vertical boundary lines. Once all of the constraints have been graphed, we can identify the region (or possibly a line or a point) satisfying all the constraints. We are seeking the point in this region that has the largest value of . One way to find this point graphically is to plot contour lines for one or two values of . For example, in Figure 1.1 the contours
Figure 1.1 Region satisfying constraints for sending aid.
are graphed as dashed lines. They both intersect the shaded region, so there are points satisfying the constraints with objective function values of 24 and 36. Since all contour lines are parallel, we can visualize sweeping the line up and to the right without rotating it to find larger objective function values. The farthest contour line that touches the shaded region is shown in Figure 1.2. The point where it touches the region has the largest objective function value. This point lies on the constraint lines for weight and pallets, so we can find it by solving these two constraints with equality in place of inequality:
with solution and objective function value 44. This agrees with Figure 1.2, where the contour line drawn is . Thus, the optimal load is four pallets of tents and two pallets of food, with an expected value of 44.
Figure 1.2 Optimal point and contour for sending aid.
To summarize, to solve a linear program with two variables graphically:
Solving a Linear Program Graphically
Graph the region that satisfies all of the constraints.
Draw a contour line of the objective function and determine which direction improves the objective function. A second contour line can be used to determine which direction is improving.
Sweep the contour line in the improving direction, generating parallel lines, until it is about to leave the region. The last line intersecting the region has the optimal objective function value. The point(s) where this line intersects the region is optimal.
Find the coordinates of an optimal point by solving a system of two linear equations from the constraints whose lines pass through this point.
If the set of points satisfying the constraints is nonempty and bounded, then an optimal solution exists and the method earlier will find it. The other cases are discussed in Section 1.3.
Viewing the problem graphically brings up several questions about linear programs that will be answered in later chapters. First, the optimal value occurred at a corner point of the region, where two (or more) constraint lines intersect. Will this always be the case? Second, the idea of sweeping the contour line until it leaves the region assumes that contour lines intersect points satisfying the constraints for in a single interval. Thus, an optimal objective function value is one where lines with slightly larger do not touch the region. Is it possible for the contour line to leave the region and reenter it? That is, for if the line for touches the region and the line for does not, it possible for the line for to touch the region? If so, we would have to do more checking to find the optimal . Related to this is the question of local maxima. The point is called a local maximum as it has the largest objective function value of all points in a small circle around . It is easier to check that it is a local maximum than examining all points that satisfy the constraints to check that it is a global maximum. Is it always true that a local maximum is also a global maximum? Finally, the region in Figure 1.2 is defined by the constraints, but the optimal point depends on the objective function. For example, if instead we wish to maximize
the optimal load is pallets of tents and pallets of food, with a cost of $58 667. However, for small changes in the coefficients of , the point is still optimal. How much can an objective function coefficient be changed without changing the optimal point?
The fractional solution makes sense in this problem: one pallet is re‐packed with as much food. In other problems, fractional solutions may not make sense. They can either be interpreted as approximate solutions that must be converted to integers to be implemented, or a different optimization problem can be studied, where the variables are discrete, only taking on integer values.
1.2.1 The Modeling Process
As we move from this small linear program to more general and complex models, some guidelines on modeling will be helpful. When formulating a mathematical program, it is not always obvious what the decision variables should be. There are often multiple approaches to defining the variables and there can be pros and cons to different approaches. The objective is intended to reflect the priorities of the decision‐maker. To pose the situation as a mathematical program, an objective must be chosen. This may be very clear, as when maximizing profit, or much more subtle, as in the example previously. The constraints may include physical, logical, financial, or other limitations. They may also reflect policies that the decision‐maker applies. Finally, a constraint may simply be an equation that defines an auxiliary variable that is used to write the problem more concisely.
Another theme that will emerge is the difference between specific and general models. We will often use algebraic notation for (some of) the constants in a model, rather than numbers. This allows us to separate the data that goes into a model from its structure. It is this structure that defines the general model. There are multiple levels of generality to a model used in an application. One way to generalize is to allow any size of the problem: instead of two items being loaded, there could be items. To make a model more specific, we often add constraints with a special structure to describe a specific situation.
The examples in this book take a verbal description of an optimization problem and translate it into mathematics. There is much more involved in using models to guide decisions. The overall modeling process may involve:
Problem definition
. The first step is to identify the problem that the decision‐maker faces. This includes specifying the objective and the system to be studied.
Data collection
. The next step is to collect data that is relevant to the model. This may entail observing the system or obtaining data that is already recorded.
Model formulation
. In this step the analyst formulates a mathematical model of the decision problem. It involves translation into mathematical language, but also abstraction or simplification of a complex operation into a manageable problem.
Model solution
. For optimization problems, this step finds an optimal or near‐optimal solution. Generally this is done numerically using an algorithm, rather than algebraically.
Verification and validation
. This step tries to determine if the model is an adequate representation of the decision problem. Verification involves checking for internal consistency in that the mathematical model agrees with its specification or assumptions. Validation seeks to build confidence that the model is sufficiently accurate. For optimization problems, accuracy may be gauged by whether the optimal solution produced by the model is reasonable or whether the objective function is accurate over a variety of feasible solutions. Validation methods that have been developed for statistical or simulation models might also be used.
Implementation
. Once an optimal solution is obtained from the model, it may need to be modified. For example, fractional values may need to be converted to integers. The result may be one or more near‐optimal solutions that are presented to the decision‐maker. In other situations, the model may provide insights that help the decision‐maker with their decisions, or a system might be implemented so that the model is run repeatedly with new data to support future decisions.
These steps are not just done in this order. The verification and validation process, feedback obtained about the model, and changing situations often lead to multiple cycles of revising the model. When applications are presented in this book, we focus on Step 3, model formulation, and mostly on the translation process, not the simplifying assumptions. Whether a model is useful, however, depends on the other steps. It is important to ask “Where does the data come from?” as in Albright and Winston (2005). But it is also necessary to ask “Where does the model come from?,” that is, what are the model assumptions and why were they made?
1.3 Optimization Terminology
Now we introduce more terminology for constrained optimization problems, as well as summarizing the terms introduced in the last section. These problems are called mathematical programs. The variables that we optimize over are the decision variables. They may be continuous variables, meaning that they can take on values in the real numbers, including fractions, or they may discrete variables that can only take on integer values. The function being optimized is the objective function. The domain over which the function is optimized is the set of points that satisfy the constraints, which can be equations or inequalities. We distinguish two kinds of constraints. Functional constraints can have any form, while variable bounds restrict the allowable values of one variable. Many problems have nonnegativity constraints as their variable bounds. In (1.1), the food constraint is listed with the functional constraints, making three functional constraints plus two nonnegativity constraints (variable bounds), but it is also a bound, so the problem can also be said to have two functional constraints and three bounds.
Let be the decision variables and satisfies the constraints be the solution set of the constraints. Departing somewhat from the usual meaning of a “solution” in mathematics, we make the following definitions
A
solution
to a mathematical program is any value
of the variables.
A
feasible solution
is a solution that satisfies all constraints, i.e.
.
The
feasible region
is the set of feasible solutions, i.e.
.
The
value
of a solution is its objective function value.
An
optimal solution
is a feasible solution that has a value at least as large (if maximizing) as any other feasible solution.
To solve a mathematical program is to find an optimal solution and the optimal value , or determine that none exists. We can classify each mathematical program into one of three categories.
Existence of Optimal Solutions When solving a mathematical program:
The problem has one or more
optimal solutions
(we include in this category having solutions whose value is arbitrarily close to optimal, but this distinction is rarely needed), or
The problem is an
unbounded problem
, meaning that, for a maximization, there is a feasible solution
with value
for every
, or
The problem is
infeasible
: there are no feasible solutions, i.e.
.
An unbounded problem, then, is one whose objective function is unbounded on (unbounded above for maximization and below for minimization). One can easily specify constraints for a decision problem that contradict each other and have no feasible solution, so infeasible problems are commonplace in applications. Any realistic problem could have bounds placed on the variables, leading to a bounded feasible region and a bounded problem. In practice, these bounds are often omitted, leaving the feasible region unbounded. A problem with an unbounded feasible region will still have an optimal solution for certain objective functions. Unbounded problems, on the other hand, indicate an error in the formulation. It should not be possible to make an infinite profit, for example.
Figure 1.3 Problem has optimal solution for dashed objective but is unbounded for dotted objective.
Example 1.1 (Unbounded region) Consider the linear program
The feasible region is shown in Figure 1.3; the dashed line has an objective function value of 210. Sweeping this line down, the minimum value occurs at the corner point with an optimal value of 180. The feasible region is unbounded. Now suppose the objective function is changed to . The dotted line shows the contour line ; sweeping the line upward decreases the objective without bound, showing that the problem is unbounded.
1.4 Classes of Mathematical Programs
In Section 1.2 we introduced the concept of a linear program. This section introduces algebraic and matrix notation for linear programs. It then defines the three main classes of mathematical programs: linear programs, integer programs, and nonlinear programs. Each of these will be studied in later chapters, though for nonlinear programs we will focus on the more tractable subclass of convex programs. A mathematical program with variables and objective function can be stated abstractly in terms of a feasible region as
However, we will always describe the feasible region using constraint equations or inequalities. The notation for the constraints is introduced in the following text.
1.4.1 Linear Programs
We have already seen two examples of linear programs.
General Form of a Linear Program
There are decision variables, and functional constraints. The constraints can use a mixture of “”, “”, and “”. Each variable may have the bound , , or no bound, which we call unrestricted in sign (u.r.s.). The distinguishing characteristics of a linear program are (i) the objective function and all constraints are linear functions and (ii) the variables are continuous, i.e. fractional values are allowed. They are often useful as approximate models even when these assumptions do not fully hold.
We will use matrix notation for linear programs whenever possible. Let , , , and
Here , , and are column vectors. If all the constraints are equalities, they can be written . Similarly, “” constraints can be written .
Example 1.2 Consider the linear program
Converting the objective function and constraints to matrix form, we have
If we let
then this linear program can be written
It is important to distinguish between the structure of an optimization problem and the data that provides a specific numerical example. The structure of (1.4) is a minimization linear program with “” constraints and nonnegative variables; the data are the values in , , and .
To write a mixture of “” and “” constraints, it is convenient to use submatrices
and write, e.g.
1.4.2 Integer Programs
Many practical optimization problems involve making discrete quantitative choices, such as how many fire trucks of each type a fire department should purchase, or logical choices, such as whether or not each drug being developed by a pharmaceutical company should be chosen for a clinical trial. Both types of situations can be modeled by integer variables.
Consider again the linear program (1.1) with the alternative objective function (1.2
2Linear Programming Models
A great variety of real‐world problems can be modeled as linear programs. Many businesses and other organizations have successfully used linear programming or other optimization models to improve their operations and decision‐making. This chapter presents some of the linear programming models that have been useful. We will cite specific successful applications, but will generally present smaller examples that illustrate the approach.
2.1 Resource Allocation
Many problems involve deciding how much of each product to produce or sell when the products compete for resources. Here is an example of such a product mix problem.
Example 2.1 (Kan Jam) Wild Sports produces the Kan Jam yard game, which consists of a flying disc and two plastic cans used as goals. In addition to the Ultimate Disc Game, they have begun producing a Splash Pool Disc Game. They also sell the disc individually. The primary materials used are plastic to make the goals, cardboard packaging, and the discs, which are manufactured at a separate location. Because of uncertainty in when these materials will be resupplied, they would like to make a one month production plan using the on‐hand materials. The material requirements and availability are shown in Table 2.1, along with the retail price on Amazon and the profit for each product. Because the pool version is smaller, they have set its price slightly lower but it still has a larger profit margin. However, the demand for this new product is limited. The forecasted demand at this price is 2000 for the month. How many of each product should be produced to maximize profit for the month?
Table 2.1 Data for Kan Jam production.
Material
Ultimate
Pool
Disc
Available
Plastic (oz)
48
40
0
240 000
Flying discs
1
1
1
8000
Packaging (
)
10
10
2
75 000
Selling price ($)
40
38
9
—
Profit margin ($)
10
12
2
—
To formulate as a linear program, let , , and denote the number of Ultimate, Pool, and separate discs produced this month, respectively. We can express profit as
Each material imposes a constraint on the production quantities. For example, the total amount of plastic used must be less than or equal to the amount of plastic available, so
