In this paper, we deal with the problem of enforcing diagnosability to labeled Petri nets (PNs) appropriately adding new sensors. We show that, solving an integer linear programming problem, it is possible to select a solution that is optimal with respect to a given objective function (e.g., the cost of sensors). The solution is based on two notions, already introduced by the authors in previous works, namely basis marking and unfolded verifier. This allows to solve the considered problem in a more efficient way with respect to other approaches in the literature. Finally, we propose an algorithm to compute the smallest value of K such that the PN system is K-diagnosable under the new labeling function, which implies that faults can be detected in at most K observations after their occurrence.