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.

  • $\begingroup$ Would downvoters please explain why? I thought this was a well-expressed question... $\endgroup$ – levand Sep 4 '13 at 20:51
  • $\begingroup$ I think the down vote was because this is not a linear programming question. You are trying to find the "center" of a polytope. $\endgroup$ – parsiad Sep 4 '13 at 20:55
  • $\begingroup$ 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... $\endgroup$ – levand Sep 4 '13 at 20:57
  • $\begingroup$ It really just depends on your definition of center. See below. $\endgroup$ – parsiad Sep 4 '13 at 21:00
  • $\begingroup$ I upvoted to even out your downvote :P I don't think this question is worthy of a downvote. $\endgroup$ – parsiad 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.

  • $\begingroup$ Isn't that almost equivalent to the Chebychev center? $\endgroup$ – becko Nov 5 '17 at 21:19

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.

  • 2
    $\begingroup$ 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})$ $\endgroup$ – user2566092 Sep 4 '13 at 21:04
  • $\begingroup$ From the looks of the question, it doesn't seem like that is an issue. $\endgroup$ – parsiad Sep 4 '13 at 21:07
  • 2
    $\begingroup$ Well, that's just a simplified example. The actual version will have thousands of variables and constraints :) $\endgroup$ – levand Sep 4 '13 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.