I have a list of animals with their parents, that is used to calculate the relationship between them.
I am using the Rsymphony R package to generate matings where each Female (Dam column) is crosses only once and each male (Sire column) is crossed twice. See bellow an reproducible example.

library("data.table")
library("Rsymphony")
library("optiSel")


Pedig = data.table(
  Indiv = as.character(c( 1,  2,  3,  4,  5,  6,  7, 8,  9, 10, 11, 12)),
  Sire  = as.character(c(NA, NA, NA,  2,  1,  1, NA, 2,  2,  3,  3,  1)),
  Dam   = as.character(c(NA, NA, NA, NA, NA,  5,  5, 6,  7,  8, 10,  9)),
  Sex   = as.character(c( 1,  1,  1,  1,  2,  2,  2, 2,  2,  2,  2,  2))
)
Pedig[, Sex := data.table::fifelse(Sex =="1", "male", "female")]
Pedig <- prePed(Pedig = Pedig)
pKin  <- pedIBD(Pedig)

Kin  <- pKin[Pedig[Sex == "female"][["Indiv"]], Pedig[Sex == "male"][["Indiv"]]]
Zeros <- 0*Kin

rhsM <- rep(nrow(Kin)/ncol(Kin), ncol(Kin))
ConM <- NULL
for(k in 1:length(rhsM)){
  Con <- Zeros
  Con[, k] <- 1
  ConM <- rbind(ConM, c(Con))
}

rhsF <- rep(1, nrow(Kin))
ConF <- NULL
for(k in 1:length(rhsF)){
  Con <- Zeros
  Con[k, ] <- 1
  ConF <- rbind(ConF, c(Con))
}

A <- rbind(ConF, ConM)
RHS <- c(rhsF, rhsM)
ub.n <- 1

# Rsymphony_solve_LP
if (is.na(ub.n)) {
  Bounds <- NULL
} else {
  Bounds <- list(upper=list(ind=1:(length(rhsM)*length(rhsF)), val=rep(ub.n, length(rhsM)*length(rhsF))))
}

Dir <- rep("==", length(RHS))
res <- Rsymphony::Rsymphony_solve_LP(
  obj=c(Kin),
  mat = A,
  dir = Dir,
  rhs = RHS,
  bounds = Bounds,
  types = "I",
  max = FALSE
)
 
Solution <- matrix(res$solution, nrow=nrow(Zeros), ncol=ncol(Zeros))
Solution <- as.data.table(Solution)
colnames(Solution) <- colnames(Kin)
Solution[, ID1 := rownames(Kin)]
Solution <- melt(Solution, id.vars="ID1", variable.name="ID2", value.name="n", variable.factor = FALSE)
Solution <- Solution[n>0]
Solution[, Value := pKin[ID2, ID1], by = .I]

The solution is to this simple example is shown below.

--------------------------------------
      ID1    ID2     n    Value
--------------------------------------
1:      9      1     1 0.062500
2:     11      1     1 0.046875
3:      5      2     1 0.000000
4:      7      2     1 0.000000
5:      8      3     1 0.000000
6:     12      3     1 0.000000
7:      6      4     1 0.000000
8:     10      4     1 0.062500
--------------------------------------

I am looking for a way to minimize the relationship of a Group instead of each pair of mating, in a way that the desired solution looks like the following table. In this case, I would like to provide the number of Groups (2) and the algorithm would create 2 groups with equal number of Sires and Dams.

--------------------------------------
      ID1    ID2     n    Value  Group
--------------------------------------
1:      9      1     1 0.062500      A
2:     11      1     1 0.046875      A
3:      5      2     1 0.000000      A
4:      7      2     1 0.000000      A
--------------------------------------
5:      8      3     1 0.000000      B
6:     12      3     1 0.000000      B
7:      6      4     1 0.000000      B
8:     10      4     1 0.062500      B
--------------------------------------

Can anyone help me with this problem?

Thank you.