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.


Published in:
Siam Journal On Optimization, 28, 3, 2152-2157
Year:
Jan 01 2018
Publisher:
Philadelphia, SIAM PUBLICATIONS
ISSN:
1052-6234
1095-7189
Keywords:
Laboratories:




 Record created 2018-12-13, last modified 2019-02-25


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)