This repository provides the official implementation of our paper: "Learning to Optimize for Mixed-Integer Nonlinear Programming"
Our approach introduces the first general Learning-to-Optimize (L2O) framework designed for Mixed-Integer Nonlinear Programming (MINLP). As illustrated above, the approach consists of two core components: integer correction layers and integer feasibility projection.
Traditional solvers struggle with large-scale MINLPs due to combinatorial complexity and non-convexity. With up to tens of thousands of discrete variables, traditional solvers and heuristics even fail to find a feasible solution. Our framework leverages deep learning to predict high-quality solutions with an orders-of-magnitude speedup, enabling optimization in scenarios where exact solvers fail.
- π€ Self-supervised learning: Eliminates the need for optimal solutions as labels.
- π’ Efficient integer correction: Ensures integer feasibility through a learnable correction layer.
- π― Efficient feasibility correction: Refine constraints violation via a gradient-based post-processing.
- π Scalability: Handles problems with up to 20,000 variables within subsecond inference.
@article{tang2024learning,
title={Learning to Optimize for Mixed-Integer Non-linear Programming},
author={Tang, Bo and Khalil, Elias B and Drgo{\v{n}}a, J{\'a}n},
journal={arXiv preprint arXiv:2410.11061},
year={2024}
}
Our recent talk will be at the ICS 2025. You can view the talk slides here.
Our approach introduces two key components:
We design two learnable integer correction layers to enforce integrality in the neural network output. The figures below illustrate the workflow of integer rounding correction.
- Rounding Classification (RC): Learns a classification strategy to determine rounding directions for integer variables.
- Learnable Thresholding (LT): Learns a threshold value for each integer variable to decide whether to round up or down.
While the correction layers enforce integer constraints, feasibility with respect to problem constraints is not guaranteed. We introduce a gradient-based projection that iteratively refines infeasible solutions. The figure below illustrates how the projection step adjusts a solution over multiple iterations.
By integrating feasibility projection with our integer correction layers, we extend RC and LT into RC-P and LT-P, respectively. These extended methods leverage the projection step to correct infeasibilities while preserving the advantages of fast inference and high-quality integer solutions.
Our learning-based methods (RC & LT) achieve comparable or even superior performance to exact solvers (EX) while being orders of magnitude faster. The figures below illustrate the impact of penalty weights on feasibility and objective values for smaller-scale problems:
The top plots show the proportion of feasible solutions, while the bottom plots display objective values. For these instances, EX finds the best feasible solutions within 1000 seconds (leftmost boxplot in the bottom plots), serving as a benchmark. With properly tuned penalty weights, our approach attains comparable or better objective values within just subsecond, demonstrating its efficiency and effectiveness.
To run this project, you will need the following libraries and software installed:
- Python: The project is developed using Python. Ensure you have Python 3.9 or later installed.
- PyTorch: an open source deep learning (ML) framework for creating deep neural networks.
- Scikit-Learn: an open-source machine learning library for the Python programming language.
- NeuroMANCER: an open-source differentiable programming (DP) library for parametric constrained problems.
- Pyomo: a Python-based open-source optimization modeling language for mathematical programming.
- Gurobi: a state-of-the-art solver for mathematical programming.
- SCIP: a fast non-commercial solvers for mixed-integer linear and non-linear programming (MILP/MINLP).
- IPOPT: an open source software package for large-scale nonlinear optimization.
- NumPy: a library to support high-level mathematical operations for large, multi-dimensional arrays and matrices.
- Pandas: a fast, powerful, flexible and easy to use open source data analysis and manipulation tool.
- tqdm: a Python library that provides a fast, extensible progress bar for loops and iterables.
βββ test # Some testing and visualization with Jupyter notebooks
βββ img # Image resources for the project
βββ src # Main source code directory
β βββ __init__.py # Initializes the src package
β βββ heuristic # Modules for the heuristics
β βββ __init__.py # Initializes the heuristics submodule
β βββ rounding.py # Heuristics for rounding
β βββ resolve.py # Heuristics for resolving some problem
β βββ func # Directory for function modules
β βββ __init__.py # Initializes the function submodule
β βββ layer.py # Pre-defined neural network layers
β βββ ste.py # Straight-through estimators for non-differentiable operations
β βββ rnd.py # Modules for differentiable and learnable rounding
β βββ proj.py # Modules for differentiable and learnable projection (archived)
β βββ postprocess # Modules for the postprocessing
β βββ __init__.py # Initializes the postprocessing submodule
β βββ project.py # postprocessing for the feasibility projection
β βββ problem # Modules for the benchmark of constrained optimization
β βββ __init__.py # Initializes the problem submodule
β βββ math_solver # Collection of Predefined SCIP solvers
β βββ __init__.py # Initializes the mathematical solver submodule
β βββ abc_solver.py # Abstract base class for solver implementations
β βββ quadratic.py # SCIP model for Integer Quadratic Problems
β βββ nonconvex.py # NeuroMANCER map for Integer Non-Convex Problems
β βββ rosenbrock.py # SCIP model for Mixed-Intger Rosenbrock Problems
β βββ neuromancer # Collection of Predefined NeuroMANCER maps
β βββ __init__.py # Initializes the NeuroMANCER map submodule
β βββ quadratic.py # NeuroMANCER map for Integer Quadratic Problems
β βββ nonconvex.py # NeuroMANCER map for Integer Non-Convex Problems
β βββ rosenbrock.py # NeuroMANCER map for Mixed-Intger Rosenbrock Problems
β βββ utlis # Utility tools such as data processing and result test
β βββ __init__.py # Initializes the utility submodule
β βββ data.py # Data processing file
β βββ solve_test.py # Testing functions to evaluate optimization solution
βββ run_qp.py # Script to run experiments for Integer Quadratic Problems
βββ run_nc.py # Script to run experiments for Integer Non-Convex Problems
βββ run_rb.py # Script to run experiments for Mixed-Integer Rosenbrock Problems
βββ README.md # README file for the project
Our framework sup 7E43 ports three benchmark problems:
- Integer Quadratic Problems (IQP): A convex quadratic objective with linear constraints and integer variables.
- Integer Non-Convex Problems (INP): A more challenging variant incorporating trigonometric terms, introducing non-convexity.
- Mixed-Integer Rosenbrock Problems (MIRB): A benchmark derived from the Rosenbrock function with linear and non-linear constraints.
To reproduce experiments, use the following commands:
--size: Specifies the problem size. Larger values correspond to more decision variables.--penalty: Sets the penalty weight for constraint violations (default: 100).--project:Enables feasibility projection as a post-processing step.
python run_qp.py --size 5python run_nc.py --size 10 --penalty 1 --projectpython run_rb.py --size 100 --penalty 10 --project