On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization

\(\) We consider the theoretical computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader’s perspective. We show that, for any constant \(c > 0\), the problem of finding a leader’s solution that is within Euclidean distance \(c^n\) of any locally optimal leader’s solution, where \(n\) is the total … Read more

Finding Groups with Maximum Betweenness Centrality via Integer Programming with Random Path Sampling

One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node … Read more

Mixed Integer Bilevel Optimization with k-optimal Follower: A Hierarchy of Bounds

We consider mixed integer bilevel linear optimization problems in which the decision variables of the lower-level (follower’s) problem are all binary. We propose a general modeling and solution framework motivated by the practical reality that in a Stackelberg game, the follower does not always solve their optimization problem to optimality. They may instead implement a … Read more

Analysis of Process Flexibility Designs under Disruptions

Most of the previous studies of process flexibility designs have focused on expected sales and demand uncertainty. In this paper, we examine the worst-case performance of flexibility designs in the case of demand and supply uncertainties, where the latter can be in the form of either plant or arc disruptions. We define the Plant Cover … Read more

On robust fractional 0-1 programming

We study single- and multiple-ratio robust fractional 0-1 programming problems (RFPs). In particular, this work considers RFPs under a wide-range of disjoint and joint uncertainty sets, where the former implies separate uncertainty sets for each numerator and denominator, and the latter accounts for different forms of inter-relatedness between them. First, we demonstrate that, unlike the … Read more

A mixed-integer fractional optimization approach to best subset selection

We consider the best subset selection problem in linear regression, i.e., finding a parsimonious subset of the regression variables that provides the best fit to the data according to some predefined criterion. We show that, for a broad range of criteria used in the statistics literature, the best subset selection problem can be modeled as … Read more

Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function

We introduce a generalized value function of a mixed-integer program, which is simultaneously parameterized by its objective and right-hand side. We describe its fundamental properties, which we exploit through three algorithms to calculate it. We then show how this generalized value function can be used to reformulate two classes of mixed-integer optimization problems: two-stage stochastic … Read more

Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller … Read more

Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We fi rst derive some basic properties of value functions of quadratic integer programs. We then propose a two-phase solution approach. The first phase constructs the value functions of quadratic integer programs in both stages. The second phase … Read more

Streaming Cache Placement Problems: Complexity and Algorithms

Virtual private networks (VPN) are often used to distribute live content, such as video or audio streams, from a single source to a large number of destinations. Streaming caches or splitters are deployed in these multicast networks to allow content distribution without overloading the network. In this paper, we consider two combinatorial optimization problems that … Read more