数理解析研究所講究録
第 798 巻 1992 年 108-118

108

A New Approach for Solving Large-Scale Discrete Optimization

Problems
Yuji NAKAGAWA\dagger
仲川 勇二 \dag er\dagger Faculty of Engineering,
Okayama University of Science

ABSTRACT
A generalized optimization system with a discrete decision space is defined, andan optimization problem associated with the system is described. A new solution
method, which is called Modular Approach (MA), is presented to solve the optimization problem. This method extends the Morin-Marsten hybrid idea to solve troublesome problems for Dynamic Programming. The present method is also an extensionof branch-and-bound using breadth-first search. Computational experiences for largescale test problems of the multiple-choice knapsack show the great power of MA.

1. INTRODUCTION
An optimization problem that has a discrete space to be determined, is called a discrete optimization problem. The typical solution methods for the problem are Dynamic Programming (DP) and
Branch-and-Bound (B&B). However, basic ideas of the two methods are quite different.
B&B,
which solves an original problem by repeatedly dividing it into smaller problems, is the top-down
scheme. On the other hand, DP is the bottom-up scheme, which decomposes stages by turns,
enumerates partial solutions, and finally solves the primal problem.
The B&B method consists of the branching and the fathoming. The bounding divides problems
and the fathoming judges whether or not the generated subproblems should be added into a candidatelist. The branching includes the searching that selects a candidate from the candidate list. The early
B&B has only two fathoming tests of feasibility and bounding [Geoffrion, Marsten; 72].
Kohler and Steiglitz [74] introduced the dominance, which is the core of DP, into B&B in a generalized form. Ibaraki [77] discussed the importance of dominance in B&B. On the other hand, Morinand Marsten $[76, 77]$ introduced the bounding test, which is the core of B&B, into DP. They call their
method hybrid DP/B&B. The hybrid DP/B&B is practically the ame as B&B using the breadthfirst-search (FIFO policy). The relationship of DP and B&B was discussed by Ibaraki [87] in detail.
Ibaraki [87] is devoted to generalizing B&B and DP.
Nakagawa[90] proposed a new solution method called modular approach (MA) for discrete $opti_{IY1}i-$zation problems. This paper is a development of the paper [Nakagawa; 90]. MA is a bottom-up
scheme as well as DP. First, MA considers an optimization system corresponding to a given discrete
optimization problem. Next, MA executes the following items 1) and 2) recursively and solves the primal problem:
1) Apply fathoming tests to the current system and reduce the decision space, and
2) Integrate several modules into one module and reduce the number of modules in the current system.
MA is an extension of hybrid DP/B&B and is easily applicable to problems with a hierarchicalstructure that DP does not deal with very easily.
$T1_{1}e$$s$

A number of multiple-choice knapsack test problems with maximum 250,000 variables, which have109
no integer-dominated variables, were solved on a work-station (CPU R3000). The computational resultshows that a policy [CIM] of choosing modules to be integrated plays an important role. The policy[CIM] is an original one of MA, and does not be used in B&B or DP.
2.

$|\Lambda|$-tupleA cartesian product of a family$\{A_{i}\}_{i\in\Lambda}$

is written as,(1)$A_{\cross\Lambda}\equiv i\in\Lambda\cross A_{i}$where$\in N$$\Lambda=\{\lambda_{1}, \lambda_{2}, \}$(the set of natural numbers).

Let a direct sum of a family of mutually exclusive sets,$U_{+\Lambda}\equiv i\in\Lambda+U_{i}$A$|\Lambda|$$\{U_{i}\}_{i\in\Lambda}$

(2)

, be

.

(3)

-tuple, which is an element of cartesian product$A_{\cross\Lambda}$, is defined as(4)$a_{\Lambda}\equiv(a_{\lambda_{1}}, a_{\lambda}i\ldots, a_{\lambda_{N}})$For example, when $\Lambda=\{2,5,8\},$For two ordered tuples
and, thenfor any(1) if, then(2) iffor any, then(3) iffor any$a_{\Lambda}=(a_{2},a_{5},a_{8})$$a_{\Lambda}^{1}$$a_{\Lambda}^{2}$.

, it holds that,,$a_{i^{1}}=a_{i^{2}}$$i\in\Lambda$$a_{\Lambda}^{1}=a_{\Lambda}^{2}$$a_{i^{1}}\geq a_{j}^{2}$$i\in\Lambda$$a_{\Lambda}^{1}\geq a_{\Lambda}^{2}$$a_{i^{1}}>a_{i}^{2}$$i\in\Lambda$$a_{\Lambda}^{1}>a_{\Lambda}^{2}$.

