Linear and Convex Optimization. Michael H. Veatch
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