Optimization, System Analysis, and Operations Research

Pareto set design when combining feasible solutions of the multicriteria axial assignment problem

L. G. Afraimovich, M. D. Emelin

Lobachevsky Nizhny Novgorod State University, Nizhny Novgorod, Russia

Abstract: —This paper considers a two-criteria three-index axial assignment problem, representing a classical NP-hard problem even in the single-criterion case. Within this formulation, the problem of combining feasible solutions is posed; it is an assignment problem on the set of solutions containing only the components of the feasible solutions selected. A polynomial algorithm is proposed to find Pareto optimal solutions in the combination problem of two feasible solutions. Based on this algorithm, a heuristic approach is constructed to estimate the Pareto set of the multicriteria axial assignment problem.

Keywords: axial assignment problem, multi-index problems, multicriteria problems, Pareto optimality, combining solutions, polynomial solvability, NP-hardness.

Presented by the member of Editorial Board: A. A. Lazarev

Received: 10.11.2024
Revised: 12.02.2025
Accepted: 26.02.2025

DOI: 10.31857/S0005231025050056

 English version: Automation and Remote Control, 2025, 86:5, 432–444