Development of an exact method for zero-one linear programming model

Authors

DOI:

https://doi.org/10.15587/1729-4061.2020.211793

Keywords:

0–1 LP, unimodular, clique inequalities, feasible test, variable sum, double

Abstract

The paper presents a new method for solving the 0–1 linear programming problems (LPs). The general 0–1 LPs are believed to be NP-hard and a consistent, efficient general-purpose algorithm for these models has not been found so far. Cutting planes and branch and bound approaches were the earliest exact methods for the 0–1 LP. Unfortunately, these methods on their own failed to solve the 0–1 LP model consistently and efficiently. The hybrids that are a combination of heuristics, cuts, branch and bound and pricing have been used successfully for some 0–1 models. The main challenge with these hybrids is that these hybrids cannot completely eliminate the threat of combinatorial explosion for very large practical 0–1 LPs. In this paper, a technique to reduce the complexity of 0–1 LPs is proposed. The given problem is used to generate a simpler version of the problem, which is then solved in stages in such a way that the solution obtained is tested for feasibility and improved at every stage until an optimal solution is found. The new problem generated has a coefficient matrix of 0 s and 1 s only. From this study, it can be concluded that for every 0–1 LP with a feasible optimal solution, there exists another 0–1 LP (called a double in this paper) with exactly the same optimal solution but different constraints. The constraints of the double are made up of only 0 s and 1 s. It is not easy to determine this double 0–1 LP by mere inspection but can be obtained in stages as given in the numerical illustration presented in this paper. The 0–1 integer programming models have applications in so many areas of business. These include large economic/financial models, marketing strategy models, production scheduling and labor force planning models, computer design and networking models, military operations, agriculture, wild fire fighting, vehicle routing and health care and medical models

Supporting Agency

  • We are grateful to the editor and the anonymous referees. We also take this opportunity to thank NWU Faculty of Economic and Management Sciences (FEMS) for the unwavering research support.

Author Biography

Elias Munapo, North West University Mmabatho Unit 5, Mahikeng, 2790, Mafikeng, South Africa

PhD, Professor of Operations Research

Department of Statistics and Operations Research

School of Economics and Decision Sciences

References

  1. Land, A. H., Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28 (3), 497. doi: https://doi.org/10.2307/1910129
  2. Dakin, R. J. (1965). A tree-search algorithm for mixed integer programming problems. The Computer Journal, 8 (3), 250–255. doi: https://doi.org/10.1093/comjnl/8.3.250
  3. Al-Rabeeah, M., Munapo, E., Al-Hasani, A., Kumar, S., Eberhard, A. (2019). Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models. International Journal of Mathematical, Engineering and Management Sciences, 4 (5), 1140–1153. doi: https://doi.org/10.33889/ijmems.2019.4.5-090
  4. Djeumou Fomeni, F., Kaparis, K., Letchford, A. N. (2020). A cut-and-branch algorithm for the Quadratic Knapsack Problem. Discrete Optimization, 100579. doi: https://doi.org/10.1016/j.disopt.2020.100579
  5. Brunetta, L., Conforti, M., Rinaldi, G. (1997). A branch-and-cut algorithm for the equicut problem. Mathematical Programming, 78 (2), 243–263. doi: https://doi.org/10.1007/bf02614373
  6. Mitchell, J. E. (2001). Branch and cut algorithms for integer programming. Encyclopedia of Optimization. Kluwer Academic Publishers.
  7. Padberg, M., Rinaldi, G. (1991). A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM Review, 33 (1), 60–100. doi: https://doi.org/10.1137/1033004
  8. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., Vance, P. H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46 (3), 316–329. doi: https://doi.org/10.1287/opre.46.3.316
  9. Savelsbergh, M. (1997). A Branch-and-Price Algorithm for the Generalized Assignment Problem. Operations Research, 45 (6), 831–841. doi: https://doi.org/10.1287/opre.45.6.831
  10. Barnhart, C., Hane, C. A., Vance, P. H. (2000). Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems. Operations Research, 48 (2), 318–326. doi: https://doi.org/10.1287/opre.48.2.318.12378
  11. Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. de, Reis, M., Uchoa, E., Werneck, R. F. (2005). Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming, 106 (3), 491–511. doi: https://doi.org/10.1007/s10107-005-0644-x
  12. Ladányi, L., Ralphs, T. K., Trotter, L. E. (2001). Branch, Cut, and Price: Sequential and Parallel. Computational Combinatorial Optimization, 223–260. doi: https://doi.org/10.1007/3-540-45586-8_6
  13. Taha, H. A. (2017). Operations Research: An Introduction. Pearson Educators.
  14. Winston, W. L. (2004). Operations Research Applications and Algorithms. Duxbury Press.
  15. Arbib, C., Pınar, M. Ç., Rossi, F., Tessitore, A. (2020). Codon optimization by 0-1 linear programming. Computers & Operations Research, 119, 104932. doi: https://doi.org/10.1016/j.cor.2020.104932
  16. Han, B., Li, Y., Geng, S. (2017). 0–1 Linear programming methods for optimal normal and pseudo parameter reductions of soft sets. Applied Soft Computing, 54, 467–484. doi: https://doi.org/10.1016/j.asoc.2016.08.052
  17. Kodama, A., Nishi, T. (2017). Petri net representation and reachability analysis of 0–1 integer linear programming problems. Information Sciences, 400-401, 157–172. doi: https://doi.org/10.1016/j.ins.2017.03.014
  18. Demiröz, B. E., Altınel, İ. K., Akarun, L. (2019). Rectangle blanket problem: Binary integer linear programming formulation and solution algorithms. European Journal of Operational Research, 277 (1), 62–83. doi: https://doi.org/10.1016/j.ejor.2019.02.004
  19. Bakhshi–Jafarabadi, R., Sadeh, J., Soheili, A. (2019). Global optimum economic designing of grid-connected photovoltaic systems with multiple inverters using binary linear programming. Solar Energy, 183, 842–850. doi: https://doi.org/10.1016/j.solener.2019.03.019
  20. Commoner, F. G. (1973). A sufficient condition for a matrix to be totally unimodular. Networks, 3 (4), 351–365. doi: https://doi.org/10.1002/net.3230030406

Downloads

Published

2020-10-31

How to Cite

Munapo, E. (2020). Development of an exact method for zero-one linear programming model. Eastern-European Journal of Enterprise Technologies, 5(4 (107), 6–10. https://doi.org/10.15587/1729-4061.2020.211793

Issue

Vol. 5 No. 4 (107) (2020): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2020 Elias Munapo

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.