phone +7 (3412) 91 60 92

Archive of Issues

Russia Yekaterinburg
Section Mathematics
Title On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems
Author(-s) Salii Ya.V.ab
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa, Ural Federal Universityb
Abstract We consider the general case of *Precedence Constrained TSP* (or a less general case of *Sequential Ordering Problem*) solved with a special kind of dynamic programming method that uses precedence constraints to significantly reduce the number of subproblems that must be solved to find the optimal solution of the original problem. Our aim is to quantify this reduction, which is necessary to clarify the influence of precedence constraints on computational complexity of dynamic programming solutions of such problems. This variety of the method of dynamic programming has been developed by A.G. Chentsov and his co-authors since 2004 but there was only one attempt at examining the influence of precedence constraints on complexity, which only described the influence of a single precedence constraint in the form of an “address pair” (sender, receiver). Our approach to studying the complexity of this method is essentially the combinatorial analysis of the number of subproblems that are *feasible* in the sense of abiding by precedence constraints. Using the well-known combinatorial principles, *the rule of product* and *the rule of sum*, we established the estimates of complexity reduction for the following cases: a) “independent” sets of precedence constraints; b) “chains” of precedence constraints, when the precedence constraints define a linear ordering on the objects bound by them; c) precedence constraints expressed by an acyclic directed graph with outdegree (the number of receivers per sender) at most one. The latter case of precedence constraints is the one encountered in real-life problems of optimizing the route of the cutter in various machines used to cut sheet material. Since this is the most complex case of the three analyzed, instead of an analytic formula, we had to develop an algorithm (which we implemented in C++) to quantify the reduction; the computational complexity of the algorithm is less than quadratic with respect to the number of objects constrained by the precedence constraints. We intend to develop our approach to treat other cases of precedence constraints, eventually reaching the general case. We would also like to note that our method is optimization criterion-agnostic and thus applicable to many kinds of TSP, as long as they are precedence constrained and solvable by dynamic programming; in fact, our approach may be used to analyze the complexity of the dynamic programming method solution of any discrete optimization problem that deals with ordering subject to precedence constraints.
Keywords precedence constraints, dynamic programming, computational complexity, sequential ordering problem, sheet cutting
UDC 519.854.1, 519.854.2
MSC 90C27, 90C39, 68Q25
DOI 10.20537/vm140107
Received 16 January 2014
Language Russian
Citation Salii Ya.V. On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, issue 1, pp. 76-86.
  1. Cormen T., Leiserson C., Rivest L., Stein C. Introduction to Algorithms, 3rd Ed., Cambridge, Massachussets: MIT Press, 2009, 1303 p.
  2. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and scheduling: a theoretical approach) Moscow-Izhevsk: Institute of Computer Science, 2008, 240 p.
  3. Bellman R. On the theory of dynamic programming, Proc. Natl. Acad. Sci. USA, 1952, vol. 38, no. 8, pp. 716-719.
  4. Bellman R. Dynamic programming treatment of the travelling salesman problem, Journal of the ACM, 1962, vol. 9, no. 1, pp. 61-63.
  5. Held M., Karp P. A dynamic programming approach to sequencing problems, Journal of the Society for Industrial & Applied Mathematics, 1962, vol. 10, no. 1, pp. 196-210.
  6. Chentsov A.G., Chentsov P.A. Precedence-constrained routing (courier problem): a dynamic programming method, Vestn. Ural. Gos. Tekh. Univ. - Ural. Politekh. Inst., 2004, no. 15, pp. 148-151 (in Russian).
  7. Grigoriev A.M., Ivanko E.E., Chentsov A.G. Dynamic programming in a generalized courier problem with inner tasks: elements of a parallel structure, Model. Anal. Inform. Sist., 2011, vol. 18, no. 3, pp. 101-124 (in Russian).
  8. Petunin A.A., Chentsov A.G., Chentsov P.A. To the question about instrument routing in the automated machines of sheet cutting, Nauch. Tekhn. Vedom. SPb Gos. Politekh. Univ. Inform. Telekom. Upr., St. Petersburg, 2013, issue 2 (169), pp. 103-111 (in Russian).
  9. Aho A.V., Garey M.R., Ullman J.D. The transitive reduction of a directed graph, SIAM Journal on Computing, 1972, vol. 1, no. 2, pp. 131-137.
Full text
<< Previous article
Next article >>