c オペレーションズ・リサーチ

混合整数 2 次錐計画法による回帰式の変数選択
宮代 隆平，高野 祐一
混合整数 2 次錐計画問題 (MISOCP) は，整数変数を含む 2 次錐計画問題 (SOCP) であり，2 次錐制約と整数変数の高い表現能力により多種多様な問題を定式化することができる．本稿ではその一例として，回帰式の変数選択問題を取り上げ，赤池情報量規準 (AIC) やベイズ情報量規準 (BIC) など，各種の情報量規準の最小化が混合整数 2 次錐計画問題として定式化できることを示す．

キーワード：混合整数 2 次錐計画法，変数選択，情報量規準，回帰分析[1, 2] などを参照されたい．

1. はじめに

SOCP の制約式 Ai x + bi  ≤ ci x + di は 2 次錐

1.1 本稿の目的制約と呼ばれるが，x x ≤ f · g（f ，g は非負のスカ

2 次錐計画問題 (Second-Order Cone Program;ラー変数）という形の制約式（hyperbolic 制約式）は，SOCP) は内点法を用いて効率的に解けることと，その以下のように 2 次錐制約として表現することができる：

高い表現能力から，近年注目を集めている．混合整数

2 次錐計画問題 (Mixed-Integer Second-Order ConeProgram; MISOCP) は，SOCP に変数の整数性が付x x ≤ f · g⇐⇒⎛⎞
2x⎝⎠ ≤ f + g .
 f −g 

加された問題である． MISOCP の魅力は，SOCP の表現能力に加えて，整数変数を用いた各種の定式化テ

これにより，線形計画問題などでは直接扱うことの難クニックが使えることである．本稿では，MISOCP がしかった双線形項 f · g を，限定された形式ではあるが多彩なクラスの問題を表せることの例として，統計学ダイレクトに記述できる．このことからも，SOCP がの回帰分析における変数選択問題を取り上げ，各種の高い表現能力を持つことが見てとれる．

情報量規準の最小化問題が MISOCP として定式化で混合整数 2 次錐計画問題 (MISOCP) とは，SOCPの一部または全ての変数に整数制約が課された問題できることを述べる．

1.2 2 次錐計画問題と混合整数 2 次錐計画問題

ある．MISOCP 自体は NP 困難であるが，整数制約2 次錐計画問題 (SOCP) の一般形は，以下のようにを連続緩和した問題は SOCP となり，内点法を用いて表される（ただしここで v = (v  v)1/2 ）：解くことができる．最近では，内点法ベースの分枝限定法が実装された，MISOCP を扱える数理計画ソル0minimizec x

バーが複数存在する．MISOCP についてより詳しく

subject toAi x + bi  ≤ ci x + diは，[3] などを参照されたい．

x(i = 1, 2, . . . , m) .

2. 回帰式の変数選択

SOCP は内点法を用いて多項式時間で解を求めること

2.1 変数選択とはができ，実際に近年の数理計画ソルバーではかなり大統計学における回帰分析では，説明変数と被説明変規模な問題まで解ける．SOCP についてより詳しくは，数の間の関係式（回帰式）を求めることが主要な目的となる．例えば，マンションの家賃を予測する場合にみやしろ りゅうへい
東京農工大学大学院工学研究院〒 184–8588 東京都小金井市中町 2–24–16
たかの ゆういち
専修大学ネットワーク情報学部〒 214–8580 神奈川県川崎市多摩区東三田 2–1–1

は，その説明変数として，総面積，築年数，立地，最寄り駅までの距離などが考えられるだろう．しかし，推定に使用するサンプル数に対して説明変数が非常に多い場合や，予測に有効ではない説明変数が含まれる場

c by ORSJ. Unauthorized reproduction of this article is prohibited.
732（28）Copyright 

オペレーションズ・リサーチ

