fellow enthusiasts of mathematical optimization!

I'm delving into a fascinating scenario within the realm of linear programming (LP) and am curious about degenerate solutions and their potential in multi-objective or hierarchical optimization contexts. Consider the following setup:

Let us define vectors $x, c_1 \in \mathbb{R}^n$, a matrix $A \in \mathbb{R}^{m \times n}$, and vectors $l, u \in \mathbb{R}^m$, where we the convex polyhedral set $X = {x \in \mathbb{R}^n : l \leq Ax \leq u}$ is non-empty and compact. Given this, we explore a degenerate linear program:

$$ \min{c^T_1 x}\\ l \le Ax \le u $$ that is, the minimum of $c_1^T x$ over $X$ results in a subset $X_1 \subseteq X$, specifically, a face of the convex polyhedron $X$.

Here's where it gets intriguing: this scenario, often seen as undesirable due to its degeneracy, opens up a unique opportunity. What if we could use this "degenerate" solution space, $X_1$, to then optimize a second cost function, $c_2^T x$, under the same constraints? That is

$$ \min{c^T_2 x}\\ x\in X1 $$

Moreover, if this subsequent problem also results in degeneracy, it might allow for sequential optimization of further cost functions, and so on.

This layered approach to optimization seems akin to hierarchical or multi-objective optimization strategies. However, despite my efforts, I've struggled to find literature that explicitly discusses this method of exploiting degenerate LP solutions for sequential cost function optimization.

Does anyone here have insights, references, or thoughts on this approach? Specifically, I'm looking for theoretical frameworks, practical applications, or any studies related to leveraging degeneracy in LP for multi-objective or hierarchical optimization purposes.

Thank you in advance for your contributions and guidance!


1 Answer 1


I think you are mentioning a special case of linear bilevel programming, and this book could serve you as a starting point: A Gentle and Incomplete Introduction to Bilevel Optimization by Yasmine Beck and Martin Schmidt. Visit especially Section 6 for some algorithms designed for linear bilevel problems.


You must log in to answer this question.

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