数理解析研究所講究録
1068 巻 1998 年 194-202

194

A REINFORCED SURROGATE CONSTRAINTS METHODFOR SEPARABLE NONLINEAR INTEGER PROGRAMMING

Yuji NAKAGAWA (仲川勇二)

Kansai University, Faculty of Informatics,

Abstract

This paper provides a new reinforcement to the surrogate constraints method forsolving separable nonlinear integer programmming problems with a few constraints.
The surrogate constraints method often has a duality gap,$\mathrm{i}.\mathrm{e}.$, fails to find an exact

solution to the original problem. A reinforcement proposed to fill the gap is to solvea sequence of target problems that enumerate all solutions hitting a target region witha single constraint.

1. INTRODUCTION
This paper presents a surrogate constraints method reinforced for solving a separable nonlinear

integer problem with multiple constraints. The surrogate constraints method solves a sequenceof surrogate problems, which have a single constraint, instead of a primal multi-constrained

problem. However, surrogate constraints method often has a duality gap,$\mathrm{i}.\mathrm{e}.$, fails to produce anexact optimal solution of the primal problem. The present reinforcement can fill the surrogate

duality gaps when there exist gaps.

Consider the following separable nonlinear integer programming problem.

195$[\mathrm{p}^{\mathrm{O}}].-$

Maximizesubject to$f( \mathrm{x})=\sum_{i- 1}^{n}f_{i}^{\mathrm{o}}(x)i$for $j=1,$$g_{j}^{\mathrm{O}}( \mathrm{x})=\sum_{1i-}^{n}g^{\mathrm{o}_{i}}j(X_{\mathrm{i}})\leq b_{j}^{\mathrm{O}}$$\ldots,m$,$\langle 1\rangle$

for $i=1,\ldots,n$ ,$x_{1}\in K_{l}^{\mathrm{O}}$where$\mathrm{x}=(x_{1}, x, \ldots, x_{n})2’ K_{l}^{\mathrm{O}}=\{1,2,\ldots, \mathrm{t}^{\mathrm{O}}\}$

for$f_{i}^{\mathrm{O}}(X_{i})\geq 0$$g_{ji}^{\mathrm{O}}(X_{i})\geq 0$

The problem$[\mathrm{P}^{\mathrm{O}}]$

for

and, without loss of generality, we assume that$x_{i}=1,\ldots,k_{i}^{\mathrm{O}}$$x_{i}=1,\ldots,k_{i}^{\mathrm{o}}$

,

,

(2)

$i=1,\ldots,n$$i=1,\ldots,n$ ,$j=1,\ldots,m$is called Multidimensional Nonlinear Knapsack Problem (MNKP) by Morinand Marsten(1976). As several special cases, the MNKP includes 1) Nonlinear Resource

Allocation Problem, named by Bretthauer and Shetty(1995), has differentiable convex objective
md constraint functions. 2) Resource Allocation Problem,$\mathrm{e}.\mathrm{g}$. Ibaraki and Katoh(1988), has theconvex objective function and the single constraint of the sum of variables.
Knapsack Problem presented by Nauss(1978) is the linearization of problem$3$)$\mathrm{M}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}$$[\mathrm{P}^{\mathrm{O}}]$

Choicewith a single

constraint.
Surrogate constraints are introduced into mathematical programming by Glover(1968).
Luenberger(1968) showed that any quasi-convex progrmmin problems can be solved exactly if$\mathrm{g}$the surrogate multipliers are correctly chosen. Karwan and Rardin(1984) give some empiricalevidences on the effectiveness of surrogate constraints in integer linear programIning. There areseveral algorithms for choosing an optimal surrogate multiplier vector to MNKP. Dyer(1980)

proposed two algorithms; one analogous to generalized linear

subgradient method. Nakagawa et$\mathrm{a}1.(19\Re)$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{g}\ovalbox{\tt\small REJECT} \mathrm{g}$and the other topresent Cutting-Off Polyhedron (COP) algorithm

that generates a sequence of multiplier vectors by cutting off polyhedrons and using a center ofthe polyhedron as a next multiplier vector.
Most of problems$[\mathrm{P}^{\mathrm{O}}]$

include surrogate duality gaps unfortunately. In other words, solving asurrogate problem with an optimal surrogate multiplier vectors, surrogate constraints method fails

196

to produce an exact solution of$[\mathrm{P}^{\mathrm{O}}]$

proposed to find an exact solution. A reinforced method, which we call Slicing algorithm, is$0\ldots \mathrm{f}[\mathrm{P}^{\mathrm{O}}]$in the feasible region of the optimal surrogate. Slicing algorithm solves a sequence of target problems that enumerate all solutions in a$\mathrm{p}\mathrm{r}\mathrm{o}\dot{\mathrm{b}}\mathrm{l}\mathrm{e}\mathrm{m}$slice of the feasible region. Sometimes we have a difficulty of solving target problems with too
wide a target solution space. The slicing method uses two practical techniques to reduce thedifficulty. One is to thin out the target solution space and the other is to narrow the feasible
reglon.

2. SURROGATE DUAL
The surrogate problem$[\mathrm{P}^{\mathrm{S}}(\mathrm{u})]$corresponding to$[\mathrm{P}^{\mathrm{S}}(\mathrm{u})]$: Maximize
subject toare written as follows:$[\mathrm{P}^{\mathrm{O}}]$$f^{\mathrm{o}}(\mathrm{x})$$\mathrm{u}\mathrm{g}^{\mathrm{O}\circ}(\mathrm{x})\leq \mathrm{u}\mathrm{b}$$\mathrm{x}\in \mathrm{K}^{\circ}$

,

,

where

$\mathrm{u}=(\mathcal{U}_{1}, u_{2}, \ldots, u_{m})\in R^{m}$,$g_{2}^{\mathrm{o}_{(\mathrm{x}),\ldots,g^{\mathrm{o}_{(_{\mathrm{X}})}}}}m)t$$\mathrm{g}^{\mathrm{o}}(\mathrm{x})=(g_{1}^{\mathrm{o}_{(_{\mathrm{X}}}}),$,$\mathrm{b}^{\mathrm{o}}=(b^{\circ}1’ b_{2}^{\mathrm{o}\ldots,\circ t},b_{m})$$\mathrm{K}^{\mathrm{O}}=\{\mathrm{x}:x_{\mathrm{i}}\in K_{:}^{\circ}for$$i=1,2,$$\ldots,$

$n\}$

.

The surrogate dual problem is defined by$[\mathrm{P}^{\mathrm{S}\mathrm{D}}]$

where$v^{\mathrm{o}\iota^{\mathrm{y}}\mathrm{r}_{[\cdot]}}$:$\min\{v^{\mathrm{O}\mathrm{P}\Gamma}[\mathrm{P}(\mathrm{S}\mathrm{u})]:\mathrm{u}\in \mathrm{U}\}$means the optimal objective function value of problem$\mathrm{U}=\{\mathrm{u}\in R^{m}$:$\sum_{\approx j}um1j=1,$$\mathrm{u}\geq 0\}$.

$[\cdot]$

and

197

The surrogate problem$\mathrm{p}\iota \mathfrak{v}_{\mathrm{P}^{\mathrm{e}\Psi}}l$$\mathrm{u}^{q}\in \mathrm{U}$: Let. For any$\mathrm{x}^{q}$$[\mathrm{P}^{\mathrm{S}}(\mathrm{u})]$has the following property.

be an optimal solution to problem$\mathrm{u}\in \mathrm{U}$such that$\mathrm{u}\mathrm{g}^{\mathrm{o}_{(\mathrm{X}^{q})}\circ}>\mathrm{u}\mathrm{b}$$\mathrm{P}^{\mathrm{s}}(\mathrm{u}^{q})$for a surrogate multiplier vector

it is held that,.

$v^{\mathrm{o}\mathrm{I}\eta}[\mathrm{p}\mathrm{S}(\mathrm{u})]\geq f(\mathrm{x})q$

This property means that the region

price of obtaining$\mathrm{x}^{q}$$\{\mathrm{u}$EU:$\mathrm{u}\mathrm{g}^{\mathrm{O}}(\mathrm{X}^{q})>\mathrm{u}\mathrm{b}^{\mathrm{o}}\}$

can be removed from$\mathrm{U}$as the. An algorithm presented by Dyer (1980) or Nakagawa et al. (1984) cangenerate a sequence of multiplier vectorsof Property 1. The multiplier vector$\mathrm{u}^{*}$$\mathrm{u}^{1},\mathrm{u}^{2},$$\ldots,\mathrm{u}^{q}$that covers the whole of$\mathrm{U}$in the meaningsuch that$\mathcal{V}^{\mathrm{O}\mathrm{I}^{\mathrm{y}}\mathrm{r}}[\mathrm{p}^{\mathrm{s}}(\mathrm{u}^{*})]=\min\{\mathcal{V}^{\mathrm{O}\mathrm{P}\Gamma}[\mathrm{p}^{\mathrm{s}}(\mathrm{u}^{1})], \mathcal{V}^{\mathrm{O}\mathrm{P}\Gamma}[\mathrm{P}^{\mathrm{S}}(\mathrm{u}^{2})], \ldots,\mathcal{V}^{\mathrm{O}}[\mathrm{P}(\mathrm{P}\mathrm{r}\mathrm{s}\mathrm{u}^{q})]\}$

is optimal to the$[\mathrm{P}^{\mathrm{S}\mathrm{D}}]$$\mathrm{s}\mathrm{u}\mathrm{I}\mathrm{T}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}$dual$[\mathrm{P}^{\mathrm{S}\mathrm{D}}]$. If an optimal solution,is feasible to the primal problem$[\mathrm{P}^{\mathrm{O}}]$, thenWhen the sequence provides no feasible solutions toduality gap. Then the value
value of$[\mathrm{P}^{\mathrm{O}}]$$f^{\mathrm{o}}(\mathrm{x}^{\mathrm{S}}\rangle \mathrm{D}$$\mathrm{x}^{\mathrm{S}\mathrm{D}}$$\mathrm{x}^{\mathrm{S}\mathrm{D}}$to the problem$[\mathrm{P}^{\mathrm{S}}(\mathrm{u}\rangle*],$is an exact optimal solution of$[\mathrm{P}^{\mathrm{O}}]$, it is said that there exists a$\mathrm{i}.\mathrm{e}$.

$[\mathrm{P}^{\mathrm{O}}]$.

$\mathrm{s}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\dot{\mathrm{e}}$provides an upper bound on the optimal objective function.

3. RESOLUTION OF SURROGATE DUALITY GAPIn order to fill the surrogate duality gap, consider$[\mathrm{P}^{\tau_{(f}\mathrm{T}},b^{\mathrm{T}})]$$\mathrm{t}\mathrm{h}\dot{\mathrm{e}}\mathrm{f}\mathrm{o}\mathrm{i}\mathrm{l}\mathrm{o}\mathrm{W}\mathrm{i}\mathrm{n}\dot{\mathrm{g}}$: Enumerate all solutions hitting$\mathrm{x}$a target$J^{\mathrm{o}}(\mathrm{x})\geq f^{\Gamma}$

subject to$\mathrm{u}^{*}\mathrm{g}^{\mathrm{o}}(\mathrm{X})\leq b^{\mathrm{T}}$$\mathrm{x}\in \mathrm{K}^{\mathrm{o}}$where$\mathrm{u}^{*}$

problem.

is an optimal multiplier vector to$[\mathrm{P}^{\mathrm{S}\mathrm{D}}]$,.

corresponding to a primal problem

et al. (1995) calls this problem target problem.

If$f^{\tau_{\leq \mathcal{V}}0}[\mathrm{P}^{\mathrm{o}_{]}}\mathrm{P}\Gamma$$[\mathrm{p}^{\mathrm{O}}]$. Miyaji, then a target problem

198$[\mathrm{P}^{\mathrm{T}\mathrm{T}}(f, \mathrm{u}^{*}\mathrm{b}\rangle]$

can enumerates exact optimal solutions tochosen from an inteIval such as
to$[\mathrm{P}^{\mathrm{O}}]$$f^{o}(\mathrm{X}^{\mathrm{N}\mathrm{a}})\mathrm{e}\mathrm{f}f^{\tau}\leq\leq f(\mathrm{O}\mathrm{S}\mathrm{D}\mathrm{x})$$[\mathrm{p}^{\mathrm{O}}]$. The target values, where$\mathrm{x}^{\mathrm{N}\mathrm{o}\mathrm{e}\mathrm{r}}$will beis a near optimal solution. The solutions hitting the target are called target solutions. MA without dominance testing

can solve exactly the target problem
to solve with decreasing value of$[\mathrm{P}^{\mathrm{T}}(f^{\mathrm{T}}, \theta \mathrm{b})]$$f^{T}$

Consider a sequence of problems. The problem$[\mathrm{P}^{\mathrm{T}}(f^{\mathrm{T}}, \mathrm{u}^{*}\mathrm{b})]$$[\mathrm{P}^{\mathrm{T}}(f^{\mathrm{T}}, \mathrm{u}^{*}\mathrm{b})]$

with

where

$f^{\mathrm{T}}=\varphi_{0},$$\varphi_{1},$$\ldots,$$\varphi_{\kappa}$$(t=0,1,2, \ldots, \kappa)$.

These target problems are solved by Slicing algorithm in the order of$[\mathrm{P}^{\mathrm{T}}(\varphi_{\kappa}, 1r\mathrm{b})]$becomes harderbecause of increasing number of target solutions.

$\varphi_{t}=\frac{(\kappa-t)f\mathrm{O}(_{\mathrm{X}^{\mathrm{S}\mathrm{D}}})-fJ<)(\mathrm{X})Near}{\kappa}$$[\mathrm{P}^{\mathrm{O}}]$$f^{T}$$[\mathrm{P}^{\mathrm{T}}(\varphi 0’ \mathrm{u}\mathrm{b}*)]$,...,, as shown in Figure 1. When Slicing algorithm finds out an optimal solution toout of target solutions, the algorithm stops. However, the problems become much harder

to solve with increasing problem size. The difficulties are divided into two cases. The first caseof difficulty is that there exist too many target solutions with the same objecuve function value.
The second case is that the feasible region satisfying the constraint is too wide.

In Slicing

algorithm, two techniques are used to decrease the difficulties. (ine technique is to thin out thetarget solutions. When the number of altemative items for a variable exceeds a threshold value, athinning out law in Slicing algorithm is practiced. The other technique against the difficulties is toslice off one piece after another of its feasible region by changing values of
noted that an optimal solution obtained byexact optimal to the primal problem

Consider a sequence of problems$[\mathrm{P}^{\mathrm{O}}]$. It should be

usin. these techniques may not be guaranteed to be$\mathrm{g}$.

$[\mathrm{P}^{\mathrm{T}}(\varphi_{k}, b)]\mathrm{T}$with$b^{\mathrm{T}}=\beta_{0},\rho_{1},\ldots,$$\beta_{t}=\frac{(_{\mathrm{V}-}t)\mathrm{u}^{*}\mathrm{g}^{\mathrm{o}}(_{\mathrm{X}}\mathrm{N}\mathrm{e}\mathrm{a}\mathrm{r})-f\mathrm{u}^{*}\mathrm{b}^{\mathrm{o}}}{v}$

Slicing algorithm tries to solve the problems
illustrates this technique.

$b^{\mathrm{T}}$$[\mathrm{P}^{\mathrm{T}}(\varphi_{k}, \beta l)]$$\beta_{\mathrm{v}}$where$(t=0,1,2, \ldots, v)$.

in the order of $t=0,1,$$\ldots,$$v$. Figure 2

199

Fig. 1

Fig. 2

4. EXAMPLE$\mathrm{S}\mathrm{l}\mathrm{i}_{\mathrm{C}\dot{\mathrm{m}}}\mathrm{g}$algorithm will be demonstrated on the following simple problem with three constraints.

200This problem has $m=3,$ $n=5,$functions
Table 1and$f_{1}^{\mathrm{O}}(x_{1})$for $i=1,$$k_{1}^{\mathrm{O}}=4$$5$$\ldots,$, and$\mathrm{b}^{\mathrm{o}}=(\mathfrak{B}4,188,191)\iota$. The values ofare as follows:$g_{ji}^{\mathrm{O}}(X_{i})$Example$-|$$\ovalbox{\tt\small REJECT}_{g_{\mathrm{O}}}^{g_{31}^{\mathrm{o}_{2}}}g_{3}^{\mathrm{o}}\ g33\mathrm{o}_{5}\mathrm{o}_{(k)8}3k4(k)1(((k)203445kk)151729361)41327512229655274634817693$.

$\mathrm{C}\mathrm{u}\mathrm{t}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}-\alpha \mathrm{f}$$\mathrm{u}^{1}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$Polyhedron (COP) algorithm presented by Nakagawa et. al 1984 is started with.

, as shown in Fig. 2. The surrogate subproblem isand$\mathrm{u}^{1}\mathrm{g}^{\mathrm{O}1}(\mathrm{x})\leq \mathrm{u}\mathrm{b}^{\mathrm{O}}$$=(1,3,4,1,4),$$\mathrm{u}\mathrm{g}^{\mathrm{O}}(\mathrm{x}^{1})>\mathrm{u}\mathrm{b}^{\mathrm{O}}$$\mathrm{x}\in \mathrm{K}^{\mathrm{O}}$$[\mathrm{P}^{\mathrm{s}}(\mathrm{u})]:1{\rm Max} f^{\mathrm{o}}(\mathrm{x})\mathrm{s}.\mathrm{t}$. The computer code based on MA produces an optimal solution$f^{\mathrm{O}}(\mathrm{X}^{1})=269.0$$\mathrm{x}^{1}$. We have the first cutting plane $-24u_{1}-3u_{2}>-4$ fromand $u=1-3u_{1}-u_{2}$ . COP algorithm generates $\mathrm{u}^{2}=(0.0536, 0.4881, 0.4583)$ as acenter of balance of a material points system that has an unit weight at all vertices. Similarly the$\mathrm{s}\mathrm{u}\mathrm{I}\mathrm{T}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}$$=$constraints method generates(0.0734, 0.1478, 0.7787),$-7u_{1}-17l\mathrm{q}>-8$$\mathrm{x}^{3}=(1,4,4,1,3),$and$f^{\mathrm{O}}(\mathrm{x}^{2})=269,$$f^{\mathrm{O}}(\mathrm{x}^{3})=268$. This plane cuts off the remaining region of

the optimal surrogate multiplier is$\mathrm{X}^{\mathrm{S}\mathrm{D}}=\mathrm{X}^{3}$$\mathrm{x}^{2_{=()}}4,3,4,1,1,$$f^{\mathrm{O}\mathrm{S}\mathrm{D}}(\mathrm{X})=268$$\mathrm{u}^{*}=\mathrm{u}^{3}$. However,$\mathrm{x}^{3}$$\mathrm{U}$$-13\mathcal{U}_{1^{-4011}}u_{2}>-,$$\mathrm{u}^{3}$, and the last cuaing plane

as shown in Fig. 3. Therefore, the optimal solution of surrogate dual problem isis infeasible to the second constraint$g_{2}^{\mathrm{o}\mathrm{O}}(\mathrm{x})\leq b_{2}$There exists a surrogate duality gap. In order to fill this surrogate gap, consider target problems$[\mathrm{P}^{\mathrm{T}}(f^{\mathrm{T}}, b^{\mathrm{T}})]$

of$b^{\mathrm{T}}=\mathrm{u}^{*}\mathrm{b}^{\mathrm{O}}=1\mathfrak{B}.7$$\mathrm{x}^{\mathrm{N}\mathrm{e}\mathrm{a}\mathrm{r}}=(1,4,4,1,2),$$f^{o}(\mathrm{x})\mathrm{N}\mathrm{e}\mathrm{a}\mathrm{r}=261$

and $f^{\mathrm{T}}=268,267,$$\ldots,$$261$ ,

where a near optimal solution

which obtained by a heuristic meffiod. The sequence of thetarget problems is solved by MA without doninance testing. The problems..,$[\mathrm{P}^{\mathrm{T}}$$[\mathrm{P}^{\mathrm{T}}$$[\mathrm{P}^{\mathrm{T}}$(268193.7) , .
$]$(262, 193.7) have no target soluUons that is feasible to the primal problem. The problem(261, 193.7)

$]$

$]$

provides a target solution$\mathrm{x}^{\mathrm{S}\mathrm{l}\mathrm{i}\mathrm{o}\mathrm{e}}=(1,4,4,1,2)$

satisfying all constraints of the

primal problem. The solution is the exact optimal solution to the primal problem.

201

References
Armstrong, R. D., D. S. Kung, P. Sinha and A. A. Zoltners,$\#\mathrm{A}$Computational$\mathrm{S}\mathrm{t}\mathrm{u}\Phi$of a Multiple-Choice

Knapsack Algorithm,’l ACM Trans. on Math. Software, 9 (1983), 184-198.

Dyer, M. E.,”Calculating Surrogate Constraints, Math. Programming, 19 (1980), 255-278.
$\mathfrak{n}$Dyer, M. E., N. Kayal and J. Walker,$\mathfrak{n}_{\mathrm{A}}$Branch and Bound Algorithm for Solving The Multiple-Choice Knapsack

Problem,’l J. Computational and Applied Math., 11 (1984), 231-249.

Glover, F.,
Ibaraki,,$’\uparrow \mathrm{S}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{o}\mathrm{e}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{s}^{\mathfrak{n}}$Oper. Res., 16 (1968) 741-749.

Approaches to Combinatorial Optimization,\dagger t Annals of Oper. Res., 10 (1987), 1-602.

$\mathrm{T}^{11},\mathrm{E}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{e}$Ibaraki, T. and N. Katoh, Resource Allocation Problems, MIT Press, Cambridge, Mass (1988).
KaIwan, M. H. and R L. Radn,’${}^{\mathrm{t}}\mathrm{S}\mathrm{u}\mathrm{n}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}$Dual Multiplier Search$\mathrm{P}\mathrm{I}\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{i}1\mathrm{I}\mathfrak{B}$in Integer PIogramming,1’ ()per.

