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

Bilevel linear programs: generalized models for the lower-level reaction set and related problems

Zare, Mohammadhosein (2018) Bilevel linear programs: generalized models for the lower-level reaction set and related problems. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

[img] PDF
Restricted to University of Pittsburgh users only until 25 September 2020.

Download (3MB) | Request a Copy

Abstract

Bilevel programming forms a class of optimization problems that model hierarchical relation between two independent decision-makers, namely, the leader and the follower, in a collaborative or conflicting setting. Decisions in this hierarchical structure are made sequentially where the leader decides first and then the follower responds by solving an optimization problem, which is parameterized by the leader's decisions. The follower's reaction, in return, affects the leader's decision, usually through shaping the leader's objective function. Thus, the leader should take into account the follower's response in the decision-making process.

A key assumption in bilevel optimization is that both participants, the leader and the follower, solve their problems optimally. However, this assumption does not hold in many important application areas because: (i) there is no known efficient method to solve the lower-level formulation to optimality; (ii) the follower either is not sufficiently sophisticated or does not have the required computational resources to find an optimal solution to the lower-level problem in a timely manner; or (iii) the follower might be willing to give up a portion of his/her optimal objective function value in order to inflict more damage to the leader.

This dissertation mainly focuses on developing approaches to model such situations in which the follower does not necessarily return an optimal solution of the lower-level problem as a response to the leader's action. That is, we assume that the follower's reaction set may include both exact and inexact solutions of the lower-level problem. Therefore, we study a generalized class of the follower's reaction sets. This is arguably the case in many application areas in practice, thus our approach contributes to closing the gap between the theory and practice in the bilevel optimization area.

In addition, we develop a method to solve bilevel problems through single-level reformulations under the assumption that the lower-level problem is a linear program. The most common technique for such transformations is to replace the lower-level linear optimization problem by its KKT optimality conditions. We propose an alternative technique for a broad class of bilevel linear integer problems, based on the strong duality property of linear programs and compare its performance against the current methods. Finally, we explore bilevel models in an application setting of the pediatric vaccine pricing problem.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: University of Pittsburgh ETD
Status: Unpublished
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Zare, Mohammadhoseinmoz3@pitt.edumoz3
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairProkopyev, Olegdroleg@pitt.edudroleg
Committee MemberOzaltin, Osmanoyozalti@ncsu.edu
Committee MemberSaure, Denisdsaure@gmail.com
Committee MemberRajgopal, Jayantgunner1@pitt.edugunner1
Committee MemberZeng, Bobzeng@pitt.edubzeng
Date: 25 September 2018
Date Type: Publication
Defense Date: 27 June 2018
Approval Date: 25 September 2018
Submission Date: 27 June 2018
Access Restriction: 2 year -- Restrict access to University of Pittsburgh for a period of 2 years.
Number of Pages: 135
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: Bilevel optimization, Mixed integer programming, Follower's reaction set, Optimistic bilevel optimization, Pessimistic bilevel optimization, Single-level reformulations
Date Deposited: 25 Sep 2018 16:11
Last Modified: 25 Sep 2018 16:11
URI: http://d-scholarship.pitt.edu/id/eprint/34682

Metrics

Monthly Views for the past 3 years

Plum Analytics


Actions (login required)

View Item View Item