ON THE USE OF ELEMENTS OF THE BRANCH AND BOUND METHOD IN DYNAMIC PROGRAMMING SCHEMES

E. I. GERMAN, I. P. MAKAROV

(Presented by the scientific and technical seminar of the Department of Automated Control Systems and the Control Laboratory)

At the present time, in connection with the rapid development of computing technology, various kinds of schemes for ordered partial enumeration of alternatives are becoming increasingly widespread among optimization methods. A broad area of their application consists of problems of determining the extremum of functions of a finite number of variables defined on discrete sets, for example, problems of discrete programming [1], extremal problems on graphs [2], discrete dynamic problems of resource allocation [3], etc.

A considerable number of problems of optimizing functions and functionals with continuous domains of definition of the variables do not admit an analytic solution. These include the broad class of problems of determining various kinds of optimal trajectories. When they are solved by numerical methods on computers, their finite-dimensional approximation is used, and the solution itself is carried out, as a rule, within one of the schemes of ordered enumeration [3, 4].

Among the most widespread schemes of ordered enumeration are the branch and bound method [1], the method of dynamic programming [3, 5], its modification—the sequential analysis of alternatives—and a number of others [6].

The substantial difference between the ideas on which these methods are based, the presence of certain advantages and disadvantages in each of them, the ambiguity in the construction of algorithms and computational schemes when implementing the methods for solving concrete problems, and the significant dependence of the efficiency of the algorithms on how fully the specific features of the problem being solved are taken into account—all this makes, in particular, attempts at the joint use of elements of different schemes within a single algorithm topical.

In the present paper one variant is proposed for using the ideas of the branch and bound method in solving one class of conditional finite-dimensional extremal problems with discrete domains of definition of the functions by the method of dynamic programming.

An example of the class of problems under consideration is the problem of determining the extremum of a nonlinear separable function

\[ f(\vec{x})=\sum_{j=1}^{N} f_j(x_j) \tag{1} \]

under the constraints

\[ x_j \in \Omega_j,\quad j=\overline{1,N}, \tag{2} \]

where \(\Omega_j\) are discrete finite sets.

Another example is provided by finite-dimensionally approximated problems of determining optimal trajectories of the following form: find the extremum

\[ f(\vec{x})=\sum_{j=1}^{N} f_j(x_j,x_{j+1}) \tag{3} \]

under constraints of the form (2).

Problems with objective functions of the form (3) admit a simple geometric interpretation. \(N\) hyperplanes are introduced into consideration, and to each admissible value \(x_j \in \Omega_j\) there corresponds one-to-one a point in the \(j\)-th hyperplane.

Without loss of generality, one may use one-dimensional hyperplanes—straight lines. Let us connect, in pairs by edges, the points of hyperplanes having neighboring indices. As the length of the edge connecting the points \(x_j \in \Omega_j\) and \(x_{j+1}\in\Omega_{j+1}\), we take the value of the function \(f_j(x_j,x_{j+1})\).

To a collection of points \(x_j^*\in\Omega_j,\ j=\overline{1,N}\), one chosen on each hyperplane, there may be assigned a path from the first to the \(N\)-th hyperplane, to which there may be put in correspondence the value of the function (3)

\[ f(\vec{x}^{\,*})=\sum_{j=1}^{N} f_j(x_j^*,x_{j+1}^*). \tag{4} \]

Then the problem of determining the extremum of the function (3) can be interpreted as the problem of determining an extremal path in the graph thus formed.

Let us note that problem (1)—(2) may be regarded as a particular case of problem (2)—(3). Therefore, in the subsequent description it suffices to proceed for problems of the form (2)—(3), assuming, for definiteness, that the minimum of (3) is sought.

Before turning to the description of the proposed modification of the dynamic programming scheme, let us briefly consider the standard scheme for solving problem (2)—(3) by the dynamic programming method.

The solution of problem (2)—(3) by the dynamic programming method is carried out by successively solving Bellman equations of the following form:

\[ l(x_{j+1})=\min_{x_j\in\Omega_j}\{l(x_j)+f_j(x_j,x_{j+1})\},\quad j=\overline{2,N-1}, \tag{5} \]

\[ l(x_2)=\min_{x_1\in\Omega_1} f_1(x_1,x_2). \tag{6} \]

The Bellman functions \(l(x_j)\), in terms of the geometric interpretation considered, correspond to the length of the shortest path from the first hyperplane to the vertex \(x_j\) of the \(j\)-th hyperplane.

Then the optimal value of the function (3) can be determined as

\[ \min_{\vec{x}} f(\vec{x})=\min_{x_N\in\Omega_N} l(x_N). \tag{7} \]

Solving the problem using equations (5)—(6) is carried out by successively computing the functions \(l(x_{j+1})\) for all \(x_{j+1}\in\Omega_{j+1}\) from the known values \(l(x_j)\) for \(x_j\in\Omega_j\).

The proposed modification of the standard scheme considered makes it possible to exclude from consideration unpromising values of the variables \(x_j\), thereby narrowing the domains \(\Omega_j\), which helps reduce the required number of computations when determining \(l(x_{j+1})\) from (5). In doing so, taking into account that \(l(x_{j+1})\) is computed for all \(x_{j+1}\), we obtain that the exclusion of one value \(x_j\) reduces the number of computations by \(|\Omega_{j+1}|\), where \(|\Omega_{j+1}|\) is the cardinality of the set \(\Omega_{j+1}\).