合には，手元のデータには良く当てはまるが，未知のと表わされ，これらの値が小さいほど良いモデルとさデータに対しては予測性能が低い回帰式が得られてしれる．以下では主として AIC 値の最小化を例にとり説まうことがある．この現象は過剰適合と呼ばれる．

明を行うが，AIC，BIC 以外にも多数の適合度指標がこのようなときには，候補となる変数の中から有用提案されている（[11] などを参照のこと）．

な説明変数集合を選び出すことにより，過剰適合を軽2.3 変数選択に関する先行研究減して回帰式の予測性能を向上させることができる．

変数選択のための手法は，これまでに多くのものがまた，この説明変数集合を選び出す問題を変数選択問提案されているが [4, 8, 12, 13]，それらの大部分は題という．変数選択を行う利点としてはほかにも，回ヒューリスティクスとみなすことができる．その中で帰分析の結果の解釈が容易になることや，推定に必要も，最も一般的な手法はステップワイズ法 [14] であり，な計算量を削減できることなどがある [4]．

回帰式の適合度指標や説明変数の有意性に基づいて変回帰式の変数選択は，統計分野では古くから重要な数を 1 個ずつ追加／削除することを繰り返す方法であ

課題として知られている [5〜7]．また，機械学習やデーる．ステップワイズ法は R [15] や MATLAB [16] など

タマイニングの分野では特徴選択とも呼ばれ，扱うデーのソフトウェアに実装されており，計算も高速なためタ量の増加を背景に近年大きな注目を集めている [8]．

広く用いられているが，局所探索型のヒューリスティ

2.2 変数選択と情報量規準

クスであるため適合度指標の意味で最適なモデルを必

以下本稿では，線形回帰モデルに対する変数選択問ずしも出力しない．

題を考える．

一方で厳密解法としては，枝刈り操作を組み合わせn 個の観測値 (yi ; xi1 , xi2 , . . . , xik ) (i = 1, 2, . . . , n)

た総当り法 [17] や整数計画法 [18] がある．これらのが与えられ，yi を被説明変数，xij (j = 1, 2, . . . , k) を手法は 1970 年代から提案されていたが，当時は計算k 種類の説明変数とする．このとき，被説明変数の値機が非力だったために小さなサイズの問題しか扱うこを予測する回帰モデルは以下のように表される：とができず，あまり注目を集めなかったと考えられる．
しかし，計算機や数理計画ソルバーの性能が飛躍的に

yi = b + a1 xi1 + a2 xi2 + · · · + ak xik + εi ,(1)

ただし εi は i 番目の観測値の予測残差．

向上した現在では，これらの厳密解法を研究するための機は熟したと考え，筆者らは特に整数計画法を用いた解法に注目している．

このとき，候補となる p 種類の変数の中から最適な説

整数計画法を用いた変数選択では，選択する説明変数の個数を事前に指定するタイプの定式化が多い [18]〜明変数集合を選択する変数選択問題を考える．
一般に，説明変数を多く含むモデルは与えられたデー[21]．選択する説明変数の個数 k を定数と見なすと，関ni=1ε2i の最小化とタに対しては当てはまりが良いものの，未知のデータ数 (2) および関数 (3) の最小化はに対しては予測能力が低くなる．モデルの複雑さ（選等価になり，これは「p 個の説明変数候補から，残差 2択した説明変数の個数）とモデルの当てはまりの良さ乗和を最小化するように k 個の説明変数を選ぶ問題」（所与のデータに対する予測誤差の小ささ）とのバランになる．この問題は以下の混合整数 2 次計画問題としスを考慮した適合度指標の代表的なものとして，赤池情て定式化できることが知られている（例えば [19]）：

報量規準 (Akaike Information Criterion; AIC [9]) や
ベイズ情報量規準 (Bayesian Information Criterion;

BIC [10]) がある．回帰モデル (1) に対するいくつかの自然な仮定の下で，定数項を削除した AIC 値は

n logn log

2014 年 12 月号

a, b, ε, z1 2εin i=1n1 2εn i=1 in

