American Journal of Oper ations Research, 2011, 1, 185-189
doi:10.4236/ajor.2011.13021 Published Online September 2011 (http://www.SciRP.org/journal/ajor)
An Exact Penalty Approach for
Mixed Integer Nonlinear Programming
Problems
Roohollah Aliakbari Shandiz, Nezam Mahdavi-Amiri
Faculty of Mathematical Sciences, Sharif Un iversity of Technology, Tehran, Iran
Received July 31, 2011; revised August 19, 2011; accepted September 15, 2011
Abstract
We propose an exact penalty approach for solving mixed integer nonlinear programming (MINLP) problems
by converting a general MINLP problem to a finite sequence of nonlinear programming (NLP) problems
with only continuous variables. We express conditions of exactness for MINLP problems and show how the
exact penalty approach can be extended to constrained problems.
Keywords: Mixed Integer Nonlinear Programming, Continuous Programming, Exact Penalty Method, Exact
Penalty Functions
1. Introduction
One way for relaxing the integer constraints on the vari-
ables of a problem is adding an appropriate penalty term
to the objective function to create a new problem with
only continuous variables. This approach was first intro-
duced by Ragavachari [1] to solve 0-1 linear program-
ming problems and was used by several researchers for
solving real nonlinear discrete programming problems
[2-5]. Recently, Murray and Ng [6] have extended this
approach for large scale 0-1 nonlinear programming
problems with linear constraints.
In [7], the exact penalty approach was extended to
nonlinear integer programming problems. In [3,8], sev-
eral penalty functions were presented and the exactness
of some of them were proved in [9]. Here, using ideas of
Lucidi [9] we introduce conditions for exactness of a
penalty function for mixed integer nonlinear program-
ming (MINLP) problems. Then, we extend the exact
penalty approach to constrained mixed integer nonlinear
programming problems.
Notation 1. Let denote the optimal value of prob-
lem .
(.)v
(.)
2. Penalty Method for Unconstrained
MINLP Problems
An unconstrained mixed integer nonlinear programming
problem is expressed as:
 
min ,
.., ,
fxy
UMINL P
s
txXyY
where, f is a real-valued continuous function on nm



, X
is a finite subset of in the form {0 , and Y is a
compact subset in .
n

m

,1}n

LP The continuous relaxation of can be ex-
pressed as:
UMIN
 

min ,
..0,1 ,.
n
fxy
R
s
tx yY
We construct the following problem by adding some
constraints to the relaxed problem :

R


 

=1
min ,
.. ==0
0,1 ,,
n
ii
i
n
fxy
UNLPs tqxqx
x
yY

where, the


ii
qx nonnegative continuous functions
as follows:
are
1,,.



0,0,1 ,
==
>0,0,1,
i
ii i
x
qxi n
x





 (1)
It is easy to see that


UMINL P

=1
=n
ii
iq x
 and

are
equivalent, because

is zero on points
UNL P

qx

R. ALIAKBARI SHANDIZ ET AL.
186
,,
n
in and is positive on points in
{0,1}n(0,1) .
n
i
q
,=1,i
,=1, ,i

,
Some appropriate definitions for the are:
  
1=1
ii ii
qqxx xn
 
2=1cos2π.
ii i
qqx x
Now, for every , let
>0r
 
,= ,
r
H
xyf xyrqx

and consider the following penalty problem for the
:

UNL P
 



min,=
.. 0,1
r
rn
,
, .
H
xy fqx
EN st x
xy r
y Y



UP
UP
Note that the problem r is a continuous ver-
sion of the problem .

UPEN

LPUMIN
Under certain assumptions, we show that for some fi-
nite value of penalty parameter r, problem is
equivalent to .

r
EN

UMINLP
For

, 0< <12

, define a punctured neighborhood
of in [0, as follows: {0,1} 1]



=0,1 ,1J

  .  (2)
Assumption 1. There exist >0

and >0

such that
i) for every
 
,n
n0,1,
x
yJY

 Y we have

,<,=1,,,
i
f
xy i
x

n
ii) each i is differentiable on q
J

and for each i
x
J

,
we have

>, <,
<, >1,
i
ii i
x
x i
x





== n
q
1,,.
q'
Note that if f has bounded derivatives, then it satisfies
Assumption 1(i), and as an example, (1) satisfies As-
sumption 1(ii).
The following theorem shows that we can find a solu-
tion of an unconstrained MINLP problem by solving a
finite sequence of NLP problems.
Theorem 1. Under Assumption 1, there exists a finite
0 such that for any 0 any solution of r>,rr


