<br><br>

ABSTRACT 

For-profit service providers are offering public services in a service network, while individual providers are interested in maximizing service revenues and minimizing operational costs in their own catchment areas, leading to potential inefficiency in overall service. Government is committed to improving the aggregated societal impact in the network by offering subsidy on network redesign, which leads to possible loss for individual service provider. To balance the conflicting interests of these two parties, in this paper, we formulate a one-leader multi-follower bilevel programming (OMBP) model to investigate the subsidized network redesign problem, which considers the government as the leader and multiple disjoint service providers as followers. To solve the OMBP problem efficiently, we decompose the OMBP problem into a group of bilevel mixed integer programming (BMIP) subproblems with each BMIP problem corresponding to a follower (i.e. K followers, K subproblems). We design an exact solution method, which initially sets the total government budget as an upper bound on the subsidy allocated to each follower-specific BMIP. Then all individual followers’ subsidy upper bounds are iteratively decremented by 1 until infeasibility occurs for some follower’s problem. We store all encountered bilevel feasible solutions that occur at later iterations and compare the stored solutions to identify the optimal one. We also take the first encountered bilevel feasible solution in the above iterative algorithm as a myopic solution, which is when the total government budget can barely afford the total subsidy. Computational experiments on randomly generated instances highlight (1) sublinear scalability with respect to the number of followers for the exact algorithm; (2) computational tradeoffs between the exact solution and the myopic solution in computational time and solution quality.

BIOGRAPHY

Xinyue Yu is a first-year Ph.D. student in Industrial Engineering at Purdue University, advised by Dr. Nan Kong and Dr. Yuehwern Yih.  Her research interests include bilevel mixed-integer programming, decomposition algorithms, and optimization under multiple decision makers. She currently focuses on algorithm design for single-leader–multiple-follower bilevel problems, with potential applications in healthcare delivery and resource allocation.