On a New Constraint Reduction Heuristic Using Improved Bisection Method for Mixed Integer Linear Programming

Article Sidebar

PDF
Cite as:
Hande Günay Akdemir, On a New Constraint Reduction Heuristic Using Improved Bisection Method for Mixed Integer Linear Programming, Int. J. Anal. Appl., 19 (1) (2021), 65-76.

Main Article Content

Hande Günay Akdemir

Abstract

In this study, we develop a surrogate relaxation-based procedure to reduce mixed-integer linear programming (MILP) problem sizes. This technique starts with one surrogate constraint which is a nonnegative linear combination of multiple constraints of the problem. At this initial step, we calculate optimal Lagrangian multipliers from LP relaxation of the problem and use them as initial surrogate multipliers. We incorporate the improved bisection method (IBM) (B. Gavish, F. Glover, and H. Pirkul, Surrogate Constraints in Integer Programming, J. Inform. Optim. Sci. 12(2) (1991), 219-228.) into our algorithm. This simple heuristic algorithm is designed to iteratively generate a new surrogate cut that is to guarantee to satisfy the most violated two constraints of the corresponding iteration. The performance of the heuristic is tested using both some problems from the OR libraries and randomly generated ones.

Article Details

References

  1. J.H. Ablanedo-Rosas and C. Rego, Surrogate Constraint Normalization for the Set Covering Problem, Eur. J. Oper. Res. 205(3) (2010), 540-551.
  2. B. Alidaee, V.P. Ramalingam, H. Wang, and B. Kethley, Computational Experiment of Critical Event Tabu Search for the General Integer Multidimensional Knapsack Problem, Ann. Oper. Res. 269(1-2) (2018), 3-19.
  3. S. Balev, N. Yanev, A. Fr ´eville, and R. Andonov, A Dynamic Programming based Reduction Procedure for the Multidimensional 0””1 Knapsack Problem, Eur. J. Oper. Res. 186(1) (2008), 63-76.
  4. J. E. Beasley, OR-Library: Distributing Test Problems by Electronic Mail, J. Oper. Res. Soc. 41(11) (1990), 1069-1072.
  5. V. Boyer, M. Elkihel, and D. El Baz, Heuristics for the 0-1 Multidimensional Knapsack Problem, Eur. J. Oper. Res. 199(3) (2009), 658-664.
  6. M. Chih, Three Pseudo-utility Ratio-inspired Particle Swarm Optimization with Local Search for Multidimensional Knapsack Problem, Swarm. Evol. Comput. 39 (2018), 279-296.
  7. J. Choi and I.C. Choi, Identifying Redundancy in Multi-dimensional Knapsack Constraints based on Surrogate Constraints, Int. J. Comput. Math. 91(12) (2014), 2470-2482.
  8. C. D'Ambrosio, S. Martello, and L. Mencarelli, Relaxations and Heuristics for the Multiple Non-linear Separable Knapsack Problem, Comput. Oper. Res. 93 (2018), 79-89.
  9. S.M. Douiri, M.B.O. Medeni, S. Elbernoussi, and E.M. Souidi, A New Steganographic Method for Grayscale Image using Graph Coloring Problem, Appl. Math. Inform. Sci. 7(2) (2013), 521-527.
  10. A. Freville, The Multidimensional 0-1 Knapsack Problem: An Overview, Eur. J. Oper. Res. 155(1) (2004), 1-21.
  11. R.D. Galvao, L.G.A. Espejo, and B. Boffey, A Comparison of Lagrangean and Surrogate Relaxations for the Maximal Covering Location Problem, Eur. J. Oper. Res. 124(2) (2000), 377-389.
  12. B. Gavish, F. Glover, and H. Pirkul, Surrogate Constraints in Integer Programming, J. Inform. Optim. Sci. 12(2) (1991), 219-228.
  13. B. Gavish and H. Pirkul, Efficient Algorithms for Solving Multiconstraint Zero-one Knapsack Problems to Optimality, Math. Program. 31(1) (1985), 78-105.
  14. F. Glover, Surrogate Constraint Duality in Mathematical Programming, Oper. Res. 23(3) (1975), 434-451.
  15. F. Glover, Heuristics for Integer Programming using Surrogate Constraints, Decision Sci. 8(1) (1977), 156-166.
  16. F. Glover, Tutorial on Surrogate Constraint Approaches for Optimization in Graphs, J. Heuristics. 9(3) (2003), 175-227.
  17. H.J. Greenberg and W.P. Pierskalla, Surrogate Mathematical Programming, Oper. Res. 18 (1970), 924-939.
  18. B. Haddar, M. Khemakhem, S. Hanafi, and C. Wilbaut, A Hybrid Quantum Particle Swarm Optimization for the Multidimensional Knapsack Problem, Eng. Appl. Artif. Intel. 55 (2016), 1-13.
  19. S. Hanafi and F. Glover, Exploiting Nested Inequalities and Surrogate Constraints, Eur. J. Oper. Res. 179(1) (2007), 50-63.
  20. S. Hanafi and C. Wilbaut, Improved Convergent Heuristics for the 0-1 Multidimensional Knapsack Problem, Ann. Oper. Res. 183(1) (2011), 125-142.
  21. R.R. Hill, Y. K. Cho, and J. T. Moore, Problem Reduction Heuristic for the 0-1 Multidimensional Knapsack Problem, Comput. Oper. Res. 39(1) (2012), 19-26.
  22. S. Karabati, P. Kouvelis, and G. Yu, A Min-max-sum Resource Allocation Problem and its Aapplications, Oper. Res. 49(6) (2001), 913-922.
  23. T. Koch, T. Achterberg, E. Andersen, et al., MIPLIB 2010, Math. Program. Comput. 3 (2) (2011), 103-163.
  24. X. Kong, L. Gao, H. Ouyang, and S. Li, Solving Large-scale Multidimensional Knapsack Problems with a New Binary Harmony Search Algorithm, Comput. Oper. Res. 63 (2015), 7-22.
  25. S. Laabadi, M. Naimi, H. El Amri, and B. Achchab, The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches, Amer. J. Oper. Res. 8(05) (2018), 395-439.
  26. M. Lama and D. Pinto, A Preprocessing that Combines Heuristic and Surrogate Constraint Analysis to Fix Variables in TSP, In Mex Int. Conf. Artif. I. (727-734). Springer, Berlin, Heidelberg, 2004, April.
  27. V.C. Li and G.L. Curry, Solving Multidimensional Knapsack Problems with Generalized Upper Bound Constraints using Critical Event Tabu Search, Comput. Oper. Res. 32(4) (2005), 825-848.
  28. Y. Li, O. Ergun, and G.L. Nemhauser, A Dual Heuristic for Mixed Integer Programming, Oper. Res. Lett. 43(4) (2015), 411-417.
  29. C.J. Lin, M.S. Chern, and M. Chih, A Binary Particle Swarm Optimization based on the Surrogate Information with Proportional Acceleration Coefficients for the 0-1 Multidimensional Knapsack Problem, J. Ind. Product. Eng. 33(2) (2016), 77-102.
  30. A. Lokketangen, and F. Glover, Surrogate Constraint Analysis-New Heuristics and Learning Schemes for Satisfiability Problems, In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 35 (1997), 537-572.
  31. L.A.N. Lorena and M.G. Narciso, Relaxation Heuristics for a Generalized Assignment Problem, Eur. J. Oper. Res. 91(3) (1996), 600-610.
  32. L.A.N. Lorena and M.G. Narciso, Using Logical Surrogate Information in Lagrangean Relaxation: An Application to Symmetric Traveling Salesman Problems, Eur. J. Oper. Res. 138(3) (2002), 473-483.
  33. S. Martello and M. Monaci, Algorithmic Approaches to the Multiple Knapsack Assignment Problem, Omega 90 (2020), Art. ID 102004.
  34. R. Marti, A., Corberan, and J. Peiro, Scatter Search, In Handbook of Heuristics, 1-24 (2016).
  35. T. Meng and Q.K. Pan, An Improved Fruit Fly Optimization Algorithm for Solving the Multidimensional Knapsack Problem, Appl. Soft Comput. 50 (2017), 79-93.
  36. F. Molina, M.O.D. Santos, F. Toledo, and S.A.D. Araujo, An Approach using Lagrangian/surrogate Relaxation for Lotsizing with Transportation Costs, Pesquisa Oper. 29(2) (2009), 269-288.
  37. A. Moumen, M. Bouye, and H. Sissaoui, New Secure Partial Encryption Method for Medical Images using Graph Coloring Problem, Nonlinear Dynam. 82(3) (2015), 1475-1482.
  38. A. Nagih and F. Soumis, Nodal Aggregation of Resource Constraints in a Shortest Path Problem, Eur. J. Oper. Res. 172(2) (2006), 500-514.
  39. M.G. Narciso and L.A.N. Lorena, Lagrangean/surrogate Relaxation for Generalized Assignment Problems, Eur. J. Oper. Res. 114(1) (1999), 165-177.
  40. S.M. Neiro and J.M. Pinto, Decomposition Techniques for the Long-range Production Planning of Oil Complexes, In Comput. Aided Chem. Eng. 18 (2004), 967-972.
  41. M.A. Osorio, F. Glover, and P. Hammer, Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions, Ann. Oper. Res. 117(1-4) (2002), 71-93.
  42. G.R. Raidl and J. Puchinger, Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization, In Hybrid Metaheuristics (31-62), Springer, Berlin, Heidelberg, 2008.
  43. J. Reese, Solution Methods for the p-median Problem: An Annotated Bibliography, NETWORKS. 48(3) (2006), 125-142.
  44. C. Rego, RAMP: A New Metaheuristic Framework for Combinatorial Optimizatio, In Metaheuristic Optimization via Memory and Evolution (441-460), Springer, Boston, MA, 2005.
  45. C. Rego, F. Mathew, and F. Glover, Ramp for the Capacitated Minimum Spanning Tree Problem, Ann. Oper. Res. 181(1) (2010), 661-681.
  46. G.M. Ribeiro and L.A.N. Lorena, Heuristics for Cartographic Label Placement Problems, Comput. Geosci. 32(6) (2006), 739-748.
  47. A. Sakallioglu, Surrogate Constraint Applications to Network Models in Operations Research, Master Thesis, Department of Mathematics, Giresun University, 2019.
  48. F. Taniguchi, T. Yamada, and S. Kataoka, Heuristic and Exact Algorithms for the Max-min Optimization of the Multiscenario Knapsack Problem, Comput. Oper. Res. 35(6) (2008), 2034-2048.
  49. J. Wang, T. Liu, K. Liu, B. Kim, J. Xie, Z. Han, Computation Offloading Over Fog and Cloud Using Multi-Dimensional Multiple Knapsack Problem, in: 2018 IEEE Global Communications Conference (GLOBECOM), IEEE, Abu Dhabi, United Arab Emirates, 2018: pp. 1-7.
  50. B. Zhang, Q.K. Pan, X.L. Zhang, and P.Y. Duan, An Effective Hybrid Harmony Search-based Algorithm for Solving Multidimensional Knapsack Problems, Appl. Soft. Comput. 29 (2015), 288-297.