Combinatorial optimization problems are fundamental to modern society, arising across many of its domains. Characterized by inherent complexity and vast search spaces, they are excellent candidates for resolution on quantum computers. Variational quantum algorithms are among the most promising near-term approaches. A survey of the literature reveals a set of de facto standards: algorithms such as QAOA and VQE, problem formulations such as QUBO, and benchmark problems such as MaxCut constitute the common baseline against which contributions are measured and the standard starting point for newcomers. This thesis proposes a shift away from the currently dominant approach, aiming toward algorithms that are operative on present-day hardware.