数理解析研究所講究録
第 1829 巻 2013 年 163-177

163

一般化上界制約付き集合多重被覆問題に対する発見的解法
梅谷俊治 (大阪大学), 荒川正尚 (富士通株式会社), 柳浦睦憲 (名古屋大学)

概要

集合被覆問題とは，台集合とその部分集合の族および各部分集合のコストが与えられたとき，台集合の全ての要素を被覆するコスト最小の部分集合の組み合わせを求める問題である．
大規模な集合被覆問題に対して効率的な発見的解法が提案されている一方で，実際の応用事例
では個々の事業者に固有の追加制約をともなうため，現場では整数計画問題に対する汎用ソルバーを利用せざるを得ない場合が少なくない．本研究では，人員スケジューリング問題における職種毎の人数制限，配送計画における車種毎の台数制限，データの論理的解析におけるロバ
ストな解析など応用事例に頻繁に現れる追加制約に対応するため，多重制約と一般化上界制約を集合被覆問題に導入した一般化上界制約付き集合多重被覆問題に対して効率的な発見的解法
を提案する．

1

Introduction

The set covering problem (SCP) is one of representative combinatorial optimization problems.
We are given a ground set of $m$ elements $i\in M=\{1, \ldots, m\},$ subsets $S_{j}\subseteq M(|S_{j}|\geq 1)$ andcosts $c_{j}(>0)$ for $j\in N=\{1, \ldots, n\}$ . We say that $X\subseteq N$ is a cover of $M$ if $\bigcup_{j\in X}S_{j}=M$
holds. The goal of SCP is to find a minimum cost cover $X$ of $M$ . The SCP is formulated as a0-1 integer programming ( $IP$ ) problem as follows:
$n$

(SCP)

minimize$\sum c_{j}x_{j}$subject to$\sum_{j\in N}^{j\in N}a_{ij}x_{j}\geq 1,$$i\in M$(1),$x_{j}\in\{0,1\}, j\in N,$

where $a_{ij}=1$ if $i\in S_{j}$ holds and $a_{ij}=0$ otherwise, and $x_{j}=1$ if $j\in X$ holds and $x_{j}=0$
otherwise, respectively. That is, a column $a_{j}=(a_{1j}, \ldots, a_{mj})^{T}$ of matrix
represents thecorresponding subset
by $S_{j}=\{i\in M|a_{ij}=1\}$ , and the vector
also represents thecorresponding cover $X$ by $X=\{j\in N|x_{j}=1\}$ . For notational convenience, for each $i\in M,$
let $N_{i}=\{j\in N|a_{ij}=1\}$ be the index set of subsetsthat contain element$NP$
The SCP is known to be-hard in the strong sense, and there is no polynomial time approximation scheme (PTAS) unless $P=NP$ . However, the worst-case performance analysis does
not necessarily reflect the experimental performance in practice. The continuous development ofmathematical programming has much improved the performance of heuristic algorithms accompanied by advances in computational machinery [7, 21]. For example, Beasley [2] presented anumber of greedy algorithms based on Lagrangian relaxation (called the Lagrangian heuristics),
and Caprara et al. [5] introduced pricing techniques into a Lagrangian heuristic algorithm toreduce the size of instances. Several efficient heuristic algorithms based on Lagrangian heuristics
have been developed to solve very large-scale instances with up to 5000 constraints and 1,000,000$(a_{ij})$$x$$S_{j}$$S_{j}$$i.$

164
variables with deviation within about 1% from the optimum in a reasonable computing time
[5, 8, 9, 23].
The SCP is often referred in the hterature that it has many important applications, e.g., crewscheduling [5], vehicle routing [17], facihty location, and logical analysis of data [4]. However,
it is often difficult to formulate problems in real applications into the SCP, because they often
have additional side constraints in practice. Most practitioners accordingly formulate them into
general mixed integer programming (MIP) problem and apply general purpose solvers, which
are usually less efficient compared to solvers specially tailored to SCP.
In this paper, we consider an extension of SCP introducing (i) multicover and (ii) generalized
upper bound (GUB) constraints, which arise in many real apphcations of SCP, e.g., vehicle
routing [10], crew scheduling [19], staff scheduling [6, 18] and logical analysis of data [16].
The multicover constraint [20, 22] is a generalization of covering constraint, in which eachelement $i\in M$ must be covered at least(is the set of non-negative integers)
times. GUB constraint is defined as follows. We are given a partition
of $N$$( \forall h\neq h’, G_{h}\cap G_{h’}=\emptyset, \bigcup_{h=1}^{k}G_{h}=N)$. For each block $G_{h}\subseteq N(h\in K=\{1, \ldots , k\})$ , thenumber of selected subsets $S_{j}(j\in G_{h})$ is constrained to be at most $d_{h}(\leq|G_{h}|)$ . We call thisproblem the set multicover problem with GUB constraints (SMCP-GUB).
The SMCP-GUB is $NP$ -hard, and the (supposedly) simpler problem of judging the existenceof a feasible solution is $NP$-complete, since the satisfiability (SAT) problem can be reduced
to this problem. In real applications, we often encounter instances with no feasible solution,and it is necessary to find an acceptable solution that violates only a small number of lessimportant constraints. We accordingly consider the following formulation of SMCP-GUB thatallows violations of the multicover constraints and introduces a penalty function with a penalty
weight vector$b_{i}\in \mathbb{Z}_{+}$$z_{+}$$\{G_{1}, \ldots, G_{k}\}$$w=(w_{1}, \ldots, w_{m})\in \mathbb{R}_{+}^{m}.$(SMCP-GUB)

minimizesubject to$z(x)= \sum_{j\in N}c_{j}x_{j}+\sum_{i\in M}w_{i}y_{i}$$\sum a_{ij}x_{j}+y_{i}\geq b_{i},$$i\in M,$$\sum_{j\in G_{h}}^{j\in N}x_{j}\leq d_{h}, h\in K$,(2)$x_{j}\in\{0,1\}, j\in N,$$y_{i}\in\{0, \ldots, b_{i}\}, i\in M.$

For a given $x\in\{0,1\}^{n}$ , we can easily compute an optimal by $y_{i}= \max\{b_{i}-\sum_{j\in N}a_{ij}x_{j}, 0\}.$
We note that when $y^{*}=0$ holds for an optimal solutionof SMCP-GUB under thesoft multicover constraints,
is also optimal under the original (hard) multicover constraints$i\in
M$ . In this paper, we accordingly set $w_{i}= \sum_{j\in N}c_{j}+1$ for all$w_{i}>\sum_{j\inN}c_{j}$ifholds for all$y$$(x^{*}, y^{*})$$x^{*}$$i\in M.$

This generalization of SCP substantially extends the variety of its applications. However,
GUB constraints often make the pricing method less effective, because they prevent solutions
from containing highly evaluated variables together. To overcome this, we propose a heuristic algorithm to reduce the size of problem instances. In this algorithm, we introduce a new
evaluation scheme of variables taking account of GUB constraints. We also develop a 2-flipneighborhood local search algorithm. It features (i) an efficient implementation that reduces

