search

anriseth / MultiJuMP.jl

MultiJuMP enables the user to easily run multiobjective optimisation problems and generate Pareto fronts.
Other
61 stars 11 forks source link

Benson's algorithm #1

Open blegat opened 8 years ago

blegat commented 8 years ago

Do you think it would be possible to support Benson's algorithm (in a similar way to bensolve) in MultiJuMP when the model is detected to be linear ? It could be done using Polyhedra.jl. Benson's algorithm has a nice application for the Entropic Cone :-P

anriseth commented 8 years ago

I don't know exactly how Benson works, but if it has some iterative process of linear solves and dual solves that can be passed to JuMP - that should be fine. We'd need to create a new linear multi-objective type as well.

matbesancon commented 5 years ago

I'm gonna give this a try. @blegat you didn't work on it on your side?

blegat commented 5 years ago

Not at all, please do :) IIRC for the best performance, the double description method shouldn't restart the computation from scratch when intersecting with an halfspace. For this reason, bensolve includes a modified version of CDD which does this. We could make the change to https://github.com/JuliaPolyhedra/cddlib but it might be easier to apply it to pure Julia implementations of the double description such ashttps://github.com/JuliaPolyhedra/ConvexHull.jl and https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/master/src/doubledescription.jl (which is used by the default library). Note that ConvexHull should be much faster than the default while https://github.com/JuliaPolyhedra/Polyhedra.jl/issues/25 are not implemented. IIRC @joehuchette told me that what's missing in ConvexHull to be as fast as CDD is implementing ordering heuristics for halfspaces (see e.g. sections 4.1 and 4.2 of http://cgm.cs.mcgill.ca/~avis/doc/avis/ABS96a.ps) but for Benson's algorithms it might be less of an issue because the ordering of the halfspaces is fixed (we do not have a list to add at the beginning but we have a new one everytime we solve an LP then we add it then we resolve the LP, ...)