Complete Solutions to Mixed Integer Programming

Ning Ruan

School of Science, Information Technology and Engineering, University of Ballarat, Ballarat, Australia.

DOI: 10.4236/ajcm.2013.33B005                

Abstract

This paper considers a new canonical duality theory for solving mixed integer quadratic programming problem. It shows that this well-known NP-hard problem can be converted into concave maximization dual problems without duality gap. And the dual problems can be solved, under certain conditions, by polynomial algorithms.

Keywords

Duality Theory; Double Well; Global Optimization; Canonical Dual Transformation; Combinatorial Optimization; NP-hard Problems

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	K. Aardal,” Capacited Facility Location: Separation Algorithms and Computational Experience,” Mathematical Programming, Vol. 81, No. 2, 1998, pp. 149-175. doi:10.1007/BF01581103
[2]	A. Atamt rk, “Flow Pack Facets of the Single Node Fixed-charge Flow Polytope,” Operations Research Letters, Vol. 29, No. 3, 2001, pp. 107-114. doi:10.1016/S0167-6377(01)00100-6
[3]	I. Barany, T. J. Van Roy and L. A. Wolsey, “Strong Formulations for Multi-item Capacitated Lot Sizing,” Management Science, Vol. 30, 1984, pp. 1255-1261.doi:10.1287/mnsc.30.10.1255
[4]	P. Belotti, J. Lee, L. Liberti, F. Margot and A. Waechter, “Branching and Bounds Tightening Techniques for Non-convex MINLP,” Optimization Methods & Software, Vol. 24, 2009, pp. 597-634. doi:10.1080/10556780903087124
[5]	B. Borchers and J. E. Mitchell, “An Improved Branch and Bound Algorithm for Mixed Integer Nonlinear Programs,” Computer & Operations Research, Vol. 21, No. 4, 1994, pp. 359-367. doi:10.1016/0305-0548(94)90024-8
[6]	M. A. Duran and I. E. Grossmann, “An Outer-approximation Algorithm for a Class of Mixed-integer Nonlinear Programs,” Mathematical Programming, Vol. 36, No. 3, 1986, pp. 307-339. doi:10.1007/BF02592064
[7]	R. Fletcher and S. Leyffer, “Solving Mixed Integer Nonlinear Programs by Outer Approximation,” Mathematical Programming, Vol. 66, No. 1, 1994, pp. 327-349. doi:10.1007/BF01581153
[8]	C. A. Floudas, I. G. Akrotirianakis, S. Caratzoulas, C. A. Meyer and J. Kallrath, “Global Optimization in the 21st Century: Advances and Challenges,” Computers & Chemical Engineering, Vol. 29, 2005, pp. 1185-1202. doi:10.1016/j.compchemeng.2005.02.006
[9]	D. Y. Gao, “Duality Principles in Nonconvex Systems: Theory, Methods and Applications,” Kluwer Academic Publishers, Dordrecht/ Boston/ London, 2000. doi:10.1007/978-1-4757-3176-7
[10]	D. Y. Gao and N. Ruan, “Solutions to Quadratic Minimization Problems with Box and Integer Constraints,” Journal of Global Optimization, Vol. 47, No. 3, 2010, pp. 463-484. doi:10.1007/s10898-009-9469-0
[11]	D. Y. Gao, N. Ruan and H. D. Sherali, “Solutions and Optimality Criteria for Nonconvex Constrained Global Optimization Problems with Connections between Canonical and Lagrangian Duality,” Journal of Global Optimization, Vol. 45, No. 3, 2009, pp. 473-497.doi:10.1007/s10898-009-9399-x
[12]	D. Y. Gao, N. Ruan and H. D. Sherali, “Canonical Dual Solutions to Fixed Cost Quadratic Programs”, In: A. Chin-chuluun, P.M. Pardalos, R. Enkhbat and L. Tseveendorj, Eds., Optimization and Optimal Control: Theory and Applications, Springer, Vol. 39, 2010, pp. 139-156. doi:10.1007/978-0-387-89496-6_7
[13]	F. Glover and H. D. Sherali, “Some Class of Valid Inequalities and Convex Hull Characterizations for Dynamic Fixed-charge Problems under Nested Condtraints,” Vol. 40, No. 1, 2005, pp. 215-234.
[14]	J. Kallrath, “Solving Planning and Design Problem in the Process Industry using Mixed-integer and Global Optimization,” Annals of Operations Research, Vol. 140, No. 1, 2005, pp. 335-373. doi:10.1007/s10479-005-3976-2
[15]	P. Kesavan, R. J. Allgor, E. P. Gatzke and P. I. Barton, “Outer Approximation Algorithms for Separable Nonconvex Mixed-integer Nonlinear Programs,” Mathematical Programming, Vol. 1000, No. 3, 2004, pp. 517-535.
[16]	P. Kesavan and P. I. Barton,” Generalized Branch-and-cut Framework for Mixed-integer Nonlinear Optimization Problems,” Computers & Chemical Engineering, Vol. 24, 2000, pp. 1361-1366. doi:10.1016/S0098-1354(00)00421-X
[17]	L. Grippo and S. Lucidi, “A Differentiable Exact Penalty Function for Bound Constrained Quadratic Programming Problems,” Optimization, Vol. 22, No. 4, 1991, pp. 557-578. doi:10.1080/02331939108843700
[18]	Z. Gu, G. L. Nem-hauser and M. W. P. Savelsbergh, “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs,” Math Program, Vol. 85, No. 3, 1999, pp. 439-467. doi:10.1007/s101070050067
[19]	O. K. Gupta and A. Ravindran, “Branch and Bound Experiments in Convex Nonlinear Integer Programming,” Management Science, 1985, pp. 1533-1546.doi:10.1287/mnsc.31.12.1533
[20]	P. Hansen, B. Jaumard, M. Ruiz and J. Xiong, “Global Minimization of Indefinite Quadratic Functions Subject to Box Constraints,” Naval Research Logistics, Vol. 40, 1993, pp. 373-392.doi:10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A
[21]	S. Leyffer, “Integrating SQP and Branch-and-bound for Mixed Integer Nonlinear Programming,” Computational Optimization and Applications, Vol. 18, No. 3, 2001, pp. 295-309. doi:10.1023/A:1011241421041
[22]	X. Lin, C. A. Floudas and J. Kallarth, ”Global Solution Approach for a Non-convex MINLP Problem in Product Portfolio Optimization.,” Journal of Global Optimization, Vol. 32, No. 3, 2005, pp. 417-431.doi:10.1007/s10898-004-5903-5
[23]	M. W. Padberg, T. J. Van Roy and L. A. Wolsey, “Valid Linear Inequalities for Fixed Charge Problems,” Operations Research, Vol. 33, 1985, pp. 842-861.doi:10.1287/opre.33.4.842
[24]	I. Quesada and I. E. Grossmann, “An IP/NLP based Branch and Bound Algorithm for Convex NINLP Optimization Problems,” Computers & Chemical Engineering, Vol. 16, 1992, pp. 937-947. doi:10.1016/0098-1354(92)80028-8