A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems

1. INTRODUCTION

Branch-and-Bound (B&B) method is one of the most general thchnique to solve combinatorial optimi­ zation problems; in particular, it is remarkable that B&B method is closely related to the prob­ lem solving methods used in Artificial Intelli­ gence.[3]

In this paper, we propose a parallelized computa­ tion scheme called Parallelized Depth-First Algo­ rithm (PDFA) for B&B method that works on multi­ processor systems. Next, we show that the space requirement of PDFA on p processing units is at most p times as much as that of the sequential B&B algorithm with the depth-first search func­ tion. And, we also show that the computation time of PDFA on p processing units can be reduced to less that 1/p that of the sequential B&B algo­ rithm using the depth-first search function.

2. DEFINITIONS AND NOTATIONS

The multiprocessor system on which PDFA is as­ sumed to be implemented consists of the follow­ ing components (see Fig. 1):

• (i) p Processing Units (PUs) with Private Momory Unit (PMU) each;

(ii) A shared Common Memory Unit (CMU). In this model, PMU#i is restricted to be accessible only by PU#i, for each i, i · 1, 2, , p. On the other hand, CMU is accessible by any PU. Moreover, we also assume:

• (i) Each PU computes independently of other PUs;
• (ii) The communication between PUs is carried out only through CMU.

PU: Processing Unit

PMU: Private Memory Unit

In the followings, let P 0 denote a minimization problem with n k-valued variables. The goal of the problem is to find out one of the optimum solutions of P and its objective value. Let I be the curreRt set of open subproblems gener­ ated by a B&B algorithm. For each subproblem P . in I, we define the functions cost, lb, h and ~ depth as follows:

• (i) Let cost(P.) be the optimal value of the objective tunction for P .·
• (ii) Since the actual value of cost(P . ) cannot be known before P. has been completely solved, we use lbtP.) as its lower bound under the assurnptioA that lb(P,) should be less than or equal to cost(~ . ), for all P in I. ~
• (iii) Wien some additional information on cost (P.) is available, we can construct a more po~erful estimation than lb. We denote it h(P.). Without loss of generality, we as­ suml h(P . ) + h(P .) if i + j. Function h is usualiy called heuristic function.

• (ix) Finally, let depth(P o) denote the number of variables whose vAlues are already as­ signed in P 0 o ~

There are several kind of search functions used in B&B method . One of the most popularly used search functions is the depth-first search func­ tion sD. It selects the subproblem Po that has the smallest h value among those with~the larg­ est depth in I.

3. PARALLELIZED DEPTH-FIRST ALGORITHM

In PDFA described below, following variables are stored in CMU for common use:

I: The set of open subproblems generated through PDFA;

Xopt: The currently best solution (a candidate of the optimal solution);

Copt: The cost of Xopt, i.e., cost(Xopt); act: The number of "active" PUs, where "active" means that the PU is prnressing a sub­ problem.

All accesses to any of these variables should be controlled under mutual exclution.

PDFA is described as follows:

Phase 1: Set I+ {P 0 }, Xopt + ~. and act+ 0.

Phase l: Do Procedure P in parallel on each PU. Algorithm terminates when no PU is active.

Procedure P is described as follows:

• Step 1: If I · ~ and act = 0 then halt. Otherwise, if I = ~ and act > 0 then repeat this step, else go to Step 2.
• Step l: Set act+ act+ 1, Po+ s (I), and I + I - {P 0}. ~ D .

~ Step 1: If P o is terminated then go to Step 5.

• Step i= If lb(Po) <Copt then decompose Po into k subpr6blems and add them to I. ~ Go to Step 6.

Step 2: If cost(Po) <Copt then set Xopt + P and Copt *- cost(P 0 ). i

Step ~: Set act + act - l~and go to Step 1.

In the followings, p-PDFA denotes PDFA with p PUs. It is obvious that 1-PDFA is identical to the sequential B&B algorithm using the depth­ first search function.

