تحقق گرافیکی از روش برنامه ریزی پویا برای حل مسائل ترکیبی NPNP سخت

In this paper, we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems with non-integer data without necessary transformations of the corresponding problem. We compare the proposed method with existing algorithms for these problems on small-size instances of the partition problem with n≤10n≤10 numbers. For almost all instances, the new algorithm considers on average substantially less “stages” than the dynamic programming algorithm

Dynamic programming is a general optimization technique developed by Bellman. It can be considered as a recursive optimization procedure which interprets the optimization problem as a multi-stage decision process. This means that the problem is decomposed into a number of stages. At each stage, a decision has to be made which has an impact on the decision to be made in later stages. By means of Bellman’s optimization principle [1], a recursive equation is set up which describes the optimal criterion value at a given stage in terms of the optimal criterion values of the previously considered stage. Bellman’s optimality principle can be briefly formulated as follows: Starting from any current stage, an optimal policy for the subsequent stages is independent of the policy adopted in the previous stages. In the case of a combinatorial problem, at some stage αα sets of a particular size αα are considered. To determine the optimal criterion value for a particular subset of size αα, one has to know the optimal values for all necessary subsets of size α−1α−1. If the problem includes nn elements, the number of subsets to be considered is equal to O(2n)O(2n). Therefore, dynamic programming usually results in an exponential complexity. However, if the problem considered is NPNP-hard in the ordinary sense, it is possible to derive pseudopolynomial algorithms. The application of dynamic programming requires special separability properties. In this paper, we give a graphical realization of the dynamic programming method which is based on a property originally given for the single machine total tardiness problem by Lazarev and Werner (see [2], Property B-1). This approach can be considered as a generalization of dynamic programming. The new approach often reduces the number of “states” to be considered in each stage. Moreover, in contrast to dynamic programming, it can also treat problems with non-integer data without necessary transformations of the corresponding problem. However, the complexity remains the same as for a problem with integer data in terms of the “states” to be considered. In the following, we consider the partition and knapsack problems for illustrating the graphical approach. Both these combinatorial optimization problems are NPNP-hard in the ordinary sense (see, e.g. [3], [4], [5] and [6]). Here, we consider the following formulations of these problems. Partition problem : Given is an ordered set B={b1,b2,…,bn}B={b1,b2,…,bn} of nn positive numbers with b1≥b2≥⋯≥bnb1≥b2≥⋯≥bn. We wish to determine a partition of the set BB into two subsets B1B1 and B2B2 such that equation(1) View the MathML source|∑bi∈B1bi−∑bi∈B2bi|→min, Turn MathJax on where B1∪B2=BB1∪B2=B and B1∩B2=⊘B1∩B2=⊘. One-dimensional knapsack problem : One wishes to fill a knapsack of capacity AA with items having the largest possible total utility. If any item can be put at most once into the knapsack, we get the binary or 0−10−1 knapsack problem. This problem can be written as the following integer linear programming problem: equation(2) View the MathML source{f(x)=∑i=1ncixi→max∑i=1naixi≤A;0<ci,0<ai≤A,i=1,2,…,n;∑i=1nai>A;xi∈{0,1},i=1,2,…,n. Turn MathJax on Here, cici gives the utility and aiai the required capacity of item i,i=1,2,…,ni,i=1,2,…,n. The variable xixi characterizes whether item ii is put into the knapsack or not. We note that problems (1) and (2) are equivalent if View the MathML sourceci=ai=bi for i=1,2,…,n and A=12∑j=1nbj. Turn MathJax on For the application of the graphical algorithm, the problem data may be arbitrary non-negative real numbers. This paper is organized as follows. In Section 2, we consider the partition problem. First we explain the concept of the graphical algorithm for this problem. Then we describe in Section 2.2 how the number of intervals (or points) to be considered by the graphical algorithm can be reduced. The algorithm is illustrated by an example in Section 2.3. Then we prove the optimality of the given algorithm and discuss some complexity aspects in Section 2.4. Computational results for small-size instances are given in Section 2.5. In Section 3, we consider the knapsack problem. In Section 3.1, a brief illustration of the application of dynamic programming to the knapsack problem is given. In Section 3.2, the graphical algorithm is applied to the knapsack problem. An illustrative example for the graphical algorithm is given in Section 3.3. Some complexity aspects are discussed in Section 3.4. Finally, we give some concluding remarks in Section 4.

The concept of the graphical approach is a natural generalization of the dynamic programming method. This algorithm can also treat instances with non-integer data without increasing the number of required operations (in terms of min-break or jump points to be considered). For small-size problems, it turned out to be superior to the standard algorithms in terms of the average and maximum complexity, i.e. the average and maximal number of “states” (break points for the partition problem and jump points for the knapsack problem) to be considered. Note that the complexity of the graphical algorithm is the same for the following instances of the partition problem with n=3:{1,3,2}n=3:{1,3,2}; {1,100,99}{1,100,99} and {10−6,1,1−10−6}{10−6,1,1−10−6}. In contrast, the complexity of the dynamic programming algorithm strongly differs for the above small instances. In particular, the third instance requires a scaling of the data since integer “states” are considered. However, this considerably increases the complexity. For further research, it will be interesting to compare the graphical algorithm with the existing dynamic programming-based algorithms on benchmark problems with larger size. In addition, a comparison with branch and bound algorithms is of interest, too. More precisely, one can compare the number of nodes of the branching tree with the number of points to be considered by the graphical algorithm.