LEMON: Landscape-Equivalent Continuous Relaxation for Multi-State Optimization

Many combinatorial problems require assigning one of several discrete values to each variable, with an objective that couples pairs or larger groups of variables. Finding an assignment that globally minimizes this objective is often intractable, so a practical alternative is to seek one that cannot be improved by changing a single variable. Searching for such assignments can still be expensive, motivating the use of continuous relaxations and gradient-based optimization. The challenge is that local minima of a relaxation need not correspond to locally optimal discrete assignments. We introduce LEMON (Landscape Equivalent Multi-State Optimization), a continuous relaxation that preserves this correspondence. We represent each discrete variable by a probability vector over its possible values. The discrete objective is then extended to these vectors and augmented with a regularization term that promotes discrete assignments. Our main result shows that the local minima of the resulting continuous objective correspond exactly to the local optima of the original discrete problem. LEMON uses a projected variant of ADAM to optimize the probability vectors, decodes them into a discrete assignment, and then checks feasibility and local optimality. We evaluate LEMON on maximum independent set, graph coloring, Max-$k$-Cut, and $k$-way number partitioning. It matches the reference optimum on $53/61$ maximum independent set instances and achieves the known chromatic number on $27/30$ coloring instances. It also closely matches public-best Max-$k$-Cut values and outperforms specialized number-partitioning baselines, while certifying local optimality across all tasks.