3. Discrete Optin
System and Problem
Consider a systemthat consists ofunits (initial modules), where $I=\{1,2, \}$ E N.
Each module has been designated a number $i\in I$. Each module
alternatives, wherehas$K_{:}=\{1,2, \}$is a set of module alternatives. Its Cartesian product $X=K_{xI}$ is
N. The set
the initial decision space. The solutions $x\in X$ are alternatives for the system.
, thenThe system
is assumed to be under a constraint space. If a solution $x\in X$ isis a feasible solution. We consider a real value function $f;Xarrow R$ as a performance index for the system. Thus the discrete optimization system is written as the following four tuple.
$\dot{u}zation$$|I|$$[\Sigma]$$i\in I$$|K_{i}|$$K_{i}$$\in$$[\Sigma]$$S\subset N^{|I|}$$[\Sigma]$$x\in S$$x$$[\Sigma]=[I, X, S, f]$$[\Sigma]$

.

.

(5)

The purpose of this paper is to solve the following discrete optimization problem corresponding to(6)$[ \Pi]:\max_{x\in X}\{f(x):x\in S\subset N^{|I|}\}$

4. Modular System and Modular Problem
A modular system at a level $l\in\{O\}+L$ is defined as(7)$[\Sigma^{(l)}]=[(M^{\langle l)}, U^{(0}), (A^{(l)}, t^{(l)}), S, f]$

where
$L$

$M^{\langle l)}$$U^{(l)}$$U_{m}$$A^{(l)}$a set of system numbers; $L=\{1,2, \}$ $\in N$ ,,a set of module numbers composing the system
numbers;ofunit
a family of mutually excusive setsa set of unit numbers composing a module $m\in M^{(l)}$ ,,an alternative space of$[\Sigma^{(l)}]$$U^{\langle l)}=\{U_{n}\}_{m\in u^{(0}}$$[\Sigma^{(l)}];A^{(l)}=$$\cross$$m\in M^{(\mathfrak{h}}$$A_{m}^{(l)}$,110a set of alternatives for a module
mapping from the decision space$A_{m}^{(l)}$$t^{(l)}$at a system level ,to a partial decision space$m\in M^{\langle l)}$$A^{(l)}$$l$$X^{(l)}\subseteq X$,

A modular systemis the systemitself. That is, $M^{(0)}=I$ , $U_{m}=\{m\}(m\in I)$ ,$A^{(0)}arrow X$
and:.
Let us now discuss a process that generates
from a systemat the previous level$(l-1)$ . We begin by applying fathoming tests to the system. Then suppose that, witbout lossof optimality, we can reduce a module alternative set $A_{m}^{(l-1)}(m\in M^{(l-1)})$ into a module alternative set. That is,$[\Sigma^{\langle 0)}]$$A_{m}^{(0)}=K_{m}(m\in I)$ ,$[\Sigma]$$\iota^{\langle 0)}$$[\Sigma^{(l-1)}]$$[\Sigma^{(l)}]$$[\Sigma^{(l-1)}]$$A_{m}^{(l)}$$A_{m}^{(l)}\subseteq A_{m}^{(l-1)}(m\in M^{\langle l-1)})$.

(8)$Next,usingap\circ licyfromamodulesetMl^{C_{1}I_{)}.M](thisp\circ 1icywi11bediscussedlater),MAchoosesasubsetC^{(l)}(|C|\geq 2)}The|C\langle l)|modu1eschosenareintegratedintoanewmodulewitham^{(l)}odu1e$

number $l+|I|$ . The integration of modules means to consider all combinations of alternatives ofas an alternative set
for the module $l+|I|$ . That is,modules$m\in C^{\langle l)}$$A\dagger_{+|I|}^{l)}$$A_{1+|I|}^{(l)}=\{1,2, \ldots, |A_{xC^{(\mathfrak{h}}}^{(l)}|\}$

Then$t1_{1}e$.

(9)decision space corresponding to module alternative set$X\dagger_{+|I|}^{l)}=m\in C^{(\mathfrak{h}}\cross X_{m}^{(t)}$$A_{l+|I|}$

is

.

(10)

The decision variables for the alternative set
respectively. Let a bijection mapping from

$Al_{+|I|}^{l)}$$A_{l+|I|}^{(l)}$$t_{l+|I|}:A\iota_{+|I|}^{l)}arrow X\int_{+|I|}^{l)}$toand the decision space
be defined as$xl_{+|I|}^{l)}$are$a_{l+|I|}$and$x_{l+|I|}$,$X\int_{+|I|}^{l)}$

.

(11)

A set of units composing a module $l+|I|$ is$+$$U_{l+|I|}=$$U_{m}$.

(12)$m\in C^{(\phi}$

A module set
composing a system
adding the new module $l+|I|$ ; that is,$M^{(1)}$$[\Sigma^{(l)}]$$M^{(l)}=M^{(l-1)}-C^{(l)}+\{l+|I|\}$is obtained by removing modules $m\in C^{(l)}$ from.

$M^{(\iota-1)}$

and

(13)

Let
$\iota^{(l)}=$$\cross$$t_{m}$,(14)$m\in Al^{\mathfrak{h}}$then$\iota^{(l)}$is the mapping from$A^{(l)}=A_{xM^{()}}^{(l)}$$|I|=|M^{(0)}|>|M^{\langle 1)}|>$$\sum U_{m}=I$$(l\in L)$

to$X^{(1)}$$>|M^{\langle|L|)}|=1$. We have the relations

.

(15)

.

(16)

$m\in M^{()}$

is assumed to be theat a level . A modular system
Then we have a modular system
last system having only one module $|L|+|I|$ ; i.e., $M^{(|L|)}=\{|L|+|I|\}$ , $U_{|L|+|I|}=I$
is corresponding to the following modular problem:
Each of modular systems$[\Sigma^{(l)}]$$l$$[\Sigma^{(|L|)}]$.

$[\Sigma^{(l)}](l\in L)$$[ \Pi^{(l)}]:\max\{f(x):a_{M0}\in A^{(1)},$$x=t^{(l)}(a_{M^{(\mathfrak{h}}}),$$x\in S\}$

.

(17)

Obviously, this problem is equivalent to [II]. As a special case, if we never use the fathoming; that is,
if Eq. (8) is$A_{m}^{(l)}=A_{m}^{(l-1)}$

at any level
relation$l\in L$(18)$(m\in M^{\langle l)})$, then an alternative set$|A\{\mathfrak{t}_{|+|I|}^{L|)}|=|X|$.

$A\{\}_{|+|I|}^{L|)}$obtained from Eq. (9) at the last level $l=|L|$ has the

(19)

111
That is, we have all possible solutions of the system$[\Sigma]$.

