Constraint-based modeling of steady state metabolic flux is one of the dominant genome scale modeling approaches in computational molecular systems biology. Fundamentally, this dominance can be attributed to the scalability & reliability of the underlying optimization algorithms. Any extension to constraint-based modeling, if it is still to be applicable at genome scale, must retain the scalability & reliability of the underlying algorithms. Extensions to constraint-based modeling, in terms of the scope of molecular mechanisms represented, the timescales involved and the type of constraints represented will be described. As the resulting multiscale constraint-based models challenge the limits of existing optimization software, previous and ongoing efforts to develop suitable optimization algorithms will be summarized. Published applications of the corresponding modeling software will be used to illustrate key concepts and future challenges.