Geodesic
On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 1 (2014), pp. 76-86 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{VUU_2014_1_a6,
     author = {Ya. V. Salii},
     title = {On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {76--86},
     year = {2014},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2014_1_a6/}
}
TY  - JOUR
AU  - Ya. V. Salii
TI  - On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2014
SP  - 76
EP  - 86
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VUU_2014_1_a6/
LA  - ru
ID  - VUU_2014_1_a6
ER  - 
%0 Journal Article
%A Ya. V. Salii
%T On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2014
%P 76-86
%N 1
%U http://geodesic.mathdoc.fr/item/VUU_2014_1_a6/
%G ru
%F VUU_2014_1_a6
Ya. V. Salii. On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 1 (2014), pp. 76-86. http://geodesic.mathdoc.fr/item/VUU_2014_1_a6/

[1] Cormen T., Leiserson C., Rivest R., Stein C., Introduction to Algorithms, 3rd Ed., MIT Press, Cambridge, Massachussets, 2009, 1303 pp. | MR | Zbl

[2] Chentsov A. G., Extremal problems of routing and scheduling: a theoretical approach, Institute of Computer Science, Moscow–Izhevsk, 2008, 240 pp.

[3] Bellman R., “On the theory of dynamic programming”, Proceedings of the National Academy of Sciences of the United States of America, 38:8 (1952), 716–719 | DOI | MR | Zbl

[4] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, Journal of the ACM, 9:1 (1962), 61–63 | DOI | MR | Zbl

[5] Held M., Karp P., “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[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, 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., 18:3 (2011), 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, no. 2(169), 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, 1:2 (1972), 131–137 | DOI | MR | Zbl