This paper develops a place invariant based deadlock prevention method to obtain an optimal, i.e., maximally permissive, liveness-enforcing Petri net supervisor with a minimal supervisory structure that means the minimal number of control places. Maximal permissiveness can be achieved by designing place invariants that make all legal markings reachable while all first-met bad markings unreachable. An integer linear programming problem is formulated to compute all place invariants and its objective function minimizes the number of place invariants, aiming to yield a minimal supervisory structure. Importantly, we develop a technique to greatly improve the efficiency of the proposed method by reducing the number of constraints and variables in the integer linear programming problem under consideration. A number of examples from the literature are used to illustrate the proposed approaches. (C) 2012 Elsevier Ltd. All rights reserved.