Semigroups -- a computational approach

MaRDI QIDQ4627687zbMATH OpenFDO

Authors Florian Kohl, YanXi Li, Johannes Rauh, Ruriko Yoshida

Publication date 11 March 2019

Full work available at URL https://arxiv.org/abs/1608.03297

zbMATH Keywords

feasibility problemlattice pointspolytopessoftware

Mathematics Subject Classification ID

Linear Diophantine equations (11D04) Lattice points in specified regions (11P21) Computer solution of Diophantine equations (11Y50) (n)-dimensional polytopes (52B11) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Abstract: The question whether there exists an integral solution to the system of linear equations with non-negative constraints, $$, where $$ and $$, finds its applications in many areas, such as operation research, number theory and statistics. In order to solve this problem, we have to understand the semigroup generated by the columns of the matrix $A$ and the structure of the "holes" which are the difference between the semigroup generated by the columns of the matrix $A$ and its saturation. In this paper, we discuss the implementation of an algorithm by Hemmecke, Takemura, and Yoshida that computes the set of holes of a semigroup, % generated by the columns of $A$ and we discuss applications to problems in combinatorics. Moreover, we compute the set of holes for the common diagonal effect model, and we show that the $n$th linear ordering polytope has the integer-decomposition property for $nleq7$. The software is available at url{http://ehrhart.math.fu-berlin.de/People/fkohl/HASE/}.

Recommendations

• Computing holes in semi-groups and its applications to transportation problems
• scientific article; zbMATH DE number 1797658
• Semigroup ideals and linear Diophantine equations
• Computing with semigroups in GAP. -- A tutorial
• A generalization of the integer linear infeasibility problem

Cited in

(12)

• Computing finite commutative semigroups. II.
• Automorphism groups and normal forms in Normaliz
• Factorization length distribution for affine semigroups. II: Asymptotic behavior for numerical semigroups with arbitrarily many generators
• On decomposable semigroups and applications.
• Semigroups of RN-algorithms
• Computing holes in semi-groups and its applications to transportation problems
• scientific article; zbMATH DE number 6129506 (Why is no real title available?)
• Computation of atomic fibers of \(\mathbb Z\)-linear maps
• Graded local cohomology of modules over semigroup rings
• Computing automorphisms of semigroups.
• A generalization of the integer linear infeasibility problem
• Digital representation of semigroups and groups

Describes a project that uses

Uses Software

• Macaulay2
• Normaliz
• lp_solve
• 4ti2
• HASE

This page was built for publication: Semigroups -- a computational approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4627687)