Res. 32 (1984) 52-69.
Luenberger, D. G., BQuasi-convex programmingll, SIAM J. Applied Math., 16 (1968) 1090-1095.
MaIse, K and S. D. Roberts,$\mathrm{r}_{\mathrm{I}1}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}$a Portable FORTRAN Uniform (0,1) GeneIator,” Simulation, 41(1983), 135-139.

Malsten, R. E. and T. L.

$\mathrm{M}\mathrm{o}\mathrm{I}\mathrm{i}\mathrm{n}^{\mathrm{r}},\mathrm{A}\mathrm{H}\mathrm{y}\mathrm{b}\mathrm{I}\mathrm{i}\mathrm{d}$Approach to DisCIete Mathematical$\mathrm{P}\mathrm{I}\mathrm{o}\mathrm{g}\mathrm{l}\mathrm{a}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g},\mathfrak{n}$

Math.

202

Programming, 14 (1977), 21-40.
Miyaji, I., Y. Nakagawa and$\mathrm{K}\mathrm{O}\mathrm{h}\mathrm{n}\mathrm{o},$”$\mathrm{D}\infty \mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}$support system for the eomposition of the examination

problem,” European J. Oper. Res., 80(1995), 139-138.
Morin, T. L. and R. E. Marsten,-an&Bound Strategies for Dynamic PIogramming, Oper. Res., 24(1976),$n$$\mathrm{n}\mathrm{B}\mathrm{I}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{h}$611-627.
Nakagawa, Y. and K. Nakashima,

