Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer
1  
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
1  
Well, that's just a simplified example. The actual version will have thousands of variables and constraints :) –  levand Sep 4 '13 at 21:10

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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