5. FathominThis section discusses three types of fathoming. The fathoming is used for reducing a decision$(l\in L)$ .
spaceof a system
As a result of a fathoming test, if we can judge that the optimalvalue (the objective function value of an optimal solution) of
does not change even if a subset
is removed from an alternative setof a module $m\in M^{(l)}$ , then the subset
has fathomed and canbe removed from further consideration. We say that the set
is inactive and the remaining set$g$$A^{(l)}$$[\Sigma^{(l)}]$$[\Sigma^{(l)}]$$A_{m}^{1}$$A_{m}^{1}$$A_{m}$$A_{m}^{1}$is active.
Let a problem [ $\Pi^{(l)}:a_{m}\in A1d$ be the problem
added a constraint
problem [ $\Pi^{(l)}:a_{m}\in A1d$ is a subproblem of, it holds that
$A_{m}-A_{m}^{1}$$[\Pi^{(l)}]$$a_{m}\in A_{m}^{1}\subseteq A_{m}$. Since a$[\Pi^{(l)}]$$v^{OPT}[\Pi^{(l)};a_{m}\in A1r\leq v^{OPT}[\Pi^{(l)}]$$wherev^{OPT}|d^{istheop_{1}tima1}prob1em[\Pi;a_{m}\in Ad\cdot$

1)

value of

$a$

,

(20)

problem$[\cdot]$. Three tests of fathoming is considered for the sub-Feasibility test: If the result of this test shows that the subproblem has no feasible solutions, thenthe alternative set
is inactive.
Dominance test: If there exists a set
such tbat$A_{m}^{1}$

2)$A_{m}^{2}\subseteq A_{m}$$v^{OPT}[\Pi^{(l)}:a_{m}\in A1u\leq v^{OPT}[\Pi^{(l)};a_{m}\in A2d$

,

(21)

then subproblem [ $\Pi^{(l)};a_{m}\in A1d$ is aid to be dominated. The alternative set
is judged to beinactive.
Bounding test: Suppose that a nonexact method has already found a feasible near-optimal solution $x^{NEAR}$ and its objective function value $f^{NEAR}$ . When we get an upper-bound of the subproblem
by some technique (in most cases, relaxation techniques are used), if$A_{m}^{1}$

$s$

3)

$[\Pi^{(l)};a_{m}\in A_{m}^{1}]$$v^{UB}[\Pi^{(l)}:a_{m}\in A1d\leq f^{NEAR}$

,

(22)

is upper-bound of a problem , the subproblem has no feasible solutions better thanis inactive.
After the fathoming test, we can remove an inactive alternative set
from an alternative set. Then alternative spaceis reduced.
of a module $m\in M^{(l)}$ of a systemof system
The fathoming mentioned above is only for the case of finding only one optimal solution. When
we want to find all of optimal solutions, at the dominance test, replace Eq. (21) with
where

$x^{NEAR}$$v^{UB}[\cdot]$$[\cdot]$. Hence the alternative set$A_{m}^{1}$$A_{m}^{1}$$[\Sigma^{(l)}]$$A^{(l)}$$A_{m}$$[\Sigma^{(1)}]$$v^{OPT}[\Pi^{(l)}:a_{m}\in A1d<v^{OPT}[\Pi^{(1)}:a_{m}\in A2d$

(23)

and at the bounding test replace Eq. (22) with$v^{UB}[\Pi^{(l)}:a_{m}\in A_{m}^{1}]<f^{NEAR}$

.

(24)

6. Procedure for Modular Approach
MA uses a policy$[Py]=[[Fm], [CIM]]$ ,

(25)

where
policy for determining what kinds of fathoming are applied for which modules.
policy for choosing modules to be integrated.
We can subdivide the policy [Fm] as follows:$[Fm]$$[CIM]$$[Fm]=$[ $[CFM]$ , [NEAR], $[FT]$ ]

(26)

where
policy for determining which modules will be put under the fathoming tests.
[NEAR] near-optimal solution $x^{NEAR}$ and its objective function value (near-optimal value) $f^{NEAR}$ .
$[FT]$
policy that is how to use what kind of fathoming tests.
$[CFM]$

112
Suppose that we have prepared two functions Fathom and ChoiceIM to execute tbe policies
and $[CIM]$ , respectively. Fig. 1 shows a procedure of MA by a pseudo code considering abstraction of data structure. An arrowmeans multiple outputs of function. For example,$\{A, B\}\Leftarrow func(C, D)$ means that the function func
has two input data
and , and returns
two data A and B. The functions in Fig. 1 are as follows:
by using policy $[Fm]$ . Then, if possible, findFathom executes fathoming tests to Systema better near-optimal solution. The function returns a reduced decision space
and a nearoptimal solution.
ChoiceIM chooses modules to be integrated from a module set
by using a policy $[CIM]$ . The
return of this function is a setof selected modules.
Integrate integrates the modules
into one module $l+|I|$ so as to obtain a new modular. This function returns the new system.
systemFindOptimalSolution finds an optimal solution of a systemhaving only one module. The
return is an optimal solution OPT
$()$

$()$

$[Fm]$$\Leftarrow$

$D$

$C$

$()$

$[\Sigma^{(1-1)}]$$()$$A_{xM^{larrow)}’}^{(l)}$$M^{\langle l)}$$()$$C^{(l)}$$m\in C^{\{1)}$$()$$[\Sigma^{(l)}]$$[\Sigma^{(|L|)}]$

$()$

$x$

7. Policies of MA
policyWhen MA is applied to practical problems, the performance of MA greatly depends on$[Py]$ . Here we discuss some examples of the policy $[Py]=[[Fm], [CIM]]$ .
Policy $[Fm]$ can be divided into three policies $[CFM]$ , [NEAR], and $[FT]$ . As for Policy $[CFM]$ , itshould be adopted to apply fathoming tests to all modules at the first level $l=1$ . At $l>1$ , the following policies are considered: Choose a module generated most recently by the integration or having thegreatest number of alternatives. Furthermore, we can consider the policy that all modules or themodules having alternatives more tban a certain number are fathomed at every certain number of levels. The policy [CFM] used by B&B and DP
is the rigid one that applies fathoming tests only to the most recently generated module.
If there exists some efficient bounding technique which quickly calculates good upper bounds, agood near-optimal value $f^{NEAR}$ is very useful in $reducin\S$ alternative spaces. However, if it does notexist, then a good $f^{NEAR}$ is of no practical use. A good EAR and agood bounding work as one body.
The general bounding technique uses the relaxation of integer restriction of problems. However, someproblems are solved effectively by using approximate equations [Nakagawa et al. 78].
The number of modules in a system can be reduced by integration. Generally the proper policy$[CIM]$ for choosing integrated modules is to choose two modules having the fewest number$(m\in M^{(1)})$
at every level is asof alternatives [Nakagawa et al. 78]. Since it is desirable that.
small as possible. However, this is not always true. In section 9, we will see an evidance against
Now let us consider relations between MA, B&B, and DP. We classify B&B into
1) earlyB&B: The early B&B which does not use the dominance in the fathoming,
2) B&B: B&B using the dominance.
DP is classified as follows:
1) pureDP: DP that does not use the bounding,2) hybridDP/B&B: DP using the bounding.
Then Fig. 2 illustrates the relationship with MA.
$t1_{1}e$$f$$|A_{m}|$$\sum_{m\in M^{(\mathfrak{h}}}|A_{m}|$$t1_{1}is$

MA includes hybridDP/B&B as its special case. That is, if Policy $[CFM]$ is a policy to choose amodule that is generated most recently (i.e., has the largest module number)and Policy $[CIM]$ is tochoose two modules having the largest module number, then MA is essentially the same as
hybridDP/B&B.
8. Example
In this section, MA is illustrated by a simple example. Consider a series-parallel reliability systemhaving five units as shown Fig. 3, and each unit has four alternatives. Table 1 shows the reliability
and cost of alternatives. The allowable maximum cost is $b=60$ .
A discrete optimization system can be written as$[\Sigma]=[I, X, S, f]$

,

(27)

113
wltere$I=\{1,2,3,4,5\}$X$K_{i}=$$=i\in I\cross K_{i},${1,2,3,4}$(i\in I)$$S=\{x\in X:g(x)=\sum_{i\in I}g_{i}(x_{i})\leq b\}$$f(x)=\{1-(1-r_{1}(x_{1})r_{2}(x_{2}))(1-r_{3}(x_{3}))\}r_{4}(x_{4})r_{5}(x_{S})$The problem to be solved is to find a combination of alternatives that achieves the maximum system reliability within the allowable cost ; i.e., to find an exact solution of optimization problem.
corresponding to system
Table 2 shows the input
for the function ModularApproach . Policy $[Py]$ is$[CFM]=$ to apply the fatboming tests to all modules at every level,[NEAR] $=[f^{NEAR}, x^{NEAR}]=$ [0.9349, (1,3,1,3,4)],$[FT]$(this policy will be explained later by an example),$[CIM]$
to integrate modules having the fewest alternatives by turns by taking
functionform of $f(x)$ into consideration.
At level $l=1$ , the function Fathom reduces the alternative space by using the following fathoming tests:
1) Dominance: An alternative $a_{1}=2(g_{1}(2)=5.8, r_{1}(2)=0.91)$ is dominated by an alternative$a_{1}=1(g_{1}(1)=5.7, r_{1}(1)=0.95)$ . The alternative $a_{1}=2$ is inactive.
2) Feasibility: Even if all modules besides a module under the fathoming test use alternatives of theminimum cost, we have$b$$[\Pi]$$[\Sigma]$$[\Sigma^{(0)}]$

