The structure of an integral monoid and integer programming feasibility

DOI10.1016/0166-218X(90)90006-XMaRDI QIDQ2277141zbMATH OpenOpenAlexFDO

Authors Jennifer K. Ryan

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(90)90006-x

zbMATH Keywords

group structureHilbert baseinteger linear programmingintegral monoidtesting feasibility

Mathematics Subject Classification ID

Integer programming (90C10)

Review text

An integer programming problem is feasible if the right-hand side vector belongs to the integral monoid generated by columns of the left-hand side matrix. The author investigates a group structure on the elements of the monoid situated in the boxes restricted by at most \(k\) (\(k\) is a constant depending on the matrix) summand columns of the matrix and suggests a method for testing feasibility. The method is more efficient for problems with fixed matrix and varying right-hand side.

Recommendations

• Decomposing finitely generated integral monoids by elimination
• A simple test for integer programming problems with bounded integer variables
• scientific article; zbMATH DE number 4204116
• Parametric integer programming in fixed dimension
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem

Cites work

• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3445421 (Why is no real title available?)
• The constraints of the group of an integral monoid
• The value function of an integer program
• Total dual integrality and integer polyhedra
• Weyl-minkowski duality for integarl monoids^*

Cited in

(7)

• Decomposing finitely generated integral monoids by elimination
• Testing integer knapsacks for feasibility
• On a transport problem and monoids of non-negative integers
• The constraints of the group of an integral monoid
• A simple test for integer programming problems with bounded integer variables
• Computing holes in semi-groups and its applications to transportation problems
• Intermediate feasibility in 0–1 integer linear systems

This page was built for publication: The structure of an integral monoid and integer programming feasibility

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