Использование оптимизатора в R [Ограничение параметров для отдельных натуральных чисел]

Question

Я пытаюсь исследовать метод оптимизации в R для решения сценария, но я не могу ограничить работу функции по желанию. Я прочитал страницы справки, но не смог добиться значительного прогресса, так как я новичок в этой области.

Позвольте мне объяснить вам проблему в меньшем кадре. У меня есть dataframe, который содержит множество студентов

scoreDf <- data.frame(Name = c("A", "B", "C"), Score = c(10, 15, 25)) 

Цель: Для выбора студентов (или групп студентов) и заказать их в такой последовательности, что мы минимизируем сумму продукт их оценки и их в следующей последовательности:

Минимум SUM (оценка * позиция); условия: Сумма баллов> = 30, положения = 0: N (различные целые числа в последовательности, 0 можно повторить) и вернуть вектор позиций

Например:

В данных данных желаемое решение представляет собой последовательность 2,0,1 для A, B, C. Это означает, что учитываются только A и C, поскольку их сумма баллов = 10 + 25 = 35> = 30 И значение целевой функции 10 * 2 + 25 * 1 = 45, что является минимальным значением. Мне интересно узнать этот результат, что CA - это группа в указанном порядке.

Я попытался использовать оптимизм, но я мог бы добиться значительного прогресса. Пожалуйста, помогите. Спасибо

Answer 1

Позвольте мне попробовать. Первым шагом было бы разработать математическую модель, которая описала бы проблему. Моя идея состояла бы в том, чтобы назначить учащимся i на позиции j с использованием двоичной переменной x (i, j). Такая модель может выглядеть следующим образом:

Это модель с линейной целью и линейными ограничениями, так и с бинарными переменными. Это модель смешанного целочисленного программирования (MIP) и, следовательно, требует решения MIP. Оптимист R не соответствовал бы счету. Подходящими решениями с открытым исходным кодом могут быть glpk, lpsolve и COIN CBC (см. Список here).

Примечание. Если проблема очень велика, есть некоторые возможности немного упростить модель и, возможно, сделать ее более эффективной, но для небольших наборов данных эта формулировка должна быть прекрасной.

Answer 2

optim предназначен для непрерывной оптимизации, но эта проблема является целым программированием.

1) lpSolve Пусть X [i, j] = 1, если ученик j находится в положении i и равен нулю в противном случае. Затем используйте lp из пакета lpSolve, оптимизируя по 9 элементам X. Ограничьте X так, чтобы сумма каждой строки и суммы каждого столбца X могла быть не более 1, а сумма баллов равна = 30. объективные коэффициенты - это временные баллы позиций. Укажите, что переменные X являются бинарными, то есть 0/1.

library(lpSolve) 
scoreDf <- data.frame(Name = c("A", "B", "C"), Score = c(10, 15, 25)) 
n <- nrow(scoreDf) 

obj <- c(outer(1:n, scoreDf$Score)) # obj fun coef of X[i,j] is position[i] * score[j] 
cons <- rbind(outer(1:n, c(col(diag(n))), "==") + 0, # lhs of col sum constraints on X 
       outer(1:n, c(row(diag(n))), "==") + 0, # lhs of row sum constraints on X 
       rep(scoreDf$Score, each = n)) # lhs of sum of scores constraint on X 
# col and row sums <= 1; sum of scores >= 30 
dir <- c(rep("<=", 2 * n), ">=") 
rhs <- c(rep(1, 2 * n), 30) 
ans <- lp("min", obj, cons, dir, rhs, all.bin = TRUE) 

ans$objval 
## [1] 45 

# reshape ans$solution vector into a 0/1 matrix whose rows are positions and cols are names 
X <- matrix(ans$solution, n, n, dimnames = list(pos = 1:n, Name = scoreDf$Name)) 
X 
## Name 
## pos A B C 
## 1 0 0 1 
## 2 1 0 0 
## 3 0 0 0 

1:n %*% X # solution sequence 
##  Name 
##  A B C 
## [1,] 2 0 1 

# rework X into a data frame showing the Name for each pos 
s <- subset(as.data.frame.table(X), Freq == 1, select = -Freq) 
s[order(s$pos), ] 
## pos Name 
## 7 1 C 
## 2 2 A 

2) КОМБИНАТ Другой подход, чтобы сделать перебор по всем перестановкам и выбрать один с минимальной целью. Это может занять слишком много времени и памяти для больших входов, но для небольших входов это кажется практичным, и может быть полезно иметь независимую альтернативу для перекрестной проверки. Мы используем permn из пакета combinat для генерации перестановок. Для каждой перестановки найдите минимальное количество ведущих имен, чьи баллы суммируются более чем на 29 (no), а затем вычисляют цель только для тех (дающих 0 остальным), давая DF. В каждой строке DF перечислены перестановки no и объектное значение obj. Затем, используя which.min, найдите строку DF, имеющую минимальный объектив.

library(combinat) 
sc <- setNames(scoreDf$Score, as.character(scoreDf$Name)) 
DF <- do.call(rbind, permn(names(sc), function(x) { 
    no <- findInterval(29, cumsum(sc[x])) + 1 # only need first no 
    data.frame(t(x), no, obj = sum(head(sc[x], no) * 1:no)) 
})) 
ix <- which.min(DF$obj) 
cbind(DF[ix, 1:DF[ix, "no"]], obj = DF$obj[ix]) 
## X1 X2 obj 
## 3 C A 45