$()$

$=$

$t1_{1}e$

$=$

$()$

$g(1,1,1,4,1)=73>b=60$ .
is judged to be inactive.
The alternative
Bounding: Even if all modules besides a module under the fathoming test use alternatives of the
maximum reliability,$a_{4}=4$3)$f(4,4,4,1,4)=0.6923<f^{NEAR}=0.9349$$f(4,4,4,2,4)=0.8407<f^{NEAR}$$f(4,4,4,3,1)=0.8536<f^{NEAR}$$f(4,4,4,3,2)=0.9303<f^{NEAR}$ .

The alternatives $x_{3}=1,2$ and $x_{4}=1,2$ are inactive.
First ChoiceIM chooses modules 4 and 5 as modules to be integrated by taking the form of reliability function $f(x)$ into consideration. Function Integrate integrates modules 4 and 5 into module 6
and returns a modular system. These results is shown in Table 3(a).
After level $l=2$ , the procedures mentioned above are repeated and lastly an optimal solution $a_{9}=2$$(x^{OPT}=(1,2,2,3,4), f^{OPT}=0.9390)$ is yielded. The progress are shown in Table 3(b), (c), (d). The
integrating process of modules is illustrated in Fig. 4.
$()$

$()$

$[\Sigma^{(1)}]$

9. Computational Results
The purpose of this computational experience is to show the power of policy CIM, which is a distinctive characteristic of MA. The MA algorithm for the multiple choice knapsack problem was inrplemented through a code written in language and tested on a UNIX workstation (SONY NEWS-3260;
CPU R3000). The computer code treats all floating-point calculations in double precision.
classes and $|K_{i}|0- 1$ variables for each class is
The multiple-choice knapsack problem withwritten$C$$|I|$$[MCK]$ ;$\max\sum_{1\in I}\sum_{k\in K}c_{k}\xi_{u}$

114
$s.t$

.

