Construction of Plat-form Models for the Problemof Packing Geometrical Objects

几何对象填充问题的平台模型构建

• 批准号: 20500012
• 负责人: NAGAMOCHI Hiroshi
• 金额: $ 2.91万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500012/
• 关键词: 可視化; 詰め込み問題; パッキング; アルゴリズム; 最適化; 機械学習; グラフ描; 準ニュートン法; 離散最適化; 配置問題; グラフ描画; ルーティング問題; 近似解法; 計算幾何学; 組合せ最適; 図形配置; データ構造; 非線形最適化; 情報可視化

In this study, we proposed "Multi-sphere Scheme" to efficiently pack given two- or three-dimensional objects in a compact space, designed all the components of the scheme, and investigated fundamental theory on geometrical packings and graph drawings. We designed an algorithm that can directly transform given triangle-mesh data into data for Multi-sphere Scheme based on a graph-theoretical analysis. We developed a 3D visual interface for Multi-sphere Scheme, by which we can easily check computational results in a visualized form. We greatly improved our solver for packing rectangles so that a long-standing open benchmark instance is solved for the first time by our new solver. As for the theory part, we found a 2D representation of triconnected graphs so that a useful triconnected decomposition can be easily obtained, and a characterization of the graphs of non-convex polytopes in a certain class.In particular, the latter result is the first such result since Steinitz' theorem, a characterization of the graphs of convex polytopes is found 80 years ago.

在这项研究中，我们提出了“多球方案”，以在紧凑空间中有两个或三维对象有效包装，设计了该方案的所有组成部分，并研究了几何包装和图形图的基本理论。我们设计了一种算法，可以基于图理论分析将给定的三角形数据直接转换为多球方案的数据。我们为多球方案开发了一个3D视觉界面，通过该方案，我们可以轻松地以可视化的形式检查计算结果。我们大大改善了求解器的矩形求解器，因此我们的新求解器首次解决了长期的开放基准实例。至于理论部分，我们发现了三连电图的2D表示，因此可以轻松地获得有用的三连电分解，并且在某个类别中的非convex多型的图表的表征尤其是后者的结果是自Steinitz'seorem以来的第一个这样的结果。

项目成果

Visualization can improve multiple decision table classifiers

可视化可以改进多个决策表分类器

• 发表时间: 2009
• 作者: 上田祐華;他;K.Haraguchi
• 通讯作者: K.Haraguchi

Efficient branch-and-bound algorithms for one-dimensional contiguous bin packing problem and two-dimensional strip packing problem

一维连续装箱问题和二维带状装箱问题的高效分支定界算法

• 发表时间: 2009
• 作者: T.Imamichi;Y.Arahori;H.Nagamochi
• 通讯作者: H.Nagamochi

Minimum Degree Orderings

• DOI: 10.1007/s00453-008-9239-2
• 发表时间: 2007-12
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: H. Nagamochi

Optimization problems and algorithms in double-layered food packing systems, Journal of Advanced Mechanical Design

双层食品包装系统的优化问题和算法，《先进机械设计杂志》

• 发表时间: 2010
• 期刊: Systems, and Manufacturing Vol.4, No.3
• 作者: Y.Karuno;H.Nagamochi;X.Wang
• 通讯作者: X.Wang

Exact algorithms for the 2-dimensional strip packing problem with and without rotations

带旋转和不带旋转的二维条带堆积问题的精确算法

• 发表时间: 2009
• 期刊: European Journal of Operational Research 198(1)
• 作者: M.Kenmochi;T.Imamichi;K.Nonobe;M.Yagiura;H.Nagamochi
• 通讯作者: H.Nagamochi