Light-EvoOPT: A Lightweight Evolutionary Optimization Framework for Ultralarge-Scale Mixed Integer Linear Programs

Huigen Ye

doi:10.1109/TEVC.2025.3550668

2025-03-12

PRE

Huigen Ye

徐

徐华 (Hua Xu)

Carlos A. Coello Coello

DOI：10.1109/TEVC.2025.3550668

原文链接

原文求助

摘要

En 中文

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 ultralarge-scale problems with complex constraints. To address these issues, this article proposes Light-EvoOPT, a Lightweight Evolutionary Optimization Framework for Ultralarge-Scale MILPs, 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 ultralarge-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 ultralarge-scale MILPs.

Keyword:

Evolutionary optimization

graph neural network (GNN)

mixed integer program

ultralarge-scale