# ============================================================
# チーム分け最適化
# 過去のグループワーク履歴をもとに、過去ペアの重複を最小化する
# ============================================================
# 必要パッケージ
# install.packages(c("ompr", "ompr.roi", "ROI"))
# install.packages(c("highs", "ROI.plugin.highs"))
library(tidyverse)
library(readxl)
library(highs)
library(ompr)
library(ompr.roi)
library(ROI)

# ============================================================
# 1. データ読み込み
# ============================================================
df <- read_excel("20260601_チーム分け.xlsx") 

n <- nrow(df)        # 学生数
G <- 4               # グループ数
sizes <- c(6, 6, 6, 6)  # 各グループの定員（合計=n）

cat("学生数:", n, "\n")
cat("グループ数:", G, "\n")
cat("グループ定員:", sizes, "\n\n")

# ============================================================
# 2. 重み行列の計算（過去に同じグループだった回数）
# ============================================================
history_cols <- c("1回目", "2回目")

w <- matrix(0, n, n)
for (col in history_cols) {
  grp <- df[[col]]
  for (i in 1:(n - 1)) {
    for (j in (i + 1):n) {
      if (!is.na(grp[i]) && !is.na(grp[j]) && grp[i] == grp[j]) {
        w[i, j] <- w[i, j] + 1
        w[j, i] <- w[j, i] + 1
      }
    }
  }
}

cat("過去ペアの延べ数:", sum(w) / 2, "\n\n")

# ============================================================
# 3. 整数計画問題の定式化（ompr）
# ============================================================
# 決定変数:
#   x[i, g] ∈ {0,1}：学生iがグループgに入るか
#   y[i, j] ∈ {0,1}：学生iとjが今回同じグループに入るか（補助変数）
#
# 目的関数: min Σ_{i<j} w[i,j] * y[i,j]
# 制約①: Σ_g x[i,g] = 1  ∀i
# 制約②: Σ_i x[i,g] <= sizes[g]  ∀g
# 制約③: y[i,j] >= x[i,g] + x[j,g] - 1  ∀i,j,g（線形化）

model <- MIPModel() |>
  # 決定変数
  add_variable(x[i, g], i = 1:n, g = 1:G, type = "binary") |>
  add_variable(y[i, j], i = 1:n, j = 1:n, i < j, type = "binary") |>

  # 目的関数
  set_objective(
    sum_over(w[i, j] * y[i, j], i = 1:n, j = 1:n, i < j),
    sense = "min"
  ) |>

  # 制約①：各学生は1グループに所属
  add_constraint(sum_over(x[i, g], g = 1:G) == 1, i = 1:n) |>

  # 制約②：グループサイズ上限
  add_constraint(sum_over(x[i, g], i = 1:n) <= sizes[g], g = 1:G) |>

  # 制約③：y[i,j]の線形化
  add_constraint(
    y[i, j] >= x[i, g] + x[j, g] - 1,
    i = 1:n, j = 1:n, i < j, g = 1:G
  )

# ============================================================
# 4. 求解
# ============================================================
cat("求解中...\n")
# result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))
result <- solve_model(model, with_ROI(solver = "highs", verbose = TRUE))

cat("\n求解ステータス:", result$status, "\n")
cat("最適ペナルティ（過去ペアの重複）:", objective_value(result), "\n\n")

# ============================================================
# 5. 結果の取り出し
# ============================================================
x_val <- get_solution(result, x[i, g])

assignment <- 
  x_val |>
  filter(value > 0.5) |>
  select(i, g) |>
  arrange(g, i) |>
  mutate(氏名 = df$氏名[i])

cat("【グループ分け結果】\n")
for (g in 1:G) {
  members <- assignment |> filter(g == !!g) |> pull(氏名)
  cat(sprintf("グループ%s（%d人）: %s\n", LETTERS[1:G][g], length(members),
              paste(members, collapse = ", ")))
}

# 重複ペアの詳細
cat("\n【重複した過去ペア】\n")
total_overlap <- 0
for (g in 1:G) {
  members_idx <- assignment |> filter(g == !!g) |> pull(i)
  if (length(members_idx) >= 2) {
    pairs <- combn(members_idx, 2)
    for (k in 1:ncol(pairs)) {
      ii <- pairs[1, k]; jj <- pairs[2, k]
      if (w[ii, jj] > 0) {
        cat(sprintf("  %sと%s: %d回の重複\n",
                    df$氏名[ii], df$氏名[jj], w[ii, jj]))
        total_overlap <- total_overlap + w[ii, jj]
      }
    }
  }
}
cat("重複の合計（ペナルティ）:", total_overlap, "\n\n")

# ============================================================
# 6. 結果をCSVに追記
# ============================================================
df_out <- df |>
  left_join(
    assignment |> select(氏名, g) |> mutate(g = LETTERS[1:G][g]) |> rename(`3回目` = g),
    by = "氏名"
  )
fn <- str_c(format(Sys.Date(), "%Y%m%d"), "_チーム分け_結果.csv")
write_excel_csv(df_out, fn)
cat("結果を", fn, "に保存しました。\n")