AN IMPROVED TEST SET APPROACH TO NONLINEAR
INTEGER PROBLEMS WITH APPLICATIONS TO
ENGINEERING DESIGN
J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ,
AND J.M. UCHA-ENR´
IQUEZ
Abs ac . Many p oblems in enginee ing design in ol e he use o nonlin-
ea i ies and some in ege a iables. Me hods based on es se s ha e been
p oposed o sol e some pa icula p oblems wi h in ege a iables, bu hey
ha e no been equen ly applied because o compu a ion cos s. The walk-back
p ocedu e based on a es se gi es an exac me hod o ob ain an op imal poin
o an in ege p og amming p oblem wi h linea and nonlinea cons ain s, bu
he calcula ion o his es se and he iden i ica ion o an op imal solu ion
using he es se di ec ions a e usually compu a ionally in ensi e.
In p oblems o which ob aining he es se is easonably as , we show
how he e ec i eness can s ill be subs an ially imp o ed. This me hodology
is p esen ed in i s ull gene ali y and illus a ed on wo speci ic p oblems: (1)
minimizing cos in he p oblem o scheduling jobs on pa allel machines gi en
es ic ions on demands and capaci y, and (2) minimizing cos in he se ies
pa allel edundancy alloca ion p oblem, gi en a a ge eliabili y. Ou com-
pu a ional esul s a e p omising and sugges he applicabili y o his app oach
o deal wi h o he p oblems wi h simila cha ac e is ics o o combine i wi h
mains eam sol e s o ce i y op imali y.
Non-linea In ege P og amming and es se and G ¨obne basis and chance
cons ained p og amming
1. In oduc ion
The e e -inc easing demand on ope a ions esea che s o lowe p oduc ion cos s
o o inc ease bene i s has p omp ed he specialized communi y o look o igo ous
me hods o decision making, such as op imiza ion me hods, o design and p ocess
bo h economically and e icien ly mos enginee ing sys ems. Op imiza ion ech-
niques, ha ing eached a deg ee o ma u i y o e he las yea s, a e being used in a
wide spec um o enginee ing applica ions, including eliabili y o sys ems, inance,
scheduling, as well as a ious con ibu ions in ae ospace, au omo i e, chemical,
elec ical o manu ac u ing indus ies. Fo some o hose applica ions Ope a ions
Resea ch has de eloped e icien algo i hms, especially when he p oblems can be
modeled ei he as con inuous (linea o nonlinea ) p og ams o disc e e linea p o-
g ams. Howe e , in many occasions he esul ing models con ain bo h nonlinea i ies
and disc e e a iables which make hei esolu ion challenging.
The pu pose o his pape is o imp o e a gene al echnique o handle nonlin-
ea in ege p oblems and o show some applica ions o enginee ing op imiza ion
p oblems in a simple manne . This echnique combines h ee essen ial elemen s: 1)
i bo ows some ools om Compu a ional Algeb a which a e applied o gene a e
Da e: Recei ed: da e / Accep ed: da e.
1
2J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ, AND J.M. UCHA-ENR´
IQUEZ
es se s o linea in ege p og ams, 2) i uses elaxed p oblems o ob ain seeds o
a dual sea ch p ocedu e, and 3) i de ines an o de on he sea ch ee o easible
solu ions ha uses he classical idea o a penal y s a egy ha should ake in o
accoun bo h he objec i e unc ion alue and he dis ance o he easible egion.
This hi d ing edien is speci ically he new one ha makes he gene al dual sea ch
(o walk-back p ocedu e) much mo e e icien in he expe imen s.
The gene al heo y o penal y unc ions usually conside s he ans o ma ion
o a cons ained p oblem in o uncons ained one(s) and a e wa d, s a ing om
some con enien seed, uses sui able di ec ions in o de o each an op imum. Ou
app oach is a na u al gene aliza ion in his con ex : once he op imum o a elaxed
in ege linea p oblem o he o iginal p oblem is eached, he p ocess s a s om
his op imum and chooses he mos p omising nodes balancing he cos and he
dis ance o he whole easible egion. The main ad ance o ou algo i hm wi h
espec o he one desc ibed in [30] is he inse ion in he pending nodes lis by he
ascending penalized cos . We will see in Sec ion 4 he e ec i eness o his change
in some examples.
The me hod is desc ibed in i s ull gene ali y and hen i is es ed in wo enginee -
ing design p oblems aken om he li e a u e, namely, he minimiza ion o he cos
o scheduling jobs on pa allel machines gi en es ic ions on demands and capac-
i y and in he minimiza ion o he cos in he se ies pa allel edundancy alloca ion
p oblem gi en a a ge eliabili y. Fo he i s p oblem, wi h s ochas ic es ic ions,
i is ema kable ha ou me hod can manage he examples es ed whe eas o he
mains eam nonlinea sol e s canno deal wi h he nonlinea o mula ion. The e-
sul s ob ained in he second p oblem a e compe i i e wi h he nonlinea sol e s,
wi h a ema kable pe o mance in he ime needed o each he op imum.
The pape is o ganized as ollows. In Sec ion 2 he basics abou he walk-back
p ocedu e using a es se associa ed wi h an in ege linea p og am a e p esen ed.
Sec ion 3 con ains he main echnique ollowed o imp o e he pu e walk-back p o-
cedu e. In his sec ion i is also in oduced he penalized cos unc ion ha can
be employed o o de , in an e icien way, he easible poin s o he elaxed in e-
ge linea p oblem. Sec ion 4 is de o ed o he examples whe e he me hod has
been es ed. In all he examples ables wi h execu ion da a (CPU ime, numbe o
p ocessed nodes) and compa ison wi h p e ious wo ks ([30], [25], [17]) and o he
nonlinea in ege p og amming sol e s a e included. Addi ionally, we show how o
exploi a combined s a egy wi h o he sol e s o speed up ce i ica ion o op imal-
i y. Finally, Sec ion 5 con ains he conclusions.
2. P elimina ies
This sec ion con ains a b ie summa y o he concep s and algo i hms used o
sol e in ege linea p og amming p oblems om an algeb aic poin o iew. In
addi ion i is ecalled he walk back p ocedu e o nonlinea in ege p og amming
p oblems based on es se s. To his end, we ha e ollowed [28] and [30].
2.1. Tes se s. Conside an in ege linea p og amming p oblem:
(LP(b)) min c(x) = c ·x
s. . A·x=b,
x∈ZN
+,
AN IMPROVED TEST SET APPROACH TO NONLINEAR INTEGER PROBLEMS 3
whe e A∈Zd×N,b∈Zd,c∈RN. The no a ion (LP(b)) deno es he in ege linea
p og amming p oblem wi h igh -hand-side ixed o b. (LP) deno es he se o all
he in ege linea p og amming p oblems ob ained by a ying he igh -hand-side
ec o b, ixed Aand he cos unc ion c. Le πbe he map de ined by π(x) = Ax.
Gi en a ec o b∈Zd, he se π−1(b) = {u∈ZN
+:π(u) = b}is he ibe o (LP)
o e b.
Fixed a e m o de <c, associa ed wi h he cos , de ined as usual in [28], he e
exis s a unique op imum β o (LP(b)). A se G<c⊂ZNis a es se o he amily
o in ege linea p oblems (LP) wi h espec o he ma ix Aand he o de <ci
• o each nonop imal poin αo (LP(b)), he e exis s g∈G<csuch ha
α−gis a easible solu ion o (LP(b)) and α−g<cα,
• o he op imal poin β,β−gis no a easible poin o any g∈G<c.
In his way, a es se o (LP) connec s he ibe as a di ec ed g aph wi h a unique
sink. I gi es an ob ious algo i hm o sol e an in ege p og am, s a ing om a
easible solu ion o his p oblem. A e e y s ep o his algo i hm, we ha e wo
di e en cases:
•The e exis s an elemen in he es se which, when sub ac ed om he
cu en poin , yields an imp o ed poin .
•The e does no exis such an elemen in he se , so ha he poin is he
op imum o he ibe .
2.2. To ic ideal. The o ic ideal associa ed wi h A, deno ed as IAis de ined as
IA=hxα−xβ:Aα=Aβ,α,β∈ZN
+i ⊂ Q[x1,...,xN].
Gi en a e m o de <ccompa ible wi h he cos unc ion c(x), a educed G ¨obne
basis G<co IAyields a es se G<c o (LP) (c . [28]). I he educed G ¨obne
basis is o med by binomials
G<c={xαi−xβi, i = 1,2,..., },wi h in<c(xαi−xβi) = xαi,
whe e in<cs ands o he g ea es monomial wi h espec o <c, hen he es se
is exp essed as
G<c={αi−βi, i = 1,2,..., }.
2.3. Walk back p ocedu e. The walk back p ocedu e is an algo i hm which com-
pu es he op imum o a nonlinea in ege p og amming p oblem unde some con-
di ions. Ou p oblem is o he o m:
(P) min c(x) = c ·x
x∈ A ⊂ Zn
+,
x∈ B ⊂ Zn
+,
whe e
• he cons ain s x∈ A a e linea , and a es se can be ob ained in p ac ice
wi h espec o he linea cos unc ion and hese es ic ions;
• he cons ain s x∈ B can be linea and nonlinea .
We can assume wi hou loss o gene ali y ha c(x) is a linea cos unc ion
because i i we e nonlinea we would ans o m he p oblem in oducing he new
cons ain c(x)≤z, ha would be included in he se x∈ B, and he objec i e
unc ion min z. The p oblem would now i wi hin he o iginal hypo hesis, bu he
es se will change because he cos unc ion ha de ines he e m o de is di e en .
4J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ, AND J.M. UCHA-ENR´
IQUEZ
Le (LIP) deno es he elaxed linea in ege p oblem, namely:
(LIP) min c(x)
x∈ A ⊂ Zn
+.
Le Gbe he es se associa ed wi h he elaxed linea p oblem (LIP). S a ing
om some solu ion o (LIP) and adding ec o s om G, e e y easible poin o he
elaxed p oblem (LIP) can be eached. So, in pa icula , e e y easible poin o
p oblem (P) can be eached as well. Bu we do no need o comple e an exhaus i e
enume a ion o he easible poin s o (P): i p′is a easible poin o (P), wi h cos
c(p′), all he pa hs s a ing om poin s whose cos is g ea e han c(p′) can be
p uned. Remembe ha sub ac ing he elemen s o he es se always educes he
cos , so adding hem (o sub ac ing he elemen s o he e e se es se ) p o ides
poin s ha do no imp o e he alue c(p′). When a pa h is p uned, all i s poin s
a e disca ded. Poin s wi h nega i e componen s a e dele ed oo. Along his p ocess
new poin s a e gene a ed, called pending nodes, and he pa hs s a ing om hem
mus be analyzed. A he end all he possibili ies will ha e been p ocessed, and
he inal esul will be an op imum o (P), o a ce i ica e ha p oblem (P) has
an emp y easible egion i no easible poin could be eached. This is he walk-
back p ocedu e, desc ibed in [30]. The abo e a gumen can be summa ized in he
ollowing esul :
Theo em 2.1. The walk-back p ocedu e sol es he p oblem (P), ha is, i ob ains
an op imum o shows ha he p oblem has no easible solu ion.
To he bes o ou knowledge, he e ha e been ew p ac ical examples whe e he
walk-back p ocedu e has been success ully applied, as in [30], [17], [9]. This lack o
applicabili y may be due o i s wo main d awbacks: he compu a ion o he es
se and he ime equi ed o isi ing he poin s x∈ A o e en ually ob ain an
op imum o (P).
•The compu a ion o he es se has, in gene al, a high cos . We ha e used
he o ic ideal app oach [28], which is implemen ed in a e y e icien way in
he so wa e 4 i2 [1]. In some cases, he e is no need o such compu a ion,
because i is possible o gi e a closed o m o a G ¨obne basis o he p oblem,
as i is made o example in [17].
•The poin s a e o de ed aking in o accoun hei cos . As soon as a easible
poin o (P) is eached, new poin s a e ound quickly, and one o hem
is o en an op imum. Howe e , he p ocessing ime o each such easible
poin s is usually long and he lis o pending nodes is huge.
The ques ion is whe he i is possible o o de he poin s ha ha e o be isi ed
in an al e na i e way, so ha new easible be e poin s a e ob ained ea lie . This
app oach is explained in Sec ion 3.
3. Combining es se s and a penalized s a egy
3.1. Penal y unc ions. T adi ionally, me hods using penal y unc ions ans o m
a cons ained p oblem in o a single uncons ained p oblem o in o a sequence o
uncons ained p oblems. Uncons ained p oblems a e easie o manage in gene al.
The gene al idea is o place he cons ain s in o he objec i e unc ion wi h a penal y
pa ame e ha penalizes p ope ly any iola ion o hese cons ain s.
AN IMPROVED TEST SET APPROACH TO NONLINEAR INTEGER PROBLEMS 5
Gi en a p oblem (P),
(P) min c(x)
x∈ A ⊂ Zn
+,
x∈ B ⊂ Zn
+,
apenal y unc ion p(x) is a unc ion such ha p(x) = 0 o x∈ A ∩ B and
p(x)≥γ > 0 i x∈ A B. Mo eo e , he s a emen γ > 0 comes om he disc e e
na u e o (P).
Fo a p oblem (P) he penal y p oblem (Ppen(µ)) is de ined as
minx∈AT(x, µ) = c(x) + µp(x), o a ce ain µ > 0.
Since T(x, µ) = c(x) i x∈ A ∩ B, i is clea ha
op (P) ≥op (Ppen(µ)).
In he p oblems ha we deal wi h in his wo k he egion Bis possibly an
eno mous, bu ini e, subse o Zn. I can be p o ed ha , in his si ua ion he
p oblem is equi alen o a penalized one.
Theo em 3.1 (c . [20] Th. 2.11).Suppose ha A B 6=∅. Le c0be a lowe bound
o c(x)in Aand ρ > 0be a lowe bound o minx∈A B p(x). Then, o any µ > µ0
wi h
µ0=op (P) −c0
ρ
we ha e
op (P) = op (Ppen(µ)).
3.2. O de ing nodes by penalized cos . Following he no a ion o [30] we de-
sc ibe in his subsec ion ou algo i hm. The walk-back p ocedu e p o ides a lis o
easible poin s, no ed P, o he elaxed linea p oblem (LIP) and a guided sea ch
p ocedu e ha allows us o ge an exac op imum o he o iginal p oblem (P).
Howe e , he way in which he poin s a e scanned is undamen al o c ea e an algo-
i hm ha pe o ms he compu a ions in a easonable ime. A i s app oach is o
o de he pending nodes lis acco ding o hei cos ([30], [17]). A second app oach,
p esen ed he e, consis s o o de ing he pending nodes by a penalized cos unc ion
o he o m
T(x, µ) = c(x) + µp(x),
whe e he cos o he poin is added o a alue associa ed wi h he dis ance o he
egion de ined by he cons ain s o Bin p oblem (P). Ins ead o o de ing he poin s
o be isi ed by he o iginal cos unc ion c, he penalized cos unc ion T(x, µ) is
used, expec ing o each as e some poin s ha a e easible o he whole p oblem
(P). This is he main ad ance o ou algo i hm compa ed o he one desc ibed in
[30]: he inse ion in he pending nodes lis o de ed by he new penalized cos
unc ion.
I is wo hwhile o emphasize ha his p ocedu e is exac and ce i ies he op i-
mali y as p o ed in Theo em 2.1, because i is only a di e en way o isi ing he
poin s equi ed o sol e he p oblem. I s a s om he op imum βo (LIP) ( ha
we assume in easible o (P) since o he wise we a e done), and p oduces ecu si ely
new poin s x ha a e in wo possible si ua ions:

6J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ, AND J.M. UCHA-ENR´
IQUEZ
(1) xis easible o (P), so we include i in he se Yo easible poin s o (P)
ob ained so a . I is no necessa y o ollow pa hs om xsince he cos
would be wo se;
(2) xis no easible o (P) and we do no ha e poin s in Ywi h be e cos ,
hen xis inse ed acco ding o he unc ion T(x, µ) in he se Po nodes
o examine.
4. Applica ions
4.1. Co ela ed se up. The walk back p ocedu e was in oduced in [30] and ap-
plied in a p oblem o assignmen o jobs o machines, wi h gi en p oduc ion and
co ela ed se up cos s, capaci y cons ain s and p obabili y o each a gi en de-
mand. We deal wi h he same p oblem by adding he imp o emen o he penalized
cos and a se o new cu s ha does no al e he op imum.
The no a ion o he model is he ollowing:
•nnumbe o job ypes, indexed by i,
•mnumbe o machines, indexed by j,
•(D1,...,Dn) andom ec o o demands,
•Nsize o he sample se used o es ima e he p obabili y,
•Cjcapaci y ( ime) o each machine,
•(ˆ
D1,..., ˆ
Dn) means ec o o he p obabili y dis ibu ion o demand,
•Sij se up ime o job ype ion machine j,
•Kij se up cos o job ype ion machine j,
•Milo spli ing,
•L′
ij he cos o p oducing a uni o p oduc ype ion machine j,
•Lij = ( ˆ
Di/Mi)L′
ij,
•pij p ocessing ime o a uni o job ype ion machine j,
•γp obabili y o no sho all.
•zij equals 1 i job ype iis scheduled on machine j, 0 o he wise,
•yij mul iples o 1/Mio demand o p oduc ia e scheduled on machine j.
The model p esen ed in [30] is:
(SP) minimize X
iX
j
(Kijzij +Lijyij)
subjec o
m
X
j=1
yij =Mi, i = 1,2,...,n,(1)
Mizij ≥yij, i = 1,2,...,n,j = 1,2,...,m,(2)
gj(z,y) =
n
X
i=1
pij ˆ
Di/Miyij +
n
X
i=1
Sijzij ≤Cj, j = 1,2,...,m,(3)
g0(z,y) = P ob (n
X
i=1
pij (Di/Mi)yij +
n
X
i=1
Sijzij ≤Cj, j = 1,2,...,m)≥γ,(4)
zij ∈ {0,1}, yij ∈ {0,1,...,Mi}(5)
The condi ion (4) will be compu ed in a sample da ase o size N. As usual we
no e (LSP) he linea elaxed p oblem de ined by cons ain s (1), (2) and (5).
AN IMPROVED TEST SET APPROACH TO NONLINEAR INTEGER PROBLEMS 7
The model (SP) admi s a amily o op imali y cu s:
(6) zij ≤yij, i = 1,...,n,j = 1,...,m.
I is clea ha i he job iis assigned o he machine j, hen some hing is p oduced
in i . These cons ain s educe he easible egion, bu do no al e he op imum o
p oblem (SP). We call p oblem (ISP) he esul ing model ob ained om (SP) a e
adding he cons ain s (6).
The es se is associa ed wi h he linea cons ain s (1), (2), (5) and (6), which
de ines a elaxed p oblem (LISP). The equa ions (3) and (4) a e checked o e e y
poin and es easibili y o P oblem (ISP).
Simila ly o [30], he linea p oblem wi h es ic ions (1), (2), (5) and (6) can be
exp essed wi h equali ies by adding slack a iables:
(LISP −II) minimize X
iX
j
(Kijzij +Lijyij)
subjec o
m
X
j=1
yij =Mi, i = 1,2,...,n,(7)
yij +aij −Mizij = 0, i = 1,2,...,n,j = 1,2,...,m,(8)
zij +bij = 1, i = 1,2,...,n,j = 1,2,...,m,(9)
−yij +zij +cij , i = 1,2,...,n,j = 1,2,...,m,(10)
yij, aij, bij, cij ∈Z+, i = 1,2,...,n,j = 1,2,...,m.(11)
Theo em 4.1. The se o binomials
yipaiqcip −yiqaipciq, i = 1,2,...,n,1≤p < q ≤m,
bipcip −zipaMi
ip , i = 1,2,...,n,p= 1,2,...,m,
bipyiqciq −zipyipaMi−1
ip aiq, i = 1,2,...,n,1≤p6=q≤m,
bipyiqziqaMi−1
iq −zipyipbiqaMi−1
ip ,1≤p < q ≤m,
is he educed G ¨obne basis o he o ic ideal co esponding o (LISP-II) wi h espec
o he lexicog aphical o de b > y > z > a > c. The le e ydeno es he se o
a iables (y11,...,ymn)and simila ly a, z, b and cdeno e he o he se s o a iables.
Wi hin a block, he a iables a e so ed lexicog aphically acco ding o index.
The p oo is w i en in Appendix A.
Howe e , his basis is no he one needed o build he es se wi h espec o
he cos unc ion. We ha e used 4 i2 o ge he basis in a s aigh o wa d way,
and he compu a ion cos has been always unde one second o all he conside ed
ins ances, which a e o he same size o hose p oposed in [30].
4.1.1. New penalized cos unc ion. Following he no a ion o Sec ion 3, le xbe he
se o a iables yij, zij. Mul iplying by a sui able cons an , we can assume ha all
he coe icien s in gj(x) o j= 1,2,...,n a e in ege s. We conside he unc ions
G0(x) = γ−g0(x), Gj(x) = gj(x)−Cj.
Le Abe he ini e se in Zn+mde ined by he linea cons ain s (1), (2), (5) and
(6). We call
B={x∈Zn+m|Gj(x)≤0, j = 0,1,...,m},
8J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ, AND J.M. UCHA-ENR´
IQUEZ
and de ine he penal y unc ion
p(x) =
m
X
j=0
max(Gj(x),0).
Theo em 3.1 gi es a cons an µ0which ames a pa ame e egion whe e he same
objec i e alue o he nonlinea p oblem and he penalized e sion is ob ained.
Le c(x) = PiPj(Kij zij +Lijyij) be he cos unc ion and ˆ
x he op imal
solu ion o he elaxed p oblem (LISP).
P oposi ion 4.1. Le c1:= PiPj(Kij +Lij),Nbe he size o he sample se
and ρ0=1
2N. Le (ISP)′be he p oblem ha esul s om (ISP) a e eplacing
cons ain (4) by g0(x)≥γ′, wi h γ′=⌈Nγ⌉
N−1
2N.
The objec i e alues o p oblems (ISP) and (ISP)′coincide. Mo eo e , o any
µ≥µ0=c1−c(ˆx)
ρ0, P oblem (ISP) and he penalized e sion o (ISP)′wi h objec i e
unc ion c(x) + µp(x)ha e he same op imal alue.
P oo . Fi s o all, we obse e ha g0(x) is a s epwise unc ion ha can only
assume he alues k
N o k= 1,...,N. The e o e, he se o easible poin s o (ISP)
ha sa is y g0(x)≥⌈Nγ⌉
N o any γ∈(0,1) is he same ha hose ha sa is y
g0(x)≥⌈Nγ⌉
N−1
2N. This p o es he i s s a emen o he p oposi ion.
F om now on we only conside (ISP)′and i s penalized e sion. In o de o
apply Theo em 2, we need o p o e ha ρ0is a alid lowe bound o p(x) on A B.
Indeed, we no e ha i x6∈ B hen ei he Gj(x)>1 o some j= 1,...,m o
g0(x)<⌈Nγ⌉
N−1
2N. In he o me case, we ha e p(x)≥Pm
j=1 Gj(x)≥1> ρ0. In
he la e case, due o ⌈Nγ⌉−1
N<⌈Nγ⌉
N−1
2N<⌈Nγ⌉
Nand aking in o accoun ha
g0(x) only assumes alues k
N, hen he cons ain g0(x)<⌈Nγ⌉
N−1
2Nis equi alen
o g0(x)≤⌈Nγ⌉−1
N. So γ′−g0(x)≥1
2Nand hence p(x)≥G0(x)≥γ′−g0(x)≥1
2N.
Theo em 2 p o ides a cons an µ0which depends on he unknown op imal alue
o (ISP)′. To a oid his incon enience, we shall eplace µ0by some hing g ea e .
We subs i u e he unknown alue o (ISP)′by c1, a alid uppe bound o ha alue.
Hence, we can apply Theo em 3.1 o (ISP)′and i s penalized e sion o conclude
he second s a emen o he p oposi ion. 

In spi e o he abo e esul , ou algo i hm does no sol e he penalized e sion.
Ra he han ha we use he o de induced by i s alues o guide he sea ch s a egy
in ou b anching ee. Howe e , he abo e es ima ion gi es a good es ima e o µ
in ou penal y e m because a big alue o µyields a poo pe o mance o ou
algo i hm.
I is clea ha c0=c(ˆ
x) is a lowe bound o minx∈A c(x). In ou compu a-
ional esul s, a e some expe imen a ion, we ha e used a di e en es ima e o he
alue o minx∈A B p(x) han he one gi en in P oposi ion 4.1 because o i s be e
pe o mance.
Indeed, he alues o he unc ions Gj(x) o j= 1,2,...,m a e g ea e han
one, while he alues o G0(x) a e less han 1. We le ¯ρ=G0(ˆ
x), and ake
¯µ0=c1−c0
¯ρ, α =⌊log( c0
¯µ0
)⌋,and µ=α¯µ0.
AN IMPROVED TEST SET APPROACH TO NONLINEAR INTEGER PROBLEMS 9
This quo ien is in ended o a oid ha he coe icien ¯µ0 akes on alues e y
la ge wi h espec o c0. The penalized cos is hen T(x, µ) = c(x) + µp(x).
We ha e conside ed o he penalized cos unc ions, as he adap i e unc ion de-
sc ibed in [11], o he o acle unc ion o [27], bu he compu a ional esul s ha e been
sligh ly wo se han he expe imen s wi h he p e iously de ined unc ion T(x, µ).
4.1.2. Compu a ional esul s. In o de o e alua e he pe o mance o he new o -
de ing in he lis Po pending nodes, se e al amilies o ins ances ha e been con-
side ed and compa ed wi h he p e ious walk-back p ocedu e. Bo h algo i hms
ha e been coded in Ma lab and un on a In el Xeon X5660 (2.8 GHz) wi h 32
GB RAM. The da a ha e been andomly gene a ed wi h he condi ions desc ibed
in [30, Example 4], ha is, n= 7 jobs and m= 4 machines, wi h capaci ies
(20,20,40,40) ( he e is a misp in in he o iginal a icle), mean demands equal o
µ= (20,16,12,8,8,4,4), lo s M= 2 and co a iance ma ix
V=










36 0 −10.8 0 0 0 7.34
0 23 0 5.9 11.500
−10.8 0 13 0 0 −4.4−4.4
0 5.9 0 6 0 0 0
0 11.5 0 0 23 0 0
0 0 −4.4 0 0 6 0
7.34 0 −4.4 0 0 0 6










.
All se up imes Sij and p oduc ion imes pij a e equal o 1. The se up and p o-
duc ion cos s (Kij , L′
ij) a e p o ided in Table 1, simila ly o [30, Fig. 3], bu wi h
he e o s co ec ed ( he alues we e swapped).
Table 1. Se up and p oduc ion cos s o n= 7 jobs, m= 4 machines
job 1 job2 job 3 job 4 job 5 job 6 job 7
machine 1 5, 3 3, 4 3, 3 1, 2 1, 3 3, 3 5, 4
machine 2 1, 4 1, 4 4, 2 5, 2 3, 4 1, 3 2, 2
machine 3 4, 3 2, 3 5, 2 4, 2 4, 4 2, 2 4, 4
machine 4 5, 3 4, 4 4, 2 4, 3 1, 3 5, 4 2, 2
Di e en sample se s ha e been conside ed, wi h 250 eco ds, mean µand co-
a iance ma ix V. The e a e no di e ences among he di e en samples, we ha e
chosen he mo e desc ip i e one. The esul s appea in Table 2 o di e en alues
o he p obabili y γ. We compa e he uns o he o iginal walk-back p ocedu e
o [30], o de ed only by he cos (column “Walk-back” in ables), and he uns
wi h he p e iously de ined penalized cos unc ion (column “WB new o de ing”
o unc ion T(x, µ)). The column “To al” g oups he numbe o isi ed nodes and
CPU ime in seconds. The maximum numbe o poin s o be conside ed has been
se o 120000, (a p oxy o a CPU ime app oxima ely equi alen o 90 minu es
o compu a ion), and he label “Max” deno es ha he un has eached his limi
and i has been e mina ed. The column “Op imum” g oups he numbe o is-
i ed nodes and CPU ime o ge an op imum. When he p ocess has eached he
maximum numbe o poin s, he alue o he bes poin ound is shown, bu i is
no possible o gua an ee ha i is an op imum. I he p ocess has no e en ound
a easible poin we w i e “NNP”. The compu a ion o he G ¨obne basis is done
16J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ, AND J.M. UCHA-ENR´
IQUEZ
•When he walk-back p ocedu e ce i ies op imali y, he op imum is usually
ound a e a la ge numbe o nodes explo ed du ing he sea ch. The new
o de ing me hod inds i e y quickly and mos pa o he ime is used o
ce i y op imali y.
•The equi ed ime o ce i y op imali y has highly dec eased in all he cases.
This ac is due o he dec ease in he ime needed o each an ini ial easible
poin . I con ibu es o speeding up he p ocess h ough p uning pa hs. As
an illus a i e example in Table 5 he a e age ime needed in he walk-
back algo i hm o n= 15, k= 4 is 571.1 s, and he new o de ing me hod
equi es 432.6 s, an imp o emen o 25%.
•The pe o mance is be e han ha appea ed in [25].
4.2.9. Compa ison wi h o he sol e s. In o de o pe o m u he compa isons wi h
s anda d in ege nonlinea sol e s as Ba on ([29]), Couenne ([6]) o Bonmin ([7]),
he p oblem (RP) has been modeled in GAMS o ma . This encoding has allowed us
o launch ou da a se s in he Neos Se e ([14], [18], [16]) unde hese sol e s. We
ha e chosen he 30 ins ances o sys ems wi h n= 8, k = 4 om Table 6, because
i con ains a good asso men o cases. A summa y o he esul s a e epo ed in
Table 7 ha shows a e age ime o ce i y op imali y and in Table 8 ha shows he
ime equi ed o each he op imum (Couenne is no conside ed in he las Table).
Table 7. Compa ison o sol e s o he case n= 8, k = 4, ime o
ce i y op imali y
WB new o de ing Ba on Couenne Bonmin
A g. Time 373.4 53.9 1020.9 272.8
N/F 0 0 9 0
Table 8. Compa ison o sol e s o he case n= 8, k = 4, ime o
ea ch he op imum
WB new o de ing Ba on Bonmin
A g. Time 2.8 25.7 209.4
The columns iden i y he sol e s. The ow “A g. Time” con ains he a e age
ime o CPU epo ed by he ou pu s o he 30 ins ances. The ow “N/F” indica es
he numbe o examples ha he sys em has no been able o inish.
We no e he ollowing ac s:
•The packages Bonmin and Ba on ha e, in gene al, a be e pe o mance
o ce i y op imali y.
•In some cases we ha e obse ed ha Ba on e u ns a nonop imal poin ,
al hough i is e y close o he minimum cos . The walk-back p ocedu e
and Bonmin always e u n an ac ual op imal poin .
•The walk-back wi h new o de ing ound he op imum e y quickly, usually
unde 3 seconds, as can be seen in Figu e 2. This cha compa es he imes
used by walk-back, Bonmin and Ba on o ind he op imum. Couenne
epo s much la ge imes.

