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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 21, 2015 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
    Commented Apr 22, 2015 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Does look very cool! $\endgroup$
    – Igor Rivin
    Commented Apr 22, 2015 at 1:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .