Software systems, and automotive software in particular, are becoming increasingly configurable to fulfill customer needs. New methods such as product line engineering facilitate the development and enhance the efficiency of such systems. In modern, versatile systems, the number of theoretically possible variants easily exceeds the number of actually built products. This produces two challenges for quality assurance and especially testing. First, the costs of conventional test methods increase substantially with every tested variant. And secondly, it is no longer feasible to build every possible variant for the purpose of testing. Hence, efficient criteria for selecting variants for testing are necessary. In this contribution, we investigate the cost drivers of testing multivariable systems and define novel criteria to systematically sample variants for the purpose of testing. The presented criteria reduce the test effort by means of tested variants as well as executed test steps. At the same time, we are able to maintain a high level of test quality by means of fault detection capability. We achieve this by designing tests for individual features and store variability information about required, excluded, and optional features within each test case. Hence we are able to drive the sampling process from the test cases’ configurations. Six optimization criteria enable control of test effort and test quality by sampling different amounts of variants for testing. This approach is inherently different to conventional design methods, where firstly variants are selected for testing and then test cases are designed for each variant. We demonstrate the feasibility of our approach and compare the results to established testing methods for multivariable systems.