2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

EDIT There is a software suite called Vinci: http://www.math.u-bordeaux1.fr/~aenge/?category=software&page=vinci The home page has links to the various special classes of polytopes, and what is appropriate for them.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – CottonTensor Apr 21 '15 at 23:33
  • 1
    $\begingroup$ @CottonTensor That's what I would do, unless the problem had special structure (which, for example, assured that the number of vertices is smallish, so then you could just triangulate from a vertex...) See the edit for link to software - anything worth doing is worth getting someone else to do for you :) $\endgroup$ – Igor Rivin Apr 22 '15 at 0:09
2
$\begingroup$

A very interesting approach to this sort of problem in the more general context of #SMT was outlined by Chistikov et al. at TACAS 2015 (held last week!): the arXiv preprint is http://arxiv.org/abs/1411.0659.

$\endgroup$
  • $\begingroup$ Does look very cool! $\endgroup$ – Igor Rivin Apr 22 '15 at 1:41

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.