10
$\begingroup$

Let's say I have a bunch of linear functions $f_1,\cdots,f_n$ in $k$ variables; then $f_1,\cdots, f_n\le0$ defines a polyhedron $P$ in the $k$-dimensional space.

What I'm looking for is going the other way: given data points inside a polyhedron $P$, is there an efficient/fast way to find the functions $f_1,\cdots,f_n$ cutting the polyhedron? Those data points are finitely many integer points (i.e. points whose all coordinates are integers) and $P$ is "the smallest" polyhedron containing them. Basically I require two things:

  1. $P$ does not contain any other integer points.

  2. The linear functions themselves have integer coefficients.

A naive way would be to loop over all possible candidate functions (their integer coefficients) in a certain range but there should be a much better/faster/efficient way of doing it.

I am not specifically looking for an answer to this problem, rather a reference or direction for where I should be looking at. Has this been studied at all? I understand that this is not exactly what linear/integer programming is about, so apologies if the question is not appropriate for this site.

Improve this question
$\endgroup$
2
  • $\begingroup$ It might be pretty hard to ensure that $\mathbf{P}$ contains no other integer points. Consider for example the data points $\{(1,1),(3,1),(1,3),(3,3)\}$ with the description $\mathbf{P}=\{x\in\mathbb{R}^2:1\leq x_1\leq 3, 1\leq x_2\leq 3\}$. Here the point $(2,2,)$ is contained in $\mathbf{P}$ but not in the list of data points. $\endgroup$
    – Sune
    Oct 2, 2019 at 8:33
  • $\begingroup$ @Sune My data points are generated through a process that can guarantee I have them all. I am effectively trying to find patterns in that process, that for reasons I won't get to now, I am almost certain will be linear in nature. $\endgroup$
    – user12005284
    Oct 2, 2019 at 14:55

1 Answer 1

Reset to default
11
$\begingroup$

You are looking for algorithms to find the integer convex hull of a polytope. Unfortunately, there is no easy way to do it efficiently and I am not sure the 2. point (the functions have integer coefficients) is even possible.

I used to do this for studying cutting planes (for small toy problems) using PORTA (http://porta.zib.de/), which is not under development anymore. But there are more modern software packages listed on the PORTA webpage that might be able to do this more efficiently and with more modern algorithms.

If I remember correctly, one algorithm to do this is the double description method, i.e. an algorithm that converts an extreme point and ray representation of a polyhedron into an matrix (inequalities) representation of a polyhedron. That this is possible goes back to the Minkowski-Weyl theorem. Here you can find a paper about that algorithm, there is probably a lot more out there.

Improve this answer
$\endgroup$
3
  • $\begingroup$ as the points have integer (in particular rational) data, the functions will have rational (and thus via scaling) integer data. $\endgroup$
    – Marco Lübbecke
    Oct 2, 2019 at 14:32
  • 2
    $\begingroup$ Thanks so much for this answer, especially the PORTA software and the DD method. They look to be very close to what I need. Also I can "guarantee" these functions can be chosen to have integer coefficients, the data is random but the process generating it is quite complicated. I will leave this question open for a bit to see if anyone has any other ideas, but otherwise I will accept this answer. $\endgroup$
    – user12005284
    Oct 2, 2019 at 15:00
  • $\begingroup$ My comment above reads "the data is random but..." but that's a typo and the opposite is true: The data is very much not random, but it is generated in a very complicated process. $\endgroup$
    – user12005284
    Oct 3, 2019 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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