A sequential deep learning algorithm for sampled mixed-integer optimisation problems

Mixed-integer optimisation problems can be computationally challenging. Here, we introduce and analyse two efficient algorithms with a specific sequential design that are aimed at dealing with sampled problems within this class. At each iteration step of both algorithms, we first test the feasibility of a given test solution for each and every constraint associated with the sampled optimisation at hand, while also identifying those constraints that are violated. Subsequently, an optimisation problem is constructed with a constraint set consisting of the current basis- namely, the smallest set of constraints that fully specifies the current test solution-as well as constraints related to a limited number of the identified violating samples. We show that both algorithms exhibit finite-time convergence towards the optimal solution. Algorithm 2 features a neural network classifier that notably improves the computational performance compared to Algorithm 1. We quantitatively establish these algorithms' efficacy through three numerical tests: robust optimal power flow, robust unit commitment, and robust random mixed-integer linear program.

Automated summary

This article introduces two efficient algorithms for solving mixed-integer optimization problems. These algorithms test the feasibility of a given test solution and identify the violated constraints at each iteration step. Then, an optimization problem is constructed with the current basis and constraints related to the violating samples. The results show that both algorithms converge to the optimal solution in finite time. Algorithm 2, which features a neural network classifier, significantly improves computational performance.