Mixed-integer multi-level optimization through multi-parametric programming
Creators: name: Avraamidou, Styliani
Publisher: name: Imperial College London
Year: 2018

description: Optimization problems involving a set of nested optimization problems over a single feasible region are referred to as multi-level programming problems. The control over the decision variables is divided among different optimization levels, but all decision variables can affect the objective function of all optimization levels. This class of problems has attracted considerable attention across a broad range of research communities, including economics, sciences and engineering. Multi-level programming problems are very challenging to be solved even when considering just two linear decision levels. For classes of problems where the lower level problems also involve discrete variables, the difficulty is further increased, typically requiring global optimization methods for its solution. In this thesis, we present novel algorithms for the exact and global solution of different classes of multi-level programming problems containing both integer and continuous variables at all optimization levels, namely (i) bi-level mixed-integer linear programming problems, (ii) bi-level mixed-integer quadratic programming problems, (iii) tri-level mixed-integer linear and quadratic programming problems, (iv) bi-level multi-follower mixed-integer linear and quadratic programming problems and (v) multi-level non-linear programming problems. Based on multi-parametric programming theory, the main idea behind the algorithms presented in Chapters 3, 5 and 6, is to recast the lower level problems as multi-parametric programming problems, in which the optimization variables of the upper level problems are considered as parameters for the lower level. The proposed algorithms are implemented in a MATLAB based toolbox, B-POP, presented in Chapter 4, and computational studies were performed to highlight the capabilities of the algorithms. B-POP was found to be much more efficient for the solution of multi-level mixed-integer linear problems than the quadratic ones. The number of constraints was also a key factor for the difficulty of each test problem, and it was shown that by increasing the number of constraints the time required to solve the bi-level problems is increased. For all classes of problems solved, it was clearly observed that the limiting step of the algorithms, and more time consuming, is the solution of the lower level multi-parametric problem. A data-driven algorithm for the solution of large scale bi-level mixed-integer non-linear programming problems is presented in Chapter 7. The main idea behind this algorithm is to approximate the bi-level problem into a single level problem by collecting data from the optimality of the lower level problem. This algorithm was tested by solving a set of bi-level test problems from the literature. The algorithm was able to converge to the global solution for many problems, and was able to find a near optimal or sub-optimal feasible solution for the rest of the problems. Furthermore, multi-level programming was applied to a variety of real-world problems, including classical bi-level problems such as the integration of production planning and distribution planning, and other novel applications such as a hierarchical economic model predictive controller and a class of robust optimization.