%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 特定領域研究(B)「新しいパラダイムとしてのアルゴリズム工学」
% 研究成果報告書 サンプル
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[a4j,11pt]{jarticle}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% パラメータの変更はしないようお願いいたします．
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\headheight}{0mm}
\setlength{\marginparwidth}{0mm}
\setlength{\topmargin}{-9mm}        % 上マージンの調節
\setlength{\oddsidemargin}{-6mm}    % 左マージンの調節
\setlength{\textwidth}{170mm}        % 印刷部分の幅
\setlength{\textheight}{240mm}       % 印刷部分の高さ
\setlength{\columnsep}{8mm}          % 2段組の間のスペース幅
\renewcommand{\baselinestretch}{1} % 行間

\newenvironment{ronbunlist}{%
\def\theenumi{1-\arabic{enumi})} 
\def\labelenumi{\theenumi}
\subsection*{学術誌等研究論文}
\begin{enumerate}}{%
\end{enumerate}}

\newenvironment{talklist}{%
\def\theenumi{2-\arabic{enumi})} 
\def\labelenumi{\theenumi}
\subsection*{口頭発表}
\begin{enumerate}}{%
\end{enumerate}}

\newenvironment{chosholist}{%
\def\theenumi{3-\arabic{enumi})} 
\def\labelenumi{\theenumi}
\subsection*{著書，解説，出版物等}
\begin{enumerate}}{%
\end{enumerate}}

\newcommand{\ronbun}[7]{%
\def\lbl{#1}
\def\vol{#5}
\def\pages{#6}
\ifx\lbl\empty{
  \ifx\vol\empty{
    \ifx\pages\empty{\item {#2}: {#3}, {\it #4}, {#7}.}
    \else{\item {#2}: {#3}, {\it #4}, {#6}, {#7}.}\fi}
  \else{
    \ifx\pages\empty{\item {#2}: {#3}, {\it #4}, {#5}, {#7}.}
    \else{\item {#2}: {#3}, {\it #4}, {#5}, {#6}, {#7}.}\fi}
  \fi}
\else{
  \ifx\vol\empty{
    \ifx\pages\empty{\item\label{#1} {#2}: {#3}, {\it #4}, {#7}.}
    \else{\item\label{#1} {#2}: {#3}, {\it #4}, {#6}, {#7}.}\fi}
  \else{
    \ifx\pages\empty{\item\label{#1} {#2}: {#3}, {\it #4}, {#5}, {#7}.}
    \else{\item\label{#1} {#2}: {#3}, {\it #4}, {#5}, {#6}, {#7}.}\fi}
  \fi}
\fi
}
\def\talk{\ronbun}

\newcommand{\chosho}[5]{%
\def\lbl{#1}
\ifx\lbl\empty{\item #2: #3, #4, #5.}
\else{\item\label{#1} #2: #3, #4, #5.}
\fi
}

\pagestyle{empty}

\begin{document}
\begin{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% タイトルページ
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%-------------------------------------------------------
% 研究課題 (日本語と英語両方)
%-------------------------------------------------------
文部科学省科学研究費補助金 特定領域研究(B)(2) (課題番号 10205211)

\bigskip
{\LARGE\bf メタヒューリスティクスによる\\
 計算困難問題の解決に関する研究\\
}

\medskip
{\large\bf Solving Computationally Hard Problems by Meta-Heuristics \\}

%-------------------------------------------------------
% 成果概要
%-------------------------------------------------------
\bigskip
\begin{quote}
 ＊＊＊＊＊＊＊　　　　　この成果報告書はサンプルです\hfill＊＊＊＊＊＊＊\\
 ＊＊＊＊＊＊＊　 ページ数も少なく，決して完成版ではありませんが，
 \hfill＊＊＊＊＊＊＊\\
 ＊＊＊＊＊＊＊　 　　　　原稿の体裁の参考にしてください\hfill＊＊＊＊＊＊＊\\
 現実社会に現れる組合せ最適化問題の解法として，
 局所探索を基盤に，タブー探索，遺伝アルゴリズム，アニーリング法など
 いわゆるヒューリスティクスと称される手法が種々提案され，
 精度の高い近似解を効率よく求めるために大きな成果を上げつつある．
 本研究の目的は，幾つかの組合せ最適化問題に対してメタヒューリスティクスに
 基づく高性能のアルゴリズムを開発することで，
 実用性の高いソフトウェアを構築することである．
 具体的にはタブー探索およびその変形を中心に，
 探索空間・近傍の影響を考慮しながら設計を進めた．
 資源制約スケジューリング問題，勤務スケジューリング問題，
 多資源一般化割当問題，配送計画問題，切断問題，詰込み問題など，
 いくつかの標準問題に対してソフトウェア開発を行い，
 汎用問題解決システムの基本となるソフトウェア群を充実させた．
\end{quote}

%-------------------------------------------------------
% 研究組織
%-------------------------------------------------------
\subsection*{研究組織 (平成10年度〜平成12年度)}

\begin{tabular}{ll}
 研究代表者: & 茨木 俊秀 (京都大学大学院・情報学研究科・教授) \\\\
 研究分担者: & 柳浦 睦憲 (京都大学大学院・情報学研究科・講師) \\
             & 堀山 貴史 (奈良先端科学技術大学院大学・情報科学研究科・助手) 平成11・12年度 \\
             & 野々部 宏司 (京都大学大学院・情報学研究科・助手) 平成12年度\\
             & 品野 勇治 (東京農工大学・工学研究科・講師) 平成12年度\\
\end{tabular}

%-------------------------------------------------------
% 補助金額
%-------------------------------------------------------
\subsection*{補助金額}
\begin{tabular}{c@{\hspace{1cm}}r}
 平成10年度 & 3,800千円\\
 平成11年度 & 4,100千円\\
 平成12年度 & 2,900千円\\
 \hline
 合計 & 10,800千円
\end{tabular}

%-------------------------------------------------------
% 補助金による主な研究活動
%-------------------------------------------------------
\subsection*{補助金による主な研究活動}
\begin{quote}
\begin{itemize}
 \item 国際会議における研究成果発表

       INFORMS (シアトル, 1998年), MIC (ブラジル, 1999年), 
       IFORS (北京, 1999年), APORS (シンガポール, 2000年),
       ISMP (アトランタ, 2000年)など.

 \item 計算機を用いた数値実験

       ワークステーション Sun Ultra 2 × 2台\\
       IBMノートパソコン Think Pad 240Z × 1台\\
       
\end{itemize}
\end{quote}

\end{center}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ここから本文
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{はじめに}
社会や産業界で解決を求められている問題を数学的にモデル化すると，
組合せ最適化問題となることが少なくない．
しかし，それらを厳密に解くことの困難さが,
NP困難性に代表される計算の複雑さの理論により明らかにされている．
そこで，これら大規模で困難な最適化問題を現実的に解くために，
近似アルゴリズム，確率アルゴリズム，並列/分散アルゴリズムなど
様々なタイプのアルゴリズムが提案されており，研究が進められている．
その結果，最適に近い解を短時間で求め得るという意味で，
今まで解けなかったような大規模な計算困難問題を実用的に解き得ることが，
数多くの研究成果によって確認されつつある．
とりわけ，近似アルゴリズムの種々のエレメントを統合し，
より高度な性能を実現するメタヒューリスティクスの考え方は注目を浴びており，
この枠組みに基づくアルゴリズムの開発と計算実験が
多くの研究者によって精力的に進められている．

本研究の目的は，メタヒューリスティクスのよる実用性の高いソフトウェアを
構築することである.
そのために，まずメタヒューリスティクスに基づくアルゴリズムの性能を決定する
要因に関する基礎研究を行い，これらの研究に基づいて，
高性能アルゴリズムの開発を進めた．
%ただし，個々の組合せ最適化問題ごとにアルゴリズムを開発するのは，
%仮に高性能が期待できるにしても，開発に要するマンパワーを考えると
%現実的ではない．
ここで，ターゲットとすべき組合せ最適化問題としては，
広範な問題を含む汎用性の高い問題を中心に考え，
同じアルゴリズムで多様な問題を扱い得る実用性の高いソフトウェア開発を目指した．

以下では，本研究の成果として得られたソフトウェアについて説明する．

\section{標準問題}
一つのアルゴリズムであらゆる組合せ最適化問題を扱うためには，
汎用性の非常に高い標準問題を一つ定めて，
すべてをその問題に定式化する必要がある．
従来，このような目的に整数計画問題が用いられてきた．
すなわち，解くべき問題を整数計画問題に定式化したのち，
整数計画アルゴリズムで最適解を求めるという手順がとられてきた．
このアプローチは一定の成功を収めてはいるが，整数計画問題では，
制約条件や目的関数を線形の方程式あるいは不等式で記述することを
前提としているため，問題によっては自然な定式化が可能とは限らない．

このように，現実問題の多様性を考えると，整数計画問題，
あるいは整数計画問題に代わる標準問題を一つ用意し，
そのアルゴリズムですべての問題を解決するというアプローチは適当ではなく，
個々の問題の特殊構造をある程度は取り込めるように，
複数の標準問題を準備するのが現実的である．
この考え方に従い，本研究では以下の問題を標準問題として採用した:
\begin{itemize}
 \itemsep=0pt
 \item (重み付き)制約充足問題 ((Weighted) Constraint Satisfaction Problem, CSP, WCSP) 
 \item 最大充足可能性問題 (MAXimum SATisfiability problem, MAX-SAT)  
 \item 一般化割当問題 (Generalized Assignment Problem, GAP)  
 \item 多資源一般化割当問題 (Multi-resource Generalized Assignment Problem, MGAP)  
 \item 一般化二次割当問題 (Generalized Quadratic Assignment Problem, GQAP)  
 \item 集合被覆問題 (Set Covering Problem, SCP)  
 \item 資源制約スケジューリング問題 (Resource Constrained Project Scheduling Problem, RCPSP)  
 \item 勤務スケジューリング問題 (Shift Scheduling Problem, SSP)  
 \item 長方形詰込み問題 (Rectangle Packing Problem, RPP)  
 \item 配送計画問題 (Vehicle Routing Problem, VRP)  
 \item 切断問題 (Cutting STock Problem, CSTP)
\end{itemize}

\subsection{標準問題の拡張}
上述の問題はいずれも代表的な組合せ最適化問題であり，
メタヒューリスティクスのアルゴリズムについてもすでに
かなりの研究があるものが多い．
本研究では，より実用性の高いソフトウェアにまとめあげるため，
従来研究されてきた問題の枠組みを拡張することで適用範囲の拡大を図った．

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
%RCPSP,VRP,PP,MGAP,GQAP

\section{アルゴリズムの開発}
メタヒューリスティクスに含まれる代表的なアルゴリズムの枠組みには
次のようなものがある．
\begin{itemize}
 \itemsep=0pt
 \item 局所探索および反復局所探索
 \item アニーリング法
 \item タブー探索
 \item 遺伝アルゴリズム
 \item ニューラルネットワーク  
\end{itemize}
これらはそれぞれ特徴をもつが，一般的には，
次の手順にしたがって(一般化)局所探索を反復するものである．
\begin{enumerate}
 \itemsep=0pt
 \item (過去の履歴に基づいて)初期解 $x$ を生成する．
 \item $x$ を(一般化)局所探索法により改善する．
 \item 以上の手順を終了条件が成立するまで反復する．
\end{enumerate}
具体的に各ステップをどう実現するかは，
アルゴリズムの枠組みや対象とする問題によって異なるため，
高い性能が得られるよう十分考慮し，計算実験を通して完成させていく必要がある．
とくに，メタヒューリスティクスの基本となる局所探索をどのように行うか，
すなわち，「解をどう表現するか(探索空間)」「解をどう修正するか(近傍)」
「解をどう評価するか(評価関数)」は
アルゴリズムの性能を決定づける要因であり，慎重に検討する必要がある．
以下では，本研究で得られた成果を例に，これら3つの要素について述べる．

\subsection{探索空間}
%GAP, RCPSP, PP
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

\subsection{近傍}
%GAP, VRP 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

\subsection{評価関数}
%GAP, SCP, CSP
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 


\section{汎用問題解決システムへの発展}
本研究の成果として得られたアルゴリズムは，
単体として用いても大きな効果があり，
すでに実用的な応用で利用されているものもある．
しかし，全体を一つの汎用問題解決システムにまとめあげることで，
より実用性を高めることができると考えられる．
今後，システム化にともなう問題点の洗い出しと，入出力ソフトウェアの開発など，
利便性も考慮した研究を進めて行く予定である．

なお，これらのアルゴリズムは，
本特定研究の成果物となるアルゴリズム・データベースに置き，
一般の利用に供す予定である．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 研究発表：論文リスト
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{研究発表}
%-------------------------------------------------------
% 学術誌等研究論文
%-------------------------------------------------------
\begin{ronbunlist}
 %%%%%%%%%%%%%%%%%%%% 平成10年度 %%%%%%%%%%%%%%%%%%%%
 \ronbun{}{Nonobe,~K., Ibaraki,~T.}
 {A tabu search approach for the constraint satisfaction problem as a general problem solver}
 {European Journal of Operational Research}
 {Vol.~106}
 {pp.~599--623}
 {1998}
 %
 \ronbun{}{Yagiura,~M., Ibaraki,~T.}
 {Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT}
 {Computing and Combinatorics (COCOON'98), edited by Hsu,~W.~-L., Kao,~M.~-Y.}
 {Springer Lecture Notes in Computer Science, Vol.~1449} 
 {pp.~105--116} 
 {1998}
 %
 \ronbun{}{阿瀬始, 茨木俊秀}
 {給油施設操業スケジューリング}
 {システム制御情報学会論文誌}
 {Vol.~11}
 {pp.~223--232}
 {1998}
 %
 \ronbun{}{永持仁, 牧野和久, 曽道智, 村田真紀, 茨木俊秀}
 {初等的フローゲームの凸性について}
 {電子情報通信学会論文誌 D-I}
 {Vol.~J81-D-I}
 {pp.~666--676} % ページを空にしてください．
 {1998}
 %
 \ronbun{}{Uno,~Y., Ibaraki,~T.}
 {Reachability problems of random digraphs}
 {IEICE Transactions}
 {Vol.~E81-A}
 {pp.~2694--2702}
 {1998}
 %
 \ronbun{}{Yagiura,~M., Yamaguchi,~T., Ibaraki,~T.}
 {A variable depth search algorithm with branching search for the generalized assignment problem}
 {Optimization Methods and Software}
 {Vol.10} % 巻号を空にしてください．
 {pp.~419--441} % ページを空にしてください．
 {1998}
 %
 %%%%%%%%%%%%%%%%%%%% 平成11年度 %%%%%%%%%%%%%%%%%%%%
 \ronbun{}{阿瀬始, 茨木俊秀, 柳浦睦憲}
 {機械式立体駐車場出庫スケジューリング}
 {システム制御情報学会論文誌}
 {Vol.~12}
 {pp.~417--427}
 {1999}
 %
 \ronbun{}{Boros,~E., Crama,~Y., Ekin,~O., Hammer,~P.L., Ibaraki,~T., Kogan,~A.}
 {Boolean normal forms, shellability and reliability computations}
 {SIAM Journal on Discrete Mathematics}
 {Vol.~13}
 {pp.~212--226}
 {2000}
 %
 \ronbun{}{Boros,~E., Hammer,~P.L., Ibaraki,~T., Kogan,~A., Mayoraz,~E., Muchnik,~I.}
 {An Implementation of Logical Analysis of Data}
 {IEEE Trans. on Knowledge and Data Engineering}
 {Vol.~12}
 {pp.~292--306}
 {2000}
 %
 \ronbun{}{Boros,~E., Ibaraki,~T., Makino,~K.}
 {Logical Analysis of Binary Data with Missing Bits}
 {Artificial Intelligence}
 {Vol.~107}
 {pp.~219--264}
 {1999}
 %
 \ronbun{}{Deng,~X., Ibaraki,~T., Nagamochi,~H.}
 {Algorithmic Aspects of the Core of Combinatorial Optimization Games}
 {Mathematics of Operations Research}
 {Vol.~24}
 {pp.~751--766}
 {1999}
 %
 \ronbun{}{Eiter,~T., Ibaraki,~T., Makino,~K.}
 {Computing Intersections of Horn Theories for Reasoning with Models}
 {Artificial Intelligence}
 {Vol.~110}
 {pp.~57--101}
 {1999}
 %
 \ronbun{}{Eiter,~T., Ibaraki,~T., Makino,~K.}
 {On the Difference of Horn Theories}
 {Theoretical Aspects of Computing (STACS'99), Meinel et al. (eds), Trier (Germany), Springer LNCS}
 {}
 {}
 {1999}
 %
 \ronbun{}{Eiter,~T., Ibaraki,~T., Makino,~K.}
 {Bidual Horn Functions and Extensions}
 {Discrete Applied Mathematics}
 {Vol.~96--97}
 {pp.~55--88}
 {1999}
 %
 \ronbun{}{Horiyama,~T., Ibaraki,~T.}
 {Ordered Binary Decision Diagrams Representing Knowledge-Bases}
 {Proceedings of the 1st Japanese-Hungarian Symposium on Discrete
 Mathematics and Its Applications, Kyoto}
 {}
 {pp.~167--174}
 {1999}
 %
 \ronbun{}{Horiyama,~T., Ibaraki,~T.}
 {Ordered Binary Decision Diagrams as Knowledge-Bases}
 {Proceedings of ISAAC '99, LNCS}
 {Vol.~1741}
 {pp.~83--92}
 {1999}
 %
 \ronbun{}{Ibaraki,~T., Kogan,~A., Makino,~K.}
 {Functional Dependencies in Horn Theories}
 {Artificial Intelligence}
 {Vol.~108}
 {pp.~1--30}
 {1999}
 %
 \ronbun{}{Makino,~K., Suda,~T., Ono,~H., Ibaraki,~T.} 
 {Data Analysis by Positive Decision Trees}
 {IEICE Transactions on Information and Systems}
 {Vol.~E82-D}
 {pp.~76--88}
 {1999}
 %
 \ronbun{}{Uno,~T., Yagiura,~M.}
 {Fast Algorithms to Enumerate All Common Intervals of Two Permutations}
 {Algorithmica}
 {Vol.~26}
 {pp.~290--309}
 {2000}
 %
 \ronbun{}{Yagiura,~M., Yamaguchi,~T., Ibaraki,~T.}
 {A Variable Depth Search Algorithm for the Generalized Assignment Problem}
 {Meta-Heuristics: Advances and Trends in Local Search Paradigms for
 Optimization, edited by Vo\ss,~S., Martello,~S., Osman,~I.~H., Roucairol,~C.}
 {Kluwer Academic Publishers} 
 {pp.~459--471} 
 {1999}
 %
 \ronbun{}{Yagiura,~M., Ibaraki,~T.}
 {Analyses of the 2 and 3-Flip Neighborhoods for the MAX SAT}
 {Journal of Combinatorial Optimization}
 {Vol.~3}
 {pp.~95--114}
 {1999}
 %
 \ronbun{}{柳浦睦憲, 茨木俊秀}
 {組合せ最適化問題に対するメタ戦略について}
 {電子情報通信学会論文誌}
 {Vol.~J83-D-I}
 {} % ページを空にしてください．
 {2000}
 %
 %%%%%%%%%%%%%%%%%%%% 平成12年度 %%%%%%%%%%%%%%%%%%%%
 \ronbun{}{阿瀬始, 茨木俊秀, 柳浦睦憲}
 {機械式立体駐車場入出庫スケジューリング}
 {システム制御情報学会論文誌}
 {Vol.~13}
 {pp.~494--503}
 {2000}
%
\ronbun{}{Boros,~E., Horiyama,~T., Ibaraki,~H., Makino,~K, Yagiura,~M.}
 {Finding Essential Attributes in Binary Data}
 {Proceedings of the 2nd International Conference on Intelligent
 Data Engineering and Automated Learning, LNCS}
 {No.1983}
 {pp.133--138}
 {2000}
%
\ronbun{}{Horiyama,~T., Ibaraki,~T.}
 {Reasoning with ordered binary decision diagrams}
 {Proceedings of the 11th Annual International Symposium on Algorithms
 and Computation, LNCS}
 {No.1969}
 {pp.120--131}
 {2000}
% 
 \ronbun{}{Nonobe, K., Ibaraki, T.}
 {An improved tabu search method for the weighted constraint satisfaction problem}
 {INFOR}
 {Vol.~39}
 {pp.~131-151}
 {2001}
 %
 \ronbun{}{Nonobe, K., Ibaraki, T.}
 {Formulation and tabu search algorithm for the resource constrained project scheduling problem}
 {Essays and Surveys in Metaheuristics, Kluwer Academic Publishers}
 {}
 {} % ページを空にしてください．
 {(to appear)}
%
 \ronbun{}{Ono,~H., Makino,~K., Ibaraki,~T.}
 {Logical Analysis of Data with decomposable structures}
 {Lecture Notes in Computer Science, 1858, 
 the Proceedings of Computing and Combinatorics,
 the 6th Annual International Conference (COCOON2000)}
 {}
 {pp.~396--406}
 {2000}
%
\ronbun{}{Nagamochi, ~H., Nakamura, ~S., Ibaraki, ~T.}
 {A simplified $\tilde {O}(nm)$ time edge-splitting algorithm in 
undirected graphs}
 {Algorithmica}
 {Vol.~26}
 {pp.~50--67}
 {2000}
%
\ronbun{}{Ibaraki, ~T.}
 {Partially defined Boolean functions with applications to data analysis: A survey}
 {Mathematica Japonica}
 {Vol.~51}
 {pp.~153--165}
 {2000}
%
\ronbun{}{Boros, ~E, Hammer, ~P.L., Ibaraki,~T., Kogan,~A., Mayoraz,~E., and Muchnik,~I.}
 {An implementation of logical analysis of data}
 {IEEE Trans. on Knowledge and Data Engineering}
 {Vol.~12}
 {pp.~292--306}
 {2000}
%
\ronbun{}{Deng,~X., Ibaraki,~T., Nagamochi,~H.,  and Zang,~W.}
 {Totally balanced combinatorial optimization games}
 {Mathematical Programming}
 {Vol.~A-87}
 {pp.~441--452}
 {2000}
%
\ronbun{}{Gaur,~D.R, Ibaraki,~T.,  and Krishnamurti,~R.}
 {Constant ratio approximation algorithms for the rectangle
stabbing problem and the rectilinear partitioning problem}
 {Springer LNCS, ESA2000}
 {Vol.~1879}
 {pp.~494--503}
 {2000}
%
\ronbun{}{Kogan,~K.,  and Ibaraki,~T.}
 {Optimal scheduling in parallel and serial manufacturing via 
the maximum principle}
 {Journal of Global Optimization}
 {Vol.~16}
 {pp.~271-294}
 {2000}
%
\ronbun{}{Boros,~E., Crama,~Y., Ekin,~O., Hammer,~P.L., Ibaraki,~T.,
and Kogan,~A.}
 {Boolean normal forms, shellability and reliability computations}
 {SIAM Journal on Discrete Mathematics}
 {Vol.~13}
 {pp.~212--226}
 {2000}
%
\ronbun{}{Boros,~E., Ibaraki,~T., and Makino,~K.}
 {Fully consistent extensions of partially defined Boolean functions}
 {International Conference IFIP TCS 2000, LNCS}
 {Vol.~1872}
 {pp.~257--272}
 {2000}
%
\ronbun{}{Nagamochi,~H.,  and Ibaraki,~T.}
 {Polyhedral structure of submodular and posimodular systems}
 {Discrete Applied Mathematics}
 {Vol.~107}
 {pp.~165--189}
 {2000}
%
\ronbun{}{Nagamochi,~H., Katayama,~S., and Ibaraki,~T.}
 {A faster algorithm for computing minimum 5-way and 6-way cuts
in graphs}
 {Journal of Combinatorial Optimization}
 {Vol.~4}
 {pp.~151-169}
 {2000}
%
 \ronbun{}{柳浦睦憲, 茨木俊秀}
 {メタ戦略とラグランジュ緩和}
 {システム/制御/情報}
 {Vol.~45}
{pp.~22--27}
 {2001}
 %
 \ronbun{}{柳浦睦憲, 茨木俊秀}
{組合せ最適化問題に対するメタ戦略について}
 {電子情報通信学会論文誌}
 {Vol.~J83-D-I}
 {pp.~3--25}
 {2000}
 %
 \ronbun{}{Yagiura,~M., Ibaraki,~T.}
 {Local Search}
 {Handbook of Applied Optimization, edited by Pardalos,~P.M., Resende,~M.G.C.}
 {Oxford University Press}
 {} % ページを空にしてください．
 {(to appear)}
 %
 \ronbun{}{Yagiura,~M., Ibaraki,~T.}
 {Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: Experimental evaluation}
 {Journal of Heuristics}
 {}
 {} % ページを空にしてください．
 {(to appear)}
\end{ronbunlist}

%-------------------------------------------------------
% 口頭発表
%-------------------------------------------------------
\begin{talklist}
 %%%%%%%%%%%%%%%%%%%% 平成10年度 %%%%%%%%%%%%%%%%%%%%
 \talk{}{Karuno,~Y., Nagamochi,~H., Ibaraki,~T.}
 {A 1.5-Approximation for Single-Vehicle Scheduling Problem on a Line with Release and Handling Times}
 {Japan-U.S.A. Symposium on Flexible Automation ISCIE/ASME}
 {}
 {pp.~1363--1366}
 {1998}
 
 \talk{}{野々部宏司, 茨木俊秀}
 {資源制約付きスケジューリング問題に対する近似解法}
 {日本オペレーションズ・リサーチ学会春季研究発表会}
 {}
 {}
 {1998}
 %
 \talk{}{野々部宏司, 茨木俊秀}
 {資源制約付きスケジューリング問題の定式化と近似解法}
 {生産スケジューリング・シンポジウム}
 {}
 {}
 {1998}
 %
 \talk{}{Yagiura,~M., Ibaraki,~T.}
 {How to Search Neighborhoods: Experimental Study with the Generalized
 Assignment Problem}
 {The INFORMS Seattle Fall 1998 Meeting}
 {}
 {}
{1998}
%
 \talk{}{Nonobe,~K., Ibaraki,~T.}
 {Implementation of CSP algorithms based on tabu search}
 {The INFORMS Seattle Fall 1998 Meeting}
 {}
 {}
 {1998}
 %
 \talk{}{Nonobe,~K., Ibaraki,~T.}
 {Formulation and Heuristics for RCSP (Resource Constrained Scheduling Problem}
 {Oxford Kobe Seminars: The 2nd Scientific Meeting on Systems Engineering and Applied Mathematics}
 {}
 {}
 {1998}
 %
 \talk{}{Yagiura,~M., Ibaraki,~T.}
 {An Ejection Chain Approach for the Generalized Assignment Problem}
 {Oxford Kobe Seminars: The 2nd Scientific Meeting on Systems Engineering and Applied Mathematics}
 {}
 {}
 {1998}
 %%%%%%%%%%%%%%%%%%%% 平成11年度 %%%%%%%%%%%%%%%%%%%%
 \talk{}{Glover,~F., Ibaraki,~T., Yagiura,~M.}
 {An Ejection Chain Approach for the Generalized Assignment Problem}
 {The 3rd Metaheuristics International Conference (MIC'99)}
 {}
 {pp.~223--228}
 {1999}
 %
 \talk{}{Horiyama,~T., Ibaraki,~T.}
 {Knowledge-Base Representation and Recognition of Positive/Horn Functions on Ordered Binary Decision Diagrams}
 {電子情報通信学会技術研究報告(コンピュテーション)}
 {Vol.~98, no.685}
 {pp.~17--24}
 {1999}
 %
 \talk{}{Horiyama,~T., Ibaraki,~T.}
 {Ordered Binary Decision Diagrams Representing Knowledge-Bases}
 {京大数理解析研究所講究録}
 {Vol.~1093}
 {pp.~93--98}
 {1999}
 %
 \talk{}{Horiyama,~T., Ibaraki,~T.}
 {Deduction and Abduction with Ordered Binary Decision Diagrams}
 {京大数理解析研究所講究録}
 {}
 {}
 {2000}
 %
 \talk{}{岸田正博, 柳浦睦憲, 茨木俊秀}
 {集合被覆問題に対する局所探索法について}
 {京都大学数理解析研究所講究録}
 {Vol.~1114}
 {pp.~211--220}
 {1999}
 %
 \talk{}{増田友泰, 柳浦睦憲, 茨木俊秀}
 {時間枠制約付き配送計画問題に対する局所探索法の適用について}
 {数理解析研究所講究録}
 {Vol.~1114}
 {pp.~194--205}
 {1999}
 %
 \talk{}{Nonobe,~K., Ibaraki,~T.}
 {Formulation and tabu search algorithm for the resource constrained project scheduling problem}
 {The 3rd Metaheuristics International Conference (MIC'99)}
 {}
 {pp.~351--356}
 {1999}
 %
 \talk{}{野々部宏司，茨木俊秀}
 {資源制約付きスケジューリング問題の定式化と近似解法}
 {特定領域研究「アルゴリズム工学」平成11年度全体会議 講演予稿集}
 {}
 {pp.~88--97}
 {1999}
 %
 \talk{}{梅谷俊治, 柳浦睦憲, 茨木俊秀}
 {段取り替え数最小化を考慮したカッティングストック問題の定式化と近似解法}
 {京都大学数理解析研究所講究碌}
 {Vol.~1114}
 {pp.~233--241}
 {1999}
 %
 \talk{}{岸田正博, 柳浦睦憲, 茨木俊秀}
 {集合被覆問題に対する局所探索法について}
 {日本オペレーションズ・リサーチ学会秋季研究発表会}
 {}
 {pp.~166--167}
 {1999}
 %
 \talk{}{増田友泰, 柳浦睦憲, 茨木俊秀}
 {時間枠制約付き配送計画問題に対する局所探索法の適用について}
 {日本オペレーションズ・リサーチ学会秋季研究発表会}
 {}
 {pp.~168--169}
 {1999}
 %
 \talk{}{野々部宏司, 茨木俊秀}
 {制約充足問題に対するタブー探索における評価関数の重みの自動調整}
 {日本オペレーションズ・リサーチ学会 1999年度春季研究発表会}
 {}
 {pp.~8--9}
 {1999}
 %
 \talk{}{野々部宏司, 茨木俊秀}
 {大きな構造物の生産スケジューリング問題に対するRCPSPアプローチ}
 {スケジューリング・シンポジウム}
 {}
 {pp.~53--58}
 {1999}
 %
 \talk{}{梅谷俊治, 柳浦睦憲, 茨木俊秀}
 {段取り替え数最小化を考慮したカッティングストック問題の定式化と近似解法}
 {スケジューリング・シンポジウム'99}
 {}
 {pp.~161--166}
 {1999}
 %
 \talk{}{梅谷俊治, 柳浦睦憲, 茨木俊秀}
 {カッティングストック問題におけるパターン生成法について}
 {OR学会平成12年度春期研究発表会}
 {}
 {}
 {2000}
 %
 \talk{}{Umetani,~S., Yagiura,~M., Ibaraki,~T.}
 {Minimizing the Number of Different Patterns in the Cutting Stock Problem}
 {The 15th Triennial Conference of the International Federation of Operational Research Societies (IFORS'99)}
 {}
 {p.~123}
 {1999}
 %
 \talk{}{Yagiura,~M., Kishida,~M., Ibaraki,~T.}
 {A 3-Flip Neighborhood Local Search Algorithm for the Set Covering Problem}
 {The 15th Triennial Conference of the International Federation of Operational Research Societies (IFORS'99)}
 {}
 {p.~23}
 {1999}
 %%%%%%%%%%%%%%%%%%%% 平成12年度 %%%%%%%%%%%%%%%%%%%%
 \talk{}{Ibaraki,~T.}
 {Metaheuristic algorithms as general problem solvers}
 {2nd HCQB Joint International Workshop (ORSJ Hokkaido Chapter and ASOR Queensland Branch), keynote speech}
 {}
 {}
 {2000}
 %
 \talk{}{Ibaraki,~T.}
 {Local search and its generalizations}
 {The fifth conference of APORS (Asia-Pacific Operations Research Societies within IFORS), keynote address}
 {}
 {}
 {2000}
 %
 \talk{}{Horiyama,~T., Ibaraki,~T.}
 {Translation between Horn CNFs and their ordered binary decision diagrams}
 {LAシンポジウム}
 {}
 {}
 {2000}
 %
 \talk{}{今堀慎治, 柳浦睦憲, 茨木俊秀}
 {配置コストをもつ二次元配置問題に対する局所探索について}
 {スケジューリング・シンポジウム 2000}
 {}
 {pp.~138--141}
 {2000}
 %
 \talk{}{増田 友泰, 柳浦 睦憲, 茨木 俊秀}
 {一般化時間枠制約付き配送計画問題に対する局所探索法の適用とその応用}
 {スケジューリング・シンポジウム2000}
 {}
 {pp. 132--137}
 {2000}
 %
 \talk{}{柳浦睦憲, 茨木俊秀}
 {組合せ最適化問題に対するメタ戦略}
 {第44回システム制御情報学会研究発表講演会講演論文集}
 {}
 {pp.~235--238}
 {2000}
 %
 \talk{}{柳浦睦憲, 野々部宏司, 茨木俊秀}
 {メタ戦略とスケジューリング}
 {スケジューリングシンポジウム2000講演論文集}
 {}
 {pp.~11--16}
 {2000}
 %
 \talk{}{Boros,~E., Horiyama,~T., Ibaraki,~T., Makino,~K., Yagiura,~M.}
 {Finding Small Sets of Essential Attributes in Binary Data}
 {The 17th International Symposium on Mathematical Programming (ISMP2000)}
 {}
 {p.~164}
 {2000}
 
 \talk{}{堀山貴史, 茨木俊秀}
 {Horn関数を表すCNF式と二分決定グラフの相互変換}
 {日本数理科学協会 Annual Meeting}
 {}
 {}
 {2000}

 \talk{}{堀山貴史, 茨木俊秀}
 {Horn CNFとその二分決定グラフ表現間の変換の計算複雑さ}
 {電子情報通信学会ソサイエティ大会}
 {}
 {D--1--5}
 {2000}
 
 \talk{}{今堀慎治, 柳浦睦憲, 茨木俊秀}
 {配置コストをもつ二次元配置問題に対する局所探索について}
 {日本オペレーションズ・リサーチ学会2000年度秋期研究発表会}
 {} % 巻号を空にしてください．
 {pp.~190--191}
 {2000}
 
 \talk{}{岩崎慎司, 柳浦睦憲, 茨木俊秀}
 {多資源一般化割当問題に対する大規模近傍探索法の適用について}
 {日本オペレーションズリサーチ学会2000年度秋季研究発表会}
 {} 
 {pp.192-193}
 {2000}
 
 \talk{}{Nonobe, K., Ibaraki, T.}
 {The Project scheduling problem with a separable convex cost function}
 {The 17th International Symposium on Mathematical Programming (ISMP2000)}
 {}
 {p. 72}
 {2000}
 
 \talk{}{野々部宏司, 茨木俊秀}
 {分離可能凸型コスト関数をもつプロジェクトスケジューリング問題}
 {日本オペレーションズ・リサーチ学会2000年度秋期研究発表会}
 {}
 {pp. 100--101}
 {2000}
 
 \talk{}{小野廣隆, 牧野和久, 茨木俊秀}
 {分解構造に基づくデータの論理的解析}
 {LAシンポジウム}
 {} % 巻号を空にしてください．
 {} % ページを空にしてください．
 {2000}
 
 \talk{}{増田 友泰, 柳浦 睦憲, 茨木 俊秀}
 {A Local-Search Heuristic for the Vehicle Routing Problem with General Time Window Constraints}
 {APORS2000}
 {}
 {}
 {2000}
 
 \talk{}{増田 友泰, 柳浦 睦憲, 茨木 俊秀}
 {一般化時間枠制約付き配送計画問題に対する局所探索法の適用とその応用}
 {日本オペレーションズ・リサーチ学会2000年度秋期研究発表会}
 {}
 {pp. 194--195}
 {2000}
 
 \talk{}{増田 友泰, 柳浦 睦憲, 茨木 俊秀}
 {一般化時間枠制約付き配送計画問題に対する局所探索法の適用とその応用}
 {日本応用数理学会}
 {}
 {pp. 164--165}
 {2000}
 
 \talk{}{梅谷 俊治, 柳浦 睦憲, 茨木 俊秀}
 {カッティングストック問題におけるパターン生成法について}
 {日本オペレーションズ・リサーチ学会2000年度春期研究発表会}
 {}
 {pp. 34--35}
 {2000}
 
 \talk{}{梅谷 俊治, 柳浦 睦憲, 茨木 俊秀}
 {カッティングストック問題におけるパターン生成について}
 {LAシンポジウム}
 {}
 {}
 {2000}

 \talk{}{Umetani, S., Yagiura, M., Ibaraki, T.}
 {A Pattern Generating Heuristic for the One Dimensional Cutting Stock Problem}
 {The 17th International Symposium on Mathematical Programming (ISMP2000)}
 {}
 {p. 84}
 {2000}

 \talk{}{梅谷 俊治, 柳浦 睦憲, 茨木 俊秀}
 {カッティングストック問題におけるパターン生成法について}
 {日本応用数理学会}
 {}
 {pp. 162--163}
 {2000}
 
 \talk{}{柳浦睦憲, 茨木俊秀}
 {組合せ最適化問題に対するメタ戦略について}
 {日本オペレーションズ・リサーチ学会「システムの最適化とOR」研究部会(北陸地区)}
 {}
 {}
 {2000}

 \talk{}{Yagiura,~M., Kishida,~M., Ibaraki,~T.}
 {A 3-Flip Neighborhood Local Search for the Set Covering Problem}
 {The 17th International Symposium on Mathematical Programming (ISMP2000)}
 {}
 {p.~84}
 {2000}
 
 \talk{}{柳浦睦憲, 今堀慎治, 茨木俊秀}
 {2次元配置問題とその一般化について}
 {科研費・特定領域研究(B)「アルゴリズム工学」
 第8回テーマ研究会: 近似アルゴリズム}
 {}
 {}
 {2001}
\end{talklist}

%-------------------------------------------------------
% 著書，解説，出版物等
%-------------------------------------------------------
\begin{chosholist}
 \chosho{}{Katoh,~N., Ibaraki,~T. (分担執筆)}
 {Handbook of Combinatorial Optimization, Vol.~2 (Chapter of ``Resource Allocation Problems")}
 {Kluwer Academic Publishers}
 {1998}
 
 \chosho{}{Burkard,~R.~E., Ibaraki,~T., Pulleyblank,~W.~R. (eds.)}
 {Mathematics of Industrial Systems III (Annals of Operations Research, Vol.~76)}
 {Baltzer Science Publishers}
 {1998}
 
 \chosho{}{茨木俊秀}
 {Cによるアルゴリズムとデータ構造}
 {昭晃堂}
 {1999}
 
 \chosho{}{柳浦睦憲, 茨木俊秀}
 {組合せ最適化 --- メタ戦略を中心として ---}
 {朝倉書店}
 {2001}
\end{chosholist}
\end{document}
