Heuristic solutions to robust variants of the minimum-cost integer flow problem
This paper deals with robust optimization applied to network flows. Two robust variants of the minimum-cost integer flow problem are considered. Thereby, uncertainty in problem formulation is limited to arc unit costs and expressed by a finite set of explicitly given scenarios. It is shown that both problem variants are NP-hard. To solve the considered variants, several heuristics based on local search or evolutionary computing are proposed. The heuristics are experimentally evaluated on appropriate problem instances.
Code (0)
등록된 구현이 없습니다.
Tasks
ARCSimilar Papers 제목 키워드 기반
Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem
The minimum common string partition problem is an NP-hard combinatorial optimization problem with applications in computational biology. In this work we propose the first integer linear programming model for solving this…
Combinatorial OptimizationFast, Flexible, and Exact Minimum Flow Decompositions via ILP
Minimum flow decomposition (MFD) (the problem of finding a minimum set of paths that perfectly decomposes a flow) is a classical problem in Computer Science, and variants of it are powerful models in multiassembly proble…
Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining
Recently, hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques, where frequent patterns found…
Efficient ExplorationClustered Orienteering Problem with Subgroups
This paper introduces an extension to the Orienteering Problem (OP), called Clustered Orienteering Problem with Subgroups (COPS). In this variant, nodes are arranged into subgroups, and the subgroups are organized into c…
An Efficient Matheuristic for the Minimum-Weight Dominating Set Problem
A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph either belongs to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a numb…