r
UPEN
also solves with

UMINLP


=
rvU
)

. vUPEN
(,
MINLP
Proof. For any feasible point
x
y for


UMINLP ,
we have
 
,= ,
r

= ,.
H
xyfxy rqxfxy
Since any feasible point for (UMINLP) is also feasible
for , the above relation implies:

UPE

r
N



.
r
vUMINLPvUPEN (3)
For any , let
>0r

,
rr

x
y be an optimal solution of


r
UPEN . Suppose that



,
rr
x
y is a convergent sub-
sequence of optimal solutions of


r
UPEN and


,
x
y


,1 is its limit. Note that since
 
,
rr

0
n
x
yY and


0,1 nY

is compact, at least one convergent subse-
quence exists.
Since r
x
x

, there exists an r such that for every
>rr , we have: <.
r
xx


 Therefore, (2) implies
that


0,1
r
i
x or r
i
x
J


.
Now, let


0=mrax ,r

 and suppose that 0.
If
>rr


0,1 ,
r
i
x then .
r
i
x
J

 Since f and i are dif-
ferentiable on
q
J

and the first-order necessary condi-
tions for problem


holds in subspace
r
UPEN
J

, then
we have

,=0,
rr
y
r
i
Hx
x


 
,,
rr
ii
qxy
xx

=0,
rr
fxy r

 
,=0.
rr r
ii
ii
fxyr qx
xx



Assumption 1(ii) implies:
 
,=> =.
rr r
ii
i
fxy rqx
x





This is clearly a contradiction to Assumption 1(i).
Therefore, for we have Thus,
0
>,rr

0,1 n
r
x.


,
rr
x
y is feasible for


and . Fur-
thermore,
UMINLP qx

r=0





=,
=,
=,
.
rr
rr
rr r
rr
vUPENHx y

f
xy rqx
fxy
vUMINLP


(4)
Relations (3) and (4) imply:





,= =
=,.
rr r
rr
r

f
xyvUMINLP vUPEN
Hxy
Therefore, for any

0
>,rr

,
rr
x
y is an optimal solu-
tion for both problems.
3. Exact Penalty Functions
The following penalty functions have been suggested [3,
9] for zero-one problems ():
01
i
x




3=41
iii i
qqxx x

,
  
1
2, ,
2
4= 1
21,>,
2
ii
ii
ii
xx
qqx
xx








R. ALIAKBARI SHANDIZ ET AL.
187
  

5=loglog1
loglog 1,
ii ii
qqxxx






  

6= 1
1,
p
p
ii ii
p
p
qqx xx 






 


 
  
7=1exp
1exp 11exp,
ii i
i
qqx x
x




 


8=1
q
q
ii ii
qqxxx1,


  
 

1
1
1
9=1exp
1exp 1
11exp ,
2
ii i
i
qqxx
x










 




where, ,>0p

, 0< <12

and . Penalty
functions were introduced in [9]. Here, to
have (1) satisfied, we add a fixed number to every func-
tion
0< <1q
(5)q
(5)(9). qq
(9) q
Also, two other penalty functions for zero-one prob-
lems can be defined as follows:
  
10=sinπ,
ii i
qqx x


 
11= 11,
iiii ii
qqxxxx x

 
where, >0

.
Note that any bounded MINLP problem can be refor-
mulated as a mixed zero-one programming problem by
using the following representation for the integer vari-
ables (see [7]):
 

=0
=2 ,0,1,=1,,
Mii
k
ikk
k
,
x
yyin

where, M is an upper integer bound for log i
x
. Thus, we
can use the penalty functions for all bounded integer
problems.
Also, note that direct use of penalty functions for
MINLP problems (not zero-one) is not suitable, because
due to the structure of the i (see (1)), the resulting
nonconvex optimization problem, in general, may have
many local minimizers (see [4]).
q
Now, we show that


r
UPEN with the penalty func-
tions are exact for
(3)(11)qq


UMINLP
1).q
. Note that
exactness of have already been proved in
[9]. Here, by using Theorem 1, we prove the exactness
corresponding to all of
(5)q(9)q
(3) (1q
Let us suppose that f satisfies Assumption 1 1). We
then need to show that Assumption 1 2) holds for every
one of(3 For) (11).qq=13,

we have

=0,13 23

,1J

. It is easy to show that for the
functions we have
(3) (11),qq
 
1
0,,>1 3> 0,
3
iiii
xqxq

 


and
 
2,1,<23<0.
3
iiii
xqxq

 


