Phononic crystals are periodic structures known for their abilities to alter the propagation of acoustic or elastic waves, and their characteristics are greatly dependent on the topological configurations of constituent materials within the unit cell. Thus it is possible to engineer a phononic crystal for specific functionality by tailoring its topology. Low manufacturing cost as well as light weight gives porous phononic crystals advantages over other kinds of phononic structures. This paper presented a bi-directional structural optimization (BESO) method in conjunction with homogenization theory for the systematic design of porous phononic crystals. On account of sustaining static loads, a bulk or shear modulus constraint is considered in the design of porous phononic structures. A multi-objective optimization was conducted to simultaneously maximize combined band gap width and bulk or shear modulus with a prescribed volume fraction of consisting solid material. The methodology was briefly introduced and several optimized porous phononic structures with exceptionally large band gaps were presented.