混合整数半无限规划问题

Mixed integer semi-infinite programming problem

本文主要讨论混合整数半无限规划(mixed integer semi-infinite programming, MISIP)问题的求解方法.首先分离内层约束中的连续变量和整数变量并将原问题转化为混合整数互补约束规划(mixed integer mathematical programming with complementarity constraints, MIMPCC)问题.其次在假设内层问题满足Slater约束规范的条件下得到了转化前后问题的等价性.继而分别将MIMPCC问题转化为可用常规优化软件求解的混合整数规划问题和非线性规划问题.由于在转化过程中会生成大量的变量和约束,为求解内层问题中变量较多的MISIP问题,本文提出一种行约束生成法,并证明该算法可在最多O(|Z|)次迭代之后得到最优解.最后通过一些数值实例验证算法的有效性.

This paper focuses on mixed integer semi-infinite programming(MISIP). We firstly reformulate the MISIP as a mixed integer mathematical programming with complementarity constraints(MIMPCC) by separating the inner continuous and integer variables. Then, the equivalence of the global and local optimal solutions of the MISIP and the MIMPCC are discussed under the assumption that the inner problem satisfies Slater’s constraint qualification. After that, we reformulate the MISIP as a mixed integer programming(MIP) or a nonlinear programming(NLP) that can be solved by standard numerical softwares. In order to solve the MISIP with many inner variables, we propose a line-and-constraint generation method which converges to an optimal solution with O(|Z|) iterations. Finally, some numerical examples are given to show the effectiveness of the two methods.