The Ordered Median Tree Location Problem Pozo, Miguel A.; Puerto, Justo; Torrejón, Alberto
Computers & operations research,
September 2024, 2024-09-00, Letnik:
169
Journal Article
Recenzirano
Odprti dostop
In this paper, we propose the Ordered Median Tree Location Problem (OMT). The OMT is a single-allocation facility location problem where p facilities must be placed on a network connected by a ...non-directed tree. The objective is to minimize the sum of the ordered weighted averaged allocation costs plus the sum of the costs of connecting the facilities in the tree. We present different MILP formulations for the OMT based on properties of the minimum spanning tree problem and the ordered median optimization. Given that ordered median location problems are rather difficult to solve we have improved the OMT solution performance by introducing covering variables in a valid reformulation plus developing two pre-processing phases to reduce the size of this formulations. In addition, we propose a Benders decomposition algorithm to approach the OMT. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium size instances on general random graphs.
•The Ordered Median Tree Location Problem (OMT) is a new problem in the literature.•Several MILP formulations based on properties of the Minimum Spanning Tree Problem and the Ordered Median Optimization are presented.•Polyhedral description and comparison of the two main formulations are detailed.•A Benders decomposition and alternative formulation for the resolution are included.•Extensive computational results are provided.
Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain ...experts and may often be suboptimal due to the hard nature of the problems. Reinforcement learning (RL) proposes a good alternative to automate the search of these heuristics by training an agent in a supervised or self-supervised manner. In this survey, we explore the recent advancements of applying RL frameworks to hard combinatorial problems. Our survey provides the necessary background for operations research and machine learning communities and showcases the works that are moving the field forward. We juxtapose recently proposed RL methods, laying out the timeline of the improvements for each problem, as well as we make a comparison with traditional algorithms, indicating that RL models can become a promising direction for solving combinatorial problems.
•Survey explores synergy of combinatorial optimization and reinforcement learning.•It covers recent papers showing how RL can be applied to solve canonical CO problems.•Graph neural networks are used as a method for graph representation in RL for CO.•Policy-based and value-based RL methods are used to learn the solutions to CO tasks.•Most of the reported experiments do not overlap.•This makes it hard to fairly compare the surveyed methods.
Nature-inspired optimization algorithms can solve different engineering and scientific problems owing to their easiness and flexibility. There is no need for structural modifications of optimization ...problems to apply meta-heuristic algorithms on them. Recently, meta-heuristic algorithms are becoming powerful methods for solving NP problems. In this paper, the authors propose a novel meta-heuristic algorithm suitable for continuous nonlinear optimization problems. The proposed method, Black Widow Optimization Algorithm (BWO), is inspired by the unique mating behavior of black widow spiders. This method includes an exclusive stage, namely, cannibalism. Due to this stage, species with inappropriate fitness are omitted from the circle, thus leading to early convergence. BWO algorithm is evaluated on 51 various benchmark functions to verify its efficiency in obtaining the optimal solutions for the problems. The obtained results indicate that the proposed algorithm has numerous advantages in different aspects such as early convergence and achieving optimized fitness value compared to other algorithms. Also, it has the capability of providing competitive and promising results. The research also solves three different challenging engineering design problems adopting BWO algorithm. The outcomes of the real case study problems prove the effectiveness of the proposed algorithm in solving real-world issues with unknown and challenging spaces.
•A novel bio-inspired Black Widow Optimization (BWO) Algorithm is proposed.•BWO is inspired by the bizarre mating behavior of black widow spiders.•BWO is compared with GA, PSO, ABC and BBO using 51 different benchmark functions.•BWO converges to the optimal value as quickly as possible.•BWO outperforms the other experimental algorithms in majority of test functions.
•A state-of-the-art survey of Benders decomposition algorithm.•Synthesizing the state-of-the-art in acceleration methods.•Focusing on combinatorial optimization.
The Benders decomposition algorithm ...has been successfully applied to a wide range of difficult optimization problems. This paper presents a state-of-the-art survey of this algorithm, emphasizing its use in combinatorial optimization. We discuss the classical algorithm, the impact of the problem formulation on its convergence, and the relationship to other decomposition methods. We introduce a taxonomy of algorithmic enhancements and acceleration strategies based on the main components of the algorithm. The taxonomy provides the framework to synthesize the literature, and to identify shortcomings, trends and potential research directions. We also discuss the use of the Benders Decomposition to develop efficient (meta-)heuristics, describe the limitations of the classical algorithm, and present extensions enabling its application to a broader range of problems.
•Survey of author’s research from 1972 to 2022.•Ten applications are presented.•Conclusions and avenues for future research are drawn.
In July 2022, I received the EURO Gold medal at the 32nd EURO ...Conference held in Espoo, Finland. This paper is based on the presentation I made at the medal award ceremony. It covers 10 topics on which I have worked throughout my career. These are the seriation problem, rotating work schedules, deterministic vehicle routing, stochastic vehicle routing, examination timetabling, districting, waste management, metro network design, green transportation, and humanitarian logistics.
Traveling salesman and vehicle routing problems with their variants, as classic combinatorial optimization problems, have attracted considerable attention for decades of their theoretical and ...practical value. Many classic algorithms have been proposed, for example, exact algorithms, heuristic algorithms, solution solvers, etc. Still, due to their complexity, even the most advanced traditional methods require too much computational time or are not well-defined mathematically; algorithm-based decision-making is no exception. Also, these methods cannot be generalized to a larger scale or other similar problems. With the latest developments in machine and deep learning, people believe it is feasible to apply reinforcement learning and other technologies in the decision-making or heuristic for learning combinatorial optimization. In this paper, we first gave an overview on how combinate deep reinforcement learning for the NP-hard combinatorial optimization, emphasizing general optimization problems as data points and exploring the relevant distribution of data used for learning in a given task. We next reviewed state-of-the-art learning techniques related to combinational optimization problems on graphs. Then, we summarized the experimental methods of using reinforcement learning to solve combinatorial optimization problems and analyzed the performance comparison of different algorithms. Lastly, we sorted out the challenges encountered by deep reinforcement learning in solving combinatorial optimization problems and future research directions.
This paper proposes a flexible pilot assignment method to jointly optimize the uplink and downlink data transmission in multi-cell Massive multiple input multiple output (MIMO) systems with ...correlated Rayleigh fading channels. By utilizing a closed-form expression of the ergodic spectral efficiency (SE) achieved with maximum ratio processing, we formulate an optimization problem for maximizing the minimum weighted sum of the uplink and downlink SEs subject to the transmit powers and pilot assignment sets. This combinatiorial optimization problem is solved by two sequential algorithms: a heuristic pilot assignment is first proposed to obtain a good pilot reuse set and the data power control is then implemented. Numerical results manifest that the proposed algorithm converges fast to a better minimum sum SE per user than the algorithms in previous works.
Since the 1960s, several approaches have been proposed to prevent the redrawing of electoral districts so that they are beneficial to a particular party or political faction (gerrymandering). In ...order to avoid gerrymandering, most approaches focus solely on redrawing electoral maps that try to maximize the compactness of the electoral districts. However, this problem is computationally hard, and several criteria must be satisfied when drawing electoral maps.
In this work we focus on drawing electoral districts for Portugal. For that, a new compact Boolean formulation is proposed for solving the electoral districting problem. This formulation satisfies all standard criteria for building electoral maps, particularly the contiguity and representation criteria. Moreover, a new compactness measure is also proposed that does not depend on geographic centers. Additionally, a heuristic formulation is also devised for problem instances where the optimum values are hard to find.
The new compactness measure and formulations are applied in the context of Portuguese parliament elections, assuming a change in the Portuguese electoral system. Experimental results on drawing electoral maps show that the proposed formulations are more effective than previous ones in drawing the electoral districts in the Portuguese context. Moreover, based on results from the last elections, gerrymandering scenarios are devised, showing that electoral outcomes can change depending on the drawing of the electoral maps.
•New compactness measure for electoral districting model.•New heuristic and exact models for electoral districting.•Extensive experimental analysis with classic models using real data from Portugal.
Learning-augmented maximum flow Polak, Adam; Zub, Maksym
Information processing letters,
August 2024, 2024-08-00, Letnik:
186
Journal Article
Recenzirano
Odprti dostop
We propose a framework for speeding up maximum flow computation by using predictions. A prediction is a flow, i.e., an assignment of non-negative flow values to edges, which satisfies the flow ...conservation property, but does not necessarily respect the edge capacities of the actual instance (since these were unknown at the time of learning). We present an algorithm that, given an m-edge flow network and a predicted flow, computes a maximum flow in O(mη) time, where η is the ℓ1 error of the prediction, i.e., the sum over the edges of the absolute difference between the predicted and optimal flow values. Moreover, we prove that, given an oracle access to a distribution over flow networks, it is possible to efficiently PAC-learn a prediction minimizing the expected ℓ1 error over that distribution. Our results fit into the recent line of research on learning-augmented algorithms, which aims to improve over worst-case bounds of classical algorithms by using predictions, e.g., machine-learned from previous similar instances. So far, the main focus in this area was on improving competitive ratios for online problems. Following Dinitz et al. (2021) 6, our results are among the firsts to improve the running time of an offline problem.
•We speed up maximum flow computation in graphs by using predictions.•Prediction is a flow satisfying flow conservation but not necessarily capacities.•We show that such predictions are efficiently learnable.•We compute flow in O(mη) time in m-edge graphs for predictions with L1 error up to η.
PDF
