How to model the problem of cutting a polyhedron into parts

Answered

Jiangfei DUAN

January 26, 2021 09:23 Edited

• 
• 
• 

Hi, I met a problem in my modeling. Here I abstract a minimal question of my problem.

Suppose I have a polyhedron (Rectangle, cube for example). For simplify, I use a rectangle as an example. The height and width of the rectangle is H, W respectively, so I can say the rectangle cover \([0:H, 0:W]\). I want to cut the rectangle into N parts evenly(For example, N = 8, then I can cut the rectangle into totally n parts \((0\le n \le 8)\), each part is roughly the same size, the critical point is that each cut should cross the corresponding two bounds). To express different parts, I use the starting point \((x_i, y_i)\) and the extent of each dimension \((h_i, w_i)\) to represent the i-th part, and this part cover \([x_i:x_i+h_i, y_i:y_i+w_i]\). Certainly, \(h_i and w_i\) can be 0, which means that part cover nothing. 

The N parts should also be non-overlapped, and they can cover the entire Rectangle \([0:H, 0:W]\). In the example, I use rectangle to illustrate the problem, but it actually can be arbitrary polyhedron, and H, W, and N are constant I can know in advance.

I wonder, how can I express my constraints?

Thanks a lot!

0

• Official comment

  

  Juan Orozco

  • Gurobi Staff

  January 26, 2021 22:41

  To get non-overlapping rectangles of the same area, you can solve the following feasibility model (implemented in Python):

  import gurobipy as gp
  from gurobipy import GRB
  
  TOTAL_HEIGHT = 5
  TOTAL_WIDTH = 10
  N = 4
  
  model = gp.Model("myModel")
  model.setParam("NonConvex",2)
  
  x = model.addVars(N, ub=TOTAL_WIDTH, name="x")
  y = model.addVars(N, ub=TOTAL_HEIGHT, name="y")
  width = model.addVars(N, name="width")
  height = model.addVars(N, name="height")
  excess_x = model.addVars(N-1, name="excess_x")
  excess_y = model.addVars(N-1, name="excess_y")
  is_smaller_x = model.addVars(N-1, vtype=GRB.BINARY, name="is_smaller_x")
  is_smaller_y = model.addVars(N-1, vtype=GRB.BINARY, name="is_smaller_y")
  
  model.addConstrs((x[i] + width[i] <= TOTAL_WIDTH for i in range(N)))
  model.addConstrs((y[i] + height[i] <= TOTAL_HEIGHT for i in range(N)))
  
  model.addConstrs((x[i] + width[i] - excess_x[i] <= x[i+1] for i in range(N-1)))
  model.addConstrs((y[i] + height[i] - excess_y[i] <= y[i+1] for i in range(N-1)))
  
  for i in range(N-1):
      model.addSOS(GRB.SOS_TYPE1, [excess_x[i], is_smaller_x[i]])
      model.addSOS(GRB.SOS_TYPE1, [excess_y[i], is_smaller_y[i]])
  
  model.addConstrs((is_smaller_x[i] + is_smaller_y[i] >= 1 for i in range(N-1)))
  
  model.addConstrs((width[i]*height[i] == TOTAL_WIDTH*TOTAL_HEIGHT/N for i in range(N)))
  
  model.optimize()

  The trick is to compare the final coordinates of a given rectangle with the initial coordinates of the next one, to prevent that the latter coordinates are located in the bottom-left of the former.
• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  December 06, 2024 00:36

  This post is more than three 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 why not try our AI Gurobot?.
• 

  Jiangfei DUAN

  January 27, 2021 12:43

  • 
  • 
  • 

  Thanks a lot.

  I got it. 

  0

Post is closed for comments.