论文标题
多项式编程的颂歌方法
An ODE approach to multiple choice polynomial programming
论文作者
论文摘要
在假设最佳点可以通过所谓的热平衡的期望值近似，我们提出了一种解决多项式编程（MCPP）的ode方法，就像在模拟退火中一样。可行区域的明确形式和目标函数的仿射特性都在将MCPP问题转换为ODE系统时都完全利用。从理论上讲，我们还可以从后者的平衡点获得前者的局部最佳。关于两个典型组合问题的数值实验，最大$ $ $ $ cut和恒星差异的计算，证明了我们的ODE方法的有效性，而所得的近似解决方案的质量与最先进的启发式启发式算法获得的质量可比，但成本要少得多。本文也是第一次使用连续算法来近似恒星差异的尝试。
We propose an ODE approach to solving multiple choice polynomial programming (MCPP) after assuming that the optimum point can be approximated by the expected value of so-called thermal equilibrium as usually did in simulated annealing. The explicit form of the feasible region and the affine property of the objective function are both fully exploited in transforming the MCPP problem into the ODE system. We also show theoretically that a local optimum of the former can be obtained from an equilibrium point of the latter. Numerical experiments on two typical combinatorial problems, MAX-$k$-CUT and the calculation of star discrepancy, demonstrate the validity of our ODE approach, and the resulting approximate solutions are of comparable quality to those obtained by the state-of-the-art heuristic algorithms but with much less cost. This paper also serves as the first attempt to use a continuous algorithm for approximating the star discrepancy.
