Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We propose a modified Lagrangian relaxation which used in (linear) combinatorial optimization with equality constraints generates an optimal intinteger solution. We call this new concept semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem.