An application of integer programming to the decomposition of numerical semigroups

Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. SIAM J. DISCRETE MATH.c 2012 Socie y o Indus ial and Applied Ma hema ics Vol. 26, No. 3, pp. 1210–1237 AN APPLICATION OF INTEGER PROGRAMMING TO THE DECOMPOSITION OF NUMERICAL SEMIGROUPS∗ V´ ICTOR BLANCO†AND JUSTO PUERTO‡ Abs ac . This pape add esses he p oblem o decomposing a nume ical semig oup in o m- i educible nume ical semig oups. The p oblem o iginally s a ed in algeb aic e ms is ansla ed, in oducing he so-called Kunz-coo dina es, o esol e a se ies o se e al disc e e op imiza ion p ob- lems. Fi s , we p o e ha finding a minimal m-i educible decomposi ion is equi alen o sol e a mul iobjec i e linea in ege p oblem. Then, we es a e ha p oblem as he p oblem o finding all he op imal solu ions o a fini e numbe o single objec i e in ege linea p oblems plus a se co e ing p oblem. Finally, we p o e ha he e is a sui able ans o ma ion ha educes he o iginal p oblem o find an op imal solu ion o a compac in ege linea p oblem. This esul ensu es a polynomial ime algo i hm o each gi en mul iplici y m. We ha e implemen ed he diffe en algo i hms and ha e pe o med some compu a ional expe imen s o show he efficiency o ou me hodology. Key wo ds. in ege p og amming, nume ical semig oups, i educibili y, mul iplici y AMS subjec classi ica ions. 90C10, 20M14, 11D75 DOI. 10.1137/110821809 1. In oduc ion. The use o in ege p og amming is commonly ela ed o he o mula ion and esolu ion o combina o ial op imiza ion p oblems in a ious a eas such as loca ion heo y, anspo a ion, o logis ics. In addi ion, al hough less known, i has been ecen ly used o sol e p oblems a ising in commu a i e algeb a. Some o he mos in e es ing p oblems in he field o compu a ional algeb a equi e pe o ming ex ensi e compu a ions o e highly complex algeb aic s uc u es. This obse a ion has led a numbe o esea che s in ha field o be in e es ed in new ools o be applied in hei p oblems. One o hese ools consis s o embedding hose p oblems in o an in ege p og amming o mula ion whe e ools om disc e e op imiza ion can be used o sol e hem in an al e na i e, mo e efficien way. The goal o his pape is o p esen , analyze, and sol e ano he p oblem a ising in commu a i e algeb a using ools om in ege p og amming: he decomposi ion o a nume ical semig oup in o i educible ones. A nume ical semig oup is a subse So Z+(he e Z+deno es he se o non- nega i e in ege s) closed unde addi ion, con aining ze o and such ha Z+ Sis fini e. No e ha he simples nume ical semig oup is Z+. Nume ical semig oups we e fi s conside ed while s udying he se o nonnega i e solu ions o Diophan ine equa ions and hei in es iga ion is closely ela ed o he analysis o monomial cu es (see [20]). Because o hese connec ions wi h algeb aic geome y, some e minology has been expo ed o he heo y o nume ical semig oups, o ins ance, he mul iplici y, he genus, o he embedding dimension o a nume ical semig oup. Fu he de ails abou ∗Recei ed by he edi o s Janua y 21, 2011; accep ed o publica ion (in e ised o m) June 11, 2012; published elec onically Augus 23, 2012. This esea ch has been pa ially suppo ed by Spanish Minis y o Science and Educa ion g an s MTM2007-67433-C02-01, MTM2010-19576-C02-01, and FQM-5849 (Jun a de Andaluc´ıa FEDER). h p://www.siam.o g/jou nals/sidma/26-3/82180.h ml †Depa men o Quan i a i e Me hods o Economics and Business, Uni e sidad de G anada, 18011 G anada, Spain ( blanco@ug .es). This au ho was also suppo ed by Juan de la Cie a g an JCI-2009-03896. ‡IMUS, Uni e sidad de Se illa, 41012 G anada, Spain (pue [email protected]). 1210 Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1211 he heo y o nume ical semig oups can be ound in he ecen monog aph by Rosales and Ga c´ıa-S´anchez [47]. In ecen yea s, he p oblem o decomposing nume ical semig oups in o i educible ones has a ac ed he in e es o he esea ch communi y (see [13, 25, 42, 44, 45]). Recall ha a nume ical semig oup is i educible i i canno be exp essed as an in- e sec ion o wo nume ical semig oups con aining i p ope ly. Fu he mo e, mo e ecen ly a diffe en no ion o i educibili y, he m-i educibili y [10], has appea ed and has s a ed o be analyzed. A nume ical semig oup o mul iplici y mis said o be m-i educible i i canno be exp essed as an in e sec ion o wo nume ical semig oups o mul iplici y mand con aining p ope ly. The ques ion o exis ence o m-i educible decomposi ions has been p o ed in [10]. Ne e heless, i is s ill missing a me hod- ology, diffe en om he almos pu e b u e o ce enume a ion, o find i educible o m-i educible decomposi ions o minimal size. The decomposi ions o nume ical semi- g oups in o i educible ones a e use ul o ob ain, om he knowledge o he simple ones, p ope ies and conclusions o e he o iginal (complex) semig oups. Fo ins ance, i Sis a nume ical semig oup and S=S1∩···∩Snis a decomposi ion o Sin o i e- ducible, impo an in a ian s such as he F obenius numbe o Sa e easie o compu e since F(S)=max iF(Si), and F(Si) has a simplified compu a ion since F(Si)is he unique special gap o Si(see [46]). In his pape , we gi e a me hodology o ob ain such a minimal decomposi ion in o m-i educible nume ical semig oups by using ools bo owed om disc e e op- imiza ion. Fo he sake o eadabili y, we es ic ou sel es o analyzing decompo- si ions in o m-i educible nume ical semig oups. Ou me hodology is applicable o decomposi ions in o s anda d i educible by conside ing ins ead o he mul iplici y he concep o conduc o , ha is, he F obenius numbe plus one. Ne e heless, in he la e case he dimension o he associa ed poly opes is highe since he con- duc o is always g ea e han he mul iplici y. This ac would make he p esen- a ion and he analysis mo e in ica e ye doable. (The in e es ed eade can find in he concluding ema ks some hin s on his subjec .) To his end, we iden i y one- o-one nume ical semig oups wi h he in ege ec o s inside a a ional polyhe- d on (see [41]). Fo he sake o his iden ifica ion, we in oduce he no ion o he Kunz-coo dina es ec o o ansla e he conside ed p oblem in he p oblem o find- ing some in ege op imal solu ions, wi h espec o app op ia e objec i e unc ions, in he Kunz polyhed on ( he one defined by he Kunz-coo dina es ec o s o all he nume ical semig oups wi h a fixed mul iplici y m). Then, he p oblem o enume a - ing he minimal m-i educible nume ical semig oups in ol ed in he decomposi ion is o mula ed as a mul iobjec i e in ege p og am (Theo em 18). We s a e ha sol - ing his p oblem is equi alen o enume a ing he en i e se s o op imal solu ions o a fini e se o single-objec i e in ege p oblems (Theo em 24). The numbe o in e- ge p oblems o be sol ed is bounded abo e by m−1, whe e mis he mul iplici y o he semig oup o be decomposed. Finally, we sol e a se co e ing p oblem o ensu e ha he decomposi ion has he smalles numbe o elemen s (Theo em 27). Al hough his app oach is exac , i s complexi y is a he high and in gene al one canno p o e ha i is polynomial o any gi en mul iplici y m. This obse a ion comes om he ac ha he e a e ela i ely ew exac me hods o sol e gene al mul- iobjec i e in ege and linea p oblems (see [23]) and i is known ha he complexi y o sol ing in gene al his ype o p oblem is #P-ha d. To o e come his difficul y, we in oduce a diffe en machine y ha iden ifies a minimal decomposi ion by sol - ing a compac linea in ege p og am (sec ion 6). This app oach ensu es ha he p oblem o finding a minimal m-i educible decomposi ion is polynomially sol able. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1212 V´ ICTOR BLANCO AND JUSTO PUERTO We emphasize ha we ha e included nume ous examples in his pape , illus a ing and suppo ing he algo i hms. Ou me hods a e also es ed o semig oups wi h a he la ge mul iplici ies, in pa icula wi h mul iplici ies ha GAP [17], unde he package nume icalsgps, which is a s anda d so wa e o making compu a ions wi h nume ical semig oups, is no able o handle, as well as o semig oups o which GAP does no ensu e minimali y. These poin s show he efficiency o he p esen ed me hods. Las bu no leas , we men ion ha a seconda y goal o his pape is o connec wo impo an fields o ma hema ics: op imiza ion and pu e algeb a. In his ega d, al hough we ollow an abs ac poin o iew, his wo k has di ec applica ions, o ins ance, in commu a i e ing heo y. In ac , le Sbe a nume ical semig oup, K afield,andK[[ ]] he ing o o mal powe se ies o e K. I is well known (see, o ins ance, [3]) ha K[[S]] = {s∈Sas s:as∈K}is a sub ing o K[[ ]], called he ing o he semig oup associa ed o S. Then, as a consequence o he esul s in his pape we ha e ha gi en a nume ical semig oup Swe can efficien ly and effec i ely decompose he ing K[[S]], up o la ge sizes, as a minimal in e sec ion o ings wi h he same mul iplici y whe e some o hem a e Go ens ein (see [32]), some o he s a e Kunz (see, e.g., [3, 4]), and o he s a e ings associa ed o nume ical semig oups wi h special simplici y: {x∈N:x≥m}∪{0}and {x∈N:x≥mand x=i}∪{0} o i∈{m+1,...,2m−1}. Fu he mo e, ano he applica ion o he esul s in his pape is o algeb aic geome y. To each poin Po a comple e i educible nonsin- gula cu e Co genus g, he e is associa ed a nume ical semig oup, he Weie ass semig oup, o he polo o de s o he a ional unc ions on Cholomo phic ou side P. (See [24, 28, 29] o u he de ails on his heo y.) The analysis o his semig oup leads o ob aining p ope ies abou many challenging algeb aic cu es which would no be possible o he wise. Ha ing new ools o ob ain i educible ep esen a ions o la ge nume ical semig oups may help in he analysis o mo e complex (highe dimension) algeb aic cu es. Indeed, he Weie ass semig oup may be decomposed in o i educible nume ical semig oups and his way i s analysis would educe o he s udy o simple semig oups. Also, one can find in he li e a u e in e es ing esea ch pape s dealing wi h he applicabili y o nume ical semig oups in au oma a heo y (see [27, 37, 38]). The es o pape is o ganized as ollows. In sec ion 2 we ecall he main defini- ions and esul s needed o his pape o be sel -con ained. Sec ion 3 ansla es he p oblem o finding nume ical semig oups o a gi en mul iplici y in o he p oblem o de ec ing in ege poin s inside a a ional polyhed on, in oducing he no ion o he Kunz-coo dina es ec o . We gi e in sec ion 4 he condi ions, in e ms o he Kunz- coo dina es ec o , o a nume ical semig oup o be an m-i educible o e semig oup. Sec ion 5 o mula es he p oblem o decomposing and minimally (wi h he smalles numbe o m-i educible semig oups in ol ed in he decomposi ion) decomposing in o m-i educible nume ical semig oups as a ma hema ical p og amming p oblem. We gi e an exac and a heu is ic app oach o compu ing such a minimal decomposi ion based on sol ing some in ege p og amming p oblems. In sec ion 6 we p esen a com- pac model o compu e, by sol ing only one in ege p og amming p oblem, a minimal decomposi ion o a nume ical semig oup in o m-i educible nume ical semig oups. In he same sec ion, we also p o e ha his p oblem is polynomially sol able. Sec ion 7 shows some compu a ional es s pe o med o check he efficiency o he p esen ed al- go i hms wi h espec o he cu en implemen a ion in GAP [17]. Finally, in sec ion 8 we d aw some conclusions abou he con ibu ions o his pape and u he esea ch. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1213 2. P elimina ies. Fo he sake o eadabili y, in his sec ion we ecall he main esul s abou nume ical semig oups needed o he pape o be sel -con ained. Le Sbe a nume ical semig oup. We say ha {n1,...,n p}is a sys em o gene - a o s o Si S={p i=1 nixi:xi∈Z+,i =1,...,p}.Wedeno eS=n1,...,n pi {n1,...,n p}is a sys em o gene a o s o S. The leas posi i e in ege belonging o Sis deno ed by m(S) and is called he mul iplici y o S(m(S)=min(S {0})). The la ges in ege no belonging o S is called he F obenius numbe o S,F(S), and i s exis ence is gua an eed by he defini ion o nume ical semig oup. (See [40, 47] o a de ailed analysis o he F obenius numbe o a nume ical semig oup.) Hence, e e y nume ical semig oup is in he o m S={0,n 1,...,n k}∪{n∈Z:n>n k} o some n1,...,n k∈Z+. The ollowing no ions o i educibili y a e ex ensi ely used h oughou his pape . De ini ion 1 (i educibili y and m-i educibili y). •A nume ical semig oup is i educible i i canno be exp essed as an in e sec- ion o wo nume ical semig oups con aining i p ope ly. •A nume ical semig oup o mul iplici y mis m-i educible i i canno be ex- p essed as an in e sec ion o wo nume ical semig oups o mul iplici y mcon- aining i p ope ly. In [10], Blanco and Rosales analyze and cha ac e ize he se o m-i educible nume ical semig oups. No e ha , in pa icula , any i educible nume ical semig oup is m-i educible, while he con e se is no ue. One o he esul s in ha pape is he key o he analysis done h ough his pape and i is s a ed as ollows. P oposi ion 2 (see [10]). Le Sbe a nume ical semig oup o mul iplici y m. Then, he e exis S1,...,S km-i educible nume ical semig oups such ha S=S1∩ ···∩Sk. F om he abo e esul , al hough he decomposi ion o a nume ical semig oup is always possible, one may hink o ob aining he minimal numbe o elemen s in ol ed in he abo e in e sec ion o m-i educible nume ical semig oups. Fo mally, we de- sc ibe wha we unde s and by decomposing and minimally decomposing a nume ical semig oup o mul iplici y min o m-i educible nume ical semig oups. De ini ion 3 (decomposi ion in o m-i educible nume ical semig oups). Le Sbe a nume ical semig oup o mul iplici y m. Decomposing Sin o m-i educible nume ical semig oups consis s o inding a se o m-i educible nume ical semig oups S1,...,S (S)such ha S=S1∩···∩S (S). (This decomposi ion is always possible by P oposi ion 2.) A minimal decomposi ion o Sin o m-i educible nume ical semig oups is a de- composi ion wi h minimum (S)(minimal ca dinali y o he numbe o m-i educible nume ical semig oups in ol ed in he decomposi ion). Obse e ha minimal decomposi ions may no be unique since one can find di - e en decomposi ions o Sin o m-i educible nume ical semig oups wi h he same numbe o semig oups in ol ed. This is he case o S=5,14,22,31 ha is mini- mally decomposed as 5,9,11,13∩5,14,17o 5,8,11,14∩5,14,17. The i educibili y o a nume ical semig oup has been widely s udied in ecen yea s by he compu a ional algeb a communi y. This end is explained by i s ex en- si e use in ela ed a eas such as numbe heo y o algeb aic geome y, whe e nume ical semig oups appea na u ally, as men ioned in he in oduc ion o his pape . This is he case o he alua ion ing, K[[S]], o a nume ical semig oup S,whichiso ype Go ens ein o Kunz when Sis i educible (see [4]). Decomposing a nume ical semi- g oup in o i educible becomes pa icula ly use ul in he case o alua ion ings since Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1214 V´ ICTOR BLANCO AND JUSTO PUERTO i means ha we can decompose any alua ion ing in o ings which a e Go ens ein o Kunz, and hen one can ans o m he analysis o gene al semig oup ings o he case o ings ha a e well known in he li e a u e. Fu he mo e, se e al algo i hms ha e been p oposed o minimally decompose a nume ical semig oup in o i educible ones (see [13, 25, 42, 44, 45], among o he s). Howe e , all a e based on a b u e o ce enume a ion o a la ge se o nume ical semi- g oups. In his pape , we p opose an al e na i e me hod o ob ain a minimal decom- posi ion by ansla ing he algeb aic p oblem o an in ege op imiza ion p oblem. Fo he sake o comple eness, we fi s ecall some o he main esul s ha will be use ul in ou de elopmen . The in e es ed eade is e e ed o [47] o u he de ails. Fo a nume ical semig oup S, he se o gaps o S,G(S), is he se Z+ S( ha is fini e by defini ion o nume ical semig oup). We deno e by g(S) he ca dinali y o ha se , which is usually called he genus o S. Hence, he F obenius numbe o S, F(S), is he la ges in ege belonging o G(S)(o −1i S=Z+). Le Sbe a nume ical semig oup o mul iplici y m. To decompose Sin o m- i educible nume ical semig oups, we fi s need o know how o iden i y hose m- i educible nume ical semig oups. In [10] i is p o ed ha Sis m-i educible i and only i i is maximal (wi h espec o he inclusion o de ) in he se o nume ical semig oups o mul iplici y mand F obenius numbe F(S). In [44] i is p o ed ha a nume ical semig oup Sis i educible i and only i g(S)=F(S)+1 2. The ollowing wo esul s ha appea in [10] allow us o check he m-i educibili y o a nume ical semig oup by analyzing i s genus and i s F obenius numbe . P oposi ion 4 (see [10]). A nume ical semig oup o mul iplici y m,S,ism- i educible i and only i one o he ollowing condi ions holds: 1. F(S)=g(S)=m−1(being hen S={x∈Z+:x≥m}∪{0}). 2. F(S)∈{m+1,...,2m−1}and g(S)=m(being hen S={x∈Z+:x≥ m, x =F(S)}∪{0}). 3. F(S)>2m(being San i educible nume ical semig oup, so g(S)=F(S)+1 2). Co olla y 5 (see [10]). Le Sbe a nume ical semig oup o mul iplici y m. Then, Sis m-i educible i and only i g(S)∈{m−1,m,F(S)+1 2}. Fo a gi en nume ical semig oup S, ou goal is o find a se o m-i educible nume ical semig oups whose in e sec ion is S. Then, we can es ic he sea ch o hese semig oups o he se o nume ical semig oups con aining S. This se is called he se o o e semig oups o S. De ini ion 6 (o e semig oups). Le Sbe a nume ical semig oup o mul iplici y m.These O(S)o o e semig oups o Sis O(S):={Snume ical semig oup :S⊆S}. The se Om(S)o o e semig oups o So mul iplici y mis Om(S)={S∈O(S): m(S)=m}. Deno e by Jm(S) hese o m-i educible nume ical semig oups in he se Om(S) and by Im(S) he se o minimal elemen s in Jm(S), wi h espec o he inclusion pose . F om he se Im(S) we can ob ain a fi s decomposi ion o Sin o an m- i educible nume ical semig oup, al hough in gene al i may no be minimal (see Example 27 in [10]). Lemma 7. Le Sbe a nume ical semig oup o mul iplici y mand Im(S)= {S1,...,S n}.ThenS=S1∩···∩Snis a decomposi ion o Sin o m-i educible nume ical semig oups. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1215 P oo . The p oo easily ollows om P oposi ion 2, since S=∩S∈Jm(S)S. Clea ly, he abo e basic decomposi ion is no ensu ed o be minimal since i may use edundan elemen s. Rema k 8. No e ha i ˆ Sis a nume ical semig oup o mul iplici y m,byP opo- si ion 4, g( ˆ S)=m−1 i and only i ˆ S={0,m,→} (→deno es ha e e y in ege g ea e han mbelongs o ˆ S). Hence, his m-i educible nume ical semig oup only appea s in i s own decomposi ion and in no one else. This is due o he ac ha ˆ S={0,m,→} is he maximal elemen in he se o nume ical semig oups o mul iplici y m,and henOm(ˆ S)=Im(ˆ S)={ˆ S}(see [10] o u he de ails). F om now on, we assume ha S=ˆ S={0,m,→} since by he abo e ema k, he decomposi ion o ˆ Sis i ial. By P oposi ion 4 and Rema k 8, i S=ˆ S={0,m,→}, i s decomposi ion in o m-i educible nume ical semig oups uses wo ypes o nume ical semig oups: hose ha ha e genus equal o he mul iplici y o Sand hose ha a e i educible (g(S)= F(S)+1 2). To efine he sea ch o he elemen s in Im(S), fi s we in oduce he no ion o special gap. De ini ion 9. Le Sbe a nume ical semig oup. The special gaps o Sa e he elemen s in he ollowing se : SG(S)={h∈G(S):S∪{h}is a nume ical semig oup}, whe e G(S)is he se o gaps o S. We deno e by SGm(S) he special gaps g ea e han m, i.e., SGm(S)={h∈ SG(S):h>m}. In [10], he au ho s p o ed ha Sis m-i educible i and only i #SGm(S)⩽1(#As ands o he ca dinali y o he se A). Mo eo e , SGm(S)=∅ i and only i S={0,m,→} ( he e a e no gaps g ea e han min S). Also, i we know he special gaps o a nume ical semig oup, we can sea ch o i s decomposi ion by using he ollowing esul . P oposi ion 10 (see [10]). Le S, S1,...,S nbe nume ical semig oups o mul i- plici y m.S=S1∩···∩Sni and only i SGm(S)∩(G(S1)∪···∪G(Sn)) = SGm(S). F om he abo e p oposi ion, e en i he minimal m-i educible nume ical semi- g oups, Im(S)={S1,...,S m}, a e known some o hese elemen s may be disca ded when looking o a minimal m-i educible decomposi ion by checking i he e a e e- dundan elemen s in he in e sec ion SGm(S)∩(G(S1)∪···∪G(Sn)). Then, in o de o find minimal decomposi ions, one may choose elemen s in Im(S) ha minimally co e he special gaps o S. To his end, we may sol e a p oblem fixing each o he special gaps o be co e ed. No e ha an uppe bound o he numbe o p oblems o be sol ed is he numbe o special gaps o a nume ical semig oup ha is bounded abo e by m−1 (see [47]). Lemma 11. Le S={0,m,→} be a nume ical semig oup o mul iplici y m,and h∈SGm(S). Then, he e exis s a minimal decomposi ion o Sin o m-i educible nume ical semig oups, S=S1∩···∩Sn, such ha ei he h=F(Si) o some io h∈ Si o some isuch ha he e exis s h∈SGm(Si)wi h F(Si)=h>h. P oo . By P oposi ion 2, he e exis s a minimal decomposi ion o Sin o an m-i educible nume ical semig oup, S=S1∩ ··· ∩ Sk. By applying P oposi ion 10, his decomposi ion mus e i y ha SGm(S)∩(G(S1)∪···∪G(Sn)) = SGm(S). Each special gap h∈SGm(S)mus beinG(Si) o somei=1,...,n. Assume ha h=F(Si)and ha o allh∈SGm(Si) wi h h>h,F(Si)=h. Then, Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1216 V´ ICTOR BLANCO AND JUSTO PUERTO S i=Si∪{F(Si)}is an m-i educible nume ical semig oup such ha SGm(S)∩ (G(S1)∪···G(S i)···∪G(Sn)) = SGm(S). Then, we ha e ob ained a diffe en min- imal decomposi ion. (No e ha i has he same numbe o e ms as he o iginal one.) By epea ing his p ocedu e o each h∈SGm(S) whene e possible, we find a minimal decomposi ion o S ulfilling he condi ions o he lemma. 3. The Kunz-coo dina es ec o . The app oach ollowed in his pape uses ma hema ical p og amming ools o sol e he p oblem o decomposing a nume ical semig oup in o m-i educible nume ical semig oups. Fo he sake o ansla ing he p oblem o a disc e e op imiza ion p oblem, we use an al e na i e encoding o nume - ical semig oups diffe en om he sys em o gene a o s. We iden i y each nume ical semig oup o mul iplici y mwi h a nonnega i e in ege ec o wi h m−1 coo dina es, whe e mis he mul iplici y o he semig oup. To desc ibe his iden ifica ion we fi s need o gi e he no ion o an Ap´e y se o a nume ical semig oup ha was in oduced by Ap´e y in [1]. De ini ion 12. Le Sbe a nume ical semig oup and n∈S {0}.TheAp´e y se o Swi h espec o nis he se Ap(S, n)={s∈S:s−n∈ S}. Howe e , we a e in e es ed in he ollowing cha ac e iza ion o he Ap´e y se (see [47]): Le Sbe a nume ical semig oup and n∈S {0}; hen Ap(S, n)={0= w0,w 1,...,w n−1},whe ewiis he smalles elemen in Scong uen wi h imodulo n o i=1,...,n−1. Mo eo e , he se Ap(S, n) comple ely de e mines S,sinceS=Ap(S, n)∪{n} (see [41]). Ac ually, nis al eady indi ec ly con ained in he Ap´e y se , namely, n=#Ap(S, n)−1. Hence, we can iden i y Swi h i s Ap´e y se wi h espec o n. Besides, he se Ap(S, n) con ains, in gene al, mo e in o ma ion han an a bi- a y sys em o gene a o s o S. Fo ins ance, Selme in [48] gi es he o mulas, g(S)= 1 n(w∈Ap(S,n)w)−n−1 2and F(S)=max(Ap(S, n)) −n. In addi ion, one can es i a nonnega i e in ege sbelongs o Sby checking i ws(mod n)⩽s.No e ha he smalles Ap´e y se is Ap(S, m(S)). We conside a sligh bu use ul modifica ion o he Ap´e y se ha we call he Kunz-coo dina es ec o . De ini ion 13 (Kunz-coo dina es). Le Sbe a nume ical semig oup o mul i- plici y m.I Ap(S, m)={w0=0,w 1,...,w m−1}wi h wicong uen wi h imodulo m, he Kunz-coo dina es ec o o Sis he ec o x∈Zm−1 +wi h componen s xi=wi−i m o i=1,...,m−1. We say ha x∈Zm−1 +is a Kunz-coo dina es ec o (o Kunz-coo dina es, o sho ) i he e exis s a nume ical semig oup whose Kunz-coo dina es ec o is x. F om he Kunz-coo dina es we can eco e he Ap´e y se . I x∈Zm−1 +is he Kunz-coo dina es ec o o S,Ap(S, m)={mxi+i:i=1,...,m−1}∪{0}.Conse- quen ly, Scan be comple ely desc ibed om i s Kunz-coo dina es. The Kunz-coo dina es ec o s ha e been implici ly used in [32] and [41] o cha ac- e ize nume ical semig oups wi h fixed mul iplici y and used in [6] o coun nume ical semig oups wi h a gi en genus. Fu he mo e, i Sis a nume ical semig oup o mul iplici y mand x∈Zm−1 +a e i s Kunz-coo dina es, om Selme ’s o mulas i is easy o compu e i s genus and i s F obenius numbe as ollows: •g(S)=m−1 i=1 xi, •F(S)=max i{m(xi−1) + i}(clea ly, i he maximum is eached in he i h componen , F(S)≡i(mod m)) Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1217 (whe e o a, b, c ∈Z,a≡b(mod c) deno es ha aand ba e cong uen modulo c, ha is, a−bis an in ege mul iple o c). The ollowing esul ha appea s in [41] allows us o manipula e nume ical semi- g oups o mul iplici y mas in ege poin s inside a polyhed on. Theo em 14 (Theo em 11 in [41]). Each nume ical semig oup is one- o-one iden i ied wi h i s Kunz-coo dina es. Fu he mo e, he Kunz-coo dina es ec o s o he se o nume ical semig oups o mul iplici y mis he se o solu ions o he ollowing sys em o diophan ine inequali ies: xi⩾1 o all i∈{1,...,m−1}, xi+xj−xi+j⩾0 o all 1⩽i⩽j⩽m−1,i+j⩽m−1, xi+xj−xi+j−m⩾−1 o all 1⩽i⩽j⩽m−1,i+j>m, xi∈Z+ o all i∈{1,...,m−1}. The polyhed on defined by he abo e sys em o inequali ies is usually called he Kunz polyhed on. F om Theo em 14 and Selme o mulas, we can iden i y all he nume ical semi- g oups (in e ms o hei Kunz-coo dina es ec o ) o mul iplici y m,genusg,and F obenius numbe Fwi h he solu ions o his sys em o diophan ine inequali ies: xi⩾1 o all i∈{1,...,m−1}, xi+xj−xi+j⩾0 o all 1 ⩽i⩽j⩽m−1, i+j⩽m−1, xi+xj−xi+j−m⩾−1 o all 1 ⩽i⩽j⩽m−1, i+j>m, m−1  i=1 xi=g, F=max i{m(xi−1) + i}−m, xi∈Z+ o all i∈{1,...,m−1}. F om he abo e o mula ion and Co olla y 5, he se o m-i educible nume ical semig oups is comple ely de e mined by he solu ions o he ollowing diophan ine sys em o inequali ies and equa ions, which is ob ained fixing he alue o he genus: (3.1) xi⩾1 o all i∈{1,...,m−1}, xi+xj−xi+j⩾0 o all 1 ⩽i⩽j⩽m−1, i+j⩽m−1, xi+xj−xi+j−m⩾−1 o all 1 ⩽i⩽j⩽m−1, i+j>m, m−1  i=1 xi∈{m−1,m,maxi{m(xi−1) + i}}, xi∈Z+ o all i∈{1,...,m−1}. No e ha he abo e sys em is no a s anda d sys em o diophan ine inequali ies since (3.1) is equi alen o sol ing h ee sys ems o diophan ine equa ions/inequali ies. Once he m-i educible nume ical semig oups a e cha ac e ized in e ms o he Kunz-coo dina es ec o s, in o de o cha ac e ize he minimal m-i educible decom- posi ions o a nume ical semig oup Swi h mul iplici y m, we need o de e mine he s uc u e o i s o e semig oups. Obse e ha hose semig oups a e he fi s candida es o appea in he decomposi ion o S. The ollowing esul cha ac e izes he se o o e semig oups o a nume ical semi- g oup in e ms o i s Kunz-coo dina es ec o . P oposi ion 15. Le Sbe a nume ical semig oup o mul iplici y mand x∈ Zm−1 +i s Kunz-coo dina es. Then, he se o Kunz-coo dina es ec o s o o e semi- Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1218 V´ ICTOR BLANCO AND JUSTO PUERTO g oups o So mul iplici y mis (3.2) Um(x)={x∈Zm−1 +:xis a Kunz-coo dina es ec o and x≤x}, whe e ≤deno es he componen wise o de in Zm−1. P oo .Le S∈O m(S)andAp(S,m)={0,w  1,...,w  m−1}.Le Ap(S, m)= {0,w 1,...,w m−1}.Thei h elemen in he Ap´e y se is cha ac e ized as being he minimum elemen in he semig oup ha is cong uen wi h imodulo m.Thus,w i⩽ wi o all i=1,...,m −1sinceS⊆S.Thenx i=w i−i m⩽wi−i m=xi o all i=1,...,m−1. Hence, x≤x. Fo he sake o eadabili y, we shall e e o he se Um(x) in oduced in (3.2) as he se o unde coo dina es o x. I is clea om P oposi ion 15 ha i xis he Kunz-coo dina es ec o o a nume ical semig oup S, he o e semig oups o S(see Defini ion 6) can be one- o-one iden ified wi h he unde coo dina es o i s Kunz- coo dina es ec o . Fo ease o p esen a ion, we iden i y a nume ical semig oup o mul iplici y mwi h an in ege ec o wi h m−1 coo dina es, i s Kunz-coo dina es. All he no ions p e i- ously gi en o nume ical semig oups a e adap ed con enien ly by using he ollowing no a ion. I Sis a nume ical semig oup and x∈Zm−1is i s Kunz-coo dina es ec o , we w i e •m(x)=m(S)=m(mul iplici y o x); •F(x)=F(S) (F obenius numbe ); •G(x)=G(S)={n∈Z:mxn(mod m)+n(mod m)>n}(gaps o x); •g(x)=g(S)(genuso x); •SG(x)=SG(S) (special gaps o x); •SGm(x)=SG m(S) (special gaps o xg ea e han m); •U m(x)={x∈Zm−1:xis a Kunz-coo dina es ec o and x≤x}(unde - coo dina es o x); obse e ha Om(S)={{0}∪{mx i+i} :x∈U m(x)}; •Ap(x)=Ap(S, m)={0}∪{mxi+i:i=1,...,m−1}(Ap´e y se o x). No e ha all he abo e indices and se s can be compu ed by using only he Kunz- coo dina es ec o o he semig oup. Recall ha we ha e assumed wi hou loss o gene ali y ha S={0,m,→}.In e ms o he Kunz-coo dina es, his assump ion is equi alen o saying ha x= (1,...,1) ∈Zm−1 +(o m−1 i=1 xi⩾m). By Co olla y 5 we say ha a Kunz-coo dina es ec o x∈Zm−1 +is m-i educible i g(x)∈{m, m −1,F(x)+1 2}. Fu he mo e, we say ha xis i educible i g(x)= F(x)+1 2. Hence, e e y i educible Kunz-coo dina es ec o in Zm−1 +is m-i educible, bu he con e se is no ue in gene al. We also say ha a se o Kunz-coo dina es ec o s, D={x1,...,x k}⊆Zm−1 +, is a decomposi ion o x∈Zm−1 +in o m-i educible Kunz-coo dina es ec o s i he semig oups associa ed wi h he elemen s in Dgi e a decomposi ion in o m-i educible nume ical semig oups o he semig oup iden ified wi h x. Equi alen ly, by P oposi- ion 10, Dis a decomposi ion o x∈Zm−1 +in o m-i educible Kunz-coo dina es ec o s i xiis an m-i educible Kunz-coo dina es ec o and SGm(x)=SG m(x)∩ G(x1)∪···∪G(xk). Then, a minimal decomposi ion x∈Zm−1 +in o m-i educible Kunz-coo dina es is a decomposi ion in o m-i educible Kunz-coo dina es, D={x1,...,x k}⊆Zm−1 +, wi h minimum ca dinali y. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1225 P oo .Le h∈SG(x). By Lemma 21, e e y nondomina ed solu ions o MIPm(x, h), y, induces a m-i educible unde coo dina e o x,namely,x−y, wi h F(x−y)=h.By P oposi ion 4, e e y m-i educible Kunz-coo dina es ec o has ei he genus m−1 ( his case has been al eady disca ded), m,o F obenius numbe +1 2.Fu he mo e, P oposi ion 4 also s a es ha i he genus is m, hen he F obenius numbe is smalle han 2mand g ea e han 2mo he wise. Hence, i h<2mand x−yis an m- i educible unde coo dina e o x he genus, g(x−y)=m−1 i=1 xi−m−1 i=1 yi,ism, and by (4.4), y=x−1−ej o some j.Nex ,sinceF(x−y)=h, we conclude ha j=k(h)and henyk(h)=xk(h)−2. Tha p o es ha i h<2m,ymus be a solu ion o IPm m(x, h). Assume now ha h>2m. By Lemma 21, we only need o sol e he mul iobjec i e p oblems (MIPm k(x)) wi h k=k(h). In addi ion, Rema k 22 p o es ha any solu ion o (MIPm k(x)) has minimum o e all sum o i s coo dina es o e Pm k(h)(x)∩{y∈Zm−1: yk(h)=0}. Hence, any nondomina ed solu ion is an op imal solu ion o some o he linea (single-objec i e) in ege p og ams abo e. Fu he mo e, assume ha y∗∈Zm−1 +is an op imal solu ion o (IPm(x, h)) o (IPm m(x, h)). I y∗we e no a nondomina ed solu ion o (MIPm(x, h)) ano he easible solu ion, y,o (MIP m(x, h)) would exis (and consequen ly ei he in Pm k(h)(x)o in Pm m(x)) such ha y≤y∗. Then, m−1 i=1 yi≤m−1 i=1 y∗ i.Nex ,sincey∗is an op imal solu ion o (IPm(x, h)) o (IPm m(x, h)),weha e ha m−1 i=1 yi=m−1 i=1 y∗ i. Hence, y=y∗since y,y∗∈Zm−1 +. Finally, we a e looking o solu ions, y, wi h he minimum diffe ence o gaps wi h x, so minimizing iyi. The e o e, o ou pu pose i is enough o minimize he sum o he componen s o y,as o mula edin(IP m(x, h)) and (IPm m(x, h)). No e ha i (IPm m(x, h)) is easible, i has a unique easible solu ion, namely, y=x−1−ek(h)(see (4.4)). Fu he mo e, his p oblem is easible i and only i k(h)=h−msince unde his condi ion h=2m+k(h)−m, he F obenius numbe . Ac ually, in his case, i (IPm(x, h)) has a solu ion, y,i mus alsobe hesolu ion o (IPm m(x, h)). This ac is s a ed in he ollowing heo em. Theo em 25. Le x∈Zm−1 +be a Kunz-coo dina es ec o h∈SGm(x)and y1 and y2op imal solu ions o p oblems (IPm(x, h)) and (IPm m(x, h)), espec i ely. Then, y1=y2. P oo .Weha e wom-i educible unde coo dina es o x,x1=x−y1and x2= x−y2.x1is an i educible Kunz-coo dina es ec o wi h F obenius numbe h.x2is a Kunz-coo dina es ec o wi h F obenius numbe hand genus m. Since he i educible Kunz-coo dina es a e hose wi h maximal genus when fixing he F obenius numbe and he maximum genus in his case is m, heny1=y2because in bo h p oblems we a e minimizing he sum o y. The ollowing esul shows ha he op imal alue o (IPm(x, h)) is known a p io i. Lemma 26. Le ybe an op imal solu ion o (IPm(x, h)).Then,  i yi= m−1  i=1 xi−h+1 2. P oo . Clea ly, op imal solu ions mus sa is y cons ain (4.2). Then, he esul ollows om Lemma 21. Le x∈Zm−1be a Kunz-coo dina es ec o . Once a decomposi ion is chosen, in o de o selec a minimal decomposi ion we use a se co e ing o mula ion o choose Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1226 V´ ICTOR BLANCO AND JUSTO PUERTO among he o e all se o minimal m-i educible unde coo dina es o xa minimal num- be o elemen s o he decomposi ion. Le SGm(x)={h1,...,h s}and Di={xi1,...,x ipi}be he se o he max- imal Kunz-coo dina es ec o s o m-i educible unde coo dina es o xwhen fixing he special gap hi(op imal solu ions o IPm(x, hi)) o i=1,...,s.Wedeno eby D=D1∪···∪Ds he se o m-i educible Kunz-coo dina es ec o s candida es o be in ol ed in he minimal decomposi ion o x. We conside he se o decision a iables zij =1i xijis selec ed o he minimal decomposi ion, 0o he wise o i=1,...,s,j=1,...,p i. We o mula e he p oblem o selec ing a minimal numbe o m-i educible un- de coo dina es ec o s o x ha decompose xin o m-i educible Kunz-coo dina es as (SCm(D)) min s  i=1 pi  j=1 zij s. .  i,j/mxij k(h)+k(h)≥h+1 zij ≥1 o all h∈SGm(x). The co e ing cons ain ensu es ha o each special gap o x he e is an elemen in {xi1,...,x ip1,...,x s1,...,x sps}such ha his a gap o i s co esponding semi- g oup. Minimizing he o e all sum we find he minimum numbe o Kunz-coo dina es ulfilling his equi emen . No e ha when sol ing (SCm(D)) a mos one elemen in Diis choosen o each i=1,...,s. In he ollowing, we gi e a p ocedu e o decompose a nume ical semig oup So mul iplici y m(a e iden ifica ion wi h i s Kunz-coo dina es ec o ) in o m-i educible nume ical semig oups. This p ocess is desc ibed in Algo i hm 2. In ha implemen- a ion we also conside wo i ial cases: (1) when he numbe o special gaps g ea e han he mul iplici y is 1, being hen he semig oup m-i educible; and (2) when he numbe o his special gaps is 2, whe e he decomposi ion is gi en by bo h solu ions o he wo unique in ege p og amming p oblems, and no disca ding p ocess is needed. As a consequence o all he abo e commen s and esul s we s a e he co ec ness o ou app oach. Theo em 27. Algo i hm 2compu es, exac ly, a minimal decomposi ion in o m-i educible Kunz-coo dina es ec o o a Kunz-coo dina es ec o x∈Zm−1 +.Fu - he mo e, he en i e se o op imal solu ions o (SCm(D)) cha ac e izes he se o minimal decomposi ions. Algo i hm 2 compu es a minimal decomposi ion o a Kunz-coo dina es ec o , x∈Zm−1 +, by enume a ing he whole se o op imal solu ions o (IPm(x, h)). Howe e , his ask is no easy since i mainly consis s o enume a ing he se o e ices o he poly ope defining he easible egion o an in ege p og amming p oblem ( he con ex hull o he in ege poin s inside he polyhed on), which is ha d o compu e (see, e.g., [2]). In wha ollows we p opose a heu is ic app oach o ob ain a “sho ” decomposi ion in o m-i educibles by choosing an op imal solu ion o (IPm(x, h)) ins ead o enume a ing all o hem. One may choose any o hem, bu we can also sligh ly modi y he in ege p og amming model o ob ain a good solu ion. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1227 Algo i hm 2. Decomposi ion in o m-i educible nume ical semig oups. Inpu : A nume ical semig oup So mul iplici y m. Compu e he Kunz-coo dina es ec o o S:x∈Zm−1 +. (Compu ing he Ap´e y se .) D={}. Compu e SGm(x). i #SGm(x)=1 hen DmIR = {x} else o hi∈SGm(x)do i hi<2m hen Se D:= D∪{1+e k(h)}. else o each op imal solu ion o (IPm(x, h)),ˆyido Se D:= D∪{x−ˆyi}. Le D={x11,...,x 1i1,...,x s1,...,x sis}. Le z∗be an op imal solu ion o (SCm(D)). Se DmIR = {xij ∈D:z∗ ij =1} Ou pu :DmIRNS={{m}∪{mx i+i:i=1,...,m−1} :x∈DmIR}. We conside he se o decision a iables wi=1i hi∈G(x−y), 0o he wise o i=1,...,n, and SGm(x)={h1,...,h n}. Fo a fixed h∈SGm(x), wi= 1 ep esen s ha hiis co e ed by he solu ion x−y and hen ha i can be disca ded o ob ain a minimal decomposi ion. Then, o ensu e ha we maximize he numbe o elemen s ha can be disca ded in he p e ious decomposi ion, we o mula e he p oblem as (IPm k(x, h)) max #SGm(x)  i=1 wi s. . y∈Pm k(h)(x), yk(h)=0, m(xk(ˆ hi)−yk(ˆ hi))+k( ˆ hi)−ˆ hi−1+M(1 −wi)≥0 o all ˆ hi∈SGm(x), whe e M0. Obse e ha he big-Mcons ain m(xk(ˆ hi)−yk(ˆ hi))+k(ˆ hi)−ˆ hi−1+M(1−wi)≥0 ensu es ha i ˆ hi∈ G(x−y) (equi alen ly, m(xk(ˆ hi)−yk(ˆ hi))+k( ˆ hi)<ˆ hi+ 1), hen wi=0. O he wise,wicould be 0 o 1, bu since we a e maximizing, wi=1. The op imal alue o his in ege p oblem is hen he numbe o nume ical semi- g oups in he decomposi ion ha can be disca ded wi h his choice. A pseudocode o he p oposed app oxima ed scheme o ob aining a “sho ” decomposi ion o a Kunz-coo dina es ec o x∈Zm−1 +in o m-i educible Kunz- coo dina es ec o s by sol ing (IPm k(x, h)) is shown in Algo i hm 3. When unning Algo i hm 3 we ob ain an op imal solu ion o he p oblem, and hen mo ing h ough all he special gaps we ob ain a decomposi ion in o m-i educible Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1228 V´ ICTOR BLANCO AND JUSTO PUERTO Algo i hm 3. Decomposi ion in o m-i educible nume ical semig oups. Inpu : A nume ical semig oup So mul iplici y m. Compu e he Kunz-coo dina es ec o o S:x∈Zm−1 +. (Compu ing he Ap´e y se .) D={}. Compu e SGm(x). i #SGm(x)=1 hen DmIR = {x} else o hi∈SGm(x)do i hi<2m hen Se D:= D∪{1+e k(h)}. else Le ˆybe an op imal solu ion o (IPm(x, h)). Se D:= D∪{x−ˆy}. Le D={x1,...,x s}. i #SGm(x)=2 hen DmIR = D else Selec a minimal decomposi ion om D. Le z∗be an op imal solu ion o (SCm(D)). Se DmIR = {xj∈D:z∗ j=1} Ou pu :DmIRNS={{m}∪{mx i+i:i=1,...,m−1} :x∈DmIR}. Kunz-coo dina es. Wi h he ollowing example we show how Algo i hms 2 and 3 un o a gi en nume ical semig oup. Example 28. Le S=5,11,12,18. The mul iplici y o Sis m= 5, i s Kunz- coo dina es ec o is x=(2,2,3,4), and SG5(S)={6,13,19}. Fi s , we sol e one in ege p oblem o each special gap: •h=6.Sinceh<2×5 = 10, he in ege p oblem o sol e is P5 5(x, 6) and hen D1={x11 =(2,1,1,1)}. •h= 13. In his case h>2×5 = 10 and h= 3 (mod 5), so he in e- ge p oblem in his case is P5 3(x, 13). The whole se o op imal solu ions is {(1,0,0,3),(0,1,0,3)},soD2={x21 =(2,1,3,1),x 22 =(1,2,3,1)}. •h= 19. Since h=19>2×5 = 10 and h= 4 (mod 5), he p oblem is now P5 4(x, 19). The se o op imal solu ions is {(1,0,0,0),(0,0,0,1)},and hen D3={x31 =(1,2,3,4),x 32 =(2,2,2,4)}. The abo e fi e Kunz-coo dina es ec o s gi e a decomposi ion in o e semig oups o S. To ob ain a minimal decomposi ion we mus sol e he associa ed se co e ing p oblem. Sol ing SC5(D) we ob ain ha z11 =z31 = 1 and all o he a iables a e se o ze o, being hen he minimal decomposi ion gi en by x11 and x31, i.e., a minimal decomposi ion in o 5-i educible Kunz-coo dina es is gi en by {(2,1,1,1),(1,2,3,4)}. T ansla ing o nume ical semig oups, S=5,11,7,8,9∩5,6,12,18,24. When sol ing (IPm k(x, h)), we ob ain he same decomposi ion. Howe e , he decomposi ion ob ained wi h Algo i hm 3 may no be minimal. The ollowing example illus a es his ac . Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1229 Example 29. Le S=12,17,18,23,26,28,33,39be a nume ical semig oup o mul iplici y 12. I s Kunz-coo dina es ec o is x=(4,2,3,2,1,1,3,3,2,2,1) and SG12(x)={21,22,27,31,32,37}. Then, six in ege p oblems mus be sol ed: IP12 12(x, 21), IP12 12(x, 22), IP12 3(x, 27), IP12 7(x, 31), IP12 8(x, 32), and IP12 1(x, 37). By sol ing hese p oblems wi h Xp ess-Mosel 7.0 [50] we ob ain he ollowing op imal solu ions: x− y∈{(1,1,1,1,1,1,1,1,2,1,1) ,(1,1,1,1,1,1,1,1,1,2,1),(1,2,3,1,1,1,1,1,1,1,1), (2,2,1,2,1,1,3,1,1,1,1),(1,2,2,2,1,1,2,3,1,1,1),(4,2,1,2,1,1,2,2,1,2,1)}. The ansla ions o he abo e coo dina es in e ms o nume ical semig oups a e {12,13,14,15,16,17,18,19,20,22,23,33,12,13,14,15,16,17,18,19,20,21,34,23, 12,13,16,17,18,19,20,21,22,23,12,15,17,18,20,21,22,23,25,26,28,43, 12,13,17,18,21,22,23,26,27,28,31,44,12,15,17,18,21,23,26,28,31,32,34,49}. Now, by sol ing p oblem (SCm(D)), 12,13,14,15,16,17,18,19,20,21,34,23is disca ded. Then, he decomposi ion using ou me hodology is gi en by fi e 12- i educible nume ical semig oups: S=12,13,14,15,16,17,18,19,20,22,23,33∩12,13,16,17,18,19,20,21,22,23∩ 12,15,17,18,20,21,22,23,25,26,28,43∩12,13,17,18,21,22,23,26,27,28,31,44∩ 12,15,17,18,21,23,26,28,32,34. Howe e , his decomposi ion is no minimal since S=12,13,16,17,18,19,20,21, 22,23,26,39∩12,15,17,18,20,21,22,23,25,26,28,43∩12,13,17,18,21,22,23,26, 27,28,31,44∩12,15,16,17,18,23,26,31,32,33,34,49is a decomposi ion in o m- i educible nume ical semig oups using a smalle numbe o e ms. In Example 29 we ound ha by applying he desc ibed me hodology we go a decomposi ion which is no minimal. This si ua ion is due o he ac ha among he whole se o op imal solu ions o (IPm(x, h)), Algo i hm 3 chooses a pa icula one, bu depending on ha choice, diffe en numbe s o elemen s can be disca ded om ha decomposi ion o ob ain he minimal one. To a oid his ac , we need o conside a compac model ha connec s all he possible elemen s in he decomposi ion and ha selec s, among all o hem, he smalles numbe o solu ions o decompose a Kunz-coo dina es ec o . 6. A compac model o minimally decomposing in o m-i educible Kunz-coo dina es ec o s. In hesec ionabo ewedesc ibedanexac anda heu is ic p ocedu e o compu e a minimal decomposi ion o a Kunz-coo dina es ec- o x∈Zm−1in o m-i educible Kunz-coo dina es. To ob ain solu ions by using ha exac p ocedu e we need o enume a e he solu ions o a knapsack ype diophan ine equa ion included in he Kunz polyhed on. Once we ha e hose solu ions, a se co - e ing p oblem mus be sol ed o ob ain a minimal decomposi ion. By using ha model, he comple e enume a ion canno be a oided since, by choosing one solu ion, one may ob ain nonminimal decomposi ions when sol ing he se co e ing model (see Example 29). We p esen he e a compac model o decompose any Kunz-coo dina es ec o , x∈Zm−1 +, me ging in a single in ege linea p og amming p oblem all he subp oblems conside ed in he p e ious sec ion o ensu e minimal decomposi ions. Mo eo e , his app oach will allow us o p o e a polynomiali y esul o he p oblem o decomposing in o m-i educible nume ical semig oups. Le SGm(x)={h1,...,h s}. We conside he ollowing amilies o decision a iables o he new model: •yl i∈Z+ o all l=1,...,s and i=1,...,m −1 such ha x−ylis an m-i educible unde coo dina e o xwi h F obenius numbe hl. •wl∈{0,1} o all l=1,...,s, ep esen ing i x−yhlis chosen (1) o no (0) o a minimal decomposi ion in o m-i educible coo dina es o x. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1230 V´ ICTOR BLANCO AND JUSTO PUERTO •zl k∈{0,1} ha measu es i hkis a gap o x−yl(1) o no (0) o all l, k =1,...,s.No e ha hk∈G(x−yl) i and only i yl k(hk)=0. In addi ion, ake M⩾max{xk(hl):l=1,...,s}. Then, he p oposed model, CIPm(x), is desc ibed as ollows: (CIPm(x)) min s  l=1 wl s. . yl i⩽xi−1 o all i=1,...,m−1 o all l=1,...,s,(6.1) yl i+yl j−yl i+j⩽xi+xj−xi+ji i+j<m o all l=1,...,s,(6.2) yl i+yl j−yl i+j−m⩽xi+xj−xi+j−m+1 i i+j>m o all l=1,...,s,(6.3) m−1  i=1 yl i=m−1  i=1 xi−hl+1 2wl o all l=1,...,s wi h hl>2m,(6.4) m−1  i=1 yl i=m−1  i=1 xi−mwl o all l=1,...,s wi h hl<2m,(6.5) yl k(hl)=0 o alll=1,...,s,(6.6)  l zl k(hk)⩾1 o all k=1,...,s,(6.7) zl k(hk)⩾1−yl k(hk)−M(1 −wl) o all l, k =1,...,s,(6.8) yl k(hk)⩽M(1 −zl k(hk)) o all k=1,...,s,(6.9) zl k(hk)⩽wl o all l, k =1,...,s,(6.10) yl i∈Z+, o all i=1,...,m−1, l=1,...,s,(6.11) wl∈{0,1}, o all l=1,...,s,(6.12) zl j∈{0,1} o all l=1,...,s,j=1,...,m−1.(6.13) The componen s o any op imal solu ions, y∗, o he abo e p oblem in he se {y∗l:y∗l=0,l =1,...,s}={y∗l1,...,y∗lp}gi e a minimal decomposi ion o xin o m-i educible Kunz-coo dina es ec o s as {x−y∗lj:j=1,...,s}. No e also ha F(x−y∗lj)=hlj. Cons ain s (6.1)–(6.3) ensu e ha x−ylis an unde coo dina e o x.Equa ions (6.4) and (6.5) gi e condi ions ela ed o he genus and he F obenius numbe o hose Kunz-coo dina es ec o s (Co olla y 5) associa ed o he choice o yl(wl= 1). Cons ain (6.6) ensu es ha hlis a gap o x−yland (6.7) ha he e is a leas one elemen in he decomposi ion ha ing hlamong i s gaps. Cons ain s (6.8)– (6.10) con ol ha he a iables zl ka e well defined. Equa ions (6.11)–(6.13) a e he in eg ali y and bina y cons ain s o he a iables. The op imal alue o (CIPm(x)) gi es he numbe o Kunz-coo dina es in ol ed in a minimal decomposi ion o xin o m-i educible Kunz-coo dina es ec o s. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1231 The solu ion o (CIPm(x)) gi es exac ly a minimal decomposi ion o xin o m- i educible Kunz-coo dina es (o m-i educible nume ical semig oups). Howe e , i is ha de o sol e han he p oblems in Algo i hm 3 since i has many mo e a iables. (By using Algo i hm 3, we need o sol e a mos m−1 p oblems wi h m−1 a iables and a se co e ing p oblem wi h a mos m−1 a iables while (CIPm(x)) has 2(m−1)2+ (m−1) in ege /bina y a iables.) In he compu a ional expe imen s (see sec ion 6) we ha e obse ed ha he solu ions when unning Algo i hm 3 a e no a om minimali y and i is as e han sol ing (CIPm(x)). Rema k 30 (m-symme y and m-pseudosymme y). Blanco and Rosales [10] also defined he no ion o m-symme y and m-pseudosymme y o a nume ical semig oup o mul iplici y m, ex ending he p e ious no ions o symme y and pseudosymme y (see [47]). A nume ical semig oup So mul iplici y mis m-symme ic i Sis m- i educible and F(S) is odd. On he o he hand, Sis m-pseudosymme ic i Sis m-i educible and F(S)ise en. Rosales and B anco analyzed in [42] and [43] hose nume ical semig oups ha can be decomposed in o symme ic nume ical semig oups. (In his case he semig oup is called he ISY-semig oup.) Ano he in e es ing applica ion o ou me hodology is o compu e a decomposi ion o Sin o m-symme ic nume ical semig oups. (Following he no a ion in [43], Sis an ISYM-semig oup.) This ollows by fixing in (CIPm(x)) ha he m-i educible nume ical o e semig oups o Sassocia ed o e en special gaps do no appea in he decomposi ion (yl i=0 o alli=1,...,m−1i lis e en). Thus, he m-i educible nume ical semig oups whose F obenius numbe s a e each o he odd special gaps mus co e he whole se o gaps. I his p oblem is easible, i s solu ion gi es a minimal decomposi ion in o m-symme ic nume ical semig oups. Howe e , in his case we canno ensu e ha i is always possible o decompose in o m-symme ic nume ical semig oups ( o ins ance, a nume ical semig oup wi h e en F obenius numbe is no decomposable in his way). Then, i p oblem (CIPm(x)) is in easible, he semig oup canno be exp essed as an in e sec ion o m-symme ic nume ical semig oups. In addi ion, [43] analyzes he se o ISYG-semig oups ( hose ha can be exp essed as an in e sec ion o symme ic semig oups wi h he same F obenius numbe ). We could in oduce he no ion o ISYGM-semig oups ( hose ha can be exp essed as an in e sec ion o symme ic nume ical semig oups wi h he same F obenius numbe and mul iplici y). This case can also be handled wi h ou app oach by fixing he F obenius numbe o he semig oup in (CIPm(x)). A simila me hodology can be applied o compu e a decomposi ion in o m- pseudosymme ic nume ical semig oups. Rema k 31 (compu a ional complexi y). Assume ha mis fixed. (CIPm(x)) hasa mos 2(m−1)2+(m−1) a iables and hen i is sol able in polynomial ime [35]. I is wo h no ing ha he heu is ic app oach also has polynomial ime o e all complexi y. Indeed, o each special gap o x, one in ege p og am is sol ed, IPm(x, h) i h>2mo IPm m(x)i h<2m. Since he numbe o special gaps is bounded abo e by m−1, he complexi y o his s ep is polynomial o fixed mul iplici y and so is polynomial. Once we ha e he solu ions o all he special gaps, he disca ding s ep consis s o sol ing he se co e ing p oblem (SCm(D)) wi h a mos m−1 a iables and so is polynomial in m. On he o he hand, he algo i hm p oposed in [10] o decompose a nume ical semi- g oup So mul iplici y min o m-i educible nume ical semig oups can be ew i en as ollows. Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1232 V´ ICTOR BLANCO AND JUSTO PUERTO x mmmmmmmmmmmmmm (( Q Q Q Q Q Q Q Q Q Q Q Q Q Q x−ek(h1) wwo oo oo oo oo oo o '' O O O O O O O O O O O O ··· x−ek(hk) x−ek(h1)−ek(h 1)··· x−ek(h1)−ek(h k) Fig. 6.1.Ske ch o Gx. Le Gx=(V,E) be a di ec ed g aph whose se o e ices is he se o un- de coo dina es o x,Um(x), and (x1,x 2)∈Ei x2=x1−eh(mod m) o some h∈SGm(x). Figu e 6.1 illus a es how his g aph is buil . In ha figu e we de- no e SGm(x)={h1,...,h k}and SGm(x+e k(h))={h 1,...,h  k}. The algo i hm sea ches o a se o e ices {x1,...,x n}wi h he p ope ies ha #SGm(xi)=1 o all i=1,...,n and ha any o he e ex is domina ed by any o he elemen s in he se . Fu he mo e, Gxis a ee since i does no ha e ci cui s. In [10], a b ead h fi s sea ch o e his ee is p oposed o find he desi ed se . Clea ly, he wo s case complexi y o his me hod is exponen ial e en o fixed mul iplici y. 7. Compu a ional expe imen s. In his sec ion we p esen he esul s o some compu a ional expe imen s designed o analyze he pe o mance o he p oposed al- go i hms. Ou algo i hms ha e been implemen ed in XPRESS-Mosel 7.0 [50], which allows us o sol e he single-objec i e in ege p oblems in ol ed in he decomposi ion in o m-i educible nume ical semig oups by using a b anch-and-bound me hod and nes ing models by calling he lib a y mmjobs. The algo i hms ha e been execu ed on aPCwi hanIn elCo e2Quadp ocesso a 2x2.50GHzand4GBo RAM. The complexi y o he algo i hm depends o he dimension o he space (mul i- plici y), he size o he coefficien s o he cons ain s, and he numbe o special gaps. Then, we andomly gene a ed h ee diffe en ba e ies o nume ical semig oups wi h he ollowing equi emen s: Ba e y I. Nume ical semig oups wi h mul iplici ies anging in [0,25] (di ided in he fi e subin e als (0,5], (5,10], (10,15], (15,20], and (20,25]) wi h gene a o s anging in [2,5000]. The e a e 10 ins ances o each subin e al. Ba e y II. Nume ical semig oups wi h mul iplici ies anging in [10,2000] (di ided in he se en subin e als (10,25], (25,50], (50,100], (100,250], (250,500], (500,1000], and (1000,2000]) wi h gene a o s anging in [2,5000]. The e a e fi e ins ances o each subin e al. Ba e y III. Nume ical semig oups wi h mul iplici ies anging in [25,150] (di ided in he fi e subin e als (25,50],(50,75],(75,100],(100,125], and (125,150]) wi h gene a o s anging in [2,5000] and wi h numbe o special gaps g ea e han he mul iplici y less han o equal o 30. The e a e 10 ins ances o each subin e al. The fi s ba e y o p oblems is designed o compa e he h ee algo i hms: he one implemen ed in GAP, he heu is ic app oach (Algo i hm 3), and he compac model (CIPm(x)). Wi h he second se o p oblems, we check he efficiency o Algo i hm 3 o sol ing la ge ins ances. Finally, wi h he hi d ba e y o p oblems, we compa e he Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1233 Table 7.1 Resul s o he compu a ional expe imen s o Ba e y I. mCM ime Heu ime GAP ime #SG #m-i ed a gap [0,5] 0.001 0.020 0.001 1.5 1.5 0 (5,10] 0.003 0.054 2.3973 2.7 2.3 0 (10, 15] 0.013 0.091 4.1645 4.1 3.4 0.1 (15,20] 0.053 0.081 523.556 5.4 4 0 (20,25] 0.046 0.089 n/a 5.7 4.4 0.1 Table 7.2 Resul s o he compu a ional expe imen s o Ba e y II. mHeu ime #SG #m-i ed (25,50] 0.242 11.8 7.2 (50,100] 1.411 19.6 9.6 (100,250] 168.272 42.4 25.4 (250,500] 1318.475 86.2 47.8 (500,1000] 1056.878 27.2 18.8 (1000,2000] 1895.058 15.2 9.8 Table 7.3 Resul s o he compu a ional expe imen s o Ba e y III. mCM ime Heu ime #SG #m-i ed a gap (25,50] 1.064 0.201 9.3 5.8 0.7 (50,75] 6.981 0.713 13.5 7.1 1.1 (75,100] 58.580 1.819 16.3 9 1 (100,125] 102.999 3.428 15.1 7.1 1.6 (125,150] 144.531 5.752 15.5 8.3 1.3 difficul y o sol ing (CIPm(x)) and he heu is ic algo i hm. (No e ha his difficul y is mainly due o he numbe o special gaps since i inc eases he numbe o a iables.) The e o e, we gene a e nume ical semig oups wi h e y la ge mul iplici ies bu whe e he numbe o special gaps is bounded abo e by 30. We used ecu si ely he unc ion RandomLis Fo NS o GAP[17] un il we ound he lis o in ege s defining he semig oup wi h he abo e equi emen s. The imple- men a ion done o decomposing in GAP (wi h he package nume icalsgps)in om- i educible nume ical semig oups is an adap a ion o he unc ion DecomposeIn oI e- ducibles o decomposing in o s anda d i educible nume ical semig oups. The esul s o hese expe imen s a e summa ized in Tables 7.1–7.3. In hese ables, mindica es he ange o he mul iplici y, CM ime and Heu ime he a e age imes in seconds consumed by sol ing (CIPm(x)) and Algo i hm 3, espec i ely, in Xp ess-Mosel,GAP ime in o ms on he a e age ime consumed by GAP o he same ask, #SG is he a e age numbe o special gaps o he p oblems, and #m-i ed is he a e age numbe o semig oups in ol ed in a minimal decomposi ion. The column a gap is he a e age diffe ence be ween he numbe o nume ical semig oups used in he heu is ic decomposi ion and he numbe o nume ical semig oups used in he minimal decomposi ion compu ed by sol ing (CIPm(x)). No e ha e en o ins ances o Ba e y I, GAP was no able o sol e any o he 10 ins ances when he mul iplici y anges in (20,25]. We ha e also obse ed ha he algo i hm implemen ed in GAP does no ensu e minimal decomposi ions in o m-i educible nume ical semig oups. Fo ins ance, con- side he semig oup S=15,17,19,48,52,59,73 ha decomposes in GAP in o six Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed. 1234 V´ ICTOR BLANCO AND JUSTO PUERTO 15-i educible nume ical semig oups, while ou me hodology ob ains a decomposi ion in o fi e 15-i educible nume ical semig oups. The eason GAP ails is closely e- la ed o he ac ha p e en s ensu ing, in all cases, ha Algo i hm 3 ge s minimal solu ions. F om ou compu a ional expe imen s we obse e ha excep o he ins ances wi h m∈[0,5], whe e he algo i hm in GAP akes almos he same ime o compu e he decomposi ions, ou me hodology sol es he p oblems as e han GAP. Ac ually, in his ba e y sol ing he p oblem (CIPm(x)) is he bes way o compu e such a decomposi ion. This is due o he minimum compu a ional ime consumed by Xp ess- Mosel o load he p oblems in ol ed in Algo i hm 3. Bo h he exac algo i hm based on sol ing (CIPm(x)) and he heu is ic app oach a e able o compu e, in easonable CPU imes, minimal decomposi ions in o m- i educible nume ical semig oups o mul iplici ies up o 150, while he p ocedu e implemen ed in GAP is no able o sol e p oblems wi h mul iplici ies anging e en in (20,25]. Fu he mo e, al hough he de aul b anch-and-bound algo i hm is no able o sol e (CIPm(x)) o la ge mul iplici ies, he heu is ic app oach sol es p oblems wi h mul iplici ies up o m= 2000. The heu is ic app oach finds a sho decomposi ion o nume ical semig oups in o m-i educible nume ical semig oups much as e han he exac app oach. Fu he - mo e, he heu is ic app oach eaches a minimal decomposi ion mos o he ime. Fo ins ance, in he fi s ba e y o p oblems, he heu is ic alue does no coincide wi h he exac op imal one in only 2 o he 50 ins ances. Mo eo e , he hi d ba e y o ins ances sa isfies ha in 30% o he cases he minimal decomposi ion coincides wi h he heu is ic sho decomposi ion, in 34% o he cases he diffe ence is only one semi- g oup, in 30% o he cases i is wo semig oups, in 4% ( wo cases) i is h ee, and in only 2% (one ins ance) i is ou . No e ha mos o he compu a ions done by using Algo i hm 3 may be pa al- lelized by sol ing in diffe en co es each o he p oblems (IPm k(x, h)) since hey a e independen . This could imp o e he CPU imes and sizes o he p oblems because mo e han 99% o he ime consumed by his algo i hm is o sol e hose p oblems, while jus a li le pa o he ime is spen sol ing he se co e ing p oblem. On he o he hand, we ha e simply implemen ed he p oposed models in Xp ess- Mosel, wi h he de aul b anch-and-bound me hod. La ge ins ances could be sol ed by applying specific mo e sophis ica ed in ege p og amming algo i hms o sol e each one o he p oblems. 8. Concluding ema ks. We p esen in his pape a new app oach o decom- posing a nume ical semig oup o mul iplici y min o he minimum numbe o m- i educible nume ical semig oups. Ou me hodology is based on ansla ing he p ob- lem o he p oblem o sol ing an in ege p og amming p oblem. Hence, his app oach connec s commu a i e algeb a and disc e e op imiza ion. The ans o ma ion om he algeb aic p oblem o he op imiza ion o mula ion uses he no ion o he Kunz- coo dina es ec o o a nume ical semig oup ha allows us o encode a nume ical semig oup o mul iplici y mas a ec o wi h m−1 nonnega i e in ege coo dina es. Al hough we ha e p esen ed he e a me hod o compu e minimal decomposi ions in o m-i educible nume ical semig oups, a simila idea can be applied o decompose a nume ical semig oup in o (s anda d) i educible ones. No e ha i we do no fix he mul iplici y, we canno use he Ap´e y se wi h espec o he mul iplici y (and consequen ly, we canno use he Kunz-coo dina es ec o defined in his pape ) o en- code all he nume ical semig oups ha may ake pa in he decomposi ion. Howe e , Downloaded 02/25/16 o 150.214.182.169. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php