A Hybrid Algorithm of Ant Colony and Benders Decomposition for Large-Scale Mixed-Integer Linear Programming

He Han (), Jie Cao and Ya-Jing Wang ()
Additional contact information
He Han: School of Management Science and Engineering, Nanjing University of Information Science & Technology, Nanjing Jiangsu 210044, P. R. China
Jie Cao: Xuzhou University of Technology, Xuzhou, Jiangsu 221018, P. R. China
Ya-Jing Wang: Shuozhou Meteorological Bureau of Shanxi Province, Shanxi, Shuozhou 038500, P. R. China

International Journal of Information Technology & Decision Making (IJITDM), 2024, vol. 23, issue 04, 1485-1507

Abstract: We propose a hybrid approach for solving problems of mixed-integer linear programming with two types of variables (MILPTTV). The hybrid approach includes three algorithms: (1) Benders decomposition; (2) the ant colony algorithm; (3) the feasible heuristic method. We decompose the programming problem into a master problem and a subproblem using Benders decomposition. The ant colony algorithm generates an initial solution for the master problem. A feasible heuristic is used to obtain feasible solutions as input to the subproblem, whereas the subproblem is solved to optimality by using a linear programming solver that is named Linprog function in MATLAB R2016a. Over successive iterations, the master problem is refined by adding cuts from the subproblem and the master problem is solved by a linear programming solver Cplexmilp function. We compare the performance of the proposed hybrid approach against a general Benders decomposition approach as well as against a mixed-integer programming solver CPLEX (version 12.6) that is invoked by MATLAB on MIPLIB test problem mas76, mas74 and some large-scale numerical examples.

Keywords: The MILPTTV problem; ant colony algorithm; Benders decomposition; feasible heuristic (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219622023500335
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijitdm:v:23:y:2024:i:04:n:s0219622023500335

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219622023500335

Access Statistics for this article

International Journal of Information Technology & Decision Making (IJITDM) is currently edited by Yong Shi

More articles in International Journal of Information Technology & Decision Making (IJITDM) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().