Skip to content

Instantly share code, notes, and snippets.

@mo271
Created May 23, 2018 13:46
Show Gist options
  • Save mo271/ab2da800131e2725af8d98f4476223b1 to your computer and use it in GitHub Desktop.
Save mo271/ab2da800131e2725af8d98f4476223b1 to your computer and use it in GitHub Desktop.
This construct the integer program for a tiling problem; it can be easily adapted to exact covers, and allowing reuse of tiles
def milp(self, solver=None):
tiles = {}
for P in self.pieces():
tiles[P.frozenset()] = [Q.frozenset() for Q in P.isometric_copies(self._box, orientation_preserving=not(self._reflection))]
p = MixedIntegerLinearProgram(solver=solver)
x = p.new_variable(binary=True)
for i in self.space():
p.add_constraint(p.sum(x[T, P] for T in tiles for P in tiles[T] if i in P) <= 1)
for T in tiles:
p.add_constraint(p.sum(x[T, P] for P in tiles[T]) <= 1)
p.set_objective(p.sum(x.values()))
return p, x
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment