ギロチンカット問題

ギロチンカット問題（ギロチンカットもんだい、英：Guillotine problem）とは、組合せジオメトリと印刷の問題のことである。 

梱包の問題、特に在庫とビンの梱包の問題に密接に関連してGerhard Wäscher, Heike Haußner, Holger Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research 183 (2007) 1109–1130, 、大きいシートから1つの長方形サイズのシートの最大数を取得する方法の問題。紙カットギロチンのように、シートの1つの構成要素を2等分する直交カットのみが許される。 

ガラス加工では、ギロチンの問題が重要である。ガラスシートは、水平線と垂直線に沿って刻み目が付けられ、これらの線に沿って分割され、より小さいパネルが得られる。  

板取り問題と同様に、NP困難な問題として知られているが、さまざまな近似および厳密アルゴリズムが考案されているMichael L. McHale, Roshan P. Shah Cutting the Guillotine Down to Size. PC AI magazine, Volume 13, Number 1 Jan/Feb 99. http://www.amzi.com/articles/papercutter.htmM. Hifi, R. M’Hallah and T. Saadi, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem. Computational Optimization and Applications, Volume 42, Number 2 (2009), 303-326, François Clautiaux, Antoine Jouglet, Aziz Moukrim, A New Graph-Theoretical Model for the Guillotine-Cutting Problem. INFORMS Journal on Computing October 2011 ijoc.1110.0478 pp. 1–15。

 脚注 

Category:組合せ最適化
Category:数学の問題
Category:離散幾何学