I consider the following two instances of the same problem, computing the spread as the difference of the highest and lowest occurrence of something in a set. Further, I compute the variance of the elements in the set.
In my optimisation problems, I have several sets that are interconnected in differently. I try to determine the minimal spread/variance by either using MILPs or QILPs (because the variance includes a squaring operation).
A "spread" MILP could look something like this: $$\begin{align} \text{minimize} \quad & \sum_{v\in V}y_\max(v) - y_\min(v) \\ \text{subject to} \quad & \sum_{w\in W} x(v,w) \le y_\max(v) \quad \forall v\in V \\ & \sum_{w\in W} x(v,w) \ge y_\min(v) \quad \forall v\in V\\ & \text{...further problem related constraints...}\\ & y_\min(v),y_\max(v) \in\mathbb{N}, x(v,w)\in{0,1} \quad \forall v \in V, w\in W \end{align}$$
How to explain why I experience in all my cases that the QILP, even for large problem instances, is faster than its considered approximation.
Assumptions:
- Problem instances are still too small
- Additional constraints and variables make the MILP harder to compute