Lehigh 大学の研究チームが、 Gurobiを用いてINFORMS2017のWagner賞を受賞

7人のスタッフが1週間かけて行っていた仕事を、ソフトウェアがわずか数分で完了

刑務所への収容者の割当ては、収容者に関する数十もの要因を考慮しなければならず、非常に複雑なプロセスを経て決定されます。例えば、刑務所に関連する要因としては、施設の稼働水準、収容者に対する提供可能なサポートプログラム、すでに収容されている収容者の特性など、また、収容者に関する要因としては、関係性犯罪歴や人口統計学的特性、精神的・身体的健康状況などがあります。

適切な収容者割当は、刑務所および収容者の両者とって重要です。なぜなら、収容者にとっては更生支援プログラムをより早く受けられるだけでなく、他の収容者との間での攻撃的な行動の機会が減りますし、刑務所にとっては、施設スタッフの労力およびや施設間の収容者移送の回数を減らすことができるからです。

Leighチームが開発したアプリケーションは、作り上げるまでに5年の歳月を費やしましたが、本アプリケーションの使用を開始した最初の年でペンシルバニア州の刑務所は、300万ドルもの経費を削減しました。また、収容者の暴力件数および収容者移送率、そして、スタッフの労力も軽減し、まさに7人のスタッフがまるまる1週間かかって行っていた仕事が今はこのアプリケーションで、わずか数分で日々処理されています。

このチームの研究プロセスおよび結果の詳細は、本賞の受賞者として提出した論文”The Inmate Assignment and Scheduling Problem and its Application in the PA Department of Corrections.” に記載されています。

問題概要

収容者割当問題は、混合整数線形計画問題（MILP）としてモデル化されています。目的関数は階層的に重みづけされた6つの関数（割当指標に対する違反、施設の収容量の超過、更生プログラムを受けるまでの待ち時間等）の合計で、およそ30,000個の0-1変数と200個の整数変数、そして25,000個の制約式を持っています。

Gurobiは、所定の最適性GAPを満たした時に解を得るためのエンジンとして使用されています。Gurobiは、わずか数分で高品質な解を提供し、本アプリケーションは、現在ペンシルバニアの刑務所を管轄する部門で日々使用されています。

以上