Integer programming and difference of convex (DC) optimization

We introduce an approach to solve a mixed binary linear programming (BLP) problem via DC (differences of convex) optimization. Starting from the non-linear counterpart of BLP, we define an exact penalty version of it. The resulting linear constrained concave minimization problem can be restated by rewriting the objective as the difference of two convex functions. We propose a new DCA two-phase algorithm defined by exploiting the structural properties of our problem. The first phase only ensures the convergence to a feasible solution. Thus, we introduce a second phase heuristic escape approach which is based on the global optimality conditions in terms of epsilon- subdifferential for the convex-constrained DC problem. Some computational results comparing our algorithm with those available in the literature are also discussed.