Novel Approaches to Mixed-Discrete and Nonconvex Programs: Polyhedral and Algebraic Methods

这项研究旨在开发新的方法，包括理论和计算，以有效地解决离散优化问题。虽然在实际中经常出现，但由于它们的组合性质，这类问题具有极大的挑战性；解空间随着决策变量的数量呈指数增长。有效的程序需要尖端理论和高速计算相结合。这一努力中使用的方法是将困难的问题重新塑造成变量更高的空间，以部分避免被指数增长所拖累。早些时候，考虑到这一目标，设计了一种用于离散变量取二进制“是-否”值的程序的“重构-线性化技术”(RLT)。各种类型的问题都取得了计算上的成功，从那时起，将低维空间提升到高维空间的想法就引起了相当大的关注。这项研究将融合代数和运筹学领域的贡献，以一种新颖的方式扩展和增强整个RLT过程。初步研究表明，RLT将其推广到混合离散问题，当被视为高结构矩阵的特殊乘积时，其论证可以变得更加简单和优雅。这一视角为重新制定方法提供了有价值的见解，并为研究开辟了令人兴奋的新途径。这些途径将被深入探索。预计研究将有助于解决目前无法获得和/或验证最佳解决方案的复杂问题。离散问题在许多情况下都很明显，包括电力分配、设施布局、资源分配和调度。这项研究还应该有助于对特殊决策程序的数学结构的一般理解，并导致对一般组合问题的改进方法。

This research is to develop new methods, both theoretical and computational, for efficiently solving discrete-optimization problems. Though arising frequently in practice, such problems are extremely challenging due to their combinatorial nature; the solution space grows exponentially in terms of the number of decision variables. Effective procedures require cutting-edge theory coupled with high-speed computing. The approach used in this effort is to recast difficult problems into higher-variable spaces so as to partially avoid being encumbered by the exponential growth. A "reformulation-linearization-technique" (RLT) for programs wherein the discrete variables take binary "yes-no" values was earlier designed with this objective in mind. Computational successes have been realized for various classes of problems, and the idea of lifting lower-dimensional spaces into higher-dimensional counterparts has since drawn considerable attention. This research will blend contributions from the fields of Algebra and Operations Research to extend and enhance the entire RLT process in a novel manner. Preliminary studies show that the RLT generalizes to mixed-discrete problems, and that the arguments can be made more simple and elegant when viewed as special products of highly-structured matrices. This perspective provides valuable insights into reformulation methods, and opens up exciting new avenues for research. These avenues will be explored in depth.The research is expected to contribute to the solving of complex problems for which optimal solutions cannot currently be obtained and/or verified. Discrete problems are evident in many contexts, including electric power distribution, facility layout, resource allocation, and scheduling. The study should also contribute to the general understanding of the mathematical structure of special decision programs, and lead to improved methods for combinatorial problems in general.