Guest User

MILP Unblock Me

a guest
Apr 2nd, 2023
1,489
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.75 KB | Gaming | 0 0
  1. import pyscipopt as popt
  2. import matplotlib.path as mpath
  3. import matplotlib.patches as mpatches
  4. import matplotlib.pyplot as plt
  5. import math
  6.  
  7. class Block:
  8.  
  9. def __init__(self, coord, width, length, name):
  10. proper_dim = width > 0 and length > 0\
  11. and (width == 1 or length == 1)\
  12. and not (width == 1 and length == 1)
  13. if not proper_dim:
  14. self.position = None
  15. return
  16. xl, yl = coord[0], coord[1]
  17. self.length = length
  18. self.width = width
  19.  
  20. self.xl, self.yl = xl, yl
  21. self.xl, self.yu = xl, yl + width
  22. self.xu, self.yl = xl + length, yl
  23. self.xu, self.yu = xl + length, yl + width
  24. self.position = {0: self.get_position()}
  25. self.t = 0
  26. self.move_direction = 'vertical' if length == 1 else 'horizontal'
  27. self.name = name
  28. self.color = 'blue'
  29.  
  30. def get_position(self):
  31. return (self.xl, self.yl), (self.xl, self.yu), (self.xu, self.yl), (self.xu, self.yu)
  32.  
  33. def update_x_position(self, deltaL):
  34. self.xl += deltaL
  35. self.xu += deltaL
  36. self.update_position()
  37.  
  38. def update_y_position(self, deltaW):
  39. self.yl += deltaW
  40. self.yu += deltaW
  41. self.update_position()
  42.  
  43. def update_position(self):
  44. self.t += 1
  45. self.position[self.t] = self.get_position()
  46.  
  47. def set_color(self, color):
  48. self.color = color
  49.  
  50. def __str__(self):
  51. if self.position:
  52. return str(self.position[self.t])
  53. else:
  54. return ''
  55.  
  56. class BlockPlotter:
  57.  
  58. def __init__(self, blocks, steps, bounds):
  59. self.fig = None
  60. self.ax = None
  61. self.blocks = blocks
  62. self.time_steps = steps
  63. self.bounds = bounds
  64.  
  65. def create_figure(self):
  66. self.fig = plt.figure()
  67. even = self.time_steps
  68. if even == 1:
  69. self.axs = self.fig.subplots(1, even+1)
  70. for ax in self.axs:
  71. ax.set_xlim(0, bounds[0])
  72. ax.set_ylim(0, bounds[1])
  73. else:
  74. self.axs = self.fig.subplots(1, even)
  75. for ax in self.axs:
  76. ax.set_xlim(0, bounds[0])
  77. ax.set_ylim(0, bounds[1])
  78.  
  79.  
  80. def plot(self):
  81. if not self.fig:
  82. self.create_figure()
  83. if self.time_steps > 1:
  84. for step in range(self.time_steps):
  85. for block in self.blocks:
  86. block_position = block.position[step]
  87. if step == 0:
  88. patch = plt.Rectangle(block_position[0],
  89. block.length, block.width, edgecolor='black',
  90. facecolor=block.color)
  91. else:
  92. block_prev_position = block.position[step-1]
  93. if block.color == 'yellow':
  94. patch = plt.Rectangle(block_position[0],
  95. block.length, block.width, edgecolor='black',
  96. facecolor=block.color,
  97. hatch='/')
  98. else:
  99. patch = plt.Rectangle(block_position[0],
  100. block.length, block.width, edgecolor='black',
  101. facecolor=block.color)
  102. if block_position != block_prev_position and block.color != 'yellow':
  103. patch = plt.Rectangle(block_position[0],
  104. block.length, block.width, edgecolor='black',
  105. facecolor='green')
  106. self.axs[step].add_patch(patch)
  107. else:
  108. for block in self.blocks:
  109. block_position = block.position[0]
  110. patch = plt.Rectangle(block_position[0],
  111. block.length, block.width)
  112. self.axs[0].add_patch(patch)
  113. plt.show()
  114.  
  115. class Problem:
  116.  
  117. def __init__(self, blocks, nr_moves, primary_block, bounds):
  118. self.model = popt.Model('Block_Mover')
  119. self.blocks = blocks
  120. self.nr_moves = nr_moves
  121. self.primary_block = primary_block
  122. self.bounds = bounds
  123.  
  124. def initialize(self):
  125. self.add_variables()
  126. self.add_constraints()
  127. self.add_objective()
  128.  
  129. def add_variables(self):
  130. # block defining variables
  131. self.xl_bt = {}
  132. self.xr_bt = {}
  133. self.yd_bt = {}
  134. self.yu_bt = {}
  135. for t in range(self.nr_moves):
  136. for block in self.blocks:
  137. self.xl_bt[block.name, t] = self.model.addVar(vtype='C', name="xl_(%s,%s)" % (block.name, t))
  138. self.xr_bt[block.name, t] = self.model.addVar(vtype='C', name="xr_(%s,%s)" % (block.name, t))
  139. self.yd_bt[block.name, t] = self.model.addVar(vtype='C', name="yd_(%s,%s)" % (block.name, t))
  140. self.yu_bt[block.name, t] = self.model.addVar(vtype='C', name="yu_(%s,%s)" % (block.name, t))
  141.  
  142. # does move
  143. self.zf_rt = {}
  144. self.zb_rt = {}
  145. for t in range(self.nr_moves):
  146. for block in self.blocks:
  147. self.zf_rt[block.name, t] = self.model.addVar(vtype='B',
  148. name="zf_(%s,%s)" % (block.name, t))
  149. self.zb_rt[block.name, t] = self.model.addVar(vtype='B',
  150. name="zb_(%s,%s)" % (block.name, t))
  151.  
  152. # OR variables for feasibility
  153. self.delta_tij = {}
  154. for t in range(self.nr_moves):
  155. for i, block_outer in enumerate(self.blocks):
  156. for j, block_inner in enumerate(self.blocks):
  157. if i >= j:
  158. continue
  159. for k in range(4):
  160. key = (t, block_outer.name, block_inner.name, k)
  161. self.delta_tij[key] = self.model.addVar(vtype='B',
  162. name='delta_(%s,%s,%s,%s)' % key)
  163.  
  164. # transition variables
  165. self.transition_t = {}
  166. for t in range(self.nr_moves):
  167. self.transition_t[t] = self.model.addVar(vtype='B',
  168. name='transition_(%s)' % t)
  169.  
  170. def add_constraints(self):
  171. # initial position
  172. t = 0
  173. for block in self.blocks:
  174. self.model.addCons(self.xl_bt[block.name, t] == block.position[0][0][0],
  175. name='Starting_%s' % (block.name))
  176. self.model.addCons(self.yd_bt[block.name, t] == block.position[0][0][1],
  177. name='Starting_%s' % (block.name))
  178.  
  179. # link block
  180. for t in range(self.nr_moves):
  181. for block in self.blocks:
  182. self.model.addCons(self.xr_bt[block.name, t] == self.xl_bt[block.name, t] + block.length,
  183. name='BlockRight_%s_%s' % (block.name, t))
  184. self.model.addCons(self.yu_bt[block.name, t] == self.yd_bt[block.name, t] + block.width,
  185. name='BlockUp_%s_%s' % (block.name, t))
  186.  
  187. # block movement
  188. for block in self.blocks:
  189. for t in range(self.nr_moves - 1):
  190. if block.move_direction == 'horizontal':
  191. self.model.addCons(
  192. self.xl_bt[block.name, t+1] == self.xl_bt[block.name, t] + self.zf_rt[block.name, t]
  193. - self.zb_rt[block.name, t],
  194. name='Move_Hor_%s_%s' % (block.name, t))
  195. self.model.addCons(
  196. self.yd_bt[block.name, t + 1] == self.yd_bt[block.name, t],
  197. name='Move_Vert_%s_%s' % (block.name, t))
  198.  
  199. else:
  200. self.model.addCons(
  201. self.yd_bt[block.name, t + 1] == self.yd_bt[block.name, t] + self.zf_rt[block.name, t]
  202. - self.zb_rt[block.name, t],
  203. name='Move_Vert_%s_%s' % (block.name, t))
  204.  
  205. self.model.addCons(
  206. self.xl_bt[block.name, t + 1] == self.xl_bt[block.name, t],
  207. name='Move_Hor_%s_%s' % (block.name, t))
  208. # only one block can move per time
  209. for t in range(self.nr_moves):
  210. forward = []
  211. backward = []
  212. for block in self.blocks:
  213. forward.append(self.zf_rt[block.name, t])
  214. backward.append(self.zb_rt[block.name, t])
  215. self.model.addCons(popt.quicksum(forward) + popt.quicksum(backward) <= 1)
  216.  
  217. # space bounds
  218. for t in range(self.nr_moves):
  219. for block in self.blocks:
  220. if block.move_direction == 'horizontal':
  221. self.model.addCons(self.xr_bt[block.name, t] <= self.bounds[0])
  222. else:
  223. self.model.addCons(self.yu_bt[block.name, t] <= self.bounds[0])
  224.  
  225.  
  226. # feasibility
  227. M = self.bounds[0]
  228. for t in range(self.nr_moves):
  229. for i, block_outer in enumerate(self.blocks):
  230. for j, block_inner in enumerate(self.blocks):
  231. if i >= j:
  232. continue
  233. key = (t, block_outer.name, block_inner.name, 0)
  234. self.model.addCons(self.xl_bt[block_outer.name, t] + block_outer.length
  235. <= self.xl_bt[block_inner.name, t] + M * self.delta_tij[key])
  236.  
  237. key = (t, block_outer.name, block_inner.name, 1)
  238. self.model.addCons(self.xl_bt[block_inner.name, t] + block_inner.length
  239. <= self.xl_bt[block_outer.name, t] + M * self.delta_tij[key])
  240.  
  241. key = (t, block_outer.name, block_inner.name, 2)
  242. self.model.addCons(self.yd_bt[block_outer.name, t] + block_outer.width
  243. <= self.yd_bt[block_inner.name, t] + M * self.delta_tij[key])
  244.  
  245. key = (t, block_outer.name, block_inner.name, 3)
  246. self.model.addCons(self.yd_bt[block_inner.name, t] + block_inner.width
  247. <= self.yd_bt[block_outer.name, t] + M * self.delta_tij[key])
  248.  
  249. self.model.addCons(
  250. popt.quicksum(self.delta_tij[t, block_outer.name, block_inner.name, k] for k in range(4)) <= 3
  251. )
  252. # final position is end
  253. self.model.addCons(self.xr_bt[self.primary_block.name, self.nr_moves - 1] == bounds[0])
  254.  
  255. # transition between blocks
  256. for t in range(1, self.nr_moves):
  257. for block_outer in self.blocks:
  258. for block_inner in self.blocks:
  259. if block_outer.name == block_inner.name:
  260. continue
  261. was_moved_previous_t = popt.quicksum([self.zf_rt[block_outer.name, t -1],
  262. self.zb_rt[block_outer.name, t -1]])
  263. moved_current_t = popt.quicksum([self.zf_rt[block_inner.name, t],
  264. self.zb_rt[block_inner.name, t]])
  265. self.model.addCons(was_moved_previous_t + moved_current_t - 1 <= self.transition_t[t])
  266.  
  267. def add_objective(self):
  268. z_forward = [val for val in self.zf_rt.values()]
  269. z_backward = [val for val in self.zb_rt.values()]
  270. transition = [val for val in self.transition_t.values()]
  271. self.model.setObjective(10 * popt.quicksum(z_forward) + 10 * popt.quicksum(z_backward)
  272. + popt.quicksum(transition), "minimize")
  273.  
  274. def solve(self):
  275. self.model.optimize()
  276.  
  277. def update_blocks(self):
  278. for t in range(self.nr_moves):
  279. for block in self.blocks:
  280. forward = self.model.getVal(self.zf_rt[block.name, t])
  281. backward = self.model.getVal(self.zb_rt[block.name, t])
  282. if forward > 0.5:
  283. if block.move_direction == 'horizontal':
  284. block.update_x_position(1)
  285. else:
  286. block.update_y_position(1)
  287. elif backward > 0.5:
  288. if block.move_direction == 'horizontal':
  289. block.update_x_position(-1)
  290. else:
  291. block.update_y_position(-1)
  292. else:
  293. if block.move_direction == 'horizontal':
  294. block.update_x_position(0)
  295. else:
  296. block.update_y_position(0)
  297.  
  298. def display(self):
  299. print("Optimal value:", self.model.getObjVal())
  300. for t in range(self.nr_moves):
  301. for block in self.blocks:
  302. if self.model.getVal(self.zf_rt[block.name, t]) > 0.5 \
  303. or self.model.getVal(self.zb_rt[block.name, t]) > 0.5:
  304. print(t, block.name, 'xl: %s, xr: %s, yd: %s, yu: %s' % (self.model.getVal(self.xl_bt[block.name, t]),
  305. self.model.getVal(self.xr_bt[block.name, t]),
  306. self.model.getVal(self.yd_bt[block.name, t]),
  307. self.model.getVal(self.yu_bt[block.name, t])
  308. )
  309. )
  310.  
  311.  
  312. if __name__ == '__main__':
  313. block1 = Block((0, 2), 1, 2, 'block1')
  314. block2 = Block((0, 3), 1, 2, 'block2')
  315. block3 = Block((0, 4), 1, 2, 'block3')
  316. block4 = Block((0, 5), 1, 2, 'block4')
  317. block5 = Block((0, 0), 2, 1, 'block5')
  318. block6 = Block((2, 4), 1, 2, 'block6')
  319. block7 = Block((2, 2), 2, 1, 'block7')
  320. block8 = Block((3, 2), 2, 1, 'block8')
  321. block9 = Block((4, 3), 3, 1, 'block9')
  322. block10 = Block((5, 3), 3, 1, 'block10')
  323. block11 = Block((4, 0), 1, 2, 'block11')
  324. block12 = Block((4, 1), 1, 2, 'block12')
  325.  
  326. blocks = [block1, block2, block3, block4, block5, block6, block7, block8, block9, block10, block11, block12]
  327. bounds = (6, 6)
  328. block2.set_color('yellow')
  329. problem = Problem(blocks, 20, block2, bounds)
  330. problem.initialize()
  331. problem.model.writeProblem(filename='./lp.lp')
  332. problem.solve()
  333. problem.update_blocks()
  334. problem.display()
  335.  
  336. plotter = BlockPlotter(blocks, len(block1.position), bounds)
  337. plotter.plot()
  338.  
Tags: MILP
Advertisement
Add Comment
Please, Sign In to add comment