Inexact feasibility pump for mixed integer nonlinear programming

详细信息    查看全文

• 作者：M. Li ; ¹ ; ^{liminEmily@sdnu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Q. Liu ^{lq_qsh@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Mixed integer nonlinear programming ; Feasibility pump ; Algorithms ; Inexactness ; Heuristic
• 刊名：Information Processing Letters
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：118
• 期：Complete
• 页码：110-116
• 全文大小：289 K

文摘

The mixed integer nonlinear programming (MINLP) problem as an optimization problem involves both continuous and discrete variables. Moreover, at least one of the functions defining the objective function or the constraints must be nonlinear. Because of its complexity, it is very difficult to obtain the exact optimal solution. Therefore, the heuristic methods for getting a feasible solution of MINLPs are very important in practice. The feasibility pump is one of the famous heuristic methods, which alternates between solving nonlinear programming (NLP) problems and mixed integer linear programming (MILP) relaxed master problems.

In this paper, we will extend the feasibility pump to the case where the NLP problems are solved inexactly and propose the convergence of this method under some conditions. Moreover, we present the study of inexactness of the Lagrange multipliers (which are returned negative) of the NLP subproblems.