Optimization Online


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

Aritra Pal(aritra1***at***mail.usf.edu)
Hadi Charkhgard(hcharkhgard***at***usf.edu)

Abstract: 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.

Keywords: bi-objective pure integer linear programming, exact algorithms, heuristic algorithms, parallelization

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 04/26/2018
Entry Accepted: 04/26/2018
Entry Last Modified: 04/26/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society