Traditionally, in the bilevel optimization framework, a leader chooses her actions by solving an upperlevel problem, assuming that a follower chooses an optimal reaction by solving a lowerlevel problem. However, in many settings, the lowerlevel problems might be nontrivial, thus requiring the use of tailored algorithms for their solution. More importantly, in practice, such problems might be inexactly solved by heuristics and approximation algorithms. Motivated by this consideration, we study a broad class of bilevel optimization problems where the follower might not optimally react to the leader’s actions. In particular, we present a modeling framework in which the leader considers that the follower might use one of a number of known algorithms to solve the lowerlevel problem, either approximately or heuristically. Thus, the leader can hedge against the follower’s use of suboptimal solutions. We provide algorithmic implementations of the framework for a class of nonlinear bilevel knapsack problem (BKP), and we illustrate the potential impact of incorporating this realistic feature through numerical experiments in the context of defenderattacker problems.
A Progressive Approximation Approach for the Exact Solution of Sparse LargeScale Binary Interdiction Games
We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 01 more »
 Award ID(s):
 2039917
 Publication Date:
 NSFPAR ID:
 10342622
 Journal Name:
 INFORMS Journal on Computing
 Volume:
 34
 Issue:
 2
 Page Range or eLocationID:
 890 to 908
 ISSN:
 10919856
 Sponsoring Org:
 National Science Foundation
More Like this


Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u,p)maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u, p)maxmin strategy for these games. The first game that we consider is Colonel Blotto, a wellstudied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm formore »

We study the chanceconstrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random sizes that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a bigM and a 01 bilinear formulation of this problem. We analyze the bilinear structure of the formulation and use the lifting techniques to identify cover, clique, and projection inequalities to strengthen the formulation. We show that in certain cases these inequalities are facetdefining for a bilinear knapsack constraint that arises in the reformulation. An extensive computational study is conducted for the operating room planning problem that minimizes the number of open operating rooms. The computational tests are performed using problems generated based on real data from a hospital. A lowerbound improvement heuristic is combined with the cuts proposed in this paper in a branchandcut framework. The computations illustrate that the techniques developed in this paper can significantly improve the performance of the branchandcut method. Problems with up to 1,000 scenarios are solved to optimality in less than an hour. A safe approximation based on conditionalmore »

Adjustable robust optimization (ARO) involves recourse decisions (i.e. reactive actions after the realization of the uncertainty, ‘waitandsee’) as functions of the uncertainty, typically posed in a twostage stochastic setting. Solving the general ARO problems is challenging, therefore ways to reduce the computational effort have been proposed, with the most popular being the affine decision rules, where ‘waitandsee’ decisions are approximated as affine adjustments of the uncertainty. In this work we propose a novel method for the derivation of generalized affine decision rules for linear mixedinteger ARO problems through multiparametric programming, that lead to the exact and global solution of the ARO problem. The problem is treated as a multilevel programming problem and it is then solved using a novel algorithm for the exact and global solution of multilevel mixedinteger linear programming problems. The main idea behind the proposed approach is to solve the lower optimization level of the ARO problem parametrically, by considering ‘hereandnow’ variables and uncertainties as parameters. This will result in a set of affine decision rules for the ‘waitandsee’ variables as a function of ‘hereandnow’ variables and uncertainties for their entire feasible space. A set of illustrative numerical examples are provided to demonstrate the potential of themore »

Recent empirical evidence suggests that the WestonWatkins support vector machine is among the best performing multiclass extensions of the binary SVM. Current stateoftheart solvers repeatedly solve a particular subproblem approximately using an iterative strategy. In this work, we propose an algorithm that solves the subproblem exactly using a novel reparametrization of the WestonWatkins dual problem. For linear WWSVMs, our solver shows significant speedup over the stateoftheart solver when the number of classes is large. Our exact subproblem solver also allows us to prove linear convergence of the overall solver.