Exploiting structure in MILP: a modeler’s perspective

Many real-life problems can be tackled as Structured Mixed Integer Linear Programs(MILP). The workflow when dealing with MILPs usually involves two tools: a modelling tool and a solver. This presentation focuses on modelling tools. Most modelling tools either enable an encoding close to the mathematical one but lack support for structures or offer predefined components to assemble but adding components or modifying them is difficult. In this lecture, we explain the advantages of having a mixed approach by illustrating with the Graph-Based Optimization Modelling Language (GBOML). GBOML is a modelling tool that combines the strengths of both worlds. It supports structure and offers an encoding close to the mathematical one and library-like functionalities such as reuse and component assembling. We explain how exploiting structure can lead to a natural encoding of problems, faster time to build the intermediate representation and sometimes faster solving time. We explain how GBOML takes advantage of its structure to perform vectorization and parallelization. We propose a benchmark of GBOML, JuMP, Plasmo and Pyomo on a published energy problem tacked as a structured MILP. We show that GBOML and JuMP take a similar time to build the intermediate representation and outperform Plasmo and Pyomo. With parallelism, GBOML outperforms the three tools. In terms of memory footprint, GBOML uses the least memory. The presentation ends with some open directions of research.