混合整数规划若干算法研究

Mixed integer programming involves mixed integer linear programming (MILP) and mixed integer nonlinear programming (MINLP). This program mainly studies nonsmooth MINLPs and their solution algorithms. By outer approximation method, we will study a nonsmooth convex MINLP and construct an outer approximation algorithm for finding its optimal solution. Using Benders decomposition, we will investigate a MINLP with conic constraint and establish the generalized Bender algorithm to solve this MINLP. These two algorithm implementation will be completed by MILP solvers.

混合整数规划包括混合整数线性规划和混合整数非线性规划。本项目拟研究非光滑混合整数非线性规划问题及求解算法。利用外逼近方法，本项目拟研究非光滑凸混合整数非线性规划问题，拟构造外逼近算法求解此类问题的最优解。借助本德斯分解方法，本项目拟研究锥约束混合整数非线性规划问题，拟构造广义本德斯算法求解此类问题的最优解。两类问题的求解算法拟考虑借助混合整数线性规划求解器实现。

本项目研究了一类极小-极大非光滑混合整数非线性规划问题及求解算法。利用函数次梯度及外逼近方法，我们将该问题化归为等价的混合整数线性规划（MILP）问题，构造外逼近算法求解MILP问题的松弛问题以得到原问题的最优解；进一步，我们证明了所建立算法有限步终止。针对锥约束混合整数规划问题，我们利用广义本德斯分解将该问题化归为等价的MILP问题，并构造广义本德斯分解算法求解MILP问题以得到原问题的最优解。作为应用，我们将所建立的算法应用于求解混合整数二阶锥规划问题。此外，我们还研究了给定函数的全局优化问题，建立了若干充分条件以确保全局最小值点的存在性。