Finding Multiple Solutions in Nonlinear Integer Programming with Algebraic Test-Sets

Finding Mul iple Solu ions in Nonlinea
In ege P og amming wi h Algeb aic
Tes -Se s
M. I. Ha illo1(B),J.M.Jim´enez-Cobano2(B), and J. M. Ucha1,2(B)
1Depa amen o de Ma em´a ica Aplicada I., Uni e sidad de Se illa, Se illa, Spain
{ha illo,ucha}@us.es
2Insi u o de Ma em´a icas de la Uni e sidad de Se illa An onio de Cas o B zezicki,
Uni e sidad de Se illa, Se illa, Spain
[email p o ec ed]
Abs ac . We explain how o compu e all he solu ions o a nonlinea
in ege p oblem using he algeb aic es -se s associa ed o a sui able
linea subp oblem. These es -se s a e ob ained using G ¨obne bases. The
main ad an age o his me hod, compa ed o o he a ailable al e na i es,
is i s exac ness wi hin a qui e good efficiency.
1 In oduc ion
In many eal-li e combina o ial op imiza ion p oblems i is o g ea in e es o
he decision-make o ha e no only one solu ion, bu he se o all op imal
solu ions (see [15]o [11], o example). The in o ma ion p o ided by his se can
gi e some unexpec ed insigh s abou he ea u es o he solu ions, and some imes
s ands as a fi s s ep o mul i-objec i e op imiza ion as well.
On he o he hand, some imes hese p oblems equi e nonlinea cons ain s
o be modeled p ope ly. In [14] a me hod o p oblems o he o m
min cx
s. .Ax
≤b
x∈Ω
x∈Nn
(1)
whe e A∈Zm×n,c ∈Zn,b ∈Zm(ope a o s ands o ansposi ion) and
he egion Ωis fini e and defined by linea and nonlinea cons ain s, was p o-
posed. This me hod makes use o he so called es -se s associa ed o he linea
subp oblem
min cx
s. .Ax
≤b (2)
x ∈ Nn
Fi s au ho is pa ially suppo ed by MTM2016-75024-P and MTM2016-74983-C2-
1-R. Thi d au ho is pa ially suppo ed by MTM2016-75024-P, P12-FQM-2696 and
MTM2016-74983-C2-1-R.
V. P. Ge d e al. (Eds.): CASC 2018, LNCS 11077, pp. 230–237, 2018.
h ps://doi.o g/10.1007/978-3-319-99639-4_16
Mul iple Solu ions in Nonlinea IP wi h Tes -Se s 231
De ini ion 1. Ase T⊂Znis a es -se associa ed o p oblem 2i T⊂ke (A),
and o any non op imal x easible o 2 he e exis s a ∈Tsuch ha x− is
easible and c(x− )<c(x).
As a consequence o his defini ion, s a ing om an op imal poin ˆxo
p oblem 2you can eco e he se o all he easible poin s, adding elemen s o
he es -se un il you e en ually comple e all he easible egion. In his way, you
can ob ain he op imal poin s o p oblem 1walking back om he linea op imal
poin un il you each he egion Ω. Technical de ails can be ound in [14]. The
easible egion will be supposed fini e, al hough his is no s ic ly necessa y.
The e a e se e al ways o compu ing es -se s (as a ma e o ac , hey can be
compu ed depending only on he cos and he ma ix o cons ain s, no aking
in o accoun he igh hand side, o example). One o he mos efficien and
manageable ways is using G ¨obne bases (see o example [7]) wi h he so wa e
4 i2 (see [9]). This app oach is based in he classical pape [4], ha shows how
o sol e a Linea In ege p oblem ob aining G ¨obne bases o a sui able binomial
ideal wi h espec o an o de ing compa ible wi h he cos unc ion.
In [3,10] he me hod o [14] is applied o eal-li e size p oblems wi h e y
compe i i e esul s. In his wo k, we (1) explain how o modi y he walk-back
me hod o ob ain all he op imal poin s, and (2) compa e i s pe o mance wi h
he na u al gene aliza ion o he algo i hm p esen ed in [15] and wi h he com-
me cial so wa e BARON (see [1]).
Rema k 1. The ideals co esponding o he me hod ha we p esen in his wo k
a e no ze o-dimensional, so some efficien s a egies as T iangula Decomposi-
ion can no be applied o he G ¨obne bases compu a ions. In p inciple, he
me hod p oposed in [2] would be an al e na i e o ea some Nonlinea In ege
Op imiza ion p oblems wi h ze o-dimensional ideals, bu as soon as some con-
s ain s can no be exp essed in e ms o polynomials o he ank o alues o
he a iables is big he me hod is useless.
2 Finding All he Op imal Poin s wi h a Gene al In ege
Cu
In [15] a me hod is in oduced o show how o compu e all he op imal poin s in
In ege Linea P oblems. Once an op imal poin is ob ained, he idea is o add
some condi ions o make i un easible and sol e again. Mo e p ecisely, i you a e
sol ing he p oblem 1and ha e ob ained an op imal solu ion (x0
1,...,x
0
n)you
can add he cons ain n

