DYNAMICAL METHODS FOR SOLVING MIXED-INTEGER OPTIMIZATION PROBLEMS

摘要

A dynamical method and system generate a global optimal solution to a mixed integer nonlinear programming (MINLP) problem, where a part or all of optimization variables of the MINLP problem are restricted to have discrete values. Relaxed continuous problems of the MINLP problem are generated. For each relaxed continuous problem that has an integer solution with an objective value superior to a current bound, the method updates the current bound with the objective value, computes a set of stable equilibrium points (SEPs) around the integer solution in a nonlinear dynamical system associated with the relaxed continuous problem, identifies from the SEPs a set of starting points for the MINLP problem, and computes a set of integer solutions to the MINLP problem with progressively tightened bounds from the starting points using an MINLP solver. The global optimal solution is generated based on the integer solutions.

主权项

1. A computer-implemented method for generating a global optimal solution to a mixed integer nonlinear programming (MINLP) problem wherein a part or all of optimization variables of the MINLP problem are restricted to have discrete values, the method comprising:
generating by a computer system a plurality of relaxed continuous problems of the MINLP problem; for each of the relaxed continuous problems that has an integer solution with an objective value superior to a current bound, updating the current bound with the objective value and performing the following:
computing a set of stable equilibrium points (SEPs) around the integer solution in a nonlinear dynamical system associated with the relaxed continuous problem;identifying from the SEPs a set of starting points for the MINLP problem; andcomputing a set of integer solutions to the MINLP problem with progressively tightened bounds from the starting points using an MINLP solver; and generating by the computer system the global optimal solution based on the integer solutions.