Application of Multiple Equilibrium Point Search in Gradient Systems to Mixed-Integer Programming

摘要

This paper proposes a solution to mixed-integer programming by using a gradient system and searching for multiple equilibrium points in the system. The method is available when the objective function of a problem is continuous and differentiable. In order to find feasible solutions of a mixed-integer programming problem by gradient systems, discrete decision variables are treated as continuous ones. We demonstrate a systematic way to build the kind of gradient systems in which equilibrium points are embedded at feasible solutions of a mixed-integer problem. For numerical computation, the multiple equilibrium points search method we have already proposed is available and its adjustments to improve efficiency and certainty for mixed-integer programming are also proposed in this paper. Results for some problems show the effectiveness of our method: high ability of thorough search and high quality of derived solutions.