Integer Programming Problems with Fermatean Fuzzy Parameters Using NAZ-Cut

Authors

  • Sheema Sadia * Department of Statistics and Operations Research, Aligarh Muslim University, Aligarh, 202002, India.

https://doi.org/10.22105/opt.v2i1.75

Abstract

Integer Programming Problems (IPPs) play a critical role in solving real-world optimization scenarios where decision variables must be integers, such as in scheduling, logistics, and resource allocation. Traditional methods like Branch and Bound and Cutting Plane techniques have been widely used for solving such problems. In 2003, Bari and Ahmad introduced the NAZ-cut method, a straightforward and computationally efficient approach to solving IPPs by systematically reducing the feasible solution space through the addition of specific constraints. This paper presents an enhanced NAZ-cut framework for solving IPPs, particularly in the context of Fermatean fuzzy environments, where uncertainty in parameters is modeled using Fermatean fuzzy sets. A new approach is proposed to minimize computational effort by excluding specific integer candidate solutions based on a well-defined criterion. A supporting theorem is provided to justify this exclusion, ensuring that only feasible and potentially optimal points are considered. The method is demonstrated through a numerical example, highlighting the effectiveness of the proposed strategy in simplifying the search process and improving computational efficiency.

Keywords:

NAZ cut, Fermatean fuzzy paramaters, Branch and bound methods, Cutting plane methods, Optimization

