Virtual private network (VPN) design according to a tree topology has been the subject of numerous research papers. Two workload models are commonly used to allow VPN clients to specify the communication capacity they need, the hose and the pipe workload models. As opposed to the pipe model, where bandwidth needs between every pair of endpoints must be specified as a matrix, the hose model has the advantage of simple specification where only one ingress and egress bandwidths per hose endpoint are specified. However, the tree bandwidth costs obtained with the hose workload model are higher by a factor of as much as 2.5 compared to those obtained with pipe workloads Duffield et al. (SIGCOMM Comput Commun Rev 29(4):95108, 1999). In this work, we propose a two-step exact approach to design a VPN tree with minimum bandwidth cost. The first step derives a pipe workload from the user specified hose workload using an exact algorithm. The second step formulates the pipe-based VPN tree bandwidth minimization as a 0–1 integer linear program, which is solved using the exact approach proposed in Thabti et al. (1–6, 2012). The bandwidth costs of VPN trees obtained using this two-step approach are lower by a factor varying between 1.31 and 2.23 compared to VPN trees obtained using the original hose workload. Furthermore, we show that tree solutions obtained using the derived pipe workload satisfy the original hose workload.