Algorithm behind multi-objective LP

[constantinosTsirogiannis]

Hi all,

Thanks for the great work that you have put in developing HiGHS. Regarding the lexicographic multi-objective feature in LP optimization, I would like to ask the following:

When optimizing for e.g. five objectives, the feature could be implemented by running sequentially five optimizations one after the other, each time optimizing a different objective. Is the current implementation doing this under the hood, or is there a more elaborate method executed which produces the desired result in one go? I had seen previous work on multi-objective simplex using the so-called Grossone method [1] and I was wondering if you are using something similar that provides runtime benefits compared to several sequential runs.

Thanks for your help,

--C

[1] Lexicographic Multi-Objective Linear Programming using Grossone Methodology: Theory and Algorithm, M. Cococcioni, M. Pappalardo, Y.D. Sergeyev

[jajhall]

No, five LPs/MIPs are solved, but sequentially, with the second to fifth having constraints to guarantee that the previous objective values will be within a percentage of their optimal value.

I'll look up the Grossonne approach to see how it differs

[jajhall]

The Grossonne approach is impractical

[constantinosTsirogiannis]

Ok, makes sense. Thanks for the quick reply!