Announcing new Packages and Solvers for Multi-objective Mixed Integer Programming ( with JuMP extension )

Specific Domains Optimization (Mathematical)
1

Hi everyone,

I am excited to announce 5 new packages for solving Multiobjective Mixed Integer Linear Programs:

  1. FPBH.jl: It is a linear programming based heuristic for computing an approximate nondominated frontier of any (both structured and unstructured) multiobjective mixed integer linear program in Julia.
    1. It has been successfully tested on nearly 700 (both structured and unstructured) instances, including instances up to 5 objectives, > 1000 constraints, > 10000 variables
    2. It is compatible with JuMP and supports LP and MPS file formats
    3. No mixed integer programming solver is required and any linear programming solver supported by MathProgBase.jl can be used. It has been tested with GLPK, CLP, SCIP, Gurobi and CPLEX
    4. All parameters are already tuned, only timelimit is required.
    5. Supports parallelization
  2. FPBHCPLEX.jl: It is an efficient implementation of FPBH.jl for CPLEX using CPLEX.jl and CPLEXExtensions.jl.
  3. Modof.jl: It is a framework used for solving multiobjective mixed integer programs in Julia. It can:
    1. handle multiple linear objectives using ModoModel ( a JuMP extension )
    2. select, sort, write and normalize a nondominated frontier
    3. compute ideal and nadir points of a nondominated frontier
    4. compute the closest and the farthest point from the ideal and the nadir points
    5. compute quality of a nondominated frontier (hypervolume, cardinality, coverage and uniformity)
    6. includes wrappers for (tested only on linux): MDLS (for multidimensional knapsack and biobjective set packing problems) and NSGA-II (for biobjective binary programs)
  4. Modolib.jl: It is a collection of instances and their efficient frontiers (if available) of various classes of multiobjective mixed integer programs. Around 700 instances with their true frontiers (biobjective assignment, knapsack, set covering, set packing, mixed binary and uncapacitated facility location; multiobjective assignment, knapsack and mixed binary) are included. It can also generate different classes of random multiobjective mixed integer programs commonly used in the literature.
  5. Modoplots.jl: It is a Julia package capable of plotting nondominated frontiers of biobjective and triobjective optimization problems.

A small example:

Solving the following multi-objective mixed integer linear program using FPBH.jl and Clp as the underlying LP Solver:

using Modof, JuMP, FPBH, Clp

model = ModoModel()
@variable(model, x[1:2], Bin)
@variable(model, y[1:2] >= 0.0)
objective!(model, 1, :Min, x[1] + x[2] + y[1] + y[2])
objective!(model, 2, :Max, x[1] + x[2] + y[1] + y[2])
objective!(model, 3, :Min, x[1] + 2x[2] + y[1] + 2y[2])
@constraint(model, x[1] + x[2] <= 1) 
@constraint(model, y[1] + 2y[2] >= 1)

@time solutions = fpbh(model, lp_solver=ClpSolver(), timelimit=10.0, threads=1)

For users interested in the algorithm and the supporting results, we refer them to:

  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
5 Likes
2

Very cool! It’s clear a lot of work has gone into making reusable software, and I hope others find it useful.

For cross referencing, this isn’t the only JuMP extension for multiobjective MILP (Hierarchical multi-objective linear programming - #7 by XavierG), but the more the merrier as far as I’m concerned.

You should be aware that substantial changes will be needed to update your JuMP extension for JuMP 0.19. We have a lot on our plate at the moment, but post JuMP 0.19 we can also consider extending MathOptInterface to support multiple objectives, so that in the future no JuMP extensions would be needed to model multiobjective problems.

1 Like
3

@miles.lubin Thank you!. I also hope that other users find it useful.

If MathOptInterface can support multiple objectives, that will be great.

Another great feature would be, if MathOptInterface can support deleting constraints and modifying rhs and lhs of certain constraints without having to rebuild the model every time from scratch. This feature would significantly improve the performance of FPBH.jl as it has to solve a lot of LPs. This is one of the major difference between FPBH.jl and FPBHCPLEX.jl, as in the latter case the LP model is created only once ( for each worker ) and is reused through out the whole algorithm.

Once a stable release of MathOptInterface and JuMP 0.19 is available, I will start porting FPBH.jl from MathProgBase.jl to MathOptInterface.

4

Another great feature would be, if MathOptInterface can support deleting constraints and modifying rhs and lhs of certain constraints without having to rebuild the model every time from scratch.

This is already included in MOI.

1 Like
5

Dear all,
very nice to see the efforts invested for dealing with multi objective models. With vOptGeneric (part of vOptSolver), a bi-objective linear assignment is formulated with JuMP (extended) as follow:

n  =  3
C1 = [  3    9   7   ;  16   10   6   ;   2    7  11  ]
C2 = [ 16   15   6   ;   5    7  13   ;  1    2  13  ]
using vOptGeneric
using GLPK ; using GLPKMathProgInterface
m = vModel( solver = GLPKSolverMIP() )
@variable( m , x[1:n,1:n] , Bin )
@addobjective( m , Min, sum( C1[i,j]*x[i,j] for i=1:n,j=1:n ) )
@addobjective( m , Min, sum( C2[i,j]*x[i,j] for i=1:n,j=1:n ) )
@constraint( m , cols[i=1:n], sum(x[i,j] for j=1:n) == 1 )
@constraint( m , rows[j=1:n], sum(x[i,j] for i=1:n) == 1 )
@time solve( m , method = :epsilon , step = 0.5 )
print_X_E(m)
getY_N(m)

In this example, the instance is solved with the epsilon-constraint method calling the MIP solver of GLPK.

Several others algorithms have been integrated to the solver this summer. I am currently writting the documentation (the next release is coming soon). More: see tutorial, exemples, and talk(s) on github / project: vOptSolver.

2 Likes