Add support for lexicographic optimization

[Nodrance]

My problem is something like
3a + b >= 14
10 - a + c >= 0
3 - b + 2d >= 0
4 - c - d >= 0
all variables are nonnegative
I want to optimize for a, and in cases where a is maximized, further optimize for d (alternatively, "optimize for a, tiebreaker d". I could just do something like objective = a*10000 + c but I want this to work for an arbitrary number of nested tiebreakers and not need finely tuned weights. For example in a problem with coefficients as large as 10,000, you might get a case where optimizing for c actually beats out optimizing for a because 10,000 is no longer a big enough gap.

Is this possible within this framework? Is it possible in general?

[KnorpelSenf]

This crate does not implement multi-objective optimisation but you can work around it as follows:

1. Run the solver, optimising for a
2. Add a constraint to the problem that fixes a at or near the optimum
3. Run the solver, optimising for d
4. Repeat for every nested tiebreaker

This means that for n tiebreakers you must run the solver n times.

[KnorpelSenf]

Hint: consider adding your n-th solution as an initial solution for the (n+1)-th run of the solver

[Nodrance]

Thank you so much @KnorpelSenf I got it all figured out thanks to your comment

If this does get added as a feature, .optimize(cond1).optimize(cond2) feels like natural syntax for this, or .optimize(cond1).futher_optimize(cond2) if you want to be explicit about OoO.

[KnorpelSenf]

@lovasoa is this in scope? If yes, how should we deal with the native support provided by some commercial solvers? Adjust the bindings for them and then fall back to manual iteration for others?

[lovasoa]

Yes, if someone can make a clean pr with support for this it would be welcome. It would have to be well tested with all solvers including on edge cases, to ensure numerical precision issues do not lead to infeasible problems at some point during the process.

[KnorpelSenf]

I think some solvers like Gurobi support multiple objectives out of the box. Should that feature be used for such solvers, or do you want to have an implementation that is consistent across all solvers (always runs the solver multiple times)?