Conic Integer Programming

二次曲线整数规划

• 批准号: 0700203
• 负责人: Alper Atamturk
• 金额: $ 27.76万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-06-01 至 2011-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0700203&HistoricalAwards=false
• 关键词: Conic; Integer; Programming

A conic integer program is an integer programming problem with conic constraints. Conic constraints are used in modeling many engineering and science applications, such as recognition and classification of data for diagnosis of diseases, bounding risk and error in diverse areas including digital imaging, communication, and finance. This grant provides funding for the development of a theory of cutting plane algorithms for conic integer programming, as well as design and implementation of computational methods for solving practical applications of conic integer programming problems. A rigorous investigation of the convex hull structure of conic integer programs will be performed. In particular, conic cutting planes for the second-order conic integer constraint set will be developed by decomposing it into its simpler building blocks.If successful, the fundamental development and solution methods that will result from this project will be very useful in a wide range of engineering and science applications involving risk constraints and discrete decisions. One of the immediate outcomes of the project will be the development of novel cutting planes that can be used in branch-and-bound solvers for conic mixed integer programming. The employment of such cuts are expected to improve the performance of these software systems significantly.

二次整数规划是具有二次约束的整数规划问题。圆锥曲线约束用于许多工程和科学应用的建模，例如疾病诊断数据的识别和分类，包括数字成像、通信和金融在内的不同领域的风险和错误边界。该基金将用于发展圆锥整数规划的切割平面算法理论，以及设计和实现解决实际应用的圆锥整数规划问题的计算方法。将对二次整数程序的凸壳结构进行严格的研究。特别是，二阶圆锥整数约束集的圆锥切割平面将通过将其分解为更简单的构建块来开发。如果成功，这个项目的基本开发和解决方法将在涉及风险约束和离散决策的广泛工程和科学应用中非常有用。该项目的直接成果之一将是开发可用于二次混合整数规划的分支定界求解器的新型切割平面。采用这种削减预计将大大提高这些软件系统的性能。