165
the number of candidates in the neighborhood without sacrificing the solution quality, and (ii)an adaptive control of penalty weights to guide the search to visit better solutions. The latterfeature is adopted because when fixed large penalty weights are used, the search tends to stopat locally optimal solutions of low quality. This is because to reach from a good solution toa better one by a sequence of neighborhood operations, it is often unavoidable to temporarily
increase the values of some variables , and large penalty weights prevent the algorithm frommoving between such solutions. To guide the search to visit a wide variety of good solutions,
we also introduce an evolutionary approach called the path relinking method [15] that generates
new solutions by combining two or more solutions obtained by then.
Figure 1 illustrates the outline of the entire algorithm for SMCP-GUB. Our algorithm first$y_{i}$

solves a Lagrangian dual problem to obtain a Lagrangian multiplier vector and a lower boundby the subgradient method (Section 2), where it is applied only once in the entire algorithm. Then, our algorithm applies the following three procedures in this order: (i) the heuristic
reduction of problem sizes (Section 6), (ii) the path relinking method to generate initial solutions(Section 5), and (iii) the 2-ffip neighborhood local search algorithm with the adaptive control ofpenalty weights (Sections 3 and 4), where they are iteratively applied until a given time limit
has run out.
$\overline{u}$$z_{LR}(\overline{u})$図 1: The outline of the proposed algorithm for SMCP-GUB

2

Lagrangian Relaxation and Subgradient Method

For a given vector $u=(u_{1}, \ldots, u_{m})\in \mathbb{R}_{+}^{m}$ , called the Lagrangian multiplier vector, theLagrangian relaxation of SMCP-GUB is defined as follows:$(LR(u))$minimize$z_{LR}(u)$$=$$\sum_{j\in N}c_{j}x_{j}+\sum_{i\in M}w_{i}y_{i}+\sum_{i\in M}u_{i}(b_{i}-\sum_{j\in N}a_{ij}x_{j}-y_{i})$$= \sum_{j\in N}(c_{j}-\sum_{i\in M}a_{ij}u_{j})x_{j}+\sum_{i\in M}y_{i}(w_{i}-u_{i})+\sum_{i\in M}b_{\iota’}u_{l}$’(3)subject to$\sum_{j\in G_{h}}x_{j}\leq d_{h},$$h\in K,$$x_{j}\in\{0,1\}, j\in N,$$y_{i}\in\{0, \ldots, b_{i}\}, i\in M,$