Therefore, Assumption 1(ii) is satisfied for (3)(11)qq

.
Thus, the penalty problem with any one of
the functions

.
r
UPEN

(3) (11)qq

is exact for .

LPUMIN
4. Extension to Constrained Problems
A constrained mixed integer nonlinear programming
problem is expressed as:




min ,
..,0,=1,,,
0,1 ,,
j
n
fxy
M
INLPs tgxyjl
xyY



where, Y is a compact subset in .
m

Let



=,0,1,0,= 1,,
n
j
SxyYgxy jl .
A penalty function for


M
INLP is defined as fol-
lows:
 

0, ,
,=
>0, ,.
x
yS
pxy
x
yS






A typical penalty function for the constraints
j
g
in


M
INLP is:
  
=1
,=max0,,
l
j
j
pxygxy


. (5)
Consider the penalty problem of

M
INLP as:






min, =,,
..0,1,,
n
H
xyf xypxy
PEN stxyY


 

and define the following continuous penalty problem for


M
INLP :







,
,
,= ,,
min
..0,1 ,.
r
r
n
H
xyf xypxy
rq x
PEN
stxy Y


 


To prove the exactness of for

,r
PEN



,
M
INLP
first we show that for some penalty function p,


PEN

is exact for


M
INLP . Note that exactness for some
penalty functions, such as absolute-value penalty func-
tion, for the nonlinear programming (NLP) problems or
nonlinear integer programming (NLIP) problems has
already been proved (see [10,11]), that is, it has been
shown that for a finite value of the penalty parameter, the
main problem and the corresponding penalty problem are
equivalent. Here, we prove exactness for the constrained

R. ALIAKBARI SHANDIZ ET AL.
188

MINLP problems.
Theorem 2. Consider

M
INLP and for every x,
define the following NLP pr oblem,



min ,
..,0,=1,,,
,
xj
fxy
NLPstgxyjl
yY



and its corresponding penalty problem,

 
min, =,,
.. .
x
H
xyf xypxy
PEN sty Y


 

Suppose that for any x feasible to

,

x
NLP there exists
a
x

such that for every >,
x

 problems


x
NLP
and

x
PEN are equivalent. Then, there exists a 0

such that for every 0 >,

 any solution of


PEN

also solves


M
INLP and


=NvM

(, )

NLPvPEI.
Proof. For any feasible point
x
y of


M
INLP ,
we have
  
,= ,,= ,.
H
xyf xypxyf xy


Since any feasible point for


M
INLP is also feasi-
ble for

PEN


, it follows from the above equality that



.v MINLPv PEN

 (6)
We know:




 


,0,1
,0,1
0,1
=,
min
=,
min
=,
min min
n
xy Y
n
xy Y
nyY
x
vPENH xy
,
,.
f
xy pxy
f
xy pxy









For any fixed x, define


=,0,=1,
xj
SyYgxy jl

,.
.
Consider the following two cases.
Case 1: . Consider the following problem:
x
S
 
,,
min
yY
f
xy pxy 

From the assumption of the theorem, there exists
x

such that for any >,
x

any solution of the above
problem is also a solution of the following problem,


min, .
yS
x
f
xy

Case 2: . From the definition of
=
x
S
x
S, for any
,
y
Y we have . Since Y is compact, then

,>0pxy

,= >0
min x
yYpxy

.
Let
f
be a lower bound of f on

0,1 ,
nY

and


=1.



 

,,>, ,
=1
x
xx
fxypxy fxypxy
fvMINLP



 .
,
This means that if >
x

then






,,fxy pxyP  >vMINL 1


>
. Thus, (6) implies
that if
x

, then minimum does not occur in this
case. Now, let

0,1
0=.
max n
x
x

 For any 0
>,

if


,
x
y

 is an optimal solution of

PEN


, then from
the previous implication we get that Case 2 does not oc-
cur. From Case 1, we have






 


0,1
0,1
,,=
=,
min min
=,.
min min
nyY
x
nyS
xx
fxypxy vPEN

,
f
xy pxy
fxy



 






Let
f
be an upper bound of f on Then

0,1 .
nY


,,.
f
xypxy f 
 


Since this relation holds for any 0
>

, we have


,=0
p
xy
 . Therefore,


,
x
y

 is feasible to


M
INLP .
Furthermore,









0,1
0,1 ,,,0
,=
=,
min min
=,
min
=.
nyS
xx
n
xyYgxy
j
fxy vPEN
fxy
f
xy
vMINLP




 
Thus,


,
x
y

 is an optimal solution for both


