Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Exploiting Local Optimality and Strong Inequalities for Solving Bilevel Combinatorial and Submodular Optimization Problems

Shi, Xueyu (2022) Exploiting Local Optimality and Strong Inequalities for Solving Bilevel Combinatorial and Submodular Optimization Problems. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

PDF (XueyuShi_etdPitt2021.pdf, PhD Dissertation)
Submitted Version

Download (2MB) | Preview


Bilevel combinatorial and submodular optimization problems arise in a broad range of real-life applications including price setting, network design, information gathering, viral marketing, and so on. However, the current state-of-the-art solution approaches still have difficulties to solve them exactly for many broad classes of practically relevant problems. In this dissertation, using the concepts of local optimality and strong valid inequalities, we explore the fundamental mathematical structure of these problems and boost the computational performance of exact solution methods for these two important classes of optimization problems.
In our initial study, we focus on a class of bilevel spanning tree (BST) problems, motivated by a hierarchical (namely, bilevel) generalization of the classical minimum spanning tree problem. We show that depending on the type of the objective function involved at each level, BST can be solved to optimality either in polynomial time by a specialized algorithm or via a mixed-integer linear programming (MILP) model solvable by an off-the-shelf solver. The latter case corresponds to an NP-hard class of the problem.
Our second study proposes a hierarchy of upper and lower bounds for the bilevel problems, where the follower’s variables are all binary. In particular, we develop a generalized bilevel framework that explores the local optimality conditions at the lower level. Submodularity and disjunctive-based approach are then exploited to derive strong MILP formulations for the resulting framework. Computational experiments indicate that the quality of our newly proposed bounds is superior to the current standard approach. Furthermore, we generalize our aforementioned results for BST and show that the proposed bounds are sharp for bilevel matroid problems.
Finally, to address the computational challenges in the submodular maximization problem, we present the polyhedral study of its mixed 0–1 set. Specifically, we strengthen some existing results in the literature by finding two families of facet-defining inequalities through the lens of sequence independent lifting. We further extend the scope of this work and describe the multi-dimensional sequence independent lifting for a more complex set. The developed polyhedral results complement the classical results from the literature for the mixed0–1 knapsack and single-node flow sets.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Shi, Xueyuxus6@pitt.eduxus6
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairProkopyev, Oleg A.droleg@pitt.edudroleg
Committee CoChairZeng, Bobzeng@pitt.edubzeng
Committee MemberRajgopal,
Committee MemberRalphs, Ted
Date: 16 January 2022
Date Type: Publication
Defense Date: 27 September 2021
Approval Date: 16 January 2022
Submission Date: 31 October 2021
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 181
Institution: University of Pittsburgh
Schools and Programs: Swanson School of Engineering > Industrial Engineering
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Combinatorial optimization; Mixed-integer programming; Network optimization; Polyhedral study
Date Deposited: 16 Jan 2022 17:42
Last Modified: 16 Jan 2022 17:42


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item