  Typical behavior of the linear programming problem (LP) is studied as a
relaxation of the minimum vertex cover problem, which is a type of the integer
programming problem (IP). To deal with the LP and IP by statistical mechanics,
a lattice-gas model on the Erd\"os-R\'enyi random graphs is analyzed by a
replica method. It is found that the LP optimal solution is typically equal to
that of the IP below the critical average degree c*=e in the thermodynamic
limit. The critical threshold for LP=IP is beyond a mathematical result, c=1,
and coincides with the replica-symmetry-breaking threshold of the IP.
