Loading AI tools
NP-hard problem in combinatorial optimization From Wikipedia, the free encyclopedia
The ring star problem (RSP) is a NP-hard problem[1] in combinatorial optimization. In a complete weighted mixed graph, the ring star problem aims to find a minimum cost ring star subgraph formed by a cycle (ring part) and a set of arcs (star part) such that each arc's child node belongs to the cycle and each arc's parent node does not. The costs for the arcs are usually different than the cycle's costs. The cycle must contains at least one node which is called the depot or the root.
RSP is a generalization of the traveling salesman problem.[1] When the costs of the arcs are infinite and the ring contains all nodes, the RSP reduces to TSP. Some applications of RSP arise in the context of telecommunications,[2] transports or logistics.
RSP was first formulated in 1998.[2] The first MILP for solving RSP was introduced in 2004 alongside valid inequalities that improve the formulation.[1] Several exact formulations have since been introduced in order to solve the Ring star problem such as a graph-layers based ILP[3] and a st-chains formulation.[4]
Many variants of the ring star problem have been studied since 2006.
The first heuristic for RSP, a general variable neighborhood search has been introduced in order to obtain approximate solutions more quickly.[12] In 2013, an evolutionary algorithm also approximates RSP. In 2020, an ant colony optimization[13] heuristic outperforms the evolutionary algorithm heuristic.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.