Abstract Operator-counting is a recently developed framework for analysing and integrating many state-ofthe-art heuristics for planning using Linear Programming. In cost-optimal planning only the objective value of these heuristics is traditionally used to guide the search. However the primal solution, i.e. the operator counts, contains useful information. We exploit this information using a SATbased approach which given an operator-count, either finds a valid plan; or generates a generalized landmark constraint violated by that count. We show that these generalized landmarks can be used to encode the perfect heuristic, h? , as a Mixed Integer Program. Our most interesting experimental result is that finding or refuting a sequence for an operator-count is most often empirically efficient, enabling a novel and promising approach to planning based on Logic-Based Benders Decomposition (LBBD). This paper originally appeared at ICAPS 2015 and is reproduced with the permission of the Association for Artificial Intelligence ([Davies et al., 2015] Copyright 2016 AAAI, all rights reserved.)