On the Creation of MipFlex. Extending JuMP and Aiding Solvers With Custom Recognition Procedures.
Abstract
Denne oppgaven tar for seg design og implementasjon av en Julia modul, MipFlex, for å tas i bruk med JuMP, og som har som hensikt å kjenne igjen spesifike lineærprogrammer og løse de med skreddersydde algoritmer. Dette er for å støtte generelle solvere med algoritmer for mindre problem-mengder. Vi tar også for oss en slik gjenkjenningsmetode, og ser på den i dybden. Many feasibility and optimization problems can be expressed as linear programswhen the decision variables form linear constraints and objective functions. In-teger programs; a subclass of problems where one or more decision variableshave to be integer, is appearing a great deal in various industries. Examples ofuse are within production planning, where one cannot produce fractional wares,or within scheduling, where each variable is required to be binary, and, forexample, corresponds to assigning a vehicle to a route or not. Integer program-ming is NP-Complete, and it is therefore made many optimization solvers, bothcommercial and open source, for use in industries. For the commercial ones itis hard to know the exact methods in use, but for the open source we see thatthere often are similar procedures in use, applied to every problem. By craftingprocedures of recognition, we hope to find that more tailored algorithms canspeed up the process of solving specific problem classes. In this research we willtherefore explore how one can make a seamless layer of recognition proceduresfor deciding which algorithms to use, while still being able to use a solver forproblems not recognized by this system. For interacting with solvers one mayuse an algebraic modeling language (AML) in order to formulate the problemsat a higher level, and we argue that a plugin at this level will be able to makethe problem solving as fast, or faster on certain problem domains, as an opensource solver. We will produce the prototype MipFlex, which makes use of Ju-lia’s AML JuMP. We will explore how the layout can be flexible and extendable,and compare how the prototype effects execution time over different problemclasses and solvers. We will also dive into a specific recognition procedure inorder to have a specific use case for MipFlex.