Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy

• 成果类型: Article
• 署名作者: Baena, Daniel; Castro, Jordi; Frangioni, Antonio
• 署名单位: Universitat Politecnica de Catalunya; University of Pisa
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2019.3341
• 发表日期: 2020
• 页码: 3051-3068
• 关键词: Benders decomposition; mixed-integer linear problems; stabilization; local branching; large-scale optimization; statistical tabular data protection; cell-suppression problem

摘要

The cell-suppression problem (CSP) is a very large mixed-integer linear problem arising in statistical disclosure control. However, CSP has the typical structure that allows application of the Benders decomposition, which is known to suffer from oscillation and slow convergence, compounded with the fact that the master problem is combinatorial. To overcome this drawback, we present a stabilized Benders decomposition whose master is restricted to a neighborhood of successful candidates by local-branching constraints, which are dynamically adjusted, and even dropped, during the iterations. Our experiments with synthetic and real-world instances with up to 24,000 binary variables, 181 million (M) continuous variables, and 367M constraints show that our approach is competitive with both the current state-of-the-art code for CSP and the Benders implementation in CPLEX 12.7. In some instances, stabilized Benders provided a very good solution in less than 1 minute, whereas the other approaches found no feasible solution in 1 hour.