This study presents an algorithmic approach for optimal placement of phasor measurements units (PMUs) to ensure complete observability in the presence of conventional measurements and zero injection buses. The financial or technical restrictions prohibit the deployment of PMUs at every bus, which in turn motivates their strategic placement around the power system. Topology-based transformations are implemented for observability analysis. Τhe PMU problem allocation is optimized based on measurement observability criteria for achieving solvability of the power state estimation. The Branch-and-Bound algorithm (BB) and Binary-Coded Genetic algorithm (BCGA) are applied to solve the optimization problem. The BCG algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a penalty parameter approach for handling constraints. The proposed algorithms detect the minimum PMU number and their locations required to make the power system numerically observable. The proposed algorithms are applied to IEEE systems as well as a large-scale system with 1011 buses to exhibit the applicability of them to practical power systems. The solution points located using the BCGA are interpreted as nonstrict global minima since they are in complete agreement with those obtained by the BB algorithm in solving the (zero-one) constraint integer linear program.