Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables

• 成果类型: Article
• 署名作者: Chen, Rui; Luedtke, James
• 署名单位: University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02019-2
• 发表日期: 2024
• 页码: 357-388
• 关键词: lift-and-project; stochastic integer programs; decomposition algorithms; approximations

摘要

We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset I of the binary variables. We show that by restricting the support of the cut to the same set of variables I, a cut can be obtained by solving a linear program with 2(vertical bar I vertical bar) constraints. While this limits the size of the set I used to define the multi-term disjunction, the procedure enables generation of multi-term disjunctive cuts using far more terms than existing approaches. We present two approaches for choosing the subset of variables. Experience on three MILP problems with block diagonal structure using vertical bar I vertical bar up to size 10 indicates the sparse cuts can often close nearly as much gap as the multi-term disjunctive cuts without this restriction and in a fraction of the time. We also find that including these cuts within a cut-and-branch solution method for these MILP problems leads to significant reductions in solution time or ending optimality gap for instances that were not solved within the time limit. Finally, we describe how the proposed approach can be adapted to optimally tilt a given valid inequality by modifying the coefficients of a sparse subset of the variables.