ε2i

(4)

i=1

subject toε i = yi −b+p

aj xij(i = 1, 2, . . . , n) , (5)j=1+ 2k ,(2)定数項を削除した BIC 値は

minimize− M zj ≤ aj ≤ M zjp
zj = k ,(j = 1, 2, . . . , p) ,(6)(7)

j=1zj ∈ {0, 1}

n+ k log n(3)(j = 1, 2, . . . , p) ,(8)

ただし M は十分に大きい正の定数．

c by ORSJ. Unauthorized reproduction of this article is prohibited. （29）733
Copyright ここで連続変数 aj および b はそれぞれ推定すべき偏回帰係数および切片であり，εi は残差である．また変数 zj は 0-1 変数であり，p 個中の j 番目の説明変数候補をモデルに含めるとき 1，そうでないときに 0 をとるものと定義する．目的関数 (4) は残差 2 乗和の最小化を表しており，制約式 (5) は残差の定義そのものである．制約式 (6) は，zj = 0 の場合に j 番目の説明変数はモデルから取り除かれることを意味しており，制約式 (7) でモデルに含まれる説明変数の個数が k 個であることを定めている．
上記の問題は，凸 2 次関数を線形制約と整数制約の⇐⇒

minimize⇐⇒minimize⇐⇒minimize⇐⇒

minimizea, b, ε, k, za, b, ε, k, za, b, ε, k, za, b, ε, k, zn
i=1

項 exp(2k/n) ·1 22kε+n i=1 inn1 22kexp log
εi +n i=1nn

12k·exp
ε2nn i=1 in
2k·expε2ini=1nlog

ε2i の上界を表す連続変数 f を導入することにより，問題は以下の形に変形できる：

下で最小化する混合整数 2 次計画問題であり，既存のminimize

fsubject toは AIC 値や BIC 値を最小にする説明変数の個数は事n2kε2i ≤ f · exp −ni=1前にわからないという問題点がある．

制約式 (5)，(6)，(7)，(8).

数理計画ソルバーなどで扱える．しかしながら，このa, b, ε, f, k, z

定式化では k を所与の定数として扱っており，現実に,(10)

そこで次節では，AIC，BIC などの情報量規準に基づいて，説明変数の個数 k も同時に最適化する変数選次に，制約式 (10) の非線形性を解消する．新たな択問題が MISOCP として定式化できることを示す．ほ0-1 変数 wj (j = 0, 1, . . . , p) を定義し，wj に関してかにも筆者らのグループでは，自由度調整済み決定係

制約式数を指標とした定式化 [22]，Mallows の Cp を指標とpした定式化 [23]，多重共線性を考慮した定式化 [24] な

j=0どを提案しており，興味がある読者は各文献を参照していただきたい．

pwj = 1

j=0を付け加える．すると，制約式 (7) と (8) より k は常に整数値を取るため，wj は「j = k の時，またその時

3. MISOCP による情報量規準の最小化
AIC 最小化問題は，関数 (2) を最小化すればよいことから，直接的には以下の非線形混合整数計画問題として定式化できる（k も変数であることに注意）：

1 2εn i=1 iのみ wj = 1」を満たす 0-1 変数となる．この wj を用いることにより，非線形の制約式 (10) は以下の線形制約式で表現できる：

nminimizen log

subject to

制約式 (5)，(6)，(7)，(8).

a, b, ε, k, z(wj · j) = k,+ 2k(9)しかし，この定式化の目的関数 (9) は非凸な非線形関数であり，0-1 変数 zj の整数性を緩和したうえでもこの問題を解くことは困難である．整数計画問題に対し⇐⇒⇐⇒n2kε2i ≤ f · exp −ni=1n2kε2i ≤ f · g, g = exp −
ni=1
⎧pn


⎪2j2
⎪
⎪
wj ·exp −⎪ εi ≤ f · g, g =
⎨
ni=1
j=0
pp


