An integer program optimizes an objective under constraints with some or all variables restricted to integers. Its continuous relaxation removes those integrality restrictions; a relaxed optimum bounds the integer optimum in the appropriate direction.
