Optimasi Penjadwalan Produksi Multi-Mesin Menggunakan Model Integer Programming pada UKM Manufaktur
Abstract
Integer programming (IP) constitutes a fundamental framework in combinatorial optimization, extending linear programming by requiring decision variables to take integer values. This article presents a comprehensive narrative review of integer programming theory from the perspective of polyhedral analysis and cutting-plane methods. We examine the geometric relationship between the linear programming relaxation and the integer hull, the role of total unimodularity in guaranteeing integral extreme points, and the structural properties of valid inequalities that tighten this relaxation. The discussion covers the derivation of Chvátal-Gomory cuts, the geometry of branch-and-bound as a recursive partitioning of the feasible region, and Lagrangian relaxation as a dual bounding technique for integer programs, including the resulting integrality gap that distinguishes integer from linear duality. We further discuss recent developments connecting polyhedral theory with machine-learning-based cutting-plane selection. The findings show that polyhedral and geometric perspectives provide a coherent theoretical foundation for understanding why integer programs are computationally harder than their linear relaxations and how modern solvers exploit geometric structure to close the integrality gap. This review contributes to a deeper theoretical understanding of integer programming as a cornerstone of discrete optimization.
References
Andersen, K., Louveaux, Q., Weismantel, R., & Wolsey, L. A. (2007). Inequalities from two rows of a simplex tableau. In M. Fischetti & D. P. Williamson (Eds.), Integer Programming and Combinatorial Optimization (IPCO 2007), Lecture Notes in Computer Science (Vol. 4513, pp. 1–15). Springer. https://doi.org/10.1007/978-3-540-72792-7_1
Balas, E. (1971). Intersection cuts—A new type of cutting planes for integer programming. Operations Research, 19(1), 19–39. https://doi.org/10.1287/opre.19.1.19
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
Basu, A., Conforti, M., Di Summa, M., & Jiang, H. (2021). Complexity of branch-and-bound and cutting planes in mixed-integer optimization II. In K. Aardal & L. Sanità (Eds.), Integer Programming and Combinatorial Optimization (IPCO 2021), Lecture Notes in Computer Science (Vol. 12707, pp. 383–398). Springer. https://doi.org/10.1007/978-3-030-73879-2_27
Bertsekas, D. P. (2022). Convex optimization algorithms. Athena Scientific.
Bertsimas, D., & Weismantel, R. (2005). Optimization over integers. Dynamic Ideas.
Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). Integer programming. Springer.
Cornuéjols, G. (2008). Valid inequalities for mixed integer linear programs. Mathematical Programming, 112(1), 3–44. https://doi.org/10.1007/s10107-006-0086-0
Dey, S. S., & Molinaro, M. (2018). Theoretical challenges towards cutting-plane selection. Mathematical Programming, 170(1), 237–266. https://doi.org/10.1007/s10107-018-1302-4
Deza, A., & Khalil, E. B. (2023). Machine learning for cutting planes in integer programming: A survey. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23) (pp. 6592–6600). https://doi.org/10.24963/ijcai.2023/739
Geoffrion, A. M. (1974). Lagrangian relaxation for integer programming. Mathematical Programming Study, 2, 82–114. https://doi.org/10.1007/BFb0120690
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275–278. https://doi.org/10.1090/S0002-9904-1958-10224-4
Hillier, F. S., & Lieberman, G. J. (2021). Introduction to operations research (11th ed.). McGraw-Hill Education.
Huang, L., Chen, X., Huo, W., Wang, J., Zhang, F., Bai, B., & Shi, L. (2021). Branch and bound in mixed integer linear programming problems: A survey of techniques and trends. arXiv preprint arXiv:2111.06257.
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. Wiley.
Schrijver, A. (1998). Theory of linear and integer programming. Wiley.
Wolsey, L. A. (2020). Integer programming (2nd ed.). Wiley.
