Annotation of the results obtained in 2023
The research topics of this project were related to the design and analysis of approximate algorithms for asymmetric routing problems of combinatorial optimization. The algorithms proposed in 2022 are based on the following ideas: - an effective reduction of the researching problem statement to the one or more statements of the asymmetric traveling salesman problem (ATSP) appended with the triangle inequality imposed on the transport cost function - the recently introduced (22+\varepsilon)-approximate Svensson-Traub algorithm is applied to approximate the induced statements. 1. In 2023, following the considered direction, we studied the approximability of the general statement of the classic vehicle routing problem (Capacitated Vehicle Routing Problem, CVRP) with the triangle inequality. It is shown that the combination of an adapted version of the well-known Haimovich-Rinnooy Kan algorithm and an arbitrary \alpha-approximate algorithm for ATSP leads to the approximate algorithm for CVRP with an approximation factor \alpha + 2 in the general case and \alpha + 1 when the capacity D satisfies the constraint D=o(n) where n is the number of vertices of a given graph. Thereby, there were shown that the combination of the well-known Iterated Tour Partiion (ITP) algorithm by Haimovich and Rinnooy Kan with the Svensson-Traub algorithm for ATSP leads to an approximate algorithm with an approximation factor 24 + \varepsilon (23 + \varepsilon for q=o( n)) for the classic CVRP problem. 2. At the same time, there was found the number of routing problems whose approximability in the class of polynomial algorithms with constanct approximation factor cannot be proved by the reduction to the asymmetric traveling salesman problem (at the current tine). For the algorithmic analysis of these problems, we carried out a deeper generalization of the Svensson and Traub approximation scheme: - we introduced new concepts of a strongly laminar statement and S-backbone by extending the same concepts from papers (Svensson, Tarnawski, Vegh - 2020) and (Traub, Vygen - 2022) for the case of not necessarily connected directed graphs; - we stated the sufficient conditions of the approximate solution existence for the Subtour Cover Problem (SCP) with a given accuracy; - the sufficient conditions for the existence of Svensson’s (\kappa, \eta)-algorithm were extended, which ensures the completion the route bone to the feasible solution of the auxiliary traveling salesman problem; - an extended version of the (\kappa, \eta)-algorithm was proved, which ensures the completion of the S-backbone to an approximate solution to the minimum weight cycle covering problem. The obtained theoretical results formed the basis for the first approximation algorithms with constant approximation factor for the problem of covering a minimum weight graph with a family of cycles of restricted capacity (Minimum-cost k-Size Cycle Cover Problem, Min-k-SCCP). For an arbitrary fixed k>1 and \varepsilon>0, polynomial approximation algorithms with constant approximation factors max{22+\varepsilon, 4 + k} and 24 + \varepsilon, respectively, are constructed. 3. In addition, we considered applicability of asymmetric routing problems to solving applied operations research problems. One of such application relates to the design of disruption-tolerant manufacturing processes and supply chains. The traditional approach to the analysis of such systems is based on the using the stochastic models, defining the choice of an optimal behavior scenario from a given (usually finite) family of possible ones. Despite a number of advantages, the use of this approach is significantly difficult in the event of problems of an unknown nature that threaten the performance of the entire simulated system. We introduced the minimax problem of constructing fault-tolerant production plans (Reliable Production Process Design Problem, RPPDP), the goal of which is to ensure the economical uninterrupted functioning of a distributed production and transport system. The introduced problem seems to be close to the classic problem of homeomorphic graph embedding (Subgraph Homeomorphism Problem, SHP), as well as problems studied within this project in 2022. The RPPDP problem statement is given by an ordered triple (G, П, k). Here G is an edge-weighted directed graph, the vertices of ehich are parted into: - dedicated vertices specifying the beginning and completion of each production plan; - homogeneous production points, united into pairwise disjoint clusters according to the principle of performing a specific production operation; - transport hubs, characterized by the cost of “opening” and throughput. The acyclic digraph P defines a partial order on a set of production clusters. The problem is to construct a minimax cost family consisting of k pairwise vertex-disjoint production plans that is homeomorphic embeddings of the graph P into the digraph G. It is shown that the RPPDP problem is NP-hard in the strong sense and remains intractable in special cases having a great meaning for applications. The following are proposed: an integer linear programming model (MILP model), an adaptive search heuristic in large neighborhoods (Adaptive Large Neighborhood Search, ALNS) and a branch-and-bound algorithm based on them. The high relaxation ability of the model and the efficiency of the implemented branching method are proved by the results of numerical experiments carried out on the public library of test statements proposed by the project team by extension of the well-known PCGTSPLIB library. The proposed library can be accessed by the link https://github.com/yogorodnikov/RPPDP-instances.

 

Publications

---

