using shapes in Gurobi

Answered

Sayyidshahab Nabavi

February 10, 2023 10:53

• 
• 
• 

Hello

I had a question regarding using Gurobi for shape optimization; for example, we have an area of 100 by 100. How can we put five circles with a radius of 40 that have the smallest intersection?

Is it possible to use libraries like shapely in Gurobi? Because passing the points as Gurobi variables is impossible.

I will be thankful if you help me with that.

Best Regards

Related to

• Python
• Nonconvex

0

• 

  Jaromił Najman

  • Gurobi Staff

  February 10, 2023 12:43 Edited

  Hi,

  I haven't done much geometry optimization but here is an idea on how to approach the modeling. Maybe someone else, has a more elaborate idea.

  For each circle, you can define it's center point as 2 variables x, y and radius r. The radius in your case is fixed to 40. In order to make sure that every circle is in the 100 by 100 box, you have to check whether the 4 points most to the north, south, west, east are within the box. So something like x + 40 <= right box border, x - 40 >= left box border, and the same for the y-axis should work.

  Regarding the intersection of circles, you might find some inspiration in the paper by Middleditch et al. (1989).

  I don't know shapely, but you certainly have to define each circle coordinate as a Gurobi variable.

  Best regards, 
  Jaromił

  0
• 

  Riley Clement

  • Gurobi Staff

  July 18, 2025 16:47 Edited

  Further to Jaromił's answer, the following may help

  Some of the trig expressions can be simplified although I'm not sure it will help the solver.

  Once you have a solution you can plot with matplotlib like so

  import matplotlib.pyplot as plt
  import numpy as np
  
  _, ax = plt.subplots()
  ax.set_xlim(0,100)
  ax.set_ylim(0,100)
  
  theta = np.linspace(0, 2*np.pi, 100)
     
  for i in range(5):
      ax.plot(R*np.cos(theta)+x[i].X,R*np.sin(theta)+y[i].X)

   

  You may also want to consider breaking symmetry with constraints of the form

  y[i+1] >= y[i] for i = 1,2,3,4

  but perhaps Gurobi will be able to detect and break symmetry automatically (and perhaps more efficiently).

  - Riley

   

  0
• 

  Riley Clement

  • Gurobi Staff

  February 11, 2023 02:47

  FYI, there are several modelling choices to be made here, all resulting in correct formulations.
  
  With one of the possible formulations I am able to achieve solutions with 4% gap rather quickly, but closing this gap to optimality is taking a long time.  Having looked at the solution, my guess is that it is optimal but is difficult for the solver to prove this (using default parameters and general constraint attributes).

  - Riley

  0

Please sign in to leave a comment.