Generalized Nash equilibrium problems with mixed-integer variables constitute an important class of games in which each player solves a mixed-integer optimization problem, where both the objective and the feasible set is parameterized by the rivals’ strategies. However, such games are known for failing to admit exact equilibria and also the assumption of all players being … Read more
We consider the central role of improving directions in solution methods for mixed integer bilevel linear optimization problems (MIBLPs). Current state-of-the-art methods for solving MIBLPs employ the branch-and-cut framework originally developed for solving mixed integer linear optimization problems. This approach relies on oracles for two kinds of subproblems: those for checking whether a candidate pair … Read more
In this paper, we investigate the partial inverse knapsack problem, a bilevel optimization problem in which the follower solves a classical 0/1-knapsack problem with item profit values comprised of a fixed part and a modification determined by the leader. Specifically, the leader problem seeks a minimal change to given item profits such that there is … Read more
Limited geographic access to obstetric care prevents some pregnant people from receiving timely and risk-appropriate services. This challenge is especially acute in rural areas, where rural residents often travel far distances to obstetric care. Furthermore, obstetric access is worsening due to the growing number of closures of rural hospitals’ obstetric units, often due to financial … Read more
Generalized Nash equilibrium problems with mixed-integer variables form an important class of games in which each player solves a mixed-integer optimization problem with respect to her own variables and the strategy space of each player depends on the strategies chosen by the rival players. In this work, we introduce a branch-and-cut algorithm to compute exact … Read more
We address the Undirected Team Orienteering Arc Routing Problem (UTOARP). In this problem, demand is placed at some edges of a given undirected graph and served demand edges produce a profit. Feasible routes must start and end at a given depot and there is a time limit constraint on the maximum duration of each route. … Read more
We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more
The multi-depot vehicle scheduling problem (MDVSP) is a critical planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. Our model guarantees service reliability measured by on-time performance (OTP), a … Read more
Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope. It models conditional relations across three sets of binary variables, where selections within two implying sets imply a choice in a corresponding implied set. We call this polytope … Read more
We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but jointly convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained … Read more