L1 space filling design

回答済み

David Walz

2022年11月23日 08:35 編集済み

• 
• 
• 

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)>}

関連

• Python
• Wrong Result
• Modeling

0

• 

  David Walz

  2022年11月23日 09:56 編集済み

  • 
  • 
  • 

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

  0
• 

  Jaromił Najman

  • Gurobi Staff

  2022年11月23日 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.

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

  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ł

   

  0
• 

  David Walz

  2022年11月23日 12:26

  • 
  • 
  • 

  Hi Jaromil,

  great thanks!

  David

  0

サインインしてコメントを残してください。