Created
May 23, 2018 13:46
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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