1

Is there any way to calculate the volume of a simplex by using LP or MIP when we have its extreme points? Is there any paper that gives me some clues?

CH.S
  • 13

1 Answers1

2

If it really is just a simplex (the convex hull of $n+1$ points in $\mathbb R^n$) then the determinant formula for the area of a simplex generalizes to give us $$V = \frac{1}{n!} \left| \det \begin{bmatrix} 1 & x_{11} & x_{12} & \dots & x_{1n} \\ 1 & x_{21} & x_{22} & \dots & x_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n+1,1} & x_{n+1,2} & \dots & x_{n+1,n}\end{bmatrix}\right|$$ where $(x_{11},\dots, x_{1n}), (x_{21}, \dots, x_{2n}), \dots, (x_{n+1,1}, \dots, x_{n+1,n})$ are the coordinates of your extreme points.

CH.S
  • 13
Misha Lavrov
  • 142,276
  • Thanks! I know this way, but this a non-linear way to calculate it. I have to formulate in LP or MIP. Actually, if I can do that in just two dimensions, it would be good. – CH.S Mar 28 '17 at 18:32
  • I mean, the volume is inherently going to be a nonlinear quantity. If you double all coordinates, it's going to expand by $2^n$. – Misha Lavrov Mar 28 '17 at 19:04
  • Yes, you are right. Do you think is there any heuristic way to predict it that is used linear quantity? – CH.S Mar 28 '17 at 19:31
  • No, I guess that's not necessarily true for an LP solution either. You have something like $a_1x_1 \le 1, a_2x_2 \le x_1, a_3x_3 \le x_2, \dots$ and you get $x_n \le \frac1{a_1a_2\cdots a_n}$. In fact, we could write down some really stupid LP whose solution is by definition the value of the determinant; it's not clear if there's an LP that's easier to write down than the computation itself. – Misha Lavrov Mar 28 '17 at 19:43