The identification of effective and long-lasting cancer therapies still remains elusive, partially due to patient and tumor heterogeneity, acquired drug resistance, and single-drug dose-limiting toxicities. The use of drug combinations may help to overcome some limitations of current cancer therapies by challenging the robustness and redundancy of biological processes. However, effective drug combination optimization requires the careful consideration of numerous parameters. The complexity of this optimization problem is clearly nontrivial and likely requires the assistance of advanced heuristic optimization techniques. In the current review, we discuss the application of optimization techniques for the identification of optimal drug combinations. More specifically, we focus on the application of phenotype-based screening approaches in the field of cancer therapy. These methods are divided into three categories: (1) modeling methods, (2) model-free approaches based on biological search algorithms, and (3) merged approaches, particularly phenotypically driven network biology methods and computation network models relying on phenotypic data. In addition to a brief description of each approach, we include a critical discussion of the advantages and disadvantages of each method, with a strong focus on the limitations and considerations needed to successfully apply such methods in biological research.