i=1
|xi−x0
i|≥1
o assu e ha (x0
1,...,x
0
n) is un easible o his new p oblem. As you ob ain new
op imal solu ions you ha e o add a simila cons ain o each solu ion. This
o mula ion can be linea ized, as i is explained in [15, P op. 1]. This me hod
232 M. I. Ha illo e al.
can be used o Nonlinea In ege p oblems simply conside ing p oblems o he
o m min cx
s. .Ax
≤b
n
i=1 |xi−xj
i|≥1,j =1,...,N
x∈Ω
x∈Nn
wi h Ncons ain s o y o ob ain he (N+ 1)- h op imal poin . One o he
aims o his pape is o compa e his na u al app oach o an al e na i e algeb aic
me hod.
3 Finding All he Op imal Poin s wi h Tes -Se s
Ou algo i hm is based on he algeb aic algo i hm o [14] ha p o ides one
solu ion o a gi en nonlinea in ege p oblem o he o m
min cx
s. .Ax
≤b
x∈Ω
x∈Nn
(P)
whe e A∈Zm×n,c∈Zn,andb∈Zm. Le us desc ibe he s eps o ou me hod:
– We s a , as in he algo i hm p oposed in [14], in he op imal poin o a
sui able linea subp oblem
min cx
s. .Ax
≤b
x∈Nn
(PL)
Rema k 2. The selec ion o he subp oblem has o do fi s wi h he compu abili y
o he es -se , ha can be a bo leneck as i is a compu a ion o a G ¨obne basis
o a ce ain ideal (see [7]). Mo eo e , al hough he es -se o he whole linea
pa o p oblem 1is a ailable, some imes i is be e o compu e he es -se
associa ed o a subma ix o A ha gi es us a mo e manageable numbe o
di ec ions o be conside ed a any poin du ing he walk-back. The cons ain s
ha a e no included in he subma ix a e simply added o he desc ip ion o Ω.
– Then we sys ema ically add he elemen s o he co esponding es -se , hus
wo sening he cos unc ion ying o ob ain in e u n easible poin s o
p oblem 1, un il we ge in o Ω.
– The diffe ence o he o iginal me hod ( ha was designed o find only one
op imal poin ) is ha now we ha e o manage he sea ching o new possible
op imal poin s inside Ω, once we ha e eached a candida e. While in he
algo i hm o [14] you disca d new poin s wi h he same op imal alue, we
ins ead s ock hem in a p o isional lis . This lis will be he se o op imal
poin s as long as we find a new be e alue inside he egion Ω.
Mul iple Solu ions in Nonlinea IP wi h Tes -Se s 233
– I we e en ually find an imp o emen in he cos we dele e he p o isional
lis . O he wise, we al eady ha e he se o op imal poin s.
The pseudocode o ou algo i hm is he ollowing one:
INPUT: c, A, b;Ω; op imal poin βo 2;Tassocia ed es -se o p oblem 2.
Op := ∅;
Lea es := {β+ |∀ ∈T}∩Nn
cos Op =∞
IF β∈Ω
THEN Op := {β};
cos Op := cβ
WHILE (Lea es =∅)DO
FOR h∈Lea es DO
IF c(h)<cos Op
Lea es =(Lea es {h})∪({h+ |∀ ∈T}∩Nn)
IF h∈Ω
THEN Op ={h};
cos Op =ch ;
Lea es =(Lea es {h})∪({h+ |∀ ∈T}∩Nn)
 he lis o old candida es is dele ed
