AI/ML Framework for Mixed-integer Nonlinear Optimization

Project description

Mixed-integer nonlinear optimization is one of the most generic optimization frameworks. Important applications in healthcare, manufacturing, logistics, etc. involve nonlinear (objective and/or constraint) functions and discrete decision variables. These problems can be modeled as mixed-integer nonlinear programming problems (MINLPs). Despite advances in optimization theory and computing systems, MINLPs constitute the most challenging optimization problems due to the presence of discontinuous/disconnected feasible regions and integer constrained variables. Algorithms for MINLPs aim to sequentially improve upper and lower bounds on the optimal objective function value. State-of-the-art algorithms for MINLPs are based on branch-and-bound, which involves recursively partitioning the problem into smaller subproblems (known as branching) to obtain lower bounds (known as bounding). The algorithm terminates when these bounds converge or when no subproblems remain to be explored. This process is represented as a tree where different nodes denote subproblems and edges denote branches. The ability to exclude or prune subproblems that will not yield an optimal solution makes branch-and-bound practically better than complete enumeration. Branching decisions at various iterations of the algorithm impacts the size of the branch-and-bound tree, and in turn, the overall time taken by the algorithm. Some branching schemes have been proposed in the literature e.g. strong branching, reliability branching, that use information generated in the previous iterations of the algorithm (e.g. the changes in lower bound, pseudocosts, etc.). On similar lines, AI/ML techniques have been incorporated to arrive at good branching decisions recently. This project will involve: (1) Developing a reinforcement learning (RL) framework for branching within the branch-and-bound algorithm. This will involve modeling branch-and-bound as a Markov Decision Process (MDP), and subsequently, learning an agent that decides the evolution of the tree. (2) Using AI/ML techniques to improve other algorithmic decisions within MINLP algorithms. (3) Implementation of the above techniques in Minotaur – an open source MINLP framework, and benchmarking the performance with other state-of-art solvers.

Outcomes

Outcomes and deliverables: 1) A fast, learning-based framework for integer programming algorithms. 2) Improved performance of the branch-and-bound based algorithms in terms of tree-size and/or computational time. 3) High quality research papers in leading AI/ML/optimization journals/conferences. 4) Contribution to open-source learning-based algorithms for MINLPs. 5) Benchmarking state-of-art MINLP solvers with the algorithms developed in this project.

Essential capabilities

Calculus, Linear Algebra, Probability and Statistics

Desireable capabilities

Mathematical optimization, Machine Learning, Programming

Expected qualifications (Course/Degrees etc.)

BTech (or equivalent degree) in relevant engineering stream OR MSc in Maths/Operations Research/Statistics or other relevant streams