Hierarchical multi-objective linear programming

Hierarchical (or lexicographic) multi-objective linear programming is when you have more than one linear objective, and you optimize them in order.

Gurobi’s documentation states that it supports this.

How can I do this in Julia, using any of the packages for linear programming (Gurobi.jl, MathProgBase, JuMP, etc.)? Do any of them offer a way to do this?

From the documentation I think that JuMP does not support hierarchical multi-objective linear programming… Will it be supported in the near future?

JuMP itself doesn’t support multiple objectives, and I don’t know of any extensions that add support either. I don’t think any of the core developers are likely to add this feature in the foreseeable future. However, it should be relatively straightforward to 1) build a JuMP extension for modeling multiple objectives, and 2) wrapping the necessary methods in the Gurobi C interface.

-Joey

@joehuchette I guess one has to start by adding this feature in Gurobi.jl. I’ll have to inspect the code and figure out where it should be done.

Right now I’m trying to do this “by hand” with JuMP. Basically, I am solving the first LP with the primary objective. Then I add a constrain to fix this to the optimal value, and optimize the secondary objective.

This approach seems to have numerical issues, since I am getting that the second optimization is infeasible (I know it isn’t). Any ideas of what I could do as a workaround?

https://github.com/anriseth/MultiJuMP.jl

@odow It doesn’t seem to support hierarchical LP.

https://github.com/JuliaOpt/Gurobi.jl/issues/82

https://github.com/JuliaOpt/Gurobi.jl/pull/86

Hi.

We are developping vOptSolver (https://github.com/vOptSolver), and methods for the lexicographic optimization (for 2 and 3 linear objectives) will be available soon (we are testing and documenting the code now) with vOptGeneric (GitHub - vOptSolver/vOptGeneric.jl: Solver of multiobjective linear optimization problems (MOMIP, MOLP, MOIP, MOCO): generic part).

  • modeling: JuMP has been extended to deal with multiple linear objectives
  • solving: your favorite MILP solver callable by JuMP (it will be tested with GLPK and CPLEX)

Xavier

2 Likes

@XavierG Nice! Will you be able to handle hierarchical multiple objectives with GLPK? Because I think GLPK does not support this natively.

You mean that a recent version of JuMP now supports multi-objectives? I did not find it.

Indeed, with vOptGeneric, the user describes the MOIP model with JuMP, and solves it with a MILP embedded into an exact and classic MOP algorithm among:

  • epsilon-constraint (=> Y_N : all non-dominated points)
  • Chalmet algorithm (=> Y_N : all non-dominated points)
  • dichotomic (Aneja-Nair algorithm) (=> Y_{SN} : all supported points)
  • lexicographic method (=> Y_{Lex} : lex points)
    These algorithms make calls to the MILP.

We have modified JuMP; now multiple objectives may be defined and handled by the mentioned algorithms. See here for examples:

https://github.com/vOptSolver/vOptSolver/blob/master/examples/examples.pdf
https://github.com/vOptSolver/vOptSolver/blob/master/talks/IFORS2017/ifors2017.pdf