# How can I find the center of a region in a linear programming problem?

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.

-
Would downvoters please explain why? I thought this was a well-expressed question... – levand Sep 4 '13 at 20:51
I think the down vote was because this is not a linear programming question. You are trying to find the "center" of a polytope. – par Sep 4 '13 at 20:55
But that's precisely my question; is it possible to solve this sort of problem using linear programming techniques? And if it's not possible, pointers towards other computationally tractable approaches would be welcome... – levand Sep 4 '13 at 20:57
It really just depends on your definition of center. See below. – par Sep 4 '13 at 21:00
I upvoted to even out your downvote :P I don't think this question is worthy of a downvote. – par Sep 4 '13 at 21:08

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.

-

The centroid of a simplex might work for you:

$$\frac{1}{n} \sum_{i=1}^n v_i.$$

Here, the $v_i$ are the vertices of the polytope.

Addendum: If you're familiar with the theory behind linear programming, you'll find it easy to go from your constraint matrix $A$ to vertices on the polytope. "Selecting" a vertex is equivalent to selecting your basic variables.

-
The number of vertices of the feasible region can be exponential in the number of inequalities defining the feasible region. In general, with $d$ variables and $n$ inequalities, the number of vertices could be $\Omega(n^{d/2})$ – user2566092 Sep 4 '13 at 21:04
From the looks of the question, it doesn't seem like that is an issue. – par Sep 4 '13 at 21:07
Well, that's just a simplified example. The actual version will have thousands of variables and constraints :) – levand Sep 4 '13 at 21:10