Journals
Resources
About Us
Open Access

An ODE Approach to Multiple Choice Polynomial Programming

An ODE Approach to Multiple Choice Polynomial Programming

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.

Author Details

Sihong Shao

Yishan Wu