Ring star problem

Last updated

Example of a Ring Star Problem network Ring Star Problem solution.svg
Example of a Ring Star Problem network

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.

Contents

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.

Exact formulations

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]

Variants of the ring star problem

Many variants of the ring star problem have been studied since 2006.

Heuristics

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.

Related Research Articles

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

Branch and bound is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

<span class="mw-page-title-main">Ant colony optimization algorithms</span> Optimization algorithm

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems that can be reduced to finding good paths through graphs. Artificial ants represent multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a preferred method for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

<span class="mw-page-title-main">Guillotine cutting</span> Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine.

<span class="mw-page-title-main">Vehicle routing problem</span> Optimization problem

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.

Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be solved in polynomial-time.

In mathematical optimization and computer science, heuristic is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.

<span class="mw-page-title-main">Ravindra K. Ahuja</span> American computer scientist

Ravindra K. Ahuja is an Indian-born American computer scientist and entrepreneur. He is currently Professor of Industrial and Systems Engineering at the University of Florida in Gainesville, Florida, and CEO of the automation and optimization solutions provider Optym, which he founded in 2000 as Innovative Scheduling, Inc.

<span class="mw-page-title-main">Fred W. Glover</span> American computer scientist

Fred Glover is Chief Scientific Officer of Entanglement, Inc., USA, in charge of algorithmic design and strategic planning for applications of combinatorial optimization in quantum computing. He also holds the title of Distinguished University Professor, Emeritus, at the University of Colorado, Boulder, associated with the College of Engineering and Applied Science and the Leeds School of Business. He is known for his innovations in the area of metaheuristics including the computer-based optimization methodology of Tabu search an adaptive memory programming algorithm for mathematical optimization, and the associated evolutionary Scatter Search and Path Relinking algorithms.

<span class="mw-page-title-main">Iterated local search</span>

Iterated Local Search (ILS) is a term in applied mathematics and computer science defining a modification of local search or hill climbing methods for solving discrete optimization problems.

Variable neighborhood search (VNS), proposed by Mladenović & Hansen in 1997, is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems. It explores distant neighborhoods of the current incumbent solution, and moves from there to a new one if and only if an improvement was made. The local search method is applied repeatedly to get from solutions in the neighborhood to local optima. VNS was designed for approximating solutions of discrete and continuous optimization problems and according to these, it is aimed for solving linear program problems, integer program problems, mixed integer program problems, nonlinear program problems, etc.

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of the knapsack problem, combining the features of the 0-1 knapsack problem and the quadratic knapsack problem.

Multi-objective linear programming is a subarea of mathematical optimization. A multiple objective linear program (MOLP) is a linear program with more than one objective function. An MOLP is a special case of a vector linear program. Multi-objective linear programming is also a subarea of Multi-objective optimization.

Maria Grazia Speranza is an Italian applied mathematician and operations researcher. Her research involves the application of mathematical optimization to problems including portfolio optimization and the combination of inventory management with vehicle routing.

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.

<span class="mw-page-title-main">Philippe Baptiste</span> French engineer and researcher (born 1972)

Philippe Baptiste is a French engineer, academic and researcher. Baptiste is most well known as the president of the National Centre for Space Studies CNES in addition to his several books and scientific publications and communications in the field of algorithms, combinatorial optimization, operational research and artificial intelligence. On December 23, 2024, he was appointed Minister responsible for Higher Education and Research, reporting to Minister Elizabeth Borne.

In mathematics, the capacitated arc routing problem (CARP) is that of finding the shortest tour with a minimum graph/travel distance of a mixed graph with undirected edges and directed arcs given capacity constraints for objects that move along the graph that represent snow-plowers, street sweeping machines, or winter gritters, or other real-world objects with capacity constraints. The constraint can be imposed for the length of time the vehicle is away from the central depot, or a total distance traveled, or a combination of the two with different weighting factors.

A large-scale capacitated arc routing problem (LSCARP) is a variant of the capacitated arc routing problem that covers 300 or more edges to model complex arc routing problems at large scales.

Optimal kidney exchange (OKE) is an optimization problem faced by programs for kidney paired donations (also called Kidney Exchange Programs). Such programs have large databases of patient-donor pairs, where the donor is willing to donate a kidney in order to help the patient, but cannot do so due to medical incompatibility. The centers try to arrange exchanges between such pairs. For example, the donor in pair A donates to the patient in pair B, the donor in pair B donates to the patient in pair C, and the donor in pair C donates to the patient in pair A.

