Discrete support vector machines (DSVM) are recently introduced classifiers that might be preferable to the standard support vector machine due to a more appropriate modeling of classification errors. However, this advantage comes at the cost of an increased computational effort. In particular, DSVM rely upon a mixed-integer program, whose optimal solution is prohibitively expensive to obtain. Therefore, heuristics are needed to construct respective classifiers. This paper proposes a novel heuristic incorporating recent advances from the field of integer programming and demonstrates its effectiveness by means of empirical experimentation. Furthermore, the appropriateness of the DSVM formulation is examined to shed light on the degree of agreement between the classification aim and its implementation in form of a mathematical program.