© 2019 Elsevier B.V. Multi-objective evolutionary algorithms (MOEAs) are a widely accepted choice for the numerical treatment of multi-objective optimization problems (MOPs). For constrained problems, however, these methods still have room for improvement to compute satisfactory approximations of the solution sets. A possible remedy is the hybridization of MOEAs with specialized local search mechanisms; which is not a simple task due to their high cost. In this work, we consider the information of the constraints when performing the local search, and propose a new and effective way to compute descent directions for constrained bi-objective optimization problems. Since the directions are computed via neighborhood sampling, the method is perfectly suited for the use within MOEAs or any other population based algorithm as the samples can be taken precisely from the populations. The new method can be used as local search engine within, in principle, any MOEA. As demonstrator, we will consider two particular hybrids. Numerical results on some benchmark problems support the benefits of the novel approach. Though this work focuses on the bi-objective case, this represents an important step to formalize gradient-free multi-objective descent directions and its efficient interleaving into MOEAs.