and upda ed wi h a new candida e
ELSE IF c(h)>cos Op
THEN Lea es =Lea es {h}
 hese b anches a e disca ded
ELSE IF c(h)=cos Op
THEN Lea es =(Lea e {h})∪({h+ |∀ ∈T}∩Nn)
IF h∈Ω
THEN Op =Op ∪{h};
a new candida e o be an op imal poin has been ob ained
END WHILE
OUTPUT: Op he se o all op imal poin s o p oblem 1wi h cos cos Op
Rema k 3. I is s aigh o wa d o modi y his algo i hm o ob ain he Kbes
op imal poin s o a gi en K,asin[11].
4 Compu a ional Expe imen s
We ha e un all he examples o es ou algo i hm coded in Py hon in a com-
pu e wi h an In el Co e i5, 3.5 Ghz, 8 Gb o RAM, unde Ubun u. The examples
wi h BARON [1] and COUENNE [6] ha e been sen o neos-se e .o g.
We ha e s udied wo amilies o examples: he in ege po olio p oblem and
he p oblem o eliabili y in se ies-pa allel sys ems.
234 M. I. Ha illo e al.
4.1 In ege Po olio P oblem
In he in ege po olio p oblem (see [3]) we ha e o sol e p oblems o he o m
max
n

i=1
cixi
s. . xCx ≤R0
n

i=1
bixi≤B
x∈Nn
(3)
whe e bia e he p ices oday o nal e na i e in es men s o asse s; cia o ecas
o hei u u e p ices; he ma ix Chas o do wi h he co a iance ma ix o he
his o ical e u ns o he asse s and i is a way o measu ing he isk o a po olio;
R0s ands o he maximum admissible isk; Bis he a ailable budge .
This so called mean- a iance po olio model was in oduced by Ma kowi z
wi h con inuous a iables (see [12] o he model and [5]o [16] o he mixed-
in ege case), bu i is in e es ing o conside he case o in ege a iables: fi s
o ake in o accoun he fini e di isibili y o he asse s and second o conside
some logical condi ions ha appea in hese p oblems.
I you conside ailo ed examples o which wo o mo e a iables ha e he
same p ice and isk you ob ain many diffe en op ima and can compa e ou
me hod o he gene aliza ion o [15]. As a gene al ou come we ha e ob ained
ha as he numbe o op imal poin s inc eases ou me hod o e comes by a
he gene al cu me hod (coded in GAMS o COUENNE). The eby, you can
conside o example he simple case
max 2x1+x2+x3+···+xn−1+xn
s. . x1+x2+x3+···+xn−1+xn≤B
x1···xnC⎛
⎜
⎝
x1
.
.
.
xn
⎞
⎟
⎠≤R0
x∈Nn
(4)
wi h Cdefined by cii =0.05,c
ij =−0.01 i i=j o n=10,15,20,50,100,
B= 10 and a no e y igh R0 o include many poin s. In his amily o
examples you can ob ain housands o op imal poin s. In a e age ou me hod is
mo e han a hund ed imes as e o big numbe s o op imal poin s.
Rema k 4. Compa ing wi h he comme cial so wa e BARON, ha has he
op ion o compu ing he Kbes op imal solu ions, we ob ain be e unning
imes only in 15% o he cases. Ne e heless, ou me hod ob ains exac ly he
comple e se o op imal poin s in all cases. BARON, in con as o ou me hod,
ails in 11% o he cases: in 5% o he cases i does no ob ain he op imal cos
and in 6% does no find he comple e se , due o ounding p oblems.

Mul iple Solu ions in Nonlinea IP wi h Tes -Se s 235
4.2 Reliabili y P oblems
The edundancy alloca ion p oblem can be o mula ed as he minimiza ion o he
design cos o a se ies-pa allel sys em wi h mul iple componen choices, while
ensu ing a gi en sys em eliabili y le el. The ob ained model is a nonlinea in e-
ge p og amming p oblem wi h a nonlinea , nonsepa able cons ain (see [8,13]
o [10]). I has he o m
min
n

i=0
k

j=1
cijxij
s.a. R(x)≥R0
k

j=1
xij ≥1,∀i=1,...,n
0≤xij ≤uij,∀i=1,...,n, j =1,...,k
xij ∈Z+
(5)
wi h R(x)=
n

i=1 1−
k

j=1
(1 − ij)xij . In his p oblem nis he numbe o sub-
sys ems (in se ies); ki he numbe o diffe en ypes o a ailable componen s (in
pa allel) o he i- hsubsys em,1≤i≤n; ij he eliabili y o he j- h com-
ponen o he i- h subsys em, 1 ≤i≤n, 1≤j≤ki;cij , he cos o he j- h
componen o he i- h subsys em, 1 ≤i≤n, 1≤j≤ki;lij,u
ij, lowe /uppe
bounds o numbe o jcomponen s o he i- h subsys em, 1 ≤i≤n, 1≤j≤ki;
R0, an admissible le el o eliabili y o he whole sys em; xij, numbe o jcom-
ponen s used in he i- h subsys em, 1 ≤i≤n, 1≤j≤ki.
We ha e s udied abou 100 examples wi h 2, 3 and 4 subsys ems and wi h
2 o 3 componen s in each subsys em ( he cos s and eliabili ies gene a ed an-
domly, ij ∈[0.90,0.99] and R0=0.90). The summa y is in Tables 1,2and 3
and con ains only he in o ma ion abou he examples wi h mul iple numbe o
solu ions.
Table 1. Reliabili y examples n=3,k=2,3.
A e age CPU Time % Comple e se o op imal solu ions ound
Tes -se 0.2 100 %
BARON K-bes 0.2 100 %
Gene al cu 0.54 100 %
Table 2. Reliabili y examples n=4,k=2.
A e age CPU Time % Comple e se o op imal solu ion ound
Tes -se 0.46 100 %
BARON K-bes 0.21 72.72 %
Gene al cu 0.98 100 %
236 M. I. Ha illo e al.
Table 3. Reliabili y examples n=4,k=3.
A e age CPU Time % Comple e se o op imal solu ion ound
Tes -se 1.1 100 %
BARON K-bes 0.19 61.54 %
Gene al cu 1.29 100 %
We can obse e ha :
– The es -se me hod and he gene al cu me hod a e exac . BARON, on he
con a y, does no gi e he comple e se o op imal poin s o e en one (in
ac , usually p o ides only one al hough you ask o he bes 3 o 4 bes ) in
abou 30%o hecases.
– BARON is be e in CPU ime han he es -se me hod, and his is be e
han he gene al cu me hod, and much be e as he numbe o op imal
poin s inc eases subs an ially. I , o example, you ea an example wi h a
hund ed op imal poin s you ha e o sol e 99 p oblems wi h 1, 2, ...,99new
cons ain s, espec i ely.
5 Conclusions
We ha e p esen ed an exac me hod o ob ain he se o all op imal poin s o a
gi en Nonlinea In ege p oblem as p oblem 1. A con enien linea subp oblem is
selec ed and hen, walking back om an op imal poin o his linea subp oblem
wi h he help o a es -se , he easible egion o he o iginal p oblem is eached
in all diffe en ways, upda ing a lis o op imal poin s. In his wo k we ha e
s udied wo amilies o examples:
– Po olio in ege p oblems ha can p oduce a huge numbe o op imal poin s
and o which ou algo i hm o e comes a gene al cu app oach as he one
p oposed in [15].
– Reliabili y p oblems, in which we poin ou p oblems o lack o exac ness in
he comme cial so wa e BARON compa ed wi h ou app oach.
Re e ences
1. Sahinidis, N. V.: BARON 14.4.0: Global Op imiza ion o Mixed-In ege Nonlinea
P og ams. Use ’s Manual (2014)
2. Be simas, D., Pe akis, G., Tayu , S.: A new algeb aic geome y algo i hm o
in ege p og amming. Manag. Sci. 46(7), 999–1008 (2000)
3. Cas o, F.J., Gago, J., Ha illo, I., Pue o, J., Ucha, J.M.: An algeb aic app oach
o in ege po olio p oblems. Eu . J. Ope . Res. 210(3), 647–659 (2011)
4. Con i, P., T a e so, C.: Buchbe ge algo i hm and in ege p og amming. In: Ma -
son, H.F., Mo a, T., Rao, T.R.N. (eds.) AAECC 1991. LNCS, ol. 539, pp. 130–139.
Sp inge , Heidelbe g (1991). h ps://doi.o g/10.1007/3-540-54522-0 102
Mul iple Solu ions in Nonlinea IP wi h Tes -Se s 237
5. Co azza, M., Fa a e o, D.: On he exis ence o solu ions o he quad a ic mixed-
in ege mean- a iance po olio selec ion p oblem. Eu . J. Ope . Res. 176, 1947–
1960 (2007)
6. Belo i, P.: COUENNE: a use ’s manual. Depa men o Ma hema ics Sciences,
Clemson Uni e si y. h ps://www.coin-o .o g/Couenne/
7. Cox, D.A., Li le, J., O’Shea, D.: Using Algeb aic Geome y. G adua e Tex s in
Ma hema ics, ol. 185, 2nd edn. Sp inge , Hiedelbe g (2005). h ps://doi.o g/10.
1007/978-1-4757-6911-1
8. Dje djou , M., Rekab, K.: A b anch and bound algo i hm o designing eliable
sys ems a a minimum cos . Appl. Ma h. Compu . 118, 247–59 (2001)
9. 4 i2 eam: 4 i2 - a so wa e package o algeb aic, geome ic and combina o ial
p oblems on linea spaces (2013). h ps://www.4 i2.de
10. Gago, J., Ha illo, I., Pue o, J., Ucha, J.M.: Exac cos minimiza ion o a
se ies-pa allel eliable sys em wi h mul iple componen choices using an algeb aic
me hod. Compu . Ope . Res. 40(11), 2752–2759 (2013)
11. Le˜ao, A.A.S., Che i, L.H., A enales, M.N.: De e mining he K-bes solu ions o
knapsack p oblems. Compu . Ope . Res. 49, 71–82 (2014)
12. Ma kowi z, H.: Po olio selec ion. J. Finance 7, 77–91 (1952)
13. Ruan, N., Sun, X.L.: An exac algo i hm o cos minimiza ion in se ies eliabil-
i y sys ems wi h mul iple componen choices. Appl. Ma h. Compu . 181, 732–41
(2006)
14. Tayu , S.R., Thomas, R.R., 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 h. P og am. Se . A
69(3), 369–401 (1995). h ps://doi.o g/10.1007/BF01585566
15. Tsai, J.-F., Lin, M.-H., Hu, Y.-C.: Finding mul iple solu ions o gene al in ege
linea p og ams. Eu . J. Ope . Res. 184(2), 802–809 (2008)
16. Li, H.-L., Tsai, J.-F.: A dis ibu ed compu a ion algo i hm o sol ing po olio
p oblems wi h in ege a iables. Eu . J. Ope . Res. 186(2), 882–891 (2008)