The Support Of Integer Optimal Solutions

The support of a vector is the number of nonzero components. We show that given an integral mxn matrix A, the integer linear optimization problem max {c(T) x : Ax = b, x >= 0, x is an element of Z(n)} has an optimal solution whose support is bounded by 2m log(2 root m parallel to Lambda parallel to(infinity)), where parallel to Lambda parallel to(infinity) is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent of the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.


Publié dans:
Siam Journal On Optimization, 28, 3, 2152-2157
Année
Jan 01 2018
Publisher:
Philadelphia, SIAM PUBLICATIONS
ISSN:
1052-6234
1095-7189
Mots-clefs:
Laboratoires:




 Notice créée le 2018-12-13, modifiée le 2019-06-19


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)