A Note on Tropical Linear and Integer Programs
A Note on Tropical Linear and Integer Programs
复制标题
关于热带线性和整数规划的注释
DOI：
10.1007/s10957-018-1429-8
复制
发表时间：
2018
影响因子：
1.9
通讯作者：
Butkovic P
中科院分区：
文献类型：
--
作者：
Butkovic P
我们提出了一个新的，简单的紧凑证明已知的强对偶定理的热带线性规划单侧约束。这一结果与子根向量的性质一起使我们能够直接求解一类特殊的双边约束热带线性规划问题。我们还研究了热带整数线性规划的对偶间隙。原问题有一个直接的解。对于对偶问题，给出了一个二次复杂度的算法。只要目标函数的系数都是整数，就可以直接求解.这种解决方案提供了一个很好的估计，在一般情况下的最佳目标函数值。
We present a new, simple compact proof of the known strong duality theorem of tropical linear programming with one-sided constraints. This result together with properties of subeigenvectors enables us to directly solve a special tropical linear program with two-sided constraints. We also study the duality gap in tropical integer linear programming. A direct solution is available for the primal problem. An algorithm of quadratic complexity is presented for the dual problem. A direct solution is available provided that all coefficients of the objective function are integer. This solution provides a good estimate of the optimal objective function value in the general case.
登录
查看更多内容
关于抽象对偶线性规划
DOI：
10.1002/nav.3800100131
发表时间：
1963
期刊：
Naval Research Logistics Quarterly
影响因子：
--
作者：
A. Hoffman
通讯作者：
A. Hoffman
可约谱理论及其在最大代数矩阵鲁棒性中的应用
影响因子：
1.5
作者：
Butkovic P
通讯作者：
Butkovic P
DOI：
10.1016/j.jsc.2011.12.049
发表时间：
2011-01
期刊：
J. Symb. Comput.
影响因子：
--
作者：
S. Gaubert;Ricardo D. Katz;Sergeĭ Sergeev
通讯作者：
S. Gaubert;Ricardo D. Katz;Sergeĭ Sergeev
关于整数最大线性规划问题
影响因子：
1.1
作者：
P. Butkovic;M. MacCaig
通讯作者：
M. MacCaig