American Journal of Computational Mathematics, 2013, 3, 2730 doi:10.4236/ajcm.2013.33B005 Published Online September 2013 (http://www.scirp.org/journal/ajcm) Complete Solutions to Mixed Integer Programming Ning Ruan School of Science, Information Technology and Engineering, University of Ballarat, Ballarat, Australia Email: n.ruan@ballarat.edu.au Received April, 2013 ABSTRACT This paper considers a new canonical duality theory for solving mixed integer quadratic programming problem. It shows that this wellknown NPhard problem can be converted into concave maximization dual problems without dual ity 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; NPhard Problems 1. Introduction Mixed integer nonlinear programming refers to optimiza tion problems which involve continuous and discrete variables [8]. In this paper, we consider the following constrained mixed integer quadratic programming: 0 () min (,)() (1) T PPxyfxcy s.t. ()0, T gx wy 11y n , n , , RyR where, 1/ 2,1/ 2, TT xxAxgxxBxbx AB a d , c, w, b are given vectors, d is a given scalar, and ,0 0.c is a feasible space defined by ,1,1 ,1,, nn ai xRyRyi n (2) Problem of the form (1) has a broad spectrum of ap plications, including process industry (process design [2, 13, 18], production planning [14], supply chain optimiza tion [1,3], logistics and so on), management science (scheduling problem), financial (portfolio optimization problems [22]), engineering (network design [23]), ma chine learning (semisupervised support vector ma chines), and computational chemistry /biology (solvent design problems). Various methods have been proposed for solving mixed integer programming, such as branch and bound [4,5,19,21,24], cutting plane, branch and cut [16], branch and reduce, outer approximation [6,7,15], hybrid meth ods, and penalty method [17]. But the difficulty for de veloping an efficient method for such mixed integer pro gramming lies not only on the nonlinearity of the func tions involved, but also on existence of both discrete and continuous variables [20]. But if we introduce the ca nonical duality with some strategy, we can find global optima in polynomial time [10, 11, 12]. The rest of paper is arranged as follows. In section 2, we demonstrate how to rewrite the primal problem as a dual problem by using the canonical dual transformation. In section 3, optimality criterions for global solutions are discussed. Finally, in the last section, we present some conclusions. 2. Canonical Dual Transformation Canonical duality theory [9] is a potentially powerful methodology which can be used to solve a large class of nonconvex and discrete problems in nonlinear analysis, global optimization, and computational science. Since {1,1} n y , one penalty term is added. Let a be a penalty factor, the original problem can be formulated 2 1 min ,2 s.t. gx0 0 T T PPxyfxcyayye wy yy e ë ë ,. nn RyR We choose the geometrically nonlinear operator Λ yy ë then, the canonical function associated with this geomet rical operator is 2 1. 2 Vae Let n R be the canonical dual variable corre Copyright © 2013 SciRes. AJCM
N. RUAN 28 sponding to , we have ()Va ,e And the Legendre conjugates of the function V defined by *1 1 :. 2 TT VVVa Thus the total complementarily function can be de fined by Ξ,,,, 0. yT T xy xcV yye gx wy ë By the criticality condition Ξ,,,, 0, yxy We obtain () 2( ) cw y Therefore, the canonical dual problem can be proposed as the following: max,, s.t.,, dd a PP S (3) and 1 2 2 2 ,, 1 2 11 , 42 d T P bA Bb d cw e a 0} (4) where e is a vector with all its entry 1. Its dual feasible space is defined as 10,a a S {,,0, nn a SRRR . (5) The notation {} ta ,, stands for finding all stationary points of d P over . The following theorem shows that is canonically (i.e., with zero duality gap) dual to the primal problem a S d P .P 3. Global Optimality Condition Theorem 1The problem is canonical dual to the primal problem in the sense that if d P P ,, is a KKT point of , then d P , y defined by 1 (), 2 cw xABby (6) is a KKT point of , and P ,(,, d Pxy P) (7) Proof. By introducing a Lagrange multiplier ,:0, nnnn RRRR :nn a LS RRR the Lagrangian associatedthe with problem d P is ,,, . dT P,,, T L The criticality conditions ,, 0, ,,,, 0, ,,,, 0 L L ,,L lead to ,ayy e ë (8) ,, ,yv d Py ë (9) ,, , d Pv vv ë and the KKT conditions (10) 00, (11) 00, (12) 1 1/ 2Diag(/ 2),w the notation yc where 112 2 :(,, ,) nn tstst st ë y two vectors denotes the Hadamard product for an,n tR . This shows that if ,, is a KKT point of the problem d P, and then , y is a KKT point omal problem f the pri .P ng the equations (6) we have By usi 2 2 dcw P , 4e a (13) 2 2 ()0, 4( ) dc P (14) 0, 2 dcww P (15) and 0, () T yye gx wy ë 0. (16) So, in terms of 1, , 2 cw BbyxA (17) we have 2 2 2 11 ,, 22 1 2 4 d PTTT xAxxBxxbd cw e a Copyright © 2013 SciRes. AJCM
N. RUAN 29 2 2 2 2 1 2 4 1 2 . T T cw fx gxa e xcyyye a yyegx wy ë ë From (13), we have .yy e a ë (18) Therefore, 2 21. 1 22 y 腚eayye a (19) Due to the fact that global maximize of ,, d P ovides a su o g the canonic lldeveloped d REFERE cility al E over proves the statement (23). This theorem prfficientn for a ble 4. Conclusions as bee dual problem eetermtic optimiza NCES Locaration Al xperien Mathematical , a S conditio h pr tra e inis tion: Sepa ce,” 1, 1, i1,, , i n we have ,,,. d PP xy (20) This proves the theorem. This theorem shows that there is no duality ga twem and its canonical d tominimize, we need to useful feasible space (21) p be een the primal problual. In order identify the global introduce a {,, a S  0} k S be a subset of a S, and we have the following theorem. Theorem 2 Suppose that the vector ,, is a critical point of the canonical dual function ,, d P . Let 1( (), cw xABby ) 2 (22) If ,, , a S then ,, is a gaxi mize of ,, d Plobal m on ,Sa the vector , y is al m, and a globinimize of y on,Px n R ,, ma, , ,, a d S d P P ,, ,, , minmin, xmax nn nn a xy RRxyRR S Pxy Px y (23) Proof. By Theorem 1 and the canonical duality theory, we know that vector ,, a S is a KKT po the problem if and only if int of () d P , y defined by 1, 2 cw xABby is a critical point of the, and problem P ,P,, d xy P By the fact that the canonical dual function ,, d P this global minimizer of the primal prm. In this paper, the canonical duality theoryn ap plied to solve mixed integer prorammingoblem. The orems show that by al dualnsformation, primal problems can be converted into canonical dual problem. By the fact that the canonical dual function is concave on the dual feasible space, so th can be solved by w tion methods. 5. Acknowledgements Dr. Ning Ruan was supported by a funding from the Australian Government under the Collaborative Research Networks (CRN) program. [1] K. Aardal,” Capacited Fa gorithms and Computation Programming, Vol. 81, No. 2, 1998, pp. 149175. doi:10.1007/BF01581103 [2] A. Atamtrk, “Flow Pack Facets of the Single Node Fixedcharge Flow Polytope,” ters, Vol. 29, N doi:10.1016/S0 Operations Research Let . o. 3, 2001, pp. 107114 1676377(01)001006 [3] I. Barany, T. J. Van Roy and L. A. Wolsey, “Strong For mulations for Multiitem Capacitated Lot Sizing,” Man agement Science, Vol. 30, 1984, pp. 12551261. d5oi:10.1287/mnsc.30.10.125 & Software, [4] P. Belotti, J. Lee, L. Liberti, F. Margot and A. Waechter, “Branching and Bounds Tightening Techniques for Nonconvex MINLP,” Optimization Methods Vol. 24, 2009, pp. 597634. doi:10.1080/10556780903087124 [5] B. Borchers and J. E. Mitchell, “An Improved Branch and Bound Algorithm for Mixed Integer Nonlinear Pro ons Vol. 21, No. grams,” Computer & OperatiResearch, 4, 1994, pp. 359367. doi:10.1016/03050548(94)900248 [6] M. A. Duran and I. E. Grossmann, “An Out erapproximation Algorithm for a Class of Mixedinteger Nonlinear Programs,” Mathematical Programming, Vol. 36, No. 3, 1986, pp. 307339. doi:10.1007/BF02592064 [7] R. Fletcher and S. Leyffer, “Solving Mixed Integer Non linear Programs by Outer Approximation,” Mathematical Programming, Vol. 66, No. 1, 1994, pp. 327349. 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 & is concave on the critical point , a S ,, is a Copyright © 2013 SciRes. AJCM
N. RUAN Copyright © 2013 SciRes. AJCM 30 Chemical Engineering, Vol. 29, 2005, pp. 11851202. 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/9781475731767 [10] D. Y. Gao and N. Ruan, “Solutions to Quadratic Minimi zation Problems with Box and Integer Constraints,” Journal of Global Optimization, Vol. 47, No. 3, 2010, pp. 463484. doi:10.1007/s1089800994690 [11] D. Y. Gao, N. Ruan and H. D. Sherali, “Solutions and . Optimality Criteria for Nonconvex Constrained Global Optimization Problems with Connections between Ca nonical and Lagrangian Duality,” Journal of Global Op timization, Vol. 45, No. 3, 2009, pp. 473497 doi:10.1007/s108980099399x [12] D. Y. Gao, N. Ruan and H. D. Sherali, “Canonical Dual Solutions to Fixed Cost Quadratic Programs”, In: A. Chinchuluun, P.M. Pardalos, R. Enkhbat and L. Tsev eendorj, Eds., Optimization and Optimal Control: Theory and Applications, Springer, Vol. 39, 2010, pp. 139156. doi:10.1007/9780387894966_7 [13] F. Glover and H. D. Sherali, “Some Class of Valid Ine qualities and Convex Hull Characterizations for Dy ested Condtraints,” Vol. namic Fixedcharge Problems under N 40, No. 1, 2005, pp. 215234. [14] J. Kallrath, “Solving Planning and Design Problem in the Process Industry using Mixedinteger and Global Opti mization,” Annals of Operations Research, Vol. 140, No. 1, 2005, pp. 335373. doi:10.1007/s1047900539762 [15] P. Kesavan, R. J. Allgor, E. P. Gatzke and P. I. Barton, eneralized Branchandcut “Outer Approximation Algorithms for Separable Non convex Mixedinteger Nonlinear Programs,” Mathemati cal Programming, Vol. 1000, No. 3, 2004, pp. 517535. [16] P. Kesavan and P. I. Barton,” G Framework for Mixedinteger Nonlinear Optimization Problems,” Computers & Chemical Engineering, Vol. 24, 2000, pp. 13611366. doi:10.1016/S00981354(00)00421X [17] L. Grippo and S. Lucidi, “A Differentiable Exact Penalty Function for Bound Constrained Quadratic Programming Problems,” Optimization, Vol. 22, No. 4, 1991, pp. 557578. doi:10.1080/02331939108843700 . P. Savelsbergh, [18] Z. Gu, G. L. Nemhauser and M. W “Lifted Flow Cover Inequalities for Mixed 01 Integer Programs,” Math Program, Vol. 85, No. 3, 1999, pp. 439467. doi:10.1007/s101070050067 [19] O. K. Gupta and A. Ravindran, “Branch and Bound Ex periments in Convex Nonlinear Integer Programming,” Management Science, 1985, pp. 15331546. 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. 373392. doi:10.1002/15206750(199304)40:3<373::AIDNAV32 20400307>3.0.CO;2A [21] S. Leyffer, “Integrating SQP and Branchandbound for Mixed Integer Nonlinear Programming,” Computational Optimization and Applications, Vol. 18, No. 3, 2001, pp. 295309. doi:10.1023/A:1011241421041 X. Lin, C. A. Floudas and J.[22] Kallarth, ”Global Solution Approach for a Nonconvex MINLP Problem in Product Portfolio Optimization.,” Journal of Global Optimization, Vol. 32, No. 3, 2005, pp. 417431. doi:10.1007/s1089800459035 [23] M. W. Padberg, T. J. Van Roy and L. A. Wolsey, “Valid Linear Inequalities for Fixed Charge Problems,” Opera tions Research, Vol. 33, 1985, pp. 842861. 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 En 2, pp. 937947 . gineering, Vol. 16, 199 doi:10.1016/00981354(92)800288
