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 Sciences^{a}, Ural Federal University^{b} 
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 
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. 7686. 
References 

Full text 