TRUST-TECH ENHANCED 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. The method computes a first integer solution to the MINLP problem with a given starting point using an MINLP solver; computes a set of stable equilibrium points (SEPs) of a nonlinear dynamical system associated with a relaxed continuous problem of the MINLP problem, where the SEPs surround the first integer solution and form one or more tiers; identifies from the SEPs a set of new starting points for the MINLP problem; computes integer solutions to the MINLP problem with progressively tightened bounds, starting from the new starting points using the MINLP solver; and generates the global optimal solution based on the integer solutions after one or more iterations.

主权项

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:
computing by a computer system a first integer solution to the MINLP problem with a given starting point using an MINLP solver; computing a set of stable equilibrium points (SEPs) of a nonlinear dynamical system associated with a relaxed continuous problem of the MINLP problem, wherein the SEPs surround the first integer solution and form one or more tiers; identifying from the SEPs a set of new starting points for the MINLP problem; computing integer solutions to the MINLP problem with progressively tightened bounds, starting from the new starting points using the MINLP solver; and generating by the computer system the global optimal solution based on the integer solutions after one or more iterations of computing the SEPs, identifying the new starting points and computing the integer solutions.