Suppose we have a linear program of the form $$\min_{x} c^T x$$ for $c \in \mathbb{R}^n, x \in \mathbb{R}^N$, subject to the constraints
- $$x_i \leq x_j \qquad \forall (i, j) \in \Gamma$$
- $$-1 \leq x_i \leq 1 \qquad \forall i$$
where $\Gamma$ is some index set consisting of pairs $(i, j)$. Here, the constraints only consist of inequalities between decision variables $x_i$, and restrictions on the domain of $x_i$.
Currently, I trying to model the constraints as a graph of inequalities between the $x_i$, where an edge $x_i \rightarrow x_j$ denotes that $x_i \leq x_j$. We can then reduce the size of the linear program by quotienting over strongly connected components, since variables in the same strongly connected component are equal.
My question:
- Are there any further ways to reduce the size of this program?
- Are any greedy strategies to solve this linear program in strongly polynomial time?
You can check for vertices that have only incoming our outgoing edges. Say vertex $i$ only has outgoing edges. Then if $c_i \geq 0$, without loss of generality, you may set $x_i = -1$. Then you can remove these vertices from the graph, along with their edges, and check if there's any new vertices with only outgoing edges.
A similar procedure can be done for vertices with only incoming edges. And you can combine them both to reduce your graph even more.