Many practical applications in control require that constraints on the inputs and states of the system are respected, while some performance criterion is optimized. In the presence of model uncertainties or disturbances, it is often sufficient to satisfy the state constraints for at least a prescribed share of the time, such as in building climate control or load mitigation for wind turbines. For such systems, this paper presents a new method of Scenario-Based Model Predictive Control (SCMPC). The basic idea is to optimize the control inputs over a finite horizon, subject to robust constraint satisfaction under a finite number of random scenarios of the uncertainty and/or disturbances. Previous SCMPC approaches have suffered from a substantial gap between the rate of constraint violations specified in the optimal control problem and that actually observed in closed-loop operation of the controlled system. This paper identifies the two theoretical explanations for this gap. First, accounting for the special structure of the optimal control problem leads to a substantial reduction of the problem dimension. Second, the probabilistic constraints have to be interpreted as average-in-time, rather than pointwise-in-time. Based on these insights, a novel SCMPC method can be devised for general linear systems with additive and multiplicative disturbances, for which the number of scenarios is significantly reduced. The presented method retains the essential advantages of the general SCMPC approach, namely a low computational complexity and the ability to handle arbitrary probability distributions. Moreover, the computational complexity can be adjusted by a sample-and-remove strategy. (C) 2014 Elsevier Ltd. All rights reserved.