# Lexicographic objective to maximize the x-th highest value

Given the following (stylized) IP:

\begin{align} \mbox{minimize }& \sum_i c_ix_i&\\ \mbox{s.t. }&\sum_i x_i \leq Q & \\ & f(x_i) \geq L & \forall i \\ & 0 \leq x_i \leq d_i & \forall i\\ & x_i \ \textrm{integer} & \forall i \end{align} where $$f(x_i)=x_i/d_i$$, and $$c_i$$, $$d_i$$, $$L$$, $$Q$$ are constants.

An optimal solution to this model has objective value $$C^*$$, and guarantees that $$f(x_i) \geq L$$ for all $$i$$. There can exist multiple alternative optimal solutions (all with the same objective value $$C^*$$). What I'm interested in is finding the optimal solution that first maximizes the lowest $$f(x_i)$$ across all $$i$$, then maximizes the second lowest $$f(x_i)$$ across all $$i$$ and so on.

One potential solution approach is the following:

• Find all unique optimal solutions $$S$$ with objective value $$C^*$$. Then simply pick the best solution by ranking all solutions in $$S$$.

To find all unique optimal solutions, we would have to iteratively solve the IP. Each time we find a solution, we add a nogood cut to cut off the last found solution. The process stops when the objective drops below $$C^*$$ after which we've found all optimal solutions.

Toy example - Given 3 different solutions $$S_k$$ with values $$f(x_{i_1})$$, $$f(x_{i_2})$$, $$f(x_{i_3})$$

S_1 = 0.4, 0.2, 0.55
S_2 = 0.25, 0.4, 0.3
S_3 = 0.25, 0.25, 0.7


Solutions $$S_2$$ and $$S_3$$ are better than $$S_1$$ because the lowest $$f(x_i)$$ in $$S_2$$ and $$S_3$$ (0.25) is higher than the lowest $$f(x_i)$$ in $$S_1$$ (0.2). Next, solution $$S_2$$ is better than $$S_3$$ because the second lowest $$f(x_i)$$ in $$S_2$$ (0.3) is higher than the second lowest $$f(x_i)$$ in $$S_3$$ (0.25).

Is there a more efficient way to find this solution that does not require generating all optimal solutions and then ranking them, e.g. through a lexicographic search? E.g. we could solve:

\begin{align} \mbox{maximize }& y&\\ \mbox{s.t. }&\sum_i x_i \leq Q & \\ & \sum_i c_i x_i = C^* & \forall i \\ & y \leq f(x_i) & \forall i \\ & 0 \leq x_i \leq d_i & \forall i\\ & x_i integer & \forall i\\ & y \geq 0 & \end{align}

To find an optimal solution that maximizes the lowest $$f(x_i)$$. But how do we then proceed to find the solution that also maximizes the second lowest, then the third lowest value of $$f(x_i)$$, etc?

• Some solvers have built-in lexicographic optimization capabilities. For instance, gurobi.com/documentation/current/refman/… Commented Jun 4 at 15:46
• @MarkL.Stone maybe I'm missing something trivial but for this problem I don't know how to express the objective as a series of lexicographic functions? Commented Jun 4 at 15:52
• @JorisKinable You can linearize the objective of maximizing the sum of the $k$ smallest $f_i(x)$. See or.stackexchange.com/a/8986/500. Then you can take the sum of the $k=1$ smallest as your first objective, sum of the $k=2$ smallest as your second objective, etc. Commented Jun 4 at 16:25