Datapath continues to consume relatively large amounts of silicon area, delay and power within digital signal processing and graphics applications. Arithmetic blocks consume a major portion of chip area, delay and power. The arithmetic Sum-Of-Product (SOP) is a widely used block. The authors introduce a novel Binary integer Linear Program (BLP) based algorithm for optimizing a general class of mutually exclusive SOPs. Benchmarks drawn from existing literature, standard APIs and constructed for demonstration purposes, exhibit speed improvements of up to 16% and area reduction of up to 57% in a 65nm TSMC process.