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

This project mainly studies mixed-integer programming (MIP) and its algorithms, including mixed-integer linear programming and mixed-integer nonlinear programming. For mixed-integer linear programming, we pay more attention to the presolving method and cutting plane method under the branch and bound framework in order to find the feasible solutions and verify the optimal solution. For mixed-integer nonlinear programming, on the one hand, we will study a nonsmooth convex MINLP and construct the outer approximation algorithm for finding its optimal solutions. On the other hand, we will investigate a nonsmooth MINLP with conic constraint and construct the generalized Bender algorithm to solve this MINLP. These implementation of two algorithms will be completed by some results in mixed-integer programming and its solvers.

本项目计划研究混合整数规划及其求解算法，包括混合整数线性规划和混合整数非线性规划。针对混合整数线性规划问题，本项目主要考虑分支定界框架下的预处理和割平面求解算法，快速找到可行解并验证最优解。针对混合整数非线性规划问题，一方面，本项目计划研究非光滑凸混合整数非线性规划问题及其求解的外逼近算法；另一方面，本项目拟研究锥约束混合整数非线性规划问题及其求解的广义本德斯算法。两类混合整数非线性规划问题的算法，本项目将主要考虑借助混合整数线性规划成果及求解器实现。

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