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

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:

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 MathProgBase.jl can be used. No mixed integer programming solver is required. FPBH.jl automatically installs GLPK and Clp by default. If the user desires to use any other LP solver, it must be separately installed. FPBH.jl has been successfully tested with:

   1. GLPK - v4.61

   2. Clp - v1.16

   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

Contents:

• Installation:
• If CPLEX is available:
• If CPLEX is not available:
• Getting Started
• Warm Up FPBH:
• Using JuMP Extension:
• Using LP File Format
• Using MPS File Format
• Using the Matrix Format - Advanced
• Advanced Features:
• Using multiple processors:
• Tuning parameters
• Solving multiobjective optimization instances from literature using Modolib.jl:
• Biobjective assignment problems:
• Biobjective 1-D knapsack problems:
• Biobjective 2-D knapsack problems:
• Biobjective set covering problems:
• Biobjective set packing problems:
• Biobjective mixed binary problems:
• Biobjective uncapacitated facility location problems:
• Triobjective assignment problems:
• Triobjective 1-D knapsack problems:
• Triobjective mixed binary problems:

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.