AN IMPROVED TEST SET APPROACH TO NONLINEAR INTEGER PROBLEMS 17
0
200
400
600
Runs
Time (s)
WB new o de ing
Bonmin
0
20
40
60
80
Runs
Time (s)
WB new o de ing
Ba on
Figu e 2. Time o ind an op imum: WB new o de ing, Bonmin
and Ba on
A na u al ques ion is how o combine he speed o he walk-back p ocedu e wi h
new o de ing o ind he op imum, and he good app oach o a nonlinea sol e like
Ba on o ce i y op imali y o he poin . This has been done including he poin
ound by he walk-back p ocedu e in he GAMS code as an ini ial easible poin . In
all he cases, he poin is ce i ied wi h he igh op imal cos , and he CPU ime
is signi ican ly educed, as i can be seen in Figu e 3.
0
50
100
Runs
Time (s)
Ba on
Ba on+poin
Figu e 3. Time o ce i y: Ba on and Ba on wi h ini ial poin
gi en by WB
5. Conclusions
The walk-back p ocedu e is based on ex ac ing ce ain linea cons ain s om
a nonlinea in ege p oblem o which a es se can be easily compu ed. S a ing
om an op imum o he elaxed p oblem, and using he e e se es se , all he
easible poin s o he o iginal p oblem can be eached, and an op imum can be
ound. The me hod has been imp o ed by gi ing a c i e ion o so he se o
18J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ, AND J.M. UCHA-ENR´
IQUEZ
poin s o be inspec ed by a penalized cos unc ion. This new cos unc ion ades
o he cos o a poin agains i s dis ance o he easible egion. As a esul , new
be e poin s a e ob ained as e han wi h he o de only by cos . Two eal design
enginee ing applica ions ha e been p esen ed: he scheduling o jobs on pa allel
machines gi en es ic ions on demands and capaci y o minimize cos s, and he
se ies pa allel edundancy alloca ion p oblem gi en a a ge eliabili y. The i s
p oblem includes a p obabilis ic cons ain wi h andom a iables in he echnology
ma ix, ha can no be ea ed wi h nonlinea sol e s. Ou app oach deals wi h
any compu able cons ain . This p oblem can be e o mula ed as a linea in ege
p og am, and s ill in ce ain cases ou app oach is compe i i e wi h he bes MILP
sol e s. The second applica ion conside ed con ains a nonlinea es ic ion gi en by
he eliabili y unc ion. This nonlinea model can be compa ed wi h o he sol e s
wi h ema kable esul s. We conclude, h ough ex ensi e compu a ions, ha bo h
applica ions show ha he combina ion o he walk-back p ocedu e and an imp o ed
o de ing is a p omising ool as an exac me hod o sol e nonlinea in ege p og ams.
Acknowledgmen s
This pape has been pa ially suppo ed by Jun a de Andaluc´ıa unde g an
FQM-5849, and Minis e io de Ciencia e Inno aci´on MTM2010-19336, MTM2010-
19576, MTM2013-46962-C2-1-P and FEDER. The au ho s would like o hank he
anonymous e iewe s o hei aluable commen s and sugges ions o imp o e he
quali y o he pape .
Re e ences
[1] 4 i2 eam. 4 i2—a so wa e package o algeb aic, geome ic and combina o ial p oblems on
linea spaces. A ailable a www.4 i2.de.
[2] Ach e be g, T. SCIP: Sol ing cons ain in ege p og ams. Ma hema ical P og amming Com-
pu a ion, 1(1):1–41, (2009).
[3] Ahmadiza , F. and Sol anpanah, H. Reliabili y op imiza ion o a se ies sys em wi h mul iple-
choice and budge cons ain s using an e icien an colony app oach. Expe Sys ems wi h
Applica ions, 38(4):3640–3646, (2011).
[4] Ahmed, S. and Shapi o, A. Sol ing Chance-Cons ained S ochas ic P og ams ia Sam-
pling and In ege P og amming. A ailable a www2.isye.ga ech.edu/people/ acul y/Shabbi -
Ahmed/cc u o ial.pd . Accessed 30 Ap il 2014.
[5] A is, D. and Fukuda, K. Re e se sea ch o enume a ion. Disc e e Applied Ma hema ics,
65(1-3):21–46, (1996).
[6] Belo i, P. Couenne. A ailable a www.coin-o .o g/Couenne/.
[7] Bonami, P. and con ibu o s. Bonmin — basic open-sou ce nonlinea mixed in ege p og am-
ming. A ailable a h ps://p ojec s.coin-o .o g/Bonmin.
[8] Cbc (Coin-o b anch and cu ). A ailable a h ps://p ojec s.coin-o .o g/Cbc.
[9] Cas o, F., Gago, J., Ha illo, I., Pue o, J., and Ucha, J.M. An algeb aic app oach o in ege
po olio p oblems. Eu opean Jou nal o Ope a ional Resea ch, 210(3):647–659, (2011).
[10] Che n, M.S. On he compu a ional-complexi y o eliabili y edundancy alloca ion in a se ies
sys em. Ope a ions Resea ch Le e s, 11(5):309–315, (1992).
[11] Coi , D. W., Smi h, A.E. and Ta e, D.M. Adap i e penal y me hods o gene ic op imiza ion
o cons ained combina o ial p oblems. INFORMS J.Compu ., 8(2):173–182, (1996).
[12] Coi , D.W. and Smi h, A.E. Reliabili y op imiza ion o se ies-pa allel sys ems using a gene ic
algo i hm. IEEE T ansac ions on Reliabili y, 45(2):254–260, (1996).
[13] Gu obi Op imiza ion, Inc. Gu obi Op imize Re e ence Manual. A ailable a
h p://www.gu obi.com.
[14] Czyzyk, J., Mesnie , M.P. and Mo ´e, J.J. The NEOS se e . IEEE Compu a ional Science
and Enginee ing, 5(3):68–75, (1998).
AN IMPROVED TEST SET APPROACH TO NONLINEAR INTEGER PROBLEMS 19
[15] Dje djou , M. and Rekab, K. A b anch and bound algo i hm o designing eliable sys ems
a a minimum cos . Applied Ma hema ics and Compu a ion, 118(2-3):247–259, (2001).
[16] Dolan, E. The NEOS se e 4.0 adminis a i e guide. Technical Repo Technical Memo an-
dum ANL/MCS-TM-250, Ma hema ics and Compu e Science Di ision, A gonne Na ional
Labo a o y, (2001).
[17] Gago, J., Ha illo, I., Pue o, J., and Ucha, J.M. Exac cos minimiza ion o a se ies-pa allel
sys em. Compu e s and Ope a ions Resea ch, 40(11):2752–2759, (2013).
[18] G opp, W. and Mo ´e, J.J. Op imiza ion en i onmen s and he NEOS se e , pages 167–
182. App oxima ion heo y and op imiza ion (Camb idge, 1996). Camb idge Uni . P ess,
Camb idge, (1997).
[19] Hemmecke, R. and Schul z, R. Decomposi ion o es se s in s ochas ic in ege p og amming.
Ma hema ical P og amming, 94(2-3):323–341, (2003).
[20] Li, D. and Sun, X. Nonlinea in ege p og amming. Sp inge , New Yo k, (2006).
[21] Li, Q., Guo, Y.K., Da ling on, J. and Ida, T. Minimised geome ic Buchbe ge algo i hm o
in ege p og amming. Annals o Ope a ions Resea ch, 108(1-4), (2001).
[22] Lued ke, J., Ahmed, S., and Nemhause , G. An in ege p og amming app oach o linea
p og ams wi h p obabilis ic cons ain s. Lec u e No es in Compu e Science 4513, pages
410–423, Be lin, 2007. Sp inge -Ve lag.
[23] MOSEK ApS, F uebje g ej 3, Boks 16, 2100 Copenhagen O, Denma k. The MOSEK op i-
miza ion ools manual e sion 6.0, 2009. A ailable a h p://www.mosek.com/.
[24] Ouzineb, M., Nou el a h, M., and Gend eau, M. Tabu sea ch o he edundancy alloca-
ion p oblem o homogenous se ies-pa allel mul i-s a e sys ems. Reliabili y Enginee ing and
Sys em Sa e y, 93(8):1257–1272, (2008).
[25] Ruan, N. and Sun, X. An exac algo i hm o cos minimiza ion in se ies eliabili y sys ems
wi h mul iple componen choices. Applied Ma hema ics and Compu a ion, 181(1):732–741,
(2006).
[26] Ruszczy´nski, A. P obabilis ic p og amming wi h disc e e dis ibu ions and p ecedence con-
s ained knapsack polyhed a. Ma hema ical P og amming, 93 (2), 195–215 (2002).
[27] Schlue e , M. and Ge d s, M. The o acle penal y me hod. Jou nal o Global Op imiza ion,
47(2):293–325, (2010).
[28] S u m els, B. G ¨obne bases and con ex poly opes, olume 8. Ame ican Ma hema ical Socie y,
P o idence, RI, (1996).
[29] Tawa malani, M. and Sahinidis, N.V. A polyhed al b anch-and-cu app oach o global op i-
miza ion. Ma hema ical P og amming, 103(2):225–249, (2005).
[30] Tayu , S.R., Thomas, R.R., and Na aj, N.R. An algeb aic-geome y algo i hm o scheduling
in p esence o se ups and co ela ed demands. Ma hema ical P og amming, 69(3):369–401,
(1995).
Appendix A. P oo o Theo em 4.1
Le Abe he ma ix associa ed wi h he es ic ions o P oblem (LSP-II). Then
Acan be di ided in i e blocks acco ding o he i e se s o a iables yij , aij , zij, bij
and cij. Le Ideno e he iden i y ma ix o size mn and Odeno e a ma ix wi h all
en ies ze o. Le Dbe he block diagonal (0,1)-coe icien ma ix associa ed wi h
cons ain s (7). Le −MI deno e he coe icien ma ix o he a iables zij, i =
1,...,n,j = 1, . . . , m in cons ain s (8). We can hen w i e Aas he (n+3mn)×5mn
in ege ma ix
A=



