* KISHIDA Masahiro YAGIURA Mutsunori IBARAKI Toshihide 1. $\mathrm{n}\mathrm{p}$ (SCP) 1,..,,,, $[1][5][10]$, [11], [4].., Fishe

Size: px

Start display at page:

Download "* KISHIDA Masahiro YAGIURA Mutsunori IBARAKI Toshihide 1. $\mathrm{n}\mathrm{p}$ (SCP) 1,..,,,, $[1][5][10]$, [11], [4].., Fishe"

いとはたかはし
5 years ago
Views:

1 * KISHIDA Masahiro YAGIURA Mutsunori IBARAKI Toshihide 1 $\mathrm{n}\mathrm{p}$ (SCP) 1 $[1][5][10]$ [11] [4] Fisher Kedia $m=200$ $n=2000$ [8] Beasley Gomory f- $m=400$ $n=4000$ [2] Beasley Chu [3] Jacobs Brusco [9] $m=1000$ $n=$ Caprara Fischetti Toth Ceria Nobil Sassano $m\simeq 5000$ $n\simeq $ $[5][6]$ 3 2 $M=\{1 \ldotsm\}$ $M$ $S_{j}$ $j\in N=\{1 \ldotsn\}$ $M$ 0-1 $x\in\{01\}^{n}$ minimize cost $(x)= \sum_{j\in N}C_{j}X_{j}$ (1) subject to $\sum_{j\epsilon N}a_{i}j^{X_{j}}\geq 1$ $i\in M$ (2) $x_{j}\in\{01\}$ $j\in N$ (3)