Annotation of the results obtained in 2022
In 2022, our research was focused on evolving the seminal recent results obtained by O. Svensson and V, Traub for the asymmetric traveling salesman problem (ATSP) with triangle inequality to several related settings of extreme routing combinatorial optimization problems. Actually, for each of them, we managed to propose first fixed-ratio polynomial time approximation algorithms. This year, the main attention was payed to such cases of the research, where fixed-ratio approximation succeed to be proved by cost-preserving polynomial time reduction of the problem on hand to some auxiliary instance of the ATSP or the problem approximated before. It is convenient to present the obtained results in terms of the studied combinatorial problems. Similarly to the ATSP, we assume for each of them that the objective function fulfills the triangle inequality. An instance of the Steiner Cycle Problem (SCP) is given by an edge-weighted digraph and a dedicated subset T of its terminal nodes. The goal is to construct the minimum cost closed (non-necessary elementary) route that visits each terminal from T. We obtain an approximation algorithm by the reduction of the initial problem to the ATSP on the subgraph of the metric closure of the given digraph induced by the subset T. An instance of the Rural Postman Problem (RPP) is also given by an edge-weighted digraph. But, instead of terminal nodes, we are given by a subset of terminal arcs R. Similarly to the SCP, we are required to find the cheapest closed route that traverses each terminal arc. We obtain a fixed-ratio approximation of this problem by reduction to the SCP. An instance of the asymmetric capacitated vehicle routing problem with unsplittable customer demands (CVRP-UCD) is given by a weighted digraph, whose node set consists of customer nodes and the dedicated depot node, an upper vehicle capacity bound D, and a couple of weighting functions. The first function specifies customer demands, while the second one the corresponding transportation costs. The problem is to present the minimum cost family of capacitated routes that satisfy the total customer demand. Our algorithm exploits polynomial time reduction of the problem in question to an auxiliary SCP instance, where the set T consists of the depot and all the customers with positive demands. Further, we use a special technique to split the obtained approximate Steiner cycle into a number of capacitated vehicle routes. By relying on the classic Hall’s Lemma, we embed the obtained routes into the family of routes of an arbitrary optimal solution of the studied problem. As a consequence, we obtain the desired approximation ratio upper bound (presented in Theorem 2, sec. 1.4) The approximation result for the Capacitated Arc Routing Problem (CARP) for the mixed graphs is obtained by the reduction of the initial problem to the CVRP-UCD. This year, we proved the fixed-ratio approximability of the `simplified’ variant of the known Prize-Collecting Traveling Salesman Problem, PCTSP. This setting differs from the general one by an absence of the knapsack constraint. An instance of the studied problem is given by an vertex- and edge-weighted digraph, each its node is penalized for skipping with a route, and each arc has a corresponding transportation cost. The problem is to construct the closed route that minimizes total transportation expenses and accumulated penalties. As it was shown in the well-known Bienstock, Goemans, Simchi-Levi, and Williamson paper (Math. Prog., 1993), the metric version of this problem has a 5/2-approximation algorithm applying the classic Chrisofides-Serdyukov algorithm as a `black box’. On the other hand, to date, for the considered asymmetric version of the problem, there are known only approximation algorithms with logarithmic ratios. By relying on the Svensson-Traub results, we proposed the first fixed-ratio approximation algorithm for this problem, with accuracy bound 23+\epsilon. An instance of the Generalized Traveling Salesman Problem (GTSP) is given by an edge-weighted digraph and additional partition of its node set into k clusters. Similarly to the classic traveling salesman problem, the weighting function specifies transportation costs. The goal is to construct the cheapest closed route visiting each the cluster at once. It is known that this problem belongs to FPT being parameterized by the number of clusters. Furthermore, an adapted version of the classic Held and Karp dynamic programming scheme solves this problem to optimality in polynomial time, if k=O(log n). This year, we proposed a fixed-ratio approximation algorithm for the case, where k= n- O(log n). In addition to the mentioned results, this year we started a research of combinatorial problems, whose approximation cannot be obtained by simple polynomial time reduction to the ATSP. For instance, this family contains the general setting of the PCATSP (with the knapsack constraint), the general setting of the GTSP, the VRP with time windows, and some other known extreme problems. For construction the desired approximation algorithms for such problems, we need to generalize the basic Svensson-Traub framework to the novel classes of MILP-models. This year, we obtained the preliminary results in a way of the extension of strongly laminar instances and backbones for the GTSP. The main results of this year can be briefly summarized in the following theorem. Theorem. For an arbitrary \alpha>=1, an \alpha-approximation algorithm for the ATSP with triangle inequality implies an existence of: (i) \alpha-approximation algorithms for the SCP, RPP and GTSP (with an additional constraint k= n-O(log n)) (ii) (3\alpha+2)-approximation algorithm for the CVRP-UCD and CARP (iii) (\alpha+1)-approximation algorithm for the PCATSP As a consequence, for an arbitrary \epsilon>0, we proposed (22+\epsilon)-approximation algorithms for the SCP, RPP, and GTSP (for k=n-O(log n)), (23+\epsilon)-approximation algorithm for the simplified version of the PCATSP, and (68 + 3\epsilon)-approximation algorithm for the CVRP-UCD and CARP.

 

Publications

---