In this work behavior of one exact polynomial algorithms for particular case of optimal sequencing problems when it's used for arbitrary graphs and sequencing widths is analysed. Based on this analysis several modifications of this algorithm are developed. Results of computational experiments has shown that proposed modifications are effective and substantially increase precision of finding optimal solution up to 98,5 percent. Additionally it is proved that an arbitrary optimal sequencing problem can be reduced to the problem with graph that has a dense sequencing for even sequencing width.
When solving practical problems related to the optimal allocation of a finite set of
jobs (tasks, projects, operations, etc.) between executors, two main classes are
distinguished: the first - problems in which the order of execution is arbitrary, the second
problems in which technological constraints are imposed. This work is devoted to the
latter. Since the technological constraints can be mathematically modeled with a
directed acyclic graph, the problems under consideration are formulated as optimization
problems on graphs. In general, these problems are NP-hard, so it is important to have
effective approximate algorithms of polynomial complexity [
Consider one of the well-known problems of sequencing vertices of a directed graph.
Suppose that a finite set of jobs is specified, on the order of execution of which the
technological constraints are imposed [
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
It is natural to set technological constraints in a form of directed acyclic graph G(V ,U ) , V n , where V is the set of vertices whose elements are associated with the jobs. Then the arrows correspond to the technological constraints. One of the optimization problems that arises in this case is the construction of optimal parallel sequencing, which is defined as such placement of the vertices of the digraph in linearranged places for which the following conditions are satisfied: ─ in each place there is no more than a given number of vertices, denoted h ; ─ if a pair of vertices i, jU , then vertex i is located to the left of vertex j ; ─ the number of non-empty places (called the sequencing length and denoted l ) on which all vertices of the graph are placed is minimal.
In the general case, that is, for an arbitrary graph G and width h , this problem is
NP-hard, so directional search schemes such as the branch and bound method are
used to find the exact solution. Only for four partial cases the exact algorithms of
polynomial complexity are found. This is the case when the graph G is directed
forest [
Suppose that we have an arbitrary acyclic directed graph G and h 2 . In this case, in order to construct the desired optimal sequencing, one can use an algorithm that was historically first. This method of constructing S is called the algorithm based on the maximum matching.
Algorithm based on maximum matching. 1. For а graph G(V ,U ) , we construct an undirected graph G(V , E) , where i, j E , if there is no path in the graph G neither from vertex i to j nor from j to i .
2. In the obtained graph G , we find the maximal matching, which is denoted M E , that is, a subset of the edges of the maximal cardinality with no vertices in common. 3. In the desired sequencing S , we consider all places empty and set k 1 . 4. If G is empty, then the algorithm is finished. 5. One of the following cases is possible: (a) Among the open vertices of G , there exists one that does not belong to any of the edges in M , then we choose it to be placed. (b) In the set M there is an edge i, j such that vertices i and j are open, then we choose them for the placement and remove i, j from M . (c) In the set M there is a pair of edges i, p and j, q such that vertices i and j are open, and between vertices p and q there is an edge in the graph G , then we choose vertices i and j for placement, edges i, p and j, q are removed from M , and the edge p, q is added to M . 6. We place the selected vertices on the k th place of the sequencing S and remove them from the graph G together with the arrows directed from them, if any. Set G : G , k : k 1 and go to 4.
It is important to note that polynomial complexity algorithms, such as the blossom algorithm, are known for finding M for arbitrary undirected graphs.
It was proved in [
Consider some of the statements and their corollaries, which will narrow down a set of parallel sequencing tasks that need consideration, namely, to the class of graphs for which dense sequencings for an even h exist. This will allow us to generalize the algorithm based on the maximum matching for the case of arbitrary input data.
To the class of graphs for which there are dense sequencings, D , belong such h graphs that, for a given value of the width h , have sequencings in which at each place there are h vertices.
Theorem 1. If there is an exact algorithm A of polynomial complexity for some ~ ~ fixed sequencing width h , then there is a polynomial algorithm for any h h .
Proof. Suppose that there is some non-empty graph G with n vertices and some ~ fixed value h h . It is clear that the length of its optimal sequencing l is in the range from 1 (if n h and all vertices are isolated) to n (the graph is a chain) inclusive.
We construct a new graph G , which is obtained from the graph G by adding h h chains of some length l 1, n to it. We now construct the sequencing S of ~
~ the graph G for h h by Algorithm A . It is known that it will be optimal and can be obtained in polynomial time.
It is clear that if l l , then the length of S will also be l . On the one hand, it cannot be greater than l , since we have h h chains occupying h h positions ~ ~ on each of the l places, and vertices, belonging to the graph G can be placed on l places in case of h h . On the other hand, it cannot be smaller than l , since the chains can only be placed in a line and their length is l . Thus, if we remove from S all vertices belonging to the chains, then we obtain the optimal sequencing of S for the original problem in polynomial time, since the addition and removal of chains can be done in linear time.
Therefore, if we can find the length of chains l l , which is generally unknown, in polynomial time, then we can use algorithm A to find the optimal sequencing for ~ h h . This can be done through binary search.
Note that l l corresponds to the minimum value of l for which there will be h h vertices of the chains on all places in the resulting sequencing S obtained by ~ ~ the algorithm A for the graph G and h h . Indeed, for l l , the length S will coincide with l , since it is necessary to place the chains, and the vertices of the graph G can be placed on a smaller number of places. For l l , S will have places where there is less than h h vertices belonging to the chains, otherwise vertices of graph ~ G could be placed at a smaller number of places than l for h h .
We apply binary search to this problem. We choose some integer value of l0 a0 ,b0 1, n , which splits this interval approximately in half. We construct a graph G , for that value of l . By applying algorithm A we find the optimal sequencing S for h h . If there are h h vertices belonging to the chains on all the places of S , ~ ~ then we choose l1 a1,b1 1,l0 , and continue our search using this interval. If S has places where there are less than h h vertices of the chains, then we choose ~ l1 a1, b1 l0 1, n and similarly continue the search. The algorithm convergence follows from the convergence of binary search for monotonic functions. The search requires logarithmic time, the check can be performed in linear time, and therefore we find the l l in polynomial time.
Since all the steps of the described algorithm can be performed in polynomial time, their number is finite, algorithm A has polynomial complexity under the condition of theorem, and thus described algorithm is exact and has polynomial complexity for any ~ h h . ■
Theorem 2. If there is an exact algorithm A of polynomial complexity for some ~ fixed sequencing width h and graphs from Dh~ (for which exists dense sequencing of ~ ~ width h ), then there is a polynomial algorithm for an arbitrary graph for h h .
Proof. Suppose there is some non-empty graph G having n vertices. It is clear that the length of its optimal sequencing l is in the range from 1 (if n h and all vertices are isolated) to n (the graph is a chain) inclusive.
We construct a new graph G , which we obtain from the graph G by adding ~ ~ n m k h r isolated vertices to it, where r h ~ n , k being some factor. This h ~ factor is not less than 0 (if it is sufficient to add r h vertices to G to obtain dense sequencing, that is, for graphs for which there are optimal sequencings where there are r free positions). It reaches its greatest value in the case of a graph-chain when have n h 1 k h r k h h ~ n k n ~ .
~ ~ ~ ~ n n h h
Therefore n ~ k 0, n ~ . Now let us construct a sequencing S of G for h h using Algo h rithm A . It is known that, if there is a dense sequencing for G , it will be optimal and can be obtained in polynomial time.
~
It is clear that if m l h n , then S will be dense and its length will be l . On the one hand, it cannot be less than l since at least l places are required to place the vertices of graph G . On the other hand, it cannot be larger than l , since in the opti~ mal sequencing S for G there are l h n positions that can be occupied by isolated vertices, and algorithm A finds the optimal dense sequencing, if any. Then if we remove from S all the added isolated vertices, then we obtain the optimal sequencing of S for the original problem in polynomial time, since the addition and removal of isolated vertices can be done in linear time.
Similarly to Proof of Theorem 1, if we can find the number of isolated vertices ~ m l h n in polynomial time, or, what is the same, the value of the factor k for which the corresponding value is reached, then we can use algorithm A to find the ~ optimal sequencing for any graph for h h .
~ ~ Note that m l h n k h r corresponds to the minimum value of k , for ~ which the obtained sequencing S by algorithm A for the graph G and h h will be dense. Indeed, for smaller values of k , obtained sequencing won’t be dense, since not enough isolated vertices have been added. For larger values of k , we also obtain ~ dense sequencing, since we add the number of vertices that is a multiple of h .
We apply binary search to this problem. We choose some integer value of n k0 a0 ,b0 0, n h~ , which splits this interval approximately in half. We construct a graph G , for that value of k , then we find the sequencing of S using algorithm A ~ for h h . If S is dense, then we choose, similarly, k1 a1,b1 0, k0 , and continue search within this interval. If S has free positions, then we choose n k1 a1 , b1 k0 1, n h~ and similarly continue the search. The algorithm convergence follows from the convergence of binary search for monotonic functions. The search requires logarithmic time, the check can be performed in linear time, so we find the required m in polynomial time.
Since all the steps of the described algorithm can be performed in polynomial time, algorithm A has polynomial complexity under the condition of the theorem, thus we obtained an algorithm that is exact and has polynomial complexity for any graph G ~ and h h . ■
Corollary 1. If there is an exact algorithm A of polynomial complexity for some ~ fixed sequencing width h and graphs from Dh~ (for which exists dense sequencing of ~ ~ width h ), then there is a polynomial algorithm for arbitrary graph and for any h h .
Proof. It follows directly from Theorems 1 and 2. ■
This corollary allows us to generalize the algorithms obtained for the class of graphs for which there are dense sequencings, for the case of all graphs and smaller h . In particular, it allows us to apply algorithms obtained for even values of h to smaller odd ones. 5
This section will discuss the theorems that prove the feasibility of using and developing modifications of the algorithm based on maximal matching to graphs for which there are dense sequencings.
Further research will use the notion of "undirected graph clique" in the classical sense.
Definition. A clique is a subset of vertices of an undirected graph such that every
two distinct vertices in the clique are adjacent [
Theorem 1. From the existence of dense sequencing for some graph G for se~ ~ quencing width h h follows the existence of disjoint cliques of size h in reachability graph, covering all its vertices.
Proof. Suppose that we have a graph G for which the optimal sequencing S of ~ length l for h h is dense.
For any place i 1,l , since the vertices of S i are in the same place, by the definition of parallel sequencing, it follows that for any two vertices v1 S i, v2 Si there is no directed path neither from v1 to v2 , nor from v2 to v1 .
It is known that in the reachability graph G corresponding to graph G , two vertices v1 and v2 are joined by an edge only when there is no directed path neither from v1 to v2 nor from v2 to v1 . From the above, it follows that there are edges in G ~ between all pairs of vertices v1, v2 Si , and hence they form a clique of size h in it.
Since the above reasoning is true for all places in the sequencing S and all of ~ them has h vertices of graph G , and that sequencing contains all vertices of graph G , this leads to the conclusion of the statement. ■
The above statement is a necessary condition for the existence of dense sequencing for the graph. Note that in the case of h 2 , it is sufficient. For h 2 there are graphs for which there are cliques of size h covering all of its vertices, but dense sequencing doesn’t exist. These pairs form the maximum matching for the graph G , since each vertex belongs to only one pair (pairs contain vertices from one clique and cliques are disjoint), in each pair the vertices are adjacent (belong to the same clique), the pairs cover all vertices (pairs cover all vertices of the cliques, and cliques cover all vertices of the graph).
Consider now the algorithm based on the maximum matching, in which we will place as many pairs as possible on each place. If we apply that algorithm, where we use the resulting set of pairs as the maximum matching, then we can get the optimal sequencing by placing pairs from one clique in one place (vertices from one clique correspond to one place in S ).■
Note that the validity of the statement does not contradict the fact that for the reachability graph there may be maximal matchings, by using which we will not obtain the optimal sequencing. In fact, such graphs and corresponding matchings exist.
The above statements suggest that the algorithm based on maximal matching can, theoretically, find the optimal solution for problems where the sequencing width is even and the graphs have dense sequencing.
We also see that in its classical form, it is only approximate to this class of sequencing problems. 6
To experimentally determine the accuracy of an algorithm based on the maximum matching, it was implemented according to algorithm discussed in section 3. This algorithm is further referred to as the classical algorithm based on the maximum matching. Preference was given to vertices with smaller labels, rather than random choice. This will not affect the generality of the results since the randomness of the selection is implemented by the randomness of the graph generation and the labeling of their vertices. Also, to generalize the algorithm for the case of width h 2 step 5 of the algorithm is repeated until free positions are exhausted or until we can’t choose the next pair or single vertex.
During the experiment, only graphs were generated for which there are dense sequencings for even values of h . Their advantages include the fact that for such graphs the exact solution is known by generation. Transitive arrows are not removed from graphs because their presence does not affect the algorithm (they do not affect the reachability graph). The labeling of vertices in the graph is random to implement the randomness of the selection of pairs and vertices that do not belong to the pair.
In this and subsequent experiments, the accuracy of the algorithm based on the maximum matching was verified.
All of the experimental conditions are summarized in Table 1.
The results of evaluating the accuracy of the classical algorithm based on the maximum matching are shown in Table 2. These results and the following contain three parameters: the number of cases when the algorithm based on the maximum matching found the exact solution; the average deviation of the length of the obtained sequencing from the length of the optimal one, and the number of cases in which the resulting sequencing is twice as long as the optimal sequencing. In this one and following tables AMM stands for algorithm based on maximal matching.
Test results show that it has very low accuracy. The number of times it gives the
optimal solution decreases rapidly. The average deviation of the obtained solutions
also grows very fast and differs significantly from the one even for small graphs
(2140 vertices). In addition, there are cases where the sequencing obtained is twice as
long as the optimal one, which exceeds the maximum accuracy estimate in [
From this, we can conclude that as the number of vertices in the graph increases, the number of maximal matchings that give suboptimal solutions increases faster than the number of matchings that give optimal ones.
It is known that the resulting matching is strongly depends on the labels of vertices in the graph. One can assume that if we can relabel the vertices so that algorithm is more likely to find matchings that give optimal sequencing, then we can improve its results. It is also known that the vast majority of optimal solutions for graphs are satisfying the level principle. Therefore, it is natural to expect that if we relabel the vertices of the graph according to the level principle, then we can increase the likelihood of getting a matching, which gives an optimal solution. The results of the corresponding experiment are shown in Table 3.
From the experiment we observe that such relabeling slows down the decrease of accuracy of the algorithm and significantly slows the growth of the average deviation. There were no cases where sequencing that are twice as long as optimal were obtained, but the hypothetical possibility of their existence remains.
The sequencings that are twice as long as the optimal one are obtained, since the algorithm can leave empty positions because the open vertices are bound in pairs that cannot be placed. This behavior of the algorithm further aggravates the impact of the initial matching. An obvious way to reduce this effect is to allow splitting the pair if it cannot be placed in the current step, but at least one of its vertices is open. The resulting algorithm is later referred to as modified algorithm based on the maximum matching. The results of the accuracy evaluation of this algorithm are shown in Table 4.
Average deviation of AMM 1.008256 1.06869 1.166475 1.341709
From the results we see that such modification significantly improves the accuracy of the algorithm. The number of cases where the algorithm was accurate for graphs with 61-100 vertices increased almost 8.5 times, for other cases this number also increased significantly. The maximum average deviation from the previous experiment has halved and does not exceed 1.5. As expected there were no cases where the length of the resulting solution was twice the length of the exact one.
Note also that despite the smaller average deviation for the case of graphs with 1020 vertices compared to the previous experiment, the number of cases where the algorithm is accurate is smaller. Therefore, such modification does not always effectively comply with the level principle. Based on the previous results, it is hypothesized that if we apply the modified algorithm to previously relabeled vertices according to the level principle, we will increase accuracy even further. The results obtained are shown in Table 5.
We see that a significant improvement in performance of the algorithm is achieved. The number of cases where the algorithm was accurate for graphs with 61-100 vertices increased almost 10 times, compared to the classical algorithm. The average deviation for the first three cases is smaller than the average deviation for the first case for the classical algorithm and for the fourth case is comparable to it.
All this indicates the feasibility of introducing modifications to the algorithm. Therefore, the effect of the initial matching on the result obtained is much smaller. Note that the algorithm did not lose the ability to violate the level principle.
It can be assumed that if we apply, in addition to algorithms based on the level principle, such a modified algorithm, we can further improve the overall results, first of all due to cases in which to obtain optimal sequencing it is necessary to violate the level principle. To verify the latter assumption, an experiment was performed comparing the accuracy of a modified maximum matching algorithm with the best of results of lexicographic and double-label algorithms. The latter further along referred to as combined algorithm (CA). The same parameters were used as for the previous experiments.
The results consist of two parts: comparison of the algorithms with each other and comparison of the accuracy of the algorithms by the values of the objective function. A comparison of the algorithms with each other contains the number of test cases in which sequencing with a shorter length is obtained by the AMM; in which a sequencing with a shorter length is obtained by the combined algorithm, and in which sequencings of equal length are obtained by the algorithms. A comparison of the accuracy of the algorithms contains the number of cases when an exact solution was obtained by the algorithm based on the maximum matching; when an exact solution is obtained by the CA; the number of cases when one of the algorithms was accurate and the average deviation of the length of the solutions obtained by the algorithms from the length of the optimal one.
The results of the experiment are shown in Table 6. The results obtained confirm that, even with all modifications, the algorithm based on maximal matching is significantly inferior to the algorithms based on the level principle on all indicators. However, we see that the number of cases where the algorithm based on maximal matching finds shorter sequencing increases. In addition, in all these cases, these sequencings were accurate (this can be seen by summing up the number of AMM wins and the number of cases where the CA was accurate and comparing it to the number of cases when one of the algorithms is accurate).
On the other hand, the number of cases when the combined algorithm gave shorter but not accurate sequencing increases with the number of vertices. This may indicate that there is some "barrier" that prevents the combined algorithm from finding the optimal solutions, and the more vertices there are in the graph the more noticeable it is. This barrier may be a level principle, more precisely the necessity to violate it.
Let's return to the idea that the labeling of vertices in the graph strongly influences the result of the algorithm. The experiments with relabeling, according to the level principle, showed the effectiveness of this approach. It can be assumed that, if we randomly relabel the vertices, we will get a new matching and a new resultant sequencing, which may be shorter than the original one. The more times we repeat this procedure, the more likely it is that one of the resulting sequencings will be optimal.
To test this hypothesis, an experiment was conducted in which the algorithm based on the maximum matching was applied to the generated graph, and if it gave a suboptimal solution, then the vertices of the graph were randomly relabeled and the algorithm was applied again. The described steps are repeated until the algorithm finds the optimal sequencing or until the maximum number of repetitions is exhausted. We call this modification a random algorithm based on maximal matching. In graphs generation the same parameter values as in the previous experiments were used; the maximum number of repetitions for all cases is set to 10.
The results of checking the accuracy of a random classical algorithm based on the maximum matching are given in Table 7. These results contain the same columns as the previous experiments.
From the results of the experiment we can see that the hypothesis finds its confirmation. Thus, the number of cases where the algorithm was accurate increased significantly, in particular for graphs with 10-20 vertices got almost perfect accuracy, and for the case of graphs with 61-100 vertices the accuracy increased almost 5 times compared to the classical algorithm. The average deviation significantly decreased. There were no cases where the length of the resulting solution exceeds twice the length of the exact one, which may be due to the fact that the matchings that give rise to them are very rare.
A similar experiment was performed for the modified algorithm. The results obtained are summarized in Table 8.
In the experiment obtained results similar to the previous ones. The number of cases where the modified algorithm was accurate exceeds 91% for all graph sizes. For graphs with the number of vertices from 61 to 100 it is 12 times better than the classical algorithm. Similarly, the average deviation decreased.
The results obtained in the last experiment are comparable to those of the algorithms based on the level principle, which confirms the effectiveness of the proposed approach, especially considering that the chosen maximum number of repetitions was relatively small. Experiments with the relabeling of vertices, according to the level principle, are not listed, because it does not qualitatively affect the operation of the algorithm and therefore its accuracy.
Considering the improvement obtained, the last algorithm was compared with the combined algorithm. The results can be seen in Table 9. From the results we observe that the scores of the random modified algorithm are much higher than the scores of the modified one. The number of cases when it and the combined one give the sequencing of same length exceeds 90%. The number of cases where the sequencing obtained by algorithm has a smaller length is also much larger and increases rapidly with the number of vertices in the graph. In contrast to the previous comparison, there are cases, when the algorithm found shorter sequencings, but they were not optimal. The number of cases in which at least one of the algorithms is accurate for graphs of all sizes exceeds 98.6%, which significantly improves the results when using only algorithms based on the level principle. From this we can conclude that the resulting algorithm not only effectively comply with the level principle, but also violates it if necessary.
All previous results further confirm the effectiveness of random algorithms based on maximal matching, as well as the importance and prospectivity of the modifications of the classical algorithm as such that may violate the level principle.
The disadvantages of the random algorithm compared to the algorithm with relabeling, according to the level principle, include its non-determinism, which greatly complicates the analytical study of its properties.
The results obtained in this section have practically proved the feasibility of using the algorithm based on maximal matching and its modifications to the problems of optimal sequencing with graphs for which there are dense sequencings and even width.
The well-known class of discrete optimization problems (which are formulated as optimization problems on graphs), and requiring the development of new effective approximate polynomial algorithms, was investigated.
The theorems allowing to reduce the problem of optimal sequencing with arbitrary graph and sequencing width to the problem with graph, for which exists dense sequencing, and even width, have been proved. It was substantiated that to solve problems from this class it is suitable to apply an algorithm based on maximum matching.
For the algorithm based on maximum matching, several modifications have been developed. Experimental verification has established that they significantly increase its accuracy. In addition, the joint application of the proposed algorithms and known algorithms based on the level principle resulted in an accuracy exceeding 98%. 8