OR トピックス

アルゴリズムと特許ーーその1.カーマーカー特許一一今野浩

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111.の大半は，はじめにr時代の流れ jを与件として，これにどのように「対応 j すべきかを論じたものであり，ソフトウェ

1980年代のはじめに，米国が知的財産権戦略を国策のア/アルゴリズム保護が L 、かにあるべきかを，その基本根幹に据えるようになって以来，超大型の特許訴訟が続から論じたものはあまり見当らない.法律家を栴手に論発している.ポラロイド社がコダック社をフィルムの製争しでも勝てるはずがない，と人々が考えているためで法の特許侵害で訴えた訴訟や，フェアチャイルド社がソあろうか.

ニー，松下など 33社を訴えた電荷結合素子 (CCD) 特については，法理論上も難しい問題が多いため，法律関許訴訟などは，係者の聞でも意見が割れていると L 、う事実は，技術者た10億ドル単位の訴訟事件として(悪)名高いものである.これに比べると，ハネウェルとミノル

タの聞の自動焦点、カメラに関する 1 億ドル余りの和解金などは，やや影が薄くなってしまうから恐ろしい.

しかし，ソフトウェア/アルコリズムの保護ちにはあまり知られていないようである.
さて，ソフトウェア先進国の米国においては， 80年代はじめ以来つぎつぎと成立したソフトウェア特許が，こ企業の存亡にかかわる，このような大型訴訟の頻発にのところ猛威をふるい始めている.そしてソフトウェア

対して，わが国のメーカーも知的財産権担当セクション

関係者の聞からは，このままでは独創的なソフトウェアの増強を図る一方，基本特許に結びつく研究の推進，徹の作成が不可能になる，底的なクロス・ライセンス戦略などによって対抗しよう

わゆる地雷特許の問題をはじめ，新規性を欠く特許，そとする叫びが上がっている.いとしている.また最近では，日本のメーカーが逆に米国して権利がきわめて広範囲にわたる特許が相次いで‘成立メーカーを特許侵害で訴えるケ}スも出始めている.

するなど，さまざまな問題が研究者/実務家を悩ましてこのような状況の中で，われわれ OR 関係者のきわめて身近なところて-新たな大問題が持ち上がりつつある.
それが本稿の主題である，ソフトウェア/アルゴリズム特許の問題である.よく知られているとおり，わが国では，1986年の法改正以来，いる.