4. SOME PROPERTIES OF PDFA

In this section, we discuss the space- and time­ requirements of PDFA.

4.1 SPACE REQUIREMENT

Let M be the largest value of all III's obtained durin~ the computation of p-PDFA to solve P 0 .

Then, the following theorem holds.

According to Theorem 1. the memoty space needed to implement p-PDFA is only O(pxkxn). which is just p times that of the sequential B&B algo­ rithm using the depth-first search function. It should be also noted here that the space re­ quirement of the sequential B&B algorithm usin~ any other search functions such as the best­ bound. the breadth-first. or the heuristic are O(kn).

4.2 TIME REQUIREMENT

Let K be the number of subproblems processed by p-PDFi to solve P 0 · It is reasonable to employ K to estimate the time requirement of p-PDFA. ARd, let T be the computation time needed to solve Pn b~ p-PDFA. We assume that T satisfies T · c ~ K I p, for some constant c.P p p

One of the most significant results to be men­ tioned in this paper is:

T can be reduced to less than T 1 /p, if p is pfoperly selected.

The reason is briefly stated as follows:

• (i) Let C be the cost of the first feasible solut~on of P 0 found by p-PDFA. Then, it is obvious that as p increses, c converges to the optimal objective value of P 0 .
• (iii) But if ~increses too much, K will also increses, since p-PDFA may pr8cess unneces­ sary subproblems to find an optimal solu­ tion.
• (ii) The sooner a good feasible solution is found, the lesser K becomes. And accord­ ingly, T will beco~e less than T /p.

We name this reduction effect in the computation time of p-·PDFA compared to T 1 , Acceleration Effect.

5. EXPERIMENT

Simulation experiment of p-PDFA was performed for a model of randomly generated 0-1 combi­ natorial optimization problems.[!] The purpose of this experiment is to know how Acceleration Effect appears in PDFA. In this simulation, we assumed that every subproblem can be processed in uniform time, for simplicity.

The problems were generated as follows. First, we set:

• (i) cost(P 0 ) · 1.0 and 1b(P 0 ) - 0.0. And the followong values were randomly generated: (ii) Let Pj and Pk be two different sons of Pi.

Then, we set: cost(P .) .. J cost(P.) and ~ cost(Pk) · cost(P .) +a, where a is a non-~ negative random number taken from the exponential distribution, Aexp(ACl) with A · 0.2.

• (iii) Let Pj be a son of p .· Then, lb(P.) was ~ J taken from uniform random numbers which distribute between [lb(P.), lb(P.) + 2 X ~ ~ (cost(Pj) - lb(P.))/(n- depth(P.))]. ~ ~
• (iv) Let a be a parameter which denotes the accuracy of the heuristic function h. Then, h(P.) was taken from the normal distribution, N(cost(P.), ((n-depth(P.)) x cr) 2 ). Thus, a small~cr implies an ~ accurate h.

The results are summarized in Fig. 2, in which n · 30. Each point in this figure represents the average of 20 different test runs. And max (K*,(n + 1) x p) (shown by the dot-dash-line) denotes a theoretical lower bound of K · Where p K* is the number of subproblems whose lb values

are less than cost(P 0 ).

From this figure, we know:

• (i) K can be reduced to less than K 1 , if p is p~operly selected. Thus, Acceleration Effect appears.
• Acceleration Effect appears more drastical­ ly when pooer heuristics are used.

6. CONCLUTION

PDFA is an attractive parallel algorithm for multiprocessor systems because of its small space requirement and especially of Acceleration Effect. Acceleration Effect appears through the parallerized B&B algorithm using the depth-first or the heuristic search function.

A similar effect as Acceleration Effect was also observed in the experiments on the Cm* multi­ processor system, which solved integer programm­ ing problems by B&B method.[2]

ACKNOWLEDGEMENT

Authors would like to thank Prof. N. Honda of Nagoya University for his helpful suggestions and discussions.