Reference : Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doigno...
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem
Aliev, Iskander [Cardiff University > Department of Mathematics > > >]
De Loera, Jesus [University of California, Davis - UC Davis > Department of Mathematics > > >]
Louveaux, Quentin mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Lecture Notes in Computer Science
Integer Programming and Combinatorial Optimization
[en] Integer Programming
[en] In this paper we study a generalization of the classical fesibility problem in integer linear programming, where an ILP needs to have a prescribed number of solutions to be considered solved.
We first provide a generalization of the famous Doignon-Bell-Scarf theorem: Given an integer k, we prove that there exists a constant c(k, n), depending only on the dimension n and k, such that if a polyhedron {x : Ax ≤ b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions.
The second contribution of the article presents a structure theory that characterizes precisely the set Sg≥k (A) of all vectors b such that the problem Ax = b, x ≥ 0, x ∈ Zn , has at least k-solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computation. Similar results can be derived for those right-hand-side vectors that have exactly k solutions or fewer than k solutions.
Finally we show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of Sg≥k(A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have exactly k solutions (similarly for at least k or less than k solutions). Under the same assumptions we prove that the k-Frobenius number can be computed in polynomial time.

File(s) associated to this reference

Fulltext file(s):

Open access
reallyFinalIPCO-ilps-with-k-solutions.pdfPublisher postprint371.98 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.