Development and analysis of methods of approximation for NP-hard optimization problems

NP 困难优化问题的近似方法的开发和分析

• 批准号: RGPIN-2021-03828
• 负责人: Gaur, Daya
• 金额: $ 1.75万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742740
• 关键词: Development; analysis; methods; approximation; NP

The objective of this research is to develop new paradigms to design and analyze practical algorithms for a broad class of NP-hard optimization problems. We will build on our prior study on linear programming based algorithms for NP-hard optimization problems, supported by NSERC Discovery Grants since 2003. This research is both theoretical and applied in nature. It involves the development of new algorithms and proving properties about the quality of the solution. Below, we outline the general methodology, the specific problems and open questions particular to the proposed program are in the proposal. The approach of modelling a problem by an exponentially sized LP, solving it (possibly using the primal-dual method), and then converting the solution to an integer solution has been immensely successful (see books by Vazirani and Williamson and Shmoys). Both the LP and the rounding scheme are problem-specific. The difficulty is in obtaining a proper LP relaxation, and a good rounding scheme. Another approach is to round the LP one variable at a time. An optimal solution to the LP is used to determine the variable whose value will be fixed. Fixing the value of one variable leads to a new LP, and the iterative process solves the new LP and sets the value of another variable. This method of iterative rounding and has been hugely successful in solving problems in the area of network design (see the book by Lau et al.). Given an integer program say, min c x, A x >= b, define the integrality gap to be the supremum of the ratio of the cost of the optimal integral solution to the cost of the optimal fractional answer to the LP relaxation for all c, A, b. The rounding gives an integral solution, and the LP relaxation gives the lower bound. Therefore, the integrality gap of the integer program bounds the approximation ratio for this approach. Program with small integrality gap is thus highly desirable. This necessitates  the development of problem-specific cut constraints.  In support of the long term objectives the short term objectives of this research program are to develop  better approximation algorithms for asymmetric TSP, D2D channel allocation and minimum satisfiability.  We will work with problems where  there is inherent uncertainty on the  variables and cannot be described  by simple integer programs. This  research will develop methods to approximate the expected cost solutions  under uncertainty. We will use and augment Lagrangian based techniques in this program as well. This research program will improve our  theoretical understanding of the success of heuristics.  The research will also impact the praxis of algorithm design for NP-hard optimization problems. The research program will train a new generation of HQP ready to contribute to emerging technologies such as ML, Blockchain and Quantum, which rely on forever improved methods of optimization. It will generate knowledge with potential for commercialization.

本研究的目的是开发新的范式来设计和分析广泛的 NP 难优化问题的实用算法，我们将在 NSERC Discovery 的支持下建立基于线性规划的 NP 难优化问题算法的研究。自 2003 年起获得资助。这项研究本质上既是理论性的，又是应用性的。它涉及新算法的开发和解决方案质量的证明。下面，我们概述了所提议的程序的一般方法、具体问题和悬而未决的问题。都在提案中。通过指数大小的 LP 对问题进行建模，解决它（可能使用原对偶方法），然后将解决方案转换为整数解决方案，这种做法非常成功（参见 Vazirani 和 Williamson 和 Shmoys 的书籍）。舍入方案是特定于问题的，困难在于获得适当的 LP 松弛，而另一种方法是一次对 LP 舍入一个变量。用于确定其值将被固定的变量。固定一个变量的值会产生一个新的 LP，并且迭代过程求​​解新的 LP 并设置另一个变量的值，这种迭代舍入的方法非常成功。解决网络设计领域的问题（参见 Lau 等人的书）。给定一个整数程序，min c x, A x >= b，将完整性差距定义为 的比率的上界。的成本对所有 c、A、b 的 LP 松弛的最优分数答案的成本的最优积分解舍入给出积分解，并且 LP 松弛给出下界，因此，整数程序的完整性差距限制了 。因此，非常需要具有较小完整性差距的近似比率，因此需要制定针对特定问题的削减约束，以支持该研究计划的短期目标。非对称 TSP、D2D 信道分配和最小可满足性的近似算法 我们将解决变量存在固有不确定性且无法用简单整数程序描述的问题。在该计划中也使用和增强了基于拉格朗日的技术。该研究计划将提高我们对启发式成功的理论理解。该研究还将影响算法设计的实践。该研究项目将训练新一代 HQP，为机器学习、区块链和量子等新兴技术做出贡献，这些技术依赖于不断改进的优化方法，将产生具有商业化潜力的知识。