$\sum_{i\in I}\sum_{k\in K}a_{tk}\xi_{k}\leq b$$\sum_{k=1}^{K}\xi_{k}=1(i\in I)$$\xi_{k}\geq 0$, integer $(k\in K_{i}, i\in I)$ .

where $I=\{1,2, \}$ $\in N,$ $K_{i}=\{1,2, \}$ N.
The MA algorithm treat a multiple-choice knapsack problem as an equivalent nonlinear knapsackvariables andalternatives for each variables:
problem. The nonlinear knapsack problem with
$\in$

$s$

$|I|$

$[NK]$:$|K_{i}|$$\max\sum_{i\in I}f_{i}(x_{i})$$s.t. \sum_{1\in I}g_{i}(x_{i})\leq b$$x_{i}\in K_{i}(i\in I)$.

$wheref_{i}(k)=[MCK],sincec_{\theta}g(k)=a(k\in thes^{i}o1ution^{\iota k}space\circ f[MCK]and[NI\langle]areK_{1},i\in I).Theprob1em_{2and\prod_{i\in I}^{much}|K|(=2^{\Sigma}),respec-}4_{\epsilon^{|K_{i}|}e^{\log_{2}|K|}}^{NK]sm_{j}a11erso1uti\circ nspacethan}has$tively.
The discrete optimization system corresponding to [NK] can be written as$[\Sigma]=[I, X, S, f]$

,

$(*)$

where

X

$= \prod_{i\in I}K_{i}$,$S=\{x\in X:g(x)=\sum_{i\in I}g_{i}(X_{1}\cdot)\leq b\}$$f( x)=\sum_{j\in I}f_{i}(x_{i})$.

Two types of Multiple-Choice Knapsack test problems were randomly generated by an uniform ran$c_{k}(i\in I$ ,dom number generater [Marse and Roberts 83]. Type 1 problems has integer coefficients$k\in K_{1})$ and$a_{k},$$1\leq c_{i,k+1}-c_{tk}\leq 8$$1\leq a_{l,k+1}-a_{k}\leq 8$

for any$k,$$k+1\in K_{i}(i\in I)$, and$b= \sum_{:\in I}\frac{(a:1+a_{||K|})}{2}$This test problems are the most difficult problems in the paper [Sinha and Zoltners 79]. Type 2 test
problems has real (double precision) coefficients$0.0\leq c_{i,k+1}-c_{k}\leq 1.0$

$0.0<a_{i,k+1}-a_{k}\leq 1.0$

for any$k,$$k+1\in K_{i}(i\in I)$

, and

115

$b= \sum_{i\in I}\frac{(a_{i1}+a_{j|K|})}{2}$The coefficients of test problems of both of types 1 and 2 are treated as double precision real numbersin the present computer code.
The computer code of MA used the following policies:$[CFM]$At the beginning and when a near-optimal (the current best) solution is renewed, allmodules are put under fathoming tests. Otherwise, a generated new module is fathomed.
[NEAR] Initial near-optimal solutions are generated by a modification of the N-N method [Nakagawa, Nakashima 77]. A near-optimal solution is renewed by a better solution foundduring bounding tests.
$[FT]$
Upper bounds of subproblems are obtained by using the Sinha-Zoltners bound [Sinba,
Zoltners 79] (This bound should be investigated in detail, since the bound hardly seems
to be much better than the LP bound)$[CIM]$: Choose two modules having the fewest alternatives,: Choose a module having the fewest alterntives and a module having the most alternatives,: Choose two modules having the most alternatives,: Choose two modules having the maximum mudule number(Note that a module generated the most recently by an integration has the maximum
$A$

$B$

$C$

$D$

module number).
as CIM is essentially the same as the hybrid DP/B&B
The computational code with the policyor the branch-and-bound using the breadth-first-search.
Table 4 shows the computational results for type 1 test problems, whose coefficients are all
integer. The times reported are in seconds and does not include the times for obtaining initial nearoptimal solutions. When we use the policy as CIM, the code can not solve some of 25 test problems
whose size is $|I|=100$ and $|K_{i}|=50$ . The code with th policy
solved all of 25 test problems whose
size is $|I|=2000$ and $|K_{i}|=50$ . However, the code can not solve some of $3000x50$ test problems. The
code with the policy A oror D. Between A and ,are clearly superior to the one with policy
there is no big difference in computational times. The code with A or
can solve all of 25 randomly
generated test problems whose size is $|I|=5000$ and $|K_{1}\cdot|=50$ . The memory space needed for keeping
the largest size of intermidiate modular problems depends on the maximum number of alternatives pera modular problem. As for the memory space, policy is clearly superior to policy A. The computation times by policy are scattered. For example, in the case of $|I|=5000$ and $|K_{i}|=50$ , times for 20
additional times of 68.2 $\pm 1.6$ seconds are usedout of 25 problems are less than 1.0 seconds, wherefor getting initial near-optimal solutions for MA (see Table 5).
Table 6 shows the computational result for type 2 test problems, whose coefficients are all real
numbers. The comparison of Tables 4 and 6 gives that problems with real coefficients is much moredifficult than ones with integer coefficients. Table 6 shows the big power of the policy CIM. The policy
is the best one for CIM and is very stable in both of the computation time and the required memory
space.
$D$

