A pivoting algorithm for linear programming with linear complementarity constraints

Authors
Khatere Ghorbani-Moghadam 1
Reza Ghanbari 2
Javad Mohammadnia 2
1 Mosaheb Institute of Mathematics, Kharazmi University, Tehran, Iran
2 Ferdowsi University of Mashhad
Abstract
Linear programming problems with complementary linear constraints (LPCC) are widely studied in operations research and are known to be NP-hard. This paper explores a specific case of LPCC where the product of two variables must be zero, i.e., xp xm=0. This scenario frequently arises in optimization problems, particularly those involving absolute values that cannot be expressed as linear or integer programming problems. To tackle this, we will present a branch-and-bound algorithm, and we will implement the algorithm on numerical examples and compare its performance with existing methods.
Keywords
Linear Programming Problems
Linear‎ Complementarity Constraints
Zero-one constraint
Branch and Bound Algorithm
1. C. Chen, H. Yang, X. Li L. Chen and M. Shi, Optimization of solar and heat pump complementary powered desiccant air conditioning system, Journal of Building Engineering, 87 (2024), https://doi.org/10.1016/j.jobe.2024.109084.

2. H. Fang, S. Leyffer, and T. Munson. A pivoting algorithm for linear programming with linear complementary constraint, Optimization Methods Software, 27 (2012) 89-114.

3. R. Fletcher, S. Leyffer, D. Ralph and S. Scholtes, Local convergence of SQP methods for mathematical programs with equilibrium constraints, SIAM Journal of Optimization, 17 (2006) 259-289.

4. Z. Guo, J. Wang, F. Dong and H. Xu, Multi-objective optimization of multi-energy complementary system based on cascade utilization of heat storage, Energy Conversion and Management, 299 (2024), https://doi.org/10.1016/j.enconman.2023.117864.

5. J. Hu, J. E. Mitchelly, J. S. Pangz and B. Yu. On Linear programs with Linear Complementary Constraints, Journal of Global Optimization, 53 (2012) 29-51.

6. J. Hu, J. E. Mitchell, J. S. Pang, K. P. Bennett, and G. Kunapuli, On the global solution of linear programs with linear complementary constraints, SIAM Journal on Optimization, 19 (2008) 445-471.

7. T. Ibaraki, Complementary programming, Operations Research, 19 (1971) 1523-1529.

8. Z. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, U. K. 1996.

9. H. Scheel and S. Scholtes, Mathematical program with complementarity constraints: Stationarity, optimality and sensitivity, Mathematics of Operations Research, 25 (2000) 1-22.

10. S. Leyffer, G. Lopez-Calva and J. Nocedal, Interior methods for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 17 (2006) 52-77.

11. S. Leyffer, T. Munson, A globally convergent filter method for MPECs, Mathematics and Computer Science Division, 2007.

12. S. Leyffer, Mathematical programs with complementarity, SIAG/OPT Views and News, 14 (2003) 15-18.

13. J. Hu, J. E. Mitchell, J. S. Pang, K. P. Bennet and G. Kunapuli, On the Global solution of linear programs with linear complementarity constraints, SIAM Journal on Optimization, 19 (2008) 445-471.

14. J. F. Bard and J. T. Moore, A branch and bound algorithm for the bi-level programming problem, SIAM Journal on Scientific Computing (1990) 281-292.

15. H. Onal, A Modified simplex approach for solving bi-level linear programming problems, European Journal of Operational Reseach, 67 (1993) 126-133.

16. J. Hu, J. E. Mitchelly, J. S. Pangz and B. Yu, On Linear Programs with Linear Complementarity Constraints, Journal of Global Optimization, 53 (2012) 29-51.