For setup violations you need to reduce the datapath delay, which is what datapath optimization does, or decrease the clock speed. For hold violations , you generally need to delay the clock, which can be done by adding delay in the clock path, or by using useful skew.
I believe there are two different cases of hold time violations. One is known as the max delay problem. This can be corrected by using a longer time period for the clock. Another is the minimum delay problem. For this you need to find the path that has minimum delay and insert delay elements on this path to ensure that the signal arrives at a particular point at the same time as rest of the signals.