⎪
⎪
⎪
(wj · j),wj = 1.
⎪⎩k =j=0,j=0て分枝限定法がうまく働くには，その連続緩和問題がpj=0(wj · exp(−2j/n)) は，変数効率的に解ける形になっている必要がある．以下ではここで制約式 g =それを念頭におき，問題を等価変形する．

wj に関して線形であることに留意されたい（この線形

まず，目的関数 (9) を次のように変換する．

minimizea, b, ε, k, zn log

化手法は SOS type 1 [25, 26] として整数計画の分野で古くから知られている）．制約式

1 2εin i=1n+ 2kni=1ε2i ≤ f · g は非線形であるが，これは 1.2 節で説明したように 2 次錐制約として表現可能である．
これらをまとめ，AIC 最小化問題の定式化として以c by ORSJ. Unauthorized reproduction of this article is prohibited.
734（30）Copyright 

オペレーションズ・リサーチ

下を得る：

表 1 データのリスト

minimizea, b, ε, fg, k, w, zf

略称

subject toε i = yi −b+pnε2i ≤ f · g,g=i=1p

aj xijj=1p

(i = 1, 2, . . . , n),
wj · exp −j=0(wj · j) = k,j=0p

p

wj = 1,j=0− M zj ≤ aj ≤ M zj

2jn,zj = k,j=1(j = 0, 1, . . . , p),zj ∈ {0, 1}(j = 1, 2, . . . , p).

データセット [32]Housing
ServoAuto MPG
Solar Flare (C-class)Solar Flare (M-class)Solar Flare (X-class)
Breast Cancer Wisconsin
Forest Fires
Automobile
Communities and Crime

公開されている 10 種類の回帰分析用のデータセットを使用した（表 1）．なお，MISOCP を解く際に生じこの定式化で表される問題は，線形制約，2 次錐制約，整数制約の下で線形目的関数を最小化する MISOCPである．

wj · exp −j=0

る数値的不安定性を軽減するために，量的変数は全て平均 0，標準偏差 1 に正規化した．

MISOCP の計算には数理計画ソルバー IBM ILOG
CPLEX 12.5 [33] を使用した．計算機環境は，CPU:

また上記の定式化のうち，制約式pnp
506 13167 19392 25
1066 26
1066 26
1066 26
194 32517 63
159 65
1993 100(j = 1, 2, . . . , p),wj ∈ {0, 1}

g=Housing
ServoAutoMPG
SolarFlareC
SolarFlareM
SolarFlareX
BreastCancer
ForestFires
Automobile
CrimeIntel Xeon W5590 3.33 GHz×2; RAM: 24 GB; OS:64bit Windows 7 Ultimate SP1; チップセット：2jn

Intel 5520 のマシンを使用し，各 MISOCP に対して並列分枝限定法（8 スレッド）を最大 12,000 秒実行した．また比較のため，MATLAB R2012b [16] のを制約式

g=p
j=0j log nwj · exp −npwj · n−j/n=j=0

LinearModel.stepwise 関数を用いて，ステップワイズ法による変数選択を行った．こちらの計算機環境はCPU: Intel Core i7-2600S 2.80 GHz; RAM: 8 GB;
OS: 64bit Windows 7 Professional SP1; チップセッに置きかえることにより，BIC 最小化問題を MISOCPとして定式化できる．さらに，AIC の有限修正 (cor-rected AIC; [27])，Hannan-Quinn 情報量規準 (HQ;[28])，残差情報量規準 (RIC; [29, 30]) などの様々な情報量規準の最小化問題，あるいは自由度調整済み決定係数 R̄2 [31] の最大化問題も同様に MISOCP として定式化できるが，ここでは省略する．詳細は [22] を参照されたい．
なお，より一般的に線形制約の下で「log f1 (x) +f2 (k); ただし f1 は凸 2 次関数，k は整数変数（f2 の凸性は不要）」の形の目的関数を最小化する問題も，同様の変形により MISOCP として定式化できることを述べておく．

