Bigler, Tamara (2023). Model-based approaches for large-scale optimization in business operations. (Thesis). Universität Bern, Bern
|
Text
23bigler_t.pdf - Thesis Available under License Creative Commons: Attribution-Noncommercial-No Derivative Works (CC-BY-NC-ND 4.0). Download (1MB) | Preview |
Abstract
Companies nowadays have to operate in an increasingly competitive and complex environment. Under these challenging conditions, it has become essential for them to optimize their business operations, i.e., the activities that they must conduct on a regular, often daily, basis. The nature of these business operations strongly varies between companies. For a pharmaceutical company, an important business operation is, for example, the scheduling of their research activities. With improved scheduling, new drugs are brought to markets earlier, which can lead to a decisive competitive advantage. For a telecommunications company, an important business operation is, for example, the promotion of new products and services to existing customers. Contacting the right customers for the right products may lead to an increase in sales and profitability of these products. Many business operations, including the two examples from above, can be improved by solving mathematical optimization problems with techniques from the field of Operations Research. An optimization problem consists of the decisions to be taken, the constraints that define the set of feasible decisions, and an objective that is either maximized (profit) or minimized (project duration). In the case of the telecommunications company, the decisions to be taken are which customers are contacted for which product on which day. An example of a constraint is an overall budget that cannot be exceeded, and an example of the objective is the maximization of the total expected profit that results from contacting the customers. A standard approach for solving such an optimization problem is first to express the problem as a mathematical model and then use standard optimization software, known as a solver, to find the best possible solution. A great advantage of this approach is that the mathematical model can easily be adjusted to changes in the underlying problem. This flexibility is required in a dynamic business environment where constraints or objectives may change over time. However, a major drawback of this standard approach is its limited scalability when applied to specific types of complex optimization problems. For these problems, the generic solvers fail to find the best or even a good solution in a reasonable running time. Specialized algorithms, so-called heuristics, are required instead. Heuristics apply problem-specific search strategies to derive a good solution to an optimization problem quickly. However, because these heuristics are designed for specific optimization problems, they are difficult to adapt if the constraints or the objective of the optimization problem change. A solution technique that has been shown to be both flexible and scalable for complex optimization problems are matheuristics. Matheuristics are model-based approaches that decompose an optimization problem into smaller subproblems and solve these subproblems using mathematical models. Essential for the performance of a matheuristic is how the problem is decomposed into subproblems, which is an important field of research in Operations Research. This thesis contributes to this field of research by introducing model-based approaches for large-scale optimization in business operations. It consists of three papers on three specific optimization problems in direct marketing, project management, and facility location. Real-world instances of all three of these problems involve a large number of customers, activities, or facilities and require the flexibility to incorporate practical constraints easily. To address these challenges, we developed three matheuristics. The matheuristics employ innovative problem decomposition strategies and outperform state-of-the-art approaches on large-scale instances. In the first paper, we study a customer assignment problem from a major telecommunications company. The telecommunications company runs different direct marketing campaigns to promote its products and services. The goal of the telecommunications company is to assign the customers to the direct marketing campaigns so that the total expected profit is maximized. Thereby, various business constraints, such as budgets and sales constraints, must be considered. Also, different customer-specific constraints ensure that each customer is not assigned to a direct marketing campaign too frequently. A particular challenge is the size of practical problem instances. These instances involve millions of customers and hundreds of direct marketing campaigns. The methodological contribution of this paper consists of decomposing the optimization problem into two subproblems that each can be solved efficiently. In the first subproblem, customers are assigned to campaigns based on their membership to a customer group. In the second subproblem, individual customers are assigned to campaigns based on the solution that was derived in the first subproblem. The unique feature of our decomposition strategy is that the customer-specific constraints are already considered in the first subproblem, even though the first subproblem deals with groups of customers and not individual customers. In an experimental analysis based on numerous generated and real-world instances, we can demonstrate that even though we decompose the problem, the resulting solutions are still of very high quality. The matheuristic has been deployed in the company and is now used daily. In a proof of benefit conducted by the company based on a selected campaign, they observed that using the matheuristic increased the number of sales by 90%, resulting in an improvement in the profitability of this campaign by 300%. The second paper deals with a project scheduling problem that often arises in the pharmaceutical industry, where research activities, e.g., clinical tests, can be executed at different locations, e.g., research labs. The problem consists of determining a start time for each activity, selecting a location for the execution of each activity, and assigning resource units, e.g., research staff or equipment, to the execution of the activities. Various practical constraints must be considered, such as transportation times that arise when, e.g., a resource unit must be transported from one location to another. With only a few activities involved, the number of possible schedules can already grow very large. We developed a mathematical model and, based on this model, a novel matheuristic for this problem. The main methodological contribution of the matheuristic is its problem decomposition strategy. Instead of dividing the project into subprojects, the model in the matheuristic is set up for all project activities. However, the solver makes some decisions only for a subset of the activities. To schedule an entire project, multiple iterations have to be performed, where in each iteration, another subset of activities is considered. This iterative decision process substantially reduces running times compared to when all decisions are conducted simultaneously. In a computational experiment, the novel model outperforms the leading model from the literature on small instances. The matheuristic outperforms the state-of-the-art heuristics on all considered performance metrics on larger instances. In the third paper, we consider the problem of locating obnoxious facilities. Obnoxious means that the facilities negatively affect their nearby environment and should thus be located far away from clients. Examples of obnoxious facilities are waste plants, oil refineries, and wind turbines. The problem consists of opening from a set of potential locations a given number of facilities such that the open facilities are far away from the clients. We further study an extension of this problem that includes practical constraints which limit the number of facilities that can be opened in certain regions of an instance. Our matheuristic starts from an initial solution and iteratively improves the solution by removing and adding facilities. The quality of the final solution (after the improvement iterations) strongly depends on the initial solution. When two very similar initial solutions are provided, the likelihood of finding very similar final solutions is high. One main methodological contribution is a procedure that we designed, which is guaranteed to generate initial solutions that are very different from each other. This diversification in the initial solutions increases the likelihood of finding high-quality final solutions. The matheuristic outperforms the state-of-the-art metaheuristics on instances including thousands of clients and potential locations for facilities. Even though we consider three specific optimization problems in this thesis, the contributions of the three papers can be generalized and applied to related problems and thus advance the state of knowledge in the field of large-scale optimization.
| Item Type: | Thesis |
|---|---|
| Dissertation Type: | Cumulative |
| Date of Defense: | 21 February 2023 |
| Subjects: | 600 Technology > 650 Management & public relations |
| Institute / Center: | 03 Faculty of Business, Economics and Social Sciences > Department of Business Management |
| Depositing User: | Sarah Stalder |
| Date Deposited: | 01 Jun 2023 15:55 |
| Last Modified: | 21 Feb 2024 23:25 |
| URI: | https://boristheses.unibe.ch/id/eprint/4332 |
Actions (login required)
 |
View Item |