DC programming approach for mixed-integer nonlinear programming problems (The state-of-the-art optimization technique and future development)

Abstract

In this paper, we consider a class of mixed integer programming problems (MIPs) whose objective functions are DC functions, that is, functions representable in terms of a difference of two convex functions, and particularly focus on the nonconvex case. Recently, Maehara, Marumo, and Murota provided a continuous reformulation without integrality gaps, for discrete DC programs having only integral variables. They also presented a new algorithm to solve the reformulated problem. Our aim is to extend their results to MIPs and further give a new algorithm to solve them. Specifically, we propose an algorithm based on DCA originally proposed by Pham Dinh and Le Thi, where convex MFs are solved iteratively.