多品種流問題に対する幾何学的アプローチ

摘要

大重み多品種流問題は最大流問題の一般化であるが，整数枝容量であっても一般には整数最適解を持たない．しかし，フローが出入りする点の集合とその上の重みによっては整数最適解を待っ．そのため，どのようなときに整数最適 解を持っのかについて長年研究されてきたが，最近になって，この疑問が解明された。その際に用いられた手法は，幾何学的な手法で，距離の夕イトスンやトロピかレ多面体と呼ばれる幾何学的概念が重要な役割を果たす．特に，それらの幾何学的構造が最適解の構造を陽に表す．このような手法は，組合せ最適化の手法として例を見ないものであり，本稿では，それを紹介する．