SGER: Branch Decomposition Techniques for Independence Systems

该基金资助发展新的数值技术，以解决运筹学中计算困难的数学问题，这些问题在电信、生物学、调度、电子带宽分配、超大规模集成电路设计、设施布局设计和编码理论等领域有相关应用。所开发的技术将用于提高该研究领域所解决问题的可扩展性。具体地说，本研究将把新的分解技术，即分支分解技术，与现有的传统方法相结合，以寻找与感兴趣问题相关的多面体的新不等式。将开发的技术与文献中的其他精确算法进行比较，以验证和评估技术的计算效率。如果成功，结果将提高解决感兴趣问题的可伸缩性和效率。这些问题的应用是在对服务需求增加的领域。此外，该结果可用于解决运筹学中其他相关的计算难题，这些问题除上述应用外具有广泛的应用范围。因此，研究结果将促进运筹学的知识基础，并为解决与现实世界应用相关的大规模问题提供新的有效技术。

This grant provides funding for the development of novel numerical techniques to solve computationally hard mathematical problems in operations research that have relevant applications in telecommunications, biology, scheduling, electronic bandwidth allocation, VLSI design, facility layout design, and coding theory. The developed techniques will used to increase the scalability of problems solved in this research area. Specifically, the research will integrate novel decomposition techniques, called branch decomposition techniques, with the existing traditional methodology to find new inequalities for the polyhedra related to the problems of interest. The developed techniques will be compared with other exact algorithms in the literature to validate and assess the computational efficacy of the techniques.If successful, the results will increase the scalability and efficiency of solving the problems of interest. Applications of these problems are in fields seeing increased demand for services. In addition, the results can be used to solve other related computationally hard problems in operations research which have a wide range of applications apart from the aforementioned applications. Thus, the results will advance the knowledge base in operations research and offer new effective techniques for solving large-scale problems related to real-world applications.