Exact solution approaches for bilevel assignment problems

Behdad Beheshti (), Oleg A. Prokopyev () and Eduardo L. Pasiliao ()
Additional contact information
Behdad Beheshti: University of Pittsburgh
Oleg A. Prokopyev: University of Pittsburgh
Eduardo L. Pasiliao: AFRL Munitions Directorate

Computational Optimization and Applications, 2016, vol. 64, issue 1, No 8, 215-242

Abstract: Abstract We consider the bilevel assignment problem in which each decision maker (i.e., the leader and the follower) has its own objective function and controls a distinct set of edges in a given bipartite graph. The leader acts first by choosing some of its edges. Subsequently, the follower completes the assignment process. The edges selected by the leader and the follower are required to constitute a perfect matching. In this paper we propose an exact solution approach, which is based on a branch-and-bound framework and exploits structural properties of the assignment problem. Extensive computational experiments with linear sum and linear bottleneck objective functions are conducted to demonstrate the performance of the developed methods. While the considered problem is known to be NP-hard in general, we also describe some restricted cases that can be solved in polynomial time.

Keywords: Bilevel programming; Assignment problem; Combinatorial optimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-015-9799-4 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:64:y:2016:i:1:d:10.1007_s10589-015-9799-4

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

DOI: 10.1007/s10589-015-9799-4

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 ().