Heunistic Methoxl for DeteImining Optimal Reliability Allocation, IEEE$n$$\mathrm{w}_{\mathrm{A}}$Trans. Reliab., R-26 (1977), 156-161.

Nakagawa, Y., M. Hikita and H.

$\mathrm{K}\mathrm{a}\mathrm{m}\Phi^{n}$

Sunogate Constraints Algonthm for Reliability Optimizanon

Problems with Multiple Constraints,’\dagger IEEE Trans. Reliab., R-33 (1984) 301-305.

Nakagawa, Y.

$\mathfrak{n}_{\mathrm{A}}$$\mathrm{P}\mathrm{a}\mathrm{I}\mathrm{t}3,73$

New Method for Discrete Optimization(1990)$\mathrm{P}_{\mathrm{K})}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{S}^{\mathfrak{n}},\mathrm{E}\mathrm{l}\infty \mathrm{t}\mathrm{I}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{o}\mathrm{e}$99-106. Translated from Trans. of the Institute ofand$\mathrm{c}_{\mathrm{o}\mathrm{m}}\mathrm{m}\mathrm{u}\mathrm{n}\mathrm{i}(\ovalbox{\tt\small REJECT} \mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}$$\mathrm{E}\mathrm{l}\propto \mathrm{t}\mathrm{I}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{e}$,in Japan,

