5
$\begingroup$

In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in computing the complete pareto frontier of the system , that is to say the set of all "primitive" solutions $\mathbf{x}$ which cannot be decomposed as $\mathbf{x} = \mathbf{x}^\prime +\mathbf{y}$ with $\mathbf{x}^\prime$ a strictly smaller solution and $\mathbf{y}$ a nonnegative vector.

For general $\mathbf{A}$, this is hard to compute: Dickson's lemma guarantees that the set of such minimal solutions is finite, but this is not much practical reassurance. I am currently using a branch-and-bound method to find them all, albeit inefficiently.

My question is this: My matrix $\mathbf{A}$ is not arbitrary, but is in fact the difference of two binary matrices, meaning that every entry is in $\{-1, 0, +1\}$. I am wondering what the state of the art is on computing the pareto frontier for such a special case---if there is an obviously more efficient method that takes advantage of the structure of this problem (nonnegative integer solutions, linear objective, approximately binary matrix.)

(That is my main question, but barring a solution there, I would also be interested in making inroads on the combinatorics of this problem---do we know any bounds on the number of pareto optimal solutions in this case, even if computing them is hard?)

Edit: Here is a representative $\mathbf{A}$, with plus, minus, and blank denoting +1, -1, and 0 for concision: $$\begin{bmatrix} & & & & & & & & & & & &- & & & &- & \\ &- &- & &+ &+ & & & & & &+ &- & &- & &+ & \\ &+ &- & &- & & & & & & & &+ & &- & & & \\ & &+ &- &- & & & & &+ & & & & &- & & & \\ &- &+ & &- & & &- & &- & &- &+ & &- & &- & \\ &- &- & &+ &- & & & &+ & & & & &+ & &- & \\ + & & & & &+ & &- & &- &- &- &+ & & &+ &+ &- \\ & & & & & & & & & & & & & & & &- & \\ & & & & & & & & &- & & & & & & & & \\ & & &- &+ & &+ & & & & &+ &- & & & &- & \\ & & & & & & & & & & & & & & &- & & \\ &- & & &+ & &- &- & &- &+ & & & & &+ &- &- \\ &+ & & & &+ &- & & &+ & &+ & & & & &- & \\ - & & & & & & & & & & & & & & & & & \\ & & & & & & & & & & & & & & & & &- \\ & & & & & &- & & & &+ & & & & &- & &- \\ &- &- &- & &+ & & & & & & &+ & & & &- &+ \\ &- & & & & &+ &- & & & & & & &+ &+ &- & \end{bmatrix}$$

Alternatively, here is a plain text representation of $A$:

 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 -1 -1 0 1 1 0 0 0 0 0 1 -1 0 -1 0 1 0 0 1 -1 0 -1 0 0 0 0 0 0 0 1 0 -1 0 0 0 0 0 1 -1 -1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 -1 1 0 -1 0 0 -1 0 -1 0 -1 1 0 -1 0 -1 0 0 -1 -1 0 1 -1 0 0 0 1 0 0 0 0 1 0 -1 0 1 0 0 0 0 1 0 -1 0 -1 -1 -1 1 0 0 1 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 1 0 0 0 0 1 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 1 0 -1 -1 0 -1 1 0 0 0 0 1 -1 -1 0 1 0 0 0 1 -1 0 0 1 0 1 0 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 0 1 0 0 0 0 -1 0 -1 0 -1 -1 -1 0 1 0 0 0 0 0 0 1 0 0 0 -1 1 0 -1 0 0 0 0 1 -1 0 0 0 0 0 0 1 1 -1 0
Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ Can you please share the matrix? $\endgroup$ Commented May 24, 2024 at 0:20
  • 2
    $\begingroup$ I'd start with trying specialized tools for computing integral points in polyhedra - e.g., Normaliz $\endgroup$ Commented May 24, 2024 at 2:59
  • $\begingroup$ @RobPratt Done! Took me a sec to figure out how to typeset it so it fit on the page. $\endgroup$ Commented May 24, 2024 at 7:27
  • $\begingroup$ @MaxAlekseyev Great! I hadn't heard of Normaliz; so far, it looks like it can work with integral points in unbounded polyhedra, which is excellent. I am looking into it. $\endgroup$ Commented May 24, 2024 at 7:30
  • 1
    $\begingroup$ @domotorp Thanks! I'll follow up on that book. I'm basically counting the number of hilbert basis elements of a convex cone. My specific question was about whether the slightly special {-1,0,+1} form of the matrix made it easier to calculate this, but given that normaliz seems to have efficient general-purpose algorithms, it may just be sufficient. $\endgroup$ Commented May 25, 2024 at 18:19

1 Answer 1

Reset to default
1
$\begingroup$

I've discussed this problem privately with Winfried Bruns (the author of Normaliz), and what follows is the courtesy of Winfried:

The inequalities define a rational polyhedron $P$. It is unbounded. We want to find a minimal system of generators of the set $S$ of lattice points in $P$ with respect to the action of the semigroup $L$ of integral vectors in the positive orthant. Normaliz can do the hard part of the computation. It must then be followed by rather easy postprocessing. (The postprocessing could be replaced by a second run of Normaliz.)

The polyhedron $P$ has a natural cone associated to it, the recession cone. It is the cone of infinite directions in the polyhedron. In other words, it is the maximal cone $C$ such that $P + C \subset P$. The semigroup $M$ of integral vectors in $C$ operates on the set $S$ by addition. Note that $M$ is a proper subsemigroup of $L$.

The input file hilb_problem.in contains the inequalities and options. If you run it by

/path/to/normaliz -c hilb_problem.in

We assume it is in the current directory. (The option -c generates terminal output.) Normaliz computes the (automatically finite) minimal system $G$ of generators of $S$ with respect to action of $M$ (and not with that of $L$).

The computation of $G$ is running on our server, but will take long time, say 2 or 3 weeks. Suppose we have $G$. I think it is best then to minimize $G$ with respect to the action of $L$: form the differences $x-y$ for $x,y$ in $G$, $x \neq y$, and if $x-y$ has nonnegative entries, discard $x$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.