Linear programming with inequality constraints treated lexicographically

Question

I'm trying to solve optimization problems of the form: $\min\{cx|Ax\preceq b,\;x\geq 0\}$, where $\preceq$ means lexicographic order; that is, the set of linear inequalities need only to be satisfied lexicographically. I'm guessing these inequalities are treated conditionally by means of binary variables thus transforming the problem into a mixed integer linear program. I'm also aware of the more direct approach, which is solving a sequence of linear programs, starting with $\min\{cx|A_{1}x\leq b_{1},\;x\geq 0\}$ and continuing with linear programs of the form $\min\{cx|A_{i}x=b_{i},\;A_{k}x\leq b_{k},\;1\leq i<k,\;x\geq 0\}$ whenever the inequality constraint at $k-1$ is satisfied in strict equality.

I'm interested in a solution by means of binary variables if there is any, or any other approach. Thanks in advance for your help.

Answer 1

If you want to have only initial constraints to be strictly equal and rest of them should be strictly less

First, add regular constraints: $$ A_i x \le b_i $$ Next, add checks for equality as in https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ : $$ e_i = A_i x \stackrel{?}{=} b_i $$ Finally, we want only some initial of these variable to be true, and for that we can use material implication as in https://blog.adamfurmanek.pl/2015/08/22/ilp-part-1/ : $$ e_{i+1} \implies e_i = 1 $$ or we can simply add the following constraints: $$ e_{i+1} \le e_i $$

Disclaimer: I am the author of the blog posts but I don't want to advertise here, only include them as a reference.

If you want some initial of the constraints to be strictly equal, the next one should be strictly less, and rest of them can be not satisfied

Do not add any regular constraints.

Create equality constraints as before: $$ e_i = A_i x \stackrel{?}{=} b_i $$

Calculate prefix conjunction of equality constraints: $$ E_i = e_1 \wedge e_2 \wedge \ldots \wedge e_{i} $$

Variables $E_i$ indicates whether first $i$ constraints are strictly equal.

Next, calculate less than constraints: $$ l_i = A_i x \stackrel{?}{<} b_i $$

Finally, make sure that after $i$ initial strictly equal constraints there is a strictly less constraint or another strictly equal constraint satisfied: $$ E_i \implies \left( l_{i+1} \vee E_{i+1} \right) = 1 $$

Answer 2

One possible solution aside from solving the sequence of linear programs could be solving the following MILP, in which $\epsilon$ is a very small positive number and $M$ a big one: $$ \min cx\\ \text{s.t.}\quad Ax+s=b\\ \epsilon y_{1}\leq s_{1}\leq My_{1}\\ -M y_{1}+\epsilon y_{2}\leq s_{2}\leq M y_{2}\\ \vdots\\ -M (y_{1}+y_{2}+...+y_{m-1})+\epsilon y_{m}\leq s_{m}\leq M y_{m}\\ y_{1},y_{2},\ldots,y_{m}\in \{0,1\}\\ x\geq 0 $$ As I said in the above comment. This allows to solve the more general problem $\min\{cx|A^{1}x\{\preceq \text{or}\succeq\}b^{1},A^{2}x\{\preceq \text{or}\succeq\}b^{2},…,A^{l}\{\preceq \text{or}\succeq\}b^{l},x\geq0\}$; which, I believe, cannot be solved sequentially. Nevertheless, I have not been able to test it exhaustively, so if anyone can spot errors or maybe find a better way, I would be very grateful.