using shapes in Gurobi

回答済み

Sayyidshahab Nabavi

2023年02月10日 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

関連

• Python
• Nonconvex

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:49

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jaromił Najman

  • Gurobi Staff

  2023年02月10日 12:43 編集済み

  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

  2025年07月18日 16:47 編集済み

  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

  2023年02月11日 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

投稿コメントは受け付けていません。