IDEAS home Printed from https://ideas.repec.org/a/wsi/ijitdm/v23y2024i04ns0219622023500335.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • He Han & Jie Cao & Ya-Jing Wang, 2024. "A Hybrid Algorithm of Ant Colony and Benders Decomposition for Large-Scale Mixed-Integer Linear Programming," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 23(04), pages 1485-1507, July.
    • Handle: RePEc:wsi:ijitdm:v:23:y:2024:i:04:n:s0219622023500335
    DOI: 10.1142/S0219622023500335
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0219622023500335
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0219622023500335?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:ijitdm:v:23:y:2024:i:04:n:s0219622023500335. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/ijitdm/ijitdm.shtml .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.