90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Document Type
- Doctoral Thesis (3)
- Article (1)
- Diploma Thesis (1)
- Preprint (1)
Language
- English (6)
Has Fulltext
- yes (6)
Keywords
- ADMM (1)
- Bundle Methods (1)
- Constraint-Coupled Systems (1)
- Convex Optimization (1)
- Distributed Optimization (1)
- Dual Decomposition (1)
- Federated Learning (1)
- Hub-and-Spoke-System (1)
- Mixed-integer Programming (1)
- Model Predictive Control (1)
Faculty / Organisational entity
Distributed Optimization of Constraint-Coupled Systems via Approximations of the Dual Function
(2024)
This thesis deals with the distributed optimization of constraint-coupled systems. This problem class is often encountered in systems consisting of multiple individual subsystems, which are coupled through shared limited resources. The goal is to optimize each subsystem in a distributed manner while still ensuring that system-wide constraints are satisfied. By introducing dual variables for the system-wide constraints the system-wide problem can be decomposed into individual subproblems. These resulting subproblems can then be coordinated by iteratively adapting the dual variables. This thesis presents two new algorithms that exploit the properties of the dual optimization problem. Both algorithms compute a quadratic surrogate function of the dual function in each iteration, which is optimized to adapt the dual variables. The Quadratically Approximated Dual Ascent (QADA) algorithm computes the surrogate function by solving a regression problem, while the Quasi-Newton Dual Ascent (QNDA) algorithm updates the surrogate function iteratively via a quasi-Newton scheme. Both algorithms employ cutting planes to take the nonsmoothness of the dual function into account. The proposed algorithms are compared to algorithms from the literature on a large number of different benchmark problems, showing superior performance in most cases. In addition to general convex and mixed-integer optimization problems, dual decomposition-based distributed optimization is applied to distributed model predictive control and distributed K-means clustering problems.
In recent years, the concept of a centralized drainage system that connect an entire city to one single treatment plant is increasingly being questioned in terms of the costs, reliability, and environmental impacts. This study introduces an optimization approach based on decentralization in order to develop a cost-effective and sustainable sewage collection system. For this purpose, a new algorithm based on the growing spanning tree algorithm is developed for decentralized layout generation and treatment plant allocation. The trade-off between construction and operation costs, resilience, and the degree of centralization is a multiobjective problem that consists of two subproblems: the layout of the networks and the hydraulic design. The innovative characteristics of the proposed framework are that layout and hydraulic designs are solved simultaneously, three objectives are optimized together, and the entire problem solving process is self-adaptive. The model is then applied to a real case study. The results show that finding an optimum degree of centralization could reduce not only the network’s costs by 17.3%, but could also increase its structural resilience significantly compared to fully centralized networks.
This thesis addresses several challenges for sustainable logistics operations and investigates (1) the integration of intermediate stops in the route planning of transportation vehicles, which especially becomes relevant when alternative-fuel vehicles with limited driving range or a sparse refueling infrastructure are considered, (2) the combined planning of the battery replacement infrastructure and of the routing for battery electric vehicles, (3) the use of mobile load replenishment or refueling possibilities in environments where the respective infrastructure is not available, and (4) the additional consideration of the flow of goods from the end user in backward direction to the point of origin for the purpose of, e.g., recapturing value or proper disposal. We utilize models and solution methods from the domain of operations research to gain insights into the investigated problems and thus to support managerial decisions with respect to these issues.
This paper presents a case study of duty rostering for physicians at a department of orthopedics and trauma surgery. We provide a detailed description of the rostering problem faced and present an integer programming model that has been used in practice for creating duty rosters at the department for more than a year. Using real world data, we compare the model output to a manually generated roster as used previously by the department and analyze the quality of the rosters generated by the model over a longer time span. Moreover, we demonstrate how unforeseen events such as absences of scheduled physicians are handled.
We introduce and investigate a product pricing model in social networks where the value a possible buyer assigns to a product is influenced by the previous buyers. The selling proceeds in discrete, synchronous rounds for some set price and the individual values are additively altered. Whereas computing the revenue for a given price can be done in polynomial time, we show that the basic problem PPAI, i.e., is there a price generating a requested revenue, is weakly NP-complete. With algorithm Frag we provide a pseudo-polynomial time algorithm checking the range of prices in intervals of common buying behavior we call fragments. In some special cases, e.g., solely positive influences, graphs with bounded in-degree, or graphs with bounded path length, the amount of fragments is polynomial. Since the run-time of Frag is polynomial in the amount of fragments, the algorithm itself is polynomial for these special cases. For graphs with positive influence we show that every buyer does also buy for lower prices, a property that is not inherent for arbitrary graphs. Algorithm FixHighest improves the run-time on these graphs by using the above property.
Furthermore, we introduce variations on this basic model. The version of delaying the propagation of influences and the awareness of the product can be implemented in our basic model by substituting nodes and arcs with simple gadgets. In the chapter on Dynamic Product Pricing we allow price changes, thereby raising the complexity even for graphs with solely positive or negative influences. Concerning Perishable Product Pricing, i.e., the selling of products that are usable for some time and can be rebought afterward, the principal problem is computing the revenue that a given price can generate in some time horizon. In general, the problem is #P-hard and algorithm Break runs in pseudo-polynomial time. For polynomially computable revenue, we investigate once more the complexity to find the best price.
We conclude the thesis with short results in topics of Cooperative Pricing, Initial Value as Parameter, Two Product Pricing, and Bounded Additive Influence.
A hub location problem consists of locating p hubs in a network in order to collect and consolidate flow between node pairs. This thesis deals with the uncapacitated single allocation p-hub center problem (USApHCP) as a special type of hub location problem with min max objective function. Using the so-called radius formulation of the problem, the dimension of the polyhedron of USApHCP is derived. The formulation constraints are investigated to find out which of these define facets. Then, three new classes of facet-defining inequalities are derived. Finally, efficient procedures to separate facets in a branch-and-cut algorithm are proposed. The polyhedral analysis of USApHCP is based on a tight relation to the uncapacitated facility location problem (UFL). Hence, many results stated in this thesis also hold for UFL.