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
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
, ,
x
RyR
where,
 
1/ 2,1/ 2,
TT
f
xxAxgxxBxbx
AB
a
d
,
c, w,
b are given vectors, d is a given scalar, and ,0
0.c
X
is a feasible space defined by
 
,|1,1 ,1,,
nn
ai

X
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
x
RyR


We choose the geometrically nonlinear operator


Λ
y
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-

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
f
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 {}
s
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

,

x
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
s
tstst st

ë
y two vectors
denotes the Hadamard product
for an,n
s
tR

. This shows that if


,,

 is a KKT point of the problem

d
P, and then


,
x
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
 





 






N. RUAN 29
 


 
 
2
2
2
2
1
2
4
1
2
.
T
T
cw
fx gxa
e
f
xcyyye
a
yyegx wy







 









ë
ë
From (13), we have
.yy e
a

ë (18)
Therefore,
 
2
21.
1
22
y
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,, ,
y
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

,
x
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

,
x
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

N. RUAN
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