A new approach for solving mixed integer DC programs using a continuous relaxation with no integrality gap and smoothing techniques

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. These MIPs contain a very wide class of computationally difficult non-convex MIPs since the DC functions have powerful expressability. Recently, Maehara, Marumo, and Mutota 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 give two specific algorithms to solve them. First, we propose an algorithm based on DCA originally proposed by Pham Dinh and Le Thi, where convex MIPs are solved iteratively. Next, to handle non-smooth functions efficiently, we incorporate a smoothing technique into the first method. We show that sequences generated by the two methods converge to stationary points under some mild assumptions.

Keywords:

• Mixed integer DC program
• integrality gap
• closed convex extension
• smoothing method

2010 Mathematics Subject Classifications:

• 90C11
• 90C26

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 This property is specific to the case where the DCA is applied to (11(11) $\underset{x\in {\mathbb{R}}^n}{min}\{{\tilde{g}}^{\mathrm{c}\mathrm{l}}\left(x\right)-h\left(x\right)\}.$(11) ). For the proof, see the convergence analysis of the next algorithm.

Additional information

Funding

This work was supported by JSPS-Japan Society for the Promotion of Science KAKENHI [grant number 15K15943].