We have the following linear program:

$ \max \;\{ d^Tx \; | \; Ax \le b, x \ge 0 \; \} $

This is our abstract definition of a linear program (maximize). Assume this linear program has an optimal solution. The lexicographical program is now defined as follows:

$ \max \;\{c^Tx\; | \; x \in \arg \max \;\{ d^Tx \; | \; Ax \le b, x \ge 0 \; \} \}$

Now i want to reformulate this second program, the lexicographical one in a equivalent linear program, but i dont have a clue. Can somebody give me a hint or an idea?


1 Answer 1


You can add the constraint that there exists is a dual variable $y$ for the first problem such that $d^T x \geq b^T y$. The full problem becomes: $$\max\{c^T x \mid Ax\leq b, \; d^T x \geq b^T y, \; A^Ty \geq d, \; x \geq 0, \; y \geq 0\}.$$

  • $\begingroup$ Thank you, it's completely right. :) $\endgroup$
    – Sven
    Commented May 6, 2018 at 13:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .