American Journal of Computational Mathematics, 2013, 3, 27-30 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 well-known NP-hard 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; NP-hard 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 (semi-supervised 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 non-convex 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 ll-developed 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. 149-175. doi:10.1007/BF01581103 [2] A. Atamtrk, “Flow Pack Facets of the Single Node Fixed-charge Flow Polytope,” ters, Vol. 29, N doi:10.1016/S0 Operations Research Let- . o. 3, 2001, pp. 107-114 167-6377(01)00100-6 [3] I. Barany, T. J. Van Roy and L. A. Wolsey, “Strong For- mulations for Multi-item Capacitated Lot Sizing,” Man- agement Science, Vol. 30, 1984, pp. 1255-1261. 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 Non-convex MINLP,” Optimization Methods 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 Pro- ons Vol. 21, No. grams,” Computer & OperatiResearch, 4, 1994, pp. 359-367. doi:10.1016/0305-0548(94)90024-8 [6] M. A. Duran and I. E. Grossmann, “An Out- er-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 Non- linear 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 & 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. 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 Minimi- zation 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 Ca- nonical and Lagrangian Duality,” Journal of Global Op- timization, 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. Chinchuluun, P.M. Pardalos, R. Enkhbat and L. Tsev- eendorj, 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 Ine- qualities and Convex Hull Characterizations for Dy ested Condtraints,” Vol. namic Fixed-charge Problems under N 40, No. 1, 2005, pp. 215-234. [14] J. Kallrath, “Solving Planning and Design Problem in the Process Industry using Mixed-integer and Global Opti- mization,” 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, eneralized Branch-and-cut “Outer Approximation Algorithms for Separable Non- convex Mixed-integer Nonlinear Programs,” Mathemati- cal Programming, Vol. 1000, No. 3, 2004, pp. 517-535. [16] P. Kesavan and P. I. Barton,” G 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 . P. Savelsbergh, [18] Z. Gu, G. L. Nemhauser and M. W “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 Ex- periments 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-NAV32 20400307>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 X. Lin, C. A. Floudas and J.[22] 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,” Opera- tions 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 En 2, pp. 937-947 . gineering, Vol. 16, 199 doi:10.1016/0098-1354(92)80028-8
|