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-难优化问题的实用算法。我们将建立在我们以前的研究线性规划为基础的算法NP难优化问题，由NSERC发现赠款自2003年以来的支持。本研究具有理论性和应用性。它涉及新算法的开发和证明解决方案的质量属性。下面，我们概述了一般的方法，具体的问题和开放的问题，特别是拟议的计划是在建议。通过指数规模的LP来建模问题，解决它（可能使用原始对偶方法），然后将解决方案转换为整数解决方案的方法非常成功（参见Vazirani和威廉姆森和Shmoys的书籍）。LP和舍入方案都是针对特定问题的。困难在于获得适当的LP松弛和良好的舍入方案。另一种方法是一次舍入LP一个变量。LP的最优解用于确定其值将被固定的变量。固定一个变量的值会产生一个新的LP，迭代过程求解新的LP并设置另一个变量的值。这种迭代舍入的方法在解决网络设计领域的问题方面取得了巨大的成功（见Lau等人的书）。给定一个整数规划，比如min c x，Ax>= B，定义完整性间隙为所有c，A，B的LP松弛的最优整数解的成本与最优分数答案的成本之比的上确界。四舍五入给出积分解，LP松弛给出下限。因此，整数规划的完整性差距限制了这种方法的近似比。因此，具有小的完整性差距的程序是非常可取的。这就需要开发针对具体问题的切割约束。 为了支持长期目标，本研究计划的短期目标是开发更好的非对称TSP、D2 D信道分配和最小可满足性的近似算法。我们将处理变量存在固有不确定性且无法描述的问题简单的整数规划。本研究将发展在不确定性下近似期望成本解的方法。我们将使用和增加拉格朗日为基础的技术在这个程序以及。 本研究计划将增进我们对数学成功的理论了解，也将影响NP难最佳化问题的演算法设计实务。该研究计划将培养新一代HQP，为ML、区块链和量子等新兴技术做出贡献，这些技术依赖于不断改进的优化方法。它将产生具有商业化潜力的知识。