An ODE Approach to Multiple Choice Polynomial Programming

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 an MCPP problem into an 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 the 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. When compared with the numerical results obtained by using Gurobi to solve MCPP directly, our ODE approach is able to produce approximate solutions of better quality in most instances. This paper also serves as the first attempt to use a continuous algorithm for approximating the star discrepancy.