- I have a problem which can be efficiently written, with some abuse of notation, as an 18 x 18 matrix equation $\mathbf{A}\mathbf{x} \geq \mathbf{1}$ over the non-negative integers $\mathbf{x}\geq \mathbf{0}$, except that some of the entries of the matrix $\mathbf{A}$ are positive infinite $(+\infty)$.
- How to handle infinities: If $\mathbf{c}$ is a vector containing infinities, let $I$ be the indices where $\mathbf{c}$ is finite, and let $J$ be the indices where $\mathbf{c}$ is positive infinity. Then the solution set to $\mathbf{c}\cdot \mathbf{x}\geq 1$ is defined as the union of $\{\mathbf{x} : \sum_{i\in I} a_i x_i \geq 1\}$ and $\bigcup_{j\in J}\{\mathbf{x} : x_j \geq 1\}$. So we lose some of the convexity and closure guarantees. The solution to a matrix equation $\mathbf{A}\cdot\mathbf{x} \geq \mathbf{1}$ is the intersection of the solution sets for its individual rows.
- For any matrix containing infinities, you can rewrite the solution set as the union of the solution sets to slightly modified matrices which have no infinities in them. You split up the cases where $x_i = 0$ (and so the infinity can be zeroed out) and the cases where $x_i > 0$ (and so the row can be replaced with an identity row $e_i$).
I am interested in computing the exact pareto frontier of the equation $\mathbf{A}\mathbf{x} \geq 1$. Using the matrix modification trick, I have written the solution set as a union of around 36 cones, and I've used the program normaliz to find module generators for those cones. You can prove that the pareto frontier of the overall equation must be a subset of the generators for these sub-cones. (Thanks to the help I received for a previous question Efficient counting of integer solutions to linear system)
However, some of these cones have proven to be impossible to solve in practice. For example, the solver will seize up after running for a year of (parallel) compute time. I suspect finding the generators may be prohibitively difficult, although perhaps I'm using the wrong settings (primal vs dual, etc.)
I am wondering if, given that I am only interested in the pareto frontier, can you compute the frontier of this system without finding the generators first?
So far, I have considered using generating functions, which make representing these infinities actually quite easy. This paper (https://arxiv.org/pdf/0707.1362) discusses finding the pareto frontier of a system of linear equations in polytime: given a polyhedral solution space $H$, you compute the generating function $U(y)$ for the upward hull $\{y : y\geq x, x\in H\}$, and then the pareto frontier is just $\bigcap_i U(y) - y_i U(y)$. But on inspection taking the intersection of generating functions looks as hard finding the generators of an arbitrary polyhedron.
I have also tried the same upward-hull approach without generating functions—adding slack equations to transform Ax > 1 into a system of equations for the upward hull, then using Fourier-Motzkin elimination to get rid of the original variables, then computing the generating function / module generators of that system. But unfortunately, the infinities/unions in my notation are incompatible with Fourier-Motzkin elimination.
Does this pareto frontier seem fundamentally difficult to compute? Is there anything else I should try as an approach?