Information andCommunication Engineers, 73-A (1990), 550-556 (In Japanese).
Nakagawa, Y. , Easy
Nauss, R.

$\mathrm{M}$$\mathrm{C}$Programming, Asakurashoten (1996) (in Japanese).

, ttThe 0-1 Knapsack PIoblem with Multiple Choice Constraints,tt

European J. of Oper. Res., 2(1978) 125-131.
$\mathrm{O}\mathrm{h}\mathrm{t}_{\mathfrak{B}}\mathrm{g},$$\mathrm{H}$,Y. Nakagawa, A. Iwasaki, and H.

$\mathrm{N}\mathrm{a}\mathrm{I}\mathrm{i}\mathrm{h}\mathrm{i}\mathrm{S}\mathrm{a},$”$\mathrm{S}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{t}\mathrm{G}\varpi(y$Procedure for Solving a Nonlinear

Knapsack Class of Reliability Optimization Problems,\dagger t Math. Comput. Modeling, 22 (1995) 261-272.
Sinha, P. and A. Zoltners,$n_{\mathrm{T}\mathrm{h}\mathrm{e}}$Multiple-Choice Knapsack Problem,n$\mathrm{O}_{\mathrm{I}}\mathrm{a}\mathrm{e}\mathrm{r}$. Res., 27 (1978), 125-131.