MSEA.jl: A Multi-Stage Exact Algorithm for Bi-objective Pure Integer Linear Programming in Julia

We present a new exact method for bi-objective pure integer linear programming, the so-called Multi-Stage Exact Algorithm (MSEA). The method combines several existing exact and approximate algorithms in the literature to compute the entire nondominated frontier of any bi-objective pure integer linear program. Each algorithm available in MSEA has multiple versions in the literature. Hence, the main contribution of our research is developing a united framework for all these versions in MSEA. The proposed method is available as an open source Julia package, named MSEA.jl, in GitHub. The package is compatible with the popular JuMP modeling language and supports input in LP and MPS le formats. The package also supports execution on multiple processors. Another desirable feature of the package is that users (if interested) can easily customize the package for their speci c problems. In other words, users have full control over all settings of the package and they can even call all different versions of the algorithms available in MSEA.jl in any sequence of interest. So, the package has the potential to be used as a research tool for other researchers in order to develop their own custom-built exact solvers. An extensive computational study demonstrates the efficacy of a few settings of MSEA.jl on some existing standard test instances.

Article

Download

View PDF