Light-EvoOPT: A Lightweight Evolutionary Optimization Framework for Ultralarge-Scale Mixed Integer Linear Programs
提出一个轻量级进化优化框架，通过问题划分、小样本初始解预测、变量与约束约简及轻量级优化器，在超大规模问题上以千分之一训练数据超越Gurobi等先进求解器。
Machine Learning (ML)-based optimization frameworks emerge as a promising technique for solving large-scale Mixed Integer Linear Programs (MILPs), as they can capture the mapping between problem structures and optimal solutions to expedite their solution process. However, existing solution frameworks often suffer from high model computation costs, incomplete problem reduction, and reliance on large-scale solvers, leading to performance bottlenecks in ultra-large-scale problems with complex constraints. To address these issues, this paper proposes Light-EvoOPT, a Lightweight Evolutionary Optimization Framework for Ultra-Large-Scale Mixed Integer Linear Programs, which can be divided into four stages: (1) Problem Formulation for problem division to reduce model computational costs, (2) Model-based Initial Solution Prediction for predicting and constructing the initial solution using a small-scale training dataset, (3) Problem Reduction for both variable and constraint reduction, and (4) Evolutionary Optimization for current solution improvement employing a lightweight optimizer. Experiments on four benchmark datasets with tens of millions of variables and constraints and a real-world problem show that the proposed framework based on the sole use of a lightweight optimizer, trained on only one-thousandth of the scale of ultra-large-scale problems, is able to outperform state-of-the-art ML-based frameworks and advanced solvers (e.g. Gurobi) within a specified computational time, validating the feasibility and effectiveness of our proposed ML-based evolutionary optimization framework for ultra-large-scale MILPs.