Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2212.06371 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913685352480768 |
|---|---|
| author | Shao, Sihong Wu, Yishan |
| author_facet | Shao, Sihong Wu, Yishan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06371 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An ODE approach to multiple choice polynomial programming Shao, Sihong Wu, Yishan Optimization and Control Combinatorics 90C59, 35Q90, 90C09, 90C23 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. |
| title | An ODE approach to multiple choice polynomial programming |
| topic | Optimization and Control Combinatorics 90C59, 35Q90, 90C09, 90C23 |
| url | https://arxiv.org/abs/2212.06371 |