Simplest Optimization Framework for this Problem

Question

The problem in question is:

Given two vectors $X$ and $\epsilon$ in $\mathbb{R}^n$, find the value $y$ such that $y$ intersects the most regions formed by the elements of $X \pm \epsilon$.

The simplest optimization framework I can think of that covers this problem is a mixed integer non-linear programming problem. Obviously MINLPs are generally hard to solve, so I'd like to figure out if there is a simpler framework in which this problem can be captured. Specifically, I'm having trouble figuring out how to simplify the idea of region intersection (ideally make it a linear constraint, but it's not clear that is possible).

EDIT:

As an example, here is a simple instance for n=3. $X=\{2, 4, 19\}$, $\epsilon = \{1, 2, 0\} \implies y \in [2,3]$ is the optimal value of $y$ ($X_1\pm \epsilon_1$ and $X_2 \pm \epsilon_2$ are both intersected this way, any other value of $y$ would intersect only one region instead of two).

Answer 1

Here is a simple nested loop which scans all region boundaries and selects the one with the highest number of region intersections:

int[] MaximizeIntersects(int[] x, int[] e)
{
    int n = x.Length;
    SortedSet<int> limits = new SortedSet<int>();
    int[] y = { 0, 0 };
    int intersects = 0;

    for(int i = 0; i < n; i++)
    {
        limits.Add(x[i] - e[i]);
        limits.Add(x[i] + e[i]);
    }

    foreach(int r in limits)
    {
        int ix = 0;

        for(int i = 0; i < n; i++)
        {
            if (((x[i]-e[i]) <= r) && ((x[i]+e[i]) >= r))
            {
                ix++;  //  increment intersect count
            }
        }

        if (ix > intersects)
        {
            //  keep most intersecting boundary so far
            y[0] = r;
            intersects = ix;
        }
        else if (ix == intersects)
        {
            //  the boundary following the best so far
            y[1] = r;
        }
    }

    return y;
}

---

Alternative solution with sub-quadratic complexity:

int[] MaximizeIntersects(int[] x, int[] e)
{
    int n = x.Length;
    SortedSet<int> boundaryStarts = new SortedSet<int>();
    SortedSet<int> boundaryEnds = new SortedSet<int>();
    Dictionary<int, int> dicCounts = new Dictionary<int, int>();
    int[] y = { 0, 0 };
    int intersects = 0;

    for (int i = 0; i < n; i++)
    {
        boundaryStarts.Add(x[i] - e[i]);
        boundaryEnds.Add(x[i] + e[i]);
        increment(dicCounts, x[i] - e[i], +1);
        increment(dicCounts, x[i] + e[i], -1);
    }

    int ix = 0;
    foreach (int r in boundaryStarts)
    {
        ix += dicCounts[r];

        if (ix > intersects)
        {
            //  keep most intersecting boundary so far
            y[0] = r;
            intersects = ix;
        }
    }

    //  end of region directly follows start of region
    y[1] = boundaryEnds.Where(be => be > y[0]).First();

    return y;
}

void increment(Dictionary<int, int> dic, int key, int delta)
{
    int value;
    if (!dic.TryGetValue(key, out value))
    {
        dic.Add(key, delta);
    }
    else
    {
        dic[key] = value + delta;
    }
}

---

Alternative solution:

A MiniZinc constraint solver model:

%  fixed input parameters
int: n = 3;
array[1..n] of int: x = [2, 4, 19];
array[1..n] of int: e = [1, 2, 0];
int: rMin = min(x) - max(e);  
int: rMax = max(x) + max(e);  
set of int: Bounds = rMin .. rMax;
%  Region boundaries caclulated as set comprehensions
set of Bounds: BoundaryStarts = {x[i] - e[i] | i in 1..n};
set of Bounds: BoundaryEnds = {x[i] + e[i] | i in 1..n};

%  single decision variable; must be start of a region
var BoundaryStarts: y;

function var int: no_of_intersects(var BoundaryStarts: r) =
  sum([(r >= (x[i] - e[i])) /\ (r <= (x[i] + e[i]))| i in 1..n]);

solve maximize(no_of_intersects(y));

output [show(y) ++ " .. " ++ show(min([if r > fix(y) then r else rMax endif | r in BoundaryEnds]))];

Short but not exactly simple. Another drawback is the restriction to integer vectors.