Session: Advances in Discrete Optimization: From Relaxation to Convex Hull Exactness
Chair: Akang Wang
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-k-Cut Problems
Speaker: Yeqing Qiu
Abstract: The Max-k-Cut problem is a fundamental combinatorial optimization challenge that generalizes the classic NP-complete Max-Cut problem. While relaxation techniques are commonly employed to tackle Max-k-Cut, they often lack guarantees of equivalence between the solutions of the original problem and its relaxation. To address this issue, we introduce the Relax-Optimize-and-Sample (ROS) framework. In particular, we begin by relaxing the discrete constraints to the continuous probability simplex form. Next, we pre-train and fine-tune a graph neural network model to efficiently optimize the relaxed problem. Subsequently, we propose a sampling-based construction algorithm to map the continuous solution back to a high-quality Max-k-Cut solution. By integrating geometric landscape analysis with statistical theory, we establish the consistency of function values between the continuous solution and its mapped counterpart. Extensive experimental results on random regular graphs and the Gset benchmark demonstrate that the proposed ROS framework effectively scales to large instances with up to 20,000 nodes in just a few seconds, outperforming state-of-the-art algorithms. Furthermore, ROS exhibits strong generalization capabilities across both in-distribution and out-of-distribution instances, underscoring its effectiveness for large-scale optimization tasks.
Talk 2: Solving Sparse & High-Dimensional-Output Regression via Compression
Speaker: Guanyi Wang
Abstract: Multi-Output Regression (MOR) has been widely used in scientific data analysis for decision-making. Unlike traditional regression models, MOR aims to simultaneously predict multiple real-valued outputs given an input. However, the increasing dimensionality of the outputs poses significant challenges regarding interpretability and computational scalability for modern MOR applications. As a first step to address these challenges, this paper proposes a Sparse & High-dimensional-Output REgression (SHORE) model by incorporating additional sparsity requirements to resolve the output interpretability, and then designs a computationally efficient two-stage framework capable of handling SHORE with provable accuracy via compression on outputs. Theoretically, we show that the proposed framework is computationally scalable while maintaining the same order of training loss and prediction loss before-and-after compression under arbitrary or relatively weak sample set conditions. Empirically, numerical results further validate the theoretical findings, showcasing the efficiency and accuracy of the proposed framework.
Talk 3: On the Exactness of Partial Convexification
Speaker: Rui Chen
Abstract: The idea of partial convexification is very commonly used in discrete optimization and global optimization (e.g., Dantzig-Wolfe decomposition, cutting planes from substructures etc.). We provide sufficient conditions and necessary conditions under which partial convexification gives the exact convex hull. Our results generalize the simplex lemma (folklore), and several known convexification results.
