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

混合离散和非凸规划的新方法：多面体和代数方法

• 批准号: 0423415
• 负责人: Warren Adams
• 金额: --
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0423415&HistoricalAwards=false
• 关键词: Novel; Approaches; Mixed; Discrete; Nonconvex

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.

本研究旨在开发新的方法，理论和计算，有效地解决离散优化问题。 虽然经常出现在实践中，这样的问题是极具挑战性的，由于其组合的性质;解决方案空间的决策变量的数量呈指数增长。 有效的程序需要尖端理论和高速计算。 在这一努力中使用的方法是重铸困难的问题到更高的变量空间，以部分避免被指数增长的阻碍。 一个“重新制定线性化技术”（RLT）的程序，其中离散变量采取二进制“是-否”的值是早期设计的这一目标铭记。 计算上的成功已经实现了各种类型的问题，并提升低维空间到高维对应的想法已经引起了相当大的关注。 这项研究将融合来自代数和运筹学领域的贡献，以一种新的方式扩展和增强整个RLT过程。 初步研究表明，RLT推广到混合离散问题，并认为参数可以更简单和优雅的高度结构化矩阵的特殊产品时，被视为。 这种观点提供了宝贵的见解重新制定的方法，并开辟了令人兴奋的新途径的研究。 将深入探讨这些途径，预计研究将有助于解决目前无法获得和/或验证最佳解决方案的复杂问题。 离散问题在许多情况下是显而易见的，包括电力分配，设施布局，资源分配和调度。 这项研究也应该有助于一般的理解的数学结构的特殊决策程序，并导致改进的方法，一般的组合问题。