Lexicographic objective to maximize the x-th highest value

Question

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?

Answer 1

As Mark L. Stone notes, some solvers (including CPLEX) handle lexicographic optimization directly. If you are using a solver that does not, but does allow you to modify branching, pruning etc. using callbacks, you can try your own implementation. I think the key is that, when you find a new incumbent solution, you prune those nodes for which the bound on the primary objective is strictly worse than the value of the new incumbent but leave alive nodes where the bound ties the new incumbent (nodes that ordinarily would be pruned). You can extend this down the line of objectives (e.g., nodes where the bounds on the first two objectives tie the new incumbent but are worse on the the third objective can be pruned).