References

  1. [1] Antunes, C. H., Alves, M. J., & Clímaco, J. (2016). Multiobjective linear and integer programming. Cham, Switzerland: Springer. https://link.springer.com/book/10.1007/978-3-319-28746-1
  2. [2] Wolsey, L. A. (2020). Integer programming. John Wiley & Sons. https://www.wiley.com/en-us/Integer+Programming%2C+2nd+Edition-p-9781119606536
  3. [3] Paneque, M. P., Bierlaire, M., Gendron, B., & Azadeh, S. S. (2021). Integrating advanced discrete choice models in mixed integer linear optimization. Transportation research part b: methodological, 146, 26–49. https://doi.org/10.1016/j.trb.2021.02.003
  4. [4] Cornuéjols, G., Trick, M. A., & Saltzman, M. J. (1995). A tutorial on integer programming. https://cs.wmich.edu/gupta/teaching/cs6310/lectureNotes_cs6310/integer%20LP%20applications%20and%20solutions%20from%20Clemson%201995.pdf
  5. [5] Papalexopoulos, T. P., Tjandraatmadja, C., Anderson, R., Vielma, J. P., & Belanger, D. (2022, June). Constrained discrete black-box optimization using mixed-integer programming. International Conference on Machine Learning (pp. 17295-17322). PMLR. https://proceedings.mlr.press/v162/papalexopoulos22a.html
  6. [6] Pisaruk, N. (2019). Mixed integer programming: Models and methods. Minsk: bsu. https://www.researchgate.net
  7. [7] Naderi, B., Ruiz, R., & Roshanaei, V. (2023). Mixed-integer programming vs. constraint programming for shop scheduling problems: new results and outlook. INFORMS journal on computing, 35(4), 817–843. https://doi.org/10.1287/ijoc.2023.1287
  8. [8] Carter, M., Price, C. C., & Rabadi, G. (2018). Operations research: a practical introduction. Chapman and Hall/CRC. https://www.taylorfrancis.com/books/mono/10.1201/9781315153223/operations-research-michael-carter-camille-price-ghaith-rabadi
  9. [9] Shoukat, R. (2024). Integrated supply chain plan under multiple distribution networks: an implementation of mixed integer linear programming. Circular economy and sustainability, 4(4), 2599–2623. https://doi.org/10.1007/s43615-024-00404-3
  10. [10] Kardoš, J. (2020). High-performance interior point methods [Thesis] https://folia.unifr.ch/global/documents/319135
  11. [11] Kemppainen, E. (2020). Imcomplete maxsat solving by linear programming relaxation and rounding. [Thesis]. https://helda.helsinki.fi/server/api/core/bitstreams/06c4b179-235b-4f52-832a-62094d508f61/content
  12. [12] Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete optimization, 19, 79–102. https://doi.org/10.1016/j.disopt.2016.01.005
  13. [13] Basu, A., Conforti, M., Di Summa, M., & Jiang, H. (2023). Complexity of branch-and-bound and cutting planes in mixed-integer optimization. Mathematical programming, 198(1), 787–810. https://doi.org/10.1007/s10107-022-01789-5
  14. [14] Deza, A., & Khalil, E. B. (2023). Machine learning for cutting planes in integer programming: A survey. ArXiv preprint arxiv:2302.09166. https://arxiv.org/abs/2302.09166
  15. [15] Jiao, H., Wang, W., & Shang, Y. (2023). Outer space branch-reduction-bound algorithm for solving generalized affine multiplicative problems. Journal of computational and applied mathematics, 419, 114784. https://doi.org/10.1016/j.cam.2022.114784
  16. [16] Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the operations research society of america, 2(4), 393–410. https://doi.org/10.1287/opre.2.4.393
  17. [17] Markowitz, H. M., & Manne, A. S. (1957). On the solution of discrete programming problems. Econometrica: journal of the econometric society, 84–110. https://doi.org/10.2307/1907744
  18. [18] Gomory, R. E. (2009). Outline of an algorithm for integer solutions to linear programs and an algorithm for the mixed integer problem. 50 years of integer programming 1958-2008: from the early years to the state-of-the-art (pp. 77–103). Springer. https://doi.org/10.1007/978-3-540-68279-0_4
  19. [19] Gomory, R. E. (1960). All-integer programming algorithm. International Business Machines Corporation.
  20. [20] Charnes, A., & Cooper, W. W. (1962). Programming with linear fractional functionals. Naval research logistics quarterly, 9(3–4), 181–186. https://doi.org/10.1002/nav.3800090303
  21. [21] Young, R. D. (1965). A primal (all-integer) integer programming algorithm. J. res. nat. bur. standards.—1965, b, 69, 213–250. https://books.google.com/books
  22. [22] BnnoBRs, J. (1962). Partitioning procedures for solving mixed-variables programming problems. Numer. math, 4(1), 238–252. http://www.im-uff.mat.br/puc-rio/disciplinas/2006.1/soe/arquivos/benders-numerische-mathematik-1962.pdf
  23. [23] Harris, P. M. J. (1964). An algorithm for solving mixed integer linear programmes. Journal of the operational research society, 15(2), 117–132. https://doi.org/10.1057/jors.1964.24
  24. [24] Trotter Jr, L. E., & Shetty, C. M. (1974). An algorithm for the bounded variable integer programming problem. Journal of the acm (jacm), 21(3), 505–513. https://doi.org/10.1145/321832.321848
  25. [25] Granot, D., & Granot, F. (2011). On integer and mixed integer fractional. Studies in integer programming, 1, 221–231. https://books.google.com/books
  26. [26] Land, A. H., & Doig, A. G. (2009). An automatic method for solving discrete programming problems. In 50 years of integer programming 1958-2008: from the early years to the state-of-the-art (pp. 105–132). Springer. https://doi.org/10.1007/978-3-540-68279-0_5
  27. [27] Bertier, P., & Roy, B. (1965). Une procédure de résolution pour une classe de problèmes pouvant posséder un caractère combinatoire. Bulletin du centre international de calcul de rome.
  28. [28] Balas, E. (1968). A note on the branch-and-bound principle. Operations research, 16(2), 442–445. https://pubsonline.informs.org/doi/pdf/10.1287/opre.16.2.442
  29. [29] Mitten, L. G. (1970). Branch-and-bound methods: General formulation and properties. Operations research, 18(1), 24–34. https://doi.org/10.1287/opre.18.1.24
  30. [30] Guignard, M., & Spielberg, K. (1981). Logical reduction methods in zero-one programming—minimal preferred variables. Operations research, 29(1), 49–74. https://doi.org/10.1287/opre.29.1.49
  31. [31] Lenstra Jr, H. W. (1983). Integer programming with a fixed number of variables. Mathematics of operations research, 8(4), 538–548. https://doi.org/10.1287/moor.8.4.538
  32. [32] Hoffman, K. L., & Padberg, M. (1991). Improving LP-representations of zero-one linear programs for branch-and-cut. ORSA journal on computing, 3(2), 121–134. https://doi.org/10.1287/ijoc.3.2.121
  33. [33] Savelsbergh, M. W. P. (1994). Preprocessing and probing techniques for mixed integer programming problems. ORSA journal on computing, 6(4), 445–454. https://doi.org/10.1287/ijoc.6.4.445
  34. [34] Balas, E., Ceria, S., Cornuéjols, G., & Natraj, N. (1996). Gomory cuts revisited. Operations research letters, 19(1), 1–9. https://doi.org/10.1016/0167-6377(96)00007-7
  35. [35] Weismantel, R. (1997). On the 0/1 knapsack polytope. Mathematical programming, 77(3), 49–68. https://doi.org/10.1007/BF02614517
  36. [36] Kesavan, P., Allgor, R. J., Gatzke, E. P., & Barton, P. I. (2004). Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs. Mathematical programming, 100(3), 517–535. https://doi.org/10.1007/s10107-004-0503-1
  37. [37] Frangioni, A., & Gentile, C. (2006). Perspective cuts for a class of convex 0--1 mixed integer programs. Mathematical programming, 106(2), 225–236. https://doi.org/10.1007/s10107-005-0594-3
  38. [38] Vyve, M. Van, & Wolsey, L. A. (2006). Approximate extended formulations. Mathematical programming, 105(2), 501–522. https://doi.org/10.1007/s10107-005-0663-7
  39. [39] Lay, E. H., Jacobson, A. R., Holzworth, R. H., Rodger, C. J., & Dowden, R. L. (2007). Local time variation in land/ocean lightning flash density as measured by the World Wide Lightning Location Network. Journal of geophysical research: atmospheres, 112(D13). https://doi.org/10.1029/2006JD007944
  40. [40] Cadoux, T. J. (2008). The Roman carcer and its adjuncts. Greece & rome, 55(2), 202–221. https://doi.org/10.1017/S0017383508000533
  41. [41] Basu, A., Conforti, M., & Di Summa, M. (2015). A geometric approach to cut-generating functions. Mathematical programming, 151(1), 153–189. https://doi.org/10.1007/s10107-015-0890-5
  42. [42] Jansen, K., & Rohwedder, L. (2023). On integer programming, discrepancy, and convolution. Mathematics of operations research, 48(3), 1481–1495. https://doi.org/10.1287/moor.2022.1308
  43. [43] Hooker, J. N. (2024). Integer programming duality. Encyclopedia of optimization (pp. 1–13). Springer. https://doi.org/10.1007/978-0-387-74759-0_289
  44. [44] Goswami, K., Schmelcher, P., & Mukherjee, R. (2024). Integer programming using a single atom. Quantum science and technology, 9(4), 45016. https://iopscience.iop.org/article/10.1088/2058-9565/ad6735/pdf
  45. [45] Senapati, T., & Yager, R. R. (2020). Fermatean fuzzy sets. Journal of ambient intelligence and humanized computing, 11(2), 663–674. https://doi.org/10.1007/s12652-019-01377-0
  46. [46] Adhami, A. Y., & Rabbani, Q. (n.d.). A procedure for solving integer bilevel linear programming problems. International journal of innovative research in science, engineering and technology, 3(1), 8233- 8237. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=5ceb62d93dc3eb8a34fcdf78408caec3c667c951
  47. [47] Haseen, S., Sadia, S., Bari, A., & Ali, Q. M. (2014). Integer Programming: NAZ cut and AT cut. International journal of engineering science and technology, 6(4), 128-137. https://www.researchgate.net/profile/Sanam-Haseen/publication/281368220_Integer_Programming_NAZ_cut_and_A-T_cut/links/55e3f8b008aecb1a7cc9e059/Integer-Programming-NAZ-cut-and-A-T-cut.pdf
  48. [48] Theodorakatos, N. P., Babu, R., & Moschoudis, A. P. (2023). The branch-and-bound algorithm in optimizing mathematical programming models to achieve power grid observability. Axioms, 12(11), 1040. https://doi.org/10.3390/axioms12111040

Downloads

Published

2025-03-23

Issue

Vol. 2 No. 1 (2025): OPT

Section

Articles

How to Cite

Sadia, S. . (2025). Integer Programming Problems with Fermatean Fuzzy Parameters Using NAZ-Cut. Optimality, 2(1), 52-62. https://doi.org/10.22105/opt.v2i1.75

Similar Articles

11-18 of 18

You may also start an advanced similarity search for this article.