Optimal network design is a problem in combinatorial optimization. It is an abstract representation of the problem faced by states and municipalities when they plan their road network. Given a set of locations to connect by roads, the objective is to have a short traveling distance between every two points. More specifically, the goal is to minimize the sum of shortest distances, where the sum is taken over all pairs of points. For each two locations, there is a number representing the cost of building a direct road between them. A decision must be made about which roads to build with a fixed budget.

References

  1. 1 2 3 Labbé, Martine; Laporte, Gilbert; Martín, Inmaculada Rodríguez; González, Juan José Salazar (May 2004). "The Ring Star Problem: Polyhedral analysis and exact algorithm". Networks. 43 (3): 177–189. doi:10.1002/net.10114. ISSN   0028-3045.
  2. 1 2 Xu, Jiefeng; Chiu, Steve Y.; Glover, Fred (1999). "Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search". Management Science. 45 (3): 330–345. doi:10.1287/mnsc.45.3.330. ISSN   0025-1909. JSTOR   2634881.
  3. ↑ Simonetti, L.; Frota, Y.; de Souza, C.C. (September 2011). "The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm". Discrete Applied Mathematics. 159 (16): 1901–1914. doi:10.1016/j.dam.2011.01.015.
  4. ↑ Kedad-Sidhoum, Safia; Nguyen, Viet Hung (January 2010). "An exact algorithm for solving the ring star problem". Optimization. 59 (1): 125–140. doi:10.1080/02331930903500332. ISSN   0233-1934.
  5. ↑ Baldacci, R.; Dell'Amico, M.; González, J. Salazar (December 2007). "The Capacitated m -Ring Star Problem". Operations Research. 55 (6): 1147–1162. doi:10.1287/opre.1070.0432. ISSN   0030-364X.
  6. ↑ Naji-Azimi, Zahra; Salari, Majid; Toth, Paolo (16 December 2010). "A heuristic procedure for the Capacitated m-Ring Star problem". European Journal of Operational Research. 207 (3): 1227–1234. doi:10.1016/j.ejor.2010.06.030. ISSN   0377-2217.
  7. ↑ Baldacci, R.; Dell’Amico, M. (16 May 2010). "Heuristic algorithms for the multi-depot ring-star problem". European Journal of Operational Research. 203 (1): 270–281. doi:10.1016/j.ejor.2009.07.026. ISSN   0377-2217.
  8. ↑ Sundar, Kaarthik; Rathinam, Sivakumar (1 March 2017). "Multiple depot ring star problem: a polyhedral study and an exact algorithm". Journal of Global Optimization. 67 (3): 527–551. arXiv: 1407.5080 . doi:10.1007/s10898-016-0431-7. ISSN   1573-2916.
  9. ↑ Fouilhoux, Pierre; Questel, Aurélien (April 2014). "A branch-and-cut for the Non-Disjoint m-Ring Star Problem". RAIRO - Operations Research. 48 (2): 167–188. doi:10.1051/ro/2014006. ISSN   0399-0559.
  10. ↑ Khamphousone, Julien; Castaño, Fabian; Rossi, André; Toubaline, Sonia (March 2024). "A survivable variant of the ring star problem". Networks. 83 (2): 324–347. doi:10.1002/net.22193.
  11. ↑ Truong, Tran Mai Anh; Toubaline, Sonia; Rossi, André (March 2024). "Survivable Ring Star Problem under the failure of two hubs". 25ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2024). Université Picardie Jules Vernes.
  12. ↑ Dias, Thayse Christine S.; de Sousa Filho, Gilberto F.; Macambira, Elder M.; dos Anjos F. Cabral, Lucidio; Fampa, Marcia Helena C. (2006). "An Efficient Heuristic for the Ring Star Problem". Experimental Algorithms. Lecture Notes in Computer Science. Vol. 4007. Springer. pp. 24–35. doi:10.1007/11764298_3. ISBN   978-3-540-34597-8.
  13. ↑ Zang, Xiaoning; Jiang, Li; Ding, Bin; Fang, Xiang (1 June 2021). "A hybrid ant colony system algorithm for solving the ring star problem". Applied Intelligence. 51 (6): 3789–3800. doi:10.1007/s10489-020-02072-w. ISSN   1573-7497.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.