Substitution boxes (S-boxes) are vital in symmetric-key cryptography, and reconstructing them from partial cryptographic information is a crucial, yet computationally challenging problem. Although recent methods have made progress in reconstructing S-boxes from partial characteristic tables using the mixed integer linear programming (MILP) method, they suffer from efficiency issues and can often recover only one valid S-box. In this work, we propose a new MILP-based approach to this reconstruction problem from the perspective of Boolean functions. Our method significantly improves the efficiency of solving the problem on the linear approximation table (LAT) and the differential-linear connectivity table (DLCT) by decoupling the reconstruction of the S-box into the reconstruction of its coordinate Boolean functions. This allows us to reconstruct all matching S-boxes from partial LAT or DLCT, even for reconstructing 8-bit S-boxes from LAT. Additionally, we introduce a new MILP formulation for handling reconstruction based on the boomerang connectivity table (BCT) using only linear constraints, which enhances performance over previous quadratic models. Our approach can also be adapted to search for S-boxes with specified cryptographic properties. Notably, we find six S-boxes with differential uniformity 4, which are CCZ-inequivalent to the 6-bit Inverse S-box and have linearity 16, demonstrating the power and versatility of our method.