Sara Samir, Hoai An Le Thi, A Collaborative Approach Based on DCA and VNS for Solving Mixed Binary Linear Programs

Abstract: This paper addresses the Mixed Binary Linear Programming problems (MBLPs) by a collaborative approach using two component algorithms. The first is DCA (Difference of Convex functions Algorithm), an efficient deterministic algorithm in nonconvex programming framework, and the second is VNS (Variable Neighborhood Search), a well known metaheuristic method. The DCA and VNS are executed in parallel. At the end of each cycle, the best-found solution is exchanged between these algorithms via MPI (Message Passing Interface) library. The next cycle starts with the previous best-found solution as an initial solution. The performance of the proposed approach is tested on a set of benchmarks of the Capacitated Facility Location Problem. Numerical experiments show the efficiency of our approach.

 

Keywords: Mixed Binary Linear Programming problems, DC programming and DCA, Metaheuristics, Parallel and distributed programming.

 

Citation: Samir S., Le Thi H.A. (2019) A Collaborative Approach Based on DCA and VNS for Solving Mixed Binary Linear Programs. In: Nguyen N.T., Gaol F. L., Hong T.-P., TrawiƄski B. (eds) Intelligent Information and Database Systems. ACIIDS 2019. Lecture Notes in Computer Science, vol 11431, pp. 510-519, Springer, Cham.

 

Download link