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

小行星9813176 在过去的二十年里，神经网络已经取得了许多令人兴奋的成果，其中最成功的应用领域是模式识别和信号处理。 发展神经网络用于数学优化已经成为一个新的推动力，为克服解决大型组合优化问题的困难提供了很大的希望。 这项研究是为了进一步推进神经网络用于非常常见但非常困难的“NP难”组合优化问题。 重点将是专门的“可分离”结构的整数优化问题，因为它们包含了广泛的调度和其他重要的应用程序，并往往导致有效的方法与数量级的性能改善。 第一个任务是通过使用最近的算法收敛结果探索稳定性和收敛特性等理论问题，为神经优化奠定坚实的基础。第二个任务探索有效的方法来解决制造调度问题，通过发展“神经动态规划”解决子问题。 这种新颖的神经动态规划超越了大多数与解决子问题相关的计算困难，如不可行性，局部极小值和子问题解决方案的收敛速度慢，此外还适合于高效的硬件实现。 第三项任务寻求该方法的硬件实现，以实现非常高的解决方案质量和计算速度。 可分离整数优化神经网络的成功开发将导致新一代方法以计算高效的方式获得具有可量化质量的接近最优的解决方案。 实际调度问题的有效解决也将对我们的工业合作伙伴及其他方面的底线产生实际影响。 然后，硬件实现具有很强的潜力，以实现非常高的解决方案质量和计算速度，为广泛的业务和工程应用。 该公司的愿景是将一个超大规模集成电路（VLSI）“数字优化器”芯片插入个人电脑，以帮助解决广泛的商业和工程优化问题。

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.