GAP {FLSSS} | R Documentation |
Generalized Assignment Problem solver
Description
Given a number of agents and a number of tasks. An agent can finish a task with certain cost and profit. An agent also has a budget. Assign tasks to agents such that each agent costs no more than its budget while the total profit is maximized.
Usage
GAP(
maxCore = 7L,
agentsCosts,
agentsProfits,
agentsBudgets,
heuristic = FALSE,
tlimit = 60,
threadLoad = 8L,
verbose = TRUE
)
Arguments
maxCore |
Maximal threads to invoke. Ideally |
agentsCosts |
A numeric matrix. |
agentsProfits |
A numeric matrix. |
agentsBudgets |
A numeric vector. |
heuristic |
A boolean value. If |
tlimit |
A numeric value. Enforce function to return in |
threadLoad |
See |
verbose |
If |
Value
A list of size nine.
assignedAgents |
is a 2-column data frame, the mining result. The 1st column is task indexes. The 2nd column is agent indexes. |
assignmentProfit |
is the profit resulted from such assignment. |
assignmentCosts |
is a numeric vector. |
agentsBudgets |
is a numeric vector. |
unconstrainedMaxProfit |
is the would-be maximal profit if agents had infinite budgets. |
FLSSSsolution |
is the solution from mining the corresponding multidimensional Subset Sum problem. |
FLSSSvec |
is the multidimensional vector (a matrix) going into the multidimensional Subset Sum miner. |
MAXmat |
is the subset sum targets' upper bounds going into the multidimensional Subset Sum miner. |
foreShadowFLSSSvec |
is the multidimensional vector before comonotonization. |
Examples
# =====================================================================================
# Play random numbers
# =====================================================================================
# rm(list = ls()); gc()
agents = 5L
tasks = 12L
costs = t(as.data.frame(lapply(1L : agents, function(x) runif(tasks) * 1000)))
budgets = apply(costs, 1, function(x) runif(1, min(x), sum(x)))
profits = t(as.data.frame(lapply(1L : agents, function(x)
abs(rnorm(tasks) + runif(1, 0, 4)) * 10000)))
# A dirty function for examining the result's integrity. The function takes in
# the task-agent assignment, the profit or cost matrix M, and calculates the cost
# or profit generated by each agent. 'assignment' is a 2-column data
# frame, first column task, second column agent.
agentCostsOrProfits <- function(assignment, M)
{
n = ncol(M) * nrow(M)
M2 = matrix(numeric(n), ncol = tasks)
for(i in 1L : nrow(assignment))
{
x = as.integer(assignment[i, ])
M2[x[2], x[1]] = M[x[2], x[1]]
}
apply(M2, 1, function(x) sum(x))
}
dimnames(costs) = NULL
dimnames(profits) = NULL
names(budgets) = NULL
rst = FLSSS::GAP(maxCore = 7L, agentsCosts = costs, agentsProfits = profits,
agentsBudgets = budgets, heuristic = FALSE, tlimit = 60,
threadLoad = 8L, verbose = TRUE)
# Function also saves the assignment costs and profits
rst$assignedAgents
rst$assignmentProfit
rst$assignmentCosts
# Examine rst$assignmentCosts
if(sum(rst$assignedAgents) > 0) # all zeros mean the function has not found a solution.
agentCostsOrProfits(rst$assignedAgents, costs)
# Should equal rst$assignmentCosts and not surpass budgets
# Examine rst$assignmentProfits
if(sum(rst$assignedAgents) > 0)
sum(agentCostsOrProfits(rst$assignedAgents, profits))
# Should equal rst$assignmentProfit
# =====================================================================================
# Test case P03 from
# https://people.sc.fsu.edu/~jburkardt/datasets/generalized_assignment/
# =====================================================================================
agents = 3L
tasks = 8L
profits = t(matrix(c(
27, 12, 12, 16, 24, 31, 41, 13,
14, 5, 37, 9, 36, 25, 1, 34,
34, 34, 20, 9, 19, 19, 3, 34), ncol = agents))
costs = t(matrix(c(
21, 13, 9, 5, 7, 15, 5, 24,
20, 8, 18, 25, 6, 6, 9, 6,
16, 16, 18, 24, 11, 11, 16, 18), ncol = agents))
budgets = c(26, 25, 34)
rst = FLSSS::GAP(maxCore = 2L, agentsCosts = costs, agentsProfits = profits,
agentsBudgets = budgets, heuristic = FALSE, tlimit = 2,
threadLoad = 8L, verbose = TRUE)
agentCostsOrProfits(rst$assignedAgents, costs)
# Should equal rst$assignmentCosts and not surpass budgets
knownOptSolution = as.integer(c(3, 3, 1, 1, 2, 2, 1, 2))
knownOptSolution = data.frame(task = 1L : tasks, agent = knownOptSolution)
# Total profit from knownOptSolution:
sum(agentCostsOrProfits(knownOptSolution, profits))
# Total profit from FLSSS::GAP():
rst$assignmentProfit