Open Access Open Access  Restricted Access Subscription Access

Properties of Optimal Solution of Indefinite Matrix Constraint in Linear Programming

M. L. Sam, A. Saptari, M. R. Salleh, K. E. Chong


This study investigated characteristics of indefinite random square matrices which represented the constraints of Linear programming problems. MATLAB simulation was used to generate different size of indefinite random non-symmetric square matrices. Solutions of primal problem and dual problem were deliberated and discussed. Based on simulation results, duality gap found in some of the indefinite non-symmetric matrices and those matrices could not obtain optimal solution whereas some ID matrices that fulfill certain conditions could achieve optimal solution and no duality gap is found. An indefinite non-symmetric matrix with all positive off-diagonal entries and alternate signs of determinant of leading principal minors surely confirmed the existence of optimal solution in linear programming problems.

Full Text:



S. H. P. Moghadam, H. Mina, S. H. Iranmanesh, and A. Keyvandarian, “A new mathematical model for single machine scheduling with learning

effect: continuous approach,“ Int. J. of Mathematics in Operational Research, Vol. 7, No. 3, pp. 348 -360, 2015.

W. X. Xing, S. C. Fang, R. L. Sheu, and Z. T. Wang, “A canonical dual approach for solving linearly constrained quadratic programs,” European Journal of Operational Research, Vol. 218, pp. 21-27, 2012.

R. J. Vanderbei, Linear Programming: Foundations and Extensions, 2nd Edition. Dordrecht, London: Kluwer Academic, 2001.

M. S. Bazarra, and J. J. Jarvis, Linear Programming and Network Flows. Canada: John Wiley and Sons, 1977.

L. A. Wolsey, Integer Programming. USA: John Wiley & Sons, 1998.

S. Y. Leu, and J. S, Li, “Shakedown analysis of framed structures: strong duality and primal-dual analysis,” Procedia Engineering, Vol. 79, pp. 204-211, 2014.

V. Jeyakumar, and G. Y. Li, “New dual constraint qualifications

characterizing zero duality gaps of convex programs and semidefinite

programs,” Nonlinear Analysis: Theory, Methods & Applications, Vol. 71, No. 12, pp. e2239-e2249, 2009.

S. L. Wu, and C. X. Li, “A splitting method for complex symmetric

indefinite linear system,” Mathematics, Vol. 313, pp. 343-354, March 2017.

A. Basu, K. Martin, and C. T. Ryan, “On the sufficiency of finite support duals in semi-infinite linear programming,” Operations Research Letters, Vol. 42, issue 1, pp. 16-20, January 2014.

E.J. Lee, and J. Zhang, “A two-phase preconditioning strategy of a sparse approximate inverse for indefinite matrices,” Computers & Mathematics

with Applications, Vol. 58, issue 6, pp. 1152-1159, September 2009.

W. W. Xu, “On eigenvalue bounds of two classes of two-by-two block indefinite matrices,” Applied Mathematics and Computation, Vol. 219, issue 12, pp. 6669-6679, Feb. 2013.

I. Romli, Taufik, A. Saptari, and M. M. Jusoh, “Symmetric matrices

properties to duality in linear programming problem,” 2011 Fourth

International Conference on Modeling, Simulation and Applied Optimization, Kuala Lumpur, Malaysia, 2011, pp. 1-7.

P. Q. Pan, “A revised dual projective pivot algorithm for linear

programming,” SIAM Journal Optimization, Vol. 16, No. 1, pp. 49-68, 2005.

D. Torres, J. Crichigno, G. Padilla, and R. Rivera, “Scheduling coupled photovoltaic, battery and conventional energy sources to maximize profit using linear programming,” Renewable Energy, Vol. 72, pp. 284-290, 2014.

G. Strang, Linear Algebra and Its Application, 4th edition. United States of America: Thomson Learning, 2006.

O. Guler, Foundations of Optimization. New York: Springer, 2010.

M. Carter, Foundations of Mathematical Economics. Cambridge, United States of America: Massachusetts Institute of Technology, 2001.

A. L. Soyster, and F. H. Murphy, “A unifying framework for duality and modelling in robust linear programs,” Omega, Vol. 41, pp. 984-997, 2013.

A. Jeffrey, Matrix Operations for Engineers and Scientists. United Kingdom: Springer, 2010.

K. Mehlhorn, and S. Saxena, “A still simpler way of introducing interiorpoint method for linear programming,” Computer Science Review, Vol. 22, pp. I-II, 2016.

© Journal of Advanced Manufacturing Technology