An Exact Optimization Algorithm for Linear Decomposition of Index Generation Functions
An Exact Optimization Algorithm for Linear Decomposition of Index Generation Functions
复制标题
索引生成函数线性分解的精确优化算法
DOI：
10.1109/ismvl.2017.56
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Jon T. Butler
中科院分区：
文献类型：
--
作者：
Shinobu Nagayama;Tsutomu Sasao;Jon T. Butler
提出了一种基于分支定界法的索引生成函数线性分解的精确优化算法。该算法通过有效的分支和定界策略来修剪非最优解，从而有效地找到索引生成函数的最优线性分解。分支策略是基于我们以前的启发式[2]使用平衡决策树，和边界是基于线性分解所需的变量数量的下限。使用基准索引生成函数的实验结果表明，该方法具有最优的线性分解性能和策略的有效性。
This paper proposes an exact optimization algorithm based on a branch and bound method for linear decomposition of index generation functions. The proposed algorithm efficiently finds the optimum linear decomposition of an index generation function by pruning non-optimum solutions using effective branch and bound strategies. The branch strategy is based on our previous heuristic [2] using a balanced decision tree, and the bound is based on a lower bound on the number of variables needed for linear decomposition. Experimental results using a benchmark index generation function show its optimum linear decompositions and effectiveness of the strategies.