Algorithm to find integer combinations satisfying a set of inequalities

Question

I have an engineering problem that is reduced to finding a set of positive integer combinations satisfying several inequalities and some other properties.

Specially, let $\mathcal{S}$ be the set of all positive integer combinations $(M, K, W, Q)$ satisfying the following $3$ inequalities: $$ WQ+K\leq N, $$ $$ W\leq M, $$ $$ MK\geq F, $$ where $F$ and $N$ are known positive integers. I need an algorithm to obtain a subset of $\mathcal{S}$. The elements of the subset should be obtained according to the following conditions:

1, For combinations $(M, K, W, Q)$ of $\mathcal{S}$ having the same $(M, Q)$, only keep the $(M, K, W, Q)$ with the largest $W$;

2, For combinations $(M, K, W, Q)$ of $\mathcal{S}$ having the same $(W, Q)$, only keep the $(M, K, W, Q)$ with the smallest $M$;

3, For combinations $(M, K, W, Q)$ of $\mathcal{S}$ having the same $(M, W, Q)$, only keep the $(M, K, W, Q)$ with the largest $K$.

Is there an efficient algorithm to achieve this? And is that possible to count the number of combinations in the subset, as a function of $F$ and $N$?

Answer 1

Combine the inequalities into two: $$W \le M \\ \frac FM \le K \le N-WQ$$

Firstly I note that the constraint filters effectively treat $Q$ as a free variable in the same way as $F$ and $N$.

Consider constraint 3:

3. For combinations $(M, K, W, Q)$ of $\mathcal{S}$ having the same $(M, W, Q)$, only keep the $(M, K, W, Q)$ with the largest $K$.

This implies $K = N - WQ$ and we can eliminate and ignore it.

---

$$W \le M \\ F \le M(N-WQ)$$

1. For combinations $(M, K, W, Q)$ of $\mathcal{S}$ having the same $(M, Q)$, only keep the $(M, K, W, Q)$ with the largest $W$;

So maximise $W$ as a function of $M$. We have $W \le M$ and $W \le \frac{N - FM}Q$, so this implies $W = \min\left(M, \left\lfloor\frac{N - FM}Q\right\rfloor\right)$.

---

2. For combinations $(M, K, W, Q)$ of $\mathcal{S}$ having the same $(W, Q)$, only keep the $(M, K, W, Q)$ with the smallest $M$;

If $M \le \left\lfloor\frac{N - FM}Q\right\rfloor$, we can't reduce $M$ because that would reduce $W$.

If $M > \left\lfloor\frac{N - FM}Q\right\rfloor$, decreasing $M$ by one cannot violate $W \le M$ and it increases the other bound on $W$. Therefore we must decrease $M$ until $M = W$.

---

So we have the following constraints: $$ W = M \\ \frac FM \le K = N - WQ $$ Substituting the first into the second we have $$F \le M(N - MQ)$$ or $$Q M^2 - MN + F \le 0$$ Since $Q > 0$, $$\frac{N - \sqrt{N^2 - 4QF}}{2Q} \le M \le \frac{N + \sqrt{N^2 - 4QF}}{2Q}$$

Since we need real roots to have any solutions, $Q$ isn't entirely free: we require $Q \le \frac{N^2}{4F}$.

Given a value of $Q$, the number of values of $M$ is approximately $\frac{\sqrt{N^2 - 4QF}}{Q}$, so the total number of solutions is approximately $$\int_{1}^{\frac{N^2}{4F}} \frac{\sqrt{N^2 - 4QF}}{Q} dQ$$

Subst $c = \frac{N^2}{4F}$ to get $2\sqrt{F} \int_1^c \frac{\sqrt{c - Q}}{Q} dQ$, and if I haven't messed up the substitutions and the use of Wolfram Alpha to cheat on the core integral, you get $4\sqrt{F} \left(\sqrt{c-1} - \sqrt{c} \tanh^{-1}\sqrt{1-\frac{1}{c}}\right)$