FPBH: A Feasibility Pump based Heuristic for Multi-objective Mixed Integer Linear Programming

Build Status:

Documentation:

DOI:

This is a LP based heuristic for computing an approximate nondominated frontier of a Multi-objective Mixed Integer Linear Program. Important characteristics of this heuristic are:

FPBH targets Julia 1.10+ and uses modern JuMP/MathOptInterface-compatible LP optimizers.

1. Can solve any (both structured and unstructured) multiobjective mixed integer linear problem. The following problem classes are supported:
   1. Objectives: 2 or more linear objectives
   2. Constraints: 0 or more linear (both inequality and equality) constraints
   3. Variables:
      1. Binary
      2. Integer variables (via reformulation into binary variables)
      3. Continuous + Binary
      4. Continuous + Integer variables (via reformulation into binary variables)
2. A multiobjective mixed integer linear instance can be provided as a input in 4 ways:
   1. ModoModel - an extension of JuMP Model
   2. LP file format
   3. MPS file format
   4. Matrix Format ( Advanced )
3. Any linear programming solver supported by MathOptInterface (MOI) can be used. No mixed integer programming solver is required. FPBH.jl has first-phase tested support for:
   1. GLPK.jl
   2. Clp.jl
   3. SCIP - v4.0.0
   4. Gurobi - v7.5
   5. CPLEX - v12.7. If CPLEX is available, we highly recommend using FPBHCPLEX.jl instead.
4. All parameters are already tuned, only timelimit is required.
5. Supports parallelization

Supporting and Citing:

The software in this ecosystem was developed as part of academic research. If you would like to help support it, please star the repository as such metrics may help us secure funding in the future. If you use Modof.jl, Modolib.jl, FPBH.jl, FPBHCPLEX.jl or pyModofSup.jl software as part of your research, teaching, or other activities, we would be grateful if you could cite:

1. Pal, A. and Charkhgard, H., A Feasibility Pump and Local Search Based Heuristic for Bi-objective Pure Integer Linear Programming.
2. Pal, A. and Charkhgard, H., FPBH.jl: A Feasibility Pump based Heuristic for Multi-objective Mixed Integer Linear Programming in Julia

Contributions

This package is written and maintained by Aritra Pal. Please fork and send a pull request or create a GitHub issue for bug reports or feature requests.