Year: 2025
Author: Sihong Shao, Yishan Wu
East Asian Journal on Applied Mathematics, Vol. 15 (2025), Iss. 1 : pp. 1–28
Abstract
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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/eajam.2023-184.151023
East Asian Journal on Applied Mathematics, Vol. 15 (2025), Iss. 1 : pp. 1–28
Published online: 2025-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 28
Keywords: Pseudo-Boolean optimization multiple choice constraint continuous approach MAX-CUT star discrepancy.