如何在R中编写循环生成任意n的Gurobi大规模指派问题约束矩阵？

Hey there! I get that building constraint matrices for large-scale assignment problems in R with Gurobi can feel tricky when you're just starting out—let's break this down step by step. Based on your description of cumulative rows and incrementing n-i sections, here's how to generalize this to any n.

First, let's clarify the constraint matrix pattern based on your n=2 and n=3 examples:

• For n tasks and n workers, we have n² binary variables x_ij (where x_ij=1 means task i is assigned to worker j)
• There are two core constraint types:
  1. Task constraints: Each task must be assigned to exactly one worker. For task i, this translates to x_i1 + x_i2 + ... + x_in = 1, so the corresponding row in the matrix has 1s in positions (i-1)*n + 1 to i*n (cumulative for the task's variables)
  2. Worker constraints: Each worker must be assigned exactly one task. For worker j, this translates to x_1j + x_2j + ... + x_nj = 1, so the corresponding row has 1s in positions j, j+n, j+2n, ..., j+(n-1)*n (cumulative for the worker's variables)
• If your "n-i incrementing cumulative rows" refers to additional constraints (like limiting total assignments for the first k tasks), I've included an extended version below too.

Here's a reusable function to generate the core constraint matrix for any n:

# Function to generate core assignment problem constraint matrix
generate_assignment_constraints <- function(n) {
  num_vars <- n^2
  # Initialize empty matrix: 2n rows (n task constraints + n worker constraints), n² columns
  constr_mat <- matrix(0, nrow = 2*n, ncol = num_vars)
  
  # Generate task constraints: cumulative rows for each task
  for (i in 1:n) {
    # Set 1s for variables belonging to task i
    constr_mat[i, (i-1)*n + 1:n] <- 1
  }
  
  # Generate worker constraints: cumulative rows for each worker
  for (j in 1:n) {
    # Set 1s for variables belonging to worker j
    constr_mat[n + j, j + 0:(n-1)*n] <- 1
  }
  
  return(constr_mat)
}

Test the code #

You can verify with n=2 and n=3:

# Test n=2
cat("Constraint matrix for n=2:\n")
print(generate_assignment_constraints(2))

# Test n=3
cat("\nConstraint matrix for n=3:\n")
print(generate_assignment_constraints(3))

The output for n=2 will look like this:

[,1] [,2] [,3] [,4]
[1,]    1    1    0    0
[2,]    0    0    1    1
[3,]    1    0    1    0
[4,]    0    1    0    1

If you need additional cumulative constraints (e.g., total assignments for the first k tasks ≤ k, where k increments from 1 to n), use this extended function:

# Function to generate assignment matrix with extra cumulative constraints
generate_assignment_constraints_with_cumulative <- function(n) {
  num_vars <- n^2
  # 3n rows: 2n core constraints + n cumulative constraints
  constr_mat <- matrix(0, nrow = 3*n, ncol = num_vars)
  
  # Core task constraints
  for (i in 1:n) {
    constr_mat[i, (i-1)*n + 1:n] <- 1
  }
  
  # Core worker constraints
  for (j in 1:n) {
    constr_mat[n + j, j + 0:(n-1)*n] <- 1
  }
  
  # Cumulative constraints: first k tasks' total assignments ≤ k
  for (k in 1:n) {
    # Set 1s for all variables in the first k tasks
    constr_mat[2*n + k, 1:(k*n)] <- 1
  }
  
  return(constr_mat)
}

Once you have the constraint matrix, you can build and solve the Gurobi model like this:

library(gurobi)

# Set problem scale
n <- 3
num_vars <- n^2

# 1. Generate constraint matrix
constr_mat <- generate_assignment_constraints(n)

# 2. Define objective function (replace with your actual cost matrix)
cost_matrix <- matrix(c(1, 2, 3, 4, 5, 6, 7, 8, 9), nrow = n)
obj <- as.vector(cost_matrix)  # Convert to vector matching variable order x11,x12,x13,...x33

# 3. Constraint directions and right-hand values: core constraints are equality
dir <- rep("=", 2*n)
rhs <- rep(1, 2*n)

# 4. Variable type: binary (0 or 1)
vtype <- rep("B", num_vars)

# 5. Build Gurobi model
model <- list(
  obj = obj,
  A = constr_mat,
  sense = dir,
  rhs = rhs,
  vtype = vtype,
  modelname = "Large-Scale Assignment Problem"
)

# 6. Solve the model
result <- gurobi(model)

# Print results
cat("\nOptimal assignment (x_ij values):\n")
print(matrix(result$x, nrow = n, byrow = TRUE))  # Reshape to matrix for readability
cat("\nMinimum total cost:", result$objval, "\n")

If your cumulative constraint pattern differs from what I assumed, just tweak the index logic in the loops. For example, if you need cumulative rows for the first k workers instead of tasks, adjust the variable positions in the cumulative constraint loop.

内容的提问来源于stack exchange，提问作者5738