Article (Scientific journals)
Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem
Aliev, Iskander; De Loera, Jesus; Louveaux, Quentin
2014In Lecture Notes in Computer Science
Peer reviewed
 

Files


Full Text
reallyFinalIPCO-ilps-with-k-solutions.pdf
Publisher postprint (380.91 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Integer Programming
Abstract :
[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.
Disciplines :
Mathematics
Author, co-author :
Aliev, Iskander;  Cardiff University > Department of Mathematics
De Loera, Jesus;  University of California, Davis - UC Davis > Department of Mathematics
Louveaux, Quentin ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Language :
English
Title :
Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem
Publication date :
June 2014
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer, Berlin, Germany
Special issue title :
Integer Programming and Combinatorial Optimization
Peer reviewed :
Peer reviewed
Available on ORBi :
since 25 April 2014

Statistics


Number of views
88 (1 by ULiège)
Number of downloads
265 (0 by ULiège)

Scopus citations®
 
3
Scopus citations®
without self-citations
2
OpenCitations
 
1

Bibliography


Similar publications



Contact ORBi