Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import pyscipopt as popt
- import matplotlib.path as mpath
- import matplotlib.patches as mpatches
- import matplotlib.pyplot as plt
- import math
- class Block:
- def __init__(self, coord, width, length, name):
- proper_dim = width > 0 and length > 0\
- and (width == 1 or length == 1)\
- and not (width == 1 and length == 1)
- if not proper_dim:
- self.position = None
- return
- xl, yl = coord[0], coord[1]
- self.length = length
- self.width = width
- self.xl, self.yl = xl, yl
- self.xl, self.yu = xl, yl + width
- self.xu, self.yl = xl + length, yl
- self.xu, self.yu = xl + length, yl + width
- self.position = {0: self.get_position()}
- self.t = 0
- self.move_direction = 'vertical' if length == 1 else 'horizontal'
- self.name = name
- self.color = 'blue'
- def get_position(self):
- return (self.xl, self.yl), (self.xl, self.yu), (self.xu, self.yl), (self.xu, self.yu)
- def update_x_position(self, deltaL):
- self.xl += deltaL
- self.xu += deltaL
- self.update_position()
- def update_y_position(self, deltaW):
- self.yl += deltaW
- self.yu += deltaW
- self.update_position()
- def update_position(self):
- self.t += 1
- self.position[self.t] = self.get_position()
- def set_color(self, color):
- self.color = color
- def __str__(self):
- if self.position:
- return str(self.position[self.t])
- else:
- return ''
- class BlockPlotter:
- def __init__(self, blocks, steps, bounds):
- self.fig = None
- self.ax = None
- self.blocks = blocks
- self.time_steps = steps
- self.bounds = bounds
- def create_figure(self):
- self.fig = plt.figure()
- even = self.time_steps
- if even == 1:
- self.axs = self.fig.subplots(1, even+1)
- for ax in self.axs:
- ax.set_xlim(0, bounds[0])
- ax.set_ylim(0, bounds[1])
- else:
- self.axs = self.fig.subplots(1, even)
- for ax in self.axs:
- ax.set_xlim(0, bounds[0])
- ax.set_ylim(0, bounds[1])
- def plot(self):
- if not self.fig:
- self.create_figure()
- if self.time_steps > 1:
- for step in range(self.time_steps):
- for block in self.blocks:
- block_position = block.position[step]
- if step == 0:
- patch = plt.Rectangle(block_position[0],
- block.length, block.width, edgecolor='black',
- facecolor=block.color)
- else:
- block_prev_position = block.position[step-1]
- if block.color == 'yellow':
- patch = plt.Rectangle(block_position[0],
- block.length, block.width, edgecolor='black',
- facecolor=block.color,
- hatch='/')
- else:
- patch = plt.Rectangle(block_position[0],
- block.length, block.width, edgecolor='black',
- facecolor=block.color)
- if block_position != block_prev_position and block.color != 'yellow':
- patch = plt.Rectangle(block_position[0],
- block.length, block.width, edgecolor='black',
- facecolor='green')
- self.axs[step].add_patch(patch)
- else:
- for block in self.blocks:
- block_position = block.position[0]
- patch = plt.Rectangle(block_position[0],
- block.length, block.width)
- self.axs[0].add_patch(patch)
- plt.show()
- class Problem:
- def __init__(self, blocks, nr_moves, primary_block, bounds):
- self.model = popt.Model('Block_Mover')
- self.blocks = blocks
- self.nr_moves = nr_moves
- self.primary_block = primary_block
- self.bounds = bounds
- def initialize(self):
- self.add_variables()
- self.add_constraints()
- self.add_objective()
- def add_variables(self):
- # block defining variables
- self.xl_bt = {}
- self.xr_bt = {}
- self.yd_bt = {}
- self.yu_bt = {}
- for t in range(self.nr_moves):
- for block in self.blocks:
- self.xl_bt[block.name, t] = self.model.addVar(vtype='C', name="xl_(%s,%s)" % (block.name, t))
- self.xr_bt[block.name, t] = self.model.addVar(vtype='C', name="xr_(%s,%s)" % (block.name, t))
- self.yd_bt[block.name, t] = self.model.addVar(vtype='C', name="yd_(%s,%s)" % (block.name, t))
- self.yu_bt[block.name, t] = self.model.addVar(vtype='C', name="yu_(%s,%s)" % (block.name, t))
- # does move
- self.zf_rt = {}
- self.zb_rt = {}
- for t in range(self.nr_moves):
- for block in self.blocks:
- self.zf_rt[block.name, t] = self.model.addVar(vtype='B',
- name="zf_(%s,%s)" % (block.name, t))
- self.zb_rt[block.name, t] = self.model.addVar(vtype='B',
- name="zb_(%s,%s)" % (block.name, t))
- # OR variables for feasibility
- self.delta_tij = {}
- for t in range(self.nr_moves):
- for i, block_outer in enumerate(self.blocks):
- for j, block_inner in enumerate(self.blocks):
- if i >= j:
- continue
- for k in range(4):
- key = (t, block_outer.name, block_inner.name, k)
- self.delta_tij[key] = self.model.addVar(vtype='B',
- name='delta_(%s,%s,%s,%s)' % key)
- # transition variables
- self.transition_t = {}
- for t in range(self.nr_moves):
- self.transition_t[t] = self.model.addVar(vtype='B',
- name='transition_(%s)' % t)
- def add_constraints(self):
- # initial position
- t = 0
- for block in self.blocks:
- self.model.addCons(self.xl_bt[block.name, t] == block.position[0][0][0],
- name='Starting_%s' % (block.name))
- self.model.addCons(self.yd_bt[block.name, t] == block.position[0][0][1],
- name='Starting_%s' % (block.name))
- # link block
- for t in range(self.nr_moves):
- for block in self.blocks:
- self.model.addCons(self.xr_bt[block.name, t] == self.xl_bt[block.name, t] + block.length,
- name='BlockRight_%s_%s' % (block.name, t))
- self.model.addCons(self.yu_bt[block.name, t] == self.yd_bt[block.name, t] + block.width,
- name='BlockUp_%s_%s' % (block.name, t))
- # block movement
- for block in self.blocks:
- for t in range(self.nr_moves - 1):
- if block.move_direction == 'horizontal':
- self.model.addCons(
- self.xl_bt[block.name, t+1] == self.xl_bt[block.name, t] + self.zf_rt[block.name, t]
- - self.zb_rt[block.name, t],
- name='Move_Hor_%s_%s' % (block.name, t))
- self.model.addCons(
- self.yd_bt[block.name, t + 1] == self.yd_bt[block.name, t],
- name='Move_Vert_%s_%s' % (block.name, t))
- else:
- self.model.addCons(
- self.yd_bt[block.name, t + 1] == self.yd_bt[block.name, t] + self.zf_rt[block.name, t]
- - self.zb_rt[block.name, t],
- name='Move_Vert_%s_%s' % (block.name, t))
- self.model.addCons(
- self.xl_bt[block.name, t + 1] == self.xl_bt[block.name, t],
- name='Move_Hor_%s_%s' % (block.name, t))
- # only one block can move per time
- for t in range(self.nr_moves):
- forward = []
- backward = []
- for block in self.blocks:
- forward.append(self.zf_rt[block.name, t])
- backward.append(self.zb_rt[block.name, t])
- self.model.addCons(popt.quicksum(forward) + popt.quicksum(backward) <= 1)
- # space bounds
- for t in range(self.nr_moves):
- for block in self.blocks:
- if block.move_direction == 'horizontal':
- self.model.addCons(self.xr_bt[block.name, t] <= self.bounds[0])
- else:
- self.model.addCons(self.yu_bt[block.name, t] <= self.bounds[0])
- # feasibility
- M = self.bounds[0]
- for t in range(self.nr_moves):
- for i, block_outer in enumerate(self.blocks):
- for j, block_inner in enumerate(self.blocks):
- if i >= j:
- continue
- key = (t, block_outer.name, block_inner.name, 0)
- self.model.addCons(self.xl_bt[block_outer.name, t] + block_outer.length
- <= self.xl_bt[block_inner.name, t] + M * self.delta_tij[key])
- key = (t, block_outer.name, block_inner.name, 1)
- self.model.addCons(self.xl_bt[block_inner.name, t] + block_inner.length
- <= self.xl_bt[block_outer.name, t] + M * self.delta_tij[key])
- key = (t, block_outer.name, block_inner.name, 2)
- self.model.addCons(self.yd_bt[block_outer.name, t] + block_outer.width
- <= self.yd_bt[block_inner.name, t] + M * self.delta_tij[key])
- key = (t, block_outer.name, block_inner.name, 3)
- self.model.addCons(self.yd_bt[block_inner.name, t] + block_inner.width
- <= self.yd_bt[block_outer.name, t] + M * self.delta_tij[key])
- self.model.addCons(
- popt.quicksum(self.delta_tij[t, block_outer.name, block_inner.name, k] for k in range(4)) <= 3
- )
- # final position is end
- self.model.addCons(self.xr_bt[self.primary_block.name, self.nr_moves - 1] == bounds[0])
- # transition between blocks
- for t in range(1, self.nr_moves):
- for block_outer in self.blocks:
- for block_inner in self.blocks:
- if block_outer.name == block_inner.name:
- continue
- was_moved_previous_t = popt.quicksum([self.zf_rt[block_outer.name, t -1],
- self.zb_rt[block_outer.name, t -1]])
- moved_current_t = popt.quicksum([self.zf_rt[block_inner.name, t],
- self.zb_rt[block_inner.name, t]])
- self.model.addCons(was_moved_previous_t + moved_current_t - 1 <= self.transition_t[t])
- def add_objective(self):
- z_forward = [val for val in self.zf_rt.values()]
- z_backward = [val for val in self.zb_rt.values()]
- transition = [val for val in self.transition_t.values()]
- self.model.setObjective(10 * popt.quicksum(z_forward) + 10 * popt.quicksum(z_backward)
- + popt.quicksum(transition), "minimize")
- def solve(self):
- self.model.optimize()
- def update_blocks(self):
- for t in range(self.nr_moves):
- for block in self.blocks:
- forward = self.model.getVal(self.zf_rt[block.name, t])
- backward = self.model.getVal(self.zb_rt[block.name, t])
- if forward > 0.5:
- if block.move_direction == 'horizontal':
- block.update_x_position(1)
- else:
- block.update_y_position(1)
- elif backward > 0.5:
- if block.move_direction == 'horizontal':
- block.update_x_position(-1)
- else:
- block.update_y_position(-1)
- else:
- if block.move_direction == 'horizontal':
- block.update_x_position(0)
- else:
- block.update_y_position(0)
- def display(self):
- print("Optimal value:", self.model.getObjVal())
- for t in range(self.nr_moves):
- for block in self.blocks:
- if self.model.getVal(self.zf_rt[block.name, t]) > 0.5 \
- or self.model.getVal(self.zb_rt[block.name, t]) > 0.5:
- print(t, block.name, 'xl: %s, xr: %s, yd: %s, yu: %s' % (self.model.getVal(self.xl_bt[block.name, t]),
- self.model.getVal(self.xr_bt[block.name, t]),
- self.model.getVal(self.yd_bt[block.name, t]),
- self.model.getVal(self.yu_bt[block.name, t])
- )
- )
- if __name__ == '__main__':
- block1 = Block((0, 2), 1, 2, 'block1')
- block2 = Block((0, 3), 1, 2, 'block2')
- block3 = Block((0, 4), 1, 2, 'block3')
- block4 = Block((0, 5), 1, 2, 'block4')
- block5 = Block((0, 0), 2, 1, 'block5')
- block6 = Block((2, 4), 1, 2, 'block6')
- block7 = Block((2, 2), 2, 1, 'block7')
- block8 = Block((3, 2), 2, 1, 'block8')
- block9 = Block((4, 3), 3, 1, 'block9')
- block10 = Block((5, 3), 3, 1, 'block10')
- block11 = Block((4, 0), 1, 2, 'block11')
- block12 = Block((4, 1), 1, 2, 'block12')
- blocks = [block1, block2, block3, block4, block5, block6, block7, block8, block9, block10, block11, block12]
- bounds = (6, 6)
- block2.set_color('yellow')
- problem = Problem(blocks, 20, block2, bounds)
- problem.initialize()
- problem.model.writeProblem(filename='./lp.lp')
- problem.solve()
- problem.update_blocks()
- problem.display()
- plotter = BlockPlotter(blocks, len(block1.position), bounds)
- plotter.plot()
Advertisement
Add Comment
Please, Sign In to add comment