Decision-makers across many professions are often required to make multi-objective decisions over increasingly larger volumes of data with several competing criteria. Data visualization is a powerful tool for exploring these complex 'solution spaces', but there is limited research on its ability to support multi-objective decisions. In this article, we explore the effects of chart complexity and data volume on decision quality in multi-objective scenarios with complex trade-offs. We look at the impact of four common multidimensional chart types (scatter plot matrices, parallel coordinates plots, heat maps, radar charts), the number of options and dimensions and participant chart usage experience on decision time and accuracy when selecting the 'optimal option'. As objectively evaluating the quality of multi-objective decisions and the trade-offs involved is challenging, we employ rank- and score-based accuracy metrics. While heat maps demonstrate a time advantage, our findings show no strong performance benefit for one chart type over another for accuracy. We find mixed evidence for the impact of chart complexity on performance, with our results suggesting the existence of a 'ceiling' in the number of dimensions considered by participants. This points to a potential limit to data complexity that is useful for decision making. Lastly, participants who use charts frequently performed better, suggesting that users can potentially be trained to effectively use complex visualizations in their decision-making.