GAP: Generalized Assignment Problem solver

In FLSSS: Mining Rigs for Problems in the Subset Sum Family

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 maxCore should not surpass the total logical processors on machine.
agentsCosts	A numeric matrix. agentsCosts[i, j] is the cost for agent i to finish task j.
agentsProfits	A numeric matrix. agentsProfits[i, j] is the profit from agent i finishing task j.
agentsBudgets	A numeric vector. agentsBudgets[i] is agent i's budget.
heuristic	A boolean value. If TRUE, the function returns once it has found a solution whose sum of ranks of the profits becomes no less than that of the optimal. See heuristic in mmKnapsack().
tlimit	A numeric value. Enforce function to return in tlimit seconds.
threadLoad	See avgThreadLoad in mFLSSSpar().
verbose	If TRUE, function prints progress.

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. Value$assignmentCosts[i] is the cost of agent i.
agentsBudgets	is a numeric vector. Value$agentsBudgets[i] shows the budget of agent i.
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

FLSSS documentation built on May 17, 2022, 5:09 p.m.