Min–max and min–max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the ...min–max and min–max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min
s–
t cut, knapsack. Since most of these problems are
NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.
A review of dynamic vehicle routing problems Pillac, Victor; Gendreau, Michel; Guéret, Christelle ...
European journal of operational research,
02/2013, Letnik:
225, Številka:
1
Journal Article
Recenzirano
Odprti dostop
► We review the research on dynamic vehicle routing. ► Our taxonomy is based on quality and evolution of information. ► We present several real-world applications of dynamic vehicle routing. ► We ...survey the current state-of-the-art solution techniques for dynamic routing. ► We describe promising research directions on dynamic routing.
A number of technological advances have led to a renewed interest in dynamic vehicle routing problems. This survey classifies routing problems from the perspective of information quality and evolution. After presenting a general description of dynamic routing, we introduce the notion of degree of dynamism, and present a comprehensive review of applications and solution methods for dynamic vehicle routing problems.
Machine learning (ML) has been recently introduced to solving optimization problems, especially for combinatorial optimization (CO) tasks. In this paper, we survey the trend of leveraging ML to solve ...the mixed-integer programming problem (MIP). Theoretically, MIP is an NP-hard problem, and most CO problems can be formulated as MIP. Like other CO problems, the human-designed heuristic algorithms for MIP rely on good initial solutions and cost a lot of computational resources. Therefore, researchers consider applying machine learning methods to solve MIP since ML-enhanced approaches can provide the solution based on the typical patterns from the training data. Specifically, we first introduce the formulation and preliminaries of MIP and representative traditional solvers. Then, we show the integration of machine learning and MIP with detailed discussions on related learning-based methods, which can be further classified into exact and heuristic algorithms. Finally, we propose the outlook for learning-based MIP solvers, the direction toward more combinatorial optimization problems beyond MIP, and the mutual embrace of traditional solvers and ML components. We maintain a list of papers that utilize machine learning technologies to solve combinatorial optimization problems, which is available athttps://github.com/Thinklab-SJTU/awesome-ml4co.
Existing planning approaches for onshore wind farm siting and grid integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an exact ...approach for the integrated layout and cable routing problem of onshore wind farm planning using the Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. In selected regions of Germany, the trade-offs between minimizing costs and landscape impact of onshore wind farm siting are investigated. Although our case studies show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, grid integration must be simultaneously optimized to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision-making and help optimize wind farms in large regions in the future.
•Integrated wind layout and cable routing problem as Quota Steiner Tree Problem (QSTP).•Integration of a novel transformation of the QSTP into the exact solver scip-Jack.•Solver vastly outperforms generic out-of-the-box MIP solver on a large instance set.•Application on the bi-objective case of minimizing costs and impact on the landscape.•Large-scale wind expansion studies should include cable routing.
Network Alignment (NA) is a hard optimization problem with important applications such as, for example, the identification of orthologous relationships between different proteins and of phylogenetic ...relationships between species. Given two (or more) networks, the goal is to find an alignment between them, that is, a mapping between their respective nodes such that the topological and functional structure is well preserved. Although the problem has received great interest in recent years, there is still a need to unify the different trends that have emerged from diverse research areas. In this paper, we introduce AntNetAlign, an Ant Colony Optimization (ACO) approach for solving the problem. The proposed approach makes use of similarity information extracted from the input networks to guide the construction process. Combined with an improvement measure that depends on the current construction state, it is able to optimize any of the three main topological quality measures. We provide an extensive experimental evaluation using real-world instances that range from Protein–Protein Interaction (PPI) networks to Social Networks. Results show that our method outperforms other state-of-the-art approaches in two out of three of the tested scores within a reasonable amount of time, specially in the important S3 score. Moreover, it is able to obtain near-optimal results when aligning networks with themselves. Furthermore, in larger instances, our algorithm was still able to compete with the best performing method in this regard.
•We propose a new ant colony optimization algorithm for the network alignment problem.•Network alignment is an important optimization problem with many applications.•A possible application is the identification of phylogenetic relationships between species.•Our algorithm is able to optimize any of the three main topological quality measures.•We provide an extensive experimental evaluation and a comparison to the state of the art.•Our algorithm outperforms the competitors in two out of three tested scores.
•A comprehensive review on the integration of machine learning into meta-heuristics.•A unified taxonomy to provide a common terminology and classification.•Classification of numerous articles based ...on different characteristics.•Technical discussions on advantages, limitations, requirements, and challenges.•Proposition of promising future research directions.
In recent years, there has been a growing research interest in integrating machine learning techniques into meta-heuristics for solving combinatorial optimization problems. This integration aims to lead meta-heuristics toward an efficient, effective, and robust search and improve their performance in terms of solution quality, convergence rate, and robustness.
Since various integration methods with different purposes have been developed, there is a need to review the recent advances in using machine learning techniques to improve meta-heuristics. To the best of our knowledge, the literature is deprived of having a comprehensive yet technical review. To fill this gap, this paper provides such a review on the use of machine learning techniques in the design of different elements of meta-heuristics for different purposes including algorithm selection, fitness evaluation, initialization, evolution, parameter setting, and cooperation. First, we describe the key concepts and preliminaries of each of these ways of integration. Then, the recent advances in each way of integration are reviewed and classified based on a proposed unified taxonomy. Finally, we provide a technical discussion on the advantages, limitations, requirements, and challenges of implementing each of these integration ways, followed by promising future research directions.
Large-scale dynamical systems are becoming pervasive today and the costs associated with maintenance and processing should be kept to the minimum. In multi-agent systems, whereas onboard capabilities ...often allow local communication, some agents need to be equipped with more expensive communication and computation devices that enable proper regulation and monitoring of the system. As such, there is an implicit combinatorial problem associated with deciding the smallest number of agents (or, more generically, state variables) that require simultaneous actuation and sensing. Due to the potential freedom or uncertainty of the weights in such a multi-agent system, we rely on structural systems theory and, in this paper, we address the problem of determining the minimum number of state variables that need to be simultaneously actuated and measured to ensure structural controllability and observability, respectively. We notice that a possible ‘separation principle’ to first find the solution to either problem and then putting them together does not necessarily hold an optimal solution. Remarkably, we show that despite the combinatorial nature of the problem, it is possible to design a solution with polynomial computational complexity, which contrasts with the non-structural version of the problem (i.e., a minimum number of a simultaneous actuator and sensor placement to guarantee controllability and observability, respectively) that it is NP-hard.
The Quadratic Knapsack Problem (QKP) is a well-studied combinatorial optimization problem with practical applications in various fields such as finance, logistics, and telecommunications. Despite its ...longstanding interest, the QKP remains challenging due to its strong NP-hardness. Moreover, recent studies have introduced new instances where all existing algorithms have failed to produce good-quality results. In this paper, we aim to address these challenging QKP instances by proposing a novel approach to enhance the regular value function used in dynamic programming (DP) literature. Our proposed method considers the contribution of each item not only with respect to the items already selected, but also estimates its potential contribution with respect to items yet to be considered. Additionally, we introduce a propagation technique and a “remove-and-fill-up” local search procedure to further improve the solution quality. Through extensive computational experiments, our heuristic algorithm demonstrates superior performance compared to existing heuristics, producing optimal or near-optimal solutions for even the most demanding QKP instances. Empirical evidence, supported by an automated instance space analysis using unbiased metrics, showcases the remarkable improvements achieved, with solutions surpassing on average the solution quality of existing algorithms by up to 98%, and up to 77% reduction of the computational time.
•We develop a novel heuristic algorithm for the quadratic knapsack problem.•We present a propagation procedure to enhance the algorithm.•We also propose a remove-and-fill-up local search procedure for further amelioration.•The algorithms can find near-optimal solutions for the most challenging instances.
A fundamental component of the game-theoretic approach to distributed control is the design of local utility functions. Relative to resource allocation problems that are additive over the resources, ...Part I showed how to design local utilities so as to maximize the associated performance guarantees (Paccagnan, et al ., 2020), which we measure by the price of anarchy. The purpose of this article is to specialize these results to the case of submodular, covering, and supermodular problems. In all these cases, we obtain tight expressions for the price of anarchy that often match or improve the guarantees associated with state-of-the-art approximation algorithms. Two applications and corresponding numerics are presented: the vehicle-target assignment problem and a coverage problem arising in wireless data caching.
PDF
