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

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

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.