A New Generation of Neural Network Optimization Techniques with Applications to Manufacturing Scheduling

点击翻译按钮获取中文摘要

9813176Luh Many exciting results on neural networks have been obtained over the past two decades, with most successful applications in the areas of pattern recognition and signal processing. Developing neural networks for mathematical optimization has been a new thrust, holding much promise for overcoming the difficulties in solving large combinatorial optimization problems. This research is to further advance neural networks for the very common but notoriously difficult "NP hard" combinatorial optimization problems. The focus will be on integer optimization problems with specialized "separable" structure, since they encompass a wide range of scheduling and other important applications, and often lead to efficient methods with orders of magnitude performance improvement. The first task is to lay a solid foundation for neural optimization by exploring theoretical issues such as stability and convergence properties using recent algorithm convergence results. The second task explores effective ways to solve manufacturing scheduling problems by developing "neural dynamic programming" for solving subproblems. This novel neural dynamic programming transcends the majority of computational difficulties associated with solving subproblems such as infeasibility, local minima, and slow convergence of subproblem solutions, and in addition is amenable to efficient hardware implementation. The third task seeks hardware implementation of the approach to achieve very high solution quality and computation speed. The successful development of neural networks for separable integer optimization will result in a new generation of methods to obtain near-optimal solutions with quantifiable quality in a computationally efficient manner. The effective resolution of realistic scheduling problems will also have practical impact on the bottom line of our industrial partners and beyond. The hardware implementation then has a strong potential to achieve very high solution quality and computation speed for a wide range of business and engineering applications. The vision is to have a VLSI "digital optimizer" chip to be plugged into PCs to help solve a wide range of business and engineering optimization problems.