I would like to solve the problem of optimizing the packing N equally-sized squares of…
- User
I would like to solve the problem of optimizing the packing N equally-sized squares of maximal size into a larger size with (x,y) in [-L, L] and [-L, L]. I have a function that does the following in a differentiable manner:
Function: get_maximal_expansion(squares, L) Input: squares is a tensor of shape Nx3, representing the coordinates of each square and angle as (x,y,theta). L is 2. Output: The maximal size of all equally-sized squares, such that no squares overlap
As a first pass, let's create a neural network that considers the case of N=17. Let's use a transformer architecture. We start off with an empty list. On each pass of the transformer, we can get it to generate the position of the next square position. We run N=17 passes of the transformer and get the final set of coordinates. We can then train the transformer somehow so that it gets us the best packing. Write me python code using Pytorch (2.7.1+cu118) that does this.
Assistant
Here's the final code with some additional improvements, such as better initialization and visualization of the packing:
import torch import torch.nn as nn import torch.optim as optim import math import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np device = torch.device("cuda" if torch.cuda.is_available() else "cpu") class PositionalEncoding(nn.Module): def __init__(self, d_model, max_len=50): super(PositionalEncoding, self).__init__() pe = torch.zeros(max_len, d_model) position = torch.arange(0, max_len, dtype=torch.float).unsqueeze(1) div_term = torch.exp(torch.arange(0, d_model, 2).float() * (-math.log(10000.0) / d_model)) pe[:, 0::2] = torch.sin(position * div_term) pe[:, 1::2] = torch.cos(position * div_term) pe = pe.unsqueeze(0).transpose(0, 1) self.register_buffer('pe', pe) def forward(self, x): return x + self.pe[:x.size(0), :] class SquarePackerTransformer(nn.Module): def __init__(self, N=17, d_model=128, nhead=4, num_layers=4, dim_feedforward=512): super(SquarePackerTransformer, self).__init__() self.N = N self.d_model = d_model self.input_dim = 3 # x, y, theta self.input_embedding = nn.Linear(self.input_dim, d_model) self.pos_encoder = PositionalEncoding(d_model, max_len=N + 1) decoder_layer = nn.TransformerDecoderLayer(d_model, nhead, dim_feedforward, batch_first=False) self.decoder = nn.TransformerDecoder(decoder_layer, num_layers) self.output_head = nn.Linear(d_model, 3) self.register_buffer('dummy_memory', torch.zeros(1, 1, d_model)) def forward(self): B = 1 # Initialize with random positions within [-2, 2] and random angles initial_config = torch.zeros(1, B, self.input_dim).to(device) initial_config[0, 0, :2] = torch.rand(2) * 4 - 2 # Random in [-2, 2] initial_config[0, 0, 2] = torch.rand(1) * 2 * math.pi - math.pi # Random angle in [-pi, pi] current_config = initial_config generated_squares = [] for i in range(self.N): seq_len = current_config.size(0) tgt_emb = self.input_embedding(current_config) * math.sqrt(self.d_model) tgt_emb = self.pos_encoder(tgt_emb) mask = nn.Transformer.generate_square_subsequent_mask(seq_len).to(device) memory = self.dummy_memory.repeat(1, B, 1) output = self.decoder(tgt_emb, memory, tgt_mask=mask) next_square_hidden = output[-1, :, :] raw_params = self.output_head(next_square_hidden) xy = torch.tanh(raw_params[:, :2]) * 2.0 theta = torch.tanh(raw_params[:, 2]) * math.pi processed_params = torch.cat([xy, theta.unsqueeze(1)], dim=1) generated_squares.append(processed_params) if i < self.N - 1: current_config = torch.cat([current_config, processed_params.unsqueeze(0)], dim=0) final_config = torch.cat(generated_squares, dim=0) return final_config def get_maximal_expansion(squares, L=2.0): N = squares.shape[0] x = squares[:, 0] y = squares[:, 1] theta = squares[:, 2] constraints = [] for i in range(N): xi, yi, theta_i = x[i], y[i], theta[i] cos_theta = torch.cos(theta_i) sin_theta = torch.sin(theta_i) for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]: coeff_x = a * cos_theta - b * sin_theta coeff_y = a * sin_theta + b * cos_theta # Constraint 1: xi + (s/2)*coeff_x >= -L C1 = 2*(-L - xi) C2 = 2*(L + xi) s_constraint1 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6)) # Constraint 2: xi + (s/2)*coeff_x <= L C1 = 2*(L - xi) C2 = 2*(-L + xi) s_constraint2 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6)) # Constraint 3: yi + (s/2)*coeff_y >= -L C1 = 2*(-L - yi) C2 = 2*(L + yi) s_constraint3 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6)) # Constraint 4: yi + (s/2)*coeff_y <= L C1 = 2*(L - yi) C2 = 2*(-L + yi) s_constraint4 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6)) constraints.extend([s_constraint1, s_constraint2, s_constraint3, s_constraint4]) # Pairwise constraints for i in range(N): for j in range(i+1, N): xi, yi, theta_i = x[i], y[i], theta[i] xj, yj, theta_j = x[j], y[j], theta[j] dx = xi - xj dy = yi - yj d = torch.sqrt(dx**2 + dy**2 + 1e-6) # Add small value to avoid division by zero phi = torch.atan2(dy, dx) f1 = torch.abs(torch.cos(theta_i - phi)) + torch.abs(torch.sin(theta_i - phi)) f2 = torch.abs(torch.cos(theta_j - phi)) + torch.abs(torch.sin(theta_j - phi)) if (f1 + f2) > 0: s_constraint = 2 * d / (f1 + f2 + 1e-6) else: s_constraint = float('inf') constraints.append(s_constraint) if constraints: constraints_tensor = torch.tensor([c if isinstance(c, torch.Tensor) else torch.tensor(c) for c in constraints if c != float('inf')]) if constraints_tensor.numel() > 0: maximal_s = torch.min(constraints_tensor) else: maximal_s = torch.tensor(0.0) else: maximal_s = torch.tensor(0.0) return maximal_s def visualize_packing(config, s, L=2.0): config = config.detach().cpu().numpy() N = config.shape[0] x, y, theta = config[:, 0], config[:, 1], config[:, 2] fig, ax = plt.subplots(figsize=(8, 8)) # Draw the larger square larger_square = patches.Rectangle((-L, -L), 2*L, 2*L, linewidth=2, edgecolor='black', facecolor='none') ax.add_patch(larger_square) # Draw each smaller square for i in range(N): xi, yi, theta_i = x[i], y[i], theta[i] cos_theta = np.cos(theta_i) sin_theta = np.sin(theta_i) # Compute the four vertices of the square vertices = [] for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]: x_v = xi + (a * cos_theta - b * sin_theta) * s/2 y_v = yi + (a * sin_theta + b * cos_theta) * s/2 vertices.append((x_v, y_v)) # Close the polygon by repeating the first vertex at the end vertices.append(vertices[0]) xs, ys = zip(*vertices) ax.plot(xs, ys, 'b-') ax.fill(xs, ys, 'skyblue', alpha=0.5) ax.set_xlim(-L, L) ax.set_ylim(-L, L) ax.set_aspect('equal') ax.set_title(f"Packing of {N} squares with size {s:.4f}") plt.show() def train(): print(f"Starting optimization for N=17 on {device}") model = SquarePackerTransformer(N=17, d_model=128, nhead=4, num_layers=4).to(device) optimizer = optim.Adam(model.parameters(), lr=0.001) num_epochs = 1000 best_size = -float('inf') best_config = None for epoch in range(num_epochs): model.train() optimizer.zero_grad() config = model() maximal_size = get_maximal_expansion(config, L=2.0) loss = -maximal_size loss.backward() optimizer.step() maximal_size_val = maximal_size.item() loss_val = loss.item() if epoch % 100 == 0: print(f"Epoch {epoch}/{num_epochs} | Loss: {loss_val:.4f} | Maximal Size: {maximal_size_val:.4f}") if maximal_size_val > 0: # Only visualize if s is positive visualize_packing(config, maximal_size_val, L=2.0) if maximal_size_val > best_size: best_size = maximal_size_val best_config = config.detach().clone() print(f"*** New Best Size found: {best_size:.4f} at Epoch {epoch} ***") print(f"\nTraining finished. Best maximal size achieved: {best_size:.4f}") if best_config is not None: print("Best configuration:") print(best_config) visualize_packing(best_config, best_size, L=2.0) if __name__ == '__main__': train()This code should now be able to train a transformer model to generate positions and angles for 17 squares within a larger square, maximizing the size of the smaller squares while ensuring they do not overlap and fit within the larger square. The visualization function helps to see the progress of the packing during training.
import torch import torch.nn as nn import torch.optim as optim import math import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np device = torch.device("cuda" if torch.cuda.is_available() else "cpu") class PositionalEncoding(nn.Module): def __init__(self, d_model, max_len=50): super(PositionalEncoding, self).__init__() pe = torch.zeros(max_len, d_model) position = torch.arange(0, max_len, dtype=torch.float).unsqueeze(1) div_term = torch.exp(torch.arange(0, d_model, 2).float() * (-math.log(10000.0) / d_model)) pe[:, 0::2] = torch.sin(position * div_term) pe[:, 1::2] = torch.cos(position * div_term) pe = pe.unsqueeze(0).transpose(0, 1) self.register_buffer('pe', pe) def forward(self, x): return x + self.pe[:x.size(0), :] class SquarePackerTransformer(nn.Module): def __init__(self, N=17, d_model=128, nhead=4, num_layers=4, dim_feedforward=512): super(SquarePackerTransformer, self).__init__() self.N = N self.d_model = d_model self.input_dim = 3 # x, y, theta self.input_embedding = nn.Linear(self.input_dim, d_model) self.pos_encoder = PositionalEncoding(d_model, max_len=N + 1) decoder_layer = nn.TransformerDecoderLayer(d_model, nhead, dim_feedforward, batch_first=False) self.decoder = nn.TransformerDecoder(decoder_layer, num_layers) self.output_head = nn.Linear(d_model, 3) self.register_buffer('dummy_memory', torch.zeros(1, 1, d_model)) def forward(self): B = 1 # Initialize with random positions within [-2, 2] and random angles initial_config = torch.zeros(1, B, self.input_dim).to(device) initial_config[0, 0, :2] = torch.rand(2) * 4 - 2 # Random in [-2, 2] initial_config[0, 0, 2] = torch.rand(1) * 2 * math.pi - math.pi # Random angle in [-pi, pi] current_config = initial_config generated_squares = [] for i in range(self.N): seq_len = current_config.size(0) tgt_emb = self.input_embedding(current_config) * math.sqrt(self.d_model) tgt_emb = self.pos_encoder(tgt_emb) mask = nn.Transformer.generate_square_subsequent_mask(seq_len).to(device) memory = self.dummy_memory.repeat(1, B, 1) output = self.decoder(tgt_emb, memory, tgt_mask=mask) next_square_hidden = output[-1, :, :] raw_params = self.output_head(next_square_hidden) xy = torch.tanh(raw_params[:, :2]) * 2.0 theta = torch.tanh(raw_params[:, 2]) * math.pi processed_params = torch.cat([xy, theta.unsqueeze(1)], dim=1) generated_squares.append(processed_params) if i < self.N - 1: current_config = torch.cat([current_config, processed_params.unsqueeze(0)], dim=0) final_config = torch.cat(generated_squares, dim=0) return final_config def get_maximal_expansion(squares, L=2.0): N = squares.shape[0] x = squares[:, 0] y = squares[:, 1] theta = squares[:, 2] constraints = [] for i in range(N): xi, yi, theta_i = x[i], y[i], theta[i] cos_theta = torch.cos(theta_i) sin_theta = torch.sin(theta_i) for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]: coeff_x = a * cos_theta - b * sin_theta coeff_y = a * sin_theta + b * cos_theta # Constraint 1: xi + (s/2)*coeff_x >= -L C1 = 2*(-L - xi) C2 = 2*(L + xi) s_constraint1 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6)) # Constraint 2: xi + (s/2)*coeff_x <= L C1 = 2*(L - xi) C2 = 2*(-L + xi) s_constraint2 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6)) # Constraint 3: yi + (s/2)*coeff_y >= -L C1 = 2*(-L - yi) C2 = 2*(L + yi) s_constraint3 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6)) # Constraint 4: yi + (s/2)*coeff_y <= L C1 = 2*(L - yi) C2 = 2*(-L + yi) s_constraint4 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6)) constraints.extend([s_constraint1, s_constraint2, s_constraint3, s_constraint4]) # Pairwise constraints for i in range(N): for j in range(i+1, N): xi, yi, theta_i = x[i], y[i], theta[i] xj, yj, theta_j = x[j], y[j], theta[j] dx = xi - xj dy = yi - yj d = torch.sqrt(dx**2 + dy**2 + 1e-6) # Add small value to avoid division by zero phi = torch.atan2(dy, dx) f1 = torch.abs(torch.cos(theta_i - phi)) + torch.abs(torch.sin(theta_i - phi)) f2 = torch.abs(torch.cos(theta_j - phi)) + torch.abs(torch.sin(theta_j - phi)) if (f1 + f2) > 0: s_constraint = 2 * d / (f1 + f2 + 1e-6) else: s_constraint = float('inf') constraints.append(s_constraint) if constraints: constraints_tensor = torch.tensor([c if isinstance(c, torch.Tensor) else torch.tensor(c) for c in constraints if c != float('inf')]) if constraints_tensor.numel() > 0: maximal_s = torch.min(constraints_tensor) else: maximal_s = torch.tensor(0.0) else: maximal_s = torch.tensor(0.0) return maximal_s def visualize_packing(config, s, L=2.0): config = config.detach().cpu().numpy() N = config.shape[0] x, y, theta = config[:, 0], config[:, 1], config[:, 2] fig, ax = plt.subplots(figsize=(8, 8)) # Draw the larger square larger_square = patches.Rectangle((-L, -L), 2*L, 2*L, linewidth=2, edgecolor='black', facecolor='none') ax.add_patch(larger_square) # Draw each smaller square for i in range(N): xi, yi, theta_i = x[i], y[i], theta[i] cos_theta = np.cos(theta_i) sin_theta = np.sin(theta_i) # Compute the four vertices of the square vertices = [] for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]: x_v = xi + (a * cos_theta - b * sin_theta) * s/2 y_v = yi + (a * sin_theta + b * cos_theta) * s/2 vertices.append((x_v, y_v)) # Close the polygon by repeating the first vertex at the end vertices.append(vertices[0]) xs, ys = zip(*vertices) ax.plot(xs, ys, 'b-') ax.fill(xs, ys, 'skyblue', alpha=0.5) ax.set_xlim(-L, L) ax.set_ylim(-L, L) ax.set_aspect('equal') ax.set_title(f"Packing of {N} squares with size {s:.4f}") plt.show() def train(): print(f"Starting optimization for N=17 on {device}") model = SquarePackerTransformer(N=17, d_model=128, nhead=4, num_layers=4).to(device) optimizer = optim.Adam(model.parameters(), lr=0.001) num_epochs = 1000 best_size = -float('inf') best_config = None for epoch in range(num_epochs): model.train() optimizer.zero_grad() config = model() maximal_size = get_maximal_expansion(config, L=2.0) loss = -maximal_size loss.backward() optimizer.step() maximal_size_val = maximal_size.item() loss_val = loss.item() if epoch % 100 == 0: print(f"Epoch {epoch}/{num_epochs} | Loss: {loss_val:.4f} | Maximal Size: {maximal_size_val:.4f}") if maximal_size_val > 0: # Only visualize if s is positive visualize_packing(config, maximal_size_val, L=2.0) if maximal_size_val > best_size: best_size = maximal_size_val best_config = config.detach().clone() print(f"*** New Best Size found: {best_size:.4f} at Epoch {epoch} ***") print(f"\nTraining finished. Best maximal size achieved: {best_size:.4f}") if best_config is not None: print("Best configuration:") print(best_config) visualize_packing(best_config, best_size, L=2.0) if __name__ == '__main__': train()This code implements a transformer-based approach to solve the problem of packing 17 equally-sized squares into a larger square of size 4x4 (from -2 to 2 in both x and y directions). The goal is to maximize the size of the smaller squares while ensuring they do not overlap and fit within the larger square. The
get_maximal_expansionfunction computes the maximal size of the smaller squares given their positions and angles, and the model is trained to maximize this size using gradient descent. The visualization function helps to visualize the packing during training.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.