maximize internal L1 distance between multiple points

Question

I am trying to maximize the internal distance between multiple 2D points while simultaneously minimizing their distance to a center point. I am using L1 distance for calculation and based on one of my previous question I was able to implement the L1 distance constraints to minimize the distance between decision variables to a center point. And this works fine. The solution coordinates are same. That is they overlap eachother.

    from ortools.linear_solver import pywraplp
    # center point    
    center = (8, 9)     
    
    solver = pywraplp.Solver.CreateSolver('GLOP')

    d1 = solver.NumVar(0, 1000, 'd1')
    d2 = solver.NumVar(0, 1000, 'd2')
    
    # list to store all the points
    points = []     
    # example with just 2 points
    for i in range(2):     
        x = solver.NumVar(0, 1000, f'x_{i}')
        y = solver.NumVar(0, 1000, f'y_{i}')
        points.append((x,y))
        
    # list to store all the distances to a single point    
    distances = [solver.NumVar(0, 1000, f'distances_{i}') for i in range(2)]  
    
    # Constraints to minimize the distance between each point to the center point
    for i in range(2):
        solver.Add(d1 == points[i][0] - center[0])      # d1 = x_i - x_center
        solver.Add(d2 == points[i][1] - center[1])      # d2 = y_i - y_center
        
        solver.Add(d1 >= 0)    # these four constraints to get absolute values
        solver.Add(-d1 <= 0)
        solver.Add(d2 >= 0)
        solver.Add(-d2 <= 0)
        solver.Add(distances[i] == d1 + d2)

        solver.Minimize(distances[0] + distances[1]) 
    
    status = solver.Solve()

Now, to avoid overlapping, I want to maximize their internal distances, hence I tried to use the similar approach as follows:

    # Constraints to maximize the distance between each individual point
    internal_dist = [solver.NumVar(0, 10000, f'internal_dist{i}') for i in range(2)]
    count = 0
    min_internal_distance = 2
    for i in range(2):
        for j in range(i + 1 , 2):
            solver.Add(d1_internal == points[i][0] - points[j][0])      # d1_internal = x_i - x_j
            solver.Add(d2_internal == points[i][1] - points[j][1])      # d2_internal = y_i - y_j
            
            solver.Add(d1_internal <= min_internal_distance )   # Tag_1 - to get absolute distance
            solver.Add(-d1_internal >= min_internal_distance)
            solver.Add(d2_internal <= min_internal_distance )
            solver.Add(-d2_internal <= min_internal_distance )


            solver.Add(internal_dist[count] == d1_internal + d2_internal)
            count += 1

And the new objective will be as such:

    solver.Minimize(distances[0] + distances[1] - internal_dist[0] - internal_dist[1])

But the solver is not finding any solution. For the second case I removed the four constraints from# Tag_1 - to get absolute distance, then I get the same solution which I get even without maximizing the distance constraints(so all points are again overlapping)

I think I am implementing the 2nd scenario quite incorrectly. Can you please guide me in the right direction. Thanks :)

Answer 1

In a similar setting, I have implemented the second part using the CP-SAT solver on the euclidian distance. See https://github.com/google/or-tools/blob/main/examples/python/spread_robots_sat.py

Note that the definition of the objective matters, sum (square pairwise distances) puts all points in 2 opposite corners.

sum(pairwise distances) puts all points in all 4 corners

maximize(min pairwise distances) spreads the points nicely. It should be easy to add the min distance to the center point. Balancing the 2 objectives is a bit tricky if you want to get the regular solution (all points equidistant on a circle).

Note, manhattan distance is really bad for this, but is the only one easy to define on a linear solver.