A time-triggered dimension reduction algorithm for the task assignment problem

DOI10.1016/J.EJCON.2022.100692MaRDI QIDQ2095343zbMATH OpenOpenAlexWikidataFDO

Authors Han Wang, Kostas Margellos, Antonis Papachristodoulou

Publication date 9 November 2022

Published in European Journal of Control (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2204.11476

zbMATH Keywords

convex relaxationcombinatorial optimisationconvex optimisationtask assignment

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Abstract: The task assignment problem is fundamental in combinatorial optimisation, aiming at allocating one or more tasks to a number of agents while minimizing the total cost or maximizing the overall assignment benefit. This problem is known to be computationally hard since it is usually formulated as a mixed-integer programming problem. In this paper, we consider a novel time-triggered dimension reduction algorithm (TTDRA). We propose convexification approaches to convexify both the constraints and the cost function for the general non-convex assignment problem. The computational speed is accelerated via our time-triggered dimension reduction scheme, where the triggering condition is designed based on the optimality tolerance and the convexity of the cost function. Optimality and computational efficiency are verified via numerical simulations on benchmark examples.

Recommendations

• Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches
• Solving the multidimensional assignment problem by a cross-entropy method
• Dynamic generalized assignment problems with stochastic demands and multiple agent-task relationships
• A hybrid genetic/optimization algorithm for a task allocation problem
• Solving the many to many assignment problem by improving the Kuhn-Munkres algorithm with backtracking

Cites work

• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• A new algorithm for the assignment problem
• A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives
• Assignment Problems and the Location of Economic Activities
• On convex relaxations for quadratically constrained quadratic programming
• Semidefinite programming approach for the quadratic assignment problem with a sparse graph
• Semidefinite programming relaxations for the quadratic assignment problem
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• \(L_p\)-norm regularization algorithms for optimization over permutation matrices

Cited in

(1)

• Task preference-based bottleneck assignment problem

This page was built for publication: A time-triggered dimension reduction algorithm for the task assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2095343)