Research ArticleOpen AccessGoogle Scholar indexed
Complete Solutions to Mixed Integer Programming
School of Science, Information Technology and Engineering, University of Ballarat, Ballarat, Australia
- 1 School of Science, Information Technology and Engineering, University of Ballarat, Ballarat, Australia
American Journal of Computational Mathematics·Volume 03 (2013)·Pages 27–30·Published 30 September 2013·DOI10.4236/ajcm.2013.33B005
Copy link · social · email
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.
KeywordsDuality TheoryDouble WellGlobal OptimizationCanonical Dual TransformationCombinatorial OptimizationNP-hard Problems
- K. Aardal,” Capacited Facility Location: Separation Algorithms and Computational Experience,” Mathematical Programming, Vol. 81, No. 2, 1998, pp. 149-175. doi:10.1007/BF01581103
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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