A novel convex dual approach to three-dimensional assignment problem: theoretical analysis

Jingqun Li (), R. Tharmarasa, Daly Brown, Thia Kirubarajan and Krishna R. Pattipati
Additional contact information
Jingqun Li: McMaster University
R. Tharmarasa: McMaster University
Daly Brown: General Dynamics Missions Systems-Canada
Thia Kirubarajan: McMaster University
Krishna R. Pattipati: University of Connecticut

Computational Optimization and Applications, 2019, vol. 74, issue 2, No 5, 516 pages

Abstract: Abstract In this paper, we propose a novel convex dual approach to the three dimensional assignment problem, which is an NP-hard binary programming problem. It is shown that the proposed dual approach is equivalent to the Lagrangian relaxation method in terms of the best value attainable by the two approaches. However, the pure dual representation is not only more elegant, but also makes the theoretical analysis of the algorithm more tractable. In fact, we obtain a sufficient and necessary condition for the duality gap to be zero, or equivalently, for the Lagrangian relaxation approach to find the optimal solution to the assignment problem with a guarantee. Also, we establish a mild and easy-to-check condition, under which the dual problem is equivalent to the original one. In general cases, the optimal value of the dual problem can provide a satisfactory lower bound on the optimal value of the original assignment problem. Furthermore, the newly proposed approach can be extended to higher dimensional cases and general assignment problems.

Keywords: Multidimensional assignment; Binary programming; Duality; Convexification; 90C09; 90C26 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-019-00113-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:74:y:2019:i:2:d:10.1007_s10589-019-00113-w

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-019-00113-w

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().