166
the Lagrangian cost associated with column $j\in N.$
where we call
For any $u,$ $z_{LR}(u)$ gives a lower bound on the optimal value of SMCP-GUB $z(x^{*})$ . The problemof finding a Lagrangian multiplier vector that maximizes $z_{LR}(u)$ is called the Lagrangian dual
problem:(4).
(LRD) maximize$\tilde{c}_{j}(u)=c_{j}-\sum_{i\in M}a_{ij}u_{i}$$u$$\{z_{LR}(u)|u\in \mathbb{R}_{+}^{m}\}$For a given , we can easily compute an optimal solution to $LR(u)$ . Let
be an optimal solution to $LR(u)$ . For each blockand$(h\in K)$ , if the number of columns $j\in G_{h}$ satisfying
is equal toor less, then set);
respectively,) for variables satisfying
respectively,
otherwise, set
andfor variables with thelowest Lagrangian costs
$i\in
M$
, set
) if
respectively,
for the other variables. For
respectively, $u_{i}<w_{i})$ holds.
The Lagrangian relaxation $LR(u)$ has integrality property, i.e., an optimal solution to thehnear programming ( $LP$ ) relaxation problem of $LR(u)$ (i.e., the problem obtained by replacing$x_{j}\in\{0,1\}$ with $0\leq x_{j}\leq 1$ for $j\in N$ , and $y_{i}\in\{0, \ldots, b_{i}\}$ with $0\leq y_{i}\leq b_{i}$ for $i\in M,$
respectively) is also optimal to the original problem $LR(u)$ . In this case, any optimal solution
to the dual of the $LP$ relaxation problem of SMCP-GUB is also optimal to the Lagrangian
dual problem LRD. Hence, the optimal value of the $LP$ relaxation problem of SMCP-GUB
is equal to that of LRD.
A common approach to compute a near optimal Lagrangian multiplier vector is the subgradient method. It uses the subgradient vector $s(u)=(s_{1}(u), \ldots, s_{m}(u))\in \mathbb{R}^{m}$ , associated witha given , defined by$\tilde{x}(u)=(\tilde{x}_{1}(u),$$u$$\ldots,$$\tilde{y}(u)=(\tilde{y}_{1}(u), \ldots,\tilde{y}_{m}(u))$$\tilde{x}_{n}(u))$$G_{h}$$\tilde{c}_{j}(u)<0$$\tilde{x}_{j}(u)arrow 1$$\tilde{c}_{j}(u)<0$$\tilde{x}_{j}(u)arrow 0$$($$d_{h}$$d_{h}$$\tilde{x}_{j}(u)arrow 1$$\tilde{c}_{j}(u)\geq 0$$($$\tilde{x}_{j}(u)arrow 0$$\tilde{c}_{j}(u)$$\tilde{y}_{i}(u)arrow b_{i}$$\tilde{y}_{i}(u)arrow 0$$($$u_{i}\geq w_{i}$$($$u^{*}$$z_{LP}$$z_{LR}(u^{*})$

$u$

$u$

$s_{i}(u)=b_{i}- \sum_{j\in N}a_{ij}\tilde{x}_{j}(u)-\tilde{y}_{i}(u)$.

(5)

This method generates a sequence of non-negative Lagrangian multiplier vectors
by the following formula:is updated fromwhere
is a given initial vector and$u^{(0)},$ $u^{(1)},$$\ldots,$$u^{(l+1)}$$u^{(0)}$$u^{(l)}$$u_{i}^{(l+1)} arrow\max\{u_{i}^{(l)}+\lambda\frac{z_{UB}-z_{LR}(u^{(l)})}{||s(u^{(l)})||^{2}}s_{i}(u^{(l)}), 0\}, i\in M$,(6)

is a parameter called the step size.
whereis an upper bound on $z(x)$ , andWhen huge instances of SCP are solved, the computing time spent on the subgradient method
becomes very large if a naive implementation is used. Caprara et al. [5] developed a variant ofpricing method on the subgradient method. They define a dual core problem consisting of asmall subset of columns $C_{d}\subset N(|C_{d}|\ll|N|)$ , chosen among those having the lowest Lagrangian, and iteratively update the dual core problem in a similar fashion to that
costs
used for solving large scale $LP$ problems. In order to solve huge instances of SMCP-GUB, wealso introduce their pricing method into the basic subgradient method (BSM) described in [21].
$z_{UB}$$\lambda>0$$\tilde{c}_{j}(u)(j\in C_{d})$3

The 2-flip Neighborhood Local Search Algorithm

The local search ( $LS$ ) starts from an initial solution and repeats replacing with a better
solution $x’$ in its neighborhood $NB(x)$ until no better solution is found in $NB(x)$ . For a positive
integer , the r-ffip neighborhood $NB_{r}(x)$ is defined by $NB_{r}(x)=\{x’\in\{0,1\}^{n}|d(x, x’)\leq r\},$
$x$

$r$

$x$

167
where $d(x, x’)=|\{j\in N|x_{j}\neq x_{j}’\}|$ is the Hamming distance between and $x’$ . In other words,$NB_{r}(x)$ is the set of solutions obtained fromby ffipping at most variables. In our $LS$ , the$LS$is set to 2. In order to improve efficiency, oursearches $NB_{1}(x)$ first, and $NB_{2}(x)\backslash NB_{1}(x)$only if is locally optimal with respect to $NB_{1}(x)$ .
Since the region searched in a single application of $LS$ is limited, $LS$ is usually applied manytimes. When a locally optimal solution is obtained, a standard strategy of our algorithm is to
update penalty weights and to resume $LS$ from the obtained locally optimal solution. We accordingly evaluate solutions with an altemative evaluation function, where the original penalty
weight vector $w$ is replaced with, which are adaptively controlled in
the search (See the details in Section 4).
We first describe our $LS$ to search $NB_{1}(x)$ , called the l-flip neighborhood search. Let
$x$

$x$

$r$

$r$

$x$

$\hat{z}(x)$$\hat{w}=(\hat{w}_{1}, \ldots,\hat{w}_{m})\in \mathbb{R}_{+}^{m}$$\triangle\hat{z}_{j}^{+}(x) = c_{j}- \sum \hat{w}_{i},$$\triangle\hat{z}_{j}^{-}(x) = -c_{j}+\sum^{i\in M_{L}}(x)\cap S_{j} \hat{w}_{i}$(7),$i\in(M_{L}(x)\cup M_{E}(x))\cap S_{j}$denote the increase ofby flipping $x_{j}=0arrow 1$ and $x_{j}=1arrow 0$ , respectively, where
and $M_{E}(x)= \{i\in M|\sum_{j\in N}a_{ij}x_{j}=b_{i}\}$ . Our $LS$ firstsearches for an improved solution obtainable by flipping $x_{j}=0arrow 1$ by searching for $j\in N\backslash X$
satisfying
and $\sum_{j\in G_{h}}x_{j’}<d_{h}$ for $G_{h}\ni j$ . If an improved solution exist, it chooses
with the minimum; otherwise, it searches for an improved solution obtainable byflipping $x_{j}=1arrow 0$ by searching for $j\in X$ satisfying
We next describe our $LS$ to search $NB_{2}(x)\backslash NB_{1}(x)$ , called the 2-flip neighborhood search.
Yagiura et al. [23] developed an $LS$ with the 3-flip neighborhood for SCP. They derived conditions that reduce the number of candidates in $NB_{2}(x)\backslash NB_{1}(x)$ and $NB_{3}(x)\backslash NB_{2}(x)$ without
sacrificing the solution quality. However, those conditions are not applicable to the 2-ffip neighborhood for SMCP-GUB because of GUB constraints. We therefore propose new conditions
that reduce the number of candidates in $NB_{2}(x)\backslash NB_{1}(x)$ taking account of GUB constraints.
Our $LS$ is based on the following three lemmas. Let
denote the increase ofbyffipping the values ofandsimultaneously.
$\hat{z}(x)$$M_{L}(x)= \{i\in M|\sum_{j\in N}a_{ij}x_{j}<b_{i}\}$$\triangle\hat{z}_{j}^{+}(x)<0$$j$$\triangle\hat{z}_{j}^{+}(x)$$\triangle\hat{z}_{j}^{-}(x)<0.$$\hat{z}(x)$$\triangle\hat{z}_{j_{1},j_{2}}(x)$$x_{j_{1}}$$x_{j_{2}}$Lemma 1 Suppose that a solution
holds, only if
$0$

$x$

is locally optimal with respect to $NB_{1}(x)$ . Then$\triangle\hat{z}_{j_{1},j_{2}}(x)<$$x_{j_{1}}\neq x_{j_{2}}.$The proofs is omitted due to space hmitations. Based on this lemma, we consider only the setof solutions obtainable by ffipping $x_{j_{1}}=1arrow 0$ and $x_{j_{2}}=0arrow 1$ simultaneously. We now define$\triangle\hat{z}_{j_{1},j_{2}}(x)=\triangle\hat{z}_{j_{1}}^{-}(x)+\triangle\hat{z}_{j_{2}}^{+}(x)-\sum_{i\in M_{E}(x)\cap S_{j_{1}}\cap S_{j_{2}}}$砺．(8)Lemma 2 Suppose that a solution is locally optimal with respect to $NB_{1}(x),$ $x_{j_{1}}=1$ and$x_{j_{2}}=0$ .
Thenholds, only if at least one of the following two conditions holds.
$x$$\triangle\hat{z}_{j_{1},j_{2}}(x)<0$(i) Both(ii)$j_{1}$

and$j_{2}$

belong to the same block$M_{E}(x)\cap S_{j_{1}}\cap S_{j_{2}}\neq\emptyset.$$G_{h}$

satisfying$\sum_{j\in G_{h}}x_{j}=d_{h}.$168
Lemma 3 Suppose that a solution is locally optimal with respect to $NB_{1}(x)$ , and for a blockand a pair of indiceswith $x_{j_{1}}=1$ and $x_{j_{2}}=0,$
andhold. Then we have$x$$j_{1},j_{2}\in G_{h}$$\emptyset$$G_{h}$$M_{E}(x)\cap S_{j_{1}}\cap S_{j_{2}}=$$\triangle\hat{z}_{j_{1},j_{2}}(x)<0$$\min_{j\in G_{h}}\Delta\hat{z}_{j}^{-}(x)+\min_{j\in}c_{h}\triangle\hat{z}_{j}^{+}(x)<0.$

The proof of Lemmas 2 and 3 are omitted due to space hmitations. Note that the condition ofLemma 3 imphes that the condition (i) of Lemma 2 is satisfied. Then, from Lemma 3, we canconclude that to find an improved solution that satisfies condition (i), it suffices to check only
one pair for each block, instead of checking all pairs
satisfying
with$j_{1},j_{2}\in G_{h},$ $x_{j_{1}}=1$ and $x_{j_{2}}=0$ (provided that the algorithm
also checks the solutions thatsatisfy condition (ii) .
Our $LS$ first searches for an improved solution in $NB_{2}(x)\backslash NB_{1}(x)$ that satisfies the condition(i). For each block $G_{h}(h\in K)$ that satisfies, it checks the solution obtained byflipping $x_{j_{1}}=1arrow 0$ and $x_{j_{2}}=0arrow 1$ with the minimum
and
,
$LS$
respectively. Our
then searches for an improved solution in $NB_{2}(x)\backslash NB_{1}(x)$ that satisfies thecondition (ii). Let
denote the subset of $NB_{2}(x)$ obtainable by ffipping $x_{j_{1}}=1arrow 0.$
Our $LS$ searches
for each $j_{1}\in X$ in the ascending order of. If an improved
solution is found, it chooses a pairandwith the minimum
among those in, and it returns to the l-ffip neighborhood search algorithm. Our $LS$ is formallydescribed as follows.
$G_{h}$$(j_{1},j_{2})$$\sum_{j\in G_{h}}x_{j}=d_{h}$$)$$\sum_{j\in G_{h}}x_{j}=d_{h}$$\triangle\hat{z}_{j_{1}}^{-}(x)$$\Delta\hat{z}_{j_{2}}^{+}(x)(j_{1}, j_{2}\in G_{h})$$NB_{2}^{(j_{1})}(x)$$NB_{2}^{(j_{1})}(x)$$\triangle\hat{z}_{j_{1}}^{-}(x)$$j_{1}$$j_{2}$$\Delta\hat{z}_{j_{1},j_{2}}(x)$$NB_{2}^{(j_{1})}(x)$Algorithm $LS(x,\hat{w})$Input:$A$

Output:solution$A$$x$and a penalty weight vector$\hat{w}.$solution $x.$

Step 1: If $I_{1}^{+}(x)=\{j\in N\backslash X|\triangle\hat{z}_{j}^{+}(x)<0,$ $\sum_{j\in G_{h}}x_{j’}<d_{h}$ for
holds, choose $j\in I_{1}^{+}(x)$ with the minimum, set
and return toStep 1.

$G_{h}\ni j\}\neq\emptyset$$\triangle\hat{z}_{j}^{+}(x)$$x_{j}arrow 1$

Step 2: If $I_{1}^{-}(x)=\{j\in X|\triangle\hat{z}_{j}^{-}(x)<0\}\neq\emptyset$ holds, choose $j\in I_{1}^{-}(x)$ with the, setminimumand return to Step 2.
$x_{j}arrow 0$$\triangle\hat{z}_{j}^{-}(x)$Step 3: For each block
satisfying $\sum_{j\in G_{h}}x_{j}=d_{h}(h\in K)$ , if
holds
for and with the minimumand, respectively,set. If the current solution has been updated at leastandonce in Step 3, return to Step 3.
$G_{h}$$j_{1}$$j_{2}$$\triangle\hat{z}_{j_{1},j_{2}}(x)<0$$\Delta\hat{z}_{j_{2}}^{+}(x)(j_{1},j_{2}\in G_{h})$$\Delta\hat{z}_{j_{1}}^{-}(x)$$x_{j_{1}}arrow 0$$x_{j_{2}}arrow 1$$x$

Step 4: For each $j_{1}\in X$ in the ascending order of, if $I_{2}(x)=\{j_{2}\in N\backslash X|$
forholds,
choose $j_{2}\in I_{2}(x)$ with}the minimum
and setand. If the current solution
has been updated at least once in Step 4, return to Step 1; otherwise output
and exit.
$\triangle\hat{z}_{j_{1},j_{2}}(x)<0,$$\sum_{j\in G_{h}}x_{j’}<d_{h}$$\triangle\hat{z}_{j_{1},j_{2}}(x)$$G_{h}\ni j_{2}$$\Delta\hat{z}_{j_{1}}^{-}(x)$$\neq\emptyset$$x_{j_{1}}arrow 0$$x_{j_{2}}arrow 1$

$x$

$x$

We note that our $LS$ does not necessarily output a locally optimal solution with respect to$NB_{2}(x)$ , because the solution
is not necessarily locally optimal with respect to $NB_{1}(x)$ in
Steps 3 and 4. Though it is easy to keep the solution locally optimal with respect to $NB_{1}(x)$in Steps 3 and 4 by returning to Step 1 whenever an improved solution is obtained in Step 2 or
3, we did not adopt this option because it consumes much computing time just to conclude thatthe current solution is locally optimal with respect to $NB_{1}(x)$ in most cases.
$x$

$x$

169
Let one-round be the computation needed to find an improved solution in the neighborhood or to conclude that the current solution is locally optimal. For convenience, let$\tau=\max_{j\in N}\sum_{i\in S_{j}}|N_{i}|,$ $\nu=\max_{j\in N}|S_{j}|$ and $n’= \sum_{j\in N}x_{j}$ . If implemented
naively, our $LS$ requires
andone-round time for $NB_{1}(x)$ and $NB_{2}(x)$ , respectively.
In order to improve efficiency, we make use of the following auxiliary data$\sigma=$$\sum_{i\in M}\sum_{j\in N}a_{ij},$$O(n\sigma)$$O(\sigma)$$\rho_{j}^{+}(x) = \sum \hat{w}_{i}, j\in N\backslash X,$$\rho_{j}^{-}(x) = (x)\cap S\sum^{j}^{i\in M_{L}} \hat{w}_{i}, j\in X$(9).

$i\in(M_{L}(x)\cup M_{E}(x))\cap S_{j}$We store the values ofandfor $j\in N$ in memory to compute each
andin $O(1)$ time. We also store the values offor $i\in M$ in memory to update the values ofandfor $j\in N$ intime whenis changed. In our implementation, one-round time is reduced to $O(n+\tau)$ for $NB_{1}(x)$ and$O(n+k\nu+n’\tau)$ for $NB_{2}(x)\backslash NB_{1}(x)$ by making use of the memory structure. Because
and $n’\leq n$ always hold, these orders are not worse than those of naive implementation, and aremuch better if
and $n’\ll n$ hold.
$\rho_{j}^{+}(x)$$\rho_{j}^{+}(x)$$\rho_{j}^{-}(x)$$\triangle\hat{z}_{j}^{+}(x)=c_{j}-$$\triangle\hat{z}_{j}^{-}(x)=-c_{j}+\rho_{j}^{-}(x)$$\theta_{i}(x)=\sum_{j\in N}a_{ij}x_{j}$$\rho_{j}^{+}(x)$$O(\tau)$$\rho_{j}^{-}(x)$$x$$\tau\leq\sigma$$\tau\ll\sigma$

4

Adaptive Control of Penalty Weights

Recall that in our algorithm, solutions are evaluated by the alternative evaluation functionin which the fixed penalty weight vector $w$ in the original objective function $z(x)$ is replacedwith, and the values ofare adaptively controlled in the search. It is$LS$
often reported that local search ( ) alone may not attain a sufficiently good solution. ur $LS$
tends to be also attracted to locally optimal solutions of insufficient quality when the originallarge penalty weights $w_{i}= \sum_{j\in N}c_{j}+1(i\in M)$ are used asin the evaluation function. We accordingly incorporate a mechanism to adaptively control the values of , i.e., ouralgorithm iteratively applies $LS$ , updating the penalty weight vector after each call to $LS$ . We
call such a sequence of calls to $LSLS$-probe, and use it as the main engine to improve solutions.
Let denote the solution at which the previous local search stops. The $LS$ -probe resumes $LS$
from after updating the penalty weight vector . Starting from the original penalty weightvector, the penalty weight vector
is updated as follows. Let best denote the best
feasible solution with respect to the original objective function $z(x)$ obtained in the current
call to $LS$ -probe. If $\hat{z}(x)\geq z(x^{best})$ holds, $LS$ -probe uniformly decreases the penalty weights
for $i\in M$ , where the parameter is adaptively computed so that for 15% ofvariables satisfying $x_{j}=1$ , the new value of
becomes negative. Otherwise, $LS$ -probe
increases the penalty weights by$\hat{z}(x)$$\hat{w}=(\hat{w}_{1}, \ldots,\hat{w}_{m})\in \mathbb{R}_{+}^{m}$$\hat{w}_{i}$$O$$\hat{w}_{i}$$\hat{z}(x)$$\hat{w}_{i}$$\hat{w}$

$x$

$x$

$\hat{w}$$\hat{w}arrow w$$\hat{w}$$\hat{w}_{i}arrow(1-\eta)\hat{w}_{i}$$x$$\eta$$\triangle\hat{z}_{j}^{-}(x)$,$\hat{w}_{i}arrow\min\{\hat{w}_{i}(1+\delta\frac{p_{i}(x)}{\max_{i\in M}p_{i}(x)}), w_{i}\}, i\in M$(10)

where $p_{i}(x)= \max\{b_{i}-\sum_{j\in N}a_{ij}x_{j}, 0\}$ is the amount of violation of the ith multicover constraint, and is a parameter that is set to 0.2 in our experiment. $LS$ -probe iteratively applies$LS$ , updating the penalty
weight vector after each call to $LS$ , until the best solution obtainedin the current call to $LS$ -probe with respect to the original objective function $z(x)$ has not
improved in the last 50 iterations.
$\delta$$\hat{w}$170
Algorithm $LS-probe(x)$Input:$A$

solution $x.$

Output: The best solution

$x$

best

with respect to $z(x)$ .

Step 1: Set $iterarrow 0,$ $x^{best}arrow x,\hat{x}arrow x$ and$\hat{w}arrow w.$

Step 2: Apply
to obtain an improved solution
solution with respect to the original objective function. Set
call to$LS(\hat{x},\hat{w})$$\downarrow\hat{x}’$. Let $x’$ be the best
obtained during the$z(\cdot)$$\hat{x}arrow\hat{x}’.$$LS(\hat{x},\hat{w})$

Step 3: If $z(x’)<z(x^{be\epsilon t})$ holds, then set $x^{best}arrow x’$ and $iterarrow 0$ ; otherwise set$iterarrow iter+1$ . If $iter\geq 50$ holds, output
and halt.
$x^{best}$

Step 4: If
holds, then uniformly decrease the penalty weightsfor; otherwise, increase the penalty weights
all $i\in M$ by
for all$i\in M$ by (10). Retum to Step 2.
$\hat{z}(\hat{x})\geq z(x^{best})$$\hat{w}_{i}$$\hat{w}_{i}arrow(1-\eta)\hat{w}_{i}$5$\hat{w}_{i}$Path Relinking Method

The path relinking [15] is an evolutionary approach to integrate intensification and diversification strategies that generates new solutions by combining two or more solutions. This approach
generates new solutions by exploring trajectories that connect good solutions. It starts from oneof the good solutions, called an initiating solution, and generates a path by iteratively moving
to a solution in the neighborhood that leads toward the other solutions, called guiding solutions.
Because it is preferable to apply path relinking to solutions of high quahty, we keep referencesets
andof good solutions with respect to the original objective function $z(x)$ and thealternative evaluation function
with the current penalty weight vector , respectively.
Initiallyandare prepared by applying $LS$ -probe to randomly generated solutions. They
are then updated by reflecting outcomes of $LS$ -probe whenever $LS$ -probe stops. Suppose thatthe last call to $LS$-probe stops at a solution and best is the best solution with respect toobtained during the last call to $LS$ -probe. Then, the worst solution(with respect toinis replaced with the solution
if $z(x^{best})\leq z(x^{worst})$ and $x^{best}\neq x’$ hold for all $x’\in R_{1}.$The worst solution(with respect toin) is also replaced with the solution
if$x\neqx’$$x’\inR_{2}.$
andhold for all
The path relinking is applied to two solutions $x’$ (initiating solution) and $x”$ (guiding solution)
randomly chosen from, respectively. Let $\xi=d(x’, x")$ be the Hamming distance
and
$x’$
$x”$
$x^{(\xi)}=x"$ ofbetween solutions. It then generates a sequence $x’=x^{(0)},$andsolutions ae follows. Starting from $x^{(0)}arrow x’$ , for $l=1,$, it chooses a solution
with thebest value ofamong those satisfying $x\in NB_{1}(x^{(l-1)})$ and $d(x, x”)<d(x^{(l-1)}, x")$ . Ouralgorithm chooses the first solution $x^{(l)}(l=1, \ldots, \xi-1)$ satisfying
ae the$LS$next initial solution of -probe.
$R_{1}$$R_{2}$$\hat{z}(x)$$R_{1}$$\hat{w}$$R_{2}$$x$$x$$z(\cdot)$$x^{worst}$$R_{1}$$X^{be8}t$$z(\cdot))$$\hat{x}^{worst}$$R_{2}$$x$$\hat{z}(\cdot)$$\hat{z}(x)\leq\hat{z}(\hat{x}^{worst})$$R_{2}$$R_{1}$$x^{(1)},$$\ldots,$$x^{(l)}$$\xi$$\ldots,$$\hat{z}(x)$$\hat{z}(x^{(l)})\leq\hat{z}(x^{(\iota+1)})$

6

Heuristic Reduction of Problem Sizes

For a near optimal Lagrangian multiplier vector , the Lagrangian costs
give rehable
information on the overall utility of selecting columns $j\in N$ for SCP. Based on this property, the$u$$\tilde{c}_{j}(u)$171
Lagrangian costs
are often utilized to solve huge instances of SCP, e.g., several heuristic
algorithms successively solve a number of subproblems, called primal core problems, consistingof a small subset of columns $C_{p}\subset N(|C_{p}|\ll|N|)$ , chosen among those having low Lagrangian
costs $\tilde{c}_{j}(u)(j\in C_{p})[5,8,9,23].$
The Lagrangian costs
are unfortunately unrehable about selecting columns $j\in N$ for
SMCP-GUB, because GUB constraints often prevent solutions from containing more thanvariables with the lowest Lagrangian costs. To overcome this, we develop an evaluation
scheme of columns $j\in N$ for SMCP-GUB taking account of GUB constraints. The main idea of
our algorithm is that we modify the Lagrangian costs
to reduce the number of redundant
columns $j\in C_{p}$ resulting from GUB constraints.
For each block $G_{h}(h\in K)$ , let
be the value of the $(d_{h}+1)$ st lowest Lagrangian costamong those for columns in, where we set
if $d_{h}=|G_{h}|$ holds. We then define a
score
for a column $j\in G_{h}$ by
if $\gamma_{h}<0$ holds, andotherwise. That is, we normahze the Lagrangian costs
so that at mostcolumns havenegative scores $\hat{c}_{j}(u)<0$ for each block $G_{h}(h\in K)$ . Let $n’= \sum_{j\in N}x_{j}$ be the number of
selected subsets for a solution . Given a solution and a Lagrangian multipher vector , a
primal core problem is defined by a subset
consisting of (i) columns $j\in N_{i}$ with the$i\inM$
lowest scoresfor each, and (ii) columns $j\in N$ with the $10n’$ lowest scores.
$\tilde{c}_{j}(u)$$\tilde{c}_{j}(u)$$d_{h}$$\tilde{c}_{j}(u)$$x_{j}$$\tilde{c}_{j}(u)$$\tilde{c}_{j}(u)$$\gamma_{h}$$G_{h}$$\gamma_{h}arrow 0$$\hat{c}_{j}(u)=\tilde{c}_{j}(u)-\gamma_{h}$$\hat{c}_{j}(u)$$\hat{c}_{j}(u)=\tilde{c}_{j}(u)$$d_{h}$$\tilde{c}_{j}(u)$

$x$

$x$

$u$

$C_{p}\subset N$$b_{i}$$\hat{c}_{j}(u)$$\hat{c}_{j}(u)$Algorithm CORE $(x, u)$
Input:$A$

solution$x$and the Lagrangian multiplier vector $u.$

Output: The primal core problem$C_{p}\subset N.$

Step 1: For each block $G_{h}(h\in K)$ , let
be the value of $(d_{h}+1)$ st lowest Lagrangian cost
if $d_{h}<|G_{h}|$ holds andotherwise, and thenset scores byifholds andotherwise$j\in
G_{h}.$
for all$\gamma_{h}$$\tilde{c}_{j}(u)(j\in G_{h})$$\gamma_{h}arrow 0$$\hat{c}_{j}(u)arrow\tilde{c}_{j}(u)-\gamma_{h}$$\gamma_{h}<0$$\hat{c}_{j}(u)arrow\tilde{c}_{j}(u)$Step 2: For each $i\in M$ , let
be the set of columns $j\in N_{i}$ with theamong those in . Then set.
$C_{1}(i)$$\hat{c}_{j}(u)$Step 3: Set$C_{2}$

Step 4: Set$C_{p}arrow C_{1}\cup C_{2}$$b_{i}$

lowest$C_{1} arrow\bigcup_{i\in M}C_{1}(i)$$N_{i}$

be the set of columns $j\in N$ with the $10n’$ lowest. Output$C_{p}$$\hat{c}_{j}(u)$.

and halt.

The primal core problem
is updated before every call to $LS$ -probe. Before updating the
primal core problem, our algorithm heuristically fixes some variables
to 1 to reflect the$x’$characteristics of the incumbent solution and the current solution . Let be the Lagrangian
multiplier vector obtained by the subgradient method, and $V=\{j\in N|x_{j}^{*}=x_{j}’=1\}$ be anindex set from which variables to be fixed are chosen. ur algorithm randomly chooses a variable$x_{j}(j\in V)$ with probability$C_{p}$$C_{p}$$x_{j}$$x^{*}$$\overline{u}$$O$$prob_{j}(\overline{u})=\frac{\tilde{c}_{\max}\overline{u})-\tilde{c}_{j}(\overline{u})}{\sum_{j’\in V(\tilde{c}(\overline{u})-\tilde{c}_{j},(\overline{u}))}x}$

,

(11)

and fixes $x_{j}=1$ , where. We note that uniform distribution is used if
holds for all $j’\in V$ . Our algorithm iteratively chooses and fixes a variable$(j\in V)$ unti120% of multicover constraints are satisfied. It then sets the Lagrangian multipher$\tilde{c}_{\max}(\overline{u})=\max_{j’\in V}\tilde{c}_{j’}(\overline{u})$$\tilde{c}_{\max}(\overline{u})=\tilde{c}_{j’}(\overline{u})$$x_{j}$

172$u_{i}arrow 0$

costs

if

$\sum_{j\in F}a_{ij}\geq b_{i}$$\tilde{c}_{j}(u)$forholds andotherwise for $i\in M$ , and computes the Lagrangian, where is the index set of the fixed variables.
$u_{i}arrow\overline{u}_{i}$$F$$j\in N\backslash F$

Algorithm FIX$(x^{*}, x’,\overline{u})$Input: The incumbent solution
multiplier vector$x^{*}$, the current solution $x’$ and the Lagrangian$\overline{u}.$Output: The set of fixed variables $F\subset N$ and the Lagrangian multiplier vector $u.$
Step 1: Set $Varrow\{j\in N|x_{j}^{*}=x_{j}’=1\}$ and
Step 2: If
each $i\in M$ , set
and , and halt.

$Farrow\emptyset.$holds for 20% of multicover constraints $i\in M$ , then forifholds andotherwise, output $F$$\sum_{j\in F}a_{ij}\geq b_{i}$$u_{i}arrow 0$$\sum_{j\in F}a_{ij}\geq b_{i}$$u_{i}arrow\overline{u}_{i}$$u$Step 3: Randomly choose a column $j\in V$ with probabihty(11), and set $Farrow F\cup\{j\}$ and. Return to Step 2.

$prob_{j}(\overline{u})$defined by$Varrow V\backslash \{j\}$7Computational Results

We first prepared eight classes of random instances for SCP, where classes
andwere
taken from Beasley’s $OR$ Library [3] and classes I- were newly generated in the same manner,
where each class has five instances. We denote instances in class as G.1, . . . , .5, and otherinstances in classes H- similarly. The summary of these instances are given in Table 1, where
the density is defined by $\sum_{i\in M}\sum_{j\in N}a_{ij}/mn$ and the costs
are random integers taken frominterval [1, 100]. For each SCP instance, we generate four types of SMCP-GUB instances withdifferent values of parameters
andas shown in Table 1, where all blocks $G_{h}(h\in K)$
have the same size
and upper boundfor each instance. Here, the right-hand sides ofmulticover constraints are random integers taken from interval [1, 5].
We compared our algorithm, called the local search algorithm with the heuristic size reduction( $LS$ $SR$ ), with one of the latest mixed integer program (MIP) solver called CPLEX12.3, where
they were tested on an IBM-compatible personal computer (Intel Xeon E54202.5 GHz, 4 $GB$
memory) and were run on a single thread. Table 1 also shows the time limits in seconds for $LS$
$SR$ and CPLEX12.3, respectively.
We tested two variants of $LS$ $SR$ : $LS$ -SRI evaluates variables
with the proposed score, and $LS$ $SR$2 uses the Lagrangian costin the heuristic
reduction of problem sizes. Tables 2-5 show the average objective values (columns “obj.”) andthe average time to find the best solution (columns “t.t. ”) of $LS$ -SRI, $LS$ $SR$ 2 and CPLEX12.3
for instance types 1-4. The best results among these algorithms are marked with underhnes.
We also illustrate in Figures 2 and 3 their comparison for each type of SMCP-GUB instanceswith respect to the relative gap %
$G$

$H$

$N$

$G$

$G$

$N$

$c_{j}$$|G_{h}|$$d_{h}$$|G_{h}|$$d_{h}$$b_{i}$---$\hat{c}_{j}(x)$$x_{j}$-$\tilde{c}_{j}(x)$

$b.$

$($

-

$)$

gap $(x)= \frac{z(x)-z_{LP}}{z_{LP}}\cross 100$ ,

(12)

where
is the optimal value of $LP$ relaxation for SMCP-GUB.
We first observe that $LS$ -SRI and $LS$ $SR$ 2 achieve better upper bounds than CPLEX12.3
for types 3 and 4 instances. This indicates that $LS$ -SRI and $LS$ $SR$2 are more efficient than
CPLEX12.3 for large instances with 10,000 variables or more. One of the main reasons for this is$z_{LP}$

-

-

173
: The benchmark instances for SMCP-GUB and time hmits for our algorithm $LS$ $SR$ andthe MIP solver CPLEX (in seconds)$\ovalbox{\tt\small REJECT} 1$-

Instance types $(d_{h}/|G_{h}|)$Time limit$\overline{LS-SR}$
CPLEX$\frac{InstanceRowsCo1umnsDensityType1Type2Type3Type4}{G.1-G.5100010,0002.0\% 1/1010/1005/1050/1006003600}$
H.I- .5
I.I- .5
J.I- .5

1000

$H$

1000

$I$

1000
2000
2000
5000

$J$

K.I- .5
L.1- 5
M.I-$M$ .5
N.I- .5
$K$

$L$

5000

$N$

5.0%
1.0%
1.0%
0.5%
0.5%
0.25%
0.25%

10,00050,000100,000
100,000
200,000
500,000
1,000,000

1/10
1/50
1/50

10/10010/50010/500

1/50
1/50
1/50

10/50010/50010/5001/100

10/1000

5/10
5/50
5/50
5/50
5/50
5/50
5/100

600
600

50/10050/50050/50050/50050/50050/50050/1000

600
1200
1200
3000
3000

3600
3600

3600
7200
7200
18,00018,000that the proposed algorithms evaluate a series of candidate solutions efficiently while CPLEX12.3
consumes much computing time for solving $LP$ relaxation problems (even though it uses thewarm-start technique for solving a series of $LP$ relaxation problems efficiently). We also observethat $LS$ -SRI achieves much better upper bounds than those of $LS$ $SR$2 and CPLEX12.3 for types
1 and 2 instances. This indicates that $LS$ $SR$ 2 was not able to choose appropriate columns forthe primal core problem
and $LP$ relaxation based heuristic algorithms in CPLEX12.3 (e.g.,
local branching [12], feasibihty pump [1, 13, 14] and RINS [11] does not work efficiently for thetested instances. This is probably because the gap between upper and lower bounds is large.
--$C_{p}$$)$

表 2: Computational results of $LS$ $SR$ and CPLEX12.3 on instance type 1-

LS-SRI

LS-SR2CPLEX$\underline{Instancez_{LP}\overline{obj.}}$t.t.

G.I- .5

1683.51395.172806.81$G$

H.I-$H$ .5
I. I- .5
J.I- .5$I$

1453.48$J$

K.I- .5
L.I- .5
M.I-$M$ .5
N. $1-N.5$

5593622916.645451.554761.81

$K$

$L$

GH

$\ovalbox{\tt\small REJECT}$

2313.4586.6
3920.42012.47974.44178.88424.47951.6JKLMNInstance (Typel)

$b.$

346.3
325.2

$\overline{obj.}$t.t.

$\overline{obj.t.t.b.}$$b.$2319.8

335.6

5892

1915

173,3
37555708.4
36283977.8
117.2
9514
11721864.91037.08633.6186.3
1432.018250.8858.4
1115.9207462747.7

GH

2578.03286.6658.8
4339.02361.01514.91882.52054.25447.219066.0
18790.05295.21555.248415

188422515.9

I

JKLMN
Instance (Type2)

図 2: Comparison of $LS$ $SR$ and CPLEX12.3 on instance types 1 and 2-

174
表 3: Computational results of $LS$ $SR$ and CPLEX12.3 on instance type 2-

LS-SR2CPLEX$\overline{obj.t.t.b.}$$\overline{obj.}$t.t.

LS-SRI$\overline{obj.}$
t.t.
$b.$

$b.$

$\frac{Instancez_{LP}}{G.1-G.5347.21896.2298.62084.21654.7}$
1491.11370.592661.28
1382.595322.892771. $20$
5219.124596.99

H.I- .5
I.I- .5
J.I- .5
K.I- .5
$H$

$I$

$J$

$K$

.5

M.I-

$N.1-N.5L.1-L.5$$M$1888.4512.0
3518.6
1810.27301.2

286.0
312.6
389.1
736.2

513.4
4637.63427.010300.4
8089.
16695.4
20177.0$8491.6$$4$$\frac{}{}\frac{3780.0}{707807642..0}$2060.5$17803940.\cdot 6$1227.63453.83384.06608.2

571.6
271.8
156.2
5663.432683499.4
128.9
14407.2
1007.3$1255.667.5$

1354.4

17504.2
17348.4$3277.6531.7$

表 4: Computational results of $LS$ $SR$ and CPLEX12.3 on instance type 3
-

CPLEX

LS-SR2LS-SRI$\frac{Instancez_{LP}\overline{obj.t.t.b..}\overline{obj.t.t.b..}\overline{obj.t.t.b}}{G.1-G.5711.02765.62618765.62622830.03308.1}$

182.71930.40547.47
1851.01087.22083.51743.5

H.I- .5$H$

I.I- .5$I$

J.I- .5
K.I- .5
L.I- .5
M.I- $M$ .5
N.I- .5
$J$

$K$

$L$

$N$

205.0
1108.0638.4
2218.4
1286.82575.22324.4

238.8
243.5
423.5
846.3
845.5
2429.42282.3205.0
1108.4638.0
2233.01293.02583.22394.4

239.3
300.6
351.0
633.5

673.5
2534.51446.1210.0
1245.0693.6
3461.82022.24292.84444.01186.72440.93261.06724.1
5298.41178.93922.4

We finally compared $LS$ -SRI with the 3-flip neighborhood local search algorithm proposedby Yagiura et al. [23] (denoted as “YKI”) and CPLEX12.3 on the standard SCP instances,where YKI was run on the same conditions as $LS$ -SRI. Table 6 shows the average objective
values and the average time to best solution of $LS$ -SRI, YKI and CPLEX12.3 for the standard
SCP instances. Figure 4 illustrates their comparisons for the SCP instances with respect to therelative gap % .
We observe that $LS$ -SRI achieve comparable upper bounds to those of YKI and better upperbounds than CPLEX12.3, and the gap between upper and lower bounds is still large regardless of multicover and GUB constraints. We accordingly suppose that $LS$ -SRI achieved good
$($

$)$

performance for both SMCP-GUB and SCP instances.

8

Conclusion

In this paper, we considered an extension of SCP called the set multicover problem with thegeneralized upper bound constraints (SMCP-GUB). We proposed a heuristic algorithm to reduce
the size of problem instances. For this algorithm, we introduced a new evaluation scheme ofvariables taking account of GUB constraints. We also developed an efficient implementation of
a 2-flip neighborhood local search algorithm. The algorithm reduces the number of candidates
in the neighborhood without sacrificing the solution quality. According to computational comparison on benchmark instances with the latest version of a MIP solver called CPLEX12.3, our175
2115: Computational results of$LS$ $SR$-

LS-SRIand CPLEX12.3 on instance type 4
LS-SR2CPLEX. .
$\underline{Instancez_{LPO}\overline{bj.t.t.b.}\overline{obj.}}t$$\overline{obj.t.t.b.}$

G. I- .5
H.I- .5
I.I- .5
J.I- .5
K.I- .5
L.I-L5
M.I-$M$ .5
N.I- .5

690. $00$
179. $40$
915.54537.951819011017.172052.04$12$
1720.12
1720.

$G$

$H$

$I$

$J$

$K$

$N$

GH

I

$J$

$K$

351.6
208.0
444.3

$\underline{727.0}$$\underline{197.2}$

1063.8612.0
2132.61235.22491.4

327.6
665.8
S40.0

2423.02309.1$\underline{2230.2}$

$L$

$M$

$t$

727.0
1972
1065.0
6114
21306
12348
2492.42238.23523728.6

2715.2200.8
1132.6

1691.72893.92779.17052.26799.97097.92887.72085
553.92964632.8
8314
736.9

3138.0
19324
186343985.2
1638.54336.2$G$

Instance (Type3)

$b.$

$H$

I

JKLMN
Instance (Type4)

図 3: Comparison of $LS$ $SR$ and CPLEX12.3 on instance types 3 and 4-

algorithm performs quite effectively for various types of instances, especially for very large-scaleinstances.

参考文献[1] Achterberg, T., Berthold, T.: Improving the feasible pump. Discrete Optim., 4 (2007),

77-86.
[2] Beasley, J. .: A Lagrangian heuristic for set-covering problems. $Nav$ . Res. Logist., 37(1990), 151-164.
$E$[3] Beasley, J. .: $OR$-Library: Distributing test problems by electronic mail. J. Oper. Res.
Soc. 41 (1990), 1069-1072.
$E$[4] Boros, E., Hammer, P. ., Ibaraki, T., Kogan, A.: An implementation of logical analysis ofdata. IEEE Trans. Knowl. Data. Eng., 12 (2000), 292-306.
$L$[5] Caprara, A., Fischetti, M., Toth,Res., 47 (1999), 730-743.

$P$

:

$A$

heuristic method for the set covering problem. Oper.

[6] Caprara, A., Monaci, M., Toth, P.: Models and algorithms for a staff scheduling problem.
Math. Progmm., 98 (2003), 445-476.

176

表 6: Computational results of $LS$ -SRI, YKI and CPLEX12.3 on the standard SCP
CPLEX

YKI

LS-SRI$\frac{Instancez_{LP}\overline{obj...t.t.b..\cdot}\overline{obj...t.t.b..\cdot}\overline{\circ bj..\cdot t.t.b}}{H.1-H.545.674414608649.8G.1-G.5149.48\frac{1664}{596}1193\frac{1664}{596}281676605.9}$

I.I- .5
J.I-J.5
K.I- .5
L.I-L.5
M.I- $M$ .5
N.I- .5
$I$

$K$

$N$

88.5
235.9
267.3
S29.0
1554.12048.3

158.4
130.8
319.4
263.6
565.8
517.6

138.27104.78276.66209.33415.77348.79

157.6
129.4
3138
258.4
550.4
503.8

22.4
SO.O
175.3

445.8
1265.31517.7

160.6
136.0
321.6
285.2
635.6
631.4

2966.02740.16430.84640.68452.04274.3

GHIJKLMN
Instance (standard$SCP\rangle$

図 4: Comparison of $LS$ -SRI, YKI and CPLEX12.3 on the standard SCP[7] Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Ann. Oper.
Res., 98 (2000), 353-371.

[8] Caserta, M.: Tabu search-based metaheuristic algorithm for large-scale set covering problems. In: Gutjahr, W. ., Hartl, R. ., Reimann, M. (eds.) Metaheuristics: Progress inComplex Systems optimization, pp. 43-63. Springer-Verlag, Berhn, 2007.
$F$

$J$

[9] Ceria, S., Nobih, P., Sassano, A.: A Lagrangian-based heuristic for large-scale set covering
problems. Math. Progmm., 81 (1998), 215-228.

column generation approach to the heterogeneous fleet vehicle[10] Choi, E., Tcha, D- $W$ .:routing problem. Comput. Oper. Res., 34 (2007), 2080-2095.
$A$[11] Danna, E., Rothberg, E., Pape, C. .: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Prog., 102 (2004), 71-90.
$L$[12] Fischetti, M., Lodi, A.: Local branching. Math. Prog., 98 (2003), 23-47.

[13] Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Prog., 104 (2005), 91-104.
[14] Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Prog. Comp., 1 (2009), 201-222.
[15] Glover, F., Laguna, M.: Tabu Search, Kluwer Academic Pubhshers, Massachusetts, 1997.

177[16] Hammer, P. ., Bonates, T. .: Logical analysis of data An overview:combinatorial
optimization to medical applications. Ann. Oper. Res., 148 (2006), 203-225.
$L$

$O$

–

$\mathbb{R}om$[17] Hashimoto, H., Ezaki, Y., Yagiura, M., Nonobe, K., Ibaraki, T., Lkketangen, A.: $A$ set
covering approach for the pickup and delivery problem with general constraints on eachroute. $Pac$ . J. Optim., 5 (2009), 183-200.

[18] Ikegami, A., Niwa, A.:
subproblem-centric model and approach to the nurse scheduhng
problem. Math. Prog., 97 (2003), 517-541.
$A$[19] Kohl, N., Karisch, S. .: Airline crew rostering: Problem types, modeling, and optimization.
Ann. Oper. Res., 127 (2004), 223-257.
$E$[20] Pessoa, L. ., Resende, M.G. ., Ribeiro, C. .:hybrid Lagrangean heuristic with GRASP
and path-relinking for set -covering. Comput. Oper. Res., in press.
$S$

$C$

$C$

$A$

$k$

[21] Umetani, S., Yagiura, M.: Relaxation heuristics for the set covering problem. J. Oper. Res.
Soc. Jpn., 50 (2007), 350-375.

[22] Vazirani, V. .: Approximation algorithms, Springer-Verlag, Berlin, 2004.
$V$[23] Yagiura, M., Kishida, M., Ibaraki, T.: 3-flip neighborhood local search for the set covering
problem. $Eur$. J. Oper. Res., 172 (2006), 472-499.
$A$