The benefits of applying multi-objective optimization (MOO) in building design have been increasingly recognized in recent decades. The existing or traditional computational design optimization (CDO) approaches mostly focus on optimization problem solving (OPS), as they often conduct optimizations directly by assuming the optimization problems in question are good enough. In contrast, the computational design exploration (CDE) approaches defined in this research mainly focus on optimization problem formulation (OPF), which are considered more essential and aim to achieve or ensure appropriate optimization problems before conducting optimizations. However, the application of the CDE is very limited especially in conceptual architectural design. The necessity of re-formulating original optimization problems and its potential impacts on optimization results are often overlooked or not emphasized enough. This paper proposes a new CDE approach that highlights the knowledge-supported re-formulation of a changeable initial optimization problem. It improves upon the traditional CDO approach by introducing a changeable initial OPF and inserting a CDE module. The changeable initial OPF allows expanding the dimensionality of an objective space and design space being investigated, and the CDE module can re-formulate the changeable optimization problem using the information and knowledge extracted from statistical analyses. To facilitate designers in achieving the proposed approach, an improved computational platform is used which combines parametric modeling software (including simulation plug-ins) and design optimization software. Assisted by the platform, the proposed approach is applied to the conceptual design of an indoor sports building that considers multi-disciplinary performance criteria (including architecture-, climate- and structure-related criteria) and a wide range of geometric variations. Through the case study, this paper demonstrates the use of the proposed approach, verifies its benefits over the traditional method, and unveils the factors that may affect the behaviour of the proposed approach. Besides, it also shows the suitability of the computational platform used.