Tools and Techniques for Efficient Encoding and Analysis of Linear Programming Models

Mathematical programming provides a powerful framework for modelling and optimising complex systems that typically involve multiple interrelated activities, e.g, several companies, actors or physical systems interacting together. From industrial production to energy planning, optimising these systems require determining an optimal sequence of actions that transition the system from an initial state toward a defined goal.

The mathematical programming workflow typically consists of four key steps. First, we formulate the problem in terms of parameters, variables, constraints and an objective function. As some parameters are unknown, or uncertain, assumptions need to be made on their value. Second, we encode this problem in a modelling tool that converts the encoding into a representation that can be processed by solvers. Third, the solvers solve the problem and return a solution to the modelling tool which outputs it. Finally, the solution is analysed, often through sensitivity analyses, to assess the impact of assumptions on the optimal outcome.

In this thesis, we focus on linear programming, a subclass of mathematical programming that enables the efficient tackling of large problems while still providing a good approximation of their behaviour. The main goal of this thesis is to find methods and tools to make the encoding and the analysis faster and easier for users. Hence, the focus of this PhD thesis is on the second and fourth steps of the workflow.

First, we introduce a modelling tool, the Graph-Based Optimisation Modelling Language (GBOML), and its innerworkings. GBOML is a modelling language designed to take advantage of the inherent structure of systems of interrelated activities. GBOML enables the encoding of these problems as hierarchical hypergraphs made-up of nodes and hyperedges. The tool puts a clear emphasis on reuse, modularity and component assembling with an encoding close to the mathematical one. In \autoref{chap:gboml}, we present the tool and show how we can leverage this structure encoding to ease model formulation, generate instances faster and even sometimes improve solving time.

Second, there exist multiple methods to assess the impact of parameter uncertainty on the objective function and right-hand side but not much on the constraint matrix coefficients. In \autoref{chap:bounds} and \autoref{chap:warm}, we propose two novel approaches for handling changes in constraint coefficients: a bounding method that provides strong guarantees on objective function behaviour and a warm-starting approach that accelerates re-optimisation.

Throughout this thesis, we highlight not only our contributions and their impact on performance but also avenues for future research in both modelling and sensitivity analysis.