L1 space filling design

I'm trying to place 4 points on the the 2D-plane [0, 1]^2 such that the L1 distance between any 2 points is maximized. This should result in the points being placed in the 4 corners. However, gurobi is quite happy placing the points on the diagonal and calling it optimal.

What am I doing wrong?

import gurobipy as gp
from gurobipy import GRB

model = gp.Model()

nP = 4 # number of points
nD = 2 # number of dimensions

X = { (i, j): model.addVar(lb=0, ub=1, name=f"X_{i},{j}")
      for i in range(nP)
      for j in range(nD)
    }

dmin = model.addVar(name="minimum distance")

z1 = {} # aux variables for (X1 - X2)_j
z2 = {} # aux variables for (|X1 - X2|)_j

for i1 in range(nP):
  for i2 in range(i1 + 1, nP):
    for j in range(nD):
      z1[i1, i2, j] = model.addVar(name=f"(X{i1} - X{i2})_{j}")
      z2[i1, i2, j] = model.addVar(name=f"|X{i1} - X{i2}|_{j}")
      model.addConstr(z1[i1, i2, j] == X[i1, j] - X[i2, j])
      model.addConstr(z2[i1, i2, j] == gp.abs_(z1[i1, i2, j]))

    model.addConstr(sum(z2[i1, i2, j] for j in range(nD)) >= dmin)

model.setObjective(dmin, sense=GRB.MAXIMIZE)
model.optimize()

Results in

Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (win64) Gurobi Compute Server Worker version 10.0.0 build v10.0.0rc2 (linux64) CPU model: Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512] Thread count: 8 physical cores, 16 logical processors, using up to 16 threads Optimize a model with 18 rows, 33 columns and 54 nonzeros Model fingerprint: 0xed002f2f Model has 12 general constraints Variable types: 33 continuous, 0 integer (0 binary) Coefficient statistics: Matrix range [1e+00, 1e+00] Objective range [1e+00, 1e+00] Bounds range [1e+00, 1e+00] RHS range [0e+00, 0e+00] Found heuristic solution: objective -0.0000000 Presolve removed 18 rows and 33 columns Presolve time: 0.00s Presolve: All rows and columns removed Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units) Thread count was 1 (of 16 available processors) Solution count 2: 0.666667 -0 No other solutions better than 0.666667 Optimal solution found (tolerance 1.00e-04) Best objective 6.666666666667e-01, best bound 6.666666666667e-01, gap 0.0000%

The solution reads

{(0, 0): <gurobi.Var X_0,0 (value 1.0)>,

(0, 1): <gurobi.Var X_0,1 (value 1.0)>,

(1, 0): <gurobi.Var X_1,0 (value 0.6666666666666667)>,

(1, 1): <gurobi.Var X_1,1 (value 0.6666666666666667)>,

(2, 0): <gurobi.Var X_2,0 (value 0.33333333333333326)>,

(2, 1): <gurobi.Var X_2,1 (value 0.33333333333333326)>,

(3, 0): <gurobi.Var X_3,0 (value 0.0)>,

(3, 1): <gurobi.Var X_3,1 (value 0.0)>}

David Walz

November 23, 2022 09:56 Edited

Also, how do you properly format code in this forum?

Jaromił Najman

Gurobi Staff

November 23, 2022 12:00

Hi David,

The logic of your model is correct. The issue is that default lower bounds for variables are 0 in Gurobi. However, your \(\texttt{(X{i1} - X{i2})_{j}}\) can take negative values. Setting the lower bound explicitly to be negative

z1[i1, i2, j] = model.addVar(lb=-1,name=f"(X{i1}-X{i2})_{j}")

solves the issue.

In general, you should avoid having whitespaces in variable names. Gurobi does not care about the names internally and the whitespaces won't affect Gurobi's optimization algorithm, but when writing the model to a file or interacting with other software, whitespaces in names often lead to unexpected behavior.

Unfortunately, the forum editor does not support markdown. All features of the forum editor should be described in Posting to the Community Forum.

Best regards,
Jaromił

November 23, 2022 12:26

Hi Jaromil,

great thanks!

David

L1 space filling design

Comments

Didn't find what you were looking for?