A policy management server manages a segmentation policy and policy constraints. The segmentation policy comprises a set of segmentation rules that each permit connections between specified groups of workloads that provide or consume network-based services. The policy constraints comprise a set of constraint rules that determine compliance of the segmentation rules. A workflow process may be initiated to resolve non-compliant rules by enabling an administrator to approve or deny the rule. In a large enterprise managing significant numbers of workloads, the policy constraints may be employed to ensure that overly permissive segmentation rules are not being created. This facilitates creation of a robust and narrowly tailored segmentation policy that reduces exposure of the enterprise to network-based security threats.