An application of integer programming to the decomposition of numerical semigroups

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. SIAM J. DISCRETE MATH.c 2012 Society for Industrial and Applied Mathematics Vol. 26, No. 3, pp. 1210–1237 AN APPLICATION OF INTEGER PROGRAMMING TO THE DECOMPOSITION OF NUMERICAL SEMIGROUPS∗ V´ ICTOR BLANCO†AND JUSTO PUERTO‡ Abstract. This paper addresses the problem of decomposing a numerical semigroup into mirreducible numerical semigroups. The problem originally stated in algebraic terms is translated, introducing the so-called Kunz-coordinates, to resolve a series of several discrete optimization problems. First, we prove that finding a minimal m-irreducible decomposition is equivalent to solve a multiobjective linear integer problem. Then, we restate that problem as the problem of finding all the optimal solutions of a finite number of single objective integer linear problems plus a set covering problem. Finally, we prove that there is a suitable transformation that reduces the original problem to find an optimal solution of a compact integer linear problem. This result ensures a polynomial time algorithm for each given multiplicity m. We have implemented the different algorithms and have performed some computational experiments to show the efficiency of our methodology. Key words. integer programming, numerical semigroups, irreducibility, multiplicity AMS subject classifications. 90C10, 20M14, 11D75 DOI. 10.1137/110821809 1. Introduction. The use of integer programming is commonly related to the formulation and resolution of combinatorial optimization problems in various areas such as location theory, transportation, or logistics. In addition, although less known, it has been recently used to solve problems arising in commutative algebra. Some of the most interesting problems in the field of computational algebra require performing extensive computations over highly complex algebraic structures. This observation has led a number of researchers in that field to be interested in new tools to be applied in their problems. One of these tools consists of embedding those problems into an integer programming formulation where tools from discrete optimization can be used to solve them in an alternative, more efficient way. The goal of this paper is to present, analyze, and solve another problem arising in commutative algebra using tools from integer programming: the decomposition of a numerical semigroup into irreducible ones. A numerical semigroup is a subset Sof Z+(here Z+denotes the set of nonnegative integers) closed under addition, containing zero and such that Z+\Sis finite. Note that the simplest numerical semigroup is Z+. Numerical semigroups were first considered while studying the set of nonnegative solutions of Diophantine equations and their investigation is closely related to the analysis of monomial curves (see [20]). Because of these connections with algebraic geometry, some terminology has been exported to the theory of numerical semigroups, for instance, the multiplicity, the genus, or the embedding dimension of a numerical semigroup. Further details about ∗Received by the editors January 21, 2011; accepted for publication (in revised form) June 11, 2012; published electronically August 23, 2012. This research has been partially supported by Spanish Ministry of Science and Education grants MTM2007-67433-C02-01, MTM2010-19576-C02-01, and FQM-5849 (Junta de Andaluc´ıa\FEDER). http://www.siam.org/journals/sidma/26-3/82180.html †Department of Quantitative Methods for Economics and Business, Universidad de Granada, 18011 Granada, Spain ([email protected]). This author was also supported by Juan de la Cierva grant JCI-2009-03896. ‡IMUS, Universidad de Sevilla, 41012 Granada, Spain ([email protected]). 1210 Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1211 the theory of numerical semigroups can be found in the recent monograph by Rosales and Garc´ıa-S´anchez [47]. In recent years, the problem of decomposing numerical semigroups into irreducible ones has attracted the interest of the research community (see [13, 25, 42, 44, 45]). Recall that a numerical semigroup is irreducible if it cannot be expressed as an intersection of two numerical semigroups containing it properly. Furthermore, more recently a different notion of irreducibility, the m-irreducibility [10], has appeared and has started to be analyzed. A numerical semigroup of multiplicity mis said to be m-irreducible if it cannot be expressed as an intersection of two numerical semigroups of multiplicity mand containing properly. The question of existence of m-irreducible decompositions has been proved in [10]. Nevertheless, it is still missing a methodology, different from the almost pure brute force enumeration, to find irreducible or m-irreducible decompositions of minimal size. The decompositions of numerical semigroups into irreducible ones are useful to obtain, from the knowledge of the simpler ones, properties and conclusions over the original (complex) semigroups. For instance, if Sis a numerical semigroup and S=S1∩···∩Snis a decomposition of Sinto irreducible, important invariants such as the Frobenius number of Sare easier to compute since F(S)=max iF(Si), and F(Si) has a simplified computation since F(Si)isthe unique special gap of Si(see [46]). In this paper, we give a methodology to obtain such a minimal decomposition into m-irreducible numerical semigroups by using tools borrowed from discrete optimization. For the sake of readability, we restrict ourselves to analyzing decompositions into m-irreducible numerical semigroups. Our methodology is applicable to decompositions into standard irreducible by considering instead of the multiplicity the concept of conductor, that is, the Frobenius number plus one. Nevertheless, in the latter case the dimension of the associated polytopes is higher since the conductor is always greater than the multiplicity. This fact would make the presentation and the analysis more intricate yet doable. (The interested reader can find in the concluding remarks some hints on this subject.) To this end, we identify one-to-one numerical semigroups with the integer vectors inside a rational polyhedron (see [41]). For the sake of this identification, we introduce the notion of the Kunz-coordinates vector to translate the considered problem in the problem of finding some integer optimal solutions, with respect to appropriate objective functions, in the Kunz polyhedron (the one defined by the Kunz-coordinates vectors of all the numerical semigroups with a fixed multiplicity m). Then, the problem of enumerating the minimal m-irreducible numerical semigroups involved in the decomposition is formulated as a multiobjective integer program (Theorem 18). We state that solving this problem is equivalent to enumerating the entire sets of optimal solutions of a finite set of single-objective integer problems (Theorem 24). The number of integer problems to be solved is bounded above by m−1, where mis the multiplicity of the semigroup to be decomposed. Finally, we solve a set covering problem to ensure that the decomposition has the smallest number of elements (Theorem 27). Although this approach is exact, its complexity is rather high and in general one cannot prove that it is polynomial for any given multiplicity m. This observation comes from the fact that there are relatively few exact methods to solve general multiobjective integer and linear problems (see [23]) and it is known that the complexity of solving in general this type of problem is #P-hard. To overcome this difficulty, we introduce a different machinery that identifies a minimal decomposition by solving a compact linear integer program (section 6). This approach ensures that the problem of finding a minimal m-irreducible decomposition is polynomially solvable. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1212 V´ ICTOR BLANCO AND JUSTO PUERTO We emphasize that we have included numerous examples in this paper, illustrating and supporting the algorithms. Our methods are also tested for semigroups with rather large multiplicities, in particular with multiplicities that GAP [17], under the package numericalsgps, which is a standard software for making computations with numerical semigroups, is not able to handle, as well as for semigroups for which GAP does not ensure minimality. These points show the efficiency of the presented methods. Last but not least, we mention that a secondary goal of this paper is to connect two important fields of mathematics: optimization and pure algebra. In this regard, although we follow an abstract point of view, this work has direct applications, for instance, in commutative ring theory. In fact, let Sbe a numerical semigroup, K afield,andK[[t]] the ring of formal power series over K. It is well known (see, for instance, [3]) that K[[S]] = {s∈Sasts:as∈K}is a subring of K[[t]], called the ring of the semigroup associated to S. Then, as a consequence of the results in this paper we have that given a numerical semigroup Swe can efficiently and effectively decompose the ring K[[S]], up to large sizes, as a minimal intersection of rings with the same multiplicity where some of them are Gorenstein (see [32]), some others are Kunz (see, e.g., [3, 4]), and others are rings associated to numerical semigroups with special simplicity: {x∈N:x≥m}∪{0}and {x∈N:x≥mand x=i}∪{0} for i∈{m+1,...,2m−1}. Furthermore, another application of the results in this paper is to algebraic geometry. To each point Pof a complete irreducible nonsingular curve Cof genus g, there is associated a numerical semigroup, the Weiertrass semigroup, of the polo orders of the rational functions on Cholomorphic outside P. (See [24, 28, 29] for further details on this theory.) The analysis of this semigroup leads to obtaining properties about many challenging algebraic curves which would not be possible otherwise. Having new tools to obtain irreducible representations for larger numerical semigroups may help in the analysis of more complex (higher dimension) algebraic curves. Indeed, the Weiertrass semigroup may be decomposed into irreducible numerical semigroups and this way its analysis would reduce to the study of simpler semigroups. Also, one can find in the literature interesting research papers dealing with the applicability of numerical semigroups in automata theory (see [27, 37, 38]). The rest of paper is organized as follows. In section 2 we recall the main definitions and results needed for this paper to be self-contained. Section 3 translates the problem of finding numerical semigroups of a given multiplicity into the problem of detecting integer points inside a rational polyhedron, introducing the notion of the Kunz-coordinates vector. We give in section 4 the conditions, in terms of the Kunzcoordinates vector, for a numerical semigroup to be an m-irreducible oversemigroup. Section 5 formulates the problem of decomposing and minimally (with the smallest number of m-irreducible semigroups involved in the decomposition) decomposing into m-irreducible numerical semigroups as a mathematical programming problem. We give an exact and a heuristic approach for computing such a minimal decomposition based on solving some integer programming problems. In section 6 we present a compact model to compute, by solving only one integer programming problem, a minimal decomposition of a numerical semigroup into m-irreducible numerical semigroups. In the same section, we also prove that this problem is polynomially solvable. Section 7 shows some computational tests performed to check the efficiency of the presented algorithms with respect to the current implementation in GAP [17]. Finally, in section 8 we draw some conclusions about the contributions of this paper and further research. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1213 2. Preliminaries. For the sake of readability, in this section we recall the main results about numerical semigroups needed for the paper to be self-contained. Let Sbe a numerical semigroup. We say that {n1,...,n p}is a system of generators of Sif S={p i=1 nixi:xi∈Z+,i =1,...,p}.WedenoteS=n1,...,n pif {n1,...,n p}is a system of generators of S. The least positive integer belonging to Sis denoted by m(S) and is called the multiplicity of S(m(S)=min(S\{0})). The largest integer not belonging to S is called the Frobenius number of S,F(S), and its existence is guaranteed by the definition of numerical semigroup. (See [40, 47] for a detailed analysis of the Frobenius number of a numerical semigroup.) Hence, every numerical semigroup is in the form S={0,n 1,...,n k}∪{n∈Z:n>n k}for some n1,...,n k∈Z+. The following notions of irreducibility are extensively used throughout this paper. Definition 1 (irreducibility and m-irreducibility). •A numerical semigroup is irreducible if it cannot be expressed as an intersection of two numerical semigroups containing it properly. •A numerical semigroup of multiplicity mis m-irreducible if it cannot be expressed as an intersection of two numerical semigroups of multiplicity mcontaining it properly. In [10], Blanco and Rosales analyze and characterize the set of m-irreducible numerical semigroups. Note that, in particular, any irreducible numerical semigroup is m-irreducible, while the converse is not true. One of the results in that paper is the key for the analysis done through this paper and it is stated as follows. Proposition 2 (see [10]). Let Sbe a numerical semigroup of multiplicity m. Then, there exist S1,...,S km-irreducible numerical semigroups such that S=S1∩ ···∩Sk. From the above result, although the decomposition of a numerical semigroup is always possible, one may think of obtaining the minimal number of elements involved in the above intersection of m-irreducible numerical semigroups. Formally, we describe what we understand by decomposing and minimally decomposing a numerical semigroup of multiplicity minto m-irreducible numerical semigroups. Definition 3 (decomposition into m-irreducible numerical semigroups). Let Sbe a numerical semigroup of multiplicity m. Decomposing Sinto m-irreducible numerical semigroups consists of finding a set of m-irreducible numerical semigroups S1,...,S r(S)such that S=S1∩···∩Sr(S). (This decomposition is always possible by Proposition 2.) A minimal decomposition of Sinto m-irreducible numerical semigroups is a decomposition with minimum r(S)(minimal cardinality of the number of m-irreducible numerical semigroups involved in the decomposition). Observe that minimal decompositions may not be unique since one can find different decompositions of Sinto m-irreducible numerical semigroups with the same number of semigroups involved. This is the case of S=5,14,22,31that is minimally decomposed as 5,9,11,13∩5,14,17or 5,8,11,14∩5,14,17. The irreducibility of a numerical semigroup has been widely studied in recent years by the computational algebra community. This trend is explained by its extensive use in related areas such as number theory or algebraic geometry, where numerical semigroups appear naturally, as mentioned in the introduction of this paper. This is the case of the valuation ring, K[[S]], of a numerical semigroup S,whichisoftype Gorenstein or Kunz when Sis irreducible (see [4]). Decomposing a numerical semigroup into irreducible becomes particularly useful in the case of valuation rings since Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1214 V´ ICTOR BLANCO AND JUSTO PUERTO it means that we can decompose any valuation ring into rings which are Gorenstein or Kunz, and then one can transform the analysis of general semigroup rings to the case of rings that are well known in the literature. Furthermore, several algorithms have been proposed to minimally decompose a numerical semigroup into irreducible ones (see [13, 25, 42, 44, 45], among others). However, all are based on a brute force enumeration of a large set of numerical semigroups. In this paper, we propose an alternative method to obtain a minimal decomposition by translating the algebraic problem to an integer optimization problem. For the sake of completeness, we first recall some of the main results that will be useful in our development. The interested reader is referred to [47] for further details. For a numerical semigroup S, the set of gaps of S,G(S), is the set Z+\S(that is finite by definition of numerical semigroup). We denote by g(S) the cardinality of that set, which is usually called the genus of S. Hence, the Frobenius number of S, F(S), is the largest integer belonging to G(S)(or−1ifS=Z+). Let Sbe a numerical semigroup of multiplicity m. To decompose Sinto mirreducible numerical semigroups, we first need to know how to identify those mirreducible numerical semigroups. In [10] it is proved that Sis m-irreducible if and only if it is maximal (with respect to the inclusion order) in the set of numerical semigroups of multiplicity mand Frobenius number F(S). In [44] it is proved that a numerical semigroup Sis irreducible if and only if g(S)=F(S)+1 2. The following two results that appear in [10] allow us to check the m-irreducibility of a numerical semigroup by analyzing its genus and its Frobenius number. Proposition 4 (see [10]). A numerical semigroup of multiplicity m,S,ismirreducible if and only if one of the following conditions holds: 1. F(S)=g(S)=m−1(being then S={x∈Z+:x≥m}∪{0}). 2. F(S)∈{m+1,...,2m−1}and g(S)=m(being then S={x∈Z+:x≥ m, x =F(S)}∪{0}). 3. F(S)>2m(being San irreducible numerical semigroup, so g(S)=F(S)+1 2). Corollary 5 (see [10]). Let Sbe a numerical semigroup of multiplicity m. Then, Sis m-irreducible if and only if g(S)∈{m−1,m,F(S)+1 2}. For a given numerical semigroup S, our goal is to find a set of m-irreducible numerical semigroups whose intersection is S. Then, we can restrict the search of these semigroups to the set of numerical semigroups containing S. This set is called the set of oversemigroups of S. Definition 6 (oversemigroups). Let Sbe a numerical semigroup of multiplicity m.ThesetO(S)of oversemigroups of Sis O(S):={Snumerical semigroup :S⊆S}. The set Om(S)of oversemigroups of Sof multiplicity mis Om(S)={S∈O(S): m(S)=m}. Denote by Jm(S)thesetofm-irreducible numerical semigroups in the set Om(S) and by Im(S) the set of minimal elements in Jm(S), with respect to the inclusion poset. From the set Im(S) we can obtain a first decomposition of Sinto an mirreducible numerical semigroup, although in general it may not be minimal (see Example 27 in [10]). Lemma 7. Let Sbe a numerical semigroup of multiplicity mand Im(S)= {S1,...,S n}.ThenS=S1∩···∩Snis a decomposition of Sinto m-irreducible numerical semigroups. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1215 Proof. The proof easily follows from Proposition 2, since S=∩S∈Jm(S)S. Clearly, the above basic decomposition is not ensured to be minimal since it may use redundant elements. Remark 8. Note that if ˆ Sis a numerical semigroup of multiplicity m,byProposition 4, g( ˆ S)=m−1 if and only if ˆ S={0,m,→} (→denotes that every integer greater than mbelongs to ˆ S). Hence, this m-irreducible numerical semigroup only appears in its own decomposition and in no one else. This is due to the fact that ˆ S={0,m,→} is the maximal element in the set of numerical semigroups of multiplicity m,andthenOm(ˆ S)=Im(ˆ S)={ˆ S}(see [10] for further details). From now on, we assume that S=ˆ S={0,m,→} since by the above remark, the decomposition of ˆ Sis trivial. By Proposition 4 and Remark 8, if S=ˆ S={0,m,→}, its decomposition into m-irreducible numerical semigroups uses two types of numerical semigroups: those that have genus equal to the multiplicity of Sand those that are irreducible (g(S)= F(S)+1 2). To refine the search of the elements in Im(S), first we introduce the notion of special gap. Definition 9. Let Sbe a numerical semigroup. The special gaps of Sare the elements in the following set: SG(S)={h∈G(S):S∪{h}is a numerical semigroup}, where G(S)is the set of gaps of S. We denote by SGm(S) the special gaps greater than m, i.e., SGm(S)={h∈ SG(S):h>m}. In [10], the authors proved that Sis m-irreducible if and only if #SGm(S)⩽1(#Astands for the cardinality of the set A). Moreover, SGm(S)=∅ if and only if S={0,m,→} (there are no gaps greater than min S). Also, if we know the special gaps of a numerical semigroup, we can search for its decomposition by using the following result. Proposition 10 (see [10]). Let S, S1,...,S nbe numerical semigroups of multiplicity m.S=S1∩···∩Snif and only if SGm(S)∩(G(S1)∪···∪G(Sn)) = SGm(S). From the above proposition, even if the minimal m-irreducible numerical semigroups, Im(S)={S1,...,S m}, are known some of these elements may be discarded when looking for a minimal m-irreducible decomposition by checking if there are redundant elements in the intersection SGm(S)∩(G(S1)∪···∪G(Sn)). Then, in order to find minimal decompositions, one may choose elements in Im(S) that minimally cover the special gaps of S. To this end, we may solve a problem fixing each of the special gaps to be covered. Note that an upper bound of the number of problems to be solved is the number of special gaps of a numerical semigroup that is bounded above by m−1 (see [47]). Lemma 11. Let S={0,m,→} be a numerical semigroup of multiplicity m,and h∈SGm(S). Then, there exists a minimal decomposition of Sinto m-irreducible numerical semigroups, S=S1∩···∩Sn, such that either h=F(Si)for some ior h∈ Sifor some isuch that there exists h∈SGm(Si)with F(Si)=h>h. Proof. By Proposition 2, there exists a minimal decomposition of Sinto an m-irreducible numerical semigroup, S=S1∩ ··· ∩ Sk. By applying Proposition 10, this decomposition must verify that SGm(S)∩(G(S1)∪···∪G(Sn)) = SGm(S). Each special gap h∈SGm(S)mustbeinG(Si)forsomei=1,...,n. Assume that h=F(Si)andthatforallh∈SGm(Si) with h>h,F(Si)=h. Then, Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1216 V´ ICTOR BLANCO AND JUSTO PUERTO S i=Si∪{F(Si)}is an m-irreducible numerical semigroup such that SGm(S)∩ (G(S1)∪···G(S i)···∪G(Sn)) = SGm(S). Then, we have obtained a different minimal decomposition. (Note that it has the same number of terms as the original one.) By repeating this procedure for each h∈SGm(S) whenever possible, we find a minimal decomposition of Sfulfilling the conditions of the lemma. 3. The Kunz-coordinates vector. The approach followed in this paper uses mathematical programming tools to solve the problem of decomposing a numerical semigroup into m-irreducible numerical semigroups. For the sake of translating the problem to a discrete optimization problem, we use an alternative encoding of numerical semigroups different from the system of generators. We identify each numerical semigroup of multiplicity mwith a nonnegative integer vector with m−1 coordinates, where mis the multiplicity of the semigroup. To describe this identification we first need to give the notion of an Ap´ery set of a numerical semigroup that was introduced by Ap´ery in [1]. Definition 12. Let Sbe a numerical semigroup and n∈S\{0}.TheAp´ery set of Swith respect to nis the set Ap(S, n)={s∈S:s−n∈ S}. However, we are interested in the following characterization of the Ap´ery set (see [47]): Let Sbe a numerical semigroup and n∈S\{0}; then Ap(S, n)={0= w0,w 1,...,w n−1},wherewiis the smallest element in Scongruent with imodulo nfor i=1,...,n−1. Moreover, the set Ap(S, n) completely determines S,sinceS=Ap(S, n)∪{n} (see [41]). Actually, nis already indirectly contained in the Ap´ery set, namely, n=#Ap(S, n)−1. Hence, we can identify Swith its Ap´ery set with respect to n. Besides, the set Ap(S, n) contains, in general, more information than an arbitrary system of generators of S. For instance, Selmer in [48] gives the formulas, g(S)= 1 n(w∈Ap(S,n)w)−n−1 2and F(S)=max(Ap(S, n)) −n. In addition, one can test if a nonnegative integer sbelongs to Sby checking if ws(mod n)⩽s.Notethat the smallest Ap´ery set is Ap(S, m(S)). We consider a slight but useful modification of the Ap´ery set that we call the Kunz-coordinates vector. Definition 13 (Kunz-coordinates). Let Sbe a numerical semigroup of multiplicity m.IfAp(S, m)={w0=0,w 1,...,w m−1}with wicongruent with imodulo m, the Kunz-coordinates vector of Sis the vector x∈Zm−1 +with components xi=wi−i m for i=1,...,m−1. We say that x∈Zm−1 +is a Kunz-coordinates vector (or Kunz-coordinates, for short) if there exists a numerical semigroup whose Kunz-coordinates vector is x. From the Kunz-coordinates we can recover the Ap´ery set. If x∈Zm−1 +is the Kunz-coordinates vector of S,Ap(S, m)={mxi+i:i=1,...,m−1}∪{0}.Consequently, Scan be completely described from its Kunz-coordinates. The Kunz-coordinates vectors have been implicitly used in [32] and [41] to characterize numerical semigroups with fixed multiplicity and used in [6] to count numerical semigroups with a given genus. Furthermore, if Sis a numerical semigroup of multiplicity mand x∈Zm−1 +are its Kunz-coordinates, from Selmer’s formulas it is easy to compute its genus and its Frobenius number as follows: •g(S)=m−1 i=1 xi, •F(S)=max i{m(xi−1) + i}(clearly, if the maximum is reached in the ith component, F(S)≡i(mod m)) Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1217 (where for a, b, c ∈Z,a≡b(mod c) denotes that aand bare congruent modulo c, that is, a−bis an integer multiple of c). The following result that appears in [41] allows us to manipulate numerical semigroups of multiplicity mas integer points inside a polyhedron. Theorem 14 (Theorem 11 in [41]). Each numerical semigroup is one-to-one identified with its Kunz-coordinates. Furthermore, the Kunz-coordinates vectors of the set of numerical semigroups of multiplicity mis the set of solutions of the following system of diophantine inequalities: xi⩾1for all i∈{1,...,m−1}, xi+xj−xi+j⩾0for all 1⩽i⩽j⩽m−1,i+j⩽m−1, xi+xj−xi+j−m⩾−1for all 1⩽i⩽j⩽m−1,i+j>m, xi∈Z+for all i∈{1,...,m−1}. The polyhedron defined by the above system of inequalities is usually called the Kunz polyhedron. From Theorem 14 and Selmer formulas, we can identify all the numerical semigroups (in terms of their Kunz-coordinates vector) of multiplicity m,genusg,and Frobenius number Fwith the solutions of this system of diophantine inequalities: xi⩾1 for all i∈{1,...,m−1}, xi+xj−xi+j⩾0 for all 1 ⩽i⩽j⩽m−1, i+j⩽m−1, xi+xj−xi+j−m⩾−1 for 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+for all i∈{1,...,m−1}. From the above formulation and Corollary 5, the set of m-irreducible numerical semigroups is completely determined by the solutions of the following diophantine system of inequalities and equations, which is obtained fixing the value of the genus: (3.1) xi⩾1 for all i∈{1,...,m−1}, xi+xj−xi+j⩾0 for all 1 ⩽i⩽j⩽m−1, i+j⩽m−1, xi+xj−xi+j−m⩾−1 for all 1 ⩽i⩽j⩽m−1, i+j>m, m−1  i=1 xi∈{m−1,m,maxi{m(xi−1) + i}}, xi∈Z+for all i∈{1,...,m−1}. Note that the above system is not a standard system of diophantine inequalities since (3.1) is equivalent to solving three systems of diophantine equations/inequalities. Once the m-irreducible numerical semigroups are characterized in terms of the Kunz-coordinates vectors, in order to characterize the minimal m-irreducible decompositions of a numerical semigroup Swith multiplicity m, we need to determine the structure of its oversemigroups. Observe that those semigroups are the first candidates to appear in the decomposition of S. The following result characterizes the set of oversemigroups of a numerical semigroup in terms of its Kunz-coordinates vector. Proposition 15. Let Sbe a numerical semigroup of multiplicity mand x∈ Zm−1 +its Kunz-coordinates. Then, the set of Kunz-coordinates vectors of oversemiDownloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1218 V´ ICTOR BLANCO AND JUSTO PUERTO groups of Sof multiplicity mis (3.2) Um(x)={x∈Zm−1 +:xis a Kunz-coordinates vector and x≤x}, where ≤denotes the componentwise order in Zm−1. Proof.LetS∈O m(S)andAp(S,m)={0,w  1,...,w  m−1}.LetAp(S, m)= {0,w 1,...,w m−1}.Theith element in the Ap´ery set is characterized as being the minimum element in the semigroup that is congruent with imodulo m.Thus,w i⩽ wifor all i=1,...,m −1sinceS⊆S.Thenx i=w i−i m⩽wi−i m=xifor all i=1,...,m−1. Hence, x≤x. For the sake of readability, we shall refer to the set Um(x) introduced in (3.2) as the set of undercoordinates of x. It is clear from Proposition 15 that if xis the Kunz-coordinates vector of a numerical semigroup S, the oversemigroups of S(see Definition 6) can be one-to-one identified with the undercoordinates of its Kunzcoordinates vector. For ease of presentation, we identify a numerical semigroup of multiplicity mwith an integer vector with m−1 coordinates, its Kunz-coordinates. All the notions previously given for numerical semigroups are adapted conveniently by using the following notation. If Sis a numerical semigroup and x∈Zm−1is its Kunz-coordinates vector, we write •m(x)=m(S)=m(multiplicity of x); •F(x)=F(S) (Frobenius number); •G(x)=G(S)={n∈Z:mxn(mod m)+n(mod m)>n}(gaps of x); •g(x)=g(S)(genusofx); •SG(x)=SG(S) (special gaps of x); •SGm(x)=SG m(S) (special gaps of xgreater than m); •U m(x)={x∈Zm−1:xis a Kunz-coordinates vector and x≤x}(undercoordinates of x); observe that Om(S)={{0}∪{mx i+i} :x∈U m(x)}; •Ap(x)=Ap(S, m)={0}∪{mxi+i:i=1,...,m−1}(Ap´ery set of x). Note that all the above indices and sets can be computed by using only the Kunzcoordinates vector of the semigroup. Recall that we have assumed without loss of generality that S={0,m,→}.In terms of the Kunz-coordinates, this assumption is equivalent to saying that x= (1,...,1) ∈Zm−1 +(or m−1 i=1 xi⩾m). By Corollary 5 we say that a Kunz-coordinates vector x∈Zm−1 +is m-irreducible if g(x)∈{m, m −1,F(x)+1 2}. Furthermore, we say that xis irreducible if g(x)= F(x)+1 2. Hence, every irreducible Kunz-coordinates vector in Zm−1 +is m-irreducible, but the converse is not true in general. We also say that a set of Kunz-coordinates vectors, D={x1,...,x k}⊆Zm−1 +, is a decomposition of x∈Zm−1 +into m-irreducible Kunz-coordinates vectors if the semigroups associated with the elements in Dgive a decomposition into m-irreducible numerical semigroups of the semigroup identified with x. Equivalently, by Proposition 10, Dis a decomposition of x∈Zm−1 +into m-irreducible Kunz-coordinates vectors if xiis an m-irreducible Kunz-coordinates vector and SGm(x)=SG m(x)∩ G(x1)∪···∪G(xk). Then, a minimal decomposition x∈Zm−1 +into m-irreducible Kunz-coordinates is a decomposition into m-irreducible Kunz-coordinates, D={x1,...,x k}⊆Zm−1 +, with minimum cardinality. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1225 Proof.Leth∈SG(x). By Lemma 21, every nondominated solutions of MIPm(x, h), y, induces a m-irreducible undercoordinate of x,namely,x−y, with F(x−y)=h.By Proposition 4, every m-irreducible Kunz-coordinates vector has either genus m−1 (this case has been already discarded), m,orFrobenius number +1 2.Furthermore, Proposition 4 also states that if the genus is m, then the Frobenius number is smaller than 2mand greater than 2motherwise. Hence, if h<2mand x−yis an mirreducible undercoordinate of xthe genus, g(x−y)=m−1 i=1 xi−m−1 i=1 yi,ism, and by (4.4), y=x−1−ejfor some j.Next,sinceF(x−y)=h, we conclude that j=k(h)andthenyk(h)=xk(h)−2. That proves that if h<2m,ymust be a solution of IPm m(x, h). Assume now that h>2m. By Lemma 21, we only need to solve the multiobjective problems (MIPm k(x)) with k=k(h). In addition, Remark 22 proves that any solution of (MIPm k(x)) has minimum overall sum of its coordinates over Pm k(h)(x)∩{y∈Zm−1: yk(h)=0}. Hence, any nondominated solution is an optimal solution for some of the linear (single-objective) integer programs above. Furthermore, assume that y∗∈Zm−1 +is an optimal solution of (IPm(x, h)) or (IPm m(x, h)). If y∗were not a nondominated solution of (MIPm(x, h)) another feasible solution, y,of(MIP m(x, h)) would exist (and consequently either in Pm k(h)(x)orin Pm m(x)) such that y≤y∗. Then, m−1 i=1 yi≤m−1 i=1 y∗ i.Next,sincey∗is an optimal solution for (IPm(x, h)) or (IPm m(x, h)),wehavethatm−1 i=1 yi=m−1 i=1 y∗ i. Hence, y=y∗since y,y∗∈Zm−1 +. Finally, we are looking for solutions, y, with the minimum difference of gaps with x, so minimizing iyi. Therefore, for our purpose it is enough to minimize the sum of the components of y,asformulatedin(IP m(x, h)) and (IPm m(x, h)). Note that if (IPm m(x, h)) is feasible, it has a unique feasible solution, namely, y=x−1−ek(h)(see (4.4)). Furthermore, this problem is feasible if and only if k(h)=h−msince under this condition h=2m+k(h)−m, the Frobenius number. Actually, in this case, if (IPm(x, h)) has a solution, y,itmustalsobethesolution of (IPm m(x, h)). This fact is stated in the following theorem. Theorem 25. Let x∈Zm−1 +be a Kunz-coordinates vector h∈SGm(x)and y1 and y2optimal solutions of problems (IPm(x, h)) and (IPm m(x, h)), respectively. Then, y1=y2. Proof.Wehavetwom-irreducible undercoordinates of x,x1=x−y1and x2= x−y2.x1is an irreducible Kunz-coordinates vector with Frobenius number h.x2is a Kunz-coordinates vector with Frobenius number hand genus m. Since the irreducible Kunz-coordinates are those with maximal genus when fixing the Frobenius number and the maximum genus in this case is m,theny1=y2because in both problems we are minimizing the sum of y. The following result shows that the optimal value of (IPm(x, h)) is known a priori. Lemma 26. Let ybe an optimal solution of (IPm(x, h)).Then,  i yi= m−1  i=1 xi−h+1 2. Proof. Clearly, optimal solutions must satisfy constraint (4.2). Then, the result follows from Lemma 21. Let x∈Zm−1be a Kunz-coordinates vector. Once a decomposition is chosen, in order to select a minimal decomposition we use a set covering formulation to choose Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1226 V´ ICTOR BLANCO AND JUSTO PUERTO among the overall set of minimal m-irreducible undercoordinates of xa minimal number of elements for the decomposition. Let SGm(x)={h1,...,h s}and Di={xi1,...,x ipi}be the set of the maximal Kunz-coordinates vectors of m-irreducible undercoordinates of xwhen fixing the special gap hi(optimal solutions of IPm(x, hi)) for i=1,...,s.Wedenoteby D=D1∪···∪Dsthe set of m-irreducible Kunz-coordinates vectors candidates to be involved in the minimal decomposition of x. We consider the set of decision variables zij =1ifxijis selected for the minimal decomposition, 0otherwise for i=1,...,s,j=1,...,p i. We formulate the problem of selecting a minimal number of m-irreducible undercoordinates vectors of xthat decompose xinto m-irreducible Kunz-coordinates as (SCm(D)) min s  i=1 pi  j=1 zij s.t.  i,j/mxij k(h)+k(h)≥h+1 zij ≥1 for all h∈SGm(x). The covering constraint ensures that for each special gap of xthere is an element in {xi1,...,x ip1,...,x s1,...,x sps}such that his a gap of its corresponding semigroup. Minimizing the overall sum we find the minimum number of Kunz-coordinates fulfilling this requirement. Note that when solving (SCm(D)) at most one element in Diis choosen for each i=1,...,s. In the following, we give a procedure to decompose a numerical semigroup Sof multiplicity m(after identification with its Kunz-coordinates vector) into m-irreducible numerical semigroups. This process is described in Algorithm 2. In that implementation we also consider two trivial cases: (1) when the number of special gaps greater than the multiplicity is 1, being then the semigroup m-irreducible; and (2) when the number of this special gaps is 2, where the decomposition is given by both solutions of the two unique integer programming problems, and no discarding process is needed. As a consequence of all the above comments and results we state the correctness of our approach. Theorem 27. Algorithm 2computes, exactly, a minimal decomposition into m-irreducible Kunz-coordinates vector of a Kunz-coordinates vector x∈Zm−1 +.Furthermore, the entire set of optimal solutions of (SCm(D)) characterizes the set of minimal decompositions. Algorithm 2 computes a minimal decomposition of a Kunz-coordinates vector, x∈Zm−1 +, by enumerating the whole set of optimal solutions of (IPm(x, h)). However, this task is not easy since it mainly consists of enumerating the set of vertices of the polytope defining the feasible region of an integer programming problem (the convex hull of the integer points inside the polyhedron), which is hard to compute (see, e.g., [2]). In what follows we propose a heuristic approach to obtain a “short” decomposition into m-irreducibles by choosing an optimal solution of (IPm(x, h)) instead of enumerating all of them. One may choose any of them, but we can also slightly modify the integer programming model to obtain a good solution. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1227 Algorithm 2. Decomposition into m-irreducible numerical semigroups. Input: A numerical semigroup Sof multiplicity m. Compute the Kunz-coordinates vector of S:x∈Zm−1 +. (Computing the Ap´ery set.) D={}. Compute SGm(x). if #SGm(x)=1then DmIR = {x} else for hi∈SGm(x)do if hi<2mthen Set D:= D∪{1+e k(h)}. else for each optimal solution of (IPm(x, h)),ˆyido Set D:= D∪{x−ˆyi}. Let D={x11,...,x 1i1,...,x s1,...,x sis}. Let z∗be an optimal solution of (SCm(D)). Set DmIR = {xij ∈D:z∗ ij =1} Output:DmIRNS={{m}∪{mx i+i:i=1,...,m−1} :x∈DmIR}. We consider the set of decision variables wi=1ifhi∈G(x−y), 0otherwise for i=1,...,n, and SGm(x)={h1,...,h n}. For a fixed h∈SGm(x), wi= 1 represents that hiis covered by the solution x−y and then that it can be discarded to obtain a minimal decomposition. Then, to ensure that we maximize the number of elements that can be discarded in the previous decomposition, we formulate the problem as (IPm k(x, h)) max #SGm(x)  i=1 wi s.t. y∈Pm k(h)(x), yk(h)=0, m(xk(ˆ hi)−yk(ˆ hi))+k( ˆ hi)−ˆ hi−1+M(1 −wi)≥0 for all ˆ hi∈SGm(x), where M0. Observe that the big-Mconstraint m(xk(ˆ hi)−yk(ˆ hi))+k(ˆ hi)−ˆ hi−1+M(1−wi)≥0 ensures that if ˆ hi∈ G(x−y) (equivalently, m(xk(ˆ hi)−yk(ˆ hi))+k( ˆ hi)<ˆ hi+ 1), then wi=0. Otherwise,wicould be 0 or 1, but since we are maximizing, wi=1. The optimal value of this integer problem is then the number of numerical semigroups in the decomposition that can be discarded with this choice. A pseudocode of the proposed approximated scheme for obtaining a “short” decomposition of a Kunz-coordinates vector x∈Zm−1 +into m-irreducible Kunzcoordinates vectors by solving (IPm k(x, h)) is shown in Algorithm 3. When running Algorithm 3 we obtain an optimal solution of the problem, and then moving through all the special gaps we obtain a decomposition into m-irreducible Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1228 V´ ICTOR BLANCO AND JUSTO PUERTO Algorithm 3. Decomposition into m-irreducible numerical semigroups. Input: A numerical semigroup Sof multiplicity m. Compute the Kunz-coordinates vector of S:x∈Zm−1 +. (Computing the Ap´ery set.) D={}. Compute SGm(x). if #SGm(x)=1then DmIR = {x} else for hi∈SGm(x)do if hi<2mthen Set D:= D∪{1+e k(h)}. else Let ˆybe an optimal solution of (IPm(x, h)). Set D:= D∪{x−ˆy}. Let D={x1,...,x s}. if #SGm(x)=2then DmIR = D else Select a minimal decomposition from D. Let z∗be an optimal solution of (SCm(D)). Set DmIR = {xj∈D:z∗ j=1} Output:DmIRNS={{m}∪{mx i+i:i=1,...,m−1} :x∈DmIR}. Kunz-coordinates. With the following example we show how Algorithms 2 and 3 run for a given numerical semigroup. Example 28. Let S=5,11,12,18. The multiplicity of Sis m= 5, its Kunzcoordinates vector is x=(2,2,3,4), and SG5(S)={6,13,19}. First, we solve one integer problem for each special gap: •h=6.Sinceh<2×5 = 10, the integer problem to solve is P5 5(x, 6) and then D1={x11 =(2,1,1,1)}. •h= 13. In this case h>2×5 = 10 and h= 3 (mod 5), so the integer problem in this case is P5 3(x, 13). The whole set of optimal solutions 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), the problem is now P5 4(x, 19). The set of optimal solutions is {(1,0,0,0),(0,0,0,1)},andthen D3={x31 =(1,2,3,4),x 32 =(2,2,2,4)}. The above five Kunz-coordinates vectors give a decomposition in oversemigroups of S. To obtain a minimal decomposition we must solve the associated set covering problem. Solving SC5(D) we obtain that z11 =z31 = 1 and all other variables are set to zero, being then the minimal decomposition given by x11 and x31, i.e., a minimal decomposition into 5-irreducible Kunz-coordinates is given by {(2,1,1,1),(1,2,3,4)}. Translating to numerical semigroups, S=5,11,7,8,9∩5,6,12,18,24. When solving (IPm k(x, h)), we obtain the same decomposition. However, the decomposition obtained with Algorithm 3 may not be minimal. The following example illustrates this fact. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1229 Example 29. Let S=12,17,18,23,26,28,33,39be a numerical semigroup of multiplicity 12. Its Kunz-coordinates vector is x=(4,2,3,2,1,1,3,3,2,2,1) and SG12(x)={21,22,27,31,32,37}. Then, six integer problems must be solved: 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 solving these problems with Xpress-Mosel 7.0 [50] we obtain the following optimal solutions: 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 translations of the above coordinates in terms of numerical semigroups are {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 solving problem (SCm(D)), 12,13,14,15,16,17,18,19,20,21,34,23is discarded. Then, the decomposition using our methodology is given by five 12irreducible numerical semigroups: 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. However, this decomposition is not 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 decomposition into mirreducible numerical semigroups using a smaller number of terms. In Example 29 we found that by applying the described methodology we got a decomposition which is not minimal. This situation is due to the fact that among the whole set of optimal solutions of (IPm(x, h)), Algorithm 3 chooses a particular one, but depending on that choice, different numbers of elements can be discarded from that decomposition to obtain the minimal one. To avoid this fact, we need to consider a compact model that connects all the possible elements in the decomposition and that selects, among all of them, the smallest number of solutions to decompose a Kunz-coordinates vector. 6. A compact model for minimally decomposing into m-irreducible Kunz-coordinates vectors. Inthesectionabovewedescribedanexactanda heuristic procedure to compute a minimal decomposition of a Kunz-coordinates vector x∈Zm−1into m-irreducible Kunz-coordinates. To obtain solutions by using that exact procedure we need to enumerate the solutions of a knapsack type diophantine equation included in the Kunz polyhedron. Once we have those solutions, a set covering problem must be solved to obtain a minimal decomposition. By using that model, the complete enumeration cannot be avoided since, by choosing one solution, one may obtain nonminimal decompositions when solving the set covering model (see Example 29). We present here a compact model to decompose any Kunz-coordinates vector, x∈Zm−1 +, merging in a single integer linear programming problem all the subproblems considered in the previous section to ensure minimal decompositions. Moreover, this approach will allow us to prove a polynomiality result for the problem of decomposing into m-irreducible numerical semigroups. Let SGm(x)={h1,...,h s}. We consider the following families of decision variables for the new model: •yl i∈Z+for all l=1,...,s and i=1,...,m −1 such that x−ylis an m-irreducible undercoordinate of xwith Frobenius number hl. •wl∈{0,1}for all l=1,...,s, representing if x−yhlis chosen (1) or not (0) for a minimal decomposition into m-irreducible coordinates of x. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1230 V´ ICTOR BLANCO AND JUSTO PUERTO •zl k∈{0,1}that measures if hkis a gap of x−yl(1) or not (0) for all l, k =1,...,s.Notethathk∈G(x−yl) if and only if yl k(hk)=0. In addition, take M⩾max{xk(hl):l=1,...,s}. Then, the proposed model, CIPm(x), is described as follows: (CIPm(x)) min s  l=1 wl s.t. yl i⩽xi−1 for all i=1,...,m−1 for all l=1,...,s,(6.1) yl i+yl j−yl i+j⩽xi+xj−xi+jif i+j<mfor all l=1,...,s,(6.2) yl i+yl j−yl i+j−m⩽xi+xj−xi+j−m+1 ifi+j>mfor all l=1,...,s,(6.3) m−1  i=1 yl i=m−1  i=1 xi−hl+1 2wlfor all l=1,...,s with hl>2m,(6.4) m−1  i=1 yl i=m−1  i=1 xi−mwlfor all l=1,...,s with hl<2m,(6.5) yl k(hl)=0 foralll=1,...,s,(6.6)  l zl k(hk)⩾1 for all k=1,...,s,(6.7) zl k(hk)⩾1−yl k(hk)−M(1 −wl) for all l, k =1,...,s,(6.8) yl k(hk)⩽M(1 −zl k(hk)) for all k=1,...,s,(6.9) zl k(hk)⩽wlfor all l, k =1,...,s,(6.10) yl i∈Z+,for all i=1,...,m−1, l=1,...,s,(6.11) wl∈{0,1},for all l=1,...,s,(6.12) zl j∈{0,1}for all l=1,...,s,j=1,...,m−1.(6.13) The components of any optimal solutions, y∗, of the above problem in the set {y∗l:y∗l=0,l =1,...,s}={y∗l1,...,y∗lp}give a minimal decomposition of xinto m-irreducible Kunz-coordinates vectors as {x−y∗lj:j=1,...,s}. Note also that F(x−y∗lj)=hlj. Constraints (6.1)–(6.3) ensure that x−ylis an undercoordinate of x.Equations (6.4) and (6.5) give conditions related to the genus and the Frobenius number of those Kunz-coordinates vectors (Corollary 5) associated to the choice of yl(wl= 1). Constraint (6.6) ensures that hlis a gap of x−yland (6.7) that there is at least one element in the decomposition having hlamong its gaps. Constraints (6.8)– (6.10) control that the variables zl kare well defined. Equations (6.11)–(6.13) are the integrality and binary constraints for the variables. The optimal value of (CIPm(x)) gives the number of Kunz-coordinates involved in a minimal decomposition of xinto m-irreducible Kunz-coordinates vectors. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1231 The solution of (CIPm(x)) gives exactly a minimal decomposition of xinto mirreducible Kunz-coordinates (or m-irreducible numerical semigroups). However, it is harder to solve than the problems in Algorithm 3 since it has many more variables. (By using Algorithm 3, we need to solve at most m−1 problems with m−1 variables and a set covering problem with at most m−1 variables while (CIPm(x)) has 2(m−1)2+ (m−1) integer/binary variables.) In the computational experiments (see section 6) we have observed that the solutions when running Algorithm 3 are not far from minimality and it is faster than solving (CIPm(x)). Remark 30 (m-symmetry and m-pseudosymmetry). Blanco and Rosales [10] also defined the notion of m-symmetry and m-pseudosymmetry of a numerical semigroup of multiplicity m, extending the previous notions of symmetry and pseudosymmetry (see [47]). A numerical semigroup Sof multiplicity mis m-symmetric if Sis mirreducible and F(S) is odd. On the other hand, Sis m-pseudosymmetric if Sis m-irreducible and F(S)iseven. Rosales and Branco analyzed in [42] and [43] those numerical semigroups that can be decomposed into symmetric numerical semigroups. (In this case the semigroup is called the ISY-semigroup.) Another interesting application of our methodology is to compute a decomposition of Sinto m-symmetric numerical semigroups. (Following the notation in [43], Sis an ISYM-semigroup.) This follows by fixing in (CIPm(x)) that the m-irreducible numerical oversemigroups of Sassociated to even special gaps do not appear in the decomposition (yl i=0foralli=1,...,m−1iflis even). Thus, the m-irreducible numerical semigroups whose Frobenius numbers are each of the odd special gaps must cover the whole set of gaps. If this problem is feasible, its solution gives a minimal decomposition into m-symmetric numerical semigroups. However, in this case we cannot ensure that it is always possible to decompose into m-symmetric numerical semigroups (for instance, a numerical semigroup with even Frobenius number is not decomposable in this way). Then, if problem (CIPm(x)) is infeasible, the semigroup cannot be expressed as an intersection of m-symmetric numerical semigroups. In addition, [43] analyzes the set of ISYG-semigroups (those that can be expressed as an intersection of symmetric semigroups with the same Frobenius number). We could introduce the notion of ISYGM-semigroups (those that can be expressed as an intersection of symmetric numerical semigroups with the same Frobenius number and multiplicity). This case can also be handled with our approach by fixing the Frobenius number of the semigroup in (CIPm(x)). A similar methodology can be applied to compute a decomposition into mpseudosymmetric numerical semigroups. Remark 31 (computational complexity). Assume that mis fixed. (CIPm(x)) hasatmost2(m−1)2+(m−1) variables and then it is solvable in polynomial time [35]. It is worth noting that the heuristic approach also has polynomial time overall complexity. Indeed, for each special gap of x, one integer program is solved, IPm(x, h) if h>2mor IPm m(x)ifh<2m. Since the number of special gaps is bounded above by m−1, the complexity of this step is polynomial for fixed multiplicity and so is polynomial. Once we have the solutions for all the special gaps, the discarding step consists of solving the set covering problem (SCm(D)) with at most m−1variables and so is polynomial in m. On the other hand, the algorithm proposed in [10] to decompose a numerical semigroup Sof multiplicity minto m-irreducible numerical semigroups can be rewritten as follows. Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1232 V´ ICTOR BLANCO AND JUSTO PUERTO x vvmmmmmmmmmmmmmm (( 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.Sketch of Gx. Let Gx=(V,E) be a directed graph whose set of vertices is the set of undercoordinates of x,Um(x), and (x1,x 2)∈Eif x2=x1−eh(mod m)for some h∈SGm(x). Figure 6.1 illustrates how this graph is built. In that figure we denote SGm(x)={h1,...,h k}and SGm(x+e k(h))={h 1,...,h  k}. The algorithm searches for a set of vertices {x1,...,x n}with the properties that #SGm(xi)=1for all i=1,...,n and that any other vertex is dominated by any of the elements in the set. Furthermore, Gxis a tree since it does not have circuits. In [10], a breadth first search over this tree is proposed to find the desired set. Clearly, the worst case complexity of this method is exponential even for fixed multiplicity. 7. Computational experiments. In this section we present the results of some computational experiments designed to analyze the performance of the proposed algorithms. Our algorithms have been implemented in XPRESS-Mosel 7.0 [50], which allows us to solve the single-objective integer problems involved in the decomposition into m-irreducible numerical semigroups by using a branch-and-bound method and nesting models by calling the library mmjobs. The algorithms have been executed on aPCwithanIntelCore2Quadprocessorat2x2.50GHzand4GBofRAM. The complexity of the algorithm depends of the dimension of the space (multiplicity), the size of the coefficients of the constraints, and the number of special gaps. Then, we randomly generated three different batteries of numerical semigroups with the following requirements: Battery I. Numerical semigroups with multiplicities ranging in [0,25] (divided in the five subintervals (0,5], (5,10], (10,15], (15,20], and (20,25]) with generators ranging in [2,5000]. There are 10 instances for each subinterval. Battery II. Numerical semigroups with multiplicities ranging in [10,2000] (divided in the seven subintervals (10,25], (25,50], (50,100], (100,250], (250,500], (500,1000], and (1000,2000]) with generators ranging in [2,5000]. There are five instances for each subinterval. Battery III. Numerical semigroups with multiplicities ranging in [25,150] (divided in the five subintervals (25,50],(50,75],(75,100],(100,125], and (125,150]) with generators ranging in [2,5000] and with number of special gaps greater than the multiplicity less than or equal to 30. There are 10 instances for each subinterval. The first battery of problems is designed to compare the three algorithms: the one implemented in GAP, the heuristic approach (Algorithm 3), and the compact model (CIPm(x)). With the second set of problems, we check the efficiency of Algorithm 3 for solving large instances. Finally, with the third battery of problems, we compare the Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. INTEGER PROGRAMMING FOR DECOMPOSING SEMIGROUPS 1233 Table 7.1 Results of the computational experiments for Battery I. mCMtime Heurtime GAPtime #SG #m-irred avgap [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 Results of the computational experiments for Battery II. mHeurtime #SG #m-irred (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 Results of the computational experiments for Battery III. mCMtime Heurtime #SG #m-irred avgap (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 difficulty of solving (CIPm(x)) and the heuristic algorithm. (Note that this difficulty is mainly due to the number of special gaps since it increases the number of variables.) Therefore, we generate numerical semigroups with very large multiplicities but where the number of special gaps is bounded above by 30. We used recursively the function RandomListForNS of GAP[17] until we found the list of integers defining the semigroup with the above requirements. The implementation done for decomposing in GAP (with the package numericalsgps)intomirreducible numerical semigroups is an adaptation of the function DecomposeIntoIrreducibles for decomposing into standard irreducible numerical semigroups. The results of these experiments are summarized in Tables 7.1–7.3. In these tables, mindicates the range of the multiplicity, CMtime and Heurtime the average times in seconds consumed by solving (CIPm(x)) and Algorithm 3, respectively, in Xpress-Mosel,GAPtime informs on the average time consumed by GAP for the same task, #SG is the average number of special gaps of the problems, and #m-irred is the average number of semigroups involved in a minimal decomposition. The column avgap is the average difference between the number of numerical semigroups used in the heuristic decomposition and the number of numerical semigroups used in the minimal decomposition computed by solving (CIPm(x)). Note that even for instances of Battery I, GAP was not able to solve any of the 10 instances when the multiplicity ranges in (20,25]. We have also observed that the algorithm implemented in GAP does not ensure minimal decompositions into m-irreducible numerical semigroups. For instance, consider the semigroup S=15,17,19,48,52,59,73that decomposes in GAP into six Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1234 V´ ICTOR BLANCO AND JUSTO PUERTO 15-irreducible numerical semigroups, while our methodology obtains a decomposition into five 15-irreducible numerical semigroups. The reason GAP fails is closely related to the fact that prevents ensuring, in all cases, that Algorithm 3 gets minimal solutions. From our computational experiments we observe that except for the instances with m∈[0,5], where the algorithm in GAP takes almost the same time to compute the decompositions, our methodology solves the problems faster than GAP. Actually, in this battery solving the problem (CIPm(x)) is the best way to compute such a decomposition. This is due to the minimum computational time consumed by XpressMosel to load the problems involved in Algorithm 3. Both the exact algorithm based on solving (CIPm(x)) and the heuristic approach are able to compute, in reasonable CPU times, minimal decompositions into mirreducible numerical semigroups for multiplicities up to 150, while the procedure implemented in GAP is not able to solve problems with multiplicities ranging even in (20,25]. Furthermore, although the default branch-and-bound algorithm is not able to solve (CIPm(x)) for larger multiplicities, the heuristic approach solves problems with multiplicities up to m= 2000. The heuristic approach finds a short decomposition of numerical semigroups into m-irreducible numerical semigroups much faster than the exact approach. Furthermore, the heuristic approach reaches a minimal decomposition most of the time. For instance, in the first battery of problems, the heuristic value does not coincide with the exact optimal one in only 2 of the 50 instances. Moreover, the third battery of instances satisfies that in 30% of the cases the minimal decomposition coincides with the heuristic short decomposition, in 34% of the cases the difference is only one semigroup, in 30% of the cases it is two semigroups, in 4% (two cases) it is three, and in only 2% (one instance) it is four. Note that most of the computations done by using Algorithm 3 may be parallelized by solving in different cores each of the problems (IPm k(x, h)) since they are independent. This could improve the CPU times and sizes of the problems because more than 99% of the time consumed by this algorithm is to solve those problems, while just a little part of the time is spent solving the set covering problem. On the other hand, we have simply implemented the proposed models in XpressMosel, with the default branch-and-bound method. Larger instances could be solved by applying specific more sophisticated integer programming algorithms to solve each one of the problems. 8. Concluding remarks. We present in this paper a new approach to decomposing a numerical semigroup of multiplicity minto the minimum number of mirreducible numerical semigroups. Our methodology is based on translating the problem to the problem of solving an integer programming problem. Hence, this approach connects commutative algebra and discrete optimization. The transformation from the algebraic problem to the optimization formulation uses the notion of the Kunzcoordinates vector of a numerical semigroup that allows us to encode a numerical semigroup of multiplicity mas a vector with m−1 nonnegative integer coordinates. Although we have presented here a method to compute minimal decompositions into m-irreducible numerical semigroups, a similar idea can be applied to decompose a numerical semigroup into (standard) irreducible ones. Note that if we do not fix the multiplicity, we cannot use the Ap´ery set with respect to the multiplicity (and consequently, we cannot use the Kunz-coordinates vector defined in this paper) to encode all the numerical semigroups that may take part in the decomposition. However, Downloaded 02/25/16 to 150.214.182.169. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php