ト：Intel Q67 Express である．
表 2 に AIC 最小化の，表 3 に BIC 最小化の計算機実験の結果を示す．「手法」はそれぞれ• SWconst：切片のみのモデルから開始するステップ
ワイズ変数選択• SWall ：全ての候補変数を含むモデルから開始するステップワイズ変数選択• MISOCP：MISOCP を用いた変数選択を意味し，AIC 値または BIC 値が最も良かった手法の値を太字で示してある．また k は選択された説明変数の個数である．なお計算時間については，MISOCPの計算が 12,000 秒を超えた場合は分枝限定法を打ち切った．そのため，その場合は得られた説明変数集合

4. 計算機実験および考察は最適解とは限らない．

本節では，AIC および BIC の最小化を目的とした変によって得られた解は，選択された変数集合がかなり数選択問題に関する計算機実験の結果を紹介する．実異なっていることがわかる．SWconst と SWall では k

験には，UCI Machine Learning Repository [32] での値がかなり異なるほか，特に Automobile では AIC

計算結果を見ると，まず 2 種類のステップワイズ法

2014 年 12 月号

c by ORSJ. Unauthorized reproduction of this article is prohibited. （31）735
Copyright 表 2 AIC 最小化の実験結果

Housingn506

p13Servo16719

AutoMPG39225

SolarFlareC

106626SolarFlareM

1066

26

SolarFlareX

1066

26

BreastCancer

194

32

ForestFires

517

63

Automobile

159

65

Crime

1993

100

データ

手法

SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP

AIC 値
776.36776.36776.36258.66266.36258.66333.22339.44333.222816.34
2819.732816.34
2926.932926.932926.932882.812882.812882.81509.72510.58508.731429.811429.811430.25−26.87−47.50−58.493424.26
3410.923419.65

k11111191491519159139777333814101212132138
32
4150
51

計算時間（秒）

1.31
0.51
10.62
1.85
0.75
8.41
3.96
1.59
51.23
3.09
4.02
227.25
2.38
5.99
92.18
1.20
7.59
10.73
3.07
8.13
10637.66
9.56
71.19> 12000
14.20
24.75> 12000
84.94
312.82> 12000

値で 20 以上の差，BIC 値で 10 以上の差があり，これ法よりかなり長い時間を要している．これもヒューリは無視できない差と言える．またこれらの結果から，ススティクスと厳密解法との性質の違いではあるが，特テップワイズ法を用いる場合には，SWconst と SWallに MISOCP では分枝限定法の実行中に解くべき連続の両方を試すべきだという知見が得られる．

緩和問題が SOCP になり内点法が必要となるため，通次に，p < 30 であるような小さなデータセットに対常の線形整数計画問題のように双対単体法を利用した

しては，MISOCP は数分以内に最適解を計算できてホットスタートが働かない．これが計算時間増大の理いることがわかる．また，p > 60 であるような大きな由であると考えられる．また，概して AIC 最小化よりデータセットに対しては，12,000 秒以内に最適解を求BIC 最小化の方が MISOCP による計算時間が短いが，めることはできていないが，その場合でも 2 種類のス

これは AIC より BIC の方が説明変数の個数にかかるテップワイズ法とほぼ同等またはそれ以上の解を出力ペナルティが大きいことによるものと思われる．

している．特に Automobile では，SWconst と SWallの良い方と比較しても AIC 値，BIC 値ともに 10 以上小さな変数集合を得ている．もちろん，もとよりス

5. おわりに
本稿では，回帰式の変数選択における情報量規準のテップワイズ法は解の最適性を保証するものではない最小化問題について，MISOCP による定式化を紹介が，変数選択の結果が重要な意味を持つ事例においてした．SOCP は hyperbolic 制約式のような非線形関は MISOCP による手法を試す価値があると思われる．

数を直接扱うことができ，さらに MISOCP では整数計算時間に関しては，MISOCP はステップワイズ