$C$

$D$

$C$

$B$

$B$

$B$

$B$

$B$

$t1_{1}e$$B$

10. Concluding Remarks

This paper presents Modular Approach in a generalized form as a new solution method fordiscrete optimization problems. The present method extends the hybridDP/B&B and is easily applicable to the problems having hierarchical structure that are difficult for Dynamic Programming and
Branch-and-Bound to apply without any special idea. Since the present approach is flexible, it willdevelop more efficient solution algorithms even for the problems that can be solved by Dynamic Programming or Branch-and-Bound. Computational experiments of the existing papers are done for problems with only integer coefficients and for less than 20 test problems per one size. Our computational
experience suggests that more than 20 test problems per one size should be solved since different problems of the same size has the quite different computational times. Test problems with real coefficientsshould be solved, since problems with integer coefficients are much easier than the ones with real coef-

ficients.

116
Acknowledgments
The author is grateful to Dr. Ronald L. Rardin, Professor of Purdue University, for his valuableadvices and discussions.
References
Armstrong R. D., D. S. Kung, P. Sinha and A. A. Zoltners : “A computational Study of a multiplechoice knapsack algorithm“, ACM Trans. on Math. Software, Vol. 9, pp. 184-198 (1983).
Dyer M. E., N. Kayal and J. Walker : “A branch and bound algorithm for solving the multiple-choiceknapsack problem“, J. Computational and Applied Math., Vol. 11, pp. 231-249 (1984).
Geoffrion A. M. and R. E. Marsten : “Integer programming algorithms: A framework and state of theart survey”, Manag. Sci., Vol. 18, No. 9, pp. 465-491 (May 1972).
Ibaraki T.: )The power of dominance relations in branch-and-bound algorithms”, J. Assoc. Comput.
Mach., Vol. 24, No. 2, pp. 264-279 (Apr. 1977).
Ibaraki T.: ”Enumerative approachs to combinatorial optimization“, Annals of Operations
Research,Vol. 10, No. 1,4, pp. (1987).
Kohler W.H. and K. Steiglitz : “Characterization and theoretical comparison of branch-and-boundalgorithm for permutation problems”, J. Assoc. Comput. Mach., Vol. 21, No. 1, pp. 140-156 (Jan.
1974).
Marse K. and S. D. Roberts : “Implementing a portable FORTRAN Uniform (0,1) generator“, SIMULATION, Vol. 41, pp. 135-139 (Oct. 1983). pp 135-139 (1983).
Marsten R. E. and T. L. Morin :“A hybrid approach to discrete mathematical programming”, Math.
program., Vol. 14, pp. 21-40 (1977).
Morin T. L. and R. E. Marsten : “Branch-and-bound strategies for dynamic programming“, Oper.
Res., Vol. 24, No. 4, pp. 611-627 (July-Aug. 1976).
Nakagawa Y. and K. Nakashima:“A heuristic method for determining optimal reliability allocation“,IEEE Trans. Reliab., Vol. R-26, No. 3, pp. 156-161 (Aug. 1977).
Nakagawa Y., K. Nakashima, and Y. Hattori :“Optimal reliability allocation by branch-and-boundtechnique”, IEEE Trans. Reliab., Vol. R-27, No. 1, pp. 31-38 (Apr. 1978).
Nakagawa Y. :“A new method for discrete optimization problems“, Electronics and Comunications inJapan, Part 3, Vol. 73, No. 11, pp. 99-106 (1990), translated from Trans. of the Institute of Electronics, Information and Communication Engineers, Vol. 73-A, No. 3, pp. 550-556 (March 1990)(In Japanese).
Parker R. G. and R. L. Rardin : “Discrete optimization”, Academic Press (1988).
Sinha P. and A. Zoltners : “The multiple-choice knapsack Problem”, Operations Res., Vol. 27, No. 3,

pp. 125-131 (1978).

1
2

45

FUNCTION ModularApproach()