2 $a_{ij}$ : $v^{\mathrm{o}}$ 212 $c_{j}$ : $S_{j}$ $S_{j}$ $j$ 1 ) ( $c_{j}$ $x_{j}$ : $S_{j}$ 1 3 $n$ 31 v\in R (2) $c_{j}(v)=c_{j}- \sum_{ji\in s}v_{i}$ $v\in R_{+}^{m}$ $L(v \rangle=\min_{x}\sum_{\in jn}c_{j}(v)xj+$ $M$ (4) subject to $x_{j}\in\{01\}$ $j\in N$ (5) $L(v)$ $L(v)$ $v$ $x(v)$ $L(v)\leq \mathrm{c}x^{*}$ (4) $-(5)$ ) $\mathrm{s}v^{*}$ (4)$-(5)$ 9 $(v)<0$ $x_{j}(v)=1$ $c_{j}(v)>0$ $x_{j}(v)=0$ $C_{j}(v)=0$ $x_{j}(v)\in\{01\}$ $\mathrm{l}\mathrm{p}$ (integrality property) $\max\{_{i}\sum_{\epsilon M}vi \sum_{i\in Sj}v_{i}\leq c_{j}(j\in N)$ $v_{i}\geq 0(i\in M)\}$ $v^{*}$ 8( $v$ $i\in M$ (6) $s_{i}(v)=1- \sum_{nj\in}a_{ij^{x}}j(v)$ $v_{i}^{k+1}= \max\{v_{i}^{k}+\lambda\frac{ub-l(v^{k})}{ s(v)k 2}s_{i}(v^{k})$ $0\}$ $i\in M$ (7) $v^{\iota}$ $\ldots$ $L(v^{k})$ $v^{k}$ $v^{*}$ $v^{\theta}$ $UB$ $\lambda>0$

3 $<\rangle$ 213 $v^{\mathrm{o}}$ \mbox{\boldmath $\lambda$} [6] $v^{\mathrm{o}}$ $v_{i}^{0}:= \min\{\frac{c_{j}}{ S_{j} } i\in S_{j}\}$ (8) $\lambda$ \beta $=\lambda_{0}$ \mbox{\boldmath $\lambda$} $\lambda:=\lambda/\rho$ $\lambda<\lambda_{\min}$ $\lambda_{0}=4$ $\beta=15$ $\rho=12$ $\lambda_{\min}=0002$ $UB$ $x=0$ $u_{j}(x)$ $=$ $ \{i\in S_{j} \sum_{h\in N}aihx_{h}=0\} $ $r_{j}(x)$ $=$ $\frac{c_{j}}{u_{j}(x)}$ $r_{j}(x)$ ( $x_{j}:=1$ ) 32 $n$ 1 $N :=$ { $j\in N $ cj(v ) $\leq\gamma$ }( $\gamma$ ) 2 1 $ N $ $ N >5m$ $N $ $(v^{\phi})$ $i$ $i$ 3 j(v ) 5 $N $ $5m$ N $\forall j\in N-N $ $x_{j}=0$ 4 $x$ $NB(x)$ $x$ $NB(x)$ $x$ 41 $x\in\{01\}^{n}$ (2) (2) $i$ (2) \theta (x) $\theta_{i}(x)$ $=$ $\max\{1-\sum_{j\in N}$ aijxj $0\}$

4 $\dot{l}$ 214 $Pi(>0)$ pcost $(x)$ $=$ $\sum_{j\in N}\text{ }j^{x_{j}+}\sum_{i\epsilon M}pi\theta_{i(X)}$ (9) $x$ $x \in$ $\{01\}^{n}$ $d(x x )$ $=$ $ \{j\in N x_{j}\neq x_{j} \} $ $x$ $NB_{h}(x)$ $NB_{h}(x)$ $=$ $\{x \in\{01\}^{n} d(x x )\leq h\}$ $h$ $x$ $h\leq 3$ $h(\leq 3 )$ $NB_{h}(x)$ $n $ $=$ $\sum_{j\in N}x_{j}$ $t$ $=$ $\max\{_{i\in M}\sum aij j\in N\}$ $=$ $\max\{_{j\in N}\sum aij i\in M\}$ $h\geq 2$ $NB_{h-1}(x)$ $NB_{h}(X)$ $NB_{h}(x)$ pcost $(x)$ 1 $d(xx )=1$ $O(1)$ pcost $(x)$ $O(n)$ $O(tl)$ $O(n+tl)$ $d(xx^{j})=2$ $x_{j}=1$ $O(n )$ $x_{j}=0$ 1 $O(tl)$ $O(n^{;}t\iota)$ $d(irx )=3$ $x_{j}=1$ $O(n )$ $x_{j}=0$ 1 $O(\mathrm{I}\mathrm{n}\mathrm{i}\mathrm{n}\{nt\iota\})$ 1 $O(tl)$ $O(niJl \min\{nt\iota\}l)$

5 215 $NB_{3}(x)$ $O(n tl \min\{nt\iota\})$ $NB_{3}(x)$ $O(tn^{\mathrm{s}})$ $n \leq n$ $l\leq n$ $l\ll n$ 43 1 $p_{i}$ \langle 1 p $p_{i}$ $p_{i}$ $:= \min\{\frac{c_{j}}{ S_{j} } i\in S_{j}\}$ $x$ $UB$ $\text{ }osi(x)<ub-1$ $p_{i}$ $:=p_{i}(1+ \theta_{i(x)}\max\{\frac{ub-1-cost(_{x)}}{ub}:\delta^{+}\})$ $\theta_{i}(x)=\max\{1-\sum_{j\in N}$ aij xj $0\}$ $p_{i}$ $:=p_{i}(1+ \lambda_{i}(x)\min\{\frac{ub-1-\text{ }OSt(x)}{UB}$ $\Delta^{-}\})$ $\lambda_{i}(x)=\frac{\sum_{j\in N}a_{i}jXj+1}{\max_{i\in \mathit{1}u}\sum_{j\in N}a_{i}jXj+1}$ $\Delta^{-}$ $\Delta^{+}$ $\Delta^{+}>0$ $-1<\Delta^{-}<0$ cost$(x)<ub-1$ $x$ ( $UB$ ) $x$ cost $(\mathrm{z}j)\geq UB-l$ $x$ 44 $X_{j}$ 1 pcost $(x)$ $S_{j}$ $x_{j}$ $:=1$ $NB_{h}(x)(h\leq 3)$

6 $\mathrm{a}\mathrm{v}\mathrm{r}$ LS 1 31 $x$ $UB:=cost(X)$ 2 31 v $x:=0$ 3 $c_{j}(v^{\phi})$ 32 $:=0$ $:= \min\{\frac{c_{\mathrm{j}}}{ S_{j} } i\in S_{j}\}$ $p_{i}$ 4 $T$ (T ) $UB$ 5 $x$ $x:=$ 6 $UB $ ( $UB =\infty$) $UB <UB$ $UB:=UB $ 7 44 $x^{\mathrm{o}}$ $x^{\phi}$ cost $(X^{\mathrm{C}})<UB$ $UB:=\text{ }OSt(X^{\mathrm{o}})$ 8 43 $Pi$ 4 6 $\mathrm{c}$ $1\mathrm{G}\mathrm{B}$ $\mathrm{m}\mathrm{h}_{\mathrm{z}}$ Sun Ultra 2Model 2300 (300 memory) $//\mathrm{m}\mathrm{s}\mathrm{c}\mathrm{m}\mathrm{g}\mathrm{a}\mathrm{m}\mathrm{s}\mathrm{i}_{\mathrm{c}\mathrm{a}\mathrm{c}\mathrm{u}\mathrm{k}}/\mathrm{j}\mathrm{e}\mathrm{b}/\mathrm{o}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{b}/\mathrm{s}\mathrm{c}\mathrm{p}\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{h}\mathrm{t}\mathrm{m}1$ Beasely OR-Library (http: ) $\mathrm{e}\sim \mathrm{h}$ 1 - rail 61 2 $NB_{1}$ $NB_{2}$ $NB3$ 10 best known #best cost 10 3 *

7 Beasley $\mathrm{e}$ type $\mathrm{f}$ type $\mathrm{g}$ type $\mathrm{h}$ type $\mathrm{a}\mathrm{a}$ $n$ density cost range % [ % [ % [ $\frac{5\%[1100}{\mathrm{r}\mathrm{a}\mathrm{i} \%[12}$ rai % [1 2 rai % [1 2 rai % [1 2 rai % [1 2 rai % [1 2 $\mathrm{r}12$ rai % $\mathrm{e}$ $\mathrm{f}$ $\mathrm{h}$ $\mathrm{g}$ rail $NB_{1}$ $NB_{2}$ $NB_{3}$ $NB_{2}$ $NB_{3}$ rail $NB_{3}$ 62 3 JB Jacobs Brusco $\mathrm{b}\mathrm{c}$ [9] Chu [3] CNS Ceria Nobil Sassano CFT Caprara Fischetti Toth $[5][6]$ our LS $NB_{3}$ 10 $\min$ $\mathrm{a}\mathrm{v}\mathrm{r}$ $\max$ 10 $\mathrm{e}\sim \mathrm{h}$ 180 rail 507\sim rail 2536\sim [7] $\mathrm{j}\mathrm{b}$ 5 1 1/60 BC CNS CFT $\mathrm{e}\sim \mathrm{h}$ 1 rai1507\sim 582 1/30 rai12536\sim /6 * $\mathrm{e}\sim \mathrm{h}$ CFT rail $507\sim 582$ CNS CFT 2 30 rail 2536\sim 4872 rail CNS CFT 2 6 $\mathrm{e}\sim \mathrm{h}$ rail 2536\sim 4872 CNS CFT

8 218 2 best #best avr #best $\mathrm{a}\mathrm{v}\mathrm{r}$ $NB_{1}$ $NB_{2}$ $NB_{3}$ #best $\mathrm{a}\mathrm{v}\mathrm{r}$ $\frac{\mathrm{k}\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{n}(/10)\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(/10)\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(/10)\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}}{\mathrm{e}12910*29010*_{2}9010*290}$ e $*_{300}$ 10 $*300$ 10 $*300$ e $*270$ 10 $*270$ 10 $*270$ e $*280$ 10 $*280$ 10 $*280$ $\frac{\mathrm{e}52810*28010*28010*280}{\mathrm{f}11410*14010*14010*14\mathrm{o}}$ f $*150$ 10 $*150$ 10 $*150$ f $*140$ 10 $*_{140}$ 10 $*140$ f $*140$ 10 $*_{140}$ 10 $*140$ $\frac{\mathrm{f} \iota 0*13010*130}{\mathrm{g}117610*176010*176010*1760}$ g * $*1540$ g * *1660 g *1680 $\frac{\mathrm{g} *168010*1680}{\mathrm{h} * }$ h $*630$ 10 $*630$ h $*595$ h $*580$ 10 $*580$ 10 $*55$ $*550$ $\frac{\mathrm{h} }{\mathrm{r}\mathrm{a}\mathrm{i} *1744r)1745}$ rail $*1820$ 10 $*182$ 10 $*2110$ $ \frac{1\mathrm{a}\mathrm{i} }{\mathrm{r}\mathrm{a}\mathrm{i} * }$ 691 rail $*9592$ $\frac{ }{\mathrm{r}\mathrm{a}\mathrm{i} }-$ *10783 $\underline{\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{l}}$ *15481

9 $\mathrm{j}\mathrm{b}$ : $\mathrm{b}\mathrm{c}$ : $\mathrm{e}1$ 29 $\mathrm{e}2$ 30 $\mathrm{e}3$ 27 $\mathrm{e}4$ 28 $\mathrm{f}4$ 14 $\mathrm{g}4$ 168 &7 ( best JB BC CNS CFT $\mathrm{l}\mathrm{s}$ our $10$ runs) known (SA) $(\mathrm{g}\mathrm{a})$ $(\mathrm{l}\mathrm{h})$ $(\mathrm{l}\mathrm{h})$ $\mathrm{m}\mathrm{l}\overline{\mathrm{n}\max}$ avr $*29$ $*29$ $*29$ $*29$ $*29$ 290 $*30$ $*30$ $*30$ $*30$ $*30$ 300 $*27$ $*27$ $*_{27}$ $*27$ $*_{27}$ 270 $*_{28}$ $*28$ $*_{28}$ $*28$ $*28$ 280 $\frac{\mathrm{e}528*28*28-*28*28*2828\mathrm{o}}{\mathrm{f}114*14*14-*14*14*1\mathrm{f}215*15*15-*_{15}*_{1}5* }$ f3 14 $*14$ $*14$ $*_{14}$ $*14$ $*14$ 140 $*14$ $*14$ $*14$ $*14$ $*_{14}$ 140 $ \frac{\mathrm{f}5}{\mathrm{g}1}$ $17613$ $17814$ $**17613$ $**17613$ $*176-$ $**17613$ $**17613$ $17613\cdot 00$ g $*154$ $*154$ $*154$ 1540 g $*166$ 167 $*166$ $*_{166}$ $*_{166}$ $*_{168}$ 170 $*_{168}$ $*_{168}$ $*168$ 1680 $\backslash ^{*}168$ 168 $*168$ 169 $*168$ $*_{168}$ $*168$ 168 $\frac{\mathrm{g}5}{\mathrm{h} *63* }$ 0 h $*63$ $*63$ $*63$ 63 0 h $*59$ 60 $*59$ $*59$ h $*58$ 59 $*58$ $*58$ $*58$ 58 0 $\frac{\mathrm{h}5}{\mathrm{r}\mathrm{a}\mathrm{i}1507}$ $17455$ $*5-5$ $*5-5$ $*_{174}*55$ $*_{174}*55$ $**17455$ $*17555$ $1 \frac{550}{745}$ rail $*_{182}$ $*_{182}$ $*182$ $\frac{\mathrm{r}\mathrm{a}\mathrm{i} *211*211* \mathrm{o}}{\mathrm{r}\mathrm{a}\mathrm{i} *691* }$ rail $ $ $ $ $ $ $**106594_{\overline{l}}$ $ $ $ $ $ $ $\overline{\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{l} }$ rail *1534 $\underline{ }$ $\mathrm{j}\mathrm{a}\mathrm{c}\mathrm{o}\mathrm{b}_{\mathrm{s}}$ simulated annealing by Brusco [9] genetic algorithm by Beasley&Chu [3] CNS: Lagrangian-based heuristic by Ceria Nobili&Sassano [6] CFT: Lagrangian-based heuristic by Caprara Fischetti&Toth [5]

10 $ \mathrm{o}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{l}$ Solutions $ \mathrm{u}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}$ a Problems [1] $\mathrm{e}\mathrm{k}$ [2] $\mathrm{j}\mathrm{e}$ [3] $\mathrm{j}\mathrm{e}$ Baker $\mathrm{l}\mathrm{d}$ Bodin $\mathrm{w}\mathrm{f}$ $\mathrm{r}\mathrm{j}$ Finnegan and Ponder Eficient Heuristic Solutions to an Airline Crew Scheduling Problem AIIE Trans 11 (1976) Beasley A Lagrangean Heuristic for Set Covering Problems Naval Research Logististics 37 (1990) Chu A Genetic Algorithm for Set Covering Problem European Journal of $\mathrm{p}\mathrm{c}$ Beasley and Operational Research 94 (1996) [4] E Boros P L Hammer T Ibaraki and A Kogan Logical Analysis of Numerical Data Mathematical Programming 79 (1997) [5] A Caprara M Fischetti and P Toth A Heuristic Method for the Set Covering Problem Proceedings of the Fifth IPCO Conference Springer-Verlag (1996) [6] S Ceria P Nobili and A Sassano A Lagrangian-based heuristic for large-scale set covering problems Mathematical Programing 81 (1998) [7] $\mathrm{j}\mathrm{j}$ Dongarra Performance of Various Computers Using Standard Linear Equations Software Technical Report No CS Computer Science Department University of Tennessee July 1998 [8] $\mathrm{m}\mathrm{l}$ ( $\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}/\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{i}o\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$ Fisher and P Kedia of Set Heuristics Management Science 36 (1990) Using Dual [9] $\mathrm{l}\mathrm{w}$ [10] $\mathrm{b}\mathrm{m}$ $\mathrm{m}\mathrm{j}$ Jacobs and Brusco A Local-Search Heuristic for Large Set-Covering Problems Naval Research Logististics 42 (1995) Smith IMPACS-A Bus Crew Scheduling System Using Integer Programing Mathmatical Programing 42 (1988) [11] $\mathrm{f}\mathrm{j}$ ( $\mathrm{g}\mathrm{r}$ Vasko and Wilson Facility Location Algorithm to Solve Large Set Covering Problems Operations Research Letters 3 (1984) 85-90

モジュラリティ最大化問題に対する切除平面法に基づく発見的解法

モジュラリティ最大化問題に対する切除平面法に基づく発見的解法 1879 2014 15-27 15 (Yoichi Izunaga) * (Yoshitsugu Yamamoto) \dagger Newman and Girvan 1 SNS Newman and Girvan [11] 1 Brandes et al. [3] $NP$- [8], [12], [1] 2 1 2 [14]. 2 $n$ 60 1 0-1 Aloise et al. [2]