Sergey S. Ketkov

Sergey S. Ketkov, Oleg A. Prokopyev

A standard approach to solving optimistic bilevel linear programs (BLPs) is to replace the lower-level problem with its Karush-Kuhn-Tucker (KKT) optimality conditions and reformulate the resulting complementarity constraints using auxiliary binary variables. This yields a single-level mixed-integer linear programming (MILP) model involving big-$M$ parameters. While sufficiently large and bilevel-correct big-$M$s can be computed in polynomial time, verifying a priori that given big-$M$s do not cut off any feasible or optimal lower-level solutions is known to be computationally difficult. In this paper, we establish two complementary hardness results. First, we show that, even with a single potentially incorrect big-$M$ parameter, it is $coNP$-complete to verify a posteriori whether the optimal solution of the resulting MILP model is bilevel optimal. In particular, this negative result persists for min-max problems without coupling constraints and applies to strong-duality-based reformulations of mixed-integer BLPs. Second, we show that verifying global big-$M$ correctness remains computationally difficult a posteriori, even when an optimal solution of the MILP model is available.

Sergey S. Ketkov, Andrei S. Shilov

In this study we analyze linear mixed-integer programming problems, in which the distribution of the cost vector is only observable through a finite training data set. In contrast to the related studies, we assume that the number of random observations for each component of the cost vector may vary. Then the goal is to find a prediction rule that converts the data set into an estimate of the expected value of the objective function and a prescription rule that provides an associated estimate of the optimal decision. We aim at finding the least conservative prediction and prescription rules, which satisfy some specified asymptotic guarantees as the sample size tends to infinity. We demonstrate that under some mild assumption the resulting vector optimization problems admit a Pareto optimal solution with some attractive theoretical properties. In particular, this solution can be obtained by solving a distributionally robust optimization (DRO) problem with respect to all probability distributions with given component-wise relative entropy distances from the empirical marginal distributions. It turns out that the outlined DRO problem can be solved rather effectively whenever there exists an effective algorithm for the respective deterministic problem. In addition, we perform numerical experiments where the out-of-sample performance of the proposed approach is analyzed.