Network Functions Virtualization (NFV) enables the complete decoupling of network functions from proprietary appliances and runs them as software applications on general- purpose servers. Service Function Chains (SFC) are paths with an ordered sequence of network functions that have to be processed. In this paper, we consider the problem of reconfiguring SFCs with the goal of bringing the network from a sub-optimal to an optimal operational state. We propose optimization models based on the make-before-break mechanism, in which a new SFC is set up before the old one is torn down. Our method takes into consideration the chaining requirements of the flows and scales well with the number of nodes in the network. We show that, with our approach, the network operational cost defined in terms of both bandwidth and installed network function costs can be reduced and a higher acceptance rate can be achieved.