DO O O O
II−MI O O
O O I I O
−IOIOI




We no e = ( y, a, z, b, c), S ={ |A = 0}and he block y ep esen s he
a iables (Y11,...,Ymn), no ed in capi al le e s. Simila o he o he blocks.
Conside he ollowing cases:
20J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, J. PUERTO-ALBANDOZ, AND J.M. UCHA-ENR´
IQUEZ
(1) K1={ ∈S| y= b= 0}. Le S′= ke A′, whe e
A′=

I−MI O
OIO
OI I 
→

I−MI O
OIO
O O I
,
which is no singula . Then K1= 0 and he e is no binomial xα−xβsuch
ha con ains only he a iables aij , zij , cij .
(2) K2={ ∈S| b= 0}. Le S′′ = ke A′′, whe e
A′′ =



DO O O
I I −MI O
O O IO
−IOI I



.
By he p e ious case, we can assume y6= 0. The ows in he hi d block
imply ha z= 0. Then ∈K2i and only i ( y, a, c)∈S′′′ = ke A′′′,
o
A′′′ =

DO O
I I O
−IOI
.
Le Yip be he le mos nonze o componen in y. We can assume Yip >0,
because S′′′ is a ec o space. The ow block co esponding o Dimplies
ha he e exis s q > p such ha Yiq <0. Then
yip di ides x +, yiq di ides x −.
The second block o ows in A′′′ implies Aip =−Yip <0, Aiq =−Yiq >0.
F om he hi d block o ows, Cip =Yip >0, Ciq =Aiq <0. Then
yipaiqcip di ides x +, yiqaipciq di ides x −.
The ini ial e m in x +−x −wi h espec o >is x +because yip di ides
x +and yip i he g ea es monomial in he binomial. Then he ini ial e m
o
(12) yipaiqcip −yiqaipciq
di ides he ini ial e m o x +−x −.
(3) Le S= ke A. By (a) and (b) we suppose b6= 0. Le B s he le mos
nonze o componen in b. As in he p e ious case, ake B s >0. Because b
is he se o g ea es a iables o ou e m o de , x +is he leading e m.
We also ha e Z s =−B s <0.
(a) I Y s ≥0 hen
−Y s +Z s +C s = 0
hen
b sc s di ides x +
and he ini ial e m o
(13) b sc s −z saM
s .
di ides x +.
(b) Y s <0. Then he e exis s Y q, s 6=qwi h Y q =−Y s >0 .
AN IMPROVED TEST SET APPROACH TO NONLINEAR INTEGER PROBLEMS 21
(i) I C q >0, hen b sy qc q di ides x +. The ini ial e m o
(14) b sy qc q −z sy saM −1
s a q, s 6=q.
di ides he ini ial e m o x +−x −.
(ii) I C q ≤0 hen 0 < Y q ≤Z q, which implies B q <0 so s < q,
because B s was he i s nonze o elemen . The ows in he
second block imply ha
Y q +A q −M Z q = 0,so A q =M Z q −Y q ≥M Y q −Y q = (M −1)Y q.
Then he ini ial e m o
(15) b sy qz qaM −1
q −z sy sb qaM −1
s , s < q
di ides he ini ial e m o x +−x −.
We ha e e iewed all he cases, so he se s (12), (13), (14) and (15) o m he educed
G ¨obne basis.
Dep o. de ´
Algeb a, Uni e sidad de Se illa. Apdo. 1160, E-41080 Se illa (Spain)
E-mail add ess:[email protected]
Dp o. de Ma em´
a ica Aplicada I, E.T.S. de Ingenie ´
ıa In o m´
a ica, A . Reina Me -
cedes, s/n, 41012 Se illa, Spain
E-mail add ess:ha [email protected]
Dp o. de Es ad´
ıs ica e I.O., Facul ad de Ma em´
a icas, apdo. 1160, 41080 Se illa,
Spain
E-mail add ess:pue [email p o ec ed]
Dep o. de ´
Algeb a, Uni e sidad de Se illa. Apdo. 1160, E-41080 Se illa (Spain)
E-mail add ess:[email protected]