An Analytical Approach to Linear Program Bounding Through Advanced Constraint Propagation Techniques
Keywords:
Linear Programming, Constraint Propagation, Bound Tightening, OptimizationAbstract
Linear programming (LP) remains a foundational optimization framework across engineering, operations research, artificial intelligence, logistics, and decision sciences. Despite the maturity of LP methodologies, computational efficiency remains a critical challenge when solving large-scale optimization problems characterized by extensive variable domains and complex constraints. Constraint propagation has emerged as a powerful mechanism for reducing search spaces, tightening variable bounds, and improving solver performance before and during optimization. This research and review article presents an analytical framework for linear program bounding through advanced constraint propagation techniques. The study synthesizes developments in constraint programming, presolve reductions, feasibility-based bound tightening, interval reasoning, and integer bound propagation to construct a unified perspective on LP bounding mechanisms. The proposed analytical framework integrates theoretical foundations from constraint propagation with modern optimization preprocessing strategies to demonstrate how bound tightening enhances solution quality and computational tractability. Findings indicate that advanced propagation techniques significantly reduce feasible regions while preserving optimality, thereby improving solver convergence and reducing computational overhead. The article contributes a structured theoretical model that bridges constraint programming and mathematical optimization and identifies future directions for hybrid propagation-driven optimization systems.
Downloads
References
1. Achterberg, T. (2007). Constraint integer programming. Ph.D. thesis.
2. Achterberg, T., Bixby, R. E., Gu, Z., Rothberg, E., & Weninger, D. (2014). Multi-row presolve reductions in mixed integer programming. In Proceedings of the Twenty-Sixth RAMP Symposium, pp. 181–196.
3. Achterberg, T., Bixby, R. E., Gu, Z., Rothberg, E., & Weninger, D. (2020). Presolve reductions in mixed integer programming. INFORMS Journal on Computing, 32(2), 473–506.
4. Apt, K. R. (1999). The rough guide to constraint propagation. In Conference on Principles and Practice of Constraint Programming, pp. 1–23. Springer.
5. Bacchus, F., J̈arvisalo, M., & Martins, R. (2019). MaxSAT Evaluation 2018: New developments and detailed results. Journal on Satisfiability, Boolean Modeling and Computation, 11(1), 99–131.
6. Batra, D., Nowozin, S., & Kohli, P. (2011). Tighter relaxations for MAP-MRF inference: A local primal-dual gap based separation algorithm. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 146–154. JMLR Workshop and Conference Proceedings.
7. Beck, A. (2014). The 2-coordinate descent method for solving double-sided simplex constrained minimization problems. Journal of Optimization Theory and Applications, 162, 892–919.
8. Belotti, P. (2013). Bound reduction using pairs of linear inequalities. Journal of Global Optimization, 56, 787–819.
9. Belotti, P., Cafieri, S., Lee, J., Liberti, L., et al. (2010). Feasibility-based bounds tightening via fixed points. In COCOA (1), pp. 65–76.
10. Benhamou, F., & Granvilliers, L. (2006). Continuous and interval constraints. In Handbook of Constraint Programming, chap. 16. Elsevier.
11. Bertsekas, D. P. (1997). Nonlinear programming. Journal of the Operational Research Society, 48(3), 334–334.
12. Bessiere, C. (2006). Constraint propagation. In Handbook of Constraint Programming, chap. 3. Elsevier.
13. Biere, A., Heule, M., & van Maaren, H. (2009). Handbook of satisfiability, Vol. 185. IOS press.
14. Bordeaux, L., Katsirelos, G., Narodytska, N., & Vardi, M. Y. (2011). The complexity of integer bound propagation. Journal of Artificial Intelligence Research, 40, 657–676.
15. Boros, E., & Hammer, P. L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1–3), 155–225.
16. M. R. Marri, S. B. Kurada, S. Gupta, S. Dey, S. Kumar and R. Chauhan, "Graph-Based Deep Learning Model for Identifying Cyber Threats in Cloud Platforms," 2025 International Conference on Computational Intelligence, Security, and Artificial Intelligence (IntelliSecAI), Al-Khobar, Saudi Arabia, 2025, pp. 1-7, doi: 10.1109/IntelliSecAI66368.2025.11472831.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Chinedu Okafor, Amina Bello (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published by The Parthenon Frontiers and its associated journals are distributed under the terms of the Creative Commons Attribution (CC BY 4.0) International License unless otherwise stated.
Authors retain full copyright of their published work. By submitting their manuscript, authors agree to grant The Parthenon Frontiers a non-exclusive license to publish, archive, and distribute the article worldwide. Authors are free to:
-
Share their article on personal websites, institutional repositories, or social media platforms.
-
Reuse their content in future works, presentations, or educational materials, provided proper citation of the original publication.
