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

Question

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$?

Answer 1

While The bound given by @SilvioM in comments has polynomial size in A,b,c as requested, one cannot expect a polynomial time approximation for ILPs (see the second paragraph), and hence, probably also not an an upperbound polynomial in OPT. So this is probably as good as it gets.

The reason for this is that the well-known formulation of TSP as ILP is clearly a reduction from TSP to ILP. Since the general TSP does not admit a constant factor approximation, even when all weights are inegers (try to find a gap-reduction from Hamiltonian Cycle as a homework), and since this reduction clearly preserves approximation (since any feasible solution of one of them is a feasible solution of the other having the same target value), this excludes a constant factor approximation unless P=NP.