I have an optimization problem that in most respects can be very elegantly expressed via linear programming.
The twist is that I don't actually want to minimize or maximize any of my variables; I want to find the center of the feasible region.
The problem is coming up with a definition of "center" that I can optimize for using an LP solver.
I started out by finding the Chebyshev center; that works for larger feasible regions but many of my feasible regions I'm interested in are extremely long and narrow. I'd like something that's more logically in the "middle" than a Chebyshev sphere can give. An added bonus would be something that still works if one of my constraints is actually an equality (essentially specifying a hyperplane through my problem space), so that it can find the center of the hyperplane within the space. The Chebyshev approach can't do this at all.
As an example problem: I'd like to find the "center" of the region specified by:
x >= 0
x <= 100
y >= 0
y <= 100
x + y >= 90
x + y <= 100
Graph is here
Ideally, I'd like the solution to be x=47.5, y=47.5; however, everything I've thought of so far gives me something either with a very small x or a very small y.
Best Answer
The only way I think you can use a quickly solvable linear programming formulation to find something close to a center would be to take your "truly free" inequalities in the form $Ax \leq b$, i.e. after all the implicit equations $Cx = d$ have been identified and removed from the inequalities and expressed separately, and then add one extra variable $\epsilon$ and solve the LP: $\max \epsilon$ subject to $Ax + \epsilon \leq b$ and $Cx = d$. Then whatever solution $(x,\epsilon)$ you get, you will have that $x$ will be toward the center of your original feasible region.