This repository contains the source code used in the computational experiments of the paper: Learning to Solve Bilevel Programs with Binary Tender (available on OpenReview.net [https://openreview.net/pdf?id=PsDFgTosqb]).
In this paper, we develop deep learning techniques to address this challenge. Specifically, we consider a BP with binary tender, wherein the upper and lower levels are linked via binary variables. We train a neural network to approximate the optimal value of the lower-level problem, as a function of the binary tender. Then, we obtain a single-level reformulation of the BP through a mixed-integer representation of the value function. Furthermore, we conduct a comparative analysis between two types of neural networks: general neural networks and the novel input supermodular neural networks, studying their representational capacities. To solve high-dimensional BPs, we introduce an enhanced sampling method to generate higher-quality samples and implement an iterative process to refine solutions.
The code environment is Python 3.7. Before you use the code, ensure you have met the following requirements:
- You have installed optimization modeling packages cvxpy and pyomo.
- You have access to Gurobi. It is used as the optimization solver for the final mixed-integer linear program in the code.
- For directly solving bilevel programs, you need to install the pao package and the MibS solver.
LP instances are randomly generated by the function InstanceLP.InstanceGen() in the file Instance.py.
MILP instances are obtained by keeping the parameters of LP instances but restricting corresponding variables to be integer or binary.
The instances used in the paper are provided in the folder instances.
The driver of the computation is the file main.py.
num_x indicates the scale of instances and solverName indicates the solver used to solve bilevel programs.
There are four solvers for selection, 'HPR' for high-point relaxation, 'MIBS' for the existing MibS solver, 'GNN' for our method with general neural network, and 'ISNN' for our method with input supermodular neural network.
By switching from solveByNN(solverName) to solveByNNEnhanced(solverName) in the function InstanceLP.solve(solverName), we enable the enhanced sampling.