# Can we compute in polynomial time, an upper bound on an optimal solution of an integer linear program?

Consider the following integer linear program (where $$A$$ is an integer matrix, $$b$$ an integer vector, and $$c$$ a positive integer vector): $$\text{minimize}~~~ c\cdot x \\ \text{subject to}~~~ A\cdot x \geq b, ~~~ x\geq 0, ~~~ x~\text{is an integer vector.}$$ Denote its optimal value by $$OPT(A,b,c)$$. Computing $$OPT(A,b,c)$$ is NP-hard in general. We are interested in computing an upper bound on $$OPT(A,b,c)$$, that is, a number $$M = MAX(A,b,c)$$ such that $$OPT(A,b,c) \leq M$$, and the size of $$M$$ (in bits) is polynomial in the size of $$A,b,c$$.

Is there an algorithm that, given $$A,b,c$$, computes such an upper bound $$MAX(A,b,c)$$ in time polynomial in the size of $$A,b,c$$?

• I thought about it, but as far as I know, duality gives me a lower bound for my problem, not an upper bound. Maybe you have an idea how to get an upper bound for a minimization problem using duality? Commented May 3, 2023 at 6:23
• What would you want such M to be if the ILP is infeasible?
– JimN
Commented May 4, 2023 at 17:07
• @SamuelBismuth, can't you consider the relaxation of the dual of your problem? Since the dual is a maximization problem (and the optimums coincide), when you relax the constraints you are going to find an upper bound on the optimum of the original minimization problem. Commented May 4, 2023 at 18:03
• @Steven The maximum of the fractional dual problem (maximization) is equal to the minimum of the fractional primal problem (minimization), which is smaller than the minimum of the integral primal problem. Therefore, it is a lower bound and not an upper bound. Commented May 12, 2023 at 8:53
• @BernardoSubercaseaux yes, this special case could be interesting. Commented Sep 28, 2023 at 10:13