INPUT System
BEGIN$[\Sigma^{(0}]$, Policy [Py| $-[[Fm], [CIM]]_{j}$$WKILBlarrow 0;|M^{(0}|>1$

DO
l $arrow l+1$ ;

6
7

{

89

$A_{x}^{(17}u^{(k\triangleleft}$’[NEAR}}$\triangleleft-$

Fathom(1,$[\Sigma^{(1-1}], [Fm])$ ;$1^{C_{\Sigma^{(\eta}}^{(0}Choim\ddagger(M,A_{l^{\underline{x}}}^{(\iota\gamma}[CI_{\nu}M_{\triangleleft}])_{;};}<_{\triangleleft-Inte^{c}g^{e}rate(C^{t_{\langle 0,}^{l-1)}}[\Sigma^{(\Psi’,}A_{-\mu}^{(0})}$ENDWHILE

10

II’$|A\}_{+|i|}^{0}|-0TRBN_{g\lambda R}x^{OPT}arrow x^{N},$$1112$$f^{\circ rr}arrow f^{NuR}$

13
14
15
16

BLSB

17
18

RETURN Optimal Solution;,$x^{orr}\triangleleft-F\dot{m}dOptmalSolution([\Sigma^{(0}\rceil)\cdot$$f^{OPT}arrow f(x^{\circ\eta,}\cdot$

ENDIF$x^{orr}$, Optral value.

$\int^{OPT_{1}}$END

Fig. 1 A Procedure of Modular Approach.

Fig.2 Relations between three methods (MA, B&B, and DP).

117$\dot{"}$$\overline{v\succ}$$\overline{v\succ}$$\underline{v}$$\underline{v}$$\vee|\theta$$\sim_{6}l$$\mathscr{Q}$$\mathscr{Q}\circ$\mbox{\boldmath $\mu$}コ$\succ\alpha\not\in$$.\overline{\succ 5}$$\bigvee_{\circ}$$\circ$$\vee\vee\hslash v$$\sim_{\theta}(\omega$$\omega$$\check{\infty}$

–

$v$

–

–

$n$

$n$

$\underline{v}$$\underline{v}$$\xi^{t}\prec\prime o_{\theta}$$\epsilon^{d}Q\dashv$$rightarrow$$\dot{N}$$\overline{\underline{\succ vv}}$$\overline{\underline{v\succ v}}$$\vee\alpha$$\vee(0$$\mathscr{Q}$$\underline{vm}$$\circ.\triangleright\alpha\alpha$$’ \circ\frac{r!}{\succ l\triangleleft}$$\bigvee_{\circ}$$\overline{\circ}$$\vee nv$$\vee\triangleleft v$$UJ\sim$$\omegarightarrow$$\overline{\frac{n}{\infty}}$$\frac{-\circ}{n}$$\frac{v}{\in^{\circ}\prime\alpha_{\prec}}$$\frac{v}{\xi\dashv..\circ n!}$$\vee\wedge Q$日$\sim w\triangleright$$U1$$\circ$$o^{\alpha}\sim n$$\underline{v}$$P^{(}o_{\triangleleft}$$vn$$\underline{\succ}$$\vee v^{Q}(8$1$\circ$$\vee\circ\infty Q$$\frac{\dot{m}\circ}{-}$$\triangleleft\ovalbox{\tt\small REJECT}$。
$:\exists\vee\succ$$v\dot{a}$$\bigvee_{\backslash }m\succ m$

科$3^{O}’\circ$$vmm$$a\underline{e^{v}}$$r^{rightarrow}\underline{=*}$$n_{t\theta}$$A$科$\dot{O}$

$v$

.

$bOq$
$\overline{5^{v}}$$\vee\S^{O}$$\dot{-\hslash}$

)
$v$
$nv$

$.=$

$\underline{\vee q}$$\infty v$$\triangleleft^{\epsilon;}$$\prec$!デ$\frac{b}{\dot{h}}0$$\dot{\triangleright}^{-}\omega_{\dashv}$$\underline{v}$$\xi^{\circ}d\prec$

$\underline{\vee\overline{\omega}m}$

り

$c$
$8$

$\dot{\omega b0v}$

旨$\frac{A\vee}{\geq}$$mB$$\frac{v}{\cdot\cdot\circ}$$Q^{\circ_{\}}$,$F^{v}\succ_{\dashv^{\supset}}Q$$\underline{\overline{o}}$$\omega$$\frac{\vee}{\alpha^{\omega}\Rightarrow\infty}$$q_{-}$$\circ$$\vee\alpha$$\mathring{o}^{8}\overline{\circ}$$\triangleleft\dot{t}$$\underline{v}$$\epsilon^{n}\circ\dashv$