1. Curbing habitat loss, reducing fragmentation, and restoring connectivity are frequent concerns of conservation planning. In this respect, the incorporation of spatial constraints, fragmentation, and connectivity indices into optimization procedures is an important challenge for improving decision support.

2. Here we present a novel optimization approach developed to accurately represent a broad range of conservation planning questions with spatial constraints and landscape indices. Relying on constraint programming, a technique from artificial intelligence based on automatic reasoning, this approach provides both constraint satisfaction and optimality guarantees.

3. We applied this approach in a real case study to support managers of the ``Côte Oubliée -- `Woen Vùù -- Pwa Pereeù'' provincial park project, in the biodiversity hotspot of New Caledonia. Under budget, accessibility, and equitable allocation constraints, we identified restorable areas optimal for reducing forest fragmentation and improving inter-patch structural connectivity, respectively measured with the effective mesh size and the integral index of connectivity.

4. Synthesis and applications. Our work contributes to more effective and policy-relevant conservation planning by providing a spatially-explicit and problem-focused optimization approach. By allowing an exact representation of spatial constraints and landscape indices, it can address new questions and ensure whether the solutions will be socio-economically feasible, through optimality and satisfiability guarantees. Our approach is generic and flexible, thus applicable to a wide range of conservation planning problems such as ecological restoration planning, reserve or corridor design.