計画法の様々な定式化テクニックも利用することがでc by ORSJ. Unauthorized reproduction of this article is prohibited.
736（32）Copyright 

オペレーションズ・リサーチ

表3

Housingn506p13Servo167

19

AutoMPG

39225

SolarFlareC

106626

SolarFlareM

106626

SolarFlareX

106626BreastCancer

194

32

ForestFires

517

63

Automobile

15965

Crime

1993

100

データ

BIC 最小化の実験結果
手法

SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP
SWconstSWall
MISOCP

きる．特に本稿では変数選択を 0-1 変数によって表し，非線形関数の線形化手法を利用して非凸非線形な目的関数を持つ情報量基準最小化問題を MISOCP に等価変形する方法を示した．
このように，SOCP の表現能力と整数計画法の定式化手法を活用することで，非常に広いクラスの問題がMISOCP として定式化できる．一方で，本稿の計算機実験でも観察されたように，分枝限定法においてホットスタートが働かないことが足かせとなり，MISOCPは計算時間の面で苦しくなる場合があることは否めない．また，SOCP を解く際の数値的不安定性が原因となって分枝限定法の計算が破綻するようなケースもあり，現時点では MISOCP として定式化することが有効な問題かどうかを見極めることが必要であると言える．MISOCP がその真価を発揮するためにも，解法のさらなる安定化と高速化が期待されている．

2014 年 12 月号

BIC 値
834.88827.07827.07288.93303.87288.93390.96405.71390.962855.932855.892855.892956.022954.422954.422900.122900.122900.12529.28528.90527.861463.811463.811463.81
31.28
42.59
20.81
3574.683594.843591.94

謝辞

k811118118
1114
11666444222333333
15
27
23
13
22
16

計算時間（秒）

1.04
0.47
13.26
1.60
1.50
10.51
3.20
2.92
59.92
2.04
6.51
73.73
1.52
6.96
20.59
0.93
7.83
5.52
1.34
11.70
1198.73
2.82
71.63> 12000
10.56
35.19> 12000
24.92
390.06> 12000

本研究の一部は JSPS 科研費 26560165 の助成を受けたものである．
参考文献[1] M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, “Applications of second-order cone programming,” Linear Algebra and its Applications, 284,
193–228, 1998.
[2] F. Alizadeh and D. Goldfarb, “Second-order coneprogramming,” Mathematical Programming, 95, 3–51,2003.
[3] H. Y. Benson and Ü. Sağram, “Mixed-integer
second-order cone programming: A survey,” 2013
Tutorials in Operations Research: Theory Driven
by Influential Applications, H. Topaloglu and J. C.
Smith (eds.), INFORMS, pp. 13–36, 2013.
[4] I. Guyon and A. Elisseeﬀ, “An introduction to variable and feature selection,” Journal of Machine Learning Research, 3, 1157–1182, 2003.
[5] K. P. Burnham and D. R. Anderson, Model Selection and Multimodel Inference: A Practical Information Theoretic Approach, 2nd ed., Springer, 2002.

