Finding efficient solutions of the multicriteria assignment problem

Emmanuel Kwasi Mensah, Esmaeil Keshavarz, Mehdi Toloo

Research output: Chapter in Book/Report/Conference proceedingChapter


The assignment problem (AP) is one of the well-known and most studied combinatorial optimization problems. The single objective AP is an integer programming problem that can be solved with efficient algorithms such as the Hungarian or the successive shortest paths methods. On the other hand, finding and classifying all efficient assignments for a Multicriteria AP (MCAP) remains a controversial issue in Multicriteria Decision Making (MCDM) problems. In this chapter, we tackle the issue by using data envelopment analysis (DEA) models. Importantly, we focus on identifying the efficiency status of assignments using a two-phase algorithm. In phase I, a mixed-integer linear programming (MILP) based on the Free disposable Hull (FDH) model is used to determine minimal complete set (MCS) of efficient assignments. In Phase II, the DEA-BCC model is used to classify efficient assignments as supported or nonsupported. A numerical example is provided to illustrate the presented approach.

Original languageEnglish
Title of host publicationMulti-Objective Combinatorial Optimization Problems and Solution Methods
Number of pages19
ISBN (Electronic)9780128237991
ISBN (Print)9780128238004
Publication statusPublished - Jan 1 2022


  • Assignment problem
  • Data envelopment analysis (DEA)
  • Efficient solution
  • Multicriteria assignment problem (MCAP)
  • Nondominated points
  • Nonsupported efficient assignments
  • Supported efficient assignments
  • Two-phase algorithm

ASJC Scopus subject areas

  • Biochemistry, Genetics and Molecular Biology(all)

Cite this