A logarithmic method for reducing binary variables and inequality constraints in solving task assignment problems

Han-Lin Li, Yao Huei Huang, Shu Cherng Fang

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

This paper studies the classical task assignment problem (TAP) in which M unbreakable tasks are assigned to N agents with the objective to minimize the communication and process costs subject to each agent's capacity constraint. Because a large-size TAP involves many binary variables, most, if not all, traditional methods experience the difficulty in solving the problem within a reasonable time period. Recent works present a logarithmic approach to reduce the number of binary variables in problems with mixed-integer variables. This study proposes a new logarithmic method that significantly reduces the numbers of binary variables and inequality constraints in solving task assignment problems. Our numerical experiments demonstrate that the proposed method is superior to other known methods of this kind for solving large-size TAPs.

Original languageEnglish
Pages (from-to)643-653
Number of pages11
JournalINFORMS Journal on Computing
Volume25
Issue number4
DOIs
StatePublished - 1 Sep 2013

Keywords

  • Binary variables
  • Mixed-integer programming problem
  • Task assignment problem

Fingerprint Dive into the research topics of 'A logarithmic method for reducing binary variables and inequality constraints in solving task assignment problems'. Together they form a unique fingerprint.

  • Cite this