P
EN

and


M
INLP . 
Theorem 2 shows that if p is an exact penalty function
for an NLP problem, then it is also exact for the MINLP
problem. Thus, (5) is an exact penalty function for


M
INLP .
Now, we show that


,r
PEN

is exact for


M
INLP ,
that is, for finite penalty parameter values of r and

,


,r
PEN

and


M
INLP are equivalent.
Assumption 2. Assumption 1(i) holds for each ,
j
g
namely, for each


,
n,
x
yJY


 we have

,<,=1,,,=1,,
j
i
.
g
xyin jl
x


Theorem 3. Suppose that both Assumption 1 and As-
sumption hold and p is an exact penalty function for


M
INLP . Then, there exist 0 and 0 r

such that for
every and 00 r>r>,

any solution of


,r
PEN

also solves


M
INLP and

N vM

=.INLP
,r 
Proof. Since p is an exact penalty function for
vPE


M
INLP ,
there exists a 0

such that for each 0 >,

any solu-
tion for


,r
N

PE also solves

M
INLP and
x
vMINLP f   For any >,
x

we have
x


R. ALIAKBARI SHANDIZ ET AL.
189



=vPEN vMINLP


PEN.
Theorem 1 on implies that there exists an
0 such that for every , any solution of is
also a solution of

,r 
0
>rrr

,r
PEN


PEN

and



,r
vP =vPENEN


Therefore, for every 0 >

and 0 any solution of

also solves

>,rr


,r
PEN

M
INLP

MINLP and

,r
vPEN

=v. 
5. Summary
We proposed an exact penalty approach for solving
mixed integer nonlinear programming (MINLP) prob-
lems and showed how to convert a MINLP problem to a
finite sequence of NLP problems. We stated conditions
for exactness of a penalty function for MINLP problems
and showed how exact penalty functions for NLP prob-
lems could serve as exact penalty functions for MINLP
problems.
6. Acknowledgements
The second author thanks the support of Research Coun-
cil of Sharif University of Technology.
7. References
[1] M. Ragavachari, “On Connections between Zero-One
Integer Programming and Concave Programming under
Linear Constraints,” Operations Research, Vol. 17, No. 4,
1969, pp. 680-684. doi:10.1287/opre.17.4.680
[2] J. Cai and G. Thierauf, “Discrete Optimization of Struc-
tures Using an Improved Penalty Function Method,” En-
gineering Optimization, Vol. 21, No. 4, 1993, pp. 293-306.
doi:10.1080/03052159308940981
[3] J. F. Fu, R. G. Fenton and W. L. Cleghorn, “A Mixed
Integer-Discrete-Continuous Programming Method and
Its Application to Engineering Design Optimization,”
Engineering Optimization, Vol. 17, No. 4, 1991, pp. 263-
280. doi:10.1080/03052159108941075
[4] S. S. Rao, “Engineering Optimization: Theory and Prac-
tice,” 4th Edition, Wiley, Hoboken, 2009.
[5] D. K. Shin, Z. Gürdal and O. H. Griffin Jr., “A Penalty
Approach for Nonlinear Optimization with Discrete De-
sign Variables,” Engineering Optimization, Vol. 16, No.
1, 1990, pp. 29-42. doi:10.1080/03052159008941163
[6] W. Murray and K. M. Ng, “An Algorithm for Nonlinear
Optimization Problems with Binary Variables,” Compu-
tational Optimization and Applications, Vol. 47, No. 2,
2008, pp. 257-288. doi:10.1007/s10589-008-9218-1
[7] F. Giannessi and F. Niccolucci, “Connections between
Nonlinear and Integer Programming Problems,” Sympo-
sia Mathematica, Vol. 19, 1976, pp. 161-176.
[8] F. Rinaldi, “New Results on the Equivalence between
Zero-One Programming and Continuous Concave Pro-
gramming,” Optimation Letters, Vol. 3, No. 3, 2009, pp.
377-386. doi:10.1007/s11590-009-0117-x
[9] S. Lucidi and F. Rinaldi, “Exact Penalty Functions for
Nonlinear Integer Programming Problems,” Journal of
Optimization Theory and Applications, Vol. 145, No. 3,
2010, pp. 479-488.
doi:10.1007/s10957-010-9700-7
[10] D. Li and X. Sun, “Nonlinear Integer Programming,”
Springer, New York, 2006.
[11] D. G. Luenberger and Y. Ye, “Linear and Nonlinear Pro-
gramming,” 3rd Edition, Springer, New York, 2008.