Let us consider in more detail the proposed procedure for narrowing the domains \(\Omega_j\). Suppose one of the values \(l(x_N)\) is known, in other words, the value of the function (3) on one of the paths between the first and the \(N\)-th hyperplanes. Then, if for an arbitrary value \(l(x_j)\) the relation

\[ l(x_j) \geq l(x_N), \tag{8} \]

holds, then the corresponding value \(x_j\) can be excluded from the set \(\Omega_j\) as unpromising. To justify this, we note that under any continuation of the path from this vertex of the \(j\)-th hyperplane to the \(N\)-th hyperplane, the value of the objective function can only increase compared with \(l(x_j)\), i.e., any path containing the given vertex \(x_j\) will yield a value of the objective function (3) no smaller than on the path already known to us.

Using the terminology of the branch-and-bound method, one may regard \(l(x_N)\) as the incumbent, i.e., the value of the objective function at the best of the solutions examined, and the quantities \(l(x_j)\) for all \(x_j \in \Omega_j\) and \(j = 1, \overline{N-1}\) as estimates, i.e., lower bounds of the objective function on the set of solutions. Then relation (8) is analogous to the rule adopted in the branch-and-bound method for excluding from consideration those vertices of the tree whose estimate is worse than the incumbent.

It is known that the branch-and-bound scheme makes it possible to obtain a solution with any a priori specified closeness to the optimum. Similarly, using instead of relation (8), for assessing promise, a relation of the form

\[ \frac{l(x_N) - l(x_j)}{l(x_N)} \cdot 100 \leq x, \tag{9} \]

where \(x\) is the a priori specified accuracy of the solution in percent, one may exclude from consideration those \(x_j\) that “promise” an insignificant, from the point of view of \(x\), improvement of the value (3).

Thus, in the proposed scheme, each value \(l(x_j)\) newly computed from (5) is compared with \(l(x_N)\) by (8) (or using (9)), and if the corresponding value \(x_j\) is recognized as unpromising, it is excluded from \(\Omega_j\).

The description of the modification under consideration of the dynamic programming scheme may be regarded as complete if, in addition, the method of obtaining and correcting \(l(x_N)\) is specified.

First of all, we note that in solving many practical problems, as \(l(x_N)\) one may take the value (3) for the best of the known solutions obtained from physical or other considerations.

Another method of obtaining \(l(x_N)\) is the use of auxiliary, comparatively simple heuristic algorithms that make it possible to obtain locally optimal solutions. For example, if the problem is the classical problem of determining the shortest route in a network, then as a first approximation for \(l(x_N)\) one may take the length of the route constructed using the following rule. From the set of arcs that make it possible to pass from a given vertex of layer \(j\) to layer \(j+1\), each time the arc with the smallest length is chosen.

The procedure for determining \(l(x_N)\), which may conventionally be called a probing procedure, need not necessarily precede the process of solving equations (5)—(6). Probing may be carried out starting from any stage in the solution of equations (5)—(6); in other words, the search for locally optimal paths to the \(N\)-th hyperplane may in principle be begun from any vertex of any hyperplane. Naturally, when probing is performed repeatedly, the smaller of the obtained values of \(l(x_N)\) is used in (8).

The effectiveness of the proposed solution scheme is determined by how substantially the regions \(\Omega_j\) can be narrowed. The latter, in turn, depends on how significant the scatter is in the values \(f_j(x_j, x_{j+1})\) for fixed \(j\) and different \(x_j \in \Omega_j\), \(x_{j+1} \in \Omega_{j+1}\). In terms of the geometric interpretation, this means that the greater the differences in the lengths of arcs between pairs of hyperplanes, the more likely it is that partial paths will occur (paths from the 1st to the \(j\)-th hyperplane, where \(j < N\)) whose length is no less than the length of a known path from the 1st to the \(N\)-th hyperplane.

The considerations presented make it possible to determine how expedient it is to use the proposed procedure for narrowing the regions \(\Omega_j\) in solving particular problems and, in particular, from which stage \(j\) one should expect relation (8) to hold for a sufficiently large number of values \(x_j\). In other words, when solving particular problems one should always weigh the effect of narrowing the regions \(\Omega_j\) against the costs of probing.

The described method for using elements of the branch-and-bound method in the standard dynamic-programming scheme was applied in solving problem [7].

References

1. A. A. Korbut, Yu. Yu. Finkelshtein. Discrete Programming. Moscow, Nauka, 1969.

2. S. Tsoi, S. M. Tsai. Applied Graph Theory. Alma-Ata, Nauka, 1971.

3. R. Bellman, S. Dreyfus. Applied Dynamic Programming Problems. Moscow, Nauka, 1965.

4. N. N. Moiseev. Numerical Methods in the Theory of Optimal Systems. Moscow, Nauka, 1971.

5. R. Bellman. Dynamic Programming. IL, 1960.

6. V. S. Mikhalevich. Sequential optimization algorithms and their applications. Kibernetika, 1965, No. 1, 2.

7. I. P. Makarov, V. G. Rotar. A model and algorithm for planning the processes of creating an ASU and increasing the capacity of a computing center. In: Cybernetics and the University, issue 5. Tomsk, TPI, 1972.