ところがその一方で，最近になってゆきすぎた訴訟社会を札す動きも出始めている.その代表例が，1992年に米国議会の技術評価局 (OTA) が発表した報告書，ソフトウェアは著作権で保護iFindingaBalanceJ[2J である.この報告書は，広いされることになってきた.しかし，このところなし崩し分野の専門家を集めて行なわれた公聴会をもとにしたも的に，ので，ソフトウェアに特許が付与されるケースが増えてソフトウェア/アルゴリズムの保護は L 、かにあるいるのである.特許庁は，現状を追認するため，これまべきかを，規範的立場から論じたものである.全体としで暖昧さを批判されてきた審査基準を改定し，て，現在の米国のソフトウェア関連の特許行政の行き過ソフトウ

ェア特許の市民権を拡大する方向に踏み出した.そしてぎや，一貫性のなさに苦言を呈するものとなっており，ソフトウェア業界も，この流れを受けて，一斉にソフトソフトウェア関係者の生の戸が，報告書全体に大きな影ウェア特許へと走り出している.

響を及ぼしたことがうかがわれる.

この問題について，わが国の工学系の学会の中にも，そこで本稿では，最近 OR の世界で発生しジャーナリシンポジウムを持催したり，特集記事を組むなどするとズムでも大きくとりあげられた，線形計画法(カーマーころが現われている [IJ.

カー)特許事件を振り返り，これを手がかりに，アルゴしかしそこで述べられたもの

リズムと特許問題について意見を述べることとしたい.
こんのひろし筆者はもともと数理計画法のー研究者であって，法律に東京工業大学工学部人文社会群関しては，全くの素人である.したがって，この文章の

干 152 目黒区大岡山 2-12-1

内容は，法律専門家諸氏から見れば穴だらけのものに違414(30)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

いない.しかし，農民にとって農業政策が大問題であるをたどるもので，しかも多項式オーダーの解法であるこのと同じく， OR/ ソフトウェア関係者にとって，知的とを証明していた.しかし，ヵーマーカーは，実用上も財産権政策は決定的に重要な意味をもっている.その意

それが単体法を上まわることを主張するにあたって，そ味で，アルゴリズムやソフトウェアに最も深くかかわっれを裏づけるデータを全く公表しなかったのである.ている研究者/実務家が，たとえ穴だらけにせよ，率直ンスを比較する際には，標準的な問題セットを用いて，る次第である.

同ーの計算環境で客観的な比較実験を行なうことが慣例

2.
【発端】となっている.この意味で，カーマーカーのやり方は，カーマーカー特許研究者としては明らかなルール違反であった.しかも彼

ニューヨーク・タイムスの一面に，ベル研究所のカーマーカー)

この分野では，新しい解法と旧来の方法のバフォーマな意見を述べることには，それなりの意味があると考え

rAT&T(N. Karmarkar) 博士が，は，1985年の夏に，約 1000人の専門家を集めて開かれた国際シンポジウムの招待講演の席でも， 50倍100 倍の線形計画法の解法として，従来のもの(単体法)より 50主張を繰り返すだけで，あらゆる質問を黙殺するという傍から 100倍速い解法を提案した J ，と L 、う記事が掲載さ怪挙に出た.このことによって，ヵーマーカーと AT&れたのは，1984年夏のことであった.それから 10年近いT は，学問の世界にパプリシティーをもちこんだとして，歳月を経た今日，世の中の情勢は，この記事の内容が“結厳しい批判を受けることになったのである.そして，こ果的"には正しかったことを示す方向に動いている.しれに追いうちをかけたのは，ベル研究所の関係者が述べかし，当時の日本の一般紙に転載されたこの記事を自にたとされるカーマーカー法は，したとき，筆者は直ちに“狼少年の物語"を連想したもるため，その詳細を公表することはできなし、」という発のである.

言であった.これによってカーマーカ一法は，当時論議本誌の読者ならどなたでもご承知のとおり，当時はダンツィクの単体法が，さまざまなチャレンジを退けて，40年近くにわたって線形計画法問題の実用解法としての軍事上の機密に属すを呼んでいた SDI プロジェクトのうさん臭さとも重なる結果となってしまった.
それはともかく，これらの過程で研究者の多くは，カ王座を守り続けていた.実際，筆者が数理計画法の研究ーマーカ一法が第 2 のハチアン法に過ぎないのではないを本業とするようになった 70年代以降だけをとっても，か，少なくとも彼らはその主張を裏づける実験結果をもスコールユク(H. Scolnik) の新解法 (1974年)，ハチち合わせていないのではないか，という疑念(確信?)(L. Khachian) の楕円体法( 1979年)が単体法にをもつにいたった.しかしその一方で，世界の Center挑戦するものとして話題となった.しかし，前者には発of Excellence として知られるベル研究所が後押していアン

表後間もなく理論的な誤りが発見されたし，後者も多項るとなると，全く根拠のない話とも考えにくいという事

式オーダーのアルゴリズムという，理論上優れた性質を情もあった.

もつにもかかわらず，実用上は単体法に速く及ばないと疑心暗鬼が渦巻くなか，カーマーカーの発言を確かめいうことが， 80年代のはじめには明らかにされていた.

るため，一群の優秀な研究者がカーマーカ一法の追試と，また，この一方で， 70年代後半から 80年代はじめにかけその理論的研究にとりかかった.そしてその後まもなく，て，単体法の実用的な意味での優秀性を理論的に保証すアドラー(1. Adler) らのグループによるアフィン変換

る研究結果……単体法が平均多項式オーダーの算法であ法，伊理，今井氏による乗法的罰金法などが発表され，ると L 、う結果…ーがあいついで発表され，単体法への信研究活動は急激に加速されることとなった.カーマーカ

頼が一層高まりを見せていた頃で、もあった.したがって，一法が，射影変換という，一般には馴染みの薄い道具を突如単体法より 50倍以上速い解法が現われたといわれて用いていたのに対して，これらの解法は“わかりやすい"も，とても信用する気になれなかったという次第であ標準的な道具を用いた方法であったばかりでなく，数値る.

実験によって，大規模な問題に対しては，単体法の効率【カーマーカ一事件】
は，1984年末にカーマーカーの射影変換法の全貌

Combinatorica誌に掲載された論文を上まわる可能性をもつことが示されたためである.

これらの方法は L 、ずれも実行可能領域の内部をたどる[3J において明らかにされた.この中でカーマーカーは，もので，その総称として，“内点法 "é l.、う言葉が使われ自分の方法が単体法とは違って，実行可能解集合の内部るようになった.そして 1986年に，ギル

1993 年 8 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(P.Gill)らス(31)415タンフォード大学のグループによって，古くから知られる.また申請書は，単体法との根本的な違いを強調するているフィアッコ=マコーミックの内点罰金法と，カーとともに，すでに述べたハチアンの方法との違いにも言マーカ一法との関連が明らかにされたのをきっかけとし及し，この「発明」が独創的で従来の方法にない特徴，て，方向ベクトルの向きや，ステップ・サイズにさまざすなわち理論的にも実用的にも優れた性質をもつものでまな工夫が凝らされた結果，超大型問題については内点あることを主張している.

法が有利である，とする見解が有力となったのは 1988年の頃である.

さらに，このアルゴリズムの適用分野として，電話送信網の最適利用をはじめ，工場の操業，プロダクトミッ【カーマーカー特許成立】

内点法に関する研究成果が専門誌を埋めつくす状態の中，1988年 5 月に米国特許商標

庁は，カ-，ーカーらと AT&T から提出されていた 3

クス，石油精製，コンピュータ・リソースのユーザーへの配分，航路操法，プロセスコントロール，リアルタイ

ム制御といった例をとりあげ，このアルゴリズムを適用

件の特許申請を認める決定を下した.これらの特許は，する手順について述べている.このように応用について1984年に発表されたカーマーカ一法(射影変換法を用いかなりのスベースを割 L 、ているのは，たもの)と，それ以降に開発されたアフィン変換法をカべるとおり)数学的アルゴリズムが特許指定を受けるた

ミーするもので，その内容は概略以下のようなものであめには，それが単なる数学理論でなく，“十分に応用されった [4].

たもの"ではなくてはならなし、，とする特許商標庁の政特許申請に記載されたカーマーカ一法の一般的手順.
10(次回で詳しく述策に対応したものである.また，特許の適用対象を，現実線形計画モデルの作成。

的な技術や工場のシステムを最適化する場面に限定し，cT X

学術的な目的での利用はこの発明の特許の対象外である!日
条件としているが，これは学界からの反発を和らげるためのAx=b , V~五 z 豆 u

ここに A は mxn 行列

V ， U はそれぞれ変数￡下

1985年当時から，専門家の聞に特許申請の噂は流布さ限，上限を与える n 次元ベクトんである.

2 v くが <u ，0ものであろう.

れていたが，この特許が成立したことは，伝統的に特許Axo=b を満たすがを選ぶ.

k=O とする.の対象外にされてきた数学そのものが，はじめて特許指30 xk をセットする.

定されたと L 、う意味で，専門家はもとより一般市民をも40

スケーリングのための対角行列 D を用いてXk をセ驚かすに十分であった.以下の文章は，このニュースが伝わって間もなく，筆者が雑誌「科学」の求めに応じてンタ}化する.

50 センター化された点、で，以下の式により最急降下方向書いたもの [5J からの抜粋であるが，これは当時の研究者たちの“素朴"な反応を代表したものである.

ρ を求める.
ρ =-D {Iー (AD)T (AD2AT)‑lAD} xDc

60 xk +l =xk+ap とする.

・・日本では，プログラムは著作権法によって保護されている.そしてこの法律ではプログラム言語，プ7 0 収束テスト:条件

ロトコルとともにアルゴリズムは保護しないことが明Txk‑cTX
TXIck+lI:豆 2- d c

確に規定されている.したがって，アメリカで成立しが成立すれば 8 0 へ，さもなければ k=k+l として 3 。

たような特許が日本にもち込まれることは理論上はあへゆく.

りえない.一方，アメリカでもこれまで 10進 16進変換

80 xk を丸めて最適解とする.

法などをはじめ，いくつかのアルゴリズムに対する特このようにカーマーカー特許は，この分野の知識のあ許が申請されたが，そのつど特許法になじまないとしる人には，アルゴリズムの全体の構成と各部分の役割おて却下されてきた.ところが，よびその内容が理解できるように記述されては L 、るが，知的財産権保護を国策として打ち出すようになって以

実際のコーディングに必要な手順，たとえば ， X O や D や米，状況はJ急激に変わってきている.今回の件も，こ自の決め方などについては書かれていないのが特徴であのアメリカの国策に沿ったものであることが明白であ80年代に入って米国がる.これはインプリメンテーションのレベルまでは特定るだけに，わが国と学会に投げられた問題はきわめて化せず，アルゴリズムのレベルにとどめることによって，大きい.“線形計画法のように，現実の経済的利益に結より広い範囲の特許を得ょうという|意図の表われであびっく応用数学の分野は，探してもたくさんあるわけ

416 (32)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

ではな\，，"とか，“今回の特許は，ソ連のディキンが 20大型の線形計画問題を解くことに成功した，と報じられ年前に発表したまま埋もれていた方法と似ているのたのは，その後間もないことであった.まずデルタ航空

で，いずれ無効になるだろう"といった楽観論もある.

では，世界の )66 の都市をカパーする航空路に配備されしかし筆者は，ことはそう簡単ではないと憂慮している約 400 機の航空機と 7000人の乗務員にかかわる大型ス(中略)一流の数学者ならば，自分の業績を特許にケジューリング問題を解くことに成功した結果，年間数仕立てて，他人の利用を制限することなど考えもしな百万ドルの経費節約が可能になったと報告している.まいのがふつうだろう.ところが，線形計画法は数学のた，同じころ米国空軍では，上に述べた問題と関連して，る.

一分野であると同時に，かなり工学的色彩の強いもの従来のソフトでは解けなかった 7 万制約式 50万変数の問である.したがって工学畑出身のカーマーカーが，そ題が解けるようになった結果，空軍の作戦立案能力が飛の世界では当たり前になっている特許申請(に同意)躍的に改善されたと報告している [7J. このように KORしたとしても別に不思議ではな L 、，という意見も一部

BX は， 100万変数を越える超大型問題を現実に解くことにはある.しかし，まだ 33才になったばかりのカーマができることをはじめて示したとし、う意味で，画期的なーカーのディレンマは，必ずしも大きいとはいえないものであった.

金銭的報酬の代わりに，学会のマジョリティを敵にまわしたことである…….

この一方で AT&T は，内点法の改良にかかわる追加特許をつぎつぎと申請し，内点法を用いたソフトウェア

ここでこの文章に，若干の注釈を加えておこう.

1988の開発はすべて AT&T 特許に抵触する，というムード

年の初頭，シベリアのエネルギー研究所に勤務するディづくりを推し進めた.このような行動に出たのは，

キン(1. Di kin) 博士から，この分野の世界的リーダー

年代末の独禁法強化措置によって，

1970

AT&T が L 、くつかTodd) 教授の組織に分割され，ベル研究所も独立採算の組織として宛に l 通の手紙が届けられた.この中でディキン博士は，再編成されたことと深く関係している.米国のような知特許付与されたカーマーカーらのアフィン変換法とほぼ的作業を重視する国においても，民間の研究所がコンスの一人で、あるコーネル大学のトッド (M.

同ーのアルゴリズムを，すでに 1966年に発表済みであるタントに収益を上げてゆくのは，決して容易なことではと述べ，その証拠物件として，論文 [6J のコピーを送っない.このため，AT&T ベル研究所は，自らの収益をてきたので、ある.この論文を仔細に検討したトッド教授確保すべしこのような行動に出たのではないだろうか.

は，その後間もなくディキンの主張をほぼそのまま認め【日本経済新聞アンケート】

る判定を下し，研究者たちにその事実を周知させるため

年 2 月，日本経済新聞社が学術会議の協力を得て，全国の手紙を送っている.そしてこれ以降，の理・工・農・医学系の研究機関の指導的立場にある人

AT&T の 3 件

このような状況の中，1989の特許のうちの少なくとも 1 つは，特許取り消しとなっ々に対して行なった「先端技術アンケート J の調査結果て然るべきである，というのが研究者グループの共通のが発表された.これによると，見解となったのである.

られるような)科学研究の知的産物の保護をどう思うか J<KQRBX >さて AT&T は，1989年になるとカーマーカー・グループが開発したソフトウェア

IKORBXjI(カーマーカー特許に見という設聞に対する 247 人の回答のうち，反対が 124人，基本的に賛成が 64人，そしてケース・パイ・ケースで賛の発売を開始した.これはアフィン変換法をベースにし成と答えた者 59 人となっていた.反対意見の大半は，たソフトであったが，またまた人々を驚かせたのは

利保護は学問の発展を阻害する j ，セット 890 万トソレ(当時の円換算で 11 億円)とし、う価格いない新説や発見を対象にしていたら特許制度が混乱す設定であった.ハードウェア込みとは L 、 L 、ながら，ハーるj，ドの価格は全体の 10%強に過ぎず，応用ソフトウェアとであった.

しては史上最高の値段であった.

はっきりしなくなってきた以上当然の成り行き J とする

そして AT&T は 250 人のスタップからなる組織を設I権r正しさが立証されてI 米国にとってのみ都合のよい提案」といった内容

一方賛成派の多くは科学と技術の境界がものが中心であった.これに対して，ケース・パイ・ケ

立し，全世界を相手にセールスを開始したのであるが，ースとする回答者の多くは， I 応用開発に直結すること j ，デルタ航空と米国空軍がこのソフトを購入し，乗務員の「産業上の有用性がはっきりしていること J を条件としスケジューリング問題や，世界の特定地域で不測の事態ていた.確かに，すでに特許制度と共存している分野のが発生した場合の，傷病兵士や物資の輸送にかかわる超研究者にとっては，数学が特許になってもあまり違和感

1993 年 8 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(33)417

はなかったかもしれない.しかし，それまで特許とは無縁であった OR の分野に身をおく筆者にとっては，条件付きを含めて，賛成する者が反対する者とほぼ同数( 1きない部分が多い，と L 、う意見を表明した.

これら 5 民の見解は，当時のほぼすべての立場をカバーするものであったが2 時間半にわたるディスカッシ票差! )を数えたことは大きな衝撃であった.

ョンの中で，問題の容易ならざる難しさが浮彫りにされ【 RAMP シンポジウム】る結果となった.特にフロアの(数理計画法の)研究者

事態を重視したわれわれ数理計画法関係者は，日本 OR 学会に組織された数理計画法研究会が主催するシンポジウムの機会をとらえて，

1
989

年 11 月にパネル・ディスカッション知的所有権問題を考える……カーマーカー特許を中心に J を開催した.
このパネルは，の中から，AT&T の上をゆくカーマーカー特許支持の意見が飛び出すにいたって，筆者の事前の予想は完全に裏切られることになったのである.
筆者は，このパネル・ディスカッションに先立ち，世AT&T ベル研究所の伊倉義郎氏，弁護界各国の 40人の研究者仲間に対してアンケート調査を行士の佐野稔氏，埼玉大学の万板薫教授，日本経済新聞社

ない，約半数から解答を得たが，その大半は山際，万根の山際和久氏，紛数理システム社長の山下浩氏の 5 名で両氏の見解に近いもので、あった.このため筆者は，構成され，筆者が司会をつとめた.

やソフトウェア関係者たちの認識は，前記の日経新聞アOR

まず伊倉氏は，カーマーカ一法のような画期的なアルンケート結果とはかなりの隔たりがあるとの確信を深ゴリズムが特許となるのは全く当然である，とする ATめ，これらの意見とパネル・ディスカッションの結果を&T の立場を主張し，この特許が学聞の発展を阻害する集約して，という意見に対しては，アカデミック・ユースが制限さとめる計画を立てていた.しかし，上で、述べたような事れてないことからして全く問題はな L 、とする意見表明

情で統一見解のとりまとめは難しいものと判断し，残念を行なった.伊倉氏が当時， KORBX の販売組織の中ながらこれを先送りせざるを得なかったので、ある.

OR 学会数理計画法研究会としての提言をま枢にあったことからして，この発言は当然予想されたも参考文献のであった.

次に知的財産権問題に精通した弁護士の佐野氏は，おかしなことは山ほどあるが，世界の流れはアメリカの知的財産権戦略どおりに動いていること，またその戦略決定にあたゥては，

1BMや AT&T 等の大企業が大きな影響をもつことから見て，特許決定は時代の流れである[1J “特集知的財産権と技術管理ヘ経営システム，
第 3 巻 1 号，

日本経営工学会，

1993.

[2J Officeo
fTechnology Assessment , Finding
fDocuments , U.
a Balance , Superintendento
992.
S. Congress , 1[3J Karmarkar , N. ,“ A New Polynomial‑Time

点を説明された.

一方万根氏は，ヵーマーカ一法をはじめとする内点法の研究者として，カーマーカ一法の基本となるアイディアは画期的なものであり，これが特許になったことは必Algorithm for Linear Programming" , Comｭbi叩 torica ，[4J4(1984) 373‑395.

万根薫，“線形計画法とKa
紅rma
釘rka
釘r 特許"

ずしも不当とはいえないとしながらも，この特許ベクト

第 l 回 RAMP シンポジウム報告集， 幻2 7 一3
幻7 ，日本オルの射影法といった公知の事柄をもカパーしているのはベレーションズ・リサーチ学会，おかしい，とする意見を表明された.
また，ジャーナリズムの世界にあって知的財産権問題を追いつづけてきた山際氏は，カーマーカー特許， CIM特許などは百害あって一利なく，特にその特許範囲の暖味さと，公知の技術を特許指定したことは全く許し難いことであると， AT&T を糾弾する発言を行なった.
最後にソフトウェア会社の経営者と，内点法の研究者という 2 つの顔をもっ山下氏は，ソフトウェアに含まれるアイディアすなわち“アルゴリズム"の中には，特許

1989.

[目今野浩，“カーマーカー特許についてヘ科学，58 (1 988) , 746‑747.
[6] Di kin , 1.,“ Iterative Solution of Problems
ofL
inear and Quadratic Programming ヘ(inRussian) , AkademiaNauk USSR , 174(1967)
747‑748.
[7J Hughs , G. C. , “ Karmarkar's Algorithm
FindsaHomeatMAC" , OR/MS Today , 22‑
23. ORSA , June , 1
989.

によって保護されて然るべきものがあるとする一方で，指定範囲があまりにも広いカーマーカー特許には納得で

418(34)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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