
Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2014, Issue 1, Pages 76–86
(Mi vuu418)




This article is cited in 2 scientific papers (total in 2 papers)
MATHEMATICS
On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems
Ya. V. Salii^{ab} ^{a} Institute of Mathematics and Computer Science, Ural Federal University, pr. Lenina, 51, Yekaterinburg, 620000, Russia
^{b} Department of Control Systems, N. N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620990, Russia
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 coauthors 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 wellknown 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 reallife 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 criterionagnostic 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.
Full text:
PDF file (296 kB)
References:
PDF file
HTML file
UDC:
519.854.1+519.854.2
MSC: 90C27, 90C39, 68Q25 Received: 16.01.2014
Citation:
Ya. V. Salii, “On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2014, no. 1, 76–86
Citation in format AMSBIB
\Bibitem{Sal14}
\by Ya.~V.~Salii
\paper On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
\yr 2014
\issue 1
\pages 7686
\mathnet{http://mi.mathnet.ru/vuu418}
Linking options:
http://mi.mathnet.ru/eng/vuu418 http://mi.mathnet.ru/eng/vuu/y2014/i1/p76
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:

A. G. Chentsov, A. M. Grigoryev, “A scheme of independent calculations in a precedence constrained routing problem”, Discrete Optimization and Operations Research (DOOR 2016), Lecture Notes in Computer Science, 9869, ed. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, Springer, Cham, 2016, 121–135

P. A. Chentsov, A. A. Petunin, “Tool routing problem for CNC plate cutting machines”, IFAC PAPERSONLINE, 49:12 (2016), 645–650

Number of views: 
This page:  203  Full text:  79  References:  33 