c by ORSJ. Unauthorized reproduction of this article is prohibited. （33）737
Copyright [6] R. R. Hocking, “The analysis and selection of variables in linear regression,”Biometrics, 32, 1–49, 1976.
[7] A. Miller, Subset Selection in Regression, 2nd ed.,
Chapman and Hall/CRC, 2002.
[8] H. Liu and H. Motoda, Computational Methods ofFeature Selection, Chapman and Hall/CRC, 2007.
[9] H. Akaike, “A new look at the statistical model identiﬁcation,” IEEE Transactions on Automatic Control,19, 716–723, 1974.
[10] G. Schwarz, “Estimating the dimension of amodel,” Annals of Statistics, 6, 461–464, 1978.
『情報量規準（シリーズ・予測[11] 小西貞則，北川源四郎，と発見の科学 2）』，朝倉書店，2004.
[12] A. L. Blum and P. Langley, “Selection of relevant
features and examples in machine learning,” ArtificialIntelligence, 97, 245–271, 1997.
[13] R. Kohavi and G. H. John, “Wrappers for feature
subset selection,” Artificial Intelligence, 97, 273–324,
1997.
[14] M. A. Efroymson, “Multiple regression analysis,”
Mathematical Methods for Digital Computers, A. Ralston and H. S. Wilf (eds.), Wiley, pp. 191–203, 1960.
[15] R Core Team, “R: A language and environment
for statistical computing,” R Foundation for Statistical Computing, http://www.R-project.org（2014年9月1 日閲覧）
[16] The MathWorks Inc., MATLAB R2012b, 2012.
[17] G. M. Furnival and R. W. Wilson Jr., “Regressions
by leaps and bounds,” Technometrics, 16, 499–511,
1974.
[18] T. S. Arthanari and Y. Dodge, Mathematical Programming in Statistics, John Wiley & Sons, 1981.
[19] D. Bertsimas and R. Shioda, “Algorithm for
cardinality-constrained
quadraticoptimization,”
Computational Optimization and Applications, 43,
1–22, 2009.
[20] H. Konno and Y. Takaya, “Multi-step methods forchoosing the best set of variables in regression analysis,” Computational Optimization and Applications,46, 417–426, 2010.
[21] H. Konno and R. Yamamoto, “Choosing the best
set of variables in regression analysis using integer programming,” Journal of Global Optimization, 44, 272–282, 2009.

[22] R. Miyashiro and Y. Takano, “Mixed integer
second-order cone programming formulations for variable selection,” Technical Report 2013-7, Departmentof Industrial Engineering and Management, Tokyo
Institute of Technology, 2013, http://www.me.titech.
ac.jp/technicalreport/h25/2013-7.pdf[23] R. Miyashiro and Y. Takano, “Subset selection
by Mallows’ Cp : A mixed integer programming approach,” Expert Systems with Applications, 42, 325–331, 2015.
[24] 小林健，高野祐一，宮代隆平，中田和秀， 多重共線性を考慮した回帰式の変数選択―混合整数半正定値計画法を用いた解法―， 日本オペレーションズ・リサーチ学会 2014
年秋季研究発表会アブストラクト集，164–165, 2014.
[25] E. M. L. Beale, “Two transportation problems,”
Proceedings of the 3rd International Conference on
Operational Research, 780–788, 1963.
[26] E. M. L. Beale and J. A. Tomlin, “Special facilities in a general mathematical programming system
for non-convex problems using ordered sets of variables,” Proceedings of the 5th International Conference on Operational Research, 447–454, 1970.
[27] N. Sugiura, “Further analysts of the data by
Akaike’s information criterion and the ﬁnite corrections,” Communications in Statistics — Theory andMethods, 7, 13–26, 1978.
[28] E. J. Hannan and B. G. Quinn, “The determination of the order of an autoregression,” Journal of theRoyal Statistical Society, Series B, 41, 190–195, 1979.
[29] C. Leng, “The residual information criterion, corrected,” arXiv, 0711.1918v1, 2013, http://arxiv.org/pdf/0711.1918.pdf[30] P. Shi and C.-L. Tsai, “Regression model selection:
A residual likelihood approach,” Journal of the Royal
Statistical Society, Series B, 64, 237–252, 2002.
[31] R. J. Wherry, “A new formula for predicting theshrinkage of the coeﬃcient of multiple correlation,”
The Annals of Mathematical Statistics, 2, 440–457,1931.
[32] K. Bache and M. Lichman, UCI Machine Learning
Repository, University of California, 2013,
http://archive.ics.uci.edu/ml[33] IBM ILOG, IBM ILOG CPLEX 12.5, 2012.

c by ORSJ. Unauthorized reproduction of this article is prohibited.
738（34）Copyright 

オペレーションズ・リサーチ