Strong formulations of robust mixed 0-1 programming

• 成果类型: Article
• 署名作者: Atamtuerk, Alper
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0709-5
• 发表日期: 2006
• 页码: 235-250
• 关键词: Optimization

摘要

We introduce strong formulations for robust mixed 0-1 programming with uncertain objective coefficients. We focus on a polytopic uncertainty set described by a ``budget constraint'' for allowed uncertainty in the objective coefficients. We show that for a robust 0-1 problem, there is an alpha-tight linear programming formulation with size polynomial in the size of an alpha-tight linear programming formulation for the nominal 0-1 problem. We give extensions to robust mixed 0-1 programming and present computational experiments with the proposed formulations.