# Volume of a region given by a Constraint Satisfaction Problem

I have a Linear Constraint Satisfaction Problem i.e. I have variables $x_1, x_2,...,x_m$, with corresponding domains $D_1,D_2,...,D_m$ satisfying linear constraints $C_1, C_2,...,C_n$ with $n << m$. I am interested in calculating the Volume in $n$-dimensional space of the region formed by $n$ particular variables, say $x_1,...,x_n$ in satisfying the problem. Due to the way the problem is formulated in the first place, I know this $n$-dimensional region, call it $\mathcal{K}$, is a closed convex polytope bounded within a unit box.

In order to compute the volume of this convex polytope, I imagine one could solve for the corners of the full problem in $m$-dimensional space and compute the volume of the convex hull of these corner points in the much smaller $n$-dimensional space, but I feel that this cannot be the most efficient method. Even if this is the best method, can someone suggest some papers for this approach?

I have considered using (Multiphase?) MC methods, but if I generate points in $\mathbb{R}^n$, in order for me to check whether it lies within my region, I have to check if there exists atleast one feasible point in $m$-D with this instantiation for $x_1,...,x_n$. So the Separation Oracle call is not cheap.

Is anyone aware of how such problems are handled or do you have any ideas for how one may approach this? Any suggestions/directions will be very helpful. Thanks!

It all depends on how small $n$ is compared to $m,$ but in general, this is very hard, and the cost of the oracle is the least of your problems: the number of such calls grows exponentially in $n.$ For more on this, see this old MO question (and especially the answers): Algorithm for finding the volume of a convex polytope
• Thanks Igor. In fact, I have read several of those papers on randomized algorithms for volume computations and am aware of $\mathcal{O}^*(n^5)$ methods. I am fine with such approximate methods and am very much willing to pay $\mathcal{O}^*(n^5)$ Oracle calls (because my $n << m$, $n < 10$ and $m$ is of ~ $10^3$ or $10^4$) as long as I don't have to incur too much cost in terms of $m$. So do you reckon this would be the best way? I.e. Solve the $m-n$-dimensional feasibility problem for each call of the separation oracle and use one of these Multiphase MC methods? – CottonTensor Apr 21 '15 at 23:33