In this section, we will give an algorithm that computes an optimal partition for an instance of IP if such a partition exists. We recall that no optimal partition exists in the case that there is no partition that satisfies constraint (5.7) of IP. Section 5.5.1 describes the algorithm IP-opt. Section 5.5.2 shows how IP-opt works for the example of figures 5.2 and 5.4. Finally, in section 5.5.3, we prove that IP-opt is correct.