Cryogenic air separation, while widely used in industry, is an energy intensive process. Effective design can improve efficiency and reduce energy consumption, however, uncertainties can make determination of the optimal design difficult. This paper addresses the conceptual design of cryogenic air separation process under uncertainty. A rigorous, highly nonlinear model of three integrated columns is developed to capture the coupled nature of the process. The multi-scenario approach is used to incorporate the uncertainty, giving rise to a nonlinear programming problem with over half a million variables. Nevertheless, this problem is solved efficiently using IPOPT, demonstrating the effectiveness of interior-point methods on complex, large-scale nonlinear programming problems. The optimal design from the multi-scenario approach is compared against the optimal design using nominal parameter values. As expected, the results using the multi-scenario approach are more conservative than the nominal case; however, they may be less conservative than traditional overdesign factors. (C) 2010 Elsevier Ltd. All rights reserved.