Polyhedral Cutting Planes for General Mixed-Integer Programming

一般混合整数规划的多面体割平面

• 批准号: 0218265
• 负责人: Alper Atamturk
• 金额: $ 30万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0218265&HistoricalAwards=false
• 关键词: Polyhedral; Cutting; Planes; General; Mixed

This research project addresses the gap in the understanding of the polyhedral (geometric) structure of general mixed-integer programming problems. With an ultimate goal of developing efficient and effective cutting plane procedures for mixed-integer problems with general integer variables, strong cutting planes applicable to general mixed-integer problems will be identified through polyhedral analysis of fundamental single-constraint mixed-integer sets. The methods of the research are based on a recent work on sequence independent lifting of valid inequalities through the use of superadditive functions for general mixed-integer programming. The expected outcome of this research project is novel cutting plane procedures that will be incorporated in branch-and-cut algorithms for solving large-scale mixed-integer programming problems. If successful, the research project may lead to significant advances in the understanding of general mixed-integer polyhedra and in the solution methods for large-scale instances of mixed-integer problems with general integer variables.

本研究计画针对一般混合整数规划问题的多面体（几何）结构的理解上的差距。 最终目标是为具有一般整数变量的混合整数问题开发高效和有效的切割平面程序，将通过基本单约束混合整数集的多面体分析来确定适用于一般混合整数问题的强切割平面。研究的方法是基于最近的工作序列独立提升有效的不等式，通过使用一般的混合整数规划的超加性功能。 这个研究项目的预期成果是新的切割平面程序，将被纳入分支和切割算法解决大规模混合整数规划问题。如果成功的话，该研究项目可能会导致对一般混合整数多面体的理解和具有一般整数变量的